《运筹学基础(第二版).pdf》由会员分享，可在线阅读，更多相关《运筹学基础(第二版).pdf（207页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学基础（第二版）张 莹 编 著清 华 大 学 出 版 社北京绪论第一部分线性规划第1章线性规划的基本性质1.1线性规划的数学模型表1.1.1生产计划问题设 备每吨产品的加1:台时总有限台时甲乙A3436B5440C987 6利润（元/t）3230求ma x目标函数 m ax之=32/1+30/2约束条件 3/1+4 5&36 ,1 1:_9Hl+8处&7 6/1 2 0,72二0表1.1.2产销平衡的运输问题运价（元/t）销售后（t）氏 二3Bt=4氏=5氏=8At =5411310Aj =71928Aj 874105min z=4z ii,1 1J-I2-3J I3 4-10j ru r
2、 x2i *9J-22一:2X23 4 8J-24 t 7J-31 -4J-32 -1033 V 5 a-34N i l +孙+工14=5 十 工22+72 3+7 2 4 =7+工32+7”+=8 in r-N21+J31=3T12+XU+J32=4 I S +工 23+工33=5-T U 4 工2+工34=8X ij 0 (z =1.2,3；，=1.2.3.4)min z=CiX j +C2JC2+j r.a i -a 2，-=仇。217 1 a222 十 aznJ CH=bza ml-fl-aMx2 4-4 2“=bmJ-1，工2 20min z=CjJCjj=i&产/=hi(i=1,2
3、,7)尸iJr,0(j=1,2,，)min z=exn：P产 j=bj=lx二0 min z=exAx=b0(1.1.1)图 I 将目标函数化为标准型max(/(.r)1.2图解法max z=2/i-372J-J-2H2&84a-j&16工1 二 072 2 0(1.2.1)(1.2.2)(1.2.3)(1.2.4)图 1 2 1 线性规划的图解法(1.2.5)(1.2.6)(1.2.7)(1.2.8)ma x?=J*I-x2工1 一 2JC2 0 x =Z)+(l_ Q x (0 1)Ax=AL/2XU)4(1/z)xt2)=/M x+A xs=b b pb=bo,-o(o q&i)X=/J
4、X1(1 7Z)X 0X Rx=ay,(1 a)z O V a V l(1.3.4)m。,力=b(1.3.5)j=l p产 j=b (1.3.6)，二iK:PjXj=b(1.3.7)KyPiOj=0(L 3.8)，=iK(a T 网)=b(1.3.9)j=iK PJ(j：j paj)=b(1.3.10)y=L(X i 4。1)，(12/。2)(/K /aQ，o,o,，CO N =(4 a i),(j*2幺。2)，(1K /Q K),0,0,，01T(1.3.11)(1.3.12)第2章 单 纯 形 法2.1单纯形法原理min 2=5+3/2+8 4JT 1 N32 2xz+2JT325J r,
5、2。(j =1,2,3)Nl 4 X3-JCK-2J7 2 +213 -25=5石 0 (j=1,2,3)附加变 量 人2 0，z。min z=4xi 4 3 5 +8JT3 4 Ojr -0/5/+4 1,+上=2 (2.1.1)x2+2 4一/+孙=5(2.1.2)工,20(j=1,2,，5)人工变量420，力 0min z=4%i 3JC2+8JT3 t 0 xi+0JT5+M r6 +(2.1 3)JT6=2 Xi x3+Jr 4 (2.1.4)Jc=5 a*2-2才3 +(2 1 5)H=(4 M)J*I -(3 M)X2+(8-3M).J+M r4+A li5+7 M 2,1.6)
6、4 =2jr?=5z=7MPl-Fl-P2JC 2 4 +Pmm=(2.1.7)PlPi Pr Pm PE+1 Pk,P”b10 0 0 ai.m+1 alt aln/01 0 0 a2,m+i-a2*a2 bz00 1 0 artm+i&E br00 0 1 a m am bmPk=P1IA p2a2 4 -P/k +-P/M (2.1.8)JPi(Xi-0a u)p2(Jr2-4-p,(/.一 )p(jrm Ja熹)(2.1.9)8=0a ri a ik表 2.1.1 确定换出变量基变址工1“246N?b比值101010220120-10155TJC3=2 一 父1 +七一4 (2.1.1
7、0)x-t=5-x2-2JT3+“5 =1 ，2xi N 2-2X4+/5+2JC6(2.1.11)4=2石=1z=M+16Nl+Ns 一/4+/6=2(2.1.12)2/i+JC2+Ns-24 4-x7=1(2.1.13)表2.1.2 换入列只有一个正元素威变量叫4isJTib比值n101-10102-2102-1-211T4=孔=/5 =4 =7 =0Z 2=14=2min z =192.2单纯形法的表格形式min z =4=1N i a i.H i/m+i -ai nxn=b i7 22 41/府+1,a2 nxn=b2e 一 E E+i/m+i /上20(k =1,2,，)n4=b i
8、 耳(？=1.2,，?)(2.2.1)j=wH-lHEX2=X cixi(2.2.2)k=1 t=1 j=m-l-1+V Cj-xi=a+(ci zi)x=+X axi=l/=m+l i=l f j=m4-l j=4-l表2.2.1单纯形法的表格形式o43800MM迭代次数(CB)T基变7i iJC l1aJC iXs皿b比值0ATM-x*171001r2-100T1001252=e5T5I M3-M8 3MMM00一 7M1工 3171-20110-12,0-11-20121，2M 4M08 2MM3M 80M-1628_ o_1340-11T2/T10011T-T0-1TT5TT1-i00
9、iA!M 42。3qXi1-20i10-120-11-20121520023M 2M-3-1 9第 行=第 行/主 元 素第 行=第 行 2 X第行第 行=第 行 一（8 3 M）X第行ati *Oik(i r)-Jark(j：=r)l a rkb仇 (i/r)drk (t =r)a rk2.3大M法和两阶段法min 之=4 +N i+A -4 +/6=24 +2JC3-%5 +JC7=5jC j0 (j=1,2,，7)S 2.3.1两阶段法的第一阶段000000110迭代次数1，：XiXiq.小x4x7b比值0A51001r2一100-11001252=8525一1-310071Xix?1-
10、20110-12*0-11-2012152-1t-2130-1续衰o000001-2O-_ o _工30-1T1Ti001TT0-11T1T%00000110表2.3.2两阶段法第二阶段的初始表438000迭代次数(0 (j=1,2,.7)b(e)=b+Pjmin z=ex0表2.4.I唯一确定换出变星00003T20T60迭代次数B)TJiIt八JCt八x?b比值J：100T-8-19000。0101-1 22300L o J001001015000T3一602.5改进单纯形法A=(B,N)X=xB8 =(P1 血，P 3N=5+10+2，出)二 J+iBXS+NXN=b(2.5.1)XB0
11、,XN)0min s=CBXB-CN XN(2.5.2)B BXB B-*NXN=B-lbXb=jf-b Z J T NX N2=CBXB+CN*N=cB(B-1&Iff NxQ-cN xN=cbB-lb+(cN C3B-1N)XN=So+NXN(2.5.3)(2.5.4)。二d+D =珠+。产，N+1B?+i=,B71=(ei.e?，e 1，W,，e Q B L(2.5.5)8二=E h EiE0(2.5.6)工1+A 一工4+工6=2JC i+2JC3-4 +N7 =5X j2 0 (j=1,2,7)min w =4*,3J-2+8J3 Mx6+Mr?(pf，pP，pS L pf，p,p)
12、，pS )r i o 1 10 1 01LO 1 201 0 1Jbw=B3=(p悭.p/)rio iL01Jlf-=r io i1J内”=）（P，p/，P,，P；,pV）1 1(4,3,8.0.0)-(M,M)r i oonLO 1201J(4 M 1 3-M 8-3M.M,M)（&。9产，另 9严，层 ）B i（P抖，P尹）r ionrio1onr iL2101JLOL21Jo11 oq2 1J1-2o-1JB?=1 01_ 一 2 1 -?*p/=r ioi,-1 0111oq12L-2 1OJ.-21JB7=1 01L-2 1Jr 1 oqB 1 I=Ec UQ 1=Eg=(S ,e2
13、)=L2 1 Jbay=B 7.b(n=_ 201C21 r21-b 1-r 1y。)=c yM=(ci，a，q.q y)y(1(Pio)，P2O.pl0).ps0)p0)ri o-1 o iq=(4.3,0.0,M)-(8-2M,M)Lo 1 o-1 oJ=(2 M-4,3-M,8-2M.M.3M-8)叱姆 =一 21 01 2i-K 1 1 _21 _2010 4一】72b=8”b=2522y=南,匹i=(c3,c4)B7l=(8,0)=(0.4)71 1措=*产M =(cg)-y(p；).p/，p/.p/.p严)=(4,3,0 M.M)(0,4)=(4 1.4.M.A1 4)一 f X2
14、)X2(2)(2)(2)-u i，02*0 5 *0 6 ，。7)P 产=BT1 p y =第3章线性规划的对偶原理3.1线性规划的对偶问题max z=32/1 30/23/i+4 4&365ii+4/2&409/1-8才2&76 0 2 0，max z=exA x&bx 2Q-35_94一48.一36一40.76.b=c=(32,30)min w=36yl+40y2 +76y33“+5y2+9y3 =324yl 十 4 y2 +8g 30y i20,22 g20y=（y i，%，1y3）min w=yby AcI mm z=exAx b4 二0(3.1.1)X=(3.1.2)(mm z=ex
15、Ax=bI二0 max w=yb(3.1.3)(3.1.4)y是自由变量min z=exA x 2bAx&bx二 0min z=ex-A r&nX-A L-b-x二 0-b-max w=(y i，刈)-b-A-(力，山)0max w=(ji y2)ft(力-M)A&c月 2以 2。max w 二yA b(3.2.1)匕 力 01 max w=vbvA&c(3.2.2)Uomin(w)J=max w-w=jm in(-w)=-ybJ-yA -c (3.2.3)ofmax(v)=exJ-Ax&-b(3.2.4)omax(v)=min vv=cxmin v=min zj min=ex)Ax b(3.
16、2.5)L 2 ojAx(0 cm Ax。)*。cx W b 1 oqC3B-1=(c3,C i)B-1=(8.3)=(2,3)L-2 1JcxA r(0严 Axy bcx=ywAxw=严 b(3.2.6)(c-/0)A)x(0)=0(3.2.7)yo(Ax-b)=0(3.2.8)(c y-:p,)xj0=0(J=1,2.，)y严(A/*6,)=0 (=1.2,?)(yw pj q)x0)=0(3.2.9)W(A,x 4)=0y b=yjl A XI J1(3.2.10)cxi0)，bex =ywb=5”6】+y严 仇+心产=2三.3。,dbi y ia之dh2M%一酝3.3对偶单纯形法工1
17、+4一=2x2+2 4一4=5%0 O=1，2,，5)min z 4/i,3J C2+8J73工1 .r3-N=-2一 -2J T3+%=-5jC j 0 (j=1,2,.5)min c=4/i+8不表3.3.1对偶单纯形法438000迭代次数(CB)T基变量o ri12xaX 4X 5bri八-10-110一20L o JJTi0-r-201-5%438000ri 0cr；=Omin z=-211+2JC2J*I-5+428Ji+2xz+2J3&6Z j O (J=1.2,3)min z=-2xi+2J2工1 +5+八 一 工”=871+2JC2+2JC3+a =6j j0(J=1,2,3,
18、4,5)min z=-2jj+2J:2一工1 4J72-工3 +工 0 (j=1,2,3.4,5,6)表 3.3.2 扩充问题0-2200000迭代次数T 基变量XinIs4hT-4-1100-8H-12201060L o J x.r11001M5-2200000_ 01.r40-30101M-800110116 M1-2 X|111001M50420022M 0 1 .r40一21110-2 -rt0-1-10-11M-6L_2j Ni12201065064020122 1 处011TT0130 400_3_-T-T3T1M 51_-2 亚1031204500735064-10min z 6
19、3.4灵敏度分析XBblXN-min z=CBB1 b肾卜 口 信2&2表3.4.1改变价值向量cci43500MM0迭代，、T 廿+皿（6）基变量次数力支为工$r 0(i=1,2,?J)max/一d ir 0 J&A6r&m in|卢 d iri I dir.1 -I dir-Blb c3B-iy.-,-表3.4.2改变限定向量方43800MM0迭代次数（CB）T基变量X jxar4“84x?右端列-8-X3101-101043.3.1X i-2*102-1-21一 6620023M-2M 3-1 48X i01T10T01T14110-1i13222601042M -4M-2-2 0X尸1
20、 w b+lAm+i x -i：bm+iAE+1=（*+1.1，an+1.2，-a n i+l.”）x =（J-J,J-2,-r,）T（3.4.3）（AIH+1）B*B （Ag+i）NXN-J*+!n xN=omin z=4耳 3J-2 T 8JT3+42212 +2 452NS&3 0 (j=1,2,3)表 3.4.3 增加一个新约束条件U)943800MM00迭代次数(C,B)T基变量工i为*Is丸方Xsb3flX工，i-210101-12-10-21010021Jt002000013520023M 2M-30-1 9二T23T.min =20表3.4.4增加一个新约束条件（2）04 38
21、 OOM MOO迭代次数(CB)Tx t x t q 1 4 x s x t x?Jrt b4nnX i41 810 1-10 10 0 2-2102-1-2101-2*0 0 2 0-2 0 1 -13LVJ62 0 0 2 3 M-2 M-3 0-1 95112J i001 0000-0 10 0-101-1210 01010-十 -y50 0 0 4 3 M-4 M-3 1 -2 0q +1 C|r+1 C 3 B PH+1 1 02i r 2-ip；=B p,=-2 1L 1L-3-r 2-3=Q cbBl pg=6 (8.3)=-T 3-亚=4=1 J C1=J C3=JC =工6=
22、0min 之=18表3.45增加一个新变量43800MM60迭代次数(cB)T基变量Xtn.r4Xs-r 0=l，2，力i=lX ij2 0 (i=1,2,，；j=1,2,E fW ,W H /C T vXa-=x(苍)=t=l i=l j=l f j=l i=l,n)K=j=lNml 7m 2 m行1 1-11、1.、行1，4.2 套裁下料问题表&2.1套裁下料问题下料数（根；案123452.9120102.1002211.53：203合计7.47.27.16.6料头00.20.30.8min j =O/i-0.lj r2 0.2JC3-0.3J T4-0.8J TSJ C i+2/2 f
23、)1002J T3+2J：4+41003/i+/a +2J T3 3 4 100X i 2 0且为整数(j=1,2,，5)4.3 汽油混合问题表&3.1四种标准汽油标 准 汽 油辛 烷 数蒸汽压力（g/cm2）库存量（L）1107.57.11X10-1380 00029 3.011.38X10-1265 200387.05.69 X10-2408 1004108.028.45 X1O-1130 100表&3 2两种飞机汽油飞 机 汽 油辛 烷 数蒸汽压力（g/c m D产量需求（L）1不小于9 1不大于9.9 6X10T越多越好2不小于100不大于9.9 6X10-2不少于25 0 000 l
24、g/cm2 981%.ma x z =J：I 十 工2十 七 十 44 +4 +/7+42250 0004 +4&380 000&265 2004 +i7&408 1004 +18 4 130 100与 0 (j=1,2,，8)7.11 X IO-孙 +1L38 X IO-皿 +5.69 X IO-1a+28.45 X lOT,/72+4 +47.114+11.38/2+5 69/3+28.45JC4 一.八八公-=-4 9.96才1十 彳2十 3十 二42.857i-L 42期 十 4.27JT3 18.4 9/4二 02.854 1.4 2 4；4.27必一18.49x80107.5/i+
25、93,2+87-1084、+/2+4 +彳416.5/1-2.022 4.033；17.0工4 07.5JT5-7.0/6 13.0亚 +8,Oq 0max z=JCi JC2+jr3 4-jr44+4+4+/8 2 2 5 0 000115&380 000JCZ,4&265 200j：3jN?&408 100JF4 4 18&130 1002.85/1 1.42必+4.27丁3 18.4902.854 一 1.42八+4.27以 一18.4 9/8 2。16.5/i 2.0/2 4.0a3-17.0/,2 07.5JC5 7.0/6-13.OJT+8.0/820与 0 (j=l,2,.8)4
26、.4购买汽车问题max z=2100Aj+4200A2+6300A3+3600/3!+72O O B2+10 800B3+378O Q-7560C2+ll 340c310 000(A1+A2+A 3)+20 000(Bi+B2+B3)+23 00 0(+C2+C3)600 000Ai Ai A3 Bi-B2 B3 f-Ci,C2 f C3 3 0Ai+2A2 +3As+2Bj+lB2+6B,+2G+4C2 4-6C3 0.B,0.C,20 且 为整数d =1.2,3)4.5产品加工问题表&5 1产品加工问题设 备产品的单件匚时设备的有效台时满负荷时的设备费用（元）1 1 11 0A510600
27、0300A2791210 000321氏684000250耳4117000783心74000200原料单价（元/件）0.250.350.50销售单价（元/件）1.252.002.805(工1 1 工/1 2 .13)10/2160007(N14+315 1116)9/22 12/31&10 0006(/11+/14)+8(JT2I 9 2 2)40004(/12/1 5)+11/31 W70007(/13+心6)&4000所有变量 0且为整数利 润=(销售单价 原料单价)该产品件数1=15V(每台时的设备费用 该设备实际使用的总台时)=1max z=(1.25 0.25)(j-n r 工 +工
28、1 3 +7”+7 16)4-(2.0 0 0.35)(721+工22)+(2.8 0 0.50)41一 哥 5 5 1 J-12 卜 工13)-10/21O vvv-7(xu+X1S+9工2 2 +12311 v vvU一 就6(1+7“)+8(工2 1 +才22)1-14(712+工15+11工”一 默17(5/1+10jr5(60007J:2+9%+1 2必 10 0006 4 +8(Js+/6)&40004J*4 +11/7 W 70007(71+Xi 4&4000巧2 0且为整数。=1,2,，7)max N=(1.25 0.25)(1 1+辽2)+(2.00 0.3 5)(%+4)十
29、 (2.80 0.5)X7 高y(十 10工$)一湍5(7支+阳+,)-箴回+8(%+工力一 藕(4工，+11不)一瑞 U (为+x2-x3-)4.6投资计划问题Nil 一 口1 2 =3.0112&2.0/21+-2*2 3 1.2/11=0.0工2 3 1.5131+1“1.5/12 1.2J:21=0.0/3 4 W 1.0max 之 =L 6JT23+1.2JT31+1.41Nii+E12=3 0112&2.0Xu 4 JT2 3 1.2XH=0.0-Z 2 3 0 (i=l,2,3；/=1.2,3.4)4.7企业年度生产计划问题S 4.7.2设新增设备的容量为决策变量设备种类梳纱机粗
30、纱机1 .络筒机德线机摇纱机浆纱机窄幅织机宽幅织机变量?,巧 一 W=耳工父 D j S Jh)D(j e Jh)力。用 一 ,“&出 Ti(i=l,2,，9)9W Li=lM&Q,(i=1,2,.9)23：*一 ZE&Ej=i工 业 一,Ihjj：j&0 (k=1,23,4)4 R 1 J%Z jy,O (i=1.2,.9)-TE 0jjtR 0(k=1,2.3,4)23 9 4max?=X P产i-F b g c J：E P*-I*R=1 i=l k=lP=TT7B+(TTOB -(-1-+-/-)-BH心i =1(TT7F,+(TT7r1(1+0)1 q1P=B J -(1 +)口(i+
31、o-1寅 1+i)-B=PMl+力”(1 i-/)-!B i(14-i)F=23 9 4max z=、Pj工j F,X 收 c*xE+P”5Rj=l i=l i=lxi x，i=HjD(j G Jh)事 5 (j&J.23=iN*R2尸 与j&0 (k=1.2,3,4)*4R 3巧&(A=1,2,3.4)UmX j2 0 (j=1,2,，23)x-0 (j J h)yi 0(i=1,2,，9)N E20/上R 0(6=1,2,3,4)4.8企业年度生产计划的按月分配问题mR，孙m a x z =1 T-班t 1T S I=7 81 =0n(i=1,2,?)j =la：j i W dj(j =1
32、,2 ,，)jC ji2 0 (j=1,2,，)m n尸_m aix=1 zj =_ l_ _ _ _ _-i =l 1 5 2 =82 =0I”=4 一n)2%/篦&仇2 (i =1,2,，7)=iJC握 0(j=1,2,，)4.9合金添加的优化问题尻.员，kS 4.9.I 种铁合金材料合 金金中各兀 素合 金1合金2 合金”元 素1dnde,dg元索2dndm dg元素md.i m 2 k合金单价fi 4m in z=e iii e2x2-e1tzltf _ b itt，.d w i -dnXz d injcn2 ,w+JCI+jc2+jr,/_ L5.U J I L xn(dll-f l
33、)X1 4(di2 一 f i)l2+(di.f i)工.=(f l bl)w(d?i 人)/1 +(出2 丘)4 ；,(d2n 人)二=(无 一 仇)w/八 、(4.9.1)(HeI-/m)X1 t-(dm2/m)l2 二 十(NEK/m)=(/M bm)ivft：(d亏=(f i b i )w (4.9.2)j=i*&f&q (，=1,2,，z)(4.9.3)(a,-bi)w(ft hi)w(q 6,)w(i=1,2,，?)(4.9.4)dq 必 一J W dq q(i=1,2,，?；j =1,2,)(4.9.5)R It Ry(djj-a j x j2X(4 一八)三(&j)Xj(i=1
34、,2,?)(4.9.6)(dij )巧 (q h i)w(i =1,2,，m)产 i(djj C i)工,&(G-6,)w(/=1,2 ，7)尸 iI Vm i n z =2_ j eix jj=iit)：(dij 一 a,)J C/2(q bi)w (i=1,2,，7)j =i)：(dq -C i&(q h i)w(?=1,2 ,7)尸 i巧 2 (/=1，2，)4.1 0露天矿车流规划的数学模型及其可行性检验标准(XH，)U X(g，)0)V /G A,i p,马=0(4.1 0.7)ve/W=IA 0 0,如 0)(4.1 0.9)Q/+RQ，1(4.1 0.1 0)6 4_ X_(-Q
35、#+Tw/Sw 匕.-.0 (4.1 0.1 1)0 V S&mi n(min(bPihn)Q,+TfRv/s J(4.1 0.1 2)矿 铲0 72 5 1岩铲0 66 0 0矿 铲0 97 6 7岩 铲0 85 4 4矿 铲1 13 7 1岩 铲1 083 5矿 铲1 283 5矿石破碎站1 0 12 9 0 0岩铲0 39 1 7岩石破碎站3 0 13 5 0 0岩铲0 47 0 9岩石直排点4 0 15 0 0 0岩铲0 55 4 4空车流率a-(1 0 1.0 7)=85.3 0 8 82 3 5 2 9 1 1 1 8j(1 0 1.0 9)=7 6 7(1 0 1.0 6)=6
36、0 0j-d Ol.1 0)=83 5j-(3 0 1.0 7)=1 6 5.6 9 1 1 7 6 4 7 0 5 883 0 1,1 1)=2 7 0.6 3 2 3 5 2 9 4 1 1 7 6j r(3 0 1.1 2)=83 5*3 0 1,0 3)=9 1 77(3 0 1,0 4)=7 0 9x(3 0 1,0 5)=5 4 4J(401.11)=100.3 6 7 6 4 7 0 5 8 82 4工(4 0 1,0 8)=5 4 4习题一(1)m a x 22/i JC z 十八24-4 +JC2+3川=83 7 1 -2 7 2十不9工1 2 0,7 2 2 0,工3自由变
37、量(2)m i n w=|7|+|y|+I /r+y&l2x+z=3(3)m i n z =2 z i 1-2J-3一 工 x2 4-J-3=4一1i 3 2一 工3&6才1&0.八20,13自由变量重车流率工(0 7,1 0 1)=2 5 1工(0 9,1 0 1)=7 6 7x(l l,1 0 1)=3 7 1*1 2,1 0 1)=8 3 57(0 3.3 0 1)=9 1 7(0 4,3 0 1)=7 0 92(0 5,4 0 1)=5 4 4工(0 6,3 0 1)=4 9 5/0 6,4 0 1)=1 0 57(0 8.3 0 1)=5 4 4工(1 0,3 0 1)=83 5系统
38、共需要K车43台(1)max Z=J?I+必42/2&10q&4/I。(2)max N=3/I-2xzNi+4 4 12/i 2/2 3JTl20.N 220(3)max z=2.5ii,JC23NI+155/i+2 q 10JTl-*0*Jl2 二f 0(4)min 之=1.5;ri+2.5;rJTl 3/23/2 2/l2 0,I 2)0(5)max Z=2J：I+2x2 亚 二 一1一0.5叫+N2&2/1 2 0,二2二0(1)max z=IOJTI 5123/i+4/2&95/i 4 2/2&811 )0,N 2 1三 0(2)maxN=2/i+/212&33JTI 卜/2&12JT
39、I f 口2&5父 1 5-0,Jf 2 二 与 0(1)max z=3xi,5qJC l=42及+/4=123li+2H2+4 =18N jO(，=1,2,，5)(2)min 之=4/i 122 T 8 4,3 4 一4 =32/2+2/3-/5=5jCj 0 (，=1,2,，5)min z=3期 2JT2Ni 仙 232/i二 4JTl 0,4 20(1)min H=2/i+2/2*432/i3孙 5/3223Z I m -713&3a：i-4*2 623&5JC12 0 ,12。，/30(2)max 之=6/i 7/2 3+7JT4+5JC53/I f 7 4 +5/4+不=22JTI,
40、r2*3JT3 2xi 9JT5=6与2 0(j=L 2,3,4),l5 自由变量IN m(3)min 2i=j=l/=dj(i=1,2,)=bj(/=1,2,)j 0(1)min =3JTI+2JC2+JT371+232=8211口2)5JC l 0 0 52 0(2)max z=$2 一4Nl 十 工2 2 4 =102JTI 32 1 4 4&8,i-2彳24JRW4力 0 (j=l,2,3,4)(1)min z=2xi 3/2JC Ir4/2：2 483JTI+2/2 6为2 0 (J=l,2,3)(2)max Z=5JTI 4 3J2 6M3x 2JC2 J 3&I82ii 2 -3
41、 4 0,JT2 0,x3 自由变量表 题i.i。某次迭代的单纯形表基变量XlX iX I.74xsbX1-1310041440101is2as001人勺一弓2000max c=4/1-3心-6JT33/+x2+3JT3&302ni 4 2J：Z+3J3&40目 0 (j=1,2,3)(1)m i n z=JCi,a,22 Zi ,J*2 2 4J T l +7/2 27N l 2 0，1 2 2 0(2)m i n w =5/i 24 4/33/i+2 处)46 1 1 3 q “5/s2 1 0月2 0 (，=1,2,3)m a x t =5/i 5 2 4 1 3J3-X +j r2+3
42、J T3&2 01 2/i +4/2+1 0/3 0(j=1,2,3)表 题 1.1 4 A、B、C三种铸铁及纯 1 n 块的规格与价格材料含量ABCMn块S i(%)410.60M n(%)0.4 50.50.41 0 0单价（元/k g）0.0 2 10.0 2 50.0 1 58第二部分整数规划m a x z=2 工 1-/1 十二 2 0 ,7 2 2 0皿、/2都是整数图5.0.1整数规划与相应线性规划的可行域第5章 整 数 规 划5.1分枝定界法m ax z -4 0/1 +901 29/1 ,71 2&5 67/i 2 0/2&70线性规划问题（0）J T 1 2 0.1 2 )
43、04 5 都是整数图5.1.1问 题（0）的可行域87图5.1.2问 题（1）、问 题（2）的可行域问题（1）问题（2）?!=3 4 92 2=3 4 1.3 9工1:=42 =2.1;=0,3=355.9r=0,5=3492-340.2-34I.3CZ=f=34O=z#X图5.1.3分枝定界法5.2割平面法m ax z=4 071 T 90期(5.2.1)91 1 7J T2&5 6(5.2.2)线 性 规 划 问 题（O X1 x+2 0 x 2&70(5.2.3)4 0 ,/2 )0(5.2.4)孙，心 都 是 整 数(5.2.5)m ax z=m i n(s r)线 性 规 划 问 题
44、（IXm i n(之)=4 0才1 90J C29/i +7x2+4=5 67 q +2 0/2 +4=7 0(5.2.6)(5.2.7)(5.2.8)(5.2.9)巧2 0(j=1,2.3,4)表5.2.1问题（1）1问题（0）的最优解-4 0-9 0 000迭代次数坛变量XiXx Xa14b0-13176301311312 90011 1319T H238T H50o131530京113 a H i3C63 0 1 3 1=4.809JC_ 2 3 82=1 3?=1.81 7*=3 5 5.9孙7一寸+各，=2 3 81 3 1(5.2.1 0)工2+(1 +1 2 4 由H邛+击)4=
45、(1 铝(5.2.1 1)1 2 4 9 1 07.M,小、+77产=+(1 -石+1 3 -0)1 O X 1 0 1 1.o 11 2 4 ,9、1 07市 八一 寸2 1 3?1 2 4 _ 9 _ 1 071 31J 3 1 3 1J +js 13 1j-3=5 6 9/i 7JT2JT4=70 7/i 20JT29/1 +8JT2 579/i -8/2 +石=5 7=bij仇=居+(o 1)aq =Fii+fy(O&几 I)工乐+X心 巧=居+f i(5.2.1 2)(5.2.1 3)(5.2.1 4)(5.2.1 5)(5.2.1 6)2.1 7)(5.2.1 8)(5.2.1 9
46、)(5.2.2 0)(5.2.2 1)“A=/,4-(6 一乱,一 为整数且大于等于0：f “工i2f ii(5.2.2 2)1 4 5一4.6772 3 11 2 41.8631 071 2 40.8633 5 4.8 5.2.2问题（2）的最优解00-4 0 -9 000迭代次数3尸基变量*1X1为jet b1 1.n1020n r7n r0 蹩131790 23813111311310_ 0 J40124-_ 9.107m而600170n r53013116620131-4 0 100315 145TT I T-9 00，.0197 231124一西 124_ 0.0019124131
47、107-1 2 4 1240024585 21995(701262 62972 3 1(5.2.2 3)卜我 产诵 产二1 2 49l 2 4J 4,皆j r._ 1 07 1 2 4+(1-0-r /H i =i-0(j=1,2,，)itQt=-bi+/0 (z=1,2,i=l了,=0 或 1(7=1,2,max(cx)=min(-ex)min z=2JTI-4(1%)6/=2zi+4y2 6JT3-4n：a/j&biQi=一aaJCj Q 0一仇十与 巧=Qi=一4+Q 0j=lItQ；=4+2。户,0=imin z=a1+jr2+-6JT4 7xs3/i 2x2+6JT3+2xi 4工5
48、4-5工1 +12+73+6工5 2巧=0或1(，=1,2,5)m in 2=11+q +4 1 3+6工,-7 4Qi=-4-3 2/2 二 6加+2义 475)0Qz=-2-5辽1 +工2+八十才4 ,一 6JS 二 0j j =0 或 1(/=1,2,，5)Qt=-1,其离可行性的距离记作1Qz=-7,其离可行性的距离记作7故离可行性的总距离为8图 5.3.1 隐枚举法表 5.3.I隐枚举法的节点X自由变量不满足的约束W值T集从 T 中选出上自由变址节 点类 型节点1QIQ2z(um J*S)不可行解.T 乖空节点2可行解,2=7节点3Q iQ i7(X1X1X1X4)为不可行解,T 非
49、空节点41 1 HQ i3(a rt)X i不可行解.T 非空。点 3X iX iX4Q iQ i7(X lX fX i)14无可行解（定义二）节点6最 优 解*5节点7X iX iQ i1不可行解.T 空集Qi=4+3xi 2x2+2X40Q2=-2 5ji+工 2 +人 0max z 3 q 2JC2/5JT3工 1+2皿 一 4 2+4以+4&4ai,j-2&3可=0 或 1(j=1 2,3)3 2 4+513 3max z=3工 1 -2 q +5jr3Ni+2J72 一 工 3&2+仇 +4 3(0 0 0)TX(0 0 1)T7 7 7 753x i +5 q 2 5(0 1 0)
50、TX(0 1 1)TX(1 0 0)TX(1 0 1)T7 7 7 783n 2.n+52 8(1 1 0)TX(1 1 1)TX5.4求解指派问题的匈牙利法p表示指派第，个人去完成第7项任务令4 =S 表示不指派第，个人去完成第/项任务 nmin z=V V=1 (j=1,2.,)i二l 入=1 (i=1,2,“)Xy=0 或 1 (/=1,2,，；/=1,2,，)表5.4.I五人指派问题人 员 石壬务(/)ABCDE甲1 27979乙89666丙71 21 21 49T1 01 4661 0戊41 071 09127979 -7-5 02 0289666-623 000kJ=7121214