资源描述：
《运筹学-用对偶分析原问题最优解(名校讲义).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三讲用对偶分析原问题最优解§1初步分析线性规划解的几种可能性§2线性规划解的求解方法之一：图解法§3对偶性质及平衡定理§4基础解及基础可行解§1初步分析线性规划解的几种可能性（1）已知线性规划的标准形式为AX=b,X≥O,CTX=min满足前2条的解为可行解，同时又满足第3条的为最优解。从解的性质看，线性规划有下述几种可能：1．不存在可行解或无解，例如规划x1=－１x1≥0无可行解3x1=min§1初步分析线性规划解的几种可能性（2）2．存在可行解，但找不到最优解，例如规划x1－x2=0x1，x2≥0－2x1=min显然，令x1=x2=λ,λ为任意非负值都是可行解，当λ→+
2、∞，则目标函数－2x1→∞，故找不出使目标函数取极小值的具体解X。§1初步分析线性规划解的几种可能性（3）x2101x1图1-13．存在最优解，但不是唯一的。例如规划x1+x2=1x1，x2≥ox1+x2=min显然两点连线上的所有点都是最优解，（见图1-1）4．一般情况有无穷多可行解，但有唯一最优解。§2线性规划解的求解方法之一：图解法（1）A0423214x131x2B2x1+x2=4L1L3L2图1-2[例1-3]求解下述线性规划2x1+x2－x3=4(1)xj≥0j=1,2,3(2)3x1+5x2=min(3)将(1)式中的x3移至右边，常数4移至左边，得：2x1+x
3、2－4=x3≥0移项得：2x1+x2≥4于是变为两维线性规划问题，其约束可行域可用直角坐标系表示,如图1-2。§2线性规划解的求解方法之一：图解法（2）图1-2中，阴影部分为可行域，若要求出最优点，必须作出目标函数的等值线，然后令等值线向最小值方向（即最优方向）移动，直到离开可行域的瞬间为止，此时的交点即为最优点。图中直线L1，L2，L3即为目标值分别为12，9及6的等值线，L3与可行域的顶点B（x1＝2，x2＝0），L3再向左下方移动，必离开可行域，于是该点即为线性规划之最优解，即：X＝（x1，x2，x3）=(2,0,0)，目标值为3x1+5x2＝6。图解法简单易行，但只适
4、于两维问题（本题虽是三维，但很容易变为两维）。对于高维问题，只能采用其它的办法求解。很幸运，该法已经找到，这就是以后将要介绍的单纯形法。§3对偶性质及平衡定理（1）1．弱对偶性（不等式性质）设原线性规划为AX=b，X≥0，CTX=min其对偶规划为YTA≤CT,YTb=max若X、Y分别是原问题和对偶问题的可行解，则必存在关系式CTX≥YTb证明：因为X、Y分别是原问题及对偶问题的可行解，因此YTAX=YT(AX)=YTb及YTAX=(YTA)X≤CTX故CTX≥YTb这是一个很有用的性质，因为有时并不需要精确求出线性规划问题最优解，只需了解最优目标值的范围，那么采用求解对偶
5、可行解就显得十分方便。§3对偶性质及平衡定理（2）2．强对偶性（对偶最优性）若分别是原问题与对偶问题可行解，且，则必分别是原问题及对偶问题的最优解。证明：设X是原向题任一可行解，则从弱对偶性知，，可见是原问题最优解。同理，设Y是对偶问题任一可行解，则，故是对偶问题最优解。§3对偶性质及平衡定理（3）1．平衡定理设原问题为(4)xj≥0(j=1,2,…，n)(5)(6)其对偶形式为(7)(8)§3对偶性质及平衡定理（4）则平衡定理阐述如下：若xj(j=1,2…，n)和yi（i=1,2,…，m）分别是原问题和对偶问题之可行解，必存在下述关系：（即弱对偶性）上式中两边相等的充分必要
6、条件是：或xj=0或xj>0,但①②§3对偶性质及平衡定理（5）证明①：根据(5)式和(7)式可得：(9)§3对偶性质及平衡定理（6）证明②：若使，即表明(9)式左边为0（不等式变为等式），而该式是由n项和组成，每一项是两因子乘积，每个因子都≥0。故每一项都≥0。若使n项为0，势必使每一项为0，即：则其中至少有一个因子为0。于是得出，或xj=0；或xj>0，必使。§3对偶性质及平衡定理（7）从强对偶性知，符合平衡定理第②条时的可行解X，Y必是最优解，于是，平衡定理为寻找线性规划最优解提供了一种方法。亦即，在若干个问题的可行解X中，若是有一组解所对应的对偶可行解，使得Xj>0所
7、对应的对偶约束条件为等式，则此时的解必为最优解。[例1-4]应用平衡定理解下述规划§3对偶性质及平衡定理（8）其对偶形式为首先令原问题中任两个变量为0（因有2个约束条件，这样可求出唯一解），试探求出一组原问题可行解。例如，令x1=x4=0，则得：§3对偶性质及平衡定理（9）故此时X=(0,2,3,0)T是原问题可行解。为检验是否为最优解，令非零xj对应的对偶约束为等式，求平衡解Y。即令将y1,y2值代入式(12)及式(15)，看是否满足。-5+1=-4≤12+9=11≤13全满足，可见Y是符合平衡定理的
