线性规划的对偶理论.docx

2.1写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题

(a)minz=2x1+2x2+4x3 (b)maxz=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)对偶问题的原问题为
maxw=2y1+3y2+5y3
s.t.y1+2y2+y3≤2
3y1+y2+4y3≤2
4y1+3y2+3y3=4
y1≥0,y2≤0,y3无约束

(b)原问题的对偶问题为
minw=5y1+3y2+8y3
s.t.y1-y2+4y3=5
2y1+5y2+7y3≥6
2y1-3y2+3y3≤3
y1无约束,y2≤0,y3≥0

2.3已知线性规划问题：
maxz=x1+x2
s.t.-x1+x2+x3 ≤2
-2x1+x2-x3 ≤1
x1,x2,x3≥0
试应用对偶理论证明上述线性规划问题最优解为无界。

解：原问题的对偶问题为
minw=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已知线性规划问题：
maxz=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),试根据对偶理论,直接求出对偶问题的最优解.

解:
对偶问题:
minw=8y1+6y2+6y3+9y4
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， 如果，则。
于是从第四个约束方程计算可有

将性质5应用于其对偶问题，这时有：如果，则
因为本题中x1=2>0，x2=2>0，x3=4>0.

所以得到约束方程组（其中）
y1+2y2 +y4 =2
3y1+y2+ y3+ y4 =4
y3+ y4 =1
解此方程组得Y=(4/5,3/5,1,0).（对偶问题的最优解）

2.8已知线性规划问题：
maxz=2x1-x2+x3
s.t.x1+x2+x3 ≤6
-x1+2x2 ≤4
x1,x2,x3≥0
先用单纯形法求出最优解，再分别就下列情形进行分析：
目标函数中变量x1,x2,x3的系数分别在什么范围内变化，问题的最优解不变；
两个约束的右端项分别在什么范围内变化，问题的最优基不变；

解：
将此问题化成标准形式，
maxz=2x1-x2+x3+0x4
s.t.x1+x2+x3+x4=6
-x1+2x2 +x5=4
x1,x2,x3,x4,x5≥0

其约束系数矩阵：

单纯形法求解的过程见表如下
单纯形法的求解过程Cj→2-1100CB基bX1X2X3X4X50X46[1]11100X54-12001Cj-zj2-1100
由于2>1,选择x1作为换入基的变量。对于P1有：
θ=min{b1/a11|a11>0}=min{6/1}=6.确定x4为换出基变量。a11=1为主元素

单纯形法的求解过程Cj→2-1100CB基bX1X2X3X4X52X16111100X51003111Cj-zj0-3-1-20
至此，所有检验数σj≤0，表明现有对应的基可行解为最优解
x1=6,x2=0,x3=0,x4=0，x5=10。
原线性规划问题的最优解为x1=6,x2=0,x3=0,
相应目标函数值maxz=2