线性规划的对偶理论

1、2.1写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题(a) min z=2x1+2x:+4x3s. t. Xi+3xc+4x322xi+x：+3xsW3 Xi+4x：+3x5=5Xu X：0, Xs无约朿解：(a)对偶问题的原问题为max w=2y,+3yu+5yss. t. y,+2*+ysW23y,+y：+4ysW24y,+3yb3ys=4y,$0,ys 无约朿(b) 原问题的对偶问题为min w=5y,+3yb8yss t. yi-y2+43=52yi+5y3+7y362yL3y：+3ysW3y,无约束，y：W0, ysMO(b) max z=5xi+6x2-r3x3s.

2、t Xi+2xc+2x3=5 -x：+5x：-3x334x,+7x：+3xs8x：无约束，x：0, xWO2.3已知线性规划问题：max z=Xi+x：s. t -Xi+ xs+ xs W2-2xi+x：-及 W1Xu x:, Xs $0试应用对偶理论证明上述线性规划问题最优解为无界。解：原问题的对偶问题为min w=2y：+ y：s t-y】-2y2 Ml2yt+ 5y： 21y： $0yi, y*0由于约束条件3可得yi-yz 20 yiy： -* 一且 y：0所以-yi2y： W-3ytW0（1）由于约束条件1可得-y - 2y2 1（2）（1）（2）不等式组无解所以其对偶问题无可行解，

3、又知点X二（1, 1, 1）为原问题一个可行解，即原问题有可行解,现在英对偶问题无可行解。根拯对偶理论性质3原问题无界.2.4已知线性规划问题：max z=2xx+4x+ x3+xiXi+ 3xs+xi W82xi+ x：W6X2+ Xs+x： W6X1+ X：+ XsW9冷20 (j=l, -4)要求G）写出其对偶问题；（b）已知原问题最优解X=（2, 2, 4, 0）,试根据对偶理论，直接求出对 偶问题的最优解.解：对偶问题：min w=8ys+ 6y：-r6ys+9yts t y,+ 2ys+yi$23yi+ y： + y3+yi4ys+y21yi+*21yi, y=, yo, yiO将

4、最优解X二（2, 2, 4, 0）代入原问题的约朿条件得:Xi+ 3x：+x：=82xx+ x：=6X:+ Xs+xi =6x,+ x：+x3=80,则夠必=勺 因为本题中也二2 0,丘二20,xo=40.所以得到约束方程组（英中y4=0）yi+ 2y：+y4 =23yi+ y: + y3+ yt =4y$+ yi =1解此方程组得Y=（4/5 ,3/5 , 1, 0）.（对偶问题的最优解）2.8已知线性规划问题：max z=2xi-xc+ xsS t Xi+ Xc +xs W6-Xi+ 2xc W4Xu X： , Xso先用单纯形法求岀最优解，再分別就下列情形进行分析：(a) 目标函数中变,

5、x3的系数分别在什么范围内变化，问题的最优解不变:(b) 两个约束的右端项分别在什么范用内变化，问题的最优基不变：解：将此问题化成标准形式，max z=2x1-x:+x3+0x1S t X1+X2+X3+X4=6_Xi+2x：+x5=4Xi, x2, x3, Xi, X0OPP P p、其约束系数矩阵：1 1 i i4 o_?-1200 1单纯形法求解的过程见表如下单纯形法的求解过程Cj-2-1100C3基bXIX2X3X4X50X46111100X54T2001Cj-zj2-1100由于21,选择X作为换入基的变量。对于匕有：0 =min bi/au an0 =min6/l 二6确定x(为换

6、出基变量。二1为主元素单纯形法的求解过程Cj-2-1100G基bXIX2X3X4X52XI6111100X51003111Cj-zj0-3-1-20至此，所有检验数。jWO,表明现有对应的基可行解为最优解 xK, x:=0, x3=0, Xi二0, x5=10o原线性巫划问题的最优解为孤二6, x2=0, x3=0,相应 U 标函数值 max Z=2xi-X：+X2=12o)若要LI标函数中变量x: ,x3的系数变化，而问题的最优解不变 分析下面已知线性规划问题：max z= (2+ X x) xi+ (-1+ X ：) -x=+ (1+ X s) xsS t Xi+ Xc +xs W6-Xi

7、+ 2xc W4Xu X： , XsoX,和m分别在什么范囤变化，问题的最优解不变解：当X X 3=0时上述线性规划问题的最终单纯性表为Cjf2+ X x-1100c3基bXIX2X3X4X52+ X1XI6111100X51003111Cj-zj03 入 1-1-X1一2 - A i0要使所有检验数。jWO,则需-3-xwo, -1-XW0, -2+ xx W0 解得当X x= X 3=0时上述线性规划问题的最终单纯性表为Cj2-1+X2100C3基bXIX2X3X4X52XI6111100X51003111Cj-zj0入：3-1-20要使所有检验数。jWO,则需X-3W0,解得X=3o 当

8、Xx=X ：=0时上述线性规划问题的最终单纯性表为Cj 一2-1l+x300G基bXIX2X3X4X52XI6111100X51003111Cj-zj0-3X 31-20要使所有检验数。jWO,则需X-1W0,解得XWl。综合上述结果：c1+X12-l=l, 6+XW-1+3二2, C3+XWI+I二2,即s x= ,X3的系数分别在Ml, W2, W2范围内，问题的最优解不变。(b)Cj-2-1100C3基bXIX5X2X3X4Xo2XI61011100X510013111Cj-zj00-3-1-20有这个线性规划问题最终单纯性表可知：B =(R 4) 为方便改写初始单纯性表：Cj-20-1100c3基bXIX5X2X3X4X50X461011100X54T12001Cj-zj20-1100所以B =1 0-1 1.分析下而已知线性规划问题：max z=2x：-Xc+ X 3) x3S t X1+ Xc +xs W6+ X i一 Xi+ 2xc4+ X 2X“