《管理运筹学》_田世海(习题及解答).docx

《《管理运筹学》_田世海(习题及解答).docx》由会员分享，可在线阅读，更多相关《《管理运筹学》_田世海(习题及解答).docx（44页珍藏版）》请在三一办公上搜索。

1、2.5用单纯形法和Excel求解下列线性规划问遨maxf=-x1+Ix2+x3t2 .r+与+W4.v7.rl+2xj6.rl,x2,x50minf=Xy-3x2-2.q3 .tl-x2+2xy62x+4.12-4x1，3叫+8xlIO内，三，,02。最优斛：X*=(14/5.22/5.1,0.0,0)z目标函数由优(ftmin2=-62/52.6分别用,M法和两阶段法求解下述线性规划问题，井指出是哪送解。min=2.vl+3x2+内maxZ=10i-5x2+.q(1)SJ.8(25xi+3x2+xj=103.0+2x6x.t.-5xl+.r,-10x15j,x,x50xiOJ=1.2.3(1

2、)鹳法一:大M法标准化加入人工变量得:maxz,=-2x,-3x2-xi-Mx6-Mx1X,+4x,+2xi-x4+A6=8sJ：3xl+Ix2-xi+X7=6xi,2,xj,x4,xj,6,x70迭代最优单纯形表如的C1.-2-3-IOO-M-MCBXB,bXiX1XaXXsX，-3X29/5-2Xi4/5O13/5-3/101/103/10-1/101O-2/51/5-2/5-1/52/5Q-OOO-1/2-1/21/2-MI/2-M最优解：X=(4/5,9/5,0,0,0,0Q)T目标函数最优值minZ=7解法二：两阶段法第一阶段数学模型为:maxT=-J6-x7.r1+4x,+2x1-

3、4+6=8SJA3.v1+2.r,-xi+x7=6.VpJ2tXrX41X51X6tXT0最优单纯形表如KC1.00000-I-IC8XbBlhXiX：XX4XSX?0X：9/5013/5一3/101/103/10-1/100X14/510-2/51/5-2/5-1/52/5Cj-Zj00000-I-I第二阶段爆优冷纯形去如下:C1.-2-3-I00CbXbBrbXiXjX?X4X53X29/5013/5一3/101/102Xi4/510-2/51/5-2/5C-Zi0001/21/2最优解：X.=(4/5.9/5.00.00.0)T目标函数最优值minZ=7因为X3的检验数=.所以此线性规划

4、同跑有无穷多最优解.(2)解：大M法数学模型为maxZ=l().vl-5x,+xj-Mxi5a+3,+x+xj=I0-5xi+x,-I0+x4=15/0,=I,2,5C(j)10-510-MR.H.S.RatioBasisa。XlX2X3X4X5X5-M53101102X40-51-10I015MC(j)-Z10-51000*BigM531000Xl10I51501/52X4004-91I25C(j)-Z(j)0-II-I0-220BigM0000-10最优觥X=(2.00)：Z=20两阶及法，第一阶段：数学模型为ninif=x55x1+3a-,+xj+x5=10-5xl+x2-IOx3+x4

5、=15xjO.y=,2,5C(j)OOOIR.H.S.RatioBsisQi)XlX2X3X4X5X51(5131O1102X4O-51-10IO15MC0)-Z(j)5-3OOXlO13/51/5O1/52X4OO49II25C(j)-Z(j)OOOOI第二阶段CG)10-5I0R.HS.RatioBasisC(i)XlX2X3X4Xl10i3/51/5022X4004-9125MCO)Zj)0*11-10最优解X=(2.0.0):Z三202.7(I)当现行解为可行解，且对应非菸变业的检胎数均小于0时，雄性规划问题才彳i惟一最优解.即的0，ajO.a0,(2)线性规划向遨行多重最优解是当某个

6、非基变她的检5金数为0所以ajO.a5=O.a0(3)现行解为退化恭本以优解的条件是地变此中含有零分疑，且所有的检验数均#仅，所以asO.OfiWO1.1 a20.现行解为可行情.0.a4O0r.该线性规划目标函数无界.因此参数范围地a*0.360.a4O(5)当alO,如aaIXi/g2-11/204hiI1/210-7Jk1.解：a=3.b=2.c=4.d=-2.c=2.f=3.g=l.h=0.1=5.j=5.k=M,l=02.9 工厂每月生产甲.乙,丙三种产品，单件产品的原材料消耗收、设每台时的消耗景、资源限量及单件产品利润如表2-28所示，表228，种产品附件产品利润如表产品资源甲乙丙

