【问题】管理运筹学课后答案

1、文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持【关键字】问题2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。(1)解：(1)令，则得到标准型为(其中 M为一个任意大的正数)初始单纯形表如表 2-1所示：表2-1cj-224-400-M-MCBXBbx2x4x5x6x70x419322-2100019/3-MX6144 34-40-11014/4-Mx726524-4000126/5-z-2+9M2+5M4+8M-4-8M0-M002.3 用单纯形法求解下列线性规划问题。(1) (2)解：(1)最优解为。(2)最优解为。2.4 分别用大M法和两阶段法求解下列线性规划问题。

2、(1) (2)解：(1)最优解为。(2)最优解为。2.6已知线性规划问题其对偶问题最优解为。试用对偶理论找出原问题最优解。解：先写出它的对偶问题将代入约束条件可知，第 2、3、4个约束为严格不等式，因此，由互补松弛性得。又因 为，所以原问题的两个约束条件应取等式，因此有故原问题最优解为。2.12现有线性规划问题先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？(1)约束条件的右端项系数由20变为30;(2)约束条件的右端项系数由90变为70;(3)目标函数中的系数由13变为8;(4)的系数列向量由变为；(5)将原约束条件改变为；(6)增加一个约束条件。解：在上述LP问题的

3、第、个约束条件中分别加入松弛变量x4,x5得列出此问题的初始单纯形表并进行迭代运算，过程如表2-11所示。1文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持由表2-11中的计算结果可知，LP问题的最优解 X*=(0,20,0,0,10)T , z*=5*20=100 。(1)约束条件的右端项系数由20变为30,则有列出单纯形表，并利用对偶单纯形法求解，过程如表2-12所示。表 2-11-551300aCbXbbX1X2X3X4X50X420-113 1020/30X59012410019cj-zj-55130013X320/3-1/31/3 11

4、/30200X570/346/32/30-10/3135cj-zj-2/32/30-13/305X220-113100X510160-2-41cj-zj00-2-50表 2-12cj-551300CbXbbX1X2X3X4X55X230-113100X5-30160-2 -41cj-zj00-2-505X2-152310-5 3/213X315-8012-1/2cj-zj-1600-1-10X43-23/5-1/501-3/1013X396/52/5101/10cj-zj-103/5-1/500-13/10由表2-12中计算结果可知，LP问题的最优解变为。(2)约束条件的右端常数由90变为70

5、,则有列出单纯形表，并利用对偶单纯形法求解，结果如表2-13所示。表 2-13cj-551300CbXbbX1X2X3X4X55X220-113100X5-10160-2 1-41ci-zj00-2-505Xr 5231r 0-53/22文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持13x35-8012-1/2G-zj-1600-1-1由表2-13结果知，LP问题的最优解变为。(3)目标函数中x3的系数由13变为8,由于x3是非基变量，其检验数变为所以LP问题的最优解不变。(4) x1的系数列向量由(-1,12)T变为(0,5) T,则x1在最

6、终单纯形表中的系数列向量变 为从而x1在最终单纯形表中的检验数变为所以LP问题的最优解保持不变。(5)将原约束条件改变为10x1+5x2+10x3< 100,则x1在最终单纯形表中系数列向量变为，检验数x2在最终单纯形表中系数列向量变为，检验数。又因的各分量均大于 0,故LP问题的最优解不变。(6)增加一个约束条件 2x1+3x2+5x3 W50则在此约束条件中加入松弛变量x6,并将此约束加入到最终单纯形表中，继续迭代，过程如表2-14所示。由表2-14中计算结果可知，LP问题的最优解变为，。表 2-14cj-5513000CbXbbx1x2x3x4x5x65x220-1131000x5

7、10160-2-4100x6502350015x220-1131000x510160-2-4100x6-1050-4 -301cj - zj00-2-5005x225/211/410-5/403/40x51527/200-5/21-1/213x35/2-5/4013/40-1/4cj - zj-5/200-7/20-1/23.1分别用分支定界法和割平面法求解下列整数规划模型。(1) min z 4x1 3x2(2) maxz x1 x2解：(1)求解得到取优解xi 2,x2 1,z11。(计算步骤略)(2)仅写出利用割平面法求解的过程。在原IP问题约束条件中加入松弛变量x3,x4,化为标准型，

