最优化方法习题答案

1、习题一1利用图解法求下列线性规划问题：(1) maxz = X + x23x)+ x2 > 2s.tx Xj +2x2 <5xpx2 >0解：根据条件，可行域为卜而图形中的阴影部分,，有图形可知，原问题在A点取得最优值, 最优值z=5(2) minz = x, -6x22Xj +x2 < 1 s.t-X + x? <7xpx2 >0解：图中阴影部分表示可行域，由图可知原问题在点A处取得最优值，最优值z=6（3）maxz = 3x）+2x2-X +x2 < 1s.txxt-2x2 >-4xpx2>0解：如图所示，可行域为图中阴彩部分，易得原线

2、性规划问题为无界解。(4) minz = 2xl -5x2X +2x2 > 6 s.tx Xj + x2 < 2xpx2 >0解：由图可知该线性规划可行域为空，则原问题无可行解C1.2对下列线性规划问题，找出所有的基解，基可行解，并求出戢优解和最优值。(1) minz = 5x! -2x2 +3x3 -6x4X +2X2+ 3X3+ 4X4 = 7 s.tx 2x1 + x2 + x3 + 2x4 = 3xpx2,x3,x4 >0rr解：易知X|的系数列向p,=z,X2的系数列向a： p2 =J >,X3的系数列向fip3 =X4的系数列向gp4=oIx + 2

3、x 9 = 7 3x 4x123令非基变址为x3=x4=0，得2x, + x2 = 3-x3-2x4_ 1xi=3,所以得到一个基解x=(-丄,耳,0,0)是非基可行解；_113 3X2T因为Pl，P3线性无关,可得基解X(2)=(-,O,-,O), Z2=；555因为Pi，P4线性无关，可得基解x=(一丄A0,-),是非基可行解；36因为p2,p3线性无关，可得基解x=(0,2,1,0), z4=-l； 因为p2,p4线性相关，x2,x4不能构成基变屋； 因为P3，P4线性无关，可得基解X=(0,0,1,1), z6 = -3：所以x,x,x是原问题的基可行解，x是最优解，最优值是z = -

4、3o(2) maxz = X + x3 -2x3 + x4 - x5x( +x2 + x3 + x4 = 1 s.tx -Xj +2x” + x5 =4xU0,i = 1,2,3,4,5f、仃、解：易知X的系数列向®P1 =,X2的系数列向fip2 =-1>X3的系数列向量j厂1、9P3 =,X4的系数列向s p4 =，X5的系数列向®p5 =0lb 因为PP2线性无关，故有 '23"，令非基变暈为X3=X4=X5=O,得-x1 + 2x2 = 4-x52X, 32 5,所以得到一个基解x=(-兰,三,0,0,0),是非基可行解；_53 3X?2 3

5、 因为pP3线性无关，可得基解x=(-4,0,5,0,0),是非基可行解； 因为PP4线性无关，可得基解x=(-4,0,0,5,0),是非基可行解： 因为Pi，Ps线性无关，可得基解x=(1,0,0,0,5), z4=-4； 因为p2,p3线性相关，得基解x:=(0,2,-1.0,0),是非基可行解； 因为p2,p4线性无关，可得基解x= (0,2,0,-1,0),是非基可行解： 因为p2,p5线性无关，可得基解x=(0,1,0,0,2), z7=-l； 因为p3,p4线性相关，x3,x4不能构成基变暈； 因为P3，P5线性无关，可得基解X00 = (0,0,1,0,4), z9=-6； 因为

6、p4,p5线性无关，可得基解x(10) = (OAOJ,4), z10 = -3 ；所以原线性规划的基可行解是x(4),x<7),x(9),x(,0),最优解是x，最优值是z = -l.1.3用单纯形法求解下列线性规划问题；(1) maxz = 2x, +3x2x1 +3x? <5s.txx1 + x2>2Xpx2 >0解：引入松弛变屋X3,剩余变屋X。和人工变屋X5,把原问题化为规范式maxz = 2X +3x2 -Mx5X, +3x2 + X3 =5s.h Xi + x? X4 + X5 =2 ,其中 M 无限大,Xj >0,i = 1,2.5构造初始单纯形表

