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

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

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

3、“三”型约 束的左边取值大于右边规划值，出现剩余量。4. 试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相 互关系。答：可行解：满足约束条件AX b, X 0的解，称为可行解。基 可行解：满足非负性约束的基解，称为基可行解 可行基：对应于基可行解的基，称为可行基。最优解：使目标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。它们的相互关系如右图所示:5. 用表格单纯形法求解如下线性规划8xi 3x2 X3 2s. 1 6X1卫 X3 8XI, X2 ,0解：标准化maxz 4X1X22x38x13x2X3 X42s. t 6x1X2X3X58XI, X2 ,

4、 X3, X4 , X5 0列出单纯形表41200b02831102/808611018/64120041/413/81/81/80(1/4)/(1/8)(13/2)/(1/4013/26-5/41/4-3/410-1/23/2-1/20228311006-2-20-11-12-50-20故最优解为X* (0,0, 2, 0,6) ,即XI 0, X2 0, X3 2 ,此时最优值为Z (X*)4.6.表115中给出了求极大化问题的单纯形表，问表中ab a2, cb c2, d为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以X】代替基

5、变量X5 : （4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。表1- 15某极大化问题的单纯形表000b0d410002-1-501003-3001000解：) dO , ciO, c2 0；(2(Cl, C2中至少有一个)d 0, ci0, C20为零)d3(Qci n ”da4a2(4 Xi,通过LINGO软件计算得:10, X220, X30, xf 12, x卢4410. 某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成 型、打磨、上漆几道重要工序。每种家具的每道工序所用的时间、每道工序的可用时 间、每种家具的利润由表117给岀。问工厂应如何安排生产，使总利润最

6、大？表1 17家具生产工艺耗时和利润表生产工序所需时间（小时）每道工序可用 时间（小时）12345成型346233600打磨435643950上漆233432800利润（百元）2. 734.52. 53解：设xi表示第i种规格的家具的生产量（i =1,2, -,5 ）,则3xi4X26x32X4吒3600St鬥3X25X36X44X539502xi3X23X34X43x-02800Xio, i1,2,5通过LINGO软件xi 0,X238, X3254, X4 0, X5 642, Z 318111. 某厂生产甲、乙、丙三种产品，分别经过A, B, C三种设备加工。 已知生产单位产品所需的设备

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

8、、丙产品的生产量，建立线性规划模型Xl X2 X3 100lOxi 4x2 5x3 600 s. t 2xi 2x2 6x3 300Xl, X2, X3 0标准化得Xl X2 X3 X4 100lOxi 4x2 5x3 xs 60012 9 5列出单纯形表S. t1064000b010011110010006001045010600300226001150106400004003/51/211/100200/3106012/51/201/100150018006/550-1/5115002-10-106200/3015/65/31/6010100/3101/6-2/31/600100004-2

9、0100-10/3-2/302X1 2X2 6x3 X6 300 Xl, X2, X3, X4, X5, X6 08/3故最优解为Xi 100 / 3, x 2 200/3, xs 0 ,又由于xi , x 2,刘取整数，故四舍五入可得最优解为 XI 33, X2 67, X3 0, Zmax 732 2)产品丙的利润C3变化的单纯形法迭代表如下:106000b6200/3015/65/31/6010100/3101/6-2/31/600100004-201 2耍使原最优讣划10 0 保持不变，C3 20/3 只要3 C3 ”-10/301即 C3-2/366670i) 口口丙件的利润增加到大

10、于6. 67时，才值得安排生产。如产品丙每件的利润增加到63)由最末单纯形表计算出11 :eCl 0, 4时，此时66. 67 ,故原最优计划不变10 2Ci 0,5 1 :Ci0,解得615 ,即当产品甲的利润“在6,15范围内糜最簡计划保持不变1/6 01/6 0 ,新的最优解 为5/34)由最末单纯形表找出最优基的逆为B 2/3201解得4 q 5 ,故要保持原最优基不变的q的变化范围为4,5(5)如合同规定该厂至少生产10件产品丙，则线性规划模型变成Xl X2 X3 100lOxi 4x2 5x3 600s. t. 2xi 2x2 6x3 300 X3 10Xi, X2 , X3 通过

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

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