7、资源限JltHH(kg)1.51.242500设备台时）31.61.21400利润（元/件）101412根据市场蠹求，预测种产M最低月需求量分别是150、260和最祖J荒求是250、310和130,试建立该问题的数学模型,使每月利润最大。解：设即.处、的分别为产品甲、乙、丙的产量,则数学模型为maxZ=10.vl14x21Zql.5x1+l.2x,+4x125003x1+1.6x,+1.2x1400I5025O6O231O12O13Oi.x02.10 某糖果厂用原料A.B.C加工成三种不同牌号的轴果甲、乙、丙。己知各种牌号釉果中A.B.C的含量,原料成本,各种原料每月的限制用量,三种牌号相果的

8、单位加工费及件价如表2-29所示.何该厂每月生产这三种牌号糖果各多少kg使得到的利润为最大？试建立这个何区的线性规划数学模型.衣2-29三种号融果的单位加工费及竹价甲乙丙原料成本玩/kg每月限用勒kgA60%20%2.(X)200()B1.502500C-2.O(ll+1j+u)-I.5O(ji+x2+2J-I.Xji+u+xm)xlX12.v1j52000Xn+.tn+xn25xum+u4IKKJx0.6(x,1t21Xj1).X0.2(*“十X，),203(,j+m+m)*2$(*12*S+1心)XBS).6X+*%),(1.2E23)2.11 建筑公司需要用6m长的塑钢材料制作A、B两种

9、型号的窗架，两种窗架所需材料烧格及数量如表2-30所示.问怎样下料使窗（1）用数量少：（2）余科最少?表2-30两种窗架所需材料燃格及数依型号A型号B付食窗架需要材料长凌m）数量（根）长度（m）数量（根）An1.72Bu2.72A3i1.33B2:2.03需要找（套）2150解：第一步：求下料方案.见下表.方案.三四/1六七八,l.十十一十二十三十四需要4B1:2.7m2II1OOOOOODOOO300B2:2m0I00322I11OOOO450Al:1.7m001001O21O32IO400A2:1.3m0II20O1O13O234600余料Q6003四70030.70.610.10.9O0