7、并计算如卜:XiX2X3X4X52+M3+M0-M0X3131005X5110-112以X2作为换入基，X3作为换成基，计算得X1X2X3X4X51 + -M30亠M3-M0X23130053X5230丄 3-11丄3以X】为换入基，X5作为换出基有X1X2X3X4X500丄 232-M2-5.5X2011212_121.5X110丄2_32320.5以X4换入，X?换出有X1X2X3X4X50320-3-M-10X40211-13X1131005根据单纯形表可知，原问题的最优解为X、(500,3),最优值为 = 10(2) maxz = Xj + x2-2x33x)+x2-x3 <5s

8、.tx X -4x? + X3 >7xpx2,x3 >0解：引入松弛变Mx4,剩余变屋X5和人工 变S：x6,把原问题规范化为max z = X + x? 2x3 一 Mx63X| +x2 -x3 + x4 =5s.tx X -4x2 + x3 -x5 + x6 =7Xj >0,i = 1,2.6X1X2X3X4X5X61+M1-4M-2+M0M0X431-11005X61-410117以作为换入基，Xq作为换出基有X,x2X3x4X502 13M3 34M 53 31-M3-M0X11丄31330053X601334313-11163以X3为换入变暈，X6为换出变量，得xi

9、X2X3X4X5X60-4M40_ 1 12_545-4M4xi1_560丄4133X301341434344所以原问题最优解为x*= (3,0,4),最优值为z=-5o(3) minz = 2x)+3x2 +x3Xj +4x2 +2x3 >8s.t/ 3x)+2x2 > 6xpx2,x3>0解：引入剩余变鼠X4,x5和人匚变址x6, X7,利用两阶段法得到辅助线性规划max w =-x6 -x7maxz =-2X -3x2 -x3X| +4x2 + 2x3-x4 + x6 =8s.tx3、+ 2x2 -x5 + x7 =6x, m,27构造初始单纯形表，并计算X1X2X3X

10、4X5X6X7t z-23-10000w4621-100X614210108X73200-1016以X2为换入变虽，X&为换出变星，得X1X2X3X4X5X6X7* z540丄2_340340w5201丄2-1320X2丄41丄2140丄402X7520-1丄2-1丄 212以X|为换入变虽，X?为换出变量，得X1X2X3X4X5 z00022X2010.6-0.301.8X110-0.40.2-0.40.8从单纯行表中可知，原问题有无限多个最优解，其中一个为x* =(0.8,1.&0),最优值为z"=7o(4) maxz = 10x1 +15x2 +12x35Xj+

11、3x2 + x3<9-5x)+6x2 + 15x3 < 15 s.t/2X + x2 + x3 >5Xj>0J = 1,2,3解：引入松弛变S：X4 X5,剩余变屋X6人工变屋X?，将原问题化为规范式 maxz = 10x)+15x2 +12x3 -Mx75X +3x2 + x3 + x4 =9一 5X + 6X2 + 15X3 + X5 = 15 st2x)+ x2 + x3-x6 + x7 =5Xj2 0,j=l,2,.,7构造初始单纯形表并计算得以X|为换入变童，X.为换出变量，得XX2X3X4X5X6X7Z10+2M15+M12+M00M0X$53110009X

12、5-5615010015X721100-115以X为换入变屋，为换岀变屋X1X2X3X4X5X6X7Z09 M552加50M0X10.60.20.20001.8X50916110024X70-0.20.6-0.40-111.4进一步计算知道，x?hO,所以原问题没有可行解。1.4设目标函数极大化的线性规划问题的单纯形表如下，表中无人工变址，当待定常数 aa2，bC,C2为何值时，表中的解：(1)为唯一最优解，(2)为多重解，(3)有无界解,(4)为退化解。X1X2X3X4X5X6C10C2-900Z°X2ai1a21007x5-1050103X640-2101解：当b,>0,c