13、2）对偶性定理：若原问题有最优解，那么对偶问题也有最优解，而且两 者的目标函数值相等。（3）互补松弛性：原问题和对偶问题的松弛变量为乂$和丫$,它们的可行 解X,Y为 最优解的充分必要条件是Y-Xs 0, YsX 0.4）对偶问题的最优解对应于原问题最优单纯形表中，初始基变量的检验数的负值。若Ys对应于原问题决策变量x的检验数，则Y对应于原问题松弛变量xs的 检验数。4. 已知线性规划问题8xi 3x2 X3 2 (第一种资源)s. 6xi x2 x3 8 “ 賊血XI, X2 , X3 0(1) 求出该问题产值最大的最优解和最优值。(2) 求出该问题的对偶问题的最优解和最优值。(3) 给岀两

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

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

16、题的数学模型，资源甲、乙、丙的影子价格是多少？若工厂可在市场上买到原 料丙，工厂是否应 该购进该原料以扩大生产？（3）原料丙可利用量在多大范围内变化，原最优生产方案中生产产品的 品种不变（即最优基不变）？（4）若产品B的价格下降了 0.5元，生产计划是否需要调整?解：（1）设XI, X2 , X3, X4分别表示甲、乙、丙产品的生产量，建立线性 规划模型2x13X2x32X48005xi4X23X34X41203xi4X25X33X4100X -1o, i1,2,初始单纯形表1534000b08002312100800/30120054340101200/40100034530011000/4

17、1534000最末单纯形表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,最优值Z 1300.(2) 原问题的对偶问题的数学模型为2yi5y2 3y313yi4y24ys5s. t yi3y25ys12yi4y23ys4yi, ys, ys 0解得影子价格分别为2、1.25、2.5。对比市场价格和影子价格，当市场 价低于影子价格时购进（3）原料丙可利用量在900, 1100范围内变化，原最优生产方案中生产产 品的品种 不变（即

18、最优基不变）。（4）若产品B的价格下降了 0.5元，生产计划不需要调整。6.某企业生产甲、乙两种产品，产品生产的工艺路线如图2- 1所示，试 统计单位产品的设备工时消耗，填入表2-7o又已知材料、设备C和设备D等资源的 单位成本和拥有量如表2 7所示。表2一 7资源消耗与资源成本表产品资源资源消耗资源成本资源拥有量甲乙元/单位资源材料（公斤）60502004200设备c （小时）3040103000设备D （小时）6050204500据市场分析，甲、乙产品销售价格分别为13700元和11640元，试确定获 利最大的产品生产计划。（1）设产品甲的计划生产量为X!,产品乙的计划生产量为X2,试建立

19、其 线性规划的数学模型；若将材料约束加上松弛变量X3,设备C约束加上松弛 变量X4 ,设备D约束加上松弛变量X5，试化成标准型。（2）利用LINDO软件求得：最优目标函数值为18400,变量的最优取值分 别为XI 20, X2 60, X3 0, X4 0, X5 300 ,则产品的最优生产计划方案是什么？并解释X3 0, X4 0, xs 300的经济意义。（3）利用LINDO软件对价值系数进行敏感性分析，结果如下：Obj Coefficient RangesVariableCurrentCoefAllowableIncreaseAllowableDecrease2008820规划问题没有可

20、行解，停止计算，这时原整数规划也没有可行解（2）定界过程。对于极大化的整数规划问题，当前所有未分枝子问题中 最大的目标函数值为整数规划问题上界；在满足整数约束的子问题的解中， 最大的目标函数值为整数规划问题的下界。当上下界相同时，则已得最优 解；否则，转入剪枝过程。（3）剪枝过程。在下述情况下剪除这些分枝：若某一子问题相应的线 性规划问题无可行解；在分枝过程中，求解某一线性规划所得到的目标函 数值Z不优于现有下界。（4）分枝过程。当有多个待求分枝时，应先选取目标函数值最优的分枝 继续进行分枝。选取一个不符合整数条件的变量Xi作为分枝变量，若Xi的 值是br,构造两个新的约束条件：Xi bi 或

