运筹学第二章线性规划的对偶理论（新）a管理ppt课件.ppt

《运筹学第二章线性规划的对偶理论（新）a管理ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论第一节对偶问题的提出资源利用问题:原问题：maxz=2x1+3x2s.t2x1+2x2≤12y1≥04x1≤16y2≥05x2≤15y3≥0x1≥0x2≥0对偶问题：minw=12y1+16y2+15y3s.t2y1+4y2+0y3≥22y1+0y2+5y3≥3y1,y2,y3≥0显然，只有当maxz=minw时，该经理认为这两种方案具有相同的结果，都是最优方案。推广到一般情况，可得：原问题：maxz=c1x1+c2x2+…+cnxns.ta11x1+a12x2+…+a1nxn≤b1a21x1+a22

2、x2+…+a2nxn≤b2……am1x1+am2x2+…+amnxn≤bmx1,x2,…,xn≥0对偶问题：minw=b1y1+b2y2+…+bmyms.ta11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2…...a1ny1+a2ny2+…+amnym≥cny1,y2,…,ym≥0以上为标准对应关系。（见表2-1)代数形式：矩阵形式：原问题对偶问题第二节原问题与对偶问题的一般对应关系例1、例2.结论：LP对偶问题的对偶问题就是原问题。例3.写出下列LP的对偶问题原问题：minz=7x1+4

3、x2-3x3s.t-4x1+2x2-6x3≤24→y1≤0-3x1+x2+2x3≥15→y2≥05x2+3x3=30→y3无约束2x1-2x2+4x3≥-1→y4≥0x1≤0,x2取值无约束，x3≥0对偶问题：maxz=24y1+15y2+30y3-10y4s.t-4y1-3y2+0y3+2y4≥72y1+y2+5y3–2y4=4-6y1+2y2+3y3+4y4≤-3y1≤0,y2≥0,y3无约束,y4≥0原问题与对偶问题的一般对应关系见表2-2。作业：P782.1(b)(c)2.22.4第三节对偶问题的基本性质原问题对

4、偶问题定理1.（弱对偶性定理）若X，Y分别为LP原问题及其对偶问题的可行解，则恒有：CX≤Yb证明：对AX≤b，两端同时左乘可行解Y,得：YAX≤Yb；对YA≥C,两端同时右乘可行解X,得：YAX≥CX,从而得：CX≤Yb证毕。定理2.（最优性定理）若X，Y分别为LP原问题及其对偶问题的可行解，且有：CX=Yb则X，Y分别为LP原问题及其对偶问题的最优解。（充要条件）证明：（充分性）设X*为LP原问题的最优解，设Y*为LP对偶问题的最优解，由弱对偶性定理知：又已知故又有：因此X，Y分别为LP原问题及其对偶问题的

5、最优解。（必要性：CBB-1b）定理3.（无界性）如果原问题（或对偶问题）有无界解，则其对偶问题（或原问题）无可行解。如果原问题（或对偶问题）无可行解，则其对偶问题（或原问题）或是无可行解或是无界解。原问题对偶问题最优解最优解无界解无可行解无可行解无界解定理4.（对偶定理）若原问题有最优解，则其对偶问题也一定有最优解，且它们的最优目标函数值相等。证明：设X*是LP的最优解，它所对应的基为B，则检验数必满足：σ=C－CBB-1A≤0令Y=CBB-1(单纯形因子),则有：YA≥C，因此，Y是对偶问题的可行解。又知LP的最优目

6、标函数值为：z*=CX*=CBB-1b=Yb=w由最优性定理（定理2）可知，Y=CBB-1是对偶问题的最优解。定理5.(互补松弛定理）原问题及其对偶问题的可行解是最优解的充要条件是：证明：（必）由化成标准形式：因此可得：若和分别是原问题和对偶问题的可行解，且则必有:z=w由最优性定理可知和分别为原问题和对偶问题的最优解。（充）因为和分别为原问题和对偶问题的最优解，故：从而：又：故必有：定理6.(解的对应关系)在同一步迭代中（同一个单纯形表中），LP原问题的检验数对应于对偶问题的一个解，且目标函数值相等（z=w

7、)。其对应关系为：原问题对偶问题决策变量X松弛变量YS松弛变量XS决策变量Y基变量XB非基变量YN非基变量XN基变量YB证明:(1)由得：或写成：原问题的检验数为：(X,XS)σ=(C－CBB-1A，－CBB-1)(-YS,-Y)(2)由LP模型的矩阵表达式：写出其对偶问题：（XB,XN,XS）σ=(0，σN，σS)=(0，CN－CBB-1N，－CBB-1)=(-YS1,-YS2,-Y)CjCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1σj=cj-zj0CN-CBB-1N-CBB

8、-1CjCBCN0CBXBbXBXNXS0XSbBNIσj=cj-zjCBCN0……结论：LP原问题的检验数的相反数是其对偶问题的一个解。在最优条件下，σ=(C－CBB-1