管理运筹学第二版课后习题参考答案

1、管理运筹学 （第二版）课后习题参考答案第 1 章 线性规划（复习思考题）1什么是线性规划？线性规划的三要素是什么？答：线性规划（Linear Programming , LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。 线性规划属于规划论中的静态规划， 是一种重要的优化工具，能够解决有限资源的最佳分配问题。建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求

2、极小值。2求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答： （ 1）唯一最优解：只有一个最优点；（ 2）多重最优解：无穷多个最优解；（ 3）无界解：可行域无界，目标值无限增大；（ 4）没有可行解：线性规划问题的可行域是空集。当无界解和没有可行解时，可能是建模时有错。3什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项 bi 0 ，决策变量满足非负性。如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“学”型约束的左

3、边取值大于右边规划值，出现剩余量。4 .试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系答：可行解：满足约束条件 AX b, X 0的解，称为可行解。基可行解：满足非负性约束的基解，称为基可行解。可行基：对应于基可行解的基，称为可行基。最优解：使目标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。它们的相互关系如右图所示：5 .用表格单纯形法求解如下线性规划。8x1 3x2 x32s.t.6x1 x2 x3 8X1,X2,X30解：标准化 maxZ 4x1 x2 2x38x1 3x2 x3 x425 .t.6x1 x2 x3x5 8x1,x2,x3,x

4、4,x50列出单纯形表41200b02831102/808611018/64120041/413/81/81/80(1/4)/(1/8)013/26 5/41/4-3/41(13/2)/(1/4)0 1/23/2-1/20228311006-2-20-1112-50-20故最优解为 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）下一步迭代将以xi代替基变量X5； （4）该线性

5、规划问题具有无界解；（5）该线性规划问题无可行解000b0d4i0002-i-50i003-300i000解：(1) d 0,C10,C20；(2) d 0,ci 0c 0(g,C2中至少有一个为零)；一d 3(3) Ci0, a20, ；4 a2(4) C20,ai0;(5) xi为人工变量，且Ci为包含M的大于零的数，d 且；或者X2为人工变量，且C2 4 a2为包含M的大于零的数，ai0,d 0.7.用大M法求解如下线性规划xi 2x2 x3 i82xi x2 3x3 i6 s. t.xi x2 x3 i0xi,x2,x30解：加入人工变量，进行人造基后的数学模型如下:Xi2X2X3X4

6、182xiX23X3 X516XiX2X3X610X0(i 1,2,6)s. t .列出单纯形表53600一 Mb01812110018/101621301016/3-M1011100110/15+M3+M6+M000038/31/35/301-1/3038/5616/32/31/3101/3016一 M14/31/32/300-1/3114/200001 1/20011/2 5/2一6310101/2-1/26371/2100 1/23/2141/2000 3/20400111-3561020113401-10-1200-10-2一 1 一 M故最优解为 X* (6,4,0,4,0,0)T

7、,即 Xi 6,X2 4, X3 0,此时最优值为 Z(X*)42 .8. A, B, C三个城市每年需分别供应电力 320, 250和350单位，由I , II两个电站提供，它们的最大可供电量分别为 400单位和450单位，单位费用如表1 16所示。由于 需要量大于可供量，决定城市 A的供应量可减少030单位，城市B的供应量不变，城市C的供应量不能少于270单位。试建立线性规划模型，求将可供电量用完的最低总费用分 配方案。表1 16单位电力输电费(单位：元)城 市、ABCI151822II212516解：设Xj为“第i电站向第j城市分配的电量" (i =1,2; j =1,2,3)

8、,建立模型如下:x11x21320x12x22250x13x23270x13x23350xij0,i1,2; j 1,2,3x22 x23x11x21 290s. t.x11x12 x13 400x214509某公司在3 年的计划期内，有4 个建设项目可以投资：项目 I 从第一年到第三年年初都可以投资。预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目 II 需要在第一年初投资，经过两年可收回本利150%，又可以重新将所获本利纳入投资计划， 但用于该项目的最大投资不得超过20 万元； 项目 III 需要在第二年年初投资，经过两年可收回本利160%，但用于该项目

