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

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

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

3、右边规划值，出现剩余量。4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。答：可行解：满足约束条件 AX b，X 0的解，称为可行解。基可行解：满足非负性约束的基解，称为基可行解可行基：对应于基可行解的基，称为可行基。最优解：使目标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。它们的相互关系如右图所示：5 用表格单纯形法求解如下线性规划8x-i3x2X326x1X2X38X1,X2,X30解：标准化maxZ4x1X22X38x13x2X3X42.6x1X2X3X58X1,X2,X3,X4,X50列出单纯形表41200b02831102/80861

4、1018/64120041/413/81/81/80(1/4)/(1/8)013/265/41/43/41(13/2)/(1/4)01/23/2-1/20228311006-22011125020故最优解为 X*（0,0,2,0,6）T，即Xi 0,x20,X3 2，此时最优值为Z（X*）4 .6表1 15中给出了求极大化问题的单纯形表，问表中 a1,a2,c1,c2,d为何值及变量 属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3） 下一步迭代将以xi代替基变量X5; （4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。表1 15某极大化问题的单纯形

5、表000b0d4100021 5010033001000解：(1)d 0,Ci0,C20 ；(2)d0,Ci0,C20(C1,C2中至少有一个为零)7d3(3)Ci0, a20,74a2(4)C20®0 ；(5) 刘为人工变量，且G为包含M的大于零的数，-;或者X2为人工变量,4 a2且C2为包含M的大于零的数，a!0,d0 .7 用大M法求解如下线性规划。X12x2X3182x1X23X316XX2X310X1,X2,X30解：加入人工变量，进行人造基后的数学模型如下X12x2X3X4182x1X23x3 X516X1X2X3X610X0(i1,2,6)列出单纯形表5 3600 M

6、b01812110018/101621301016/3-M1011100110/15+M3+M6+M000038/31/35/3011/3038/5616/32/31/3101/3016M14/31/32/3001/3114/2000011/20011/25/2631/20101/21/26371/21001/23/2141/20003/2040011135610201134011012001021 M故最优解为 X* (6,4,0,4,0,0)t，即 Xi 6,X24, X3 0，此时最优值为 Z(X*)42 .8. A, B, C三个城市每年需分别供应电力320, 250和350单位，由I

7、 ,11两个电站提供，它们的最大可供电量分别为 400单位和450单位，单位费用如表116所示。由 于需要量大于可供量，决定城市 A的供应量可减少030单位，城市B的供应量不变， 城市C的供应量不能少于270单位。试建立线性规划模型，求将可供电量用完的最低总 费用分配方案。表1 16单位电力输电费(单位：元)X11X21290X11X21320X12X22250X13X23270X13X23350站城市ABCI151822II212516i解：设xij为“第X11X12X21X22x13400X23 450电站向第j城市分配的电量” (i =1,2; j =1,2,3 ),建立模型如下:冷 0

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

9、该公司在这个计划期获得最大利润解：设x X2表示第一次投资项目i，设Xi(1)X3表示第二次投资项目i，设x(1) X4(1)(2)(3)Xi ,Xi , Xi表示第三次 投资项目i ，(i =1,2,3,4)，则建立的线性规划模型为x(3)xfX1X21)30X1(2)x31)1.2X11.2x12)1.5x(1) v(1)1 x230 X1 xj30 x；1.2x1(1)X1x31)2015100,i123,4通过LINGO软件计算得:(1)%10,20, x31)0X12x4410某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、上漆几道重要工序。每种家具的每道工序所用

10、的时间、每道工序的可用时间、每种家具 的利润由表1 17给出。问工厂应如何安排生产，使总利润最大表1 17家具生产工艺耗时和利润表生产工序所需时间（小时）每道工序可用时间（小时）12345成型346233600打磨435643950上漆233432800利润（百元）33解：设Xi表示第i种规格的家具的生产量（i=1,2,5 ），则3x14x26X32X43x536004x13x25x36X44X539502x13x23x34x43x52800Xi0,i1,2,5通过LINGO软件计算得:X10,X238,X3 254, X40,X5 642,Z318111.某厂生产甲、乙、丙三种产品，分别经过

11、 A, B, C三种设备加工。已知生产单 位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表2 10所示。表1 18产品生产工艺消耗系数甲乙丙设备能力A （小时）111100B （小时）1045600C （小时）226300单位产品利润（元）1064（1）建立线性规划模型，求该厂获利最大的生产计划。（2） 产品丙每件的利润增加到多大时才值得安排生产如产品丙每件的利润增加到6, 求最优生产计划。（3）产品甲的利润在多大范围内变化时，原最优计划保持不变（4）设备A的能力如为100+1Oq，确定保持原最优基不变的q的变化范围。（5）如合同规定该厂至少生产10件产品丙，试确定最优计划的变化

12、。解：（1）设X!,X2,X3分别表示甲、乙、丙产品的生产量，建立线性规划模型XiX2X310010为4x25X36002x12x26X3300XiXX标准化得X1X2X3X410010x14x25X3X56002x12x26X3X6300Xi,X2,X3,X4,X5,X60列出单纯形表1064000b010011110010006001045010600300226001150106400004003/51/211/100200/3106012/51/201/100150018006/5501/5115002-10106200/3015/65/31/6010100/3101/62/31/60

