管理运筹学整理答案

第二章2.5表2-3为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxz=5x+3x，约束形式为＜，x,x为松弛变量，表中解代入目标函数后得z=10。1 2 3 4表2-3x1x2x3x4x3 2c011/5x1 ade01Gb-1f g 求a〜g的值；表中给出的解是否为最优解。解：a=2,b=0,c=0,d=1,e=4/5,f=0,g=5；表中给出的解为最优解。2・6表2-4中给出某求最大化线性规划问题的初始单纯形表及迭代后的表，x,x为松4 5弛变量，求表中a〜I的值及各变量下标m〜t的值。表2-4xxxxx12345xm6bcd10x1-13e01na1-200x、jfg2-11/20x4h11/21tG07jk/解：a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0；变量的下标为m—4,n—5,s—1,t—62・10下述线性规划问题：max鶯=呂斗H-4te+6x^+3^-,9眄'百+2卫+込+3工工§M1丽(资源“

心l+3旳+?芮+q+J7：<270(资源对'工|十3比+2劝+不十壮$荃1B0〔资源3、E鼻0 (j=1*…♦5)已知最优解中的基变量为口虫】・应・且已知313'-1-11-3r2411Ji一&9-327_213_L2-3L0J要求根据以上信息确定三种资源各自的影子价格。解：由以上信息可以求得该问题的对偶问题的最优解1-11-31-(4 8\Yt=CB-1=——x(6,8,9)-69-3=-丄：b 2713 3丿2-310所以三种资源的影子价格分别为418。3’‘32.11某单位加工制作100套工架，每套工架需用长为2.9m、.lm和1.5m的圆钢各一根。已知原材料长7.4m。问如何下料使得所用的原材料最省？解：简单分析可知，在每一根原材料上各截取一根2.9m,2.lm和1.5m的圆钢做成一套工架，每根原材料剩下料头0.9m,要完成100套工架，就需要用100根原材料，共剩余90m料头。若采用套截方案，则可以节省原材料，下面给出了几种可能的套截方案，如表2-5所示。表2-5可能的下料方案长度/mABCDE2.9120102.1002211.531203合计/m7.47.37.27.16.6料头/m00.10.20.30.8实际中，为了保证完成这100套工架，使所用原材料最省，可以混合使用各种下料方案。设按方案A,B,C,D,E下料的原材料数分别为x1?x2，x3，x4，x5,根据表2-5可以得到下面的线性规划模型minz=0x+0.1x+0.2x+0.3x+0.8x1 2 3 4 5x+2x+x=1001 2 42x+2x+x=100St< 3 4 53x+x+2x+3x=1001 2 3 5x>0,i=1,2,3,4,5i用大M法求解此模型的过程如表2-6所示，最优解为:：*=(0,40,30,20,0)t,最优值为z*=16。表2-6CjXbBB-MX6100-MX7100-MX100»-j160101004M1-0.1

+3M2-0.2+4M0-0.3+3M3-0.8+4M100/3-MX6200/35/3-2/3-1-1/3200/3-MX7100100/2-M-0.3-0.1-0.3X6X4X2X450/3501050301/3

-0.1

+5M/3[5/3]表2-6CjXbBB-MX6100-MX7100-MX100»-j160101004M1-0.1

+3M2-0.2+4M0-0.3+3M3-0.8+4M100/3-MX6200/35/3-2/3-1-1/3200/3-MX7100100/2-M-0.3-0.1-0.3X6X4X2X450/3501050301/3

-0.1

+5M/3[5/3]1/3

-0.1

+5M/32/3-0.2+4M/3-5/32/30.1-5M/3-10-0.3+3M-0.8-3/21/21-0.65-3M/2-9/101/213/10-0.741/3-4M/33/5-1/5-M+0.06-1/21/200.153M/2-3/101/21/10

-M

+0.12-1/31/3-4M/3-1/52/5

-M

-0.02150/15100/1求解该问题的LINGO程序如下：model:sets:row/1..3/:b;arrange/1..5/:x,c;link(row,arrange):a;endsetsdata:b=100,100,100;c=1,0.1,0.2,0.3,0.8;a=1,2,0,1,0,0,0,2,2,1,3,1,2,0,3;enddatamin=@sum(arrange(j):c(j)*x(j));@for(row(i):@sum(arrange(j):a(i,j)*x(j))=b(i););end运行该程序后，也立即可以得到最优解为：x*=(0,40,30,20,0)T最优值为z*=16。即按方案B下料40根，方案C下料30根，方案D下料20根，共需原材料90根就可以制作完成100套工架，剩余料头最少为16m。2.13某昼夜服务公交公司的公交线路每天各时段内所需要司机和乘务人员如表2-9所示。班次时间所需人数班次时间所需人数16:00-10:0060418:00-22:0050210:00-14:0070522:00-2:0020314：00-18：006062:00-6：0030设司机和乘务人员分别在各时段开始时上班并连续工作8小时。问该公司公交线路应如何安排司机和乘务人员，使得既能满足工作需要，又使配备的总人数最少？(本科生仅需建立问题的数学模型)解：设x.为安排从第i班次开始时上班的人数，则该问题的数学模型为minz=minz=工6xi=1ix+x>6061x+x>7012x+x>60s.t.TOC\o"1-5"\h\z2 3s.t.<x+x>50

34x+x>205x+x>306x>0,i=1,2,...,6i求解此模型得到最优解：x求解此模型得到最优解：x*=(40,30,30,20,0,30)T,z*=150。2.18现有线性规划问题maxz=-5x+5x+13xTOC\o"1-5"\h\z1 2 3—x+x+3xW201 2 3s.ti12x+4x+10x<901 2 3x,x,x>0123先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？约束条件①的右端项系数由20变为30；约束条件②的右端项系数由90变为70；目标函数中x的系数由13变为8；3解：在上述LP问题的第①、②个约束条件中分别加入松弛变量x4,x5得maxz=—5x+5x+13x+0x+0xTOC\o"1-5"\h\z1 2 3 4 5—x+x+3x+x=201 2 3 4s..i12x+4x+10x+x=901 2 3 5x,x,x,x,x>012345列出此问题的初始单纯形表并进行迭代运算，过程如表2-12所示。表2-12c-551300eiCjXbxxxxxBB123450X420-11[3]1020/30x90124100195G-55130013jX320/3-1/3[1/3]11/30200x70/346/32/30-10/31355G-2/32/30-13/305jX220-113100x10160-2-415G00-2-50由表2-12中的计算结果可知，LP问题的最优解X*=(0,20,0,0,10)Tz*=5*20=100。(1)约束条件①的右端项系数由20变为30,则有"10""10""30"-41_90_Bib=30-30_列出单纯形表，并利用对偶单纯形法求解，过程如表2-13所示。表2-13c-551300jCXbxxxxxBB123455x^30-1131002X-30160[-2]-415G00-2-505x2-152310[-5]3/213x15-8012-1/23G-1600-1-10Jx43-23/5-1/501-3/1013x96/52/5101/103G-103/5-1/500-13/10由表2-13中计算结果可知，LP问题的最优解变为X*=(0,0,9,3,0)t,z*=13x9=117。(2)约束条件②的右端常数由90变为70,则有'20、<-10丿('20、<-10丿B-1b=1-4列出单纯形表，并利用对偶单纯形法求解，结果如表2-14所示。

由表2-14结果知，LP问题的最优解变为X*=（0,5,5,0,0）t,z*=5x5+13x5=90。（3）目标函数中x3的系数由13变为8,由于x3是非基变量，其检验数变为b二8一5x3一0x（-2）=一7<03所以LP问题的最优解不变。第三章「1生产第i类服装0否则maxz=「1生产第i类服装0否则maxz=120x+10x+100x一5000y一2000y一3000y1 2 3解：设X.为第i类服装的月产量，y=J1 i表3-4设备租金（元）生产成本（元/件）销售价格（元/件）人工工时（小时/件）设备工时（小时/件）设备可用工时（小时）服装种类西服500028040053300衬衫2000304010.5480羽绒服3000200300426002 35x+x+4x<20001 2 33x<300y110.5x<480ys.t.Ss.t.S2x<600y3x>0,且为整数iy=0or1i3・6某部队现有5种武器装备储存管理，存放量分别为°怡=1,...,5）。为了安全起见，拟分为8个仓库存放，各仓库的最大允许存放量分别为巧心=1,...,8）,且有工5a<工8b。J i=1L j=1j一种武器装备可以分多个仓库存放，但每个仓库只能存放一种，也只能整件存放。已知第i种武器装备每单位在第j个仓库存放一年的费用为Cj•。第j个仓库固定费用为每年dj元，但若仓库不存放则没有费用。要求设计一个使总费用最小的存储方案，试建立相应的优化模型。解：设x-.为第i种武器装备在仓库j中存放的数量,iJ=J1,第i种武器装备存放在第•个仓库中%=10,其他

minHc*X+工(d*minHc*X+工(d*ij ij jj乙x=a,Vijijix<by,Vi,jpjij乙y<i,VjiijX为整数，且y为0或1,1ij ijs.t.<工y)iijVi,j3.7某地准备投资D元建民用住宅。可以建住宅的地点有n处：A、、A2、……、A。1 2 nA.处每幢住宅的造价为《•，最多可造a.幢。问应当在哪几处建住宅，分别建几幢，才能使建造的住宅总数最多，试建立问题的数学模型。解：在Aj地所建住宅的数量为Xj,11,在A地建住宅

y=\j

j[o,否则则该问题的数学模型为maxz=工xjj=1x<ayjjj<艺dx<Djjj=1x为整数,y=0or1,Vjj3・9某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为吨）以及各工厂到各销售点的单位运价（元/吨）如表3-5所示，要求研究产品如何调运才能使得总运费最小。试建立该问题的数学模型，并采用表上作业法求出最佳的调运方案（要求用最小元素法找到初始调运方案）表3-5产地销地B]B2B3B4产量A]41241116A22103910A85116223销量8141214解：数学模型:

minz=4x+12x+4x+llx+2x+10x+3x+9x11 12 13 14 21 22 23 24+8x+5x+11x+6x31 32 33 34x+x+x+x=1611121314x+x+x+x=1021222324x+x+x+x=2231323334x+x+x=8112131x+x+x=14122232x+x+x=12132333x+x+x=14142434x>0,Vz,j利用最小元素法，求得的初始解表3-6非基变量的检验数:利用最小元素法，求得的初始解表3-6非基变量的检验数:表3-7由于非基变量x24的检验数为负，所以初始解不是最优解，x24进基，在闭回路{x24,x23,x13,x14}中进行运量调整，得到新的调运方案：A28210A14822销量8141214重新计算检验数:表3-9表3-9计算得到的总运费为：12*4+4*11+8*2+2*9+14*5+8*6=244.有多个最优解！3・14某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售。各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3-20所示。问该公司应如何调运产品，在满足各销售点的需要量前提下，使总的运费为最小。解：（1）求初始调运方案①方法一：利用最小元素法求得的初始调运方案如表3-21所示。②方法二：利用伏格尔法求得的初始调运方案如表3-22所示。表3-22

（2）最优解的判别得到运输问题的初始基可行解后就要判别这个解是否为最优解，判别的方法是计算非基变量即空格的检验数。因运输问题的目标函数是要求实现最小化，所以当所有的非基变量检验数全都大于等于0时为最优解。下面分别使用两种求空格检验数的方法。①方法一：闭回路法对于表3-22所示的初始调运方案，利用闭回路法计算所有空格的检验数，如表3-23所示。空格闭回路检验数(A.B.)(1,1)—(1,3)—(2,3)—(2,1)5(AB)(2,2)—(2,3)—(1,3)—(1,2)4122'(A’.B,)(2.4)—(2,3)—(1,3)—(1,4)3p*2'4" (A「BJ(3.1)—(3,3)—(2.3)—(2.1)23-31^ （A3，B2）(3,2)—(3,3)—(1,3)—(1,2)12(3.4)—(1,4)—(1,3)—(3,3)8这时检验数均为正数，所以表3-22给出的方案即为最有调运方案。②方法二：位势法联立方程：u1+v3u1+v3=3,u1+v4=10,令v4=0得<u二101u二8，2u—53u+v=1, u+v=8,u+v=4,1 2 4 3 2v—-71v—1。v—-73v—04u3+v4=5对于表3-22所示的初始调运方案，利用位势法计算所有空格的检验数，结果与用闭回路法得到的结果相同。最优调运方案：A]fB25t,A1^B44t,A2^B13t,A2^B31t,A3^B37t，最小运费78兀。第四章4.3某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。解：该问题的数学模型如下：minZ=pd-+pd-+pd++12233p(d-+d++d-+d++d-+d+)4445566500x+650x+800x+d--d+=16000TOC\o"1-5"\h\z2 3 1 16x+8x+10x+d--d+二2001 2 3 2 2d++d-—d+=243 3s.t.<x+d--d+二12s.t.4 4x+d--d+二105 5x+d--d+二66 6\o"CurrentDocument"x,x,x>0,d-,d+n0(i=1,2, ,6)1 2 3 ii4.4已知条件如表4-9所示。表4-9工序型号每周最大加工能力AB1（小时/台）4615011（小时/台）3270利润（元/台）300450如果工厂经营目标的期望值和优先等级如下：P1:每周总利润不得低于10000元；P2：因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；P3：希望工序I的每周生产时间正好为150小时，工序II的生产时间最好用足，甚至可适当加班。（1） 试建立这个问题的目标规划模型。（2） 如果工序II在加班时间内生产出来的产品，每台A型机减少利润20元，每台B型机减少利润25元，并且工序II的加班时间每周最多不超过30小时，这是P4级目标，试重

新建立这个问题的目标规划模型。解：(1)目标规划模型：minf=pd-+p(300d-+450d-)+p(d-+d++d-)11 2 2 3 3 4 4 5300x+450x+d--d+=100001x1211+d—d211+d—d+=10

22x+d—d+=152 3 3+6x+d—d+=1502 4 4+2x+d—d+=702 5 5i=1,2,3,4,5s.t.<4x13x1x,x,d-,d+>0minf=pd-+p(300d-+450d-)+p(d-+d++minf=pd-+p(300d-+450d-)+p(d-+d++d-)+pd+11 2 2 3 3 4 4 5 46300x+280x+450x+425x+d--d+二10000123411x+x+d-—d+=101222x+x+d-—d+=1534334x+4x+6x+6x+d-—d+=1f1234443x+3x+2x+2x+d-—d+=70123455d++d-—d+=30566x,x,12x,x,d-34i,d+>0ii=1,2,3,4,5,6s.t.bbbbbbbb23123q6一a(2)1一245'510a2107q23a34p6(1)ap2a631-第七章7.1在下列矩阵中确定p和q的取值范围，使得该矩阵在(a,b)交叉处存在鞍点。22解：(1)p>=5,qv=5;(2)pv=7,q>=77.3下列矩阵为局中人A,B对策时局中人A的赢得矩阵，先尽可能按优超原则简化,再用线性方程组求解方法求局中人A,B各自的最优策略及对策值。

1)-140122234 0 3 00 2 5 9(21)-140122234 0 3 00 2 5 9(2) 7 3 9 5 96 8 7 60 8 8 3「-3302_「240-2_(5)-4-12-2(6)482611-20-20420-13-1-4-2-20—————0411解：(1)矩阵中第3列优超于第4列，第1列优超于第3列，所以划去第3列和第4列得到新的赢得矩阵10A1=A1=2204矩阵A1中，第3行优超于第1行，第4行优超于第2行，在矩阵A1中划去第1行和第2行得新赢得矩阵A2：「22]A=2L04在赢得矩阵A2中存在鞍点a11=2而a11为原赢得矩阵的第3行第1列元素，所以原矩阵对策的解为Q,P),v=2。1G(2)由于第3行优超于第2行，第4行优超于第1行，故可划去第1、2行，得到新的赢得矩阵395939594687660886088对于A1，第2列优超于第3、4、5列，得到「73Ac=46

