1、1管理运筹学 （第二版）课后习题参考答案第 1 章 线性规划（复习思考题）1什么是线性规划？线性规划的三要素是什么？答：线性规划（Linear Programming，LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值
2、。2求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答：（1）唯一最优解：只有一个最优点；（2）多重最优解：无穷多个最优解；（3）无界解：可行域无界，目标值无限增大；（4）没有可行解：线性规划问题的可行域是空集。当无界解和没有可行解时，可能是建模时有错。3什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项 ，0ib决策变量满足非负性。如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“”型约束的左边取值大于右边规划值，
3、出现剩余量。4试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。答：可行解：满足约束条件 的解，称为可行解。0XbA，基可行解：满足非负性约束的基解，称为基可行解。可行基：对应于基可行解的基，称为可行基。最优解：使目标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：25用表格单纯形法求解如下线性规划。 3214maxxZs.t. 0,868321x解：标准化 3214axZs.t. 0,862854321xx列出单纯形表 jc4 1 2 0 0BCBXb 1x23x45xi0 4x2 8 3 1 1 0 2/80 58 6
4、1 1 0 1 8/6j4 1 2 0 04 1x1/4 1 3/8 1/8 1/8 0 (1/4)/(1/8)0 513/2 6 5/4 1/4 3/4 1 (13/2)/(1/4)j0 1/2 3/2 -1/2 02 3x2 8 3 1 1 00 56 2 2 0 1 1j12 5 0 2 0故最优解为 ，即 ，此时最优值为 TX),0(*,321xx 4*)(XZ6表 115 中给出了求极大化问题的单纯形表，问表中 为何值及变dca,21量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以 代替基变量 ；（4）该线性规划问题具有无界解；（5）
5、该线1xx3性规划问题无可行解。表 115 某极大化问题的单纯形表jc1c20 0 0BCBXb x3x45xi0 3xd 4 1a1 0 00 42 1 5 0 1 00 5x3 23 0 0 1j1c20 0 0解：（1） ；0,021cd（2） ；中 至 少 有 一 个 为 零 ）（ 1,c（3） ；22134,0,ac（4） ；,12（5） 为人工变量，且 为包含 M 的大于零的数， ；或者 为人工变量，x1c 234ad2x且 为包含 M 的大于零的数， 2c 0,1da7用大 M 法求解如下线性规划。 32165maxxZs.t. 0,8321x解：加入人工变量，进行人造基后的数学
6、模型如下： 654321065ma MxxZs.t. )6,21(083215ixxi4列出单纯形表 jc5 3 6 0 0 MBCXb 1x23x45x6xi0 4x18 1 2 1 1 0 0 18/10 516 2 1 3 0 1 0 16/3M 6x10 1 1 1 0 0 1 10/1j5+M 3+M 6+M 0 0 00 4x38/3 1/3 5/3 0 1 1/3 0 38/56 316/3 2/3 1/3 1 0 1/3 0 16M 6x14/3 1/3 2/3 0 0 1/3 1 14/2jM3120 0 M3200 4x1 1/2 0 0 1 1/2 5/2 6 33 1/
7、2 0 1 0 1/2 1/2 63 2x7 1/2 1 0 0 1/2 3/2 14j1/2 0 0 0 3/2 M230 4x4 0 0 1 1 1 35 16 1 0 2 0 1 13 2x4 0 1 1 0 1 2j0 0 1 0 2 1 M故最优解为 ，即 ，此时最优值TX),6(*,4,632xx为 42)(Z8A，B，C 三个城市每年需分别供应电力 320，250 和 350 单位，由 I，II 两个电站提供，它们的最大可供电量分别为 400 单位和 450 单位，单位费用如表 116 所示。由于需要量大于可供量，决定城市 A 的供应量可减少 030 单位，城市 B 的供应5量不
8、变，城市 C 的供应量不能少于 270 单位。试建立线性规划模型，求将可供电量用完的最低总费用分配方案。表 116 单位电力输电费（单位：元）电站 城市 A B CI 15 18 22II 21 25 16解：设 为“第 i 电站向第 j 城市分配的电量” （i=1,2; j=1,2,3） ，建立模型如下：ijx 232211312 6585ma xxxZs.t. 3,21;,0573209452311213jixxij9某公司在 3 年的计划期内，有 4 个建设项目可以投资：项目 I 从第一年到第三年年初都可以投资。预计每年年初投资，年末可收回本利 120%，每年又可以重新将所获本利纳入投资
9、计划；项目 II 需要在第一年初投资，经过两年可收回本利 150%，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资不得超过 20 万元；项目 III需要在第二年年初投资，经过两年可收回本利 160%，但用于该项目的最大投资不得超过 15 万元；项目 IV 需要在第三年年初投资，年末可收回本利 140%，但用于该项目的最大投资不得超过 10 万元。在这个计划期内，该公司第一年可供投资的资金有 30 万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？解：设 表示第一次投资项目 i，设 表示第二次投资项目 i，设 表示第三)1(ix)2(ix)3(ix次投资项目 i， （i=1
10、,2,3,4 ） ，则建立的线性规划模型为 )1(4)1(3)3(1.6.2.maxZ6s.t. 4,321,0,5302.1.2.1)3(2)1(14)( )1(3)2()1()()()()()(4)3(1 213)1()(ixxxxxxiii通过 LINGO 软件计算得： 4)2(1)()(3)(2)(1 xx10某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、上漆几道重要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具的利润由表 117 给出。问工厂应如何安排生产，使总利润最大？表 117 家具生产工艺耗时和利润表所需时间（小时）生产工序1 2 3 4
11、 5每道工序可用时间（小时）成型 3 4 6 2 3 3600打磨 4 3 5 6 4 3950上漆 2 3 3 4 3 2800利润（百元） 2.7 3 4.5 2.5 3解：设 表示第 i 种规格的家具的生产量（i=1,2,5） ，则ix 54321.5.7.ma xxZs.t. 5,21,0280396465431ixxxi通过 LINGO 软件计算得： 318,642,4,532 Zx11某厂生产甲、乙、丙三种产品，分别经过 A， B，C 三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表 210 所示。表 118 产品生产工艺消耗系数甲 乙 丙 设
12、备能力A（小时） 1 1 1 1007B（小时） 10 4 5 600C（小时） 2 2 6 300单位产品利润（元）10 6 4（1）建立线性规划模型，求该厂获利最大的生产计划。（2）产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到 6，求最优生产计划。（3）产品甲的利润在多大范围内变化时，原最优计划保持不变？（4）设备 A 的能力如为 100+10q，确定保持原最优基不变的 q 的变化范围。（5）如合同规定该厂至少生产 10 件产品丙，试确定最优计划的变化。解：（1）设 分别表示甲、乙、丙产品的生产量，建立线性规划模型321,x32460maxZs.t. 0,51132
13、1x标准化得 654321 06ma xxZs.t. 0,54016543214xx列出单纯形表 jc10 6 4 0 0 0BCXb 1x23x45x6i0 4x100 1 1 1 1 0 0 1000 5600 10 4 5 0 1 0 600 6300 2 2 6 0 0 1 150j10 6 4 0 0 00 4x40 0 3/5 1/2 1 1/10 0 200/3810 1x60 1 2/5 1/2 0 1/10 0 1500 6180 0 6/5 5 0 1/5 1 150j0 2 1 0 1 06 2x200/3 0 1 5/6 5/3 1/6 010 1100/3 1 0 1
14、/6 2/3 1/6 00 6100 0 0 4 2 0 1j0 0 8/3 10/3 2/3 0故最优解为 ，又由于 取整数，故四舍五入可,3/2,/1xx 321,x得最优解为 , 67,3321x7maZ（2）产品丙的利润 变化的单纯形法迭代表如下：cjc10 6 3c0 0 0BCXb 1x2x45x6i6 2x200/3 0 1 5/6 5/3 1/6 010 1100/3 1 0 1/6 2/3 1/6 00 6100 0 0 4 2 0 1j0 0 20/33c 10/3 2/3 0要使原最优计划保持不变，只要 ，即 故当产品丙067.3c每件的利润增加到大于 6.67 时，才值
15、得安排生产。如产品丙每件的利润增加到 6 时，此时 66.67，故原最优计划不变。（3）由最末单纯形表计算出，061,0321,015143 ccc解得 ，即当产品甲的利润 在 范围内变化时，原最优计划保持不561c ,6变。（4）由最末单纯形表找出最优基的逆为 ，新的最优解为1026/3/51B)(3306102/3/51 qqbBX解得 ，故要保持原最优基不变的 q 的变化范围为 4q 5,49（5）如合同规定该厂至少生产 10 件产品丙，则线性规划模型变成321460maxxZs.t. 0,150321321x通过 LINGO 软件计算得到： 708,1,58,231 Zx第 2 章 对
16、偶规划（复习思考题）1对偶问题和对偶向量（即影子价值）的经济意义是什么？答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品生产带来的，同时又是资源消耗带来的。对偶变量的值 表示第 i 种资源的边际价值，称为影子价值。可以把对偶问题的iy解 Y 定义为每增加一个单位的资源引起的目标函数值的增量。 2什么是资源的影子价格？它与相应的市场价格有什么区别？答：若以产值为目标，则 是增加单位资源 i 对产值的贡献，称为资源的影子价iy格（Shadow Price） 。即有 “影子价格= 资源成本+影子利润”
17、 。因为它并不是资源的实际价格，而是企业内部资源的配比价格，是由企业内部资源的配置状况来决定的，并不是由市场来决定，所以叫影子价格。可以将资源的市场价格与影子价格进行比较，当市场价格小于影子价格时，企业可以购进相应资源，储备或者投入生产；当市场价格大于影子价格时，企业可以考虑暂不购进资源，减少不必要的损失。3如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？答：（1）最优性定理：设 分别为原问题和对偶问题的可行解，且 ，YX, YbXCT10则 分别为各自的最优解。YX,（2）对偶性定理：若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相等。（3
18、）互补松弛性：原问题和对偶问题的松弛变量为 和 ，它们的可行解SXY为最优解的充分必要条件是 *,YX 0,*YXS（4）对偶问题的最优解对应于原问题最优单纯形表中，初始基变量的检验数的负值。若 对应于原问题决策变量 x 的检验数，则 对应于原问题松弛变量 的检验S Sx数。4已知线性规划问题 3214maxxZs.t. 0,868321x（ 第 二 种 资 源 ）（ 第 一 种 资 源 ）（1）求出该问题产值最大的最优解和最优值。（2）求出该问题的对偶问题的最优解和最优值。（3）给出两种资源的影子价格，并说明其经济含义；第一种资源限量由 2 变为4，最优解是否改变？（4）代加工产品丁，每单位产品需消耗第一种资源 2 单位，消耗第二种资源 3 单位，应该如何定价？解：（1）标准化，并列出初始单纯形表 jc4 1 2 0 0BCBXb 1x23x45xi0 4x2 8 3 1 1 0 2/80 58 6 1 1 0 1 8/6j4 1 2 0 0
