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

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.<.v1+4,+2x>8(2>5xi+3x2+xj=103.0+2x6x.t.-5xl+.r,-10x15j,x,x50xi>OJ=1.2.3(1)鹳法一:大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-MCBX»B,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-4+6=8SJA3.v1+2.r,-xi+x7=6.VpJ2tXrX41X51X6tXT0最优单纯形表如KC1.00000-I-IC8XbBlhXiX：XX×4XSX?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的检验数=«.所以此线性规划同跑有无穷多最优解.(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)-Z<j>10-51000*BigM531000Xl10I'51501/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=15xjO.y=,2,5C(j)OOOIR.H.S.RatioB<sisQi)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，aj<O.a<0,(2)线性规划向遨行多重最优解是当某个非基变她的检5金数为0所以ajO.a5=O.a<0或ajO.asO&=0,a>0(3)现行解为退化恭本以优解的条件是地变此中含有零分疑，且所有的检验数均#仅，所以asO.OfiWO1.1 a20.现行解为可行情.>0.a4O0r.该线性规划目标函数无界.因此参数范围地a*0.36>0.a4O(5)当al>O,如<0时，该战性规划何胭的第一个等式约束为矛盾方程，因而无可行解。2.8 已知晚性规划同胚!的初始单纯形表和刖单纯形我迭代后得到的表2-27如下，试求1.的值，表2-27初始单纯形表和用单纯形衣迭代后得到的表XiX2«3X4X5*46bC(110*5IT3C0IG-4a12OOa>a>aIXi/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，种产品附件产品利润如表产品资源甲乙丙资源限JltHH(kg)1.51.242500设备台时）31.61.21400利润（元/件）101412根据市场蠹求，预测种产M最低月需求量分别是150、260和最祖J荒求是250、310和130,试建立该问题的数学模型,使每月利润最大。解：设即.处、的分别为产品甲、乙、丙的产量,则数学模型为maxZ=10.vl÷14x21Zql.5x1+l.2x,+4x125003x1+1.6x,+1.2x1400I5025O½6O231O12O13Oi.x02.10 某糖果厂用原料A.B.C加工成三种不同牌号的轴果甲、乙、丙。己知各种牌号釉果中A.B.C的含量,原料成本,各种原料每月的限制用量,三种牌号相果的单位加工费及件价如表2-29所示.何该厂每月生产这三种牌号糖果各多少kg使得到的利润为最大？试建立这个何区的线性规划数学模型.衣2-29三种号融果的单位加工费及竹价甲乙丙原料成本玩/kg每月限用勒kgA>60%>20%2.(X)200()B1.502500C<20%50%60%1.OO1200加工物后kg0.500.400.30售价，元/kg3.402.852.25解：i殳与为生产第j种糖果耗用的第i种原料的数也则一：种柚果的生产状分别为:X=X+X2+XJ;XC=Xl2+X22+Xn:XX=XU+Xzi+XDmax:=(5.40-0.54)Kxl+xj,+t)÷(2.K5-O.4O)(xlj+x+m)+(2.25-O.3O)U11+n+xn>-2.O(ll+1j+u)-I.5O(ji+x2+2J-I.<Xji+u+xm)xl÷X12.v1j52000Xn+.tn+xn25xu÷m+u4IKKJx0.6(x,1t21Xj1).X£0.2(*“十X，),203(,j+m+m)*2$(*12*S+1心)XBS<).6<X"+*%),'("1.2E23)2.11 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架，两种窗架所需材料烧格及数量如表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.40.8第二步：建立线性规划数学模型设均(尸1.2.，14为笫j种方案使用原材料的根It则(I)用料最少数学模型为14minZ=£x,M2xl+x,+X,+x4300X2+3.rj+2x6+2.0+Xlj+.7+.%)450<X3+.*+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余科最少数学模型为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根X'2,=(0,450.0,0,0,0,0,0,0.0.0,200.0.0)Z=0，用料650根显然用料最少的方案也优.习题31.2 判断对错.并说明为什么.(1)任何线性规划同应存在并具有唯一的对偶问即，(2)根据对钩间题的性质，行原何明为无界解时，其对偶问题无可行解；反之，当对仍问题无可行耨时.其晾问时具有无界解.(3若跳性规划的原同咫有多也最优解.则其对例问JS也一定具有多盅最优解.(4)则恒有：设x.y分别为标准形式的原问捌与对偶问题的可行解,f.y*分别为其最优解.si<c=X,<biyiy-j/-ui/-(5)己知,为跷性规划的对偶问遨的最优解，若)厂0,说明在城优生产计划中,第i种资源已完全耗尽。(6)若某种资源的影子价格等于k,在其它条件不变的情况卜，当该种资源增加5个单位时.相应的目标的数侪将增大5k.(7)互为对隅的问应中，原问四一定是求设大伯的税性规划问Sfi.(8对偶单纯形法是直接解对偶问题的一种方法。(9)线性规划灵敏度分析的主要功能是分析城性规划参数变化而破优解的影响.(10)若线性规划问题最优基中某个基变Ia的目标系数发生变化,则所有非基变量的枪胎数发生变化.解：2.6.7.8×其余J1.3 求出卜列然性规划的对偶规划Imax57.fxl+2.V,+3.r,-÷4x4-.v1+x,-+3.0=56.vl+Ix2+3x5-5x1>8min=3M+5.0÷x1I2xl-9-9x,+9.xl.i0.xj<0<20SJ.-.v1+3.v2+6x,82xl+x2-X34i.v2,Xj0QUIlmin=C/-/-maxf=Cx÷Eys.t.Av+Fy=bAv+Fybx0sJ.4%-B%"zzee.V,>O.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=8vl+4y2(2)SJ.-v+2v233y1+.y256yl-y2ly.y2minw=mb+nb"n+n'C(3) 1.i1.SJ.<mF+nF=En>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.r2>0minz=x+x2X1+2x2+xi>4sJ.2.vl-xi+3x,>7x.x,.x30呆优研：X,=(0.0.4.0.5)r目标函数批优值03.4Wi(D对偶问题为:minh三8>i+4y2y,+3y,42yl-2y,2->1+2v,3y.y2o将x=5.V2=4带入约束条件的为严格不等式，由互不松弛性得最优解：X=(O,IO.I2)目标函数最优值：/=283.5minW=8y1+6y2+6y,+9y4y+2y2+9y,2s/(2>f=(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因而嫉优解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 解最优解为：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)按从初始表为最终表的迭代电序,从最终表反推回去即得初始表.如下Xl×2X4XsX450I2I0XS103-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-53<r215,此时原生优基不变.3.9 (1)解：令X4,求最优解(目标函数化为求极大>XlX2X3X4Xs21012»X252I03ci-zt1003X411/201/2IX221/21-3/20Cj-Zj-1/20-3/2020时，CHBr(p,.pj>-<C,C3>=(-2,-l)fk21/2I-<-l.>=(1/2-,32-2)11/2-32j最终表如下：XiX2XjX4X411/2*01/2iX221/2I-3/20Cj-Zj-202-320l2-0<ffh2-2O得04入0/2此时上表为最优表.minz=2+20X>l2时，表I中刈的检验数首先变为负数，故迭代得下表Xi×2XtX4Xi210142X2I01-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解：目标函数化为求极大.先求出入川时的数优解,为简便用对照单纯形法,即XiX2X3X4Xi2I0-2-IX：-10I-PIQZ100-5-IXi4XjII0-2-10I-3G-ZJ0-50-6最终表变为Xi×2XX4OWWl时为业优表Xi4-31一20一3minz=-5*6×3I0-rI-IGN0-50-6XlX2×3X4xsXi2+日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.maxz(«)=36÷W(2)作图如下3.12W：设该厂每天生产原稿纸Xi捆，11记本X2打，练习本X、箱，又加人表示该厂招收的格时工数，则本例可列出如卜的参数线性规划模型：inaxz(2)=.v+2x2+3.v,-15z3-xl+13-.v,+26-.ri30000333.vf30-V,+-a100+3030'xy0,(y=1.2.3)（八）当入=0时求解得JR终单纯形衣如NXiX2XaX4X5X220107/31/10-10XI100001-4/3-1/1040G-Zj00131/10-20即该厂呆优生产计划为生产原稿纸100O捆,日记本2000打，可盈利5000元/天。(B)从上表中看出劳动力的影子价格为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=5<KX>7.当3200时，盈利为z=9000-5A.z()前参数人变化如右图.0200200习题44.1(3)(5)<7><8)(IO>J其余X4.2运S邕BlB2B3B4B5产量产地Al0005510产地A20090312产地A34600010销送46958忌费用4.3运帕里炳地Bl徜地B2情地B3靖地Bd产量产地U00404产地A29016025产地A311001526卖际销量10102015梢量10102015总我用202I4.4(1)3<c2,10(2)c,4=17运表I运表2tplfe产£BB>BiBiBtBjB.>Bi产量A11515AlIO515A2OO15IO25A2515525AA5AJ5tfiS:51515IO销fit51515IO4.5增加一个假想销地B4.得最优圜运方案如下去.地Z=ifeBiBjBjB.产吊CuQ»2Ci)4A88Aj527Aj4O04恺盘48524.6解:产销平衡变为123虚产最0408012002150054058002570610650032M600640042'M670710023MM5500I3'MM62003、地产后、B1B3B3B4B5产量A150IO60A150202090As3020旬A45050As5050销累5050508070总运贽为：Z=CuXu+cv125+caX2j+CMXj4=2404.9解:运辎问题的产地与错地也可看作发地与收地,该问即可构各季度的生产能力看作是相应发点的发货用：同样把按合同交付柴油机的四个季度的数成行作是收货点的收货fit这样总发货量:为：25+35+30+IO=I（X）（台），总收货破为：10+15+25+20=70（台）。于是该问题就可以看作是一个产大于铺的运输问题,弓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,当j<i时，实际上i季度生产的柒油机不可能在j季度销日，所以这时将费用记为M（任意大正数）；各发点到虚设收点D的单位运价均为0.干是单位运价表和经用表上作业法求解,科多个最忧方案之一如下去.3.9单位运价衰（台）Q）最优,运方案发I234D发累巡I234D发mI10.810.9511.1011.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.求目标函数最小ft.衣4-66习时4.0运价表B1B2B)B,供给贵A497-70A2653220Ai859IO50解：先化为平衡我B11BijBaBmBWB45Ai44977M70An66533220A588599IO50M0MM0M403020402040301805.1(I)X,5.2X=(5.<2>×,(IO>×.<3)-<9>s2.75,3)TMaxf=26,755.3(I)X=(4.3)Maxf=55<2>X(3)X=5.4X=(0,5.5(1)(20,I.6)MaXf=36<4>1.I.I)Maxf=6;=(2,I)Maxf=13X=(2,3)TMaXf=34地优解:OOOOOO最少完工时间为48«X.rHW1».甲做C,乙做6,fttA.79101271312161712151614151411121516IlMinf=215.641()764631O30OolO'100O000甲IttC乙iA,丙做B,丁做D,最少完工时间为15,<001.5.7W：改Kj=I或0,分别代表选择第Sj个井位或不选第Sj个井位.则：(I)Xl+Xr=1：X7+x=1(2)X1+xsISX4+Xs1(3>xs+.v6+X7+x2.IOmin=ZX/-IM÷=I.r7+.rt=I所以该问题的数学模型为:Xy+X,IXj=O或I(7=1.2.-10)XABCDE甲2529314237<1)乙3938262033丙3427284032T2442362345D0000M5,8(1>(2>的初始效率矩阵如下:XABCDE2529314237乙3938262033丙3427284032T2442362345D2427262032采用匈牙利法求解后得：(I)甲一B，乙一D，丙一E,丁一A,C放弃，最少时间为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).vlX2I(XX)V2.I2(X)va41600*.r1+x2+.V3÷.V4=2000H=OjJ=123,4与0三1.2.3.4习题6<)俨minz三Pldl÷%d1÷<f2*)÷P3d2xl÷r211()r-x2÷<f-<l*0传)x1÷2x24f-4/三IO(c)Kx1÷IOx2÷<ff-4-56<d)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.Ptdl÷P2<>+Pjd)*÷Pi(<A÷*+<s+*+<4+4')500I+650U+SOOxs十八=1.6x10'6x+8x2+lx3+-</：*=200d2'+d3".=24X1÷J-<Z*=12X2+<A-<A4=10X3+4_4=6>0(j=h2,3)力“0=l,2,3,6)6.4 (1)(3)(6)(7)(8>(9)<10)(2)(4)(5)×6.5 解：11inZ=PId+PdiIO.r16+dJ=200Ilxl+3X225$"lx÷5O.r2+J2-J2*=1900x.t2O.rff'.rf0(=1.2>6.6 解：1)建模为minf=Pl(d/÷J)÷>Jl"÷Pi(<+”)SJ.xl+一”=3三十"2-2xl÷x2÷dj-dC=4i,>O,Jz,J1O(/=1,23)2)单纯形求解:CBGXbBlb0Xl0X2P:dPi<11*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-