资源描述：
《运筹学第二章-线性规划的对偶理论(新)a管理精品资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性规划的对偶理论第一节对偶问题的提出资源利用问题:原问题：maxz=2x1+3x2s.t2x1+2x2≤12y1≥0 4x1≤16y2≥0 5x2≤15y3≥0 x1≥0x2≥0对偶问题：minw=12y1+16y2+15y3s.t2y1+4y2+0y3≥2 2y1+0y2+5y3≥3 y1,y2,y3≥0显然，只有当maxz=minw时，该经理认为这两种方案具有相同的结果，都是最优方案。推广到一般情况，可得： 原问题：maxz=c1x1+c2x2+…+cnxns.ta11x1+a12x2+…+a1nxn≤b1a21x1+
2、a22x2+…+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
3、=7x1+4x2-3x3s.t-4x1+2x2-6x3≤24→y1≤0 -3x1+x2+2x3≥15→y2≥0 5x2+3x3=30→y3无约束2x1-2x2+4x3≥-1→y4≥0 x1≤0,x2取值无约束，x3≥0对偶问题：maxz=24y1+15y2+30y3-10y4s.t-4y1-3y2+0y3+2y4≥7 2y1+y2+5y3–2y4=4 -6y1+2y2+3y3+4y4≤-3 y1≤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是对偶问题的可行解。
6、又知LP的最优目标函数值为：z*=CX*=CBB-1b=Yb=w由最优性定理（定理2）可知，Y=CBB-1是对偶问题的最优解。定理5.(互补松弛定理） 原问题及其对偶问题的可行解是最优解的充要条件是： 证明：（必）由 化成标准形式：因此可得：若和分别是原问题和对偶问题的可行解，且 则必有:z=w由最优性定理可知和分别为原问题和对偶问题的最优解。 （充）因为和分别为原问题和对偶问题的最优解，故： 从而： 又： 故必有：定理6.(解的对应关系)在同一步迭代中（同一个单纯形表中），LP原问题的检验数对应于对偶问题的一个解，且目
7、标函数值相等（z=w)。其对应关系为： 原问题对偶问题 决策变量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-C
8、BB-1N-CBB-1CjCBCN0CBXBbXBXNXS0XSbBNIσj=cj-zjCBCN0……结论：LP原问题的检验数的相反数是其对偶问题的一个解。 在最优条件下，σ=(C－CBB-1A)≤0其相反数则为对偶问题的一个可行解， 且z=w。此