13、c2<0,为唯一最优解； 当 bj > 0,C1 = 0,c2< 0或C| < 0,c2 = 0,为多垂解； 当b! >0,a2 <O,Cj <0,c2 >0,具有无界解； 0=0,5>0或32>0工2>0,为退化的可行解。1.5某商店要制定茱种商品第二季度的订划，已知该商店仓库容纳此种商品的容址不超过 600件，3月底已存货200件，以后每月初进货一次。假定各月份此种商品买进您出的单价 如卜，问各月进货、售货各多少件才能使利润最大？假设进货时受到仓库容屋的限制，售货时受到进货虽的限制，不考虑货物存放在仓库的耗损与保管费用。月份

14、买进单价/（元/件）售出单价/（元/件）41718516.51861719解：设Xj表示每个月进货氐 人表示相应月份售货氐 其中i = 1,23,则有数学模型:max z = 18y】+18y2 + 19y) 17x, -16.5x2-17x3x, <600-200Xj -y! + x2 <600-200x1-y, + x2-y2 + x3 <600-200s.t/ -X + Yj < 200-x) + yl-x2 + y2 <200 -Xj + yj-xyXj + yZOOXpYj >0,i = 1,2,3经计算，当 X） = 400,y, = 600,x

15、2 = 500,y2 = 600,x3 = 600,y3 = 600时，即四月份进货400件，售货600件，五月份进货500件，售货600件，六月份进货600件售货600件时, 最犬利润为6100元。1.6设市场上可买到n种不同的食品，第j种食品的单位售价为勺，每种食品含有m种基本 营养成分，第j种食品每一个单位含第i种营养成分为a»,每人每天对第i种营养成分的需 要屋不少于0,试确定在保持营养成分要求条件下的最经济食谱。解：设没人每天需要第j种食品的数屋为Xj （j=ix.,n）,建立数学模型为: minz =CjXj工 aijXjnbi = 12,ms.t. HXj > 0

16、, j= l,2,.n1.7 A,B两种产品都需要经过前、后两道工序加工，每一个单位产品A需要前道工序1h 和后道工序2h,每一个位产品B需要询道工序2h和后道工序3h.可利用的询道工序有llh, 后道工序有17h。没加工一个单位产品B的同时，会产生2个单位的副产品C,并且不需要 任何费用，产品C 一部分可出您盈利，其余的只能加以销毁。出售单位产品A,B,C的利润 分别为3元，7元，2元，每单位产品C的销毁费为1元预测表明，产品C戢多只能出 售13个单位。试建立总利润最人的生产计划数学模型。解：设xx2分别为产品A,B的产最，X3为副产品C的销售诡，Xq为副产品C的销毁呈,于是有x3+x4=2

17、x2, z为总利润，则数学模型如下：max z = 3x, +7x, + 2x3 -x4x1 -i-2x2 < 1 12x, + 3x, < 17s.tx-2x24-x3 + x4 = 0x3<13xpx2,x3,x4>0习题二2.1写出卜列线性规划问题的对偶问题:(1) minz = 10X -5x?+X3X +2x2 +4X3 >10X +6X2 -5X3 <2S.t/-l<x2 <7xpx30,x2g 由变量解：原问题的对偶问题为：max w = 10y】 +2y2 + y3 +7y4yrSlO 2y1+6y2-y3 + y4=-5 4y)