260对于，第1行优超于第3行，故可划去曜3行，得到A=3A=37346易知a3没有鞍点，故求解7x7x+4x=v343x+6x=v34x+x=1347y+3y=v124y+6y=v12y+y=1121=1=2'y2=丄,v=5，所以原矩阵对策的一个解为2；，2,0,0,0；，2,0,0,0122丿\t,V=5

GX*=(1/6,0,3/6,2/6),Y*=(2/6,0,1/6,3/6),v=0X*=(0,3/4,1/4,0),Y*=(1/4,0,3/4,0),v=5/27.4写出与下列对策问题等价的线性规划问题。_133_421322(2)解：(2)等价的LP问题如下:maxvix+4x+3x>vTOC\o"1-5"\h\z1 2 3I3x+2x+2x>v1 2 3Is.t.<3x+x+2x>vs.t.<1 2 3 Ix+x+x=11 2 3x>0,i=1,2,3immviiy+3y+3y<vTOC\o"1-5"\h\z1 2 3II4y+2y+y<v1 2 3IIs.t.<3y+2y+2y<v1 2 3IIy+y+y=11 2 3y>0,j=1,2,3Jj第十章10.1某一决策问题的损益矩阵如表10-1所示，其中矩阵元素值为年利润。表10-1表10-1Ei鬥Pi400360000方Ei鬥Pi400360000方案若各事件发生的概率P是未知的，分别用maxmin决策准则、maxmax决策准则、拉j普拉斯准则和最小机会损失准则选出决策方案。若P值仍是未知的，并且a是乐观系数，问a取何值时，方案S,和S3是不偏不倚的？j 1 3若Pi=0.2,P2=0.7,P3=0.1,那么用EMV准则会选择哪个方案？解：(1)采用maxmin准则应选择方案S2，采用maxmax决策准则应选择方案S],采用Laplace准则应选择方案S],采用最小机会损失准则应选择方案S”(2)0.10256；(3)方案S1或S3。10.2某地方书店希望订购最新出版的好的图书。根据以往经验，新书的销售量可能为50,100,150或200本。假定每本新书的订购价为4元，销售价为6元，剩书的处理价为每本2元。要求：(1)建立损益矩阵；分别用悲观法、乐观法及等可能法决定该书店应订购的新书数字；建立后悔矩阵，并用后悔值法决定书店应订购的新书数；如果书店据以往统计资料预计新书销售量的规律如表10-2所示。表10-2需求数50100150200占的比例/%20403010分别用期望值法和后悔值法决定订购数量；如果某市场调查部门能帮助书店调查销售量的确切数字，该书店愿意付出多大的调查费用？解：(1)损益矩阵如表10-3所示。表10-3销售■■订购E150E1002E3 150E2004S150100100100100S21000200200200S3150-100100300300S200-2000200400

（2）悲观法：S],乐观法：S4，等可能法：S2或S3。3）后悔矩阵如表10-4所示。表10-4E1E2E3E4最大后悔值S10100200300300S21000100200200S32001000100200S