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

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

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

3、型约束的左边取值大于右边 规划值，出现剩余量。4 .试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。答：可行解：满足约束条件 AX =b, X20的解，称为可行解。基可行解：满足非负性约束的基解，称为基可行解。可行基：对应于基可行解的基，称为可行基。最优解：使目标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。它们的相互关系如右图所示：5 .用表格单纯形法求解如下线性规划。8x1 3x2 x3 M 2s. t. « 6x1 +x2 + x3 < 8x1, x2,x3 >0解：标准化 max Z =4x1 x2 - 2x3s列出单

4、纯形表8x15. t. 6 6x11+ 3x2 + x3 + x4十x2十x3x1,x2,x3,x4,x5=2+ x5 = 8之041200b02831102/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-2011-12-50-20故最优解为 X* = （0,0,2,Q6）T ,即 x1 =0,x2 =0,x3 =2,此时最优值为 Z（X*）=4.6.表1 15中给出了求极大化问题的单纯形表，问表中a1,a2,c1,c2,d为何值及变量属于哪一类型

5、时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以x1代替基变量x5； （4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。表1 15某极大化问题的单纯形表000b0d4i0002-i-50i003-300i000解：(1) d 之0,C1 <0,C2 <0；(2) d之0,c1M 0,c2 M 0 (c1,c2中至少有一个为零)；d 3(3) Ci > 0, a2 > 0, > ;4 a2(4) C2 >0,ai <0;(5) Xi为人工变量，且Ci为包含M的大于零的数，d ;或者X2为人工变量，且C2为包

6、4 a2含M的大于零的数，ai >0,d >0 .7.用大M法求解如下线性规划。xi + 2x2 +x3 <i8,2xi +X2+3X3 Wi6s. t . i 23xi x2 x3 = i0Xi,X2,X3 - 0解：加入人工变量，进行人造基后的数学模型如下:s. t.xi 2x2 x3 x4 = i82xi x2 3x3 x5 = i6xi x2 x3 x6 = i0.Xi -0 (i =1,2, ,6)列出单纯形表53600-Mb0i8i2ii00i8/i0i62i30i0i6/3一 Mi0iii00ii0/i5+M3+M6+M000038/31/35/301-1/30

7、38/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-35610201-13401-10-1200-10-2一 1 一 M故最优解为 X* = (6,4,0,4,0,0)T ,即 Xi =6,X2 =4,X3 =0,此时最优值为 Z(X*)=42.8. A, B, C三个城市每年需分别供应电力 320, 250和350单位，由I , II两个电站提供，它 们的最大可供电量分别为400单位和450单位，单位费用如表1 16

8、所示。由于需要量大于可供量， 决定城市A的供应量可减少030单位，城市B的供应量不变，城市C的供应量不能少于270单位 试建立线性规划模型，求将可供电量用完的最低总费用分配方案。表1 16单位电力输电费（单位：元）鹏K城市ABC151822ii212516解：设Xj为“第i电站向第j城市分配的电量”(i =1,2; j =1,2,3 ),建立模型如下:x11 ' X12，X13 = 400X21X22X23 - 450X11x21 _290s. t .X11X21M 320X12X22= 250X13 , X23- 270X13X23M 350Xj 至 0,i =1,2; j =1,2

9、,3J9.某公司在3年的计划期内，有4个建设项目可以投资：项目I从第一年到第三年年初都可 以投资。预计每年年初投资，年末可收回本利 120%每年又可以重新将所获本利纳入投资计划； 项目II需要在第一年初投资，经过两年可收回本利150%又可以重新将所获本利纳入投资计划，但用于该项目的最大投资不得超过 20万元；项目III需要在第二年年初投资，经过两年可收回本 利160%但用于该项目的最大投资不得超过 15万元；项目IV需要在第三年年初投资，年末可收 回本利140%但用于该项目的最大投资不得超过 10万元。在这个计划期内，该公司第一年可供投 资的资金有30万元。问怎样的投资方案，才能使该公司在这个