18、-5y2 <1(2) maxz = x( -2x2 +3x3 -4x42X + x2 + x3 -5x4 < 13 s.t.4X -2X2+3X3+ X4 >5 xpx2,x3 >0,x4自由变量解：原问题的对偶问题足min w = 6y】+13y2 + 5y3 y1+2y2+4y3>l 5y! + y2-2y3>-2s.t.2< 一 y】+ y2 + 3y3 > 32yi-5y2 + y3=-4y】无约束，2 o,y3 <02.2证明下列线性规划为题为最优解2X +x2 -2x3 =3X -2x2 +3x3 > 2 minz = x

19、,-2x2-2x3 s.t/1 < x2 5 7xpx2 >0,x3 由变量证明：原问题的对偶问题为max w =3y( +2y22力+2<1儿 一 2丫2<-2 -2y,+3y2=-2易知该对偶问题无可行解，由定理知则原问题无最优解。2.3对线性规划问题minz = 4X +6x2 + 18x3X +3x3 >3s.tJx2 +2X3 >5xnx2,x3 >0（1）写出该线性规划问题的对偶问题；（2）已知对偶为题的最优解为（2,6）,试用互补松弛定理求其原问题的最优解。 解：（1）原问题的对偶问题为：max w =3y, +5y2心y2S.t/3yi

20、2y2 <18（2）根据互不松弛定理有（yA-c）x = 0 则/10_、(X|,X2，X3)01- (3,5)(2,6) = 032丿fx( + 3x3 =3有x2 + 2x3=5又因为yb = cx有(2=(3,5)4(xpx2,x3) 62即：2X +3x2 +9x3 = 18 Xj =0联立解得k2=3即原问题的最优解为(0,3,1)X3 = 12.4对线性规划问题maxz = 2x, +x2 +5x3 +6x42X + x3 + x4 <8s.t? 2x)+ 3x2 + X3 + 2x4 =12x,x2,x3,x4 >0(1) 写出该线性规划问题的对偶问题：(2)

21、已知原问题的最优解为(0,0,4,4)，试用互补松弛定理求对偶问题的最优解。解：(1)原问题的对偶问题为：minz = 8y! + 12y22yi+2y2>23y2 >1s.tJ + y2 > 5Yi +2y? 16Yi >0,y2无约束利用互补松弛定理有（yA-c）x =00'（"2）2 0 112 3 12有4=0 y+y2=5y + 2y 产 6所以对偶问题的最优解为（4,1）2.5用对偶单纯形法求解下列线性规划问题:(1) minz = 2Xj +4x2 +5x3X +x2 -3x3 > 1s.tJX +x2 >6xpx2,x3 &

22、gt;0解：利用对偶单纯形，添加松弛变Kx4,x5,原问题化为规范式maxz =-2x)-4x2 -5x3-Xj -x2 +3x3 + x4 =-ls.txx, -x2 + x5 =-6则有对偶单纯形表xpx2,x3,x4,x5 >0X1X2X3X4X5-2-4-500X4-1310-1X51-1001-6以X2为换入星，Xs为换出量有X1X2X3X4X560-50-4X42031-15X2110016由表可知。原问题的最优解为（060）（2）maxz = -Xj -x2 -2x3X -5x2 +3X3 <42X| +x2 +6x3 > 10 s.t.-X -2x2 +3X3

23、 <7XHX2,X3 >0解：利用对偶单纯形添加松弛变Ux4,x5,x6-原问题化为规范式,maxz =-Xj -x2 -2x3X）-5x2 +3X3 + X4 =42X Xj 6X3 + X5 = 10s.tJ，则有单纯形表X -2x2 +3x3 + x6 =7Xj n0,i = 1,2,345,6X1X2X3X4X5X612000X41-531004X521-6010-10X61230017以X3为换入量，Xs换出得X1X2X3X4X5X6-1/3-2/300-1/30X40-11/2011/20-1X31/31/610-1/605/3X60-5/2001/212以X2为换入量

24、，X4为换出虽有X.X2X3X4X5*6-1/3002/3-3/110X20102/11-1/1102/11X31/3011/33-5/33054/33X6000-5/113/11127/11由表知原问题无最优解。2.6设有线性规划minz = -2x, + x2 + x33X +x2 +x3 <60Xj -x2 +2X3 <10S.t/X +x2 -x3 < 20xpx2,x3 >0求出最优解，并进行以下分析（1）C2在什么范用内变动而不彩响最优解？（2）b3从20变为16,求最优解；（3）X3的系数变为（1,3,-1）其价值系数从1变为5,试问最优解是否会发生变化?

25、（4）增加约束条件2x, + x2-+-x5<31,最优解有何变化？解：引入松弛变Sx4,x5,x6,将原问题化为规范行:maxz = 2X -x2 -x33X +x2 + x3 + x4 <60Xj -x2 + 2x3 + x5 < 10S.t/x( +x2 -x3 + x6 <20X1X2X3X4X5X62-11000X431110060X51-1201010X611-100120列单纯形表有以X为换入变最，为换出变虽有X1X2X3X4X5X601-50-20X40451-3030X11-1201010X60230-1110以X?为换入变星，X6为换出变蚩有X1X2

26、X3X4X5X600-7/20-3/2-1/2X40011-1-210X）101/201/21/215X201-3/20-1/21/25所以原问题的最优解为（15,5,0,10,0,0）17 3（1）因为X2是基变量，由书中（2.6）式有max（专）= -】，min（,-2-） = 22T 2744所以一 ISACqS'时，最优解不变，即一 2c2<-,所以当一 -<c2<2«t,原问题最优333解不变。1-1-2ro、Q、(2) Ab =B-'Ab =01/21/20=-20-1/21/2、幻10)<8、18、b = b + Ab =15+-

27、2=13所以5丿-2,此时皈问题的最优解为(13,3Q1&O,O)1 -11/2 3=-2<01/2 .(3) g3 =c3-cBB_,p3 =-1-(2,-1-1) 01/20 -1/2所以原问题的最优解变。(4)添加松弛变屋x“在原最终单纯形表中添加一行一列并计算有X1X2X3X4X5X6X700-7/20-3/2-1/2X40011-1-2010X|101/201/21/2015X201-3/20-1/21/205X70010932-8以X3为换入最，x7为换出量有XIX2X3X4X5X6X7000063/2-1213/2X40001-101-218Xl1000-42-11

28、9X2010013-437X300109-328以X&为换入屋，X3为换出暈有X1X2X3X4X5X6X700-40-9/2013/2X4001/31-701/346/3Xl10-2/30201/341/3X201-4/30101/311/3X600-1/30-31-2/38/3得最优解为(41/3,11/3,0,46/3,0,8/3,0)，最优值为71/32.7某厂生产£44三种产品，需要BpB2.B3三种设备加工，需要单位各种产品所需 要的设备台时、设备的现有加匚能力及每件产品的预期利润如下表所示台/hA2A3设备能力Bi111100b21045600b3226300单位

29、产品利润1064(1) 求获利最人的产品生产计划；(2) 每件产品A3的利润增加到多人时，才值得安排生产？如果每件产品A3的利润增加到50/6,求最优计划的变化；(3) 产品A|的利润在多人范围变化时原戢优计划保持不变？(4) 如设备B|的能力为100 + 108,确定保持最优基不变的§的变化范|用；(5) 如有一种新产品，加工一件需要设备B”B2，B3的台时各为lh,4h,3h预期每件的利润为8元，是否值得安排生产?a）如合同规定该厂至少生产10件产品A?,试确定最优计划的变化。解：设计划生产产品A,A2,A3各X,X2，X3件，则有maxz = 10Xj +6x2 +4x3x +

30、x2 + x3 < 10010X +4x? +5x3 <600 st2、+2x?+6X3 <300x ,x2,x3 >0（1）构造单纯形表如下:X1X2X3X4X5X61064000X411110010()X51045010600X6226001300以X|为换入屋，X5为换出星令X1X2X3X4X5X60210-10600X403/51/21-1/10040xi12/51/201/10060X606/550-1/51180以X2为换入址，Xa为换岀暈有X1X2X3X4X5X600-8/3-10/3-2/30-2200/3X2015/65/3-1/60200/3X101

31、/6-2/31/60100/3X6004-201100得最优生产计划，即X =(100/3,200/3,000,100)为最优解，获利2200/3元由于X3为非基变屋，则只有b >0才值得生产，即 Ac3 > Ac3 > 8/3,即 c >20/3 时 A3才值得生产。而当c =50/6 > 20/3 ,此时最优 解发生变化，根据计算，当c'= 50/6时，s=5/3>0时，此时将X3作为换入变屋，X&作 为换出变屋，得X1X2X3X4X5X6000-5/2-2/3-5/12-2325/3X201025/12-1/6-5/24275/6Xi1

32、00-7/121/6-1/24175/6X3001-1/201/425此时生产最优计划为(175/6,275/6,25,0,0,0)由于、的生产星为基变氐则有叭誥，需)一，呎甥卜5,即gw-4,5时，原最优生产计划保持不变。得C|w65(4)若矩阵1B = (Pi，P2，P3)= 42改变，根据(2.7)有max-200/3) 5/3 )5/3-2/3-1/61/60o'0 ,为使最优基不发生1< Ab1 < min一100/3 -100-2/3-2Ab, g-40,50,即qg-475时，最优基不发生改变。rcBB_,p7 =(6,10,0) 0 =61 1(5)经 计

