线性规划的对偶问题
Docume
t
umber：NOCGYUNOOBUYTTUU9861986UT
f第二章线性规划的对偶问题
习题
写出下列线性规划问题的对偶问题
1maxz＝10x1＋x2＋2x32maxz＝2x1＋x2＋3x3＋x4
stx1＋x2＋2x3≤10
stx1＋x2＋x3＋x4≤5
4x1＋x2＋x3≤20
2x1－x2＋3x3＝－4
xj≥0（j＝123）
x1－x3＋x4≥1
x1，x3≥0，x2，x4无约束
3mi
z＝3x1＋2x2－3x3＋4x44mi
z＝－5x1－6x2－7x3
stx1－2x2＋3x3＋4x4≤3
st－x1＋5x2－3x3≥15
x2＋3x3＋4x4≥－5
－5x1－6x2＋10x3≤20
2x1－3x2－7x3－4x4＝2＝
x1－x2－x3＝－5
x1≥0，x4≤0，x2，，x3无约束
x1≤0，x2≥0，x3无约束
已知线性规划问题maxz＝CX，AXb，X≥0。分别说明发生下列情况时，其对偶问
题的解的变化：
（1）问题的第k个约束条件乘上常数λ（λ≠0）；
（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；
（3）目标函数改变为maxz＝λCX（λ≠0）；
（4）模型中全部x1用3x1代换。已知线性规划问题mi
z＝8x1＋6x2＋3x3＋6x4
stx1＋2x2＋x4≥3
3x1＋x2＋x3＋x4≥6
fx3＋x4＝2x1＋x3≥2
xj≥0（j＝1234）1写出其对偶问题；2已知原问题最优解为x＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。已知线性规划问题mi
z＝2x1＋x2＋5x3＋6x4对偶变量
st2x1＋x3＋x4≤8y12x1＋2x2＋x3＋2x4≤12y2xj≥0（j＝1234）
其对偶问题的最优解y14；y21，试根据对偶问题的性质，求出原问题的最优解。考虑线性规划问题maxz＝2x1＋4x2＋3x3
st3x1＋4x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80
xj≥0（j＝123）（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。
f已知线性规划问题maxz＝10x1＋5x2
st3x1＋4x2≤9
5x1＋2x2≤8
xj≥0（j＝12）
用单纯形法求得最终表如下表所示：
x1
x2
0
x1
1
jcjZj
0
x2
x3
x4
b
1
3
14
0
1
1
7
0
5
25
14
14
试用灵敏度分析的方法分别判断：
（1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变；
（2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述
最优基保持不变；
（3）问题的目标函数变为maxz＝12x1＋4x2时上述最优解的变化；
（4）约束条件右端项由

98

变为1191
时上述最优解的变化。
线性规划问题如下：maxz＝5x1＋5x2＋13x3
stx1＋x2＋3x3≤20①
12x1＋4x2＋10x3≤90②
xj≥0r