10、计划期获得最大利润？解：设Xi表示第一次投资项目i ,设Xi表示第二次投资项目i ,设Xi表示第三次投资项目i , (i=1,2,3,4 ),则建立的线性规划模型为X1(1)+x21) <30X1十 x31) <1,2x1(1)+30-X1(1) -x21)x(3) +x=1.2X1 +1.5x2" +1.2X1(1) +30-X1(1)-x21)-X1(2)-x31)s.t. «x21) <20x31) <15x41) <10.Xi Xi(2),x(3)之 0,i =1,2,3,4通过 LINGOS件计算得：X1（1） =10,x21） =2

11、0,x31） =0,X1=12,x1=44 .10 .某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、 上漆几道重 要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具的利润由表1 17给出 问工厂应如何安排生产，使总利润最大？表1 17家具生产工艺耗时和利润表生产工序所需时间（小时）每道工序引用时 问（小时）12345346233600打磨435643950上漆233432800利润（百元）2.734.52.53解：设Xi表示第i种规格的家具的生产量(i =1,2,5),则3x1 +4x2 +6x3 +2x4 +3x5 <36004x1 +3x2 +5

12、x3 +6x4 +4x5 <3950 s. t.2x1 3x2 3x3 4x4 3x5 < 2800为 _0,i =1,2, ,5通过 LINGOS件计算得：x1 =0,x2 =38,x3 = 254, x4=0,x5 = 642,Z =3181 .11 .某厂生产甲、乙、丙三种产品，分别经过 A, B, C三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表2-10所示。表1 18产品生产工艺消耗系数甲乙丙设备能力A (小时)111100B (小时)1045600C (小时)226300单位产品利润(元)1064(1)建立线性规划模型，求该厂获利

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

14、2 + 5x3 + x5 = 6002x1 2x2 6x3 x6 =300x1 , x2, x3 , x4 , x5 , x6 -0列出单纯形表1064000b010011110010006001045010600300226001150106400004003/51/211/100200/3106012/51/201/100150018006/550-1/511500210106200/3015/65/3-1/6010100/3101/62/31/600100004-201008/310/32/30故最优解为Xi =100/3,X2 =200/3,x3 = 0 ,又由于Xi,X2,X3取整数

15、，故四舍五入可得最优解为Xi =33, X2 =67, X3 =0, ZmaX =732.(2)产品内的利润C3变化的单纯形法迭代表如下:106000b6200/3015/65/3-1/6010100/3101/6 2/31/600100004-20100C3 20/3 10/3 2/30202要使原最优计划保持不变，只要 仃3 =C3 -20W0,即C3 E6工-6.67.故当产品内每件的利润增加到大于6.67时，才值得安排生产。33如产品内每件的利润增加到6时，此时6<6.67,故原最优计划不变 (3)由最末单纯形表计算出,1c “2c ,1c仃3 = -1 - - c1 <0

16、,a4 = -10 +- c1 < 0,ct5 = 1 - c1 < 0 ,636解得6WC1W15,即当产品甲的利润C1在6,15范围内变化时，原最优计划保持不变。飞/3-1/6 0、(4)由最末单纯形表找出最优基的逆为B,= =2/3 1/6 0 ,新的最优解为20解得4 <q <5 ,故要保持原最优基不变的q的变化范围为-4,5.(5)如合同规定该厂至少生产10件产品内，则线性规划模型变成 'x1 +x2 +x3 <100 10x1 +4x2 +5x3 <600s.t. <2x +2x2 +6x3 <300 x3 >10x1,