33、算 B_,p7 = 01q7=c7-cbB-'P7=8-6 = 2>0,WiJ此时最优解发生变化，且该产品值得生产。(6)原最优解不满足新的约束条件，x3>10,即-x3<-10,引入松弛变Mx7,在原最终单纯形表中增加一行或一列有：X1X2X3X4X5X6X700-8/3-10/32/300-2200/3X2015/65/3-1/600200/3X1101/6-2/31/600100/3X6004-2010100X700-10001-10将X?做为换出变屋，X3作为换入变垠，利用对偶单纯形有X1X2X3X4X5X6X7000-10/3-2/30-8/3-22120/

34、3X20105/3-1/605/6175/3X1100-2/31/601/695/3X6000-201460X7000100110得到此时最优生产计划X，= (95/3,175/3,10,0,0,60)2.8对所有t值，讨论以卜参数线性规划问题最优解的变化范用;maxz = (7 + 2t)x+ (12 + t)x2 +(10-t)x3X +x2 + x3 <20s.t? 2x)+2x2 + x3 < 30X,x2,x3 >0,t >0解：将上述问题转化为标准型有maxz = (7 + 2t)x+ (12 + t)x2 +(10-t)x3X + x? + X7 + X4

35、 S 20s.tx 2X + 2x2 + x3 + x5 <30xpx2,x3,x4,x5 >0,t>0令匸0,用单纯法求解如下:CJ71210009CbXBbXIX2X3X4X50X42011110200X5302210115-z071210000X45001/21-1/21012X215111/201/230z1805040610X3100012112X210110-11-z-22050082将t的变化直接反应到最终的单纯形表中CJ7+2t12+t10-t000CbXBbX1X2X3X4X510-tX3100012-1512+tX210110-11-z220T-5003t

