第二章线性规划的对偶理论

2.1 写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题(a) min z=2x1+2x2+4x3(b) max z=5x1+6x2+3x3s.t. x1+3x2+4x32s.t. x1+2x2+2x3=52x1+x2+3x33-x1+5x2-3x33x1+4x2+3x3=54x1+7x2+3x38x1, x20, x3无约束x1无约束,x20, x30解：(a)对偶问题的原问题为max w=2y1+3y2+5y3s.t. y1+2y2+y32 3y1+y2+4y32 4y1+3y2+3y3=4y10, y20, y3无约束(b)原问题的对偶问题为min w=5y1+3y2+8y3s.t. y1-y2+4y3=5 2y1+5y2+7y36 2y1-3y2+3y33y1无约束, y20, y302.3 已知线性规划问题：max z=x1+x2s.t. -x1+ x2+ x32-2x1+x2- x31x1, x2, x30试应用对偶理论证明上述线性规划问题最优解为无界。解：原问题的对偶问题为min w=2y1+ y2s.t. -y1- 2y2 1 2y1+ 5y2 1 y1- y2 0 y1, y20由于约束条件3可得y1-y2 0 y1y2 -y1-y2 且y20所以-y1-2y2 -3y20（1）由于约束条件1可得-y1- 2y2 1（2）（1）（2）不等式组无解所以其对偶问题无可行解,又知点X=(1,1,1)为原问题一个可行解,即原问题有可行解,现在其对偶问题无可行解。根据对偶理论性质3原问题无界.2.4 已知线性规划问题：max z=2x1+4x2+ x3+x4s.t. x1+ 3x2 +x482x1+ x26 x2+ x3 +x46x1+ x2+ x39xj0 (j=1,4)要求(a)写出其对偶问题;(b)已知原问题最优解X=(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解.解:对偶问题:min w=8y1+ 6y2+6y3+9 y4s.t. y1+ 2y2 +y42 3y1+ y2 +y3 +y4 4 y3+ y4 1y1 +y3 1 y1, y2,y3, y40将最优解X=(2,2,4,0)代入原问题的约束条件得:x1+ 3x2 +x4=82x1+ x2=6x2+ x3 +x4=6x1+ x2+ x3=80，x2=20， x3=40.所以得到约束方程组（其中）y1+ 2y2 +y4=2 3y1+ y2 +y3+ y4=4 y3+ y4 =1解此方程组得Y=(4/5 ,3/5 , 1, 0).（对偶问题的最优解）2.8 已知线性规划问题：max z=2x1-x2+ x3s.t. x1+ x2 +x36-x1+ 2x24x1, x2 ,x30先用单纯形法求出最优解，再分别就下列情形进行分析：(a) 目标函数中变量x1, x2 ,x3的系数分别在什么范围内变化，问题的最优解不变；(b) 两个约束的右端项分别在什么范围内变化，问题的最优基不变；解：将此问题化成标准形式，max z=2x1-x2+x3+0x4s.t. x1+x2+x3+x4 =6-x1+2x2 +x5=4x1, x2, x3, x4, x50其约束系数矩阵：单纯形法求解的过程见表如下单纯形法的求解过程Cj2-1100CB基bX1X2X3X4X50X46111100X54-12001Cj-zj2-1100由于21, 选择x1作为换入基的变量。对于P1有：=min b1/a11 | a110 =min6/1 =6. 确定x4为换出基变量。a11=1为主元素单纯形法的求解过程Cj2-1100CB基bX1X2X3X4X52X16111100X51003111Cj-zj0-3-1-20至此，所有检验数j0，表明现有对应的基可行解为最优解x1=6, x2=0, x3=0, x4=0，x5=10。原线性规划问题的最优解为x1=6, x2=0, x3=0,相应目标函数值max z=2x1-x2+x2=12。(a)若要目标函数中变量x1, x2 ,x3的系数变化，而问题的最优解不变分析下面已知线性规划问题：max z=（2+1）x1+（-1+2）-x2+（1+3） x3s.t. x1+ x2 +x36-x1+ 2x24x1, x2 ,x301，2和3分别在什么范围变化，问题的最优解不变解：当2=3=0时上述线性规划问题的最终单纯性表为Cj2+1-1100CB基bX1X2X3X4X52+1X16111100X51003111Cj-zj0-3-1-1-1-2-10要使所有检验数j0，则需-3-10，-1-10，-2+1 0解得1-1。当1=3=0时上述线性规划问题的最终单纯性表为Cj2-1+2100CB基bX1X2X3X4X52X16111100X51003111Cj-zj02-3-1-20要使所有检验数j0，则需2-30，解得23。当1=2=0时上述线性规划问题的最终单纯性表为Cj2-11+300CB基bX1X2X3X4X52X16111100X51003111Cj-zj0-33-1-20要使所有检验数j0，则需3-10，解得31。综合上述结果：c1+12-1=1，c2+2-1+3=2， c3+31+1=2，即x1, x2 ,x3的系数分别在1，2，2范围内，问题的最优解不变。（b）Cj2-1100CB基bX1X5X2X3X4X52X161011100X510013111Cj-zj00-3-1-20有这个线性规划问题最终单纯性表可知：为方便改写初始单纯性表：Cj20-1100CB基bX1X5X2X3X4X50X461011100X54-112001Cj-zj20-1100所以分析下面已知线性