管理运筹学教程习题解答(1.0版)
《管理运筹学教程》习题参考答案
第一章 线性规划
1、解：设每天应生产A 、B 、C 三种型号的产品分别为321,,x x x 件。则线性规划模型为： ??
?
??≥≤++≤++++=0,,20005040401200637.3020405max 321321321321x x x x x x x x x t s x x x Z 2、解：设5种债劵的投资额分别为54321,,,,x x x x x 件。则线性规划模型为：
????
?
?
??
?≥+≥+≤≤+≤+=++++++++=0
,,,,)(2.0)(65.0121830
.05.0055.0045.009.0065.0max 5432121543243215432154321x x x x x x x x x x x x x x x x x x x x t s x x x x x Z
3、（1）解：对原问题标准化，令1
x '＝－1x ，333x x x ''-'= ???
????≥''''=''-'+-'=-''-'++'=+''+'-+'-''-'++'-='0,,,,, 30444 25443 92. 442max 5433213321
5
3321
43321
3321
x x x x x x x x x x x x x x x x x x x x t s x x x x Z （2）解：对原问题标准化，令1
x '＝－1x ，333x x x ''-'= ???
????≥''''=''-'++'-=-''-'++'=+''-'++'''+'--'='0,,,,, 264425 144434 192223. 442max 5433213321
5
3321
43321
3321
x x x x x x x x x x x x x x x x x x x x t s x x x x Z （3）解：对原问题标准化，令22
2x x x ''-'= 22
1m ax x x x Z ''-'+= ???????≥''≥'≥=''-'-≥''-'+≤''-'+0,0,0 3)(2 4)(7 6)(32. 22
1221
2
21
22
1x x x x x x x x x x x x t s
4、（1）解：首先将线性规划模型标准化得：
3212m ax x x x z +-=
??
???
?≥=+-+=++-=+++0
,,,20210260
3.62163215
3214321x x x x x x x x x x x x x x x t s Λ
最优解为1 =0，2 = 110/3 , 3 = 70/3。目标函数值： * = 100/3
（2）解：首先将线性规划模型标准化得：
???
??≥=++++=++++0
,,,32227
432.62
16432154321x x x x x x x x x x x x x t s Λ
1234max 532z x x x x '=-+--
最优解为1 =0，2 = 1.5, 3 = 0,4=0。目标函数值： * = 1.5
5、(1)利用大M 法。
解:在上述问题中加入松弛变量和人工变量得：
???
??≥=+-+-=+++0
,,,10527
.62
1653214321x x x x x x x x x x
x x t s Λ 这里M 是一个充分大的正数,取基变量为 x 4 , x 6 ，可得如下表
由于46。
123
利用两阶段法。
先在以上问题的约束条件中加入松弛变量、人工变量，给出第一阶段的线性规划问题：
12346max 235z x x x Mx Mx =+---
64m ax x x w --=
???
??≥=+-+-=+++0
,,,10527.62
1653214321x x x x x x x x x x x x t s Λ 这里取基变量为 x 4 , x 6 ，可得如下表
由于
46。
这里 4、6 是人工变量。第一阶段我们已求得 = 0,因人工变量 6 = 4 = 0，所以
(45/7, 4/7, 0 ,0)T
是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表中的人工变量列取消，并将目标函数系数换成原问题的目标函数系数，重新计所有检验数 j ￡ 0，所以 1 = 45/7，2 = 4/7 , 3 = 0 是原线性规划问题的最优解。目标函数值： Z * = 102/7。
(2)利用大M 法。
解:在线性规划中加入人工变量得：
765214m ax Mx Mx Mx x x z -----='
??????
?≥=+++=+-+=++0
,,,426343
3.72174216
321521x x x x x x x x x x x x x x t s Λ 这里
567
由于5, 6,7为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形
表。
最优解为1 =0.4，2 = 1.8, 3 = 1。目标函数值： * = 3.4
利用两阶段法。
先在约束条件中加入人工变量，给出第一阶段的线性规划问题：
765m ax x x x w ---=
??????
?≥=++=-+=+0
,,,426343
3.43214213
2121x x x x x x x x x x x x t s
567由于
567表。
567567以(0.4,1.8 , 1 ,0)T
是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表中的人工变量列取消，并将目标函数系数换成原问题的目标函数系数，重新计算检验数行，可得如下第二阶段的初始单纯形表
最优解为x 1 =0.4，2 = 1.8, 3 = 1。目标函数值： * = 3.4
6、（1）解：将线性规划问题化为对偶问题??????
?≤≤≤+-=+-≥--++=无约束
－－3
213213
21213
21,0,033564
5 327
34..301320max y y y y y y y y y y y t s y y y W （2）解：将线性规划问题化为对偶问题
???
??≤≤≥+-≥++=0
,02
231 2..136min 21
21212
1y y y y y y t s y y W 7、用对偶单纯形法求解线性规划问题。
（1）解：将模型转化为
32118124m ax x x x Z ---='
??
?
??≥-=+---=+--0
,,,52233.521532431x x x x x x x x x t s Λ
可得原问题最优解X *=（2.5，0，0）， Z *=10 （2）解：将模型转化为 ???
??≥≥++≥+-++=0,,50
260
2..25640min 3
21321321321y y y y y y y y y t s y y y W
进一步可以变为
???
??≥-=+---=+-+----=0,,50
y 260-y 2..25640max 3
2153214321321y y y y y y y y y t s y y y W
可得原问题最优解X *=（25，0）， Z *=1500 8、已知线性规划问题
32124m ax x x x Z ++=
???
??≥≤++≤++0,,86238.3
21321321x x x x x x x x x t s 31,x x 的目标函数系数的变化围；
（3）的变化围。
（1） 可得原问题最优解X *=（0，0，2），最优值 Z *= 4 对偶问题最优解（2，0），最优值 Z *= 4
（2）如果1x 系数的改变，使016681101)0,2(111111≤-=?
?
?
?????????--=-=-c c P B C c B σ 即 161≤c 时，原最优方案不发生改变。 如果3x 系数的改变，使
1102201138
)0,()0,0,,1,4(331?
?
??
??----=-=-c c A B C C B A σ 0)0,,0,31,84(333≤---=c c c
即 ???
??≤-≤-≤-0
0310
843
33c c c 解得213≥c ，这时原最优方案不发生改变。
（3）如果b 改变，则
01101211
≥??
??????????-=-b b b B
???≥+-≥00211b b b 解得 ??
?≥≥1
210
b b b 即??
?≥≥12
10
b b b 的围变化时并不影响最优方案。
9
可得原问题最优解X *=（0，20，0），最优值 Z *= 100 (1) 如果1b 改变，则
??
?
???-=????????????-=-3030903014011
b B
即第一个约束条件的右端的常数项由20变为30时，则最优方案调整为 X=(0,0,9)T ,目标值为117。 （2）如果2b 改变，则
?
?
?
???-=????????????-=-1020702014011b B
即第二个约束条件的右端的常数项由90变为70时，则最优方案调整为 X=(0,5,5)T ,目标值为90。
(3)目标函数中3x 的系数由13变为8，由于3x 是非基变量，因此3c 改变为8时，使
0715********)0,5(831
33≤-=-=?
?
?
?????????--=-=-P B C c B σ 这时原最优方案不发生改变。
(4) 由于1x 是非基变量，它对应的系数矩阵变化时，不会改变1
-B ，它只影响单纯形表j P 列，只是对检验数有影响，因此。
0505501401)0,5(51111≤-=--=?
?
?
???????
??---=-=-P B C c B σ 这时原最优方案不发生改变。
(5) 以x 6为基变量，将上式反映到最终单纯形表中得到
为基变量，因此所对应的检验数应为0，因此经计算得下表。在上表中，x2、x5、x
6
增加约束后，最优方案调整为 X=(0,12.5,2.5)T,目标值为95。
则运输量最少为50×90＋50×80＋150×70＋200×80=35000 11、
则运输量最少为20×80＋140×50＋120×110＋40×110＋20×90＋80×60=32800 12、解：由于已知各面食加工厂制作单位面粉食品的利润及各面粉厂到各面食加工厂之间的
由于要求的是利润最大化，再一点，该问题是产销不平衡问题，增加一个虚拟的面食厂D ，他的需求量为10，各面粉厂到面食厂的运价为0。在伏格尔方法中从行差额和列差额中选出最大者，选择它所在的行或列中的最大元素进行分配运量。得初始方案为：
则最大利润为15×8＋0×6＋15×5＋10×5＋20×9＋10×0=425
13、解：设1x 为买第一种包装的袋数，2x 为买第二种包装的袋数，则数学模型为
??
?≥≥++=整数
,0,1072435.4864min 212121x x x x t s x x z 14、解：设ij x 为第i 辆平板车装j c 类箱子的数量，7,,2,1;2,1Λ==j i 。 则箱数的约束为
8
4669782717261625152414231322122111≤+≤+≤+≤+≤+≤+≤+x x x x x x x x x x x x x x 重量的约束为
2,1,40245.0327654321=≤++++++i x x x x x x x i i i i i i i
厚度的约束为
2,1,102064527.48723.61527.487654321=≤++++++i x x x x x x x i i i i i i i
特殊约束
7.302)(64)(52)(7.48271726162515≤+++++x x x x x x
自然约束
7,,2,1;2,1,,0Λ==≥j i x ij 整数
目标函数是使浪费的空间最小，也就是装的越多，空间浪费的越少。
)
(64)(52)(7.48)(72)(3.61)(52)(7.48max 2717261625152414231322121211x x x x x x x x x x x x x x z +++++++++++++=
15、（1）解：求相应的线性规划（LP ）
2134min x x z --=
???
??≥≤+≤+0,832104.2
12121x x x x x x t s 得（LP ）的最优解5/62,5/6,5/1121-===z x x
首先注意其中一个非整数变量的解，如2x ，在松弛问题中的解5/62=x ，于是原问题增加两个约束条件
12≤x ，22≥x
将两个约束分别并入原问题的松弛问题（LP ）中，形成两个分支，即后继问题（LP 1）和(LP 2)，这并不影响原问题的可行域。
解（LP 1），得最优解为
12,1,4/921-===z x x
再解（LP 2），得最优解为
10,2,121-===z x x
继续对（LP 1）进行分解。对（LP 1）增加两个约束条件
21≤x ，31≥x
将两个约束分别并入（LP 1）中，形成两个分支，即后继问题（LP 11）和(LP 12)，这并不影响（LP 1）的可行域。 解（LP 11），得最优解为
11,1,221-===z x x
再解（LP 12），无最优解。
因此得原问题的最优解为11,1,221-===z x x 。 (2) 解：求相应的线性规划（LP ）
212max x x z +=
??????
?≥≤+≤+-≤+0
,212605.21212
121x x x x x x x x t s 得（LP ）的最优解75.7,25.2,75.221===z x x
首先注意其中一个非整数变量的解，如2x ，在松弛问题中的解25.22=x ，于是原问题增加两个约束条件
22≤x ，32≥x
将两个约束分别并入原问题的松弛问题（LP ）中，形成两个分支，即后继问题（LP 1）和(LP 2)，这并不影响原问题的可行域。
解（LP 1），得最优解为
3/23,2,6/1721===z x x
再解（LP 2），无最优解。
继续对（LP 1）进行分解。对（LP 1）增加两个约束条件
21≤x ，31≥x
将两个约束分别并入（LP 1）中，形成两个分支，即后继问题（LP 11）和(LP 12)，这并不影响（LP 1）的可行域。
解（LP 11），得最优解为
6,2,221===z x x
再解（LP 12），得最优解为。5.7,5.1,321===z x x 继续对（LP 12）进行分解。对（LP 12）增加两个约束条件
12≤x ，22≥x
将两个约束分别并入（LP 12）中，形成两个分支，即后继问题（LP 121）和（LP 122），这并不影响（LP 12）的可行域。 解（LP 121），得最优解为
7/22,1,6/1921===z x x
再解（LP 122），无最优解。
继续对（LP 121）进行分解。对（LP 121）增加两个约束条件
31≤x ，41≥x
将两个约束分别并入（LP 121）中，形成两个分支，即后继问题（LP 1211）和（LP 1212）。 解（LP 1211），得最优解为。
7,1,321===z x x
再解（LP 1212），无最优解为。
因此得原问题的最优解为7,1,321===z x x 。
16、解：通过观察的方法找一个可行解，易得(x 1 , x 2 , x 3 , x 4)=(0 ,0 ,0，1)符合约束条件，计算出其目标函数值Z =4。对于极小化问题，当然希望z ≤4，于是增加一个约束条件，后加的约束条件称为过滤条件。
过滤条件为： 443524321≤+++x x x x ◎ 目标函数可以改写成：
13422345m in x x x x z +++=
因为5，、4、3，2是递减的，变量(x 2 ,x 4 ,x 3, x 1 )也按下述顺序取值（0，0，0，0），（0，0，0，1），（0，0，1，0），（0，0，1，1）等.
423451342≤+++x x x x ◎
1
4224404134213421342≥+-+≥-++≥-++x x x x x x x x x x x x
得最优解(2 4 31 )＝（0，1，0，0），最优值z ＝4。
（2）3212m ax x x x z -+=
?????
??
??=≤-+≤-+≤+≤++1
0,,4
4225423.3213
2132132321或x x x x x x x x x x x x x x t s 解：通过观察的方法找一个可行解，易得(x 1 , x 2 , x 3)=(1 ,0 ,0)符合约束条件，计算出其目标函数值Z =2。对于极大化问题，当然希望z ≥2，于是增加一个约束条件，后加的约束条件称为过滤条件。
过滤条件为： 22321≥-+x x x ◎ 目标函数可以改写成：
1232m ax x x x z ++-=
因为-1，1，2是递增的，变量(x 3，x 2 , x 1)也按下述顺序取值（0，0，0），（0，0，1），（0，1，0），（0，1，1）等。
22123≥++-x x x ◎
4
422542312312323123≤++-≤++-≤+≤++x x x x x x x x x x x
改进过滤条件，用
32123≥++-x x x ◎
最优解为(x 3，x 2 , x 1)＝（0，1，1）；最优值为z=3。
17、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如表2，问如何分配工作可使总的消耗时间为最少？
解：首先进行行、列变换，使每一行和每一列都出现0元素。在第一列减去15，第二列减去17，第三列减去16，第四列减去17，然后再从第二行中减去1。得
首先进行行、列变换，使每一行和每一列都出现0元素。如上表中第一行减去7，第二行减去5，第三行减去4，第四行减去2，然后再从第四列中减去1。得
0 1 5 7 3 5 5 0 11 0 0 1 4 5 7 0
进行试指派，寻找最优解。由有0元素最少的行开始，圈出一个0元素，用◎表示，然后划去同行同列的其他0元素，这样依次进行，得
◎ 1 5 7
3 5 5 ◎
11 ?◎ 1
4 5 7 ?
由于独立的0元素个数少于矩阵的阶数，因此作最少的直线覆盖所有的0元素。在没有◎的行打√；对打√的行上的所有0元素的列打√号；再对打√的列上有◎的行上打√号。重复以上步骤，直到得不出新的打√号的行列为止。最后对没有打√号的行画横线，将打有√号的列画竖线。
◎ 1 5 7
3 5 5 ◎√
11 ?◎ 1
4 5 7 ?√
√
由于覆盖直线个数3少于矩阵阶数4，故进行变换，以增加0元素。
在没有被直线覆盖的部分中找出最小元素3；然后对没有覆盖的行中各元素中减去这个最小元素3；被直线覆盖的列中各元素都加上这个最小元素3。这样在没有覆盖的元素中又增加了0元素。
0 1 5 10
0 2 2 0
11 0 0 4
1 2 4 0
再进行试指派，寻找最优解。
◎ 1 5 10
? 2 2 ?
11 ?◎ 4
1 2 4 ◎
由于独立的0元素个数仍然少于矩阵的阶数，因此作最少的直线覆盖所有的0元素。
◎ 1 5 10 √
? 2 2 ?√
11 ?◎ 1
1 2 4 ◎√
√√
0 0 4 10
0 1 1 0
12 0 0 5
1 1 3 0
再进行试指派，寻找最优解。
?◎ 4 10
◎ 1 1 ?
12 ?◎ 5
1 1 3 ◎
0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1
得到最优解的指派方案为：甲－B ，乙－A ，丙－C ，丁－D ；最少消耗时间为70。
第二章 目标规划
一、思考题
1，答：因为在经营管理实际中，决策者不仅要考虑资源的最佳配置和有效利用，还要考虑
到市场、竞争对手、替代品的政策法律环境等多方面的影响因素和指标要求，此时线性规划模型不能完全解决问题。
2，答：一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，并按多个目标的重要性，给定优先等级和权重，顺序求最小值。 按决策者的意愿，对于事先给定的目标值，分为三种情况：
（1） 当约束要求目标不超过目标值，目标函数求正偏差变量最小。 （2） 当约束要求目标不低于目标值，目标函数求负偏差变量最小。 （3） 当约束要求目标等于目标值，目标函数求正负偏差变量之和最小。 3，答：（一）初始基变量的选择
首先选择所有的负偏差变量-
i d 为初始基变量；如果负偏差变量数小于约束方程数，则增加选择不同约束条件的松弛变量；如果负偏差变量和松弛变量的总数还小于约束方程数时，则需要加入人工变量，此时引入的M 将被视作最高优先级，即0级优先级：∞=1/P M 。 （二）满意解的判断
当所有非基变量的检验数大于等于零时，目标规划问题获得最优解。非基变量的检验数为：m m i i i i j P P P ααασ+++=++Λ11，由于∞=-j
j P P 1，m j ≤≤2，所以当非基变量检验
数中的首项系数0>i α时，获得满意解。 （三）入基变量和出基变量的选择
入基变量的选择：选择检验数首项系数为负的非基变量入基，若有多个首项系数为负，则取其中检验数首项优先级最高系数最小的非基变量入基。如果首项优先级相同且系数相等，再比较第二个优先级的系数···。若有两个及两个以上的非基变量检验数（的所有各项系数）都相等，这些非基变量中有决策变量时，则首先选择决策变量入基；若它们同时是决策变量或偏差变量，则可以选择其中下标最小的变量入基。