9、的最大投资不得超过15 万元；项目IV 需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30 万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？x1(1)x2(1)30解：设x(1)表示第一次投资项目i ,设x(2)表示第二次投资项目i ,设Xi表示第三次投 资项目 i ， ( i =1,2,3,4 ) ，则建立的线性规划模型为x1(2)x3(1)1.2x1(1)30x1(1)x(21)x1(3)x(41)1.2x1(2)1.5x2(1)1.2x1(1)30x1(1)x2(1)x1(2)x3(1)s.

10、 t.(1) x2(1) x4(1)(2)(3)xi , xi, xi2015100,i 1,2,3,4通过 LINGOS件计算得：x(1)10,x21)20, x31)0,x112,x144.10 .某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、上 漆几道重要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具的利 润由表1 17给出。问工厂应如何安排生产，使总利润最大？表1 17家具生产工艺耗时和利润表生产工序所需时间（小时）每道工序引用时问（小时）12345346233600打磨435643950上漆233432800利润（百元）2.734.52.53解

11、：设x表示第i种规格的家具的生产量（i =1,2,5）,则3x14x26x32x43x536004x13x25x36x44x539502x13x23x34x43x52800XiQi1,2,5s. t.通过 LINGOS件计算得：X 0,x238, X3254, X4 0, X5 642,Z3181.11 .某厂生产甲、乙、丙三种产品，分别经过A, B, C三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表2-10所示。表1 18产品生产工艺消耗系数甲乙丙设备能力A (小时)111100B (小时)1045600C (小时)226300单位产品利润(元)106

12、4(1)建立线性规划模型，求该厂获利最大的生产计划。(2)产品内每件的利润增加到多大时才值得安排生产？如产品内每件的利润增加到6,求最优生产计划。(3)产品甲的利润在多大范围内变化时，原最优计划保持不变?(4)设备A的能力如为100+10q,确定保持原最优基不变的q的变化范围。(5)如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。解：(1)设X1,X2,X3分别表示甲、乙、丙产品的生产量，建立线性规划模型X1 X2 X3 100s. t.10x1 4x2 5x3 6002X1 2x2 6x3 300X1,X2.X30标准化得x1 x2 x3 x4 100s t 10x1 4x2 5x

13、3 x5 6002x1 2x2 6x3 x6 300%?2,乂3,乂4?5?60列出单纯形表1064000b010011110010006001045010600300226001150106400004003/51/21一0200/31/10106012/51/201/100150018006/550-1/5115002-10-106200/3015/65/3-1/6010100/3101/6 2/31/600100004-20100 8/310/3 2/30故最优解为X1 100/3, X2 200/3, X3 0,又由于xhX2,X3取整数，故四舍五入可得最优解为 X133, X2 67

14、,X3 0, Zmax 732.(2)产品内的利润C3变化的单纯形法迭代表如下:106000b6200/3015/65/3-1/6010100/3101/6 2/31/600100004-20100C3 20/310/3 2/30要使原最优计划保持不变，只要 3 c330,即C3 6- 6.67 .故当产品内每件33的利润增加到大于6.67时，才值得安排生产。如产品内每件的利润增加到6时，此时6<6.67,故原最优计划不变。(3)由最末单纯形表计算出12131 -Ci 0, 410 Cl0, 5 1 -cl0,636解得6 C1 15,即当产品甲的利润C1在6,15范围内变化时，原最优计

15、划保持不变5/31/6 0（4）由最末单纯形表找出最优基的逆为B 12/3 1/ 60 ，新的最优解为201解得 4 q 5 ，故要保持原最优基不变的 q 的变化范围为 4,5 （ 5）如合同规定该厂至少生产10 件产品丙，则线性规划模型变成x3 1005x36006x3300100x132, x258,x3 10,Z 708 第 2 章 对偶规划（复习思考题）1对偶问题和对偶向量（即影子价值）的经济意义是什么？答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品生产带来的，同时又是资源消耗带来的。