21、Xi bi 1,分别并入相应的数 学模型中，构成两个子问题。对任个子问题，转步骤（1）.3. 试用分枝定界法求如下线性规划：9xi 7x2 56 xi, X2 0 xi, X2 取整数7xi 20x2 70s. t.解：最优整数解为：XI 4, X2 2, Z 340.4. 有4名职工，由于各人的能力不同，每个人做各项工作所用的时间不同，所花费时间如表3 7所示。表3 7 (单位:问指派哪个人去完成哪项工作，可使总的消耗解：设X(%由人员，完成,切为个人i对于任务j的时间耗费矩阵，则 0 ,任务i不由人员j完成建立整数规划模型为：4Xij1il4Xij 1jlXij 0 或 1, i , j

22、1, 2, 3, 4解得： X12 1, X21 1, X33 1, X44 1 , 其余均为零，z 70 ,即任务A由乙完成， 任务B由甲完成，任务C由丙完成，任务D由丁完成。5. 某部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50 人，周五至少需要80人，周六周日每天至少需要90人，先规定应聘者需连续工作5 天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下 聘用总人数最少。解：设&表示在第i天应聘的雇员人数(i =1,2, 3,4, 5, 6,7 )。数学模型S1x4s5s6750S1s2s5s6750S1x2x3s6750S1s2x3s4750ts2x35

23、4s580X2X3X4X5X690X3X4XoX6X790Xi0,i1,2 ,Xi取整1,2,7s.解得：Xi 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元，而且公司预测这个月生产的笔 记本电脑能够全部

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

25、i为装配线正常生产 时间未利用数，dl为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标 约束为(2) 销售目标优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子，A, B, C三种 型号的电脑每小时的利润是”“，”，因此，老客户的销售目 标约束为5 8 12再考虑一般销售。类似上面的讨论，得到(3) 加班限制首先是限制装配线加班时间，不允许超过200小时，因此得到其次装配线的加班时间尽可能少，即写出目标规划的数学模型5xi8x212x3 di di1700xid2d250s2d3d350s3d4d480X1d 0d 01004-s2d6d6120s3d7d71005

26、x18x212x3 di 九1900-i 0, i 1,2di , di 0, 1 1, 2, 8经过LINGO软件计算，得到Xi 100, X2 55, xs 80 ,装配线生产时间为1900小 满足藝配线加班不超过200小时的要求。能够满足老客户的需求，但未能达 到销售目标。销售总利润为100X 1000+55X 1440+80X2520=380800 （元）。2.已知3个工厂生产的产品供应给4个客户，各工厂生产量、用户需求 量及从各工厂到用户的单位产品的运输费用如表43所示。由于总生产量 小于总需求量，上级部门经研究后，制定了调配方案的8个目标，并规定了 重要性的次序。表4 3工厂产量一

27、用户需求量及运费单价（单位：元）工厂用户1234生产量152672354634523需求量（单 位）200100450250第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应 用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用 户的满足率不低于80%；第四目标：应尽量满足各用户的需求；第五目 标：新方案的总运费不超过原运输问题（线性规划模型）的调度方案的 10%；第六目标：因道路限制，工厂2到用户4的路线应尽量避免运输任务； 第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求 减少总运费。请列出相应的目标规划模型，并用LINGO软件求解。解：假设三个工厂 对应的生产量分别为300 , 200, 400.（1）求解原运输问题由于总生产量小于总需求量，虚设工厂4,生产量 为100个单位，到各个用户间的运费单价为0o用LINGO软件求解，得到总 运费是2950元，运输方案如下表所示。经过LINGO软件计算，得到Xi 100, x2 55, xs 80 ,装配线生产时间为1900小工厂1234生产量用户1100200300220020032501504004100100需求量(单位)20010045025