由互补松弛定理得：在对偶问题中对应第一，二个约束为紧，第三个约束条件为松，即，
**?y1+2y2=2*
?y1=4?*?*
?y1+3y2=1??*
?y2=1?*?*
?2y1+4y2≥3
∴对偶规划问题的最优解 y1*= （4，1）
（3）影子价格为 y1 = 4 ：
8、已知线性规划问题
maxz=x1+2x2+3x3+4x4 s.t. x1+3x2+2x3+3x4≤20 2x1+x2+3x3+2x4≤20 xj≥0(j=1,L,4)
**
=1.2,y2=0.2， 其对偶问题的最优解为y1试根据对偶理论求出原问题的最优解.
解：先写出其对偶问题。 minw=20y１+20y２st. y１+2y２≥1
3y１+y２≥2+8y≥3 2y2y+3y1１2２3y１+2y２≥4
y１≥0，y２≥0∴对偶规划问题的最优解
**
y1=1.2，y２=0.2，代入约束条件，知第1，2约束条件成立严格不等式，**由互补松弛定理，原规划最优解中相应变量x1=x2=0**又Qy1，y2不为0，则在原问题规划中对应的约束条件为紧，得
*
?x3=4?2x3+3x4=20??
??*?
??3x3+2x4=20??x4=4
∴原对偶规划问题的最优解 x*= （0,0,4,4）
6
9、已知某线性规划问题的最优单纯形表如表2-2所示，表中x4,x5为松弛变量，问题的约束为≤形式
(1) 写出原线性规划问题； (2) 写出原问题的对偶问题；
(3) 直接由表2-2写出对偶问题的最优解. 解：
?1/2 0??10?
（1）由表知B?； Ｉ=???
01?1/6 1/3????
?x11x12??1/2?
= B-1N=?令B??则?
??1/2??x21x22?
-1
表2-2
xBx10 1 0
x21/2-1/2-4
x3
1 0 0
x4
1/2
x5
0
b
5/2
x3
x1
-1/6 1/3 5/2-4
-2
0??x11x12??10??1/2?20?
=?B B-1B=?=????x???x?1/61/30113???2122?????0??a??1/2??1/2?1?
N=?= B-1N=????????
??1/2???1/61/3??b???1?
1 2??0 ?5/2??5?-1
∴A=??；Bb=???b=??
?3 1 15/2?????10?
0??C1=6?1/2
（C3，C1）（4，2）?=??? ???
1/61/3C10?=???3?1?
C2+（?4，-2）??=?4?C2=?2
?-1?
原线性问题为：∴ maxz=6x1?2x2+10x3 st. x2+2x3 5≤ 3x1?x2+x3 ≤10 xi(i=1,2,3)≥0
minw=5y１+10y２（2）st. 3y２≥6 y１?y２≥?2 2y１+y２≥10 y１≥0，y２≥0
7
（3）x*=(5/2，0，5/2)T； Z*=40; x4=x5=0 y3=y5=0?3y2 ＝6?y１=4??
??? 即?y１y＝2 ?y?y２=2 ２４
?2y+y =10?y=4?１２? 4
T*
Y*=（4，2） w=40；
10、某厂拟生产甲、乙、丙三种产品，都需要在A、B两种设备上加工，有关数据如表2-3所示.
(1) 如何充分发挥设备能力，使产品总产值最大？
(2) 若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？
解：（1）设x1，x2，x3分别表示甲、乙、丙各产品的数量，Z 表示总产值则：
maxz=3x1+2x2+x3
≤400st. x1+2x2+x3 2x1+x2+2x3 ≤500 xi(i=1,2,3)≥0化为标准形： maxz=3x1+2x2+x3
=400st. x1+2x2+x3 +x4 2x1+x2+2x3+x5 =500 xi(i=1,2,3，4，5)≥0C CB
XB
3 2 X1X21 2 2
1
1 0 X3
X4
0 X50 1 0
400 500 b
产品 设备 A B 产值(千元/件)表2-3 单耗（台时/件） 设备有效 甲 乙 丙 台时（每月）1 2 3 2 1 2 1 2 1 400 500 0 X40 X5
1 1 2 0 1 0
检验数 3 2 0 X4
0 3/20 1 -1/2150
8
3 X11 1/2 1 0 1/2 250 -3/2250
检验数 0 1/2 -20 2 X23 X1
0 1 1 0
0 2/3 -1/3100 1 -1/3 2/3 200 -2-1/3 -4/3-800
检验数 0 0
x*=(200,100)T； Z*=800; （2）原问题的对偶问题为 minw=400y１+500y２ st. y１+2y２≥3 2y１+y２≥2 y１+2y２≥1 y１≥0，y２≥0
此时，y1，y2分别表示出租A，B设备所得利润，
*
由（1）中的最优表得y1=1/3，即如出租A设备可获得1000/3元，而1000/3<350
所以不合算。
11、已知某实际问题的线性规划模型为
maxz=∑cjxj
j=1n
s.t. ∑aijxj≤bi
j=1
n
(i=1,2,L,m)
xj≥0(j=1,2,L,n) 若第i项资源的影子价格为yi(i=1,2,L,m)
(1) 若第一个约束条件两端乘以2，变为 ∑(2aij)xj≤2bi，
j=1n
?1是对应于这个新约束条件的影子价格，求y?1与y1的关系； y
9
(2) 令x'1=3x1，用x'1/3替换模型中所有的x1，问影子价格yi是否变化？若x1不可能在最优基中出现，问x'1是否可能在最优基中出现；
(3) 如果目标函数变为
maxz=∑2cjxj
j=1n
问影子价格有何改变？ (4) 如果模型中约束条件变为 ∑aijxj=bi
j=1n
i=1,2,L,m
问(1)、(2)、(3)中的结论是变化?
解：（1）由影子价格的定义可得：
?Z∧?Z
，y1=y1='而b1'=2b1?b1?b1
∧
∴y1=
1
y1；2
（2）由（1）可知y1只与bi的值有关∴当x1的系数由3变为x’的系数1/3时，yi的值并不发生变化；
∵x1不可能在最优基中出现，∴ x’也不可能在最优基中出现
z=∑CJXj=∑biyi=w
j=1
j=1
n
n
（3）∵当目标函数由z=∑CJXj变为z=∑2CJXj时，Cj增大了两倍∵
j=1
j=1
nn
∴影子价格yi也增大了两倍。（4）分别相同。
12、用对偶单纯形法求解下列线性规划问题：
(1) minz=10x1+5x2+4x3 s.t. 3x1+2x2?3x3≥3
10
运筹学 线性规划的对偶理论复习题