16、对偶变量的值yi 表示第i 种资源的边际价值，称为影子价值。可以把对偶问题的解Y定义为每增加一个单位的资源引起的目标函数值的增量。2什么是资源的影子价格？它与相应的市场价格有什么区别？答：若以产值为目标，则yi 是增加单位资源i 对产值的贡献，称为资源的影子价格s. t.x1 10x1 2x1x24x22x2x3x1,x2 , x3通过LINGOS件计算得到:ShadowPrice ） 。即有“影子价格=资源成本+影子利润”因为它并不是资源的实际价格,而是企业内部资源的配比价格，是由企业内部资源的配置状况来决定的，并不是由市场来 决定，所以叫影子价格。可以将资源的市场价格与影子价格进行比较，当

17、市场价格小于影 子价格时，企业可以购进相应资源，储备或者投入生产；当市场价格大于影子价格时，企 业可以考虑暂不购进资源，减少不必要的损失。3.如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数 之间的关系？答：(1)最优性定理：设X,Y分别为原问题和对偶问题的可行解，且CX bTY,则X,Y 分别为各自的最优解。(2)对偶性定理：若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函 数值相等。(3)互补松弛性：原问题和对偶问题的松弛变量为XS和YS,它们的可行解X*,Y*为最优解的充分必要条件是Y Xs 0,YsX0.(4)对偶问题的最优解对应于原问题最优单纯形表中

18、，初始基变量的检验数的负值。若 Ys对应于原问题决策变量x的检验数，则 Y对应于原问题松弛变量xs的检验数。4 .已知线性规划问题8x1 3x2 x3 2 (第一种资源)5 .t.6x1 x2 x3 8 (第二种资源)x1,x2,x30(1)求出该问题产值最大的最优解和最优值。(2)求出该问题的对偶问题的最优解和最优值。(3)给出两种资源的影子价格，并说明其经济含义；第一种资源限量由2变为4,最优解是否改变？(4)代加工产品丁，每单位产品需消耗第一种资源 2单位，消耗第二种资源3单位，应该如何定价？41200b02831102/808611018/64120041/413/81/81/8020

19、13/26 5/41/4-3/412601/23/2-1/20228311006-2-20-11-12-50-20解：(1)标准化，并列出初始单纯形表由最末单纯性表可知，该问题的最优解为:X(0,020,6)T,即 X10,X20,X32(2)由原问题的最末单纯形表可知，对偶问题的最优解和最优值为:y12, y2 0,w 4 .(3)两种资源的影子价格分别为2、0,表示对产值贡献的大小；第一种资源限量由 2变为4,最优解不会改变(4)代加工产品丁的价格不低于2 2 0 3 4.5 .某厂生产A, B, C, D4种产品，有关资料如表26所示表26资源消耗资源产品资源供应量(公斤)原料成本(元/

20、公斤)ABCD甲23128002.0乙543412001.0丙345310001.5单位产品售价(元)14.52115.516.5(1)请构造使该厂获利润最大的线性规划模型，并用单纯形法求解该问题(不计加工成本)(2)该厂若出租资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数学模型，资源甲、乙、丙的影子价格是多少？若工厂可在市场上买到原料丙，工厂是否应该购进该原料以扩大生产？(3)原料丙可利用量在多大范围内变化，原最优生产方案中生产产品的品种不变(即 最优基不变)？(4)若产品B的价格下降了 0.5元，生产计划是否需要调整？解:(1)设X1,X2,X3,X4分别表小甲、乙、丙产品的生产

21、量,建立线性规划模型2x1 3x2 x3 2x4800t5x1 4x2 3x3 4x4 1200. . .3x1 4x2 5x3 3x41000xi0,i 1,2,3,4初始单纯形表1534000b08002312100800/30120054340101200/40100034530011000/41534000最末单纯形表i534000b0i00i/40-i3/40ii/4-i420020-2i0i-i5i00-3/4iii/400-3/4i-i3/40-ii/400-i/4-i解得最优解为：X* (Q100,0,200,100)T ,最优值Z 1300.(2)原问题的对偶问题的数学模型为

