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

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

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

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

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

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

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

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

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

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

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

可行基：对应于基可行解的基，称为可行基。

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

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

它们的相互关系如右图所示：5．用表格单纯形法求解如下线性规划。

s .t . ⎪⎩⎪⎨⎧≥≤++≤++0,,86238321321321x x x x x x x x x解：标准化 32124max x x x Z ++=s .t . ⎪⎩⎪⎨⎧≥=+++=+++0,,,,862385432153214321x x x x x x x x x x x x x 列出单纯形表故最优解为T X )6,0,2,0,0(*=，即2,0,0321===x x x ，此时最优值为4*)(=X Z ．6．表1—15中给出了求极大化问题的单纯形表，问表中d c c a a ,,,,2121为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以1x 代替基变量5x ；（4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。

表1—15 某极大化问题的单纯形表解：（1）0,0,021<<≥c c d ；（2）中至少有一个为零）（2121,0,0,0c c c c d ≤≤≥； （3）22134,0,0a d a c >>>； （4）0,012≤>a c ；（5）1x 为人工变量，且1c 为包含M 的大于零的数，234a d >；或者2x 为人工变量，且2c 为包含M 的大于零的数，0,01>>d a ．7．用大M 法求解如下线性规划。

s .t . ⎪⎪⎩⎪⎪⎨⎧≥=++≤++≤++0,,101632182321321321321x x x x x x x x x x x x解：加入人工变量，进行人造基后的数学模型如下：s .t . ⎪⎪⎩⎪⎪⎨⎧=≥=+++=+++=+++)6,,2,1(0101632182632153214321 i x x x x x x x x x x x x x i列出单纯形表故最优解为T X )0,0,4,0,4,6(*=，即0,4,6321===x x x ，此时最优值为42*)(=X Z ． 8．A ，B ，C 三个城市每年需分别供应电力320，250和350单位，由I ，II 两个电站提供，它们的最大可供电量分别为400单位和450单位，单位费用如表1—16所示。

由于需要量大于可供量，决定城市A 的供应量可减少0～30单位，城市B 的供应量不变，城市C 的供应量不能少于270单位。

试建立线性规划模型，求将可供电量用完的最低总费用分配方案。

表1—16 单位电力输电费（单位：元）解：设ij x 为“第i 电站向第j 城市分配的电量”（i =1,2; j =1,2,3），建立模型如下：s .t . ⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧==≥≤+≥+=+≤+≥+=++=++3,2,1;2,1,035027025032029045040023132313221221112111232221131211j i x x x x x x x x x x x x x x x x x ij9．某公司在3年的计划期内，有4个建设项目可以投资：项目I 从第一年到第三年年初都可以投资。

预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目II 需要在第一年初投资，经过两年可收回本利150%，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资不得超过20万元；项目III 需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资不得超过15万元；项目IV 需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资不得超过10万元。

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

问怎样的投资方案，才能使该公司在这个计划期获得最大利润？解：设)1(i x 表示第一次投资项目i ，设)2(i x 表示第二次投资项目i ，设)3(i x 表示第三次投资项目i ，（i =1,2,3,4），则建立的线性规划模型为s .t . ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥≤≤≤----+++=+--+≤+≤+4,3,2,1,0,,101520302.15.12.1302.130)3()2()1()1(4)1(3)1(2)1(3)2(1)1(2)1(1)1(1)1(2)2(1)1(4)3(1)1(2)1(1)1(1)1(3)2(1)1(2)1(1i x x x x x x x x x x x x x x x x x x x x x x i i i 通过LINGO 软件计算得：44,12,0,20,10)2(1)2(1)1(3)1(2)1(1=====x x x x x ． 10．某家具制造厂生产五种不同规格的家具。

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

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

问工厂应如何安排生产，使总利润最大？表1—17 家具生产工艺耗时和利润表解：设i x 表示第i 种规格的家具的生产量（i =1,2,…,5），则s .t . ⎪⎪⎩⎪⎪⎨⎧=≥≤++++≤++++≤++++5,,2,1,0280034332395046534360032643543215432154321 i x x x x x x x x x x x x x x x x i通过LINGO 软件计算得：3181,642,0,254,38,054321======Z x x x x x ．11．某厂生产甲、乙、丙三种产品，分别经过A ，B ，C 三种设备加工。

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

表1—18 产品生产工艺消耗系数（1）建立线性规划模型，求该厂获利最大的生产计划。

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

（3）产品甲的利润在多大范围内变化时，原最优计划保持不变？（4）设备A 的能力如为100+10q ，确定保持原最优基不变的q 的变化范围。

（5）如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。

解：（1）设321,,x x x 分别表示甲、乙、丙产品的生产量，建立线性规划模型s .t . ⎪⎪⎩⎪⎪⎨⎧≥≤++≤++≤++0,,3006226005410100321321321321x x x x x x x x x x x x标准化得s .t . ⎪⎪⎩⎪⎪⎨⎧≥=+++=+++=+++0,,,,,3006226005410100654321632153214321x x x x x x x x x x x x x x x x x x列出单纯形表故最优解为0,3/200,3/100321===x x x ，又由于321,,x x x 取整数，故四舍五入可得最优解为0,67,33321===x x x ,732max =Z ．（2）产品丙的利润3c 变化的单纯形法迭代表如下：要使原最优计划保持不变，只要0333≤-=c σ，即67.6363≈≤c ．故当产品丙每件的利润增加到大于6.67时，才值得安排生产。

如产品丙每件的利润增加到6时，此时6<6.67，故原最优计划不变。

（3）由最末单纯形表计算出0611,03210,0611151413≤-=≤+-=≤--=c c c σσσ，解得1561≤≤c ，即当产品甲的利润1c 在]15,6[范围内变化时，原最优计划保持不变。

（4）由最末单纯形表找出最优基的逆为⎪⎪⎪⎭⎫ ⎝⎛---=-10206/13/206/13/51B ，新的最优解为 解得54≤≤-q ，故要保持原最优基不变的q 的变化范围为]5,4[-．（5）如合同规定该厂至少生产10件产品丙，则线性规划模型变成s .t . ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≤++≤++≤++0,,1030062260054101003213321321321x x x x x x x x x x x x x通过LINGO 软件计算得到：708,10,58,32321====Z x x x ．第2章 对偶规划（复习思考题）1．对偶问题和对偶向量（即影子价值）的经济意义是什么？答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品生产带来的，同时又是资源消耗带来的。

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

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

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

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