8、可得不考虑整数条件，用单纯形法求解原问题的松弛问题，计算结果如表 3-1所示。表3-111003文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持CBXbbxiX2X3X40X36211060X4204J 5 014Cj-Zj11000X326/5 01-1/55/31X244/5101/55Cj-Zj1/500-1/51xl5/3105/6-1/61X28/301-2/31/3Cj-Zj00-1/6-1/30因此，松弛问题的最优解为Xi=5/3,X2=8/3,X3=0,X4=0;z=13/3。由于X2不为整数，因此在最终单纯形表中根据X2所在的行

9、作割平面即将它作为约束条件，引入松弛变量后加到最终单纯形表中，并采用对偶单纯形法继续迭代, 计算过程如表3-2所示。表3-2cj11000CBXbbxix2x3x4X51xi5/3105/6-1/601X28/301-2/31/300X5-200-1-1 1Cj-Zj00-1/6-1/3001xi21010-1/61X2201-101/30X420011-1Cj-Zj0000-1/6由于Xi,X2的值均为整数，所以得到原问题的最优解为x (2,2)T,z43.4某厂新购4台不同类型机器， 可以把它们安装在 4个不同的地点。由于对特定的机 器而言，某些地方可能安装起来特别方便且合适，所以不同的机

10、器安装在不同的地点费用是不同的。估计白费用见表3-3,试制定使得总安装费用最小的安装方案。表3-3(费用单位：元)7''.地点机器1234机器总数1109871234561321121443561需要量11114文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持解设 1,如果机器i安装在地点牛.又xj 0,否则5 机器i安装在地点j所需的费用。建立该问题的数学模型如下： 目标函数： 约束条件：4（1）每一部机器只分配在一个地点，即j1xj 1 i 1,2,3, 44（2）每一个地点只能有一台机器，即i 1xj 1 j 1,2,3,4

11、（3） % 。或1工作指派问题可以看成是一类特殊的运输问题，每个供应点的供应量为1,每个需求点的需求量也为1。因此，本题可以采用表上作业法进行计算，也可以利用匈牙利法进行计算。计算得到的最佳安装方案为：机器1安装在地点4、机器2安装在地点1、机器3安装在地点3、机器4安装在地点2,最小总安装费为14元。3.9设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用的效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如表 3-17所示。试确定使总运费最少的化肥调拨方案。表 3-17需求产地IIIIIIIV产量（万吨）A1613221750B141319156

12、0C192023-50最低需求（万吨）3070010最高需求（万吨）507030不限解：这是一个产销不平衡的运输问题，总产量为160万t,四个地区的最低需求为110万t,最高需求为无限。根据现有产量，第 IV个地区每年最多能分配到60万t,这样最高需求就为210万t,大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D,其年产量为50万t。由于各地区的需求量包含两部分，如地区 I,其中30万t是最低需求， 故不能由假想化肥厂 D供给，令相应的单位运价为M （任意大的正数）；而另一部分20万t满足或不满足均可以，因此可以由假想化肥厂 D供给，按前述，可令相应的单位运价为 0。 对凡是需求

13、分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表（表3-18）和单位运价表（表 3-19）。并根据表上作业法，可以求得这个问题的最优 解，如表3-20所示。表 3-18。一.销地产心、II'IIIIIIVIV'产量A50B60C50D505文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持销量302070301050表 3-19销地产地II'IIIIIIVIV'A161613221717B141413191515C19192023MMDM0M0M0表 3-20销地产地II'IIII

14、IIVIV'产量A5050B20103060C3020050D302050销量3020703010504.2 利用单纯形法求解下列目标规划模型。(1) min z P(di di ) P2d3解：(1)本题的三个约束条件都是目标约束，有三个负偏差变量，因此选择负偏差变量为初始基变量。并计算出各非基变量的检验数，得到初始的单纯形表如表4-1所示。非基变量X1,X2的检验数分别为 01= -Pi-2P2和 斯-2Pi -2P2,它们的最高优先级的系数都 小于零，但 中P1的系数等于-2,其绝对值等于 2,大于d中P1的系数的绝对值1,因此 X2应当进基。用最小比值法确定d1应当出基。换基后