13、01000042010010/32/308/3故最优解为xi 100/3,x2 200/3, X3 0，又由于Xi,X2,X3取整数，故四舍五入可得最优解为 x1 33, x2 67,x3 0, Zmax 732 .(2)产品丙的利润C3变化的单纯形法迭代表如下:106000b6200/3015/65/31/6010100/3101/62/31/60010000420100C3 20/310/32/30202要使原最优计划保持不变，只要3 C3仝 0，即C3 6- 6.67 .故当产品丙每33件的利润增加到大于时，才值得安排生产。如产品丙每件的利润增加到6时，此时6，故原最优计划不变(3)由最

14、末单纯形表计算出解得611 孑1 0, 4102c10,511C10，3615，即当产品甲的利润C1在6,15范围内变化时,原最优计划保持不变(4)由最末单纯形表找出最优基的逆为 B 15/32/321/6 01/60，新的最优解为0 1解得4 q 5，故要保持原最优基不变的q的变化范围为4,5.(5)如合同规定该厂至少生产10件产品丙，则线性规划模型变成X1X2X310010%4x25X36002x12x26X3300X310X1,X2 , X30通过 LINGO软件计算得到：x132,x258,x310,Z708 .第2章对偶规划(复习思考题)1 对偶问题和对偶向量(即影子价值)的经济意义

15、是什么答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品 生产带来的，同时又是资源消耗带来的。对偶变量的值yi表示第i种资源的边际价值，称为影子价值。可以把对偶问题的解丫定义为每增加一个单位的资源引起的目标函数值的增量。2 什么是资源的影子价格它与相应的市场价格有什么区别答：若以产值为目标，则yi是增加单位资源i对产值的贡献，称为资源的影子价格(Shadow Price )。即有“影子价格=资源成本+影子利润”。因为它并不是资源的实际价 格，而是企业内部资源的配比价格，是由企业内部资源的配置状况来

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

17、 最优解的充分必要条件是Y*Xs 0,YsX*0 .(4)对偶问题的最优解对应于原问题最优单纯形表中， 初始基变量的检验数的负值。若 YS对应于原问题决策变量x的检验数，则 丫对应于原问题松弛变量xS的检验数。4 已知线性规划问题8x1 3x2 x3 2 （第一种资源） .6为x2 x3 8 （第二种资源）Xi, X2,X30（1）求出该问题产值最大的最优解和最优值。（2）求出该问题的对偶问题的最优解和最优值。（3） 给出两种资源的影子价格，并说明其经济含义；第一种资源限量由2变为4,最优解是否改变（4）代加工产品丁，每单位产品需消耗第一种资源2单位，消耗第二种资源3单位,应该如何定价解：（1

18、）标准化，并列出初始单纯形表41200b02831102/808611018/64120041/413/81/81/802013/265/41/43/412601/23/2-1/20228311006-22011125020由最末单纯性表可知，该问题的最优解为：X*（0,0,2,0,6）t，即X,0,x20,x32，最优值为Z 4 .(2) 由原问题的最末单纯形表可知，对偶问题的最优解和最优值为：yi 2胡20,w4 .(3) 两种资源的影子价格分别为2、0,表示对产值贡献的大小；第一种资源限量由 2变为4,最优解不会改变。(4) 代加工产品丁的价格不低于2 2 0 3 4 5某厂生产A, B

19、, C, D4种产品，有关资料如表26所示。表26资源消耗资源产品资源供应量(公斤)原料成本(元/公斤)ABCD甲2312800乙54341200丙34531000单位产品售价(元)21(1) 请构造使该厂获利润最大的线性规划模型，并用单纯形法求解该问题(不计加 工成本)。(2) 该厂若出租资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数学 模型，资源甲、乙、丙的影子价格是多少若工厂可在市场上买到原料丙，工厂是否应该 购进该原料以扩大生产(3) 原料丙可利用量在多大范围内变化，原最优生产方案中生产产品的品种不变(即 最优基不变)(4) 若产品B的价格下降了元，生产计划是否需要调整解：(

20、1)设X!,X2,X3,X4分别表示甲、乙、丙产品的生产量，建立线性规划模型2x13x2X32x48005x14x23X34x412003x14x25X33x41000Xi0,i123,4初始单纯形表1534000b08002312100800/30120054340101200/40100034530011000/41534000最末单纯形表1534000b01001/40-13/4011/4-1420020-2101-15100-3/4111/400-3/41-13/40-11/400-1/4-1解得最优解为：X* (0,100,0,200,100)t，最优值 Z 1300.(2) 原问题

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

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

23、济意义。（3）利用LINDO软件对价值系数进行敏感性分析，结果如下：Obj Coefficie nt Ran gesVariableCurre ntCoefAllowableIn creaseAllowable Decrease2008820240试问如果生产计划执行过程中，甲产品售价上升到13800元，或者乙产品售价降低60元，所制定的生产计划是否需要进行调整（4）利用LINDO软件对资源向量进行敏感性分析，结果如下：Right hand Side Ran gesResourceCurre nt RhsAllowableIn creaseAllowableDecrease材料42003004

