运筹学全书习题答案.doc

运筹学全书习题答案配套教材参考答案请勿盗版 尊重作者 第1章参考答案1.1 用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。（1）有唯一最优解，最优值。 (2)问题有无界解。 1.1（1） 1.1（2）(3)有唯一最优解，最优值。(4)有无穷多最优解，最优值。 1.1（3） 1.1（4）1.2 将下列线性规划问题化成标准型。(1) (2) 1.3 用单纯形法求解下述问题。（1)先将问题化为标准型： ，然后用单纯形法求解如下：Cj1064000CBxBbx1x2x3x4x5x6000x4 x5 x61006001501101141153100010001j10640000100x4 x1 x64060900103/52/53/51/21/25/2100-1/101/10-1/10001j02-10-106100x4 x1 x6200/3100/3500101005/61/625/3-2/3-1-1/61/60001j00-8/3-10/3-2/30问题有唯一最优解，最优值。(2)先将问题化为标准型，再用单纯形法求解。过程如下：Cj10600CBxBbx1x2x3x400x3 x4 152436521001j210002x3 x1 340141/310-1/21/6j01/30-1/312x2 x1 3/415/401101/4-1/12-1/85/24j00-1/12-7/24问题有唯一最优解，最优值。1.4 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题。 (1)用大M法求解，过程如下：先构造辅助问题：Cj1-11-M-MCBxBbx1x2x3x4x5-M-Mx4 x5 6614252-61001j1+5M-1+7M1-4M00-M-1x4 x2 18/56/5-3/54/50122/5-6/510/j9/5-3M/50-1/5+22M/50/1-1x3 x2 9/1124/11-3/227/110110/j39/2200/11x3 x1 9/724/7013/1411/710/j0-39/140/由上表可知，辅助问题有最优解，且人工变量，故原问题有唯一最优解，最优值。用两阶段法求解上述问题，过程如下：先构造辅助问题：Cj000-1-1CBxBbx1x2x3x4x5-1-1x4 x5 6614252-61001j57-400-10x4 x2 18/56/5-3/54/50122/5-6/510/j-3/5022/50/00x3 x2 9/1124/11-3/227/110110/j000/由上表可知，辅助问题有最优解，且人工变量，因此得到原问题的一个可行解，重新计算原问题的检验数，并用单纯形法继续求解。Cj1-1100x3 x2 9/1124/11-3/227/110110j39/220011x3 x1 9/724/7013/1411/710j0-39/140故原问题有唯一最优解，最优值。(2) 用大M法求解，过程如下：先构造辅助问题： Cj-2-3-100-M-MCBxBbx1x2x3x4x5x6x7-M-Mx6 x7 86134220-100-11001j-2+4M-3+6M-1+2M-M-M00-3-Mx2 x7 221/45/2101/2-1-1/41/20-1/01j-5/4+5M/21/2-M-3/4+M/2-M/0-3-2x2 x1 9/54/501103/5-2/5-3/101/51/10-2/5/j000-1/2-1/2/由上表可知，辅助问题有最优解，且人工变量，故原问题有最优解，最优值。又，可再进行一次迭代，以取代作为基变量，检验数不变，因此问题有无穷多最优解。Cj-2-3-100-M-MCBxBbx1x2x3x4x5x6x7-1-2x3 x1 32015/32/31-0-1/201/6-1/3/j000-1/2-1/2/用两阶段法求解上述问题，过程如下：先构造辅助问题：Cj00000-1-1CBxBbx1x2x3x4x5x6x7-1-1x6 x7 86134220-100-11001j462-1-1000-1x2 x7 221/45/2101/2-1-1/41/20-1/01j5/20-11/2-1/0-3-2x2 x1 9/54/501103/5-2/5-3/101/51/101/5/j00000/辅助问题有最优解，且人工变量，故原问题有基可行解。重新计算检验数：Cj00000CBxBbx1x2x3x4x5-3-2x2 x1 9/54/501103/5-2/5-3/101/51/101/5j000-1/2-1/2因检验数，故即为问题的最优解，最优值。又，可再进行一次迭代，以取代作为基变量，检验数不变，因此问题有无穷多最优解。 (3) 用大M法求解，过程如下：先构造辅助问题： Cj-4-100-M-MCBxBbx1x2x3x4x5x6-M-M0x5 x6 x4 3643411320-10001100010j-4+7M-1+4M-M000-4-M0x1 x6x4 1231001/35/35/30-10001/010j01/3+5M/3-M0/0-4-10x1 x2 x43/56/511000101/5-3/51001/j001/50/-4-10x1 x2 x32/59/51100010001-1/53/51/j001/5-1/5/由上表可知，辅助问题有最优解，且人工变量，故原问题有最优解，最优值。用两阶段法求解上述问题，过程如下：先构造辅助问题：Cj0000-1-1CBxBbx1x2x3x4x5x6-1-10x5 x6 x4 3643411320-10001100010j74-10000-10x1 x6x4 1231001/35/35/30-10001/010j05/3-10/0000x1 x2 x43/56/511000101/5-3/51001/j0000/辅助问题有最优解，且人工变量，故是原问题的一个基可行解。重新计算检验数：Cj-4-100CBxBbx1x2x3x4-4-10x1 x2 x43/56/511000101/5-3/51001j001/50-4-10x1 x2 x32/59/51100010001-1/53/51j000-1/5检验数，所以原问题有最优解，最优值。(4) 用大M法求解，过程如下：先构造辅助问题： Cj101512000-MCBxBbx1x2x3x4x5x6x700-Mx4 x5 x7 91555-52361115110001000-1001j10+2M15+M12+M00-M0100-Mx1 x5 x7 9/5247/51003/59-1/51/5163/51/51-2/501000-1001j06-M/510+3M/5-2-2M/50-M01012-Mx1 x3 x7 3/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001j027/8-43M/800-21/8-7M/16-5/8-3M/80-M0由上表可知，辅助问题有最优解，但人工变量，故原问题不可行。用两阶段法求解上述问题，过程如下：先构造辅助问题：Cj000000-1CBxBbx1x2x3x4x5x6x700-1x4 x5 x7 91555-52361115110001000-1001j21100-1000-1x1 x5 x7 9/5247/51003/59-1/51/5163/51/51-2/501000-1001j0-1/53/5-2/50-1000-1x1 x3 x7 3/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001j0-43/800-7/16-3/80-10检验数，所以辅助问题有最优解。但人工变量，故原问题不可行。1.5 设为每吨合金中矿物的含量（吨）。建立线性规划模型如下：1.6 当,时，目标函数最优值取得最小值。求解线性规划 得最优解，最优值。当,时，目标函数最优值取得最大值。求解线性规划 得最优解（不唯一），最优值。因此原问题目标函数最优值的下界为32/5，上界为21。1.7设工厂每天生产A、B、C三种型号的产品分别为、件。建立数学模型如下：1.8 设该公司投资于债券的金额为，建立该问题的数学模型如下：章末习题2.1 写出下列线性规划问题的对偶问题 2.2 判断下面说法是否正确，为什么？错误。如果线性规划的原问题存在可行解但有无界解，则其对偶问题不可行。错误。如果线性规划的对偶问题无可行解，原问题可能有无界解，也可能无可行解。错误。在互为对偶的一对原问题与对偶问题中，如原问题求最小值，则其可行解的目标函数值一定不小于其对偶问题（求最小值）可行解的目标函数值。正确。对偶问题可能有不同形式，但实质上都是同一问题。2.3 给出线性规划问题其对偶问题为证明：易知是对偶问题的一个可行解，其对应的目标函数值。又观察可知，是原问题的一个可行解，所以原问题可行，根据弱对偶性知，。2.4 证明：先写出对偶问题：显然，时，这与矛盾。因此对偶问题无可行解。由观察可知是原问题的一个可行解，故原问题有可行解而对偶问题无可行解，由弱对偶性的推论（3）知，原问题目标函数值无界。2.5 先写出对偶问题将最优解代入各约束条件中，分别有根据互补松弛性，得解得原问题的最优解为。2.6先写出对偶问题将最优解代入各约束条件中，分别有根据互补松弛性，得解得原问题的最优解为。2.7 （1）因为只有两个主约束，故基变量有两个，其他均为非基变量，即约束（2）的松弛变量为非基变量。因此约束条件（2）应为将上式，得。故（2）（3）根据互补松弛性，故又，两式联立解方程组得。2.8 用对偶单纯形法求解下列线性规划问题Cj-3-4-500CBxBbx1x2x3x4x500x4 x5 -8-10-1-2-2-2-3-11001j-3-4-5000-3x4 x1 -3501-11-5/21/210-1/2-1/2j0-1-7/20-3/2-4-3x2 x1 3201105/2-2-111/2-1j00-1-1-1因此问题的最优解为，。Cj-5-2-400CBxBbx1x2x3x4x500x4 x5 -4-10-3-6-1-3-2-51001j-5-2-400-50x1 x5 4/3-2101/3-12/3-1-1/3-201j0-1/3-2/3-5/30-5-2x1 x2 2/3210011/31-121/3-1j00-1/3-1-1/3因此问题的最优解为，。2.9 先用单纯形法求解该线性规划问题，得最优单纯形表如下：Cj-551300CBxBbx1x2x3x4x550x2 x5 2010-116103-21-401j00-2-50因此问题的最优解为，。由20变为45，因此最优解发生变化。用对偶单纯形法求解，得Cj-551300CBxBbx1x2x3x4x5013x4 x3 189-23/56/5-1/52/50110-3/101/10j-103/5-1/500-13/10新的最优解为，。由90变为70，因此最优解发生变化。用对偶单纯形法求解，得Cj-551300CBxBbx1x2x3x4x5513x2 x3 5523-81001-523/2-1/2j-1600-1-1新的最优解为，。由13变为8，仅的检验数发生变化：，最优解不变。由5变为6，因是基变量，所有检验数都发生变化，重新求检验数：Cj-561300CBxBbx1x2x3x4x560x2 x5 2010-116103-21-401j10-5-606-5x2 x1 165/85/8011023/8-1/83/4-1/41/161/16j00-2-50新的最优解为，。增加变量（），故最优解不变，仍为。增加一个约束条件，将原最优解代入该约束条件中：，所以原最优解不再是可行解。Cj-5513000CBxBbx1x2x3x4x5x6 500x2 x5 x6 201050-11621033-251-40010001j00-2-500500x2 x5 x6 2010-10-11651003-2-41-4-3010001j00-2-5005013x2 x5 x3 25/2155/211/427/2-5/4100001-5/4-5/23/40103/4-1/2-1/4j-5/200-7/20-1/2新的最优解为，。的系数列向量由变为，故原最优解不变, 。章末习题3.1总运费最省的调运方案为： 销售地生产地B1B2B3生产量（吨）A1314A277A3202需求量（吨）23813最低总运费为57。3.2该问题的最优调运方案为：销售地生产地B1B2B3B4生产量（吨）A14037A2628A333需求量（吨）663318总运费为89。3.3最优调运方案为：销售地生产地B1B2B3B4生产量（吨）A133A2325A33047需求量（吨）632415总运费为40。3.4最优调运方案如下表，总运费为204。销售地生产地B1B2B3B4生产量（吨）A152310A2538A355需求量（吨）5783233.5 总的运输费用最低的调运方案如下表，其中B1城市少供应30万吨，B3城市少供应40万吨。城市企业B1B2B3生产量（万吨）A1150250400A2140310450需求量（万吨）320250350总运费为14650。3.6总运输费用最低的产品调运方案如下表所示，最低运输费用为5900。A3A4A5A6A7A8产量A1700100800A2100400500A36004003001300A411002001300需求量（吨）130013004002003004003900章末习题4.1 设、分别表示A、B、C三种规格的电视机的产量。4.2设、分别表示A、B两种电视机的产量。 4.3设、分别表示甲、乙两种仪器的产量。 4.4 用图解法求解下列目标规划问题：满意解为，。 连接点与点的线段AB上所有的点都是问题的满意解，。其中A点对应的偏差变量值为；B点对应的偏差变量值为。4.5 用单纯形法求解下列目标规划：问题的满意解为，。0000002111/2-1/201-111/2-1/238-10-331-111103-31(2)问题的满意解为，。00000551-1130-12-2-11045111-111-2224.6满意解为，。章末习题5.1 60单位长的标准玻璃纸裁为45、20、15三种规格，有五种裁剪方式：方式452015废料12345100000321010124005100设（）表示采用第种方式裁剪的标准玻璃纸的数量。建立模型如下：5.2 设（）表示三种产品的产量。5.3 设（）表示三种金属容器A、B、C的产量。5.4 设5.5先用单纯形法求得松弛问题的最优解，结果如下表所示。1100b15/3101/3-1/315/20101/200-1/3-1/6以所在行为源行的割平面为，引入松弛变量加入上表中，求解得11000b1102211000101/2-1/41/2001-1/23/4-3/200-1/40-1/4因此，原整数规划问题的最优解为，其最优值为。（2）先用单纯形法求得松弛问题的最优解，结果如下表所示。1100b49/5102/5-1/5523/1001-1/103/1000-11/10-7/10以所在行为源行的割平面为，引入松弛变量加入上表中，求解得11000b4502211000101/2-1/41/2001-1/43/8-5/400-3/40-7/8因此，原整数规划问题的最优解为，其最优值为。5.6 先用单纯形法原整数规划问题的松弛问题，最优解为不是整数。将和分别加入松弛问题中形成两个子问题，分别求解得和，前者是整数解，故其最优值构成原整数规划问题最优值的下界。而后者最优值。但因目标函数中价格系数均为整数，故当、均取整数时，目标函数值也应为整数。而不超过26/5的整数中最大的就是5，因此原整数规划问题的最优解为，最优值。（对（LP2）继续分支可得到另一个最优解） 先用单纯形法原整数规划问题的松弛问题，最优解为不是整数。将和分别加入松弛问题中形成两个子问题，分别求解得和，均不是整数解，前者最优值，后者最优值，故取（LP2）进一步分支：和。这一分支的最优解为，仍不是整数解；而这一分支不可行，因此进行剪支。继续对（LP21）进行分支：和，分别得到最优解和，最优值分别为和。由于为整数解，其函数值，因此（LP1）的进一步分支不可能得到比它更优的整数解，对（LP1）进行剪支。而虽大于14，但其中的整数解的目标函数值也不可能超过14，因此不必再进一步分支。至此，松弛问题的全部子问题均已考察完毕，保留下来的整数解即为原整数规划问题的最优解，最优值。5.7 ，。 ，。5.8 虚设一人，成本矩阵为，用匈牙利算法求得，即安排甲做B，乙做C和D，丙做E，丁做A，总花费131。5.9 设，则原问题变为如下标准形： 由目标函数知，目标函数值由小到大依次为-10、-8、-6、-5、-4、-3、-2先令所有变量均为0，代入两个约束条件中，均不成立。令，其余变量仍为0，约束条件（1）成立，但（2）不成立。令，其余变量仍为0，约束条件（1）、（2）都不成立。令，其余变量仍为0，约束条件（1）、（2）都不成立。令，其余变量为0，约束条件（1）、（2）均成立。故原问题最优解为，最优值。章末习题6.1 s至t的最长路线为sacdt或sacet或sbcdt或sbcet。6.2 A、B、C、D四个企业分配到的资金分别为0、20、40、40（万元），总盈利最大为85。6.3 第一种资源3单位全都分配给第三个部门，第二种资源1单位分配给第一个部门，2单位分配给第二个部门。这样的分配方案获得的总利润最大，总利润为16。 6.4 既满足交货任务（不允许缺货）又使总费用最少的生产计划为：1月生产400件，3月生产400件，4月生产300件，5月生产300件，2月和6月不生产，最少总费用为161000元。6.5 满足需求量又使热销季节总费用最小的订货方案为10月订货40双，11月订货50双，1月订货40双，2月订货50双，12月和3月不订货，总费用为610。6.6 应分别装载三种货物2，2，0或3，2，1件，才能使所运货物总价值最大，总价值为480元。6.7 装载货物的总价值最大为20，最优方案有三种：四种货物的装载量分别为1，3，1，0；或2，1，2，0；或0，5，0，0。6.8 五年内所有机器都按低负荷投入生产，总收益最大。各年投入的机器数量分别为1000台、400台、160台、64台、25台。6.9 初始役龄为7（T=7）的设备的10年最佳更新策略有三种：第1年、第5年和第8年更新；第1年、第5年和第7年更新或第1年、第3年和第7年更新，10年总收益最大为70万元。初始役龄T=6的设备的9年最优更新策略有四种：第1年和第6年更新；第1年和第5年更新；第1年、第3年和第6年更新；第1年、第3年和第7年更新，9年最大总收益为64万元。6.10应安排1个E1， 1个E2，3个E3备用，总费用8000元，设备的可靠性最高可增加0.042。章末习题7.1 图（a）中，、之间有d、e两条箭线连接。图（b）中，有、两个终点节点。网络图中只能有一个起始节点和一个终点节点。图（c）中，构成一条回路。图（a）、图（b）改正如下：7.2 根据表7-8，表7-9所示的工序明细表，绘制网络图。 7.3 各事项的最早与最迟时间见下图：7.4 试画出表7-10、表7-11的网络图，并为事项编号。7.5网络图及各节点时间参数如下图，关键路线为。（2）各工序的最早开工、最早完工、最迟开工、最迟完工时间及总时差、关键工序如下表：工序工时(周)ESLSEFLFST关键工序A(1-2)301341B(1-3)400440是C(2-4)434781D(7-10)3142017236E(3-9)44138179F(6-9)5121217170是G(4-5)2789101H(5-6)2101012120是I(8-9)2141516171K(9-10)6171723230是L(4-7)78814151M(3-5)64410100是（3）若要求工程完工时间缩短2天，应缩短关键工序。但因A、C、L、I、K组成的路线所需工时为22周，仅比关键路线少1周，因此应缩短工序K的时间至少一周，再缩短关键工序（B、M、H、F、K）中任意一道工序一周。7.6 各节点时间参数见下图：关键路线为：。各工序的时间参数及关键工序如下表所示：工序工时(周)ESLSEFLFSTFT关键工序(1-2)1000101000是(1-3)1206121863(1-4)150171532170(2-3)51013151830(2-5)181010282800是(3-5)101518252833(3-6)111518262930(3-7)1515273042120(4-7)1015322542175(5-8)202828484800是(6-8)142634404888(6-9)252629515433(7-9)0305430542424(7-10)19304249611212(8-9)64848545400是(8-11)15487163862323(9-10)75454616100是(9-11)18546872861414(10-11)256161868600是7.7各事项的最早时间和最迟时间如图所示：各工序的最早开始、最早结束、最迟开工及最迟完工时间、总时差和自由时差如下表所示：工序工时(周)ESLSEFLFSTFT关键工序(1-2)30