第二章 线性规划的对偶理论
习 题
1、某厂生产A、B、C三种产品，每种产品要
表2-1
经过Ⅰ、Ⅱ、Ⅲ三道工序加工，设每件产品在每道工序上加工所消耗的工时，每道工序可供利用的工时上限，以及每件产品的利润如表2-1所示.
试列出使总利润最大的线性规划模型，并写出它的对偶问题，同时，就这个对偶问题作出经济上的解释.
消 工序 耗 产品 A B C 可用工时Ⅰ34260Ⅱ Ⅲ 2 1 2 1 3 3 单件 利润 （元）200 300 250 40 20 解：设x1，x2，x3分别表示A、B、C各产品的数量，Z 表示总产值则：
maxz=200x1+300x2+250x3st. 3x1+4x2+2x3 ≤60≤40 2x1+x2+2x3
x1+3x2+3x3 ≤20 xi(i=1,2,3)≥0原问题的对偶问题为
minw=60y１+40y２+20y３ st. 3y１+2y２+y３≥200 ４y１+y２+3y３≥300 2y１+2y２+3y３≥250 y１≥0，y２≥0，y３≥0
经济解释：y1，y2，y3分别表示给别人代工时所得收入，对厂方而言，w越大越好，但定价不能太高，要对方容易接受，应考虑使总收入即对方的总支出尽可能少才比较合理，厂方不会吃亏，对方也容易接受。
2、写出下列线性规划问题的对偶问题： (1) maxz=10x1+x2+2x3 s.t. x1+x2+2x3≤10
x1+x2+x3≤20
1
xj≥0(j=1,2,3)
解：minw=10y１+20y２st. y１+y２≥10 y１+y２≥1
2y１+y２≥2 y１≥0，y２≥0
(2) minz=2x1+2x2+4x3 s.t. 2x1+3x2+5x3≥2
3x1+x2+7x3≤3 x1+4x2+6x3≤5
xj≥0(j=1,2,3)
解：maxw=2y１+3y２+5y３st. 2y１+3y２+y３≤2 3y１+y２+4y３≤2
5y１+7y２+6y３≤4 y１≥0，y２≤0，y３≤0
(3) maxz=5x1+6x2+3x3 s.t. x1+2x2+2x3=5
?x1+5x2?x3≥3 4x1+7x2+3x3≤8
x1无约束，x2≥0，x3≤0解：minw=5y１+3y２+8y３st. y１?y２+4y３=5 2y１+5y２+7y３≥6
2y１?y２+3y３≤3 y１自由，y２≤0，y３≥0
(4) minz=3x1+2x2?3x3+4x4 s.t. x1?2x2?3x3+4x4≤3
2
x2+3x3+4x4≥?5 2x1?3x2?7x3?4x4=2 x1≥0,x4≤0,x2,x3无约束
解：
maxw=3y１?5y２+2y３st. y１+2y２≤3
-2y１+5y２?3y３＝2 -3y１+3y２?7y３＝-3 4y１+4y２?4y３≥4 y１≤0，y２≥0，y３≤0
3、应用对偶理论证明线性规划问题. maxz=x1+x2 s.t. ?x1+x2+x3≤2 ?2x1+x2?x3≤1 x1,x2,x3≥0 有可行解，但无最优解.
?0?
? 是线性问题的可行解，即该问题存在可行解； 证明：x=?0???0???
又∵其对偶问题为：
minw=2y１+y２st. -y１?2y２≥1
y１+y２≥1 y１?y２≥0 y１≥0，y２≥0
∵y１,y２≥0∴-y１?2y２≤0这与约束条件（）不符1∴该对偶问题无可行解∴原问题无最优解。
4、应用弱对偶定理，证明线性规划问题
3
maxz=x1+2x2+x3 s.t. x1+x2?x3≤2 x1?x2+x3=1 2x1+x2+x3≥2 x1≥0,x2≤0,x3无约束 的最大值不超过1. 证明：该线性问题的对偶问题为：
minw=2y１+y２+2y３st. y１+y２+2y３≥1 y１?y２+y３≤2 -y１+y２+y３=1
y１≥0，y２自由，y３≤0
由对偶问题的对偶定理可得：?0?
??
cx0≤y0b=?1?(2,1,2)=1
?0???
∴maxz≤1 即最大值不超过1
T易知Y=（0，是对偶问题的一个可行解，1，0）
5、应用对偶理论，证明线性规划问题
maxz=3x1+2x2 s.t. ?x1+2x2≤4 3x1+2x2≤14 x1?x2≤3 x1,x2≥0 有最优解，并证明其对偶问题也有最优解. 证明：对偶问题
4
minw=4y１+14y２+3y３st. -y１+3y２+y３≥3
2 2y１+2y２?y３≥4
y１≥0，y２≥0，y３≥0
T
由题易知X=（3，0）是原问题的一个可行解，T Y=（0，1，0）是对偶问题的一个可行解
由对偶问题的推论2?3可得它们都有最优解。即得证。
6、已知标准线性规划问题
maxz=cx s.t. Ax = b x≥0
具有最优解，假设将右端向量b改为另一向量d，如果改变后的问题是可行的，试证该问题一定有最优解.
7、考虑下列原始线性规划
maxz=2x1+x2+3x3 s.t. x1+x2+2x3≤5 2x1+3x2+4x3=12 xj≥0(j=1,2,3)
(1) 写出其对偶问题；
(2) 已知（3,2,0）是上述原始问题的最优解，根据互补松弛定理，求出对偶
问题的最优解；
(3) 如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格.
解：（1）对偶问题：
minw=5y１+12y２st. y１+2y２≥2 y１+3y２≥1 2y１+4y２≥3 y１≥0，y２无符号限制
2，0)T； （2）由题知原问题的最优解为x*=(3，
5
运筹学 线性规划的对偶理论复习题