17、x2,x3 -0通过 LINGOS件计算得到： =32% =58,x3 =10,Z =708.第2章 对偶规划(复习思考题)1 .对偶问题和对偶向量(即影子价值)的经济意义是什么？答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润， 后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品生产带来的，同时又是资源消耗带来的。对偶变量的值yi表示第i种资源的边际价值，称为影子价值。可以把对偶问题的解Y定义为每增加一个单位的资源引起的目标函数值的增量。2 .什么是资源的影子价格？它与相应的市场价格有什么区别？答：若以产值为目标，则yi是增加单位资源i对产值的

18、贡献，称为资源的影子价格(Shadow Price ) o即有“影子价格=资源成本+影子利润”。因为它并不是资源的实际价格，而是企业内部资 源的配比价格，是由企业内部资源的配置状况来决定的，并不是由市场来决定，所以叫影子价格。可以将资源的市场价格与影子价格进行比较，当市场价格小于影子价格时，企业可以购进相应资源， 储备或者投入生产；当市场价格大于影子价格时，企业可以考虑暂不购进资源，减少不必要的损失。3 .如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系?答：(1)最优性定理：设X,Y分别为原问题和对偶问题的可行解，且 CX=bTY,则X,Y分别 为各自的最优

19、解。(2)对偶性定理：若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相 等。(3)互补松弛性：原问题和对偶问题的松弛变量为Xs和Ys,它们的可行解X*,Y*为最优解的充分必要条件是Y*XS =0,YSX* = 0.(4)对偶问题的最优解对应于原问题最优单纯形表中， 初始基变量的检验数的负值。若-Ys对 应于原问题决策变量x的检验数，则-Y对应于原问题松弛变量xS的检验数。4 .已知线性规划问题8x1 +3x2 +x3 M 2 (第一种资源)5 .t. 6 6x1 +x2 +x3 <8 (第二种资源)x1, *2?3 - 0(1)求出该问题产值最大的最优解和最优值。(2)求

20、出该问题的对偶问题的最优解和最优值。(3)给出两种资源的影子价格，并说明其经济含义；第一种资源限量由2变为4,最优解是否改变？(4)代加工产品丁，每单位产品需消耗第一种资源 2单位，消耗第二种资源3单位，应该如 何定价？解：(1)标准化，并列出初始单纯形表41200b02831102/808611018/64120041/413/81/81/802013/26-5/41/4-3/412601/23/2-1/20228311006-2-20-11-12-50-20由最末单纯性表可知，该问题的最优解为：X* = (0,0,2,0,6)T ,即x1 =0,x2 = 0,x3 = 2 ,最优值为 Z

21、=4 .(2)由原问题的最末单纯形表可知，对偶问题的最优解和最优值为：yi 2, y2 = 0, w 4 .(3)两种资源的影子价格分别为2、0,表示对产值贡献的大小；第一种资源限量由 2变为4, 最优解不会改变。(4)代加工产品丁的价格不低于2m2+0m3 = 4.5.某厂生产A, B, C, D4种产品，有关资料如表26所示。表26源消耗资源产品资源供应量(公斤)原料成本(元/公斤)ABCD甲23128002.0乙543412001.0丙345310001.5单位产品售价(元)14.52115.516.5(1)请构造使该厂获利润最大的线性规划模型，并用单纯形法求解该问题(不计加工成本)(2

22、)该厂若出租资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数学模型，资 源甲、乙、丙的影子价格是多少？若工厂可在市场上买到原料丙，工厂是否应该购进该原料以扩大生产？(3)原料丙可利用量在多大范围内变化，原最优生产方案中生产产品的品种不变(即最优基 不变)？(4)若产品B的价格下降了 0.5元，生产计划是否需要调整？解：(1)设Xi,X2,X3,X4分别表示甲、乙、丙产品的生产量，建立线性规划模型2x1 +3x2 +x3 +2x4 <8005x1 +4x2 +3x3 + 4x4 <1200 s. t.3x1 4x2 5x3 3x4 < 1000xi _0,i =1,2,