36、-8-2-2tT开始增人，当t>8/3时，首先出现4>°,故当0 <t<-时，得最优解(0, 10 10, 0) 3目标函数的最优值为max z = 220(0 <t<-)o t =-为第一临界点33当討<5时q。 x4作为换入变域由。规则确定也为换出换用单纯形法进行迭代:CJ7+2t12+t10-t009CbXbbX1X2X3X4X50X45001/21-1/212+tX215111/201/215-z-180-15tT-504-3t/206t/2由表可知，t继续增大，当>5时首先輙6 >0,故当*4时，得最优解(035A5)目

37、标函数的戢优值为180+151,匸5为第二临界点。当t>5时，o,>0, X|作为换入变星，由0规则确定X?为换出变氐 用单纯形法进行迭代：Cj7+2t12+t10-t000CbXBbX|X2X3X4X50X45001/21-1/27+2tX115111/201/2-z-105-30t05-t13/2-2107/2y由表知 当I继续增大时，所有检验数都非正，所以当05时，得最优解(15, 0, 0, 5) 目标函数的最优值为105+3012.9考电卜列问题:maxz = 3X +x2xt +x <4s.t.x, -x2 <4xpx2 >0(1)用单纯形方法求出最优

38、解:(4)(2)将约束右端b= 改变为U丿(-2+ t (t>0),对t的所有值求出问题的最优解。解：(1)引入松弛变®x3,x4,把原问题化为标准形maxz = 3X +x2x, +x2 +x3 =4S.t/ 2Xj - X2 + x4 = 4,建立初始单纯形表XpX2,x3,x4 >0X1X2X3X43100X311104X42-1014以X|为换入变屋，X4为换出变量，有X1X2X3X405/20-3/2X3011-1/22X11-1/201/22以X2为换入变虽，X3为换出变屋有X1X2X3X400-5/3-2/3X2012/3-1/34/3X1101/31/38

39、/3所以，原问题的最优解为(8/3 , 4/3)-1/3-<-2f，_5t/3、1/3J >-t/3 >2/3 b=B-Ab= M3将其加在最终单纯农中有X】X2X3X400-5/3-2/3X2012/3-1/34/3-5t/3X1101/31/38/3 -t/34由表可知当问题的最优解为(8/3 -t/3, 4/3-5t/3)5当时，利用对偶单纯形有X1X2X3X40-23/2/3X40-3-215t-4X111104-2t由表可知当时，问题的最优解为(421, 0),当t>2时，原问题无解。习题三3.1托割平而法求解卜列整数线性规划。(1) min z = 2xx

40、- x2K3兀2 <1s.tJ X)+x2 <4xx2>Ofi为整数解：增加松弛变虽心,兀，将其化为标准形为兀).3占+禺=1minw = -2xI+x2 s.t/ x1 + x2 + x4=4先不考虔整数条件，则对应线性规划单纯和七，禺，兀no且为整数形表如下£兀4W-21001310111014以忑为换出基，E为换入基，进一步得单纯形表X1卷W300-1勺401313X211014所以，原线性规划问题的最优解为x# = (0,4),是整数解所以也是原整数规划的整数解。(2) maxz = -12x1 +9x22X + x2 < 10X +5x2 <6

