2.1 写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题
(a) min z=2x1+2x2+4x3 (b) max z=5x1+6x2+3x3 s.t. x1+3x2+4x3≥2 s.t. x1+2x2+2x3=5 2x1+x2+3x3≤3 -x1+5x2-3x3≥3 x1+4x2+3x3=5 4x1+7x2+3x3≤8 x1, x2≥0, x3无约束 x1无约束,x2≥0, x3≤0
解：(a)对偶问题的原问题为 max w=2y1+3y2+5y3 s.t. y1+2y2+y3≤2 3y1+y2+4y3≤2 4y1+3y2+3y3=4
y1≥0, y2≤0, y3无约束 (b)原问题的对偶问题为 min w=5y1+3y2+8y3 s.t. y1-y2+4y3=5 2y1+5y2+7y3≥6 2y1-3y2+3y3≤3
y1无约束, y2≤0, y3≥0
2.3 已知线性规划问题：
max z=x1+x2 s.t. -x1+ x2+ x3 ≤2 -2x1+x2- x3 ≤1 x1, x2, x3≥0
试应用对偶理论证明上述线性规划问题最优解为无界。
解：原问题的对偶问题为 min w=2y1+ y2 s.t. -y1- 2y2 ≥1 2y1+ 5y2 ≥1 y1- y2 ≥0 y1, y2≥0 由于约束条件3可得 y1-y2 ≥0 → y1≥y2 → -y1≤-y2 且y2≥0 所以 -y1-2y2 ≤-3y2≤0 （1） 由于约束条件1可得 -y1- 2y2 ≥1 （2） （1）（2）不等式组无解
所以其对偶问题无可行解,又知点X=(1,1,1)为原问题一个可行解,即原问题有可行解, 现在其对偶问题无可行解。根据对偶理论性质3原问题无界.
2.4 已知线性规划问题：
max z=2x1+4x2+ x3+x4 s.t. x1+ 3x2 +x4 ≤8 2x1+ x2 ≤6 x2+ x3 +x4 ≤6 x1+ x2+ x3 ≤9 xj≥0 (j=1,…4)
要求(a)写出其对偶问题;(b)已知原问题最优解X=(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解. 解:
对偶问题: min w=8y1+ 6y2+6y3+9 y4 s.t. y1+ 2y2 +y4 ≥2 3y1+ y2 + y3 +y4 ≥4 y3+ y4 ≥1 y1 +y3 ≥1 y1, y2,y3, y4≥0
将最优解X=(2,2,4,0)代入原问题的约束条件得: x1+ 3x2 +x4 =8 2x1+ x2 =6 x2+ x3 +x4 =6 x1+ x2+ x3 =8<9
根据对偶理论性质5， 如果
?ni?1?j?bi，则y?i?0。 aijx?4?0 于是从第四个约束方程计算可有y
?j?0，则将性质5应用于其对偶问题，这时有：如果x?mi?1?i?cj aijy因为本题中x1=2 >0，x2=2>0， x3=4>0.
所以得到约束方程组（其中y4?0）
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+ x3 s.t. x1+ x2 +x3 ≤6 -x1+ 2x2 ≤4 x1, x2 ,x3≥0
先用单纯形法求出最优解，再分别就下列情形进行分析：
(a) 目标函数中变量x1, x2 ,x3的系数分别在什么范围内变化，问题的最优解不变； (b) 两个约束的右端项分别在什么范围内变化，问题的最优基不变； 解：
将此问题化成标准形式， max z=2x1-x2+x3+0x4 s.t. x1+x2+x3+x4 =6 -x1+2x2 +x5=4 x1, x2, x3, x4, x5≥0
其约束系数矩阵：
P1P2P3P4P5?11110? ??12001???
单纯形法求解的过程见表如下 单纯形法的求解过程 Cj→ 2 -1 1 0 0 CB 基 b X1 X2 X3 X4 X5 0 X4 6 [1] 1 1 1 0 0 X5 4 -1 2 0 0 1 Cj-zj 2 -1 1 0 0 由于2>1, 选择x1作为换入基的变量。对于P1有：
θ=min{ b1/a11 | a11>0 }=min{6/1 }=6. 确定x4为换出基变量。a11=1为主元素
单纯形法的求解过程 Cj→ 2 -1 1 0 CB 基 b X1 X2 X3 X4 2 X1 6 1 1 1 1 0 X5 10 0 3 1 1 Cj-zj 0 -3 -1 -2 至此，所有检验数σj≤0，表明现有对应的基可行解为最优解 x1=6, x2=0, x3=0, x4=0，x5=10。
原线性规划问题的最优解为x1=6, x2=0, x3=0, 相应目标函数值max z=2x1-x2+x2=12。
0 X5 0 1 0