15、，通过计算求得新的基本可行解，如表4-2所示。表4-1cj00P100P1P20CbXbbX1X2P15012 1-100002504021001-10040P2802200001-140P1-1-2010100伪P2-2-2000001表4-2Cj00P100P1P20CbXbbX1X20X2251/211/2-1/20000500153/2 0-1/21/21-10010P23010-11001-130jP1001001006文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持P2-101-10001尽管xi与d1具有相同的负检验数，但根据前面讨

16、论的原则，由于 xi是决策变量，选择xi进基，用最小比值法确定 d2出基，换基后，计算所得新的基本可行解如表4-3所示。表4-3cj00P100P1P20CbXbbx1x20x220012/3-2/3-1/31/300一0x11010-1/31/3 2/3-2/30030P22000-2/32/3-2/32/31-130P100100100jP2002/3-2/32/3-2/301首项系数小于零的检验数只有d1的为2/3P2,因此d1应当进基，由于存在两个最小比值，取下标最小的变量出基，因此xi出基，换基后，再计算新的基本可行解，如表 4-4所示。表4-4ci00P100P1P20CbXbbx

17、1x20x24021001-10003030-112-200P20-2000-221-1P100100100dP220002-201此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：xi=0,x2=40, d1 =30,其他偏差变量都等于零。4.3 某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时 消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有 生产能力；（3

18、）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。解：该问题的数学模型如下：5.2 计算从A至ij B、C和D的最短路。已知各段路线的长度如图5-1所示。图5-1解：求从A到B、C和D的最短路等价于求从 B、C和D到A的最短路。设阶段变量k=1,2,3,4,依次表示4个阶段选路得过程，第 1阶段从B、C或D出发到 B3、C3或D3,第2阶段从B3、C3或D3出发到B2、C2或D2,第3阶段从B2、C2或D2出发 到B1、C1或D1,第4阶段从B1、C1或D1出发到A;状态变量Sk表示k阶段初可能处的位置；7文档收集于互联网，如有不妥请联系删除.文档来源

19、为：从网络收集整理.word版本可编辑.欢迎下载支持决策变量Xk表示k阶段可能选择的路线；阶段指标Vk表示k阶段与所选择的路线相应的路长；4指标函数vk4vi表示k至第4阶段的总路长；i k递推公式 fk minVk fkJ, k 4,3,2,11 0计算过程如表5-1所示。由表中计算结果可以看出： 从B到A的最短路线为B一C 3一C 2一B 1一A ,最距离为16; 从C到A的最短路线为 CH>C 3一C 2一B 1 一A或Cf D 3'C 2一B 1 一A ,最短距离为 21;从D 到A的最短路线为DH*D 3'C 2一 B 1 一A ,最短距离为20。表5-1kSk

20、XkVkVk4=Vk+fk+1fk*Xk4BiA33+03ACiA88+08AD1A77+07A3B2Bi44+37BiCi22+8C2Bi33+36B1Ci88+8Di77+7D2Ci44+812CiDi66+72B3B21010+717B2C21313+6C3B21212+711C2C255+6D266+12D3C277+613C2D288+121BB399+1716C3C355+11CB31010+1721C3、D3C31010+11D388+13DC31515+1120D3D377+135.3某工业部门根据国家计划的安排，拟将某种高效率的设备5台，分配给所属的甲、乙、丙三个工厂，各工厂

21、若获得这种设备之后，可以为国家提供的盈利如表5-2所示。表5-28文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持设备数工厂f、012345甲03791213乙0510111111丙046111212问：这5台设备如何分配给各工厂，才能使国家得到的盈利最大？解：将问题按工厂分为 3个阶段，甲、乙、丙 3个工厂分别编号为1、2、3;设sk表示分配给第k个工厂至第n个工厂的设备台数；xk表示分配给第k个工厂的设备台数；则Sk+i=sk- xk为分配给第k+1个工厂至第n个工厂的设备台数；Pk（Xk）表示xk台设备分配给第k个工厂所得得盈利值；fk（s

