资源描述:
《运筹学-用对偶分析原问题最优解(名校讲义).ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第三讲用对偶分析原问题最优解§1初步分析线性规划解的几种可能性§2线性规划解的求解方法之一:图解法§3对偶性质及平衡定理§4基础解及基础可行解§1初步分析线性规划解的几种可能性(1)已知线性规划的标准形式为AX=b,X≥O,CTX=min满足前2条的解为可行解,同时又满足第3条的为最优解。从解的性质看,线性规划有下述几种可能:1.不存在可行解或无解,例如规划x1=-1x1≥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是符合平衡定理的