41、s.t?3X -2x? <3XyXzAO且为整数解：増加松弛变©x3,x4,x5,将其化为标准形为:2X +x2 + x3 <10-Xj +5x2 + x4 <6 maxz = -12X +9x2 s.t/3x, -2x2 + x5 <3 xpx2,x3,x4,x5 >0K为整数先不考虑幣数条件，则对应线性规划单纯形表如下屁X5Z-1290002110010£-150106X53-20013以勺作为换入变呈，耳为换出变虽得X5Z-51/500-9/50兀311/501-1/5044/5兀2-1/5101/506/5X513/5002/5127/

42、5所以线性规划的最优解为(0,6/5,44/5,0,27/5)分址 44/5取整后分数最大，考虑单纯形表中该分屋所对应的行约束-xx,-丄心=聖，则有割555414平而方程-(-X1+-x4)<0,增加松弛变fflx6,化为等式约束X| x4 + x6 =并加入上面最后的单纯形表中有：555“3兀4X5X6Z51/500-9/50011/501-1/50044/51/5101/5006/5X513/5002/51127/5X6-1/500-4/501-4/5利用对偶单纯形法有勺冯忑X5X6z-203/200000-9/4兀343/200100-1/49兀2-4/2510001/41X55

43、/200011/25X61/40010-5/41由表可知最优解为(0,1)嚴优值为9.3.2用分支定界法求解下列整数线性规划问题：(1) maxz = x1 +5x23X +4x2 <11s.t? 7X +6x2 <42xpx2>0且为整数解：先不考虑州，x2为整数的约束条件，求的相应线性规划问题的最优解为x® = (0,11/4), 目标函数的最优值为z()=55/4,由于x!0) = 2+3/4,构造两个线性规划子问题如下： maxz = x, +5x23x)+4x2 < 11 7X +6X2 <42s.tJ(1)x2 <2 xpx2 >0K为整数和 m axz = x, +5x23x)+4x2 < 11 7X +6X2 <42s.tJx, >3Xpx2 n OIL为整数先不考虑整数的约束条件，求解(1)所对应的线性规划子问题得到戢优解x,=(l,2),最优值为z,=ll, (2)所对应的线性规划子问题没可行解。故原整数规划的最优解为x,= (1,2),最优值为Zj = 1 1 O(2) minz = 3X|