22、k）表示sk台设备分配给第 k个工厂至第n个工厂时所得到得最大赢利值。由以上的假设可写出逆推关系式为下面采用逆推法进行计算。第3阶段：设S3台设备（S3=0,1,2,3,4,5）全部分配给工厂丙时，则最大赢利值为 其中 X3=S3=0,1,2,3,4,5。因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值。其数值计算如表5-3所示。表5-3表中x3表示使f3（S3）为最大值时的最优决策。第2阶段：设把S2台设备（S2=0,1,2,3,4,5）分配给工厂乙和工厂丙时，则对每个S2值有一种最优分配方案，使最大盈利值为 其中 x2=0,1,2,3,4,5。因为给乙

23、工厂 x2台，其盈利为P2（x2）,余下的S2-x2台就给丙工厂，则它的盈利最大值为f3（S2-x2）。现要选择x2的值使P2（x2） f3（x2）取最大值。其数值计算如表54所示。表5-4第1阶段：设把与台（这里只有S1=5的情况）设备分配给甲乙丙 3个工厂，则最大盈利值为 其中 x1=0,1,2,3,4,5o因为给甲工厂x1台，其盈利为P1（x1）,剩下的5-x1台就分给一合丙两个工厂，则它的盈 利最大值为f2（5-x1）。现要选择x1值使P（x。 f2（5 X）取最大值，它就是所求的总盈利最大 值，其数值1t算如表 5-5所示。表5-5然后按计算表格的顺序反推算，可知最优方案有两个：（1

24、）由于 x10 ,根据 S2=S1 - x1 =5 - 0=5,查表 5-4 知 x2 2 ,由 S3=S2 - x2 =5-2=3 ,故* . . . . .一 . . ， .一 . . . .一 . . 一 x3 S3 3。即甲工厂分配 0台、乙工厂分配 2台、丙工厂分配 3台。（2）由于 x12 ,根据 S2=S1 - x1 =5 - 2=3,查表 5-4 知 x2 2 ,由 S3=S2 - x2 =3-2=1 ,故9文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持*. . . . .一 . . ， .一 . . . .一 . . 一X3

25、S3 1。即甲工厂分配 2台、乙工厂分配 2台、丙工厂分配1台。以上两个分配方案所得的总盈利均为21万元。在此问题中，如果原设备的太熟不是5台，而是4台或3台，用其他方法求解时，往往需要从头再算，但用动态规划求解时,这些列出的表仍旧有用，只需要修改最后的表格就1,x37.1 求解下列矩阵对策，其中赢得矩阵 1/ 211（1） 1 1/ 211 11k种货物的件数。0,1,2，,15；0,1,2，,15, S4S3 4x3；0,1,2，,15, s s 3x2；2xi °* 一 一，0,x4 0,最优值为22千克。A分别为22 16(2)1451可得到：当设备台数位4台时，最优分配方案

26、为x*1,x22,x31或x*2,x；2,x30,总盈利为17万元。当设备台数位3台时，最优分配方案为：x* 0,x2 2,x3 1,总盈利为14万元。5.4设有一辆载重量为 15吨的卡车，要装运 4种货物。已知4种货物的单位重量和价 值如表5-6所示，在装载重量许可的情况下每辆车装载某种货物的条件不限，试问如何搭配这4种货物才能使每辆车装载货物的价值最大？表5-6货物代号重量（吨）价值（千元）货物代号重量（吨）价值（千元）123345234456解：设决策变量x1,x2,x3,x4分别为4种货物的装载件数，则问题为一线性整数规划:将其转化为动态规划问题，分为4个阶段，每个阶段的指标函数记为g