22、2yi 5 y2 3y313yi 4 y2 4y35s.t. yi 3y2 5y312yi 4y2 3y34yi,y2, y30解得影子价格分别为2、i.25、2.5。对比市场价格和影子价格，当市场价低于影子价格时购进。(3)原料丙可利用量在900,ii00范围内变化，原最优生产方案中生产产品的品种不 变(即最优基不变)。(4)若产品B的价格下降了 0.5元，生产计划不需要调整。6 .某企业生产甲、乙两种产品，产品生产的工艺路线如图2i所示，试统计单位产品的设备工时消耗，填入表27。又已知材料、设备C和设备D等资源的单位成本和拥有量如表2 7所小o表27资源消耗与资源成本表产品资源资源消耗资源

23、成本资源拥启量甲乙元/单位资源材料(公斤)60502004200设备C (小时)3040103000设备D (小时)6050204500据市场分析，甲、乙产品销售价格分别为 13700元和11640元，试确定获利最大的产品生产计划。(1)设产品甲的计划生产量为人,产品乙的计划生产量为X2 ,试建立其线性规划的数学模型；若将材料约束加上松弛变量 X3,设备C约束加上松弛变量X4,设备D约束加上松 弛变量X5 ,试化成标准型。(2)利用LINDO软件求得：最优目标函数值为 18400,变量的最优取值分别为X120, X260,X3 0,X40,X5300 ,则产品的最优生产计划方案是什么？并解释X

24、30,X4 0, X5 300的经济意义。(3)利用LINDO软件对价值系数进行敏感性分析，结果如下：Obj Coefficient RangesVariableCurrent CoefAllowableIncreaseAllowable Decrease200882024026.6773.33试问如果生产计划执行过程中，甲产品售价上升到13800元，或者乙产品售价降低60元，所制定的生产计划是否需要进行调整？(4)利用LINDO软件对资源向量进行敏感性分析，结果如下:Right hand Side RangesResourceCurrent RhsAllowableIncreaseAllow

25、able Decrease材料4200300450设备C3000360900设备D4500Infinity300试问非紧缺资源最多可以减少到多少，而紧缺资源最多可以增加到多少?解：(1)建立的线性规划模型为60Xi 50X24200,30X1 40X2 3000s. t.60Xi 50X24500Xi,X20将其标准化60x1 50x2 x3 420030x1 40x2 x43000s.t.60x1 50x2 x5 4500 xi0,i 1,2, ,5（2）甲生产20件，乙生产60件，材料和设备C充分利用，设备D剩余600单位。（3）甲上升到13800需要调整，乙下降60不用调整。（ 4） 非

26、紧缺资源设备D 最多可以减少到300， 而紧缺资源材料最多可以增加到300，紧缺资源一设备C最多可以增加到360。第 3 章 整数规划（复习思考题）1整数规划的类型有哪些？答：纯整数规划、 0-1 规划和混合整数规划。2试述整数规划分枝定界法的思路。答： （ 1 ）首先不考虑整数条件，求解整数规划相应的线性规划问题。若相应的线性规划问题没有可行解，停止计算，这时原整数规划也没有可行解。（ 2）定界过程。对于极大化的整数规划问题，当前所有未分枝子问题中最大的目标函数值为整数规划问题上界；在满足整数约束的子问题的解中，最大的目标函数值为整数规划问题的下界。当上下界相同时，则已得最优解；否则，转入剪

27、枝过程。（3）剪枝过程。在下述情况下剪除这些分枝：若某一子问题相应的线性规划问题无可行解；在分枝过程中，求解某一线性规划所得到的目标函数值Z不优于现有下界。（4）分枝过程。当有多个待求分枝时，应先选取目标函数值最优的分枝继续进行分枝。选取一个不符合整数条件的变量 Xi作为分枝变量，若Xi的值是bi ,构造两个新的约束条件:Xi b；或为b* 1,分别并入相应的数学模型中，构成两个子问题。对任一个子问题,转步骤（1）.3 .试用分枝定界法求如下线性规划:s. t.9X1 7x2 567X120X270Xi,X2Xi,X20取整数最优整数解为:4, X2 2,Z3404.有4名职工，由于各人的能力

