下载文档原格式
第二章 对偶问题与灵敏度分析一、写出下列线性规划的对偶问题1、P89,(a)321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++.,0,;534;332;243321321321321无约束x x x x x x x x x x x x解：原模型可化为321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≥≥++.,0,;534;3-3--2-;243321321321321321无约束x x x y y y x x x x x x x x x 于是对偶模型为321532m ax y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+-≤+-.,0,;4334;243;22321321321321无约束y y y y y y y y y y y y2、P89,(b)321365m ax x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++.0,0,;8374;35;522321321321321x x x x x x x x x x x x 无约束解：令033≥-='x x 原模型可化为321365m ax x x x Z '-+=⎪⎪⎩⎪⎪⎨⎧≥'≥≤'+≤'='+.0,0,;83-74;3--5-;52-2321321321321321x x x y y y x x x x x x x x x 无约束于是对偶模型为321835m in y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥-≥---≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束 或⎪⎪⎩⎪⎪⎨⎧≥≤++≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束二、灵敏度分析1、P92, 线性规划问题213m ax x x Z += ⎪⎩⎪⎨⎧≥≤+≤+0,1025;74212121x x x x x x最优单纯形表如下试用灵敏度分析的方法，分析：（1） 目标函数中的系数21,c c 分别在什么范围内变化，最优解不变（2） 约束条件右端常数项21,b b 分别在什么范围内变化，最优基保持不变解：（1） 1c 的分析：要使得最优解不变，则需⎪⎪⎩⎪⎪⎨⎧≤⨯-⨯+=≤⨯+⨯-=034131003513201413c c σσ 即 ⎪⎩⎪⎨⎧≤≥42511c c 所以：4251≤≤c 时可保持最优解不变。
第二章 对偶理论与灵敏度分析练习题答案1．判断下列说法是否正确：(1) 任何线性规划问题存在并具有惟一的对偶问题；(✓)(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(✗)(3) 设j ˆx ，i ˆy 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m**j j j j i i i i j 1j 1i 1i 1ˆˆc x c x b y b y ====≤=≤∑∑∑∑；(✓)(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；(✓)(5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(✓)(6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(✗)(7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；(✗)(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；(✓)(9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；(✗)(10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。
(✓)2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。
要求：(1)(3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。
一、选择题
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
二、判断题
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
三、写出下列线性规划问题的对偶问题
123
12312
3123123(1)2242352
373..465,,0
Min Z x x x x x x x x x s t x x x x x x =++++≥⎧⎪++≤⎪⎨++≤⎪⎪≥⎩ 对偶问题：123
12312
3123123()235232342..57640,,0
a MaxW y y y y y y y y y s t y y y y y y =++++≤⎧⎪++≤⎪⎨++≤⎪⎪≥≤⎩
123
1232313132(2)2433212
210..215,0,0
Max Z x x x x x x x x s t x x x x x =-+-+≤⎧⎪+≥⎪⎨
-=⎪⎪≥≤⎩ 对偶问题：123
1231
23123123()121015023204..2230,0,b MinW y y y y y y y y y s t y y y y y y free
=++++≥⎧⎪-+≥⎪⎨+-≥⎪⎪≥≤⎩
12312312312123(3)2323253..100,0,Max Z x x x x x x x x x s t x x x x x free
=+-+-≤⎧⎪-+≥⎪⎨
+=⎪⎪≥≤⎩ 对偶问题：123
123123123123()253102
21..3030,0,c MinW y y y y y y y y y s t y y y y y y free
=++++≥⎧⎪-+≤⎪⎨
-+⋅=⎪⎪≥≤⎩
123132312123(4)23332210..280,,0Min Z x x x x x x x s t x x x x free x =+-+≥⎧⎪+≤⎪⎨+=⎪⎪≤≥⎩ 对偶问题：123
123123123123()3108021
022..32030,0,d MaxW y y y y y y y y y s t y y y y y y free
=+++⋅+≥⎧⎪⋅++=⎪⎨
++⋅≤-⎪⎪≥≤⎩
四、应用对偶单纯形法求解下列线性规划问题
12121212
(1)24..75,0Min Z x x x x s t x x x x =++≥⎧⎪+≥⎨⎪≥⎩
标准型：
'12
12312412
24..75,0Max Z x x x x x s t x x x x x =----+=-⎧⎪--+=-⎨⎪≥⎩
X*=(23/13, 6/13, 0, 0)T , Z ’max=-29/13 原问题X*=(23/13, 6/13, 0, 0)T , Zmin=29/13.
12312312
3123123(2)42245363..5212,010,Min Z x x x x x x x x x s t x x x x x x =++++≥⎧⎪-
+≥
⎪⎨++≥⎪⎪≥⎩ 标准型： 123
123412351236123456'42245363..5212,,10,,,0Max Z x x x x x x x x x x x s t x x x x x x x x x x =------+=⎧⎪-+-+=-⎪⎨
----+=-⎪⎪≥⎩
237/23)T , Zmin=226/23.
3. 123123123
1232242352373..4650,1,2,3
j Max Z x x x x x x x x x s t x x x x j =---++≥⎧⎪++≤⎪⎨
++≤⎪⎪≥=⎩
解：
1231231231232242352373..4650,1,2,3
j Max Z x x x x x x x x x s t x x x x j =---++≥⎧⎪++≤⎪⎨
++≤⎪⎪≥=⎩
标准型：123
12341235
12362242352
373
..4650,1,2,3,4,5,6
j Max Z x x x x x x x x x x x s t x x x x x j =---++-=⎧⎪+++=⎪⎨
+++=⎪⎪≥=⎩
*max
(0,,0,0,,)3333
T X Z ==-
五、应用对偶理论证明如下线性规划问题有可行解，但无最优解
六、灵敏度分析题
1. 解：依题意知，*
811
(,
,0,0)99
T =X ，max
103Z =，1
51991299B -⎛⎫- ⎪= ⎪ ⎪- ⎪⎝⎭
，2115B ⎛⎫∴= ⎪⎝⎭
(1,2,0,0)=C ，(3,7)T =b ，3411
;33
σσ=-=-
（1）若目标函数122Z x x =+变为1235Z x x =+，则
511099(0,0)(3,5)120199⎛⎫- ⎪⎛⎫==- ⎪ ⎪ ⎪⎝⎭
- ⎪⎝⎭-1
N N B σC -C B N ＝107(,)99-- 因此，最优解不变，但最优值变为max 79Z =。
（2）当(3,7)T =b 变为(8,11)T =b 时，'512989990121114999⎛⎫⎛⎫- ⎪
⎪⎛⎫===≥
⎪ ⎪ ⎪ ⎪ ⎪⎝⎭- ⎪ ⎪⎝⎭⎝⎭
-1
b B b 因此，最优解结构不变，数值变为*2914(
,,0,0)99T =X ，max 5719
93
Z ==。
（3）新产品C 3=1,3(1,3)T P =,则在系数矩阵中要增加一列，对应决策变量3x
1
333B c C B P σ-=-5111991(1,2)0123399⎛⎫- ⎪⎛⎫=-=-≤ ⎪ ⎪ ⎪⎝⎭
- ⎪⎝⎭
所以最优解和最优值不变，该产品不宜生产。
（4）若产品1的消耗系数由1(2,1)T P =变为1
(1,2)T
P =则 1
111B c C B P σ-=-511991(1,2)012299⎛⎫- ⎪⎛⎫=-=
⎪ ⎪ ⎪⎝⎭- ⎪⎝⎭
N N =--1
B σ
C C B N 51101199(0,0)(1,2)(,)12013399⎛⎫- ⎪⎛⎫=-=-- ⎪ ⎪
⎪⎝⎭
- ⎪⎝⎭ 故最优解改变，但最优值没变，产品结构无变化。
2. 解：设甲、乙两种产品的产量分别为1x 和2x 件。
原料A 消耗花费的钱：12(24)1x x +⨯ （元）。
原料B 消耗花费的钱：12(32)2x x +⨯ （元） 产品销售收益：121316x x +
扣除成本后的利润：1212121316(24)2(32)Z x x x x x x =+-+-⨯+
（1）利润最大化模型为：
12
1212125824160
.32180,0
Max Z x x x x s t x x x x =++≤⎧⎪
+≤⎨⎪≥⎩
解得：最优解*(50,15,0,0)T =X ，最优值max 370Z =（元）。
（2）从最优表中可知，原料A 的影子价格为*
13 1.75y σ=-=（7/4），原料B 的影子价格为*
240.5y σ=-=（1/2），显然原料A 更珍贵。
（3）若市场上有A 原料出售，企业应该购入以扩大生产。
假设在保持最优解不
变的前提下，最多购入Q （kg ）。
（请注意这里的逆矩阵先写第二行再第一行）
1
111604203118084Q -⎛⎫
- ⎪+⎛⎫==≥ ⎪ ⎪ ⎪⎝⎭- ⎪
⎝⎭B X B b
15004
31508Q Q ⎧
-≥⎪⎪⎨
⎪+≥⎪⎩
200Q ≤ 所以在保持最优解不变的前提下，最多只能再购入200kg 。
此时最优解为：*(0,90,0,0)T =X ，最优值max 720Z =（元）。
可增加利润350=(720-370)元。
（4）若乙产品价格可达到20元／件，此时原线性规划模型中产品乙的价值系数变成C2＝12。
111042(0,0)(5,12)310184⎛⎫- ⎪⎛⎫==- ⎪ ⎪ ⎪⎝⎭- ⎪
⎝⎭-1
N N B σC -C B N ＝133(,)42-，40σ∴>， 选4x 进基，继续迭代，求出最优解和最优值。
此时最优解为：*(0,40,0,100)T =X ，最优值max 480Z =（元）。
（5）若新产品丙可投入开发，设其在模型中的价值系数为C3。
1
333B c C B P σ-=-113423(5,8)031484c ⎛⎫
- ⎪⎛⎫=-≥
⎪ ⎪ ⎪⎝⎭- ⎪⎝⎭
3297.254c ≥
= 同时，一单位丙的原料成本为3*1+4*2=11元，所以产品丙的价格至少应为7.25+11=18.25元。
七、研究讨论题。
