《管理运筹学》第四版第6章单纯形法的灵敏度分析与
对偶课后习题解析
《管理运筹学》第四版第6章单纯形法的灵敏度分析与对
偶课后习题解析
《管理运筹学》第四版课后习题解析
第6章单纯形法的灵敏度分析与对偶
1(解：
(l)cl?24
⑵ c2?6
(3)cs2?8
2(解：
(1)cl??0.5
(2)?2?c3?0
(3)cs2?0.5
3(解：
(1)bl?250
(2)0?b2?50
(3)0?b3?150
4(解：
(1)bl??4
(2)0?b2?10
(3)b3?4
最优基矩阵和其逆矩阵分别为:B???
最优解变为xl?10??10??l??, B????41??;41?????x2?0, x3?13,最小值变为-78;
?0, x2?14, x3?2,最小值变为-96;最优解没有变化;最优解变为xl
6(解：
⑴利润变动范围cl?3,故当cl=2时最优解不变。
⑵根据材料的对偶价格为1判断，此做法有利。
(3)0?b2?45o
(4)最优解不变，故不需要修改生产计划。
(5)此时生产计划不需要修改，因为新的产品计算的检验数为?3小于零，对原生产计划没有影响。
7.解：
⑴设xl,x2,x3为三种食品的实际产量，则该问题的线性规划模型为
max z?2.5xl?2x2?3x3
约束条件:8xl?16x2?10x3?350
10xl?5x2?5x3?450
2xl?13x2?5x3?400
xl,x2,x3?0
解得三种食品产量分别为xl?43.75,x2?x3?0,这时厂家获利最大为109.375万
ye©
(2)如表中所示，工序1对于的对偶价格为0.313万元，由题意每增加
10工时可以多获利3.13万元，但是消耗成本为10万元，所以厂家这样做不合算。
(3)B食品的加工工序改良之后，仍不投产B,最大利润不变;
若是考虑生产甲产品，则厂家最大获利变为169.7519万元，其中
xl?14.167,x2?0, x3?ll, x4?31.667;
(4)若是考虑生产乙产品，则厂家最大获利变为163.1万元，其中xl?ll,x2?0, x3?7.2, x4?38;
所以建议生产乙产品。
8(解：
均为唯一最优解，根据从计算机输出的结果看出，如果松弛或剩余变量为零且对应的对偶价格也为零，或者存在取值为零的决策变量并且其相差值也为零时，可知此线性规划有无穷多组解。
9(解：
(1)minf= 10yl+20y2.
s.t.yl+y2?2
yl+5y2?l
yl+y2?l
yi,y2?0
(2)max JL— 1 OOyl +200y2.
s.t. l/2yl+4y2?4
2yl+6y2?4
2yl+3y2?2
yl,y2?0
10(解
(l)min f=?10yl+50y2+20y3.
s.t. ?2yl +3y2+y3?l
?yl+y2+y3 =5
yl, y2?0, y3没有非负限制。
(2)max z= 6yl?3y2+2y3.
s.t.yl?y2?y3?l
2yl+y2+y3 =3
?3yl+2y2?y3??2
yl, y2?o, y3没有非负限制
11.解：
max z?6y 1 ?7y2?8y3?9y4?l Oy5
约束条件:yl?y5?l
yl?y2?l
y2?y3?l
y3?y4?l
y4?y5?l
yl,y2,y3,y4,y5?0
用对偶问题求解极大值更简单，因为利用单纯形法计算时省去了人工变量。
12.解：
⑴该问题的对偶问题为
max f?4yl?12y2
约束条件:3yl ?y2?2
2yl?3y2?3
yl?y2?5
求解得maxf=12,如下所示：
(2)该问题的对偶问题为min Z?2yl?3y2?5y3约束条件:2yl?3y2?y3??3
3yl?y2 ?4y3 ??8 5yl?7y2 ?6y3 ??10
yl,y2,y3?0
求得求解得min z=24,如下所示：
思考：
在求解
min f?CX 约束条件:AX?b X?0
max 2?CX 约束条件:AX?b X?0
以上两种线性规划时一般可以选取对偶单纯形法。
13.解：
其中:C为非负行向量，列向量b中元素的符号没有要求
其中:C为非正行向量，列向量b中元素的符号没有要求
⑴错误。原问题存在可行解，则其对偶问题可能存在可行解，也
可能无可行解；
(2)正确;
(3)错误。对偶问题无可行解，则原问题解的情况无法判定，可能无可行解，可能有可行解，甚至为无界解;(4)正确；
14(解：
maxz??xl ?2x2?3x3
??4??xl?x2?x3?sl
?x2?x3?s3??2?
?xi?04?l,?,3；sj?0,j?l,?,3?
用对偶单纯形法解如表6-1所示。表6-1
续表
最优解为xl=6, x2=2, x3=0,目标函数最优值为10。
15.解:原问题约束条件可以表示为AX?b?ta,其中a和b为常数列向量。令t?0,将问题化为标准型之后求解，过程如下：
其中最优基矩阵的逆矩阵为
?100????1
B???ll?l?,
?001???
则
B*b???ll?l??10???2?
，001 »3»3冲»»
♦ vx VZ d •♦♦♦♦♦•
?100??t??l??t?????????
B?1 *ta???l 1 ?1 ???t??t??3????3t?
?001??t??l??t?????????
?5?t???
(b?ta)??2?3t?则B?l*
?3?t???
从而，1)当
时，最优单纯形表为2?3t?0, 3?t?0,此0^ 5?t?0,线性规划问题的最优解为(xl,x2)?(5?t,3?t^,
目标函数最大值为ll?3t;
37
2)当?t?时，由2?3t?0可知，(xl,x2)?(5?&3?t)并非最优解，利用对偶
22
此时7?2t?0, ?2?3t?0, 3?t?0,从而线性规划问题的最优解为
(xl,x2)?(7?2t,3?t),目标函数的最大值为13; 3)当
7
?t?10 时，，由7?2t?0 可知,(xl,x2)?(7?2t,3?t)并非最优解,利用 2
此时?7?2t?0, 5?t?0, 10?t?0,从而线性规划问题的最优解为
(xl,x2)?(0,10?t),目标函数的最大值为20?2t;
16解先写出原问题的对偶问题
min f?20yl ?20y2
约束条件:yl?4y2?2⑴
2yl?3y2?2 (2) 3yl?2y2?l
(3)4yl?y2?l (4)
yl,y2?0
13
将yl?,y2?代入对偶问题的约束条件，得有且只有(2)、(4)式等式成立，105
也就是说，其对应的松弛变量取值均为0,⑴和(3)式对应的松弛变量不为0,
从而由互补松弛定理有xl?x3?0;又因为yl?0,y2?0,从而原问题中的
两个约束应该取等式，把xl?x3?0代入其中，得到
2x2?4x4?20
3x2 ?x4?20
解方程组得到x2?6,x4?2o经验证xl?0,x2?6,x3?0,x4?2满足原问题约
束条件，从而其为原问题的最优解，对应的目标函数最大值为14;
《管理运筹学》第四版课后习题解析 第6章单纯形法的灵敏度分析与对偶 1．解： （1）c 1≤24 （2）c 2≥6 （3）c s 2≤8 2．解： （1）c 1≥−0.5 （2）−2≤c 3≤0 （3）c s 2≤0.5 3．解： （1）b 1≥250 （2）0≤b 2≤50 （3）0≤b 3≤150 4．解： （1）b 1≥−4 （2）0≤b 2≤10 （3）b 3≥4 5. 解： 最优基矩阵和其逆矩阵分别为：⎪⎪⎭⎫ ⎝⎛=1401B ，⎪⎪⎭ ⎫ ⎝⎛-=-14011 B ； 最优解变为130321 ===x x x ，，最小值变为-78； 最优解没有变化； 最优解变为2140321 ===x x x ，，，最小值变为-96； 6．解： （1）利润变动范围c 1≤3，故当c 1=2时最优解不变。 （2）根据材料的对偶价格为1判断，此做法有利。 （3）0≤b 2≤45。 （4）最优解不变，故不需要修改生产计划。 （5）此时生产计划不需要修改，因为新的产品计算的检验数为−3小于零，对原生产计划没有影响。 7. 解：
(1)设321,,x x x 为三种食品的实际产量，则该问题的线性规划模型为 ,, 4005132 4505510 35010168 325.2max 321321321321321≥≤++≤++≤++++=x x x x x x x x x x x x x x x z 约束条件： 解得三种食品产量分别为0,75.43321===x x x ，这时厂家获利最大为109.375万元。 (2)如表中所示，工序1对于的对偶价格为0.313万元，由题意每增加10工时可以多获利3.13万元，但是消耗成本为10万元，所以厂家这样做不合算。
第一部分绪论 第二部分线性规划与单纯形法 1 判断下列说法是否正确： (a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的； (b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大； (c)线性规划问题的每一个基解对应可行域的一个顶点； (d)如线性规划问题存在可行域,则可行域一定包含坐标的原点； (e)对取值无约束的变量x i,通常令其中 ,在用单纯形法求得的最优解中有可能同时出现 (f)用单纯形法求解标准型的线性规划问题时,与对应的变量都可以被选作换入变量； (g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负； (h)单纯形法计算中,选取最大正检验数δk对应的变量x k作为换入变量,将使目标函数值得到最快的增长； (i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果； (j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示； (k)若x1,x2分别是某一线性规划问题的最优解,则 也是该线性规 划问题的最优解,其中λ1,λ2可以为任意正的实数； (1)线性规划用两阶段法求解时,第一阶段的目标函数通常写为 X ai为人工变量),但也可写为,只要所有 k i均为大于零的常数； (m)对一个有n个变量、m个约束的标准型的线性规划问题,其可行域的顶点恰好 为个； (n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解； (o)线性规划问题的可行解如为最优解,则该可行解一定是基可行解； (p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解； (q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；
运筹学部分课后习题解答P47 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都 为最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? < 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 、 B C B X b 1x 2x 3x 4x 0 3x \ 9 3 4 1 0 0 4x 8 [5] 2 . 0 1 j j C Z - 10 5 0 0 0 3x 21/5 . 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 （ 1/5 j j C Z - 1 0 -2 5 2x 3/2 0 ； 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 （ j j C Z - -5/14 -25/14
将下列线性规划模型化为标准形式并列出初始单纯形表。 （1） 123 123123123123min 2432219 43414..524260,0,z x x x x x x x x x s t x x x x x x =++-++≤??-++≥?? --=-??≤≥? 无约束 解：（1）令11333','",'x x x x x z z =-=-=-，则得到标准型为（其中M 为一个任意大的正 数） 12334567123341233561233712334567max '2'24'4''003'22'2''19 4'34'4''14..5'24'4''26',,','',,,,0 z x x x x x x Mx Mx x x x x x x x x x x x s t x x x x x x x x x x x x x =-++-++--++-+=??++--+=?? ++-+=??≥? 初始单纯形表如表2-1所示： 表2-1 c j -2 2 4 -4 0 0 -M -M θ C B X B b 1'x x 2 3'x 3''x x 4 x 5 x 6 x 7 0 x 4 19 3 2 2 -2 1 0 0 0 19/3 -M x 6 14 [ 4 ] 3 4 -4 0 -1 1 0 14/4 -M x 7 26 5 2 4 -4 0 0 0 1 26/5 -z -2+9M 2+5M 4+8M -4-8M -M 用单纯形法求解下列线性规划问题。 （1） 123 123123 123123max 2360 210..220,,0 z x x x x x x x x x s t x x x x x x =-+++≤??-+≤?? +-≤??≥? （2） 1234 123412341234 min 52322347..2223,,,0z x x x x x x x x s t x x x x x x x x =-+++++≤?? +++≤??≥? 解：（1）最优解为**(15,5,0),25T x z ==。 （2）最优解为**(0,1.5,0,0),3T x z ==-。 分别用大M 法和两阶段法求解下列线性规划问题。 （1） 123 123123123 max 2357..2510,,0z x x x x x x s t x x x x x x =+-++=??-+≥??≥? （2） 12 12123 1241234min 433 436..24,,,0 z x x x x x x x s t x x x x x x x =++=??+-=?? ++=??≥? 解：（1）最优解为**(6.429,0.571,0),14.571T x z ==。 （2）最优解为**(0.4,1.8,1,0), 3.4T x z ==。
一、填空题 1、对偶问题的对偶问题是（）。 正确答案：原问题 2、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y﹡b。 正确答案：= 3、若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX（）Yb。 正确答案：<= 4、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y*b。 正确答案：= 5、设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为（）。 正确答案：min=Yb YA>=c Y>=0 6、影子价格实际上是与原问题各约束条件相联系的（）的数量表现。 正确答案：对偶变量 7、线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为（）。 正确答案：AT 8、在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，…
n)，则原问题（）。 正确答案：无解 二、选择题 1、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。 A. “≥” B. “≤” C. “>” D. “=” 正确答案：A 2、如果z*是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡满足（）。 A.W﹡=Z﹡ B.W﹡≠Z﹡ C.W﹡≤Z﹡ D.W﹡≥Z﹡ 正确答案：A 3、如果某种资源的影子价格大于其市场价格，则说明（）。 A.该资源过剩 B.该资源稀缺 C.企业应尽快处理该资源 D.企业应充分利用该资源，开辟新的生产途径
正确答案：B 4、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。 A.≥ B.≤ C. > D. = 正确答案：A 5、对偶单纯形法的迭代是从（）开始的。 A.正则解 B.最优解 C.可行解 D.可行解 正确答案：A 6、如果某种资源的影子价格大于其市场价格，则说明（）。 A.该资源过剩 B.该资源稀缺 C.企业应尽快处理该资源 D.企业应充分利用该资源，开辟新的生产途径 正确答案：B 7、线性规划灵敏度分析的主要功能是分析线性规划参数变化对（）的影响。
运筹学基础及应用 习题解答 习题一 P46 1.1 (a) 该问题有无穷多最优解，即满足2 1 0664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。 (b) 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 1.2 (a) 约束方程组的系数矩阵 4
???? ? ??--=1000030204180036312A 最优解()T x 0,0,7,0,10,0=。 (b) 约束方程组的系数矩阵 ? ?? ? ??=21224321A
最优解T x ??? ??=0,511,0,5 2。 1.3 (a) (1) 图解法 最优解即为???=+=+82594321 21x x x x 的解??? ??=23,1x ，最大值235=z (2)单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 ???=++=+++++=8 259 43 ..00510 max 421321 4321x x x x x x t s x x x x z 则43,P P 组成一个基。令021==x x 得基可行解()8,9,0,0=x ，由此列出初始单纯形表
21σσ>。5 839,58min =?? ? ??=θ 02>σ，2 3 28,1421min =??? ??=θ 新的单纯形表为 0,21<σσ，表明已找到问题最优解0 , 0 , 23 1,4321====x x x x 。最大值 2 35*= z
(b) (1) 图解法 最优解即为?? ?=+=+5 24262121x x x x 的解??? ??=23,27x ，最大值217=z (2) 单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 1234523124125 max 2000515 .. 6224 5z x x x x x x x s t x x x x x x =+++++=?? ++=??++=? 则3P ，4P ，5P 组成一个基。令021==x x 得基可行解()0,0,15,24,5x =，由此列出初始单纯形表 21=+x x 2621+x x
运筹学基础及丨、V:用习题解答 习题一 P46 1.1 (a) 2 = 3。(b) 用亂解法找+到满足所打约柬条仲的公：it•范W，所以该问题无可行解。 1.2 (a)约束方程组的系数矩阵
最优解A.=(o，i a o,7，o，o)r (b)约束方程组的系数矩阵 f I 2 3 4、 4 = l2 2 I 2, 最优解1 = (^,0，11，0^ V5 5 )" 1.3 (a) (1)图解法
⑵单纯形法 首先在各约朿条件上添加松弛变铽，将问题转化为标准形式max z = 10a-, +5a'2 +0x3 +0a4 [3a-. +4 义2 + A3 = 9 si. < [5a-j + 2X2 + a'4 = 8 则A，P4组成个猫《=令 A = ;c2 = 0 得-站可行解a_ = (0.0.9,8)，山此列出初始单纯形表
cr 2 >0， 0 - minj 2A x 2 xi =~，a-3 =0, a 4 最优解即为严+2X2 = 24 的解x =卩，2V 最大值z : I A"i + X y = 5 I 2 2 / 新的单纯形农为 A', Xo X A 14 14 _5_ _25 M ~T? q.qcO ，表明已找到问题垴优解. (b) (1)图解法 17 (2) 单 纯形法 苘先在外约朿条件.h 添加松弛变M ，将问题转化为标准形式 max z = 2.v, + x 2 + Ox 3 + 0.v 4 + Oa 5 5a'2 + = 15 6.y, + 2x 2 + .v 4 = 24
0 0 0 -- 2 *^4 o A : 5 、Q 0 一4 (7,^2 <0,表明已找到问题最优解^ =1，X 2=- , A-3 2 L 估 • 17 Hi Z =—— 2 1.6 (a)在约朿条件中添加松弛变量或剩余变量，且令k = jc 2 -a :； (a*2 > 0,.v ； > o) Xx = ~X-> 该问题转化为 max z' = -3a, - x 2 + .v 2 - 2a 3 + 0.v 4 + (Xv 5 2x | + 3a -2 - 3a 2 + 4a 3 +a 4 =12 攀 M I 4a'| +x 2 -A*2 -2a*3 —^5 =8 3a*, -X 2 +X 2 — 3a*3 = 6 A*,, A '2，X 2, x 3，A-4 , A 3 ^ 0 -K 约朿系数矩陴为 2 3 -3 4 I 0 4 丨-1-2 0-1 3 -丨丨一3 0 0 在A 屮人为地添加两列单位向虽/>7， 2 3 -3 4 1 0 0 0 4 丨-1 -2 t) -1 丨 0 3-1 I -3 0 0 0 1 令 max z'= -3a -i - x 2 +x 2- 2.v 3 + Oa:., + 0.v 5 - Mx 6 - Mx 7 得初始单纯形表 15 最大 a 4 = 0，x 5 SS ^ Xi x 2 x 4 x 5 x 6 -2 0 0 M -M 4 1 0 -I 0 0 0 0 0
运筹学第四版课后答案《运筹学第四版课后答案》 第一章：线性规划基础 1.1 定义和性质 1.2 简单例子 1.3 代数表示法 1.4 简单例子 1.5 几何解释 1.6 凸集和凸函数 1.7 最优解的存在性 1.8 问题的变形 第二章：线性规划的几何解释 2.1 可行解集合 2.2 目标函数与等高线图 2.3 目标函数与等高线图（续） 2.4 从可行解的角度理解最优解 2.5 敏感性分析
2.6 邻域分析 2.7 图形方法 第三章：单纯形法 3.1 单纯形法的基本思想 3.2 人工变量法 3.3 人工变量法的例子 3.4 高级单纯形法 3.5 人工变量法的应用 第四章：对偶性 4.1 对偶问题的引入 4.2 对偶问题的定义 4.3 对偶性及其应用 4.4 敏感性分析的对偶方法4.5 例子 第五章：灵敏度分析 5.1 参数的变化对最优解的影响5.2 例子
5.3 例子（续） 5.4 增加既约费用 5.5 减少右端常数 第六章：网络优化问题 6.1 最小生成树问题 6.2 最短路径问题 6.3 最大流问题 6.4 最小费用流问题 第七章：整数规划 7.1 整数规划的引入 7.2 整数规划的一般形式7.3 整数规划的求解方法7.4 割平面算法 7.5 分支定界算法 第八章：动态规划和最优控制8.1 动态规划问题的引入8.2 状态转移方程
8.3 过程的描述 8.4 有限阶段情况的简化 8.5 资源分配问题 第九章：随机模型 9.1 随机规划问题的引入 9.2 随机变量的概率分布 9.3 期望值和方差的计算 9.4 随机规划问题的求解 9.5 例子 第十章：多目标规划 10.1 多目标规划问题的引入10.2 多目标规划问题的定义10.3 有效解集的概念 10.4 Pareto最优解的概念10.5 方法的具体实现 第十一章：饱和模型和逆问题11.1 饱和模型与逆问题的引入
第1章 线性规划基本性质 P47 1—1（2） 解：设每天从i 煤矿()2,1=i 运往j 城市()3,2,1=j 的煤为ij x 吨，该问题的LP 模型为： () ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨ ⎧==≥=+=+=+=++=+++++++==∑∑==3,2,1;2,10200150100250 200..85.681079min 231322122111232221 13121123 2221131211213 1 j i x x x x x x x x x x x x x t s x x x x x x x c ij i j ij ij ω P48 1—2（2） ⎪⎩⎪ ⎨⎧≥-≤-≥-+=0,)2(33) 1(0..max 2 121212 1x x x x x x t s x x z
解：Φ=21R R ，则该LP 问题无可行解。 P48 1—2（3） ⎪⎩⎪ ⎨⎧≥-≥-≥--=0,)2(55) 1(0..102min 2 1212121x x x x x x t s x x z 解：目标函数等值线与函数约束（2）的边界线平行，由图可知则该LP 问题为多重解（无穷多最优解）。 ⎪⎩⎪⎨⎧==⇒⎩⎨⎧-=-=-45455502 12121x x x x x x 则10,45,45**1-=⎪⎭ ⎫ ⎝⎛=z X T （射线QP 上所有点均为最优点） P48 1—2（4）
⎪⎪⎩⎪⎪⎨⎧≥≤-≤+≤+--=0 ,)3(22)2(825)1(1043..1110min 212121 2121x x x x x x x x t s x x z 解：由图可知Q 点为最优点。⎪⎩⎪⎨⎧==⇒⎩⎨⎧=+=+7137 6 82510432 12121x x x x x x 则29,713,76**-=⎪⎭ ⎫ ⎝⎛=z X T P48 1—3（2）
运筹学清华大学第四版答案 【篇一：运筹学作业2(清华版第二章部分习题)答案】s=txt>2．1 题（p. 77）写出下列线性规划问题的对偶问题： ? ? ??（1）? ? ? ??maxz?2x1?2x2?4x3s.t.x1?3x2?4x3?22x1?x2?3x3?3x1?4x2? 3x3?5x1?0，x2?0,x3无约束； 解：根据原—对偶关系表，可得原问题的对偶规划问题为： ?maxw?2y1?3y2?5y3?s.t.y1?2y2?y3?2??3y1?y2?4y3?2 ? ?4y1?3y2?3y3?4? y1?0,y2?0,y3?0?? mn?minz???cijxij? i?1j?1? n? ??cijxij?ai,i?1,?,m（2）? j?1 ?n ??cijxij?bj,j?1,?,n ?j?1 ???xij?0,i?1,?,m;j?1,?,n 解：根据原—对偶关系表，可得原问题的对偶规划问题为： mn? ?maxw??aiui??bjvj i?1j?1??ui?vj?cij ? ?i?1,?,m;j?1,?,n? ??ui无约束，vj无约束 2．2判断下列说法是否正确，为什么？ （1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：错。 因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。但，现实中肯定有一些问题是无最优解的，故本题说法不对。 maxz?3x1?x2 例如原问题
s.t.?x1?x2?1?x2?3? ?x?0,x?02?1有可行解，但其对偶问题 minw?y1?3y2 s.t.?3?y1?y2?1?y1? ?y?0,y?02?1无可行解。 （2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错，如（1）中的例子。 （3）在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可 行解的目标函数值一定不超过其对偶问题可行解的目标函数值。答：错。正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。 （4）任何线性规划问题具有唯一的对偶问题。 答：正确。 2．5给出线性规划问题 maxz?x1?2x2?x3 x1?x2?x3?2? ??x1?x2?x3?1? ?2x1?x2?x3?2 ?x?0,x?0,x?023?1 s.t. 写出其对偶问题；（2）利用对偶问题性质证明原问题目标函数值z?1 解：（1）原问题的对偶问题为： minw?2y1?y2?2y3 ? ??? ? ?y?1y1?y2?2y3?1y1?y2?y3?2?y1?y2?y3?1?0,y2无约束,y3?0 s.t. （2）取y??011?，既y1?0,y2?1,y3?0，经验证，y??0t11?是对偶问题的t 一个可行解，并且w?1。由对偶问题的性质可得z?w?1 2．9 用对偶单纯形法求解下列线性规划问题： minz?5x1?2x2?4x3 （2）s.t.?3x1?x2?2x3?4, ?6x?3x?5x?10?123
四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：
根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。 问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省 ? 某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 起运时间 服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4
每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少? 五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行域中的哪一个顶点。
六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。
八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 Xl X2 X3 X4 —10 b -1 f g X3 2 C O 1 1／5 Xl a d e 1 (1)求表中a ～g 的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2） 表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3
第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为
min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。
第一章 思考题、主要概念及内容 1、了解运筹学的分支，运筹学产生的背景、研究的内容和意义。 2、了解运筹学在工商管理中的应用。 3、体会管理运筹学使用相应的计算机软件，注重学以致用的原则。 第二章 思考题、主要概念及内容 图解法、图解法的灵敏度分析 复习题 1. 考虑下面的线性规划问题： max z=2x1+3x2 ；约束条件： x1+2x2 <6 5x1+3x2 < 15 x1, x2 >0 (1) 画出其可行域． (2) 当z=6 时，画出等值线2x1+3x2=6 ． (3) 用图解法求出其最优解以及最优目标函数值． 2. 用图解法求解下列线性规划问题，并指出哪个问题具有惟一最优解、无穷多最优解、无界解或无可行解． (1) min f=6x1+4x2 ；约束条件： 2x1+x2 >1， 3x1+4x2 >3， x1 ，x2 >0 (2) max z=4x1+8x2 ；约束条件： 2x1+2x2 < 1，0 -x1+x2 >8， x1,x2 >0 (3) max z=3x1-2x2 ； 约束条件： x1+x2 <1， 2x1+2x2 >4， x1 ，x2 >0 (4) max z=3x1+9x2 ；约束条件： x1+3x2 w 22 -x1+x2 <4
x2w6， 2x1-5x2 <0 x1, x2 >0 3. 将下述线性规划问题化成标准形式： (1) max f=3x1+2x2 ； 约束条件： 9x1+2x2 < 30 3x1+2x2 < 13 2x1+2x2 <9 x1 ，x2 >0． (2) min f=4x1+6x2 ； 约束条件： 3x1-x2>6 x1+2x2 < 10 7x1-6x2=4 ， x1 ，x2 >0． (3) min f=-x1-2x2 ； 约束条件： 3x1+5x2 < 70, -2x1-5x2=50 ， -3x1+2x2 > 30 x1 O, x2 (提示：可以令x ' 1=1，这样可得x' 1 >同样可以令x '-2" 2=x2其中x 2 x" 2>0可见当x' 2>册,2 x2 >0当x ' 2<册,2 x2 <0即-x2 这样原线性规划问题可以化为含有 决策变量x' ，1x ' ，2 x" 2的线性规划问题，这里决策变量x'，1x'，2 x" 2>．0 ) 4. 考虑下面的线性规划问题： min f=11x1+8x2 ； 约束条件： 10x1+2x2 > 220 3x1+3x2 > 128 4x1+9x2 > 326 x1 2 x2 >0． (1) 用图解法求解． (2) 写出此线性规划问题的标准形式． (3) 求出此线性规划问题的三个剩余变量的值． 5. 考虑下面的线性规划问题： max f=2x1+3x2 ； 约束条件： x1+x2 < 120 2x1+x2 >42
第一章 第一章 1. 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（Decision Variable）是决策问题待定的量值，取值一般为非负；约束条件（Constraint Conditions）是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数（Objective Function）是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2.（1）设立决策变量； （2）确定极值化的单一线性目标函数； （3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量； （4）非负约束。 3.（1）唯一最优解：只有一个最优点 （2）多重最优解：无穷多个最优解 （3）无界解：可行域无界，目标值无限增大 （4）没有可行解：线性规划问题的可行域是空集 无界解和没有可行解时，可能是建模时有错。 4. 线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 5. 可行解：满足约束条件AX =b,X≥0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 6. 计算步骤： 第一步，确定初始基可行解。 第二步，最优性检验与解的判别。 第三步，进行基变换。 第四步，进行函数迭代。 判断方式： 唯一最优解：所有非基变量的检验数为负数，即σj< 0 无穷多最优解：若所有非基变量的检验数σj≤ 0 ，且存在某个非基变量xNk 的检验数σk= 0 ，让其进基，目标函数的值仍然保持原值。如果同时存在最小θ值，说明有离基变量，则该问题在两个顶点上同时达到最优，为无穷多最优解。无界解：若某个非基变量xNk 的检验数σk> 0 ，但其对应的系数列向量P k' 中，每一个元素a ik' (i=1,2,3,…,m)均非正数，即有进基变量但找不到离基变量。
《管理运筹学》各章的作业 ----复习思考题及作业题 第一章绪论 复习思考题 1、从运筹学产生的背景认识本学科研究的内容和意义。 2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。 3、体会运筹学的学习特征和应用领域。 第二章线性规划建模及单纯形法 复习思考题 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 8在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取
优质参考资料
(2) x i 3 (1) 什么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样 的情况下，继续第二阶段？ 作业题: 1 、把以下线性规划问题化为标准形式： (i) max z= x i -2x 2 +x 3 s.t. x i +x 2 +x 3 w i2 2x i +x 2 -x 3 > 6 -x i +3x 2 =9 x i , x 2, x 3 > 0 (2) min z= -2x i -x 2 +3x 3 -5x 4 s.t x i +2x 2 +4x 3 -x 4 6 2x i +3x 2 -x 3 +x 4 = i2 x i +x 3 +x 4 w 4 x i , x 2, x 4 max z= x i +3x 2 +4x 3 (3) s.t. 3x i +2x 2 w i3 x 2 +3x 3 w i7 2x i +x 2 +x 3 =i3 x i , x 3 > 0 2 、用图解法求解以下线性规划问题 max z= x 1 +3x 2 s.t. x i +X 2 < 10 -2x i +2x 2 w 12 X i w 7 x i , X 2 > 0 min z= x 1 -3x 2 s.t. 2x 1 -x 2 w 4 x i +X 2 > 3
WORD整理版 《管理运筹学》各章的作业 ----复习思考题及作业题 第一章绪论 复习思考题 1、从运筹学产生的背景认识本学科研究的内容和意义。 2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。 3、体会运筹学的学习特征和应用领域。 第二章线性规划建模及单纯形法 复习思考题 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 作业题: 1、把以下线性规划问题化为标准形式： (1) max z= x1-2x2+x3 s.t. x1+x2+x3≤12 2x1+x2-x3≥ 6 -x1+3x2＝9 x1, x2, x3≥0 (2) min z= -2x1-x2+3x3-5x4 s.t x1+2x2+4x3-x4≥ 6 2x1+3x2-x3+x4＝12 x1+x3+x4≤ 4 x1, x2, x4≥0
1 绪论 1、运筹学的内涵 答：本书将运筹学定义为：“通过构建、求解数学模型，规划、优化有限资源的合理利用，为科学决策提供量化依据的系统知识体系。” 2、运筹学的工作过程 答： （1）提出和形成问题。即要弄清问题的目标、可能的约束、可控变量、有关的参数以及搜索有关信息资料。 （2）建立模型。即要把问题中的决策变量、参数和目标、约束之间的关系用一定的模型表示出来。 （3）求解模型。根据模型的性质，选择相应的求解方法，求得最优或者满意解，解的精度要求可由决策者提出。 （4）解的检验和转译。首先检查求解过程是否有误，然后再检查解是否反映客观实际。如果所得之解不能较好地反映实际问题，必须返回第（1）步修改模型，重新求解；如果所得之解能较好地反映实际问题，也必须仔细将模型结论转译成现实结论。 （5）解的实施。实施过程必须考虑解的应用范围及对各主要因素的敏感程度，向决策者讲清楚用法，以及在实施中可能产生的问题和修改的方法。 3、数学模型及其三要素 答：数学模型可以简单的描述为：用字母、数字和运算符来精确地反映变量之间相互关系的式子或式子组。数学模型由决策变量、约束条件和目标函数三个要素构成。决策变量即问题中所求的未知的量，约束条件是决策所面临的限制条件，目标函数则是衡量决策效益的数量指标。
2 线性规划 1、试述线性规划数学模型的组成部分及其特性 答：线性规划数学模型由决策变量、约束条件和目标函数三个部分组成。 线性规划数学模型特征： （1） 用一组决策变量表示某一方案，这组决策变量均为非负的连续变量； （2） 存在一定数量（m ）的约束条件，这些约束条件可以用关于决策变量的一组线 性等式或者不等式来加以表示； （3） 有一个可以用决策变量加以表示的目标函数，而该函数是一个线性函数。 2、一家餐厅24小时全天候营业，在各时间段中所需要的服务员数量分别为： 2：00~6：00 3人 6：00~10：00 9人 10：00~14：00 12人 14：00~18：00 5人 18：00~22：00 18人 22：00~ 2：00 4人 设服务员在各时间段的开始时点上上班并连续工作八小时，问该餐厅至少配备多少服务员，才能满足各个时间段对人员的需要。试构造此问题的数学模型。 解：用决策变量1x ,2x ,3x ,4x ,5x ,6x 分别表示2：00~6：00， 6：00~10：00 ，10：00~14：00 ，14：00~18：00，18：00~22：00， 22：00~ 2：00 时间段的服务员人数。 其数学模型可以表述为：123456min Z x x x x x x =+++++ 16122334455612345639125184,,,,,0 x x x x x x x x x x x x x x x x x x +>=+>=+>=+>=+>=+>=≥ 3、现要截取2.9米、2.1米和1.5米的元钢各100根，已知原材料的长度是7.4米，问应如何下料，才能使所消耗的原材料最省。试构造此问题的数学模型。 解：圆钢的截取有不同的方案，用θ表示每种切割方案的剩余材料。其切割方案如下所示： 2.9 2.1 1.5 θ 1' 1 1 1 0.9 2' 2 0 0 0.1 3' 1 2 0 0.3 4' 1 0 3 0 5' 0 1 3 0.8 6' 0 0 4 1.4 7' 0 2 2 0.2 8' 0 3 0 1.1 目标函数为求所剩余的材料最少，即