23、3,4初始单纯形表1534000b08002312100800/30120054340101200/40100034530011000/41534000最末单纯形表1534000b01001/40-13/4011/4-1420020-2101-15100-3/4111/400-3/41-13/40-11/400-1/4-1ztt r t r、 、r*T> r .解得最优解为：X =(0,100,0,200,100)，最优值 Z =1300.(2)原问题的对偶问题的数学模型为2y1 + 5y2 +3y3 之 13y1十4y2 +4y3 25s.，y1 + 3y2 +5y3 之 12,+4y

24、2 +3y3 >4y1, y2, y3 -0解得影子价格分别为2、1.25、2.5。对比市场价格和影子价格，当市场价低于影子价格时购 进。(3)原料丙可利用量在900,1100范围内变化，原最优生产方案中生产产品的品种不变(即 最优基不变)。(4)若产品B的价格下降了 0.5元，生产计划不需要调整。6 .某企业生产甲、乙两种产品，产品生产的工艺路线如图 21所示，试统计单位产品的设备工时消耗，填入表27。又已知材料、设备C和设备D等资源的单位成本和拥有量如表 2-7所示。表27资源消耗与资源成本表产品资源资源消耗资源成本资源拥启量甲乙元/单位资源材料(公斤)60502004200设备C

25、(小时)3040103000设备D (小时)6050204500据市场分析，甲、乙产品销售价格分别为13700元和11640元，试确定获利最大的产品生产计(1)设产品甲的计划生产量为七,产品乙的计划生产量为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)利用L

26、INDO软件对价值系数进行敏感性分析，结果如下：Obj Coefficient RangesVariableCurrent CoefAllowable IncreaseAllowable Decrease200882024026.6773.33试问如果生产计划执行过程中，甲产品售价上升到13800元，或者乙产品售价降低60元，所制定的生产计划是否需要进行调整？(4)利用LINDO软件对资源向量进行敏感性分析，结果如下：Right hand Side RangesResourceCurrent RhsAllowable IncreaseAllowable Decrease材料4200300450

27、设备C3000360900设备D4500Infinity300试问非紧缺资源最多可以减少到多少，而紧缺资源最多可以增加到多少? 解：(1)建立的线性规划模型为”60x1 +50x2 <4200 ,30x1 +40x2 <3000s.t. 1260x1 50x2 < 4500x1,x2 _0将其标准化60x1 +50x2 + x3 =4200,30x1 + 40x2 + x4 = 3000s.t. 1260x1 50x2 x5 = 4500X -0,i =1,2, ,5(2)甲生产20件，乙生产60件，材料和设备C充分利用，设备D剩余600单位。(3)甲上升到13800需要调整

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

29、时，则已得最优解；否则，转入剪枝过程。(3)剪枝过程。在下述情况下剪除这些分枝：若某一子问题相应的线性规划问题无可行解；在分枝过程中，求解某一线性规划所得到的目标函数值 Z不优于现有下界。(4)分枝过程。当有多个待求分枝时，应先选取目标函数值最优的分枝继续进行分枝。选取一个不符合整数条件的变量xi作为分枝变量，若为的值是b*,构造两个新的约束条件：为可月或 - 、 一， 一 - 、 一， -»、一，xi引bi+1,分别并入相应的数学模型中，构成两个子问题。对任一个子问题，转步骤(1).3 .试用分枝定界法求如下线性规划:'9xi + 7x2 < 567x1 +20x2

30、<70s. t.x1,x2 _ 0x1,x2取整数解:最优整数解为：xi =4,x2 =2,Z =3404 .有4名职工，由于各人的能力不同，每个人做各项工作所用的时间不同，所花费时间如表 37所小。表37 （单位：分钟）问任务人ABCD甲15182124乙19232218丙26171619丁19212317问指派哪个人去完成哪项工作，可使总的消耗时间最少?解：设xj1 ,任务i由人员上完成1P ,任务i不由人员j完成tj为个人i对于任务j的时间耗费矩阵，则建立整数由乙完成，任务B由甲完5 .某部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五至少需要80人，周六周日每