10、.40.8第二步：建立线性规划数学模型设均(尸1.2.，14为笫j种方案使用原材料的根It则(I)用料最少数学模型为14minZ=x,M2xl+x,+X,+x4300X2+3.rj+2x6+2.0+Xlj+.7+.%)450X3+.*+2/+/+3.v11+2.v1,+xn4002+X,+2a;+.v7+演+3xl0+2x1,+3.v1,+4am600xjOJ=1,2,14用单纯形法求解得到两个基木最优解X,=(50.2(X).0.0.84.0.().0.0.0.0.2()0.0.01:Z=534X,2,=(0,200.l.0.84,0.0.0.0,0,0.150.0.0)2=534余科最少数

11、学模型为minZ=0.6xl+0.3.+0.7XII+0.4xlj+0.8xl41.1 l+X2+Xy+4300x2+3xl+2x6+2x7+Xx+xm+1j450xf+.r6+2+3,rll+2.vl,+xlj400.x2+xj+2xl+x7+.,+3x+2玉2+3.rn+4.v14600O=1.2,.I4用单纯形法求解得到两个基本最优解X,l,=(0,300,0,0,50.0.0.0.0.0.0.2(X).0.0);Z=0.用料550根X2,=(0,450.0,0,0,0,0,0,0.0.0,200.0.0)Z=0，用料650根显然用料最少的方案也优.习题31.2 判断对错.并说明为什么.

12、(1)任何线性规划同应存在并具有唯一的对偶问即，(2)根据对钩间题的性质，行原何明为无界解时，其对偶问题无可行解；反之，当对仍问题无可行耨时.其晾问时具有无界解.(3若跳性规划的原同咫有多也最优解.则其对例问JS也一定具有多盅最优解.(4)则恒有：设x.y分别为标准形式的原问捌与对偶问题的可行解,f.y*分别为其最优解.sic=X,8min=3M+5.0x1I2xl-9-9x,+9.xl.i0.xj0O.r=1.2.1.m:J三1.2.1.9n解:M加W=5,+8%+20)、SJA-yi+6,y2+l2.yj1居+7y9y”2-J1+3y,-9y333-5力+9为=4M无限制,0,yjmaxw

13、=8vl+4y2(2)SJ.-v+2v233y1+.y256yl-y2ly.y2minw=mb+nbn+nC(3) 1.i1.SJ.0.m无约束3.3用对偶单纯形法求下列战性规划向明maxW=ZaM+WI-IJ-IM1+VjMqi无限制i=1,2,m;j=,2,n解:minz=x+x22xl+.v,4sJ.rl+326.r1.r20minz=x+x2X1+2x2+xi4sJ.2.vl-xi+3x,7x.x,.x30呆优研：X,=(0.0.4.0.5)r目标函数批优值03.4Wi(D对偶问题为:minh三8i+4y2y,+3y,42yl-2y,2-1+2v,3y.y2o将x=5.V2=4带入约束

14、条件的为严格不等式，由互不松弛性得最优解：X=(O,IO.I2)目标函数最优值：/=283.5minW=8y1+6y2+6y,+9y4y+2y2+9y,2s/(2f=(45.35,l,0)3v1+V2+j+v44X+N.V1+.VjiK0J=1.2.3.43.6 解(I)设：用,士空3分别为产品A、B.C的产录,则该问题的线性规划模里为:maxZ=3.v,+,+5.v,61+3.v,+5,453xl+4.r,+5.v130.vi.,x0用单纯形法迭代的最优解如F表：C1.31500C15XbBlbXlXaXsXlXj0X4153-I01-15X363/54/5101/5Cj-Zj0-300-1

15、因而嫉优解X=(0.0,6)r,最大利润为30(2)劳动力和原料的影子价格分别为0.I,议购进的原料数为M?.为保挣最优基不变,必有8而夕，一斗451-S-纳卜。-IkO1/5人30+MJlk6+,5j因而几多可购进原料15单位，总利涧增加CM-6_30=(0jf45,1-30=15(单30+Ap2)位,净利润增加l5-O.8xS=3单位。C3.原最优解不变，C3e5最优计划不变.(4)劳动力可以诚少15个单位，原G优解不变.(5)最优解X=(0.().6.15.0.4尸，最大利润为30.注：本题还有另一个最优解X=(5,0,3Q,0),maxZ=30.3C6.5/2WGW53.7 解最优解为

16、：X=(0.20.0.0J0)rmaxZ=100(D酸优基不变,最优解为：X=(O,20,基0,15JmaxZ=100(2)最优解为：X=(0.0.9.18.0)rmaxZ=117(3)最优解不变。(4)最优解为：X=(5/8,1658.0,0,0)rmaxZ=965/8(5)被优解不变.(6最优解为：X=(0,0,20/3,0,703)rmaxZ=260/3(7)以优解不变.8)最优解为：X=(0.25/25/2.0.15.0/maxZ=95(9)最优解为：X=(0,20.0,0,2OVmaXZ=1003.8 (1)按从初始表为最终表的迭代电序,从最终表反推回去即得初始表.如下Xl2X4Xs

17、X450I2I0XS103-I10ICj-Zj6-21000(2)计算最终衣中N”X.NS的新的桧骁数/1/21/20、/、C11B(pi.pl,p5)-(c2,q,c5)=(I0.6+tt1-(-2,0.0)0-1/Z-l/nI/Oj(4-l2,.4-l6fl.2+i3f1)0EP-6rl8Bj.原最优解不变.(3)B,b=B(y+b)=1/20V5+2-1/61/3JJO+0-53XlX2X3X4Xs21012X252I03ci-zt1003X411/201/2IX221/21-3/20Cj-Zj-1/20-3/2020时，CHBr(p,.pj-=(-2,-l)fk21/2I-=(1/2-

18、,32-2)11/2-32j最终表如下：XiX2XjX4X411/2*01/2iX221/2I-3/20Cj-Zj-202-320l2-0l2时，表I中刈的检验数首先变为负数，故迭代得下表Xi2XtX4Xi210142X2I01-2-IQZ100-l-2故关系曲戏如下图Xi2-I0-2-I*IWXW2时为显优表X210I11三inz=lG-ZJ00-5-INN2时为最优表.xl-2I()21Binz=-1x11II-30图示如右所示Cj-Zj-I0-303.11制：（1）先将Q值反映到最终表中.故见终表变为3.10解：目标函数化为求极大.先求出入川时的数优解,为简便用对照单纯形法,即XiX2X

19、3X4Xi2I0-2-IX：-10I-PIQZ100-5-IXi4XjII0-2-10I-3G-ZJ0-50-6最终表变为Xi2XX4OWWl时为业优表Xi4-31一20一3minz=-5*63I0-rI-IGN0-50-6XlX23X4xsXi2+日101/2-1/20X：0I1/2IZ20OWC2时为最优.Imaxz(0)二20先*4-？00-1/21/2*12OZj00-l-220Xi61000IX22+夕0I10-1X48-800-rI2Cj-ZjI()O3()248时为最优,maxZ(D)=12+96Xi61000IX2100101IXj。一80OI1-2-C时为G优,G-Zj1.m

20、axz()=36W(2)作图如下3.12W：设该厂每天生产原稿纸Xi捆，11记本X2打，练习本X、箱，又加人表示该厂招收的格时工数，则本例可列出如卜的参数线性规划模型：inaxz(2)=.v+2x2+3.v,-15z3-xl+13-.v,+26-.ri30000333.vf30-V,+-a100+3030xy0,(y=1.2.3)（八）当入=0时求解得JR终单纯形衣如NXiX2XaX4X5X220107/31/10-10XI100001-4/3-1/1040G-Zj00131/10-20即该厂呆优生产计划为生产原稿纸100O捆,日记本2000打，可盈利5000元/天。(B)从上表中看出劳动力的

21、影子价格为2()元/天,大于市场价格.故该厂应招收临时工，,b=f1/10TOmq将我反映到上表中，并用对偈单纯形表计过程如k-l040M40A)下:XiX2XAX4KSXJ2(XK)-00I7/31/10-oXi10+40I0-4/3-1/1040G-ZJ00-1/3-1/10-20xs200-1/10-7/30一1/1001Xi9WX)I483/100CrZ10-2-5-3/100由此可知,当招收I1时工人数在200人以下时，该厂盈利z=57.当3200时，盈利为z=9000-5A.z()前参数人变化如右图.0200200习题44.1(3)(5)J其余X4.2运S邕BlB2B3B4B5产量

22、产地Al0005510产地A20090312产地A34600010销送46958忌费用4.3运帕里炳地Bl徜地B2情地B3靖地Bd产量产地U00404产地A29016025产地A311001526卖际销量10102015梢量10102015总我用202I4.4(1)3BiBiBtBjB.Bi产量A11515AlIO515A2OO15IO25A2515525AA5AJ5tfiS:51515IO销fit51515IO4.5增加一个假想销地B4.得最优圜运方案如下去.地Z=ifeBiBjBjB.产吊CuQ2Ci)4A88Aj527Aj4O04恺盘48524.6解:产销平衡变为123虚产最040801

23、2002150054058002570610650032M600640042M670710023MM5500I3MM62003、地产后、B1B3B3B4B5产量A150IO60A150202090As3020旬A45050As5050销累5050508070总运贽为：Z=CuXu+cv125+caX2j+CMXj4=2404.9解:运辎问题的产地与错地也可看作发地与收地,该问即可构各季度的生产能力看作是相应发点的发货用：同样把按合同交付柴油机的四个季度的数成行作是收货点的收货fit这样总发货量:为：25+35+30+IO=I（X）（台），总收货破为：10+15+25+20=70（台）。于是该问

24、题就可以看作是一个产大于铺的运输问题,弓I进康设收货点D,其收货冢:为30（台）,即化为产销平衡问题,这时单位运价可取作;Ch=第i季度每台柴油机的生产成本+（j-i）个季度每台柴油机的存贮费（ji）.如：C2=10.80+（2-l）O.I5=10.95；Cn=IO.80+（3-l）0.15=11.10,当ji时，实际上i季度生产的柒油机不可能在j季度销日，所以这时将费用记为M（任意大正数）；各发点到虚设收点D的单位运价均为0.干是单位运价表和经用表上作业法求解,科多个最忧方案之一如下去.3.9单位运价衰（台）Q）最优,运方案发I234D发累巡I234D发mI10.810.9511.1011.

25、2502511015025IlMI1.lO11.2511.40035Il53035IllMM11.0()11.15030Ill25530IvMMM11.30010IV1010收量1015252030收量IO15252030即第一季度生产25台，IO台当季度交货,IO台2季度交货,S台3季度交货：第二季友生产5台,当季度交货：第三季度生产30台。20台当季度交货,10台4季度交货：第四季度生产IO台，于当季度交货.按此方案生产，该厂消髭的生产与存贮总费用最少为773万元。4.10运价衣如表466,BI的需求为30b口O,的需求为40,Ba的需求为2Obj6O,Al不可达B,B,的需求为30.求目

26、标函数最小ft.衣4-66习时4.0运价表B1B2B)B,供给贵A497-70A2653220Ai859IO50解：先化为平衡我B11BijBaBmBWB45Ai44977M70An66533220A588599IO50M0MM0M403020402040301805.1(I)X,5.2X=(5.,(IO.3)-s2.75,3)TMaxf=26,755.3(I)X=(4.3)Maxf=55X(3)X=5.4X=(0,5.5(1)(20,I.6)MaXf=361.I.I)Maxf=6;=(2,I)Maxf=13X=(2,3)TMaXf=34地优解:OOOOOO最少完工时间为48X.rHW1.甲做

27、C,乙做6,fttA.79101271312161712151614151411121516IlMinf=215.641()764631O30OolO100O000甲IttC乙iA,丙做B,丁做D,最少完工时间为15,xs+.v6+X7+x2.IOmin=ZX/-IM=I.r7+.rt=I所以该问题的数学模型为:Xy+X,IXj=O或I(7=1.2.-10)XABCDE甲2529314237(2的初始效率矩阵如下:XABCDE2529314237乙3938262033丙3427284032T2442362345D2427262032采用匈牙利法求解后得：(I)甲一B，乙一D，丙一E,丁一A,C

28、放弃，最少时间为105小时。(2)甲一B,乙一C和D,丙一E,T-A,最少时间为131小时.5.935450()35450067680067680089810008981000化极小10IO9Il00IOIO9Il001211IO1200I12IlIO12001312Il13001312Il1300之后用匈牙利法求解得X：6=X；S=Xi=-v,-I=KI=11其余为。最大受益43.5.10设A.B、JD设备分别生产产品的数皱为MXj.X1.=I选择矽设备“=1()不边择海设缶minz=20.0+1OOOyl+24j+920v2+16x,800y,+28,rl+700yjXI9(X).vlX2

29、I(XX)V2.I2(X)va41600*.r1+x2+.V3.V4=2000H=OjJ=123,4与0三1.2.3.4习题6)俨minz三Pldl%d1f2*)P3d2xlr211()r-x2f-l*0传)x12x24f-4/三IO(c)Kx1IOx2ff-4-56d)xpx,0(-1.23)满意斛是戕段GD上任直点，其中G点X=(2.4).D,X=(IO,3IW3)T6.2(1)满意解为(“与)=吟，畀)其氽变成为偏差向SU=(0。5)(2)满意解为(内.心,；，；)=(6030,10,15),其余变，为0.偏差向量=(0.0.45.10)Min/=S.I.PtdlP2+Pjd)*Pi(A

30、*+s+*+4+4)500I+650U+SOOxs十八=1.6x106x+8x2+lx3+-/：*=200d2+d3.=24X1J-Z*=12X2+A-0(j=h2,3)力“0=l,2,3,6)6.4 (1)(3)(6)(7)(8(9)6.6 解：1)建模为minf=Pl(d/J)JlPi(O,Jz,J1O(/=1,23)2)单纯形求解:CBGXbBlb0Xl0X2P:dPi11*Pi出Pi必0Ch-PiPid1301-10000Ps人201001-1000d4I100001-1Pl000-10-100P：100-10000P101000-10-IX13101-10000di201001-100di10-11001-1Pl000-10000P100-100-100P10100000-1Xl3101-10000d2-1001-11-1-11X2101-11001-IPl000-