《管理运筹学》(第二版)课后习题参考答案第1章线性规划(复习思考题)1.什么是线性规划？线性规划的三要素是什么？答：线性规划(Lin ear Programmi ng, LP )是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。

线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。

建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。

决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。

2.求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答：(1)唯一最优解：只有一个最优点；(2)多重最优解：无穷多个最优解；(3)无界解：可行域无界，目标值无限增大；(4)没有可行解：线性规划问题的可行域是空集。

当无界解和没有可行解时，可能是建模时有错。

3.什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项b i 0，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“2型约束的左边取值大于右边规划值，出现剩余量。

4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。

答：可行解：满足约束条件AX b，X 0的解，称为可行解。

基可行解：满足非负性约束的基解，称为基可行解可行基：对应于基可行解的基，称为可行基。

最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。

它们的相互关系如右图所示：5 •用表格单纯形法求解如下线性规划8论3X2 x3 2s.t. 6X-I X2 X38X i, X2,X3解：标准化maxZ 4X1 X22X38X I 3X2 X3 X4 2s.t. 6x i X2 X3 X5 8X i,X2,X3,X4,X5 0列出单纯形表故最优解为 X* （0,0,2,0,6）T，即X i 0,X2 0,X3 2，此时最优值为Z（X*） 4 .6.表1 —15中给出了求极大化问题的单纯形表，问表中 a i,a2,C i,C2,d为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以X1代替基变量X5 ; （4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。

1 150 2 -1 -5 0 1 0 0 3 -3 0 0 10 0 0解：(1) d 0,c1 0, c20 ;(2) d 0,G 0,C2 0 (C1,C2中至少有一个为零)(3)d 3 C1 0, 0,—一；4 a2(4) C2 0,a10；(5)&为人工变量，且G为包含M的大于零的数，- —;或者x为人工变量,4 a2且C2为包含M的大于零的数，a i 0,d 0 .7 •用大M法求解如下线性规划X1 2x2X3 182x1 X2 3x3 16s.t.X1 X2 X3 10X1,x 2> X3 0解：加入人工变量,进行人造基后的数学模型如下X1 2X2X3 X4 182x1 X2 3X3 X5 16s.t.10X1 X2 X3 X6X i 0 (i 1,2, ,6) 列出单纯形表-M14/31/3[2/3] 0 0—1/3 114/21 —1/20 0 1 1/2 —5/2 —63[1/2] 0 1 0 1/2—1/26 37 1/2 1 0 0 —1/2 3/2141/20 0 0 —3/24 0 0 1 1 1 —3561 0 20 1—134 0 1 —1 0 —1 2—1—2—1 — M故最优解为 X* (6,4,0,4,0,0)T，即 X i 6,X 2 4, X 3 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单位电力输电费(单位：元)城市^ A B C I 15 18 22 II212516解：设X j 为“第i 电站向第j 城市分配的电量” (i=1,2; j=1,2,3)，建立模型如下:9.某公司在3年的计划期内，有4个建设项目可以投资：项目I 从第一年到第三年 年初都可以投资。

预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本X 11400X21 450 X 11290X 11 s.t. X12X 13 X 13 X j0,ix 21 320x 22 250 x 23 270 x 23 3501,2; jX22X23X21利纳入投资计划；项目II 需要在第一年初投资，经过两年可收回本利150%，又可以重新 将所获本利纳入投资计划，但用于该项目的最大投资不得超过 20万元；项目III 需要在第二年年初投资，经过两年可收回本利 160%，但用于该项目的最大投资不得超过 15万 元；项目IV 需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资不得超过10万元。

在这个计划期内，该公司第一年可供投资的资金有 30万元。

问怎样的投资方案，才能使该公司在这个计划期获得最大利润？解：设X i ⑴表示第一次投资项目i ，设X i ⑵表示第二次投资项目i ，设X i ⑶表示第三次 投资项目i ,（i=1,2,3,4）,则建立的线性规划模型为10. 某家具制造厂生产五种不同规格的家具。

每种家具都要经过机械成型、打磨、 上漆几道重要工序。

每种家具的每道工序所用的时间、每道工序的可用时间、每种家具 的利润由表1 —17给出。