31、天至少需要90人，先规定应聘者需连续工作5天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。解：设Xi表示在第i大应聘的雇员人数(i =1,2,3,4,5,6,7)。数学模型为X +x4 +x5 +x6 +x7 >50x1 +x2 +x5 +x6 +x7 >50x1 +x2 +x3 +x6 +x7 >50x1 +x2 +x3 +x4 +x7 >50s. t. (x1 + x2 + x3 + x4 + x5 >80x2 +x3 +x4 +x5 +x6 >90x3 +x4 +x5 + x6 +x7 >90xi 之0,i =

32、1,2,，7、xi取整数，i =1,2,，7解得：x1 = 0, x2 = 4, x3 = 32, x4 = 10, x5 = 34, x6 = 10, x7 = 4, Z = 94 .第4章 目标规划(复习思考题)1 .某计算机公司生产 A, B, C三种型号的笔记本电脑。这三种笔记本电脑需要在复杂的装配 线上生产，生产一台A, B, C型号的笔记本电脑分别需要 5小时、8小时、12小时。公司装配线正 常的生产时间是每月1700小时，公司营业部门估计A, B, C三种笔记本电脑每台的利润分别是 1000 元、1440元、2520元，而且公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑

33、以下 目标：第一目标：充分利用正常的生产能力，避免开工不足；第二目标：优先满足老客服的需求，A, B, C三种型号的电脑各为50台、50台、80台，同时 根据三种电脑三种电脑的纯利润分配不同的加权系数；第三目标：限制装配线加班时间，最好不超过 200小时；第四目标：满足各种型号电脑的销售目标，A, B, C三种型号分别为100台、120台、100台，再根据三种电脑的纯利润分配不同的加权系数；第五目标：装配线加班时间尽可能少。请列出相应的目标规划模型，并用 LINGOS件求解。解：建立目标约束。(1)装配线正常生产设生产A, B, C型号的电脑为x1,x2,x3 (台)，dT为装配线正常生产时间

34、未利用数，dj为装配 线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为(2)销售目标优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子，A, B, C三种型号的电脑每小时的利润是 照,1440，竺20,因此，老客户的销售目标约束为 5812再考虑一般销售。类似上面的讨论，得到（3）加班限制首先是限制装配线加班时间，不允许超过 200小时，因此得到 其次装配线的加班时间尽可能少，即写出目标规划的数学模型5xi +8x2 +12x3 +d-dj = 1700 x1 +d-d2+ = 50x2 +d1-d3+ = 50x3 +d4-d/ = 80s. t.+ xi +d5

35、-d5+ = 100x2 +d6-d6+=120x3 +d7-d7+=1005x1 +8x2 +12x3 +dj-d1+ = 1900 xi 至 0,i =1,2d,di 0,l =1,2, ,8经过LINGOt件计算,得到x =100,x2 =55,x3 =80,装配线生产时间为1900小时，满足装配线加班不超过200小时的要求。能够满足老客户的需求，但未能达到销售目标。销售总利润为100X 1000+55X 1440+80X 2520=380800 （元）。2 .已知3个工厂生产的产品供应给4个客户，各工厂生产量、用户需求量及从各工厂到用户 的单位产品的运输费用如表4-3所示。由于总生产量小于总需求量，上级部门经研究后，制定了 调配方案的8个目标，并规定了重要性的次序。表43工厂产量一用户需求量及运费单价（单位：兀）1234生1里152672354634523需求量（单位）200100450250第一目标：用户4为重要部门，需求量必须全部满足;第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于 80%第四目标：应尽量满足各用户的需求；第五目标：新方案的总运费不超过原运输问题(线性规划模型)的调度方案的10%第六目标：因道路限制，工厂 2到用户4的路线应尽量