24、50设备C3000360900设备D4500Infinity300试问非紧缺资源最多可以减少到多少，而紧缺资源最多可以增加到多少解：（1）建立的线性规划模型为60%50x2420030%40x2300060为 50x24500x-! ,x20将其标准化60%50x2 x3420030x140x2 x300060%50x2 x54500Xi0,i 1,2,5（2）甲生产20件，乙生产60件，材料和设备C充分利用，设备D剩余600单位。（3）甲上升到13800需要调整，乙下降60不用调整。（4）非紧缺资源设备D最多可以减少到300,而紧缺资源一材料最多可以增加到 300, 紧缺资源一设备C最多可以

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

26、一线性规划所得到的目标函数值Z不优于现有下界。（4）分枝过程。当有多个待求分枝时，应先选取目标函数值最优的分枝继续进行分枝。选取一个不符合整数条件的变量 Xi作为分枝变量，若Xi的值是b*，构造两个新的约 束条件：Xi b*或Xi b* 1，分别并入相应的数学模型中，构成两个子问题。对任一 个子问题，转步骤（1）.3 试用分枝定界法求如下线性规划：9x1 7x2567%20x270x.（ ,x20x1, x2取整数解：最优整数解为：捲4x 2,Z340 .4有4名职工，由于各人的能力不同，每个人做各项工作所用的时间不同，所花费时间如表37所示。表37 （单位：分钟）解：设Xj 1，任务1 由人

27、员完牛亠，tj为个人i对于任务j的时间耗费矩阵，则 0，任务i不由人贝j元成建立整数规划模型为：4xij1i14xij1j1Xij0或 1,i, j 1,2,3,4解得： x12 1,x21 1,x33 1,x44 1，其余均为零， Z 70，即任务 A 由乙元成，任 务B由甲完成，任务C由丙完成，任务D由丁完成。5某部门一周中每天需要不同数目的雇员：周一到周四每天至少需要 50 人，周五 至少需要 80 人，周六周日每天至少需要 90人，先规定应聘者需连续工作 5天，试确定 聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。解：设Xi表示在第i天应聘的雇员人数(i =

28、1,2,3,4,5,6,7)。数学模型为X1X4X5X6X750X1X2X5X6X750X1X2X3X6X750X1X2X3X4X750X1X2X3X4X580X2X3X4X5X690X3X4X5X6X790Xi0,i1,2,7Xi取整数,i1,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

29、小时，公司营业部门估计 A, B, C三种笔 记本电脑每台的利润分别是 1000元、 1440元、 2520元，而且公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标:第一目标：充分利用正常的生产能力，避免开工不足；第二目标：优先满足老客服的需求，A, B, C三种型号的电脑各为50台、50台、80 台，同时根据三种电脑三种电脑的纯利润分配不同的加权系数；第三目标：限制装配线加班时间，最好不超过 200小时；第四目标：满足各种型号电脑的销售目标，A，B，C三种型号分别为100台、120台、100台，再根据三种电脑的纯利润分配不同的加权系数；第五目标：装配线加班时间尽可能少。请列出

30、相应的目标规划模型，并用 LINGC软件求解。解：建立目标约束。（1）装配线正常生产设生产A，B，C型号的电脑为x1, x2, x3 （台），d1为装配线正常生产时间未利用数，d1为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为（2）销售目标优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子，A，B，C三种型号的电脑每小时的利润是 ，兰1°,缪，因此，老客户的销售目标约束为5812再考虑一般销售。类似上面的讨论，得到（3）加班限制首先是限制装配线加班时间，不允许超过 200小时，因此得到其次装配线的加班时间尽可能少，即写出目标规划的数学模型5x1 8

31、x212x3 d1d11700X1d2d250X2d3d350X3didi80X1d5d5100X2d6d6120X3d7d71005x18x212x3 d1d11900Xi0,i1,2di,di0,l1,2, ,8经过LINGC软件计算，得到xi 100, X2 55,X3 80，装配线生产时间为1900小时,满足装配线加班不超过200小时的要求。能够满足老客户的需求，但未能达到销售目标。 销售总利润为 100X 1000+55X 1440+80X 2520=380800 （元）。2已知3个工厂生产的产品供应给4个客户，各工厂生产量、用户需求量及从各工 厂到用户的单位产品的运输费用如表 4

32、3所示。由于总生产量小于总需求量，上级部门 经研究后，制定了调配方案的8个目标，并规定了重要性的次序。表43工厂产量一用户需求量及运费单价（单位：元）1234生产量152672354634523需求量（单位）200100450250第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于 80%第四目标：应尽量满足各用户的需求；第五目标：新方案的总运费不超过原运输问题（线性规划模型）的调度方案的 10%第六目标：因道路限制，工厂 2到用户4的路线应尽量避免运输任务；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少总运费。请列出相应的目标规划模型，并用 LINGCt件求解。解：假设三个