问工厂应如何安排生产，使总利润最大？表1 —17家具生产工艺耗时和利润表生产工序所需时间（小时）每道工序可用时 间（小时）12 3 4 5 成型 3 4 6 2 3 3600 打磨 4 3 5 6 4 3950 上漆 2 3 3 4 32800利润（百元）2.734.52.53解：设X i 表示第i 种规格的家具的生产量（i=1,2,…,5）,则3x 1 4X 26X 3 2X 4 3X53600 4X 1 3X 2 5x 36X 44X 53950 s.t.2x 1 3X 2 3X34X 4 3X52800X i 0,i 1,2, ,5通过 LINGO 软件计算得：X 10,X 2 38以 254, X 4 0, X 5 642,Z 3181 .11.某厂生产甲、乙、30 (3) (1) (2)x-i x 4 1.2x-i1.5xy '1.2X 1(1)30 X 1(1)xjs.t.(1)X 220x 31)15(1)X 4 10x (1),x (2)(3) ,Xi0,i 1,2,3,4通过LINGO 软件计算得：x （1）10, x 21)20, x 31)0, x 1(2)12,X ；2)⑴X 1（1X2 X 1(2)xf 1.2X !(1)30 X 1⑴ X 21)X144(2)丙三种产品，分别经过 A , B, C三种设备加工。

已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表 2 —10所示。

1 18（1）建立线性规划模型，求该厂获利最大的生产计划。

（2）产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到6，求最优生产计划。

（3）产品甲的利润在多大范围内变化时，原最优计划保持不变？（4）设备A的能力如为100+10q，确定保持原最优基不变的q的变化范围（5）如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。

解：（1）设X1,X2,X3分别表示甲、乙、丙产品的生产量，建立线性规划模型X x2x310010x14X25X3600s.t.2x12x26x3300%公2必0标准化得x1x2x3x410010x14x25x3x5600 s.t.2x12x26x3x6300X1,X2,X3,X4,X5,X6 0列出单纯形表故最优解为X i 100/3, X 2 200/3, X 3 0，又由于X i ,X 2,X 3取整数，故四舍五入可得 最优解为 X 1 33, X 2 67, X 3 0,Z maX 732 .(2)产品丙的利润C 3变化的单纯形法迭代表如下:要使原最优计划保持不变，只要3 03号，即 C 3时6.67 .故当产品丙每件的利润增加到大于6.67时，才值得安排生产。

如产品丙每件的利润增加到6时，此时6<6.67，故原最优计划不变(3)由最末单纯形表计算出10 2 01 0, 5 1 101 0，3 6 解得4 q 5，故要保持原最优基不变的q 的变化范围为［4,5］.(5)如合同规定该厂至少生产10件产品丙，则线性规划模型变成X i X 2 X 3 10011 6010, 4解得615，即当产品甲的利润01在［6,15］范围内变化时, (4)由最末单纯形表找出最优基的逆为 B5/31/6 02/3 1/6 0 ，新的最优解为 20 1原最优计划保持不变10X i 4x2 5x3 600s.t. 2x i 2x2 6x3 300X3 10X l,X2,X3 0通过LINGO 软件计算得到：x132,X258,X3 10,Z 708 .第2章对偶规划（复习思考题）1•对偶问题和对偶向量（即影子价值）的经济意义是什么？答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品生产带来的，同时又是资源消耗带来的。

对偶变量的值y i表示第i种资源的边际价值，称为影子价值。

可以把对偶问题的解Y 定义为每增加一个单位的资源引起的目标函数值的增量。

2•什么是资源的影子价格？它与相应的市场价格有什么区别？答：若以产值为目标，则y i是增加单位资源i对产值的贡献，称为资源的影子价格（Shadow Price。

即有“影子价格=资源成本+影子利润”。

因为它并不是资源的实际价格，而是企业内部资源的配比价格，是由企业内部资源的配置状况来决定的，并不是由市场来决定，所以叫影子价格。

可以将资源的市场价格与影子价格进行比较，当市场价格小于影子价格时，企业可以购进相应资源，储备或者投入生产；当市场价格大于影子价格时，企业可以考虑暂不购进资源，减少不必要的损失。