27、1（x1）3x1, g2（x2）4x2, g3（x3）5%, g4（x4）6x4状态变量Sk表示第k种至第4种货物总允许载重量，即允许状态集合为 Q 0,1,2，,15, k 1,2,3,4,最优值函数fk（sJ表示装载第k种至第4中货物的价值，则动态规划模型为状态转移方程为允许决策集合为即表示在载重量允许的范围内可能装载第用逆推方法求解如下：D4（s4）0,1,2, -,包,S45D3（S3）0,1,2,，s3, S34D2（S2）0,1,2, ', S2 , S2Di（15）0,1,2，,7 , S2 15最后得到问题的最优解为x* 6,x210文档收集于互联网，如有不妥请联系删除

28、文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持9 3 18 02 7 2 16 5 4 6 72 2 3 4(3)(4)2 4 3 3 83 5 4 45 6 2 2 12 3 163 2 3 5 4解：(1)由于max min aj 1, min max aj 1/2，所以A所对应的支付矩阵没有纯对 i j jj i j策。即局中人1以(0.36,0.36,0.27)的概率分别出策略 1、2和3,其赢得值为-0.4545。(2)由于maxminaij1, min max a. 2,所以A所对应的支付矩阵没有纯对策。i j ijj i ij即局中人1以0.56、0.44的概率分别

29、出策略 1和策略2,赢得值为0.67.(3 )根据赢得矩阵有 max min ajmin max aja31 3 ,所以 G 的解为i jj i(3, 1)，Vg 3。(4 )根据赢得矩阵有max min aij min max aija23 4 ,所以 G 的解为1 j j j i j(2,3),VG 4 °7.2 甲、乙两家公司生产同一种产品，争夺市场的占有率。假设两家公司市场占有率之和为100%,即顾客只购买这两家公司的产品，无其他选择。若公司甲可以采用的商业策略为A1、A2、A3,公司乙可以采用的商业策略为B1、B2、B3。表7-1给出在不同策略下公司甲的市场占有率。在此情况

30、下，请为这两家公司选择他们的最优策略。表7-1B1B2B3A10.40.80.6A20.30.70.4A30.50.90.5解：若完全采用二人常数和对策的方法确定最优纯策略，则由可得，局中人甲采用策略 A3、局中人乙采用策略 B1,各获得50%的市场占有率。从计算结果可以看出，局中人甲采用策略A3、局中人乙采用策略 B1,各获得50%的市场占有率。10.1 某一决策问题的损益矩阵如表10-1所示，其中矩阵元素值为年利润。表10-1单位：元(1)若各事件发生的概率 Pj是未知的，分别用max min决策准则、max max决策准则、 拉普拉斯准则和最小机会损失准则选出决策方案。(2)若Pj值仍是

31、未知的，并且 是乐观系数，问取何值时，方案 S1和S3是不偏不倚的？(3)若P1=0.2,P2=0.7,P3=0.1,那么用EMV准则会选择哪个方案？解：(1)采用maxmin准则应选择方案 S2,采用maxmax决策准则应选择方案 S1，采 用Laplace准则应选择方案 S1，采用最小机会损失准则应选择方案(2) 0.10256;(3)方案 S1 或 S3。11文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持10.8假设有外表完全相同的木盒100只，将其分为两组，一组内装白球，有 70盒，另一组内装黑球，有 30盒。现从这100盒中任取一盒，

32、请你猜，如这盒内装的是白球，猜对 了得500分，猜错了罚200分；如这盒内装的是黑球，猜对了得1000分，猜错了罚150分。有关数据列于表10-7。(1)为使期望得分最多，应选哪一种方案？(2)试求出猜白和猜黑的转折概率。图 10-1计算各方案的期望值。猜白”的期望值为0.7 * 500 + 0.3 * (-200) = 290猜黑”的期望值为0.7 *(-150) + 0. 3 * 1000 = 195经比较可知 猜白”方案是最优的。现假定出现白球的概率从0. 7变为0.8,这时各方案的期望值为猜白”的期望值为0.8 * 500 + 0.2 * (-200) = 360猜黑”的期望值为0.8 * (-150) + 0.2 * 1000 = 80可见猜白方案仍是最优的。再假定出现白球的概率从0.7变为0.6,这时各方案的期望值为猜白”的期望值为0. 6 * 500 + 0.4 * (-200) = 220猜黑”的期望值为0.6 * (-150)