28、不同，每个人做各项工作所用的时间不同，所花费时I可如表3 7所小。时间26表37 （单位：分钟）AB15班=工工 917- = 327-3;r-i;k=4,2, 1 = 3乙：10下界 16 最21上聚丁 34922改孑5182 1 . 2 =341 7 23?241819丁19212317问指派哪个人去完成哪项工作，可使总的消耗时间最少?解：设xj 1 '彳尸成二，tj为个人i对于任务j的时间耗费矩阵，则建0 ,任务i不由人员j完成立整数规划模型为:xj 15. t .xj1xj0 或 1,i,j1,2,3,4解得：X12 1,X211,X331,X44 1 ,其余均为零，Z 70,

29、即任务A由乙完成，任务B由甲完成，任务C由内完成，任务D由丁完成。5.某部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五至少需要80人，周六周日每天至少需要90人，先规定应聘者需连续工作 5天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。解：设xi表小在第i天应聘的雇员人数(i=1,2,3,4,5,6,7)。数学模型为x1x4乂5%x750Xx2乂5x6x750x1x2乂3x6x750x1x2乂3x4x750x1x2乂3x4乂580x2乂3x4乂5x690x3x4乂5乂6x790xi0,i1,2,7xi取整数，i1,2,7s. t.解得：

30、x10,x24,x332, x4 10, x5 34, x6 10, x74,Z 94 第 4 章 目标规划（复习思考题）1 .某计算机公司生产A, B, C三种型号的笔记本电脑。这三种笔记本电脑需要在复杂 的装配线上生产，生产一台 A, B, C型号的笔记本电脑分别需要 5小时、8小时、12小时。 公司装配线正常的生产时间是每月1700小时，公司营业部门估计 A, B, C三种笔记本电脑每台的利润分别是1000 元、 1440 元、 2520 元，而且公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标：第一目标：充分利用正常的生产能力，避免开工不足；第二目标：优先满足老客服的需

31、求，A， B， C 三种型号的电脑各为 50 台、 50 台、 80台，同时根据三种电脑三种电脑的纯利润分配不同的加权系数；第三目标：限制装配线加班时间，最好不超过200 小时；第四目标：满足各种型号电脑的销售目标，A, B, C三种型号分别为100台、120台、100 台，再根据三种电脑的纯利润分配不同的加权系数；第五目标：装配线加班时间尽可能少。请列出相应的目标规划模型，并用LINGOt件求解。解：建立目标约束。（ 1）装配线正常生产设生产A,B,C型号的电脑为X1,X2,X3（台）,d1为装配线正常生产时间未利用数，d1为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约

32、束为A, B, C三种(2)销售目标优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子,型号的电脑每小时的利润是 , ,52°,因此，老客户的销售目标约束为5812再考虑一般销售。类似上面的讨论，得到(3)加班限制首先是限制装配线加班时间，不允许超过 200小时，因此得到其次装配线的加班时间尽可能少，即写出目标规划的数学模型s. t .5x1X1 X2X3X1X2X3 5X1Xi8x28x2 Qidi ,di12x3 d150508010012010012x3d11,20,l 1,2, ,8经过LINGO软件计算，得到d1d1X X2 55心 80

33、,装配线生产时间为1900小时,满足装配线加班不超过200小时的要求。能够满足老客户的需求，但未能达到销售目标。销售总禾I润为 100X 1000+55X 1440+80X 2520=380800 （元）。2 .已知3个工厂生产的产品供应给4个客户，各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费用如表 43所示。由于总生产量小于总需求量，上级部门经研 究后，制定了调配方案的8个目标，并规定了重要性的次序。表43工厂产量一用户需求量及运费单价（单位：元）用 户、1234生1里152672354634523需求量（单位）200100450250第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于 80%第四目标：应尽量满足各用户的需求；第五目标：新方案的总运费不超过原运输问题（线性规划模型）的调度方案的10%第六目标：因道路限制，工厂 2到用户4的路线应尽量避免运输任务；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少总运费。请