《管理运筹学》第二版课后习题参考答案
《管理运筹学》（第二版）课后习题参考答案第 1 章线性规划（复习思考题）1．什么是线性规划？线性规划的三要素是什么？答：线性规划（Linear Programming ，LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。
建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值
时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者
希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，
有的则要求极小值。
2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？
答：（1）唯一最优解：只有一个最优点；
（2）多重最优解：无穷多个最优解；
（3）无界解：可行域无界，目标值无限增大；
（4）没有可行解：线性规划问题的可行域是空集。当无界解和没有可行解时，可能是建模时有错。
3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？
答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项b i 0 ，决策变量满足非负性。
如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。
4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。答：可行解：满足约束条件AX b，X 0 的解，称为可行解。基可行解：满足非负性约束的基解，称为基可行解
可行基：对应于基可行解的基，称为可行基。
最优解：使目标函数最优的可行解，称为最优
解。最优基：最优解对应的基矩阵，称为最优
基。
它们的相互关系如右图所示：
5．用表格单纯形法求解如下线性规划
8x1 3x2 x3 2
s.t. 6x1x2 x3 8
x1, x2 , x3 0
解：标准化
maxZ 4x1 x2
2x3
8x1 3x2 x3 x4 2
s. t. 6x1 x2 x3 x5 8
x1,x2 , x3,x4 ,x5 0
列出单纯形表
故最优解为X* （0,0,2,0,6）T，即x1 0,x2 0,x3 2 ，此时最优值为Z（X*）4．
6．表1—15 中给出了求极大化问题的单纯形表，问表中a1,a2,c1,c2,d 为何值
及变量
属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最
优解之一；（3）
下一步迭代将以x1代替基变量x5 ；（4）该线性规划问题具有无界解；（5）
该线性规划问题无可行解。
表 1— 15 某极大化问题的单纯形表
0 0
b
d
4 1 0 0
2
－1 － 5 0 1 0
3
－3
0 0 1
解：（
1
） d0 ,c 1 0,
c 2 0；
（2
）
d 0,c 1 0,c 2 0 （c 1,c 2中至少有一个为零）
d 3
（3c
1 0,a
2 0,d
4 a
2
（4）
c
2 0,
a 1 0；
（5） x 1为人工变量，且 c 1为包含 M 的大于零的数， d 3
；或者 x 2为人工变
量，
4 a 2
且 c 2为包含 M 的大于零的数， a 1 0,d 0 ．
7．用大 M 法求解如下线性规划。
x
1
2x 2
x
3
18
s.t . 2x
1 x
2 3x
3 16
x 1 x 2 x
3 10
x 1,x 2,x 3 0
解：加入人工变量， 进行人造基后的数学模型如下
x 1 2x 2 x 3 x
4
18 2x 1 x 2 3x 3 x
5 16
s. t. 1
x 1 x 2 x 3 x
6 10
x
i 0 (i 1,2,
,6) 列出单纯形表
5 3
6 0 0
－ M
故最优解为X* (6,4,0,4,0,0)T，即x1 6,x2 4,x3 0，此时最优值为Z(X*) 42．8．A，B，C三个城市每年需分别供应电力320，250和350单位，由I，II 两个电站
提供，它们的最大可供电量分别为400 单位和450 单位，单位费用如表1—16所示。由于需要量大于可供量，决定城市A的供应量可减少0～30 单位，城市B的供应量不变，城市C的供应量不能少于270 单位。试建立线
性规划模型，求将可供电量用完的最低总费用分配方案。
表1—16 单位电力输电费(单位：元)
解：设 x ij 为“第 i 电站向第 j 城市分配的电量”(i =1,2; j =1,2,3 )，建立模型如下：
9．某公司在 3 年的计划期内，有 4 个建设项目可以投资：项目 I 从第一年到第三年 年初都可以投资。预计每年年初投资，年末可收回本利 120%，每年又可以重新将所获本 利纳入投资计划； 项目 II 需要在第一年初投资， 经过两年可收回本利 150%，又可以重新 将所获本利纳入投资计划，但用于该项目的最大投资不得超过 20 万元；项目 III 需要在 第二年年初投资，经过两年可收回本利 160%，但用于该项目的最大投资不得超过 15 万元； 项目 IV 需要在第三年年初投资， 年末可收回本利 140%，但用于该项目的最大投资不得超 过 10 万元。在这个计划期内，该公司第一年可供投资的资金有 30 万元。问怎样的投资 方案，才能使该公司在这个计划期获得最大利润？
解：设 x i (1)
表示第一次投资项目 i ，设 x i (2)
表示第二次投资项目
投资项目 i ，(i =1,2,3,4 )，则建立的线性规划模型为
x
11
x 21
s. t.
x 11 x 21 290 x 11 x 21 320 x 12 x 22 250 x 13 x 23 270 x 13 x
23 350
x ij 0,i 1,2;j 1,2,3
i ，设 x i (3)
表示第三次 s. t.
(3) x 1
(1) x 4
x 1(2)
1.2x1
( 2)
x 1(1)
x 2(1)
30 x 3(1)
1.2x 1(1)
30 x 1(1)
x (
21)
1.5x 2(1)
1.2x 1(1)
30 x 1(1)
x 2(1)
20 15 10 0,i 1,2,3,4
x1(2) x3(1)
通过 LINGO 软件计算得： (1) x 1
(1) x
2 (1)
x 3 (1)
x 4 (1) (2) (3)
x i ,x i ,x i
10, x 2(1)
20, x 3
(1)
0,x 1(2)
12,x 1(2)
44
x 12 x 13 400 x 22 x 23 450
10．某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、
上漆几道重要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具
的利润由表 1—17 给出。问工厂应如何安排生产，使总利润最大？
表 1— 17 家具生产工艺耗时和利润表
解：设 x i 表示第 i 种规格的家具的生产量（ i =1,2, ?,5 ），则
3x 1 4x 2 6x 3 2x 4 3x
5 3600 s. t. 4x
1 2x 1 3x
2 5x
3 6x
4 4x
5 3950
3x 2 3x 3 4x 4 3x
5 2800 x i
0,i 1,2, ,5
通过 LINGO 软件计算得
： x 1 0, x 2 38,x 3 254, x 4 0,x 5 642,Z 3181
11．某厂生产甲、乙、丙三种产品，分别经过 A ，B ，C 三种设备加工。
已知生产单 位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表 2— 10 所
示。
表 1— 18 产品生产工艺消耗系数
1）建立线性规划模型，求该厂获利最大的生产计划。
2）产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到
6，求最优生产计划。
（3）产品甲的利润在多大范围内变化时，原最优计划保持不变？
（4）设备A的能力如为100+10q，确定保持原最优基不变的q 的变化范围
（5）如合同规定该厂至少生产10 件产品丙，试确定最优计划的变化。
解：（1）设x1 , x2 , x3分别表示甲、乙、丙产品的生产量，建立线性规划
模型
x1 x2 x3 100
10x1 4x2 5x3 600 s.t .
2x1 2x2 6x3 300
x1,x2,x3 0
标准化得
x1 x2 x3 x4 100
10x1 4x2 5x3 x5 600
1 2 3 5
s.t .
2x1 2x2 6x3 x6 300 x1,x2,x3,x4,x5,x6 0
列出单纯形表
8/3
故最优解为 x 1 100 / 3, x 2 200/3,x 3 0 ，又由于 x 1 , x 2 , x 3取整数，故四舍
五入可得 最优解为 x 1 33,x 2 67,x 3 0, Z max 732．
2）产品丙的利润 c 3 变化的单纯形法迭代表如下：
33
件的利润增加到大于 6.67 时，才值得安排生产。
如产品丙每件的利润增加到 6 时，此时 6<6.67 ，故原最优计划不变
3）由最末单纯形表计算出
1/6 0
1/6 0 ，新的最优解
为
01
解得 4 q 5 ，故要保持原最优基不变的 q 的变化范围为 [ 4,5] ．
（5）如合同规定该厂至少生产 10 件产品丙，则线性规划模型变成
x 1 x 2 x 3 100 10x 1 4x 2 5x 3 600
s. t. 2x 1 2x 2 6x 3 300 x 3 10
x 1, x 2 , x 3 通过 LINGO 软件计算得到： x 1 32,x 2 58,x 3 10,Z 708．
解得 6 1 1 1
6c 1 0, 4
10 2
c 1 0, 5 1 1
c 1 0， 36
15 ，即当产品甲的利润 c 1在[6,15] 范围内变化时， 原最优计划保持不变
4）由最末单纯形表找出最优基的逆为 B 1
5/3 2/3 2
第 2 章对偶规划（复习思考题）
1．对偶问题和对偶向量（即影子价值）的经济意义是什么？答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品生产带来的，同时又是资源消耗带来的。
对偶变量的值y i 表示第i 种资源的边际价值，称为影子价值。可以把对偶问题的解Y定义为每增加一个单位的资源引起的目标函数值的增量。
2．什么是资源的影子价格？它与相应的市场价格有什么区别？
答：若以产值为目标，则y i 是增加单位资源i 对产值的贡献，称为资源的影子价格（Shadow Price ）。即有“影子价格=资源成本+影子利润”。因为它并不是资源的实际价格，而是企业内部资源的配比价格，是由企业内部资源的配置状况来决定的，并不是由市场来决定，所以叫影子价格。可以将资源的市场价格与影子价格进行比较，当市场价格小于影子价格时，企业可以购进相应资源，储备或者投入生产；当市场价格大于影子价格时，企业可以考虑暂不购进资源，减少不必要的损失。
3．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？
答：（1）最优性定理：设X,Y 分别为原问题和对偶问题的可行解，且CX b T Y ，则X,Y 分别为各自的最优解。
（2）对偶性定理：若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相等。
（3）互补松弛性：原问题和对偶问题的松弛变量为X S和Y S ，它们的可行解X*,Y*为最优解的充分必要条件是Y*X S 0,Y S X *0．
4）对偶问题的最优解对应于原问题最优单纯形表中，初始基变量的检
验数的负值。
若Y S 对应于原问题决策变量x 的检验数，则Y 对应于原问题松弛变量x S 的检验数。
4．已知线性规划问题
8x1 3x2 x3 2 （第一种资源）
s. t. 6x1 x2 x3 8 （第二种资源）
x1,x2 ,x3 0
（1）求出该问题产值最大的最优解和最优值。
（2）求出该问题的对偶问题的最优解和最优值。
（3）给出两种资源的影子价格，并说明其经济含义；第一种资源限量由
2 变为4，最优解是否改变？
（4）代加工产品丁，每单位产品需消耗第一种资源 2 单位，消耗第二种资源 3 单位，
应该如何定价？
解：（1）标准化，并列出初始单纯形表
由最末单纯性表可知，该问题的最优解为：X *（0,0,2,0,6）T，即x1
0,x2 0,x3 2，
最优值为Z 4 ．
（2）由原问题的最末单纯形表可知，对偶问题的最优解和最优值为：
y1 2,y2 0,w 4 ．
（3）两种资源的影子价格分别为2、0，表示对产值贡献的大小；第一种资源限量由 2 变为 4 ，最优解不会改变。
（4）代加工产品丁的价格不低于 2 2 0 3 4 ．
5．某厂生产A，B，C，D4种产品，有关资料如表2—6 所示。
表2— 6
（1）请构造使该厂获利润最大的线性规划模型，并用单纯形法求解该问题（不计加工成本）。
（2）该厂若出租资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数学模型，资源甲、乙、丙的影子价格是多少？若工厂可在市场上买到原料丙，工厂是否应该购进该原料以扩大生产？
（3）原料丙可利用量在多大范围内变化，原最优生产方案中生产产品的品种不变（即最优基不变）？
（4）若产品 B 的价格下降了0.5 元，生产计划是否需要调整？
解：（1）设x1 , x2 , x3, x4分别表示甲、乙、丙产品的生产量，建立线性规划模型
2x1 3x2 x3 2x4 800
5x1 4x
2 3x
3 4x
4 120
s.t . 1
3x1 4x2 5x3 3x4 100
x i 0,i 1,2,
初始单纯形表
最末单纯形表
解得最优解为：X *(0,100,0,200,100)T，最优值Z 1300．
(2)原问题的对偶问题的数学模型为
2y1 5y2 3y3 1
3y1 4y2 4y3 5
s.t . y1 3y2 5y3 1
2y1 4y2 3y3 4
y1,y2,y3 0
解得影子价格分别为2、1.25 、2.5 。对比市场价格和影子价格，当市场价低于影子
价格时购进
（3）原料丙可利用量在[900,1100] 范围内变化，原最优生产方案中生产产品的品种不变（即最优基不变）。
（4）若产品 B 的价格下降了0.5 元，生产计划不需要调整。
6．某企业生产甲、乙两种产品，产品生产的工艺路线如图2— 1 所示，试统计单位
产品的设备工时消耗，填入表2—7。又已知材料、设备 C 和设备 D 等资源的单位成本和拥有量如表2—7 所示。
表2—7 资源消耗与资源成本表
据市场分析，甲、乙产品销售价格分别为13700 元和11640 元，试确定获利最大的产品生产计划。
（1）设产品甲的计划生产量为x1 ，产品乙的计划生产量为x2 ，试建立其线性规划的数学模型；若将材料约束加上松弛变量x3 ，设备C约束加上松弛变量x4 ，设备D约束加上松弛变量x5 ，试化成标准型。
（2）利用LINDO 软件求得：最优目标函数值为18400，变量的最优取值分别为
x1 20,x2 60,x3 0,x4 0,x5 300 ，则产品的最优生产计划方案是什么？并解释x3 0,x4 0,x5 300的经济意义。
（3）利用LINDO软件对价值系数进行敏感性分析，结果如下：
Obj Coefficient Ranges