《运筹学》题库

1、 运筹学习题库数学建模题（5）1、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙4610120360200300试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为xl、x2，则xl、x220,设z是产品售后的总利润，则maxz=70 x1+120 x2s.t.9x+4x360124x+6x20012x+10 x0122、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量原材料（吨/件）223000吨工时（工时

2、/件）52.54000工时零件（套/件）1500套产品利润（元/件）43建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为x、X，12设Z为产品售后总利润，则maxz=4x+3x12s.t.2x+2x3000125x+2.5x400012x0123、一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润1010资源储备量|100600300建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙

3、三种产品的生产数量应为x、x、x，则x、x、x0,设z是产品售后的TOC o 1-5 h z123123总利润，贝ymaxz=10 x+6x+4x123Stx+x+x10012310 x+4x+5x600彳1232x+2x+6x0J1234、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数201518148410试建立队员所能携带物品最大量的线性规划模型，不求解。

4、解：引入01变量x,x=1表示应携带物品i,x=0表示不应携带物品ITOC o 1-5 h ziiinaxz=20 x+15x+18x+14x+8x+4x+10 x2345675x+5x+2x+6x+12x+2x+4x251、234567x=0或1,i=1,2,.,7i5、工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：I资、品源ABC资源限量材料（kg）1.51.242500设备（台时）31.61.21400利润（元/件）101412根据市场需求，预测三种产品最低月需求量分别是150、260、120,最高需求量是250、310、13

5、0,试建立该问题数学模型，使每月利润最大，为求解。TOC o 1-5 h z解：设每月生产A、B、C数量为x,x,x。123MaxZ=10 x+14x+12x123厂1.5x+1.2x+4x25001233x+1.6x+1.2x1400123150 x2501260 x3102120 x01236、A、B两种产品，都需要经过前后两道工序，每一个单位产品A需要前道工序1小时和后道工序2小时，每单位产品B需要前道工序2小时和后道工序3小时。可供利用的前道工序有11小时，后道工序有17小时。每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一部分可出售盈利，其余只能加以销

6、毁。出售A、B、C的利润分别为3、7、2元，每单位产品C的销毁费用为1元。预测表明，产品C最多只能售出13个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产A、B数量为x,x,销毁的产品C为x。23MaxZ=3x+7x+2（2x一x）一x12233厂x+2x11122x+3x17122x一x01237、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500m3，在两个工厂之间有一条流量为200万m3的支流。第一化工厂每天排放有某种优化物质的工业污水2万m3，第二化工厂每天排放该污水1.4万m3。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20%可自然净

7、化。根据环保要求，河流中的污水含量不应大于0.2%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000元/万m3，第二化工厂的为800元/万m3。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。500万m3200万m3解：设第一化工厂和第二化工厂的污水处理量分别为每天X1m3和x2万m3,minZ二1000 x+800 x120.8x+x1.612x80123x+x+2x65S.t.701321x+7x+35x450123x,x,x01239、某公司生产的产品A，B，C和D都要经过下列工序：刨、立铣、钻孔和装

8、配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铣钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下：产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别x1,x2,x3,x4单位则应满足的目标函数为：maxz=2x1+3x2+x3+x4满足的约束条件为：0.5x+x+x+0.5x1800TOC o 1-5 h z12

9、342x+x+x+x280012340.5x+0.5x+x+x300012343x+x+2x+3x60001001x6002x5003x400410、某航空公司拥有10架大型客机、15架中型客机和2架小型客机，现要安排从一机场到4城市的航行计划，有关数据如表1-5，要求每天到D城有2个航次（往返），到A,B,C城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班计划。客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d）大型A6000700080001000050007000100001800012510BCD中型A100020004

10、00030004000600024820BCD小型A20003500600040005500800012619BCD解：设大型客机飞往A城的架次为x1A，中型客机飞往A城的架次为x2A，小型客机飞往A城的架次为x3A，其余依此类推。资源限制派出的大型客机架次不能超过10架，表示为x+x+x+x10TOC o 1-5 h z1A1B1C1D同理x+x+x152A2B2Cx+x+x0且为整数；（i=l,2,3;j=A,B,C,D）ij目标函数为maxz=1000 x+0 x+2000 x+8000 x+2000 x+1A1B1C1D2A2000 x+2000 x+2000 x+2000 x+200

11、0 x2B2C3A3B3C11、CRISP公司制造四种类型的小型飞机：AR1型（具有一个座位的飞机）、AR2型（具有两个座位的飞机）、AR4型（具有四个座位的飞机）以及AR6型（具有六个座位的飞机）。AR1和AR2一般由私人飞行员购买，而AR4和AR6一般由公司购买，以便加强公司的飞行编队。为了提高安全性，联邦航空局（F.A.A）对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进行的，因此小型飞机的制造是以月为单位进行的。表说明了CRISP公司的有关飞机制造的重要信息。AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）8171115建造飞机所需要

12、的时间（天）47911每架飞机所需要的生产经理数目1122每架飞机的盈利贡献（千美元）6284103125CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30，每月按30天计算）。JonathanKuring是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设x表示下个月生产AR1型飞机的数目，x表示AR2型，x表示AR4型，x表示1234AR6型目标函数：maxz=62x+84x+103x+125x12344x+7x+9x+llx270123

13、4x+x+2x+2x601234x81约束条件：x172x113x01234x,x,x,x为整数123412、永辉食品厂在第一车间用1单位原料N可加工3单位产品A及2单位产品B,产品A可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元，加工后单位售价增加9元。产品B可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位售价可增加6元。原料N的单位购入价为2元，上述生产费用不包括工资在内。3个车间每月最多有20万工时，每工时工资0.5元，每加工1单位N需要1.5工时，若A继续加工，每单位需3工时，如B继续加工，每单位需2工时。原料N每月最多能得

14、到10万单位。问如何安排生产，使工厂获利最大？解：设x为产品A的售出量；x为A在第二车间加工后的售出量；x表示产品B的售出123量;x4表示B在第三车间加工后的售出量；x5为第一车间所用原材料的数量,则目标函数为：maxz=8x+9.5x+7x+8x一2.75xTOC o 1-5 h z12345x10000053x+2x+1.5x20000045约束条件：012345化标准形式（5）1、将下列线性规划模型化为标准形式解：minz=x-2x+3x123x+x+x21233x+x+2x=5123x0 x0 x无约束v123maxz=-x+2x-3(x-x)+0-x+0-xx+1x21+2x445

15、67x+x=756xx+xxx=2124573xx2x=5123x0172、将下列线性规划模型化为标准形式minz=x+2x+3x123二2x+x+x421234x2x3x=6123x0 x无约束v123解：2x+x+xx+x=9123343x+x+2x2x一x=4123354x+2x+3x3x61233x0J15maxz=x-2x一3x+3x12333、将下列线性规划变为最大值标准形。minz=-3x+4x-2x+5x12344xx+2xx=2TOC o 1-5 h z1234x+x+3xx14st0,x无约束1234解：maxz=3x一4x+2x一5x+5xTOC o 1-5 h z123

16、44一4x+x一2x+x一x=212344x+x+3x一x+x+x=14stI123445一2x+3x一x+2x一2x一x=2123446x,x,x,x,x,xx0123445,6图解法(5)1、用图解法求解下面线性规划minz=3x+2x122x+4x2212x+4x10122x一x712x一3x012解：可行解域为abcda,最优解为b点。”2兀+4x=22Q12由方程组x=0解出X=ll,x2=02x.X*二1=(11,0)T丿2.minz=3X11+2X0=332、用图解法求解下面线性规划minz=2X+X12一x+4x82125x02解：从上图分析，可行解域为abcde，最优解为e点

17、。由方程组x+x=812X=5解出X=5,x2=31X.X*二X=（5,3）t丿2.minz=Z*=2X5+3=133、已知线性规划问题如下：MaxZ=x+3x12f5x+10 xi50 x012x15x+10 x=5012由图可知：5x+10 x12二50解之得：X=2x二42则maxZ=2+3*4=144、用图解法求解下面线性规划问题maxz二2x+x12”5x15i6x+2x24St.12x+x012解：5、用图解法求解下面线性规划问题maxz二2x+3x12x+2x812x16s.t14x0,j二1,2j值为z*二2*4+3*2二14。二、单纯型法（15）1、用单纯型法求解下面线性规划

18、问题的解maxz=3x+3x2+4x33x+4x+5x40TOC o 1-5 h z123v6x+4x+3x0123解：加入松弛变量x,x,得到等效的标准模型:45maxz=3x1+3x2+4x3+0 x+0 x3x+4x+5x+x二4012340,j二1,2,.,5j列表计算如下：CBXBb3x13x24x30 x40 x59L0 x44034(5)1080 x566643012200000334t004x383/54/511/5040/30 x542(21/5)8/503/511012/516/544/503/5t1/504/504x3204/712/71/73x11018/2101/75

19、/21324/745/71/73803/705/71/7X*=(10,0,2,0,0)t.maxz=3X10+4X2=382、用单纯型法求解下面线性规划问题的解maxz=70 x+120 x12”9x+4x360124x+6x20012s.t.3x+10 x012解：加入松弛变量X,x,x，得到等效的标准模型:345maxz=70 x1+120 x2+0 x3+0 x4+0 x5s.t.=360=200=3009x+4x+xTOC o 1-5 h z1234x+6x+x1243x+10 x+x125x0,j=1,2,.j5j列表计算如下：70120000CBXBbx1x2x3x4x59L0 x

20、336094100900 x420046010100/30 x53003(10)001300000070120t0000 x324039/5010-2/5400/130 x420(11/5)001-3/5100/11120 x2303/101001/1010036120001234t000-120 x31860/11001-39/1119/1170 x1100/111005/11-3/11120 x2300/110103/222/1143000701200170/1130/1111000-170/11-30/111003001860 x*(，-,0,0)T11111110030043000-m

21、axz=70Xit+120rr=f3、用单纯型法求解下面线性规划问题的解2x+2x3000125x+2.5x4000maxz=4x+3xS.t.V1212x02解：加入松弛变量X,3x4，X，得到等效的标准形式:5maxz=4x+3x+012x+03x+0XS.t.V42x+2x+x1235x+2.5x+x二4000124x+x二50015x0,j二1,2,.,5j二3000用表解形式的单纯形法求解，列表计算如下：CBXBbx3x4x53000400050043000 xxxxx123452210052.5010(1)0001000004f30009L3000/2=15004000/5=800

22、500/1=5000 x30 x4200015004x500i0210-20(2.5)01-5100014000403f00-42000/2=10001500/2.5=600 x3x2x180060050040014001004600001400014001-0.8(2)100.4-2301.2-200-1.22f0.5-0.4111-0.400-0.50.40310.400-1-0.40据上表，X*=(100,1400,0,0,400)Tmaxz=4X100+3X1400=4604、用单纯型法求解下面线性规划问题的解maxz=10 x+6x+4x123s.t.800/2=400500/1=5

23、00 x+x+x10012310 x+4x+5x6001232x+2x+6x0123得到等效的标准模型：解：加入松弛变量X,X,X,456maxz=10 x+6x+4x+0 x+0 x+0 x12x+x+x+x123410 x+4x+5x1232x+2x+6x123x0,j=1,2,.,656=100=600Vs.t.+x6=300100 x*=(丁,200丁,0,0,0,100)Tj列表计算如下：1064000CBXBbx1x2x3x4x5x69L0 x41001111001000 x5600(10)45010600 x630022600115000000010f640000 x4400(3

24、/5)1/21-1/100200/310 x16012/51/201/1001500 x618006/550-1/51150104501002f-10-106x2200/3015/65/3-1/6010 x1100/3101/6-2/31/600 x6100004-201220010620/310/32/30300-8/3-10/3-2/301002002200/.maxz=10Xr+6X5、用单纯型法求解下面线性规划问题的解MaxZ=4x-2x+2x1233x+x+x60TOC o 1-5 h z123x一x+2x101232x+2x一2x0123用单纯形法求解，并指出问题的解属于哪一类解：

25、（1）、将原问题划为标准形得：MaxZ=4x一2x+2x+0 x+0 x+0 x123456广3x+x+x+x=601234x一x+2x+x=1012352x+2x一2x+x=401236.x,x,x,x,x,x0123456Cj4-22000CBXBbx1x2x3x4x5x60 x4603111000 x5101-120100 x6402-22001j4-22000Cj4-22000CBXBbx1x2x3x4x5x60 x43004-51-304x1101-120100 x62004-60-21oj02-60-40Cj4-22000CBXBbx1x2x3x4x5x60 x4100011-1-

26、14x115101/201/21/4-2x2501-3/20-1/21/4oj00-30-3-1/2所以X=(15,5,0,10,0,0)T为唯一最优解MaxZ=4*15-2*5=506、用单纯形法求解下述LP问题。maxz二2.5x+x123x+5x1512s.t5x+2x012解：引入松弛变量x3、x4,化为标准形式:maxz二2.5x+x123x+5x+x二15123s.t25x+2x+x二101234构造单纯形表,计算如下：cj2.5cXEbx0 x1530 x105oj2.50 x3901009xxx5105201210019/513/545/192.5x1212/501/55j00

27、01/21x45/19015/193/192.5x20/19102/195/19j0001/2由单纯形表，可得两个最优解X二(2,0,9,0)T、X二(20/19,45/19,0,0)T，所以两点之间的所有解都是最优解，即最优解集合为：aX+(1-a)X，其中0a1。7、用单纯形法解线性规划问题maxz=2x+x15x22156x+2x2412x+x0 x012解：化为标准型maxz=2x+x+0 x+0 x+0 x123455x+x=15236x+2x+x=24124x+x+x=5125x01-5列出单纯形表c.21000cXbxx2x3xxox31505100ox424620104ox51

28、10015-Z021000ox3150510032x1411/301/60120 x5102/30-1/613/2-Z-801/30-1/300X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2-Z-20000-1/4-1/2Z*=17/2,X*=(7/2,3/2,15/2,0,0)8、用单纯型法求解下面线性规划问题的解解:maxz=x+x12x2x2122x+x2i2x+x0 x012c.11000CBXBbX1X2X3X4X50X3211210020X42-210100X54-11001-Z0110001X121-21000X460-3210

29、0X560-1101-Z-203-100把表格还原为线性方程maxz=3xx+223x2x+x=2123V3x+2x+x=6234x+x+x=6V235x=2+2x-x123Vx=6+3x2x423x=6+x-x523令X=03x=2+2x12Vx=6+3x42x=6+x52此时，若让X2进基，则会和基变量Xi同时增加，使目标函数值无限增长，所以本题无界9、用单纯型法求解下面线性规划问题的解maxz=2x+4x12x+2x812x41x0 x0I12c.24000cBXBbx1x2x3x4x50 x381210040 x44100100 x53010013-Z0240000 x321010-2

30、20 x441001044x2301001-Z-122000-42x121010-20 x4200-1124x2301001-Z-2000-2002x14100100 x5100-1/21/214x2011/2-1/20Z*=20,X*=(2,3,0,2,0)Z*=20,X*=(4,2,0,0,1)10、用单纯型法求解下面线性规划问题的解maxz=3x+15x2x141V2x2123x+2x0 x012解：列表如下C.35000cBXBbx1x2x3x4x50 x34101000 x4120201060 x518320019-Z0350000 x341010045x260101/200 x56

31、300-113 123 -Z-30300-5/200 x360011/3-1/35x220101/203x12100-1/31/3-Z-20000-3/2-1X*=(2,6,6,0,0)Z*=3611、用单纯型法求解下面线性规划问题的解maxz二2x+x12”5x15i6x+2x24St.12x+x012解：化为标准型maxz=2x+x12x+x=1513x+2x+x=24St.012345单纯型表如下：c.21000CXbxx2xxx0 x31505100一0 x4246201040 x55110015Z0210000 x3150510032x1411/301/60120 x102/30-1

32、/613/2Z001/30-1/300 x315/20015/4-15/22x17/21001/4-1/21xc3/2010-1/43/2Z17/2000-1/4-1/2由些可得，问题的最优解为X=7/2,x2=3/2，最优值maxz=17/212、用大M法求解如下线性规划模型：minz=5x2x4x1233x+x+2x4123v6x+3x+5x10123x,x,x0解：用大M法，先化为等效的标准模型：maxz/=5x2x4x123s.t.厂TOC o 1-5 h z HYPERLINK l bookmark154 3x+x+2x-x二412340,j二1,2,.,5j增加人工变量X、x，得到

33、：67maxz/=5x2x4xMxMx12367s.t3x+x+2x-x+x二412346701239x+5x+3x30123x,1x,x230minz=540 x450 x720 x解：用大M法，先化为等效的标准模型:maxz/=-540 x-450 x-720 x123s.t.厂3x+5x+9x-x二7012340,j二1,2,.,5j增加人工变量X、X,得到：67maXz/=-540X-450X-720X-MX-MXTOC o 1-5 h z12367s.t3x+5x+9x-x+x二70123460,j1,2,.,5j大M法单纯形表求解过程如下：-540-450-72000-M-MCBX

34、BbX1x2x3x4x5x6x79L-Mx670359-101070/3(9)30/9=10/-Mx730530-1013-12M-10M-12MMM-M-M12M-540f10M-45012M-720-M-M00-Mx660010/3(8)-11/31-1/360/8=2.5540X110/315/91/30-1/901/910/3/1/3=10-300+10/3M-8M-180-M-M/3+60-MM/3-600-150+10/3M8M-540fMM/3600M/3+60TOC o 1-5 h z720 x315/205/1211/81/241/81/24540 x15/61(5/12)0

35、1/241/81/241/8540572720135/2475/12135/275/215/2/5/12=185/6/5/12=2x3720450 x220/32112/5011/61/61/61/6101/103/101/103/10360-57001804507207515751500751575M15M0125f0135/2475/12135/2M75/2M20:该对偶问题的最优解是x*=(0,2,3，0，0)t最优目标函数值minz=(5700)=570014、用单纯形法求解线性规划问题maxz=-3x+x13x+x+x10 x0 x0123化成标准形式有maxz=3x+x+0 x+0

36、 x5134x+x+x+x=412342x+xxx=101-5加入人工变量则为maxz=3x+x+0 x+0 x一Mx一Mx134567”x+x+x+x=4i234一2x+x一x一x+x=1017列出单纯形表c.-30100-M-McBJXBbx1x2x3xx5xx70 x441111000-Mx1-21-10-110-Mx790310001-Z10M-2M-34M10-M000 x4330211-100 x21-21-10-110-Mx7660403-31-Z6M6M-304M+103M-4M00 x400001-1/2-1/21/20 x23011/30001/3-3x11102/301/

37、2-1/21/6-Z300303/2-M-3/2-M+1/20 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4-Z-M-1/4人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0)Z*=3/215、用单纯形法求解线性规划问题maxz=3x一2x”2x+11x22120 x012解化为标准形式有maxz=-3x-2x+0 x+0 x+Mx123452x+x+x=21233x+4xx+x=121245x015列表计算c.3200McBXBbx1x2x3x4x50 x322i1002Mx512340-11

38、3-Z-12M3M+34M+20-M0-2x2221100Mx54-50-4-11-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4)Z*=4M-4说明原问题无解写对偶问题(10)1、写出下列线性绘画问题的对偶问题maxz=2x+x+3x+xTOC o 1-5 h z1234厂x+x+x+x1134x,x0,x,x无约束1324解：mino=5y一4y+y123y+2y+y2123yy=1123123y+y=113y0,y无约束,y01232、写出下述线性规划的对偶问题maxz=x+4x+3x1232x+3x5x10 x11233y1+y301y02y3无约束3、写出下列线性规

39、划的对偶问题minz=25x+2x+3x123x+xx11232xx+x=1123x0 x0 x无约束J123解：maxw=y+y12+y3y+iy+22y3252y1y02y=3y无约束334、写出下列线性规划的对偶问题maxz=2x+x+4x1232x+3x+x11233xx+x40 x21233y-y112y+y+y=4123y0y无约束J123151515 151515 4 对偶性质1、已知线性规划问题如下：MaxZ=x+3x12I5x+10 x112x01/10y+y+y3123.y,y0;y0为严格不等式所以y广0132#X=（2,4）祇入原问题可知：x1+x21由对偶问题性质可知

40、：50y+4y=1413解之得：y1=1/5y2MinZ=1410y1+y3二3所以Y=（1/5,0，1）t2、已知线性规划问题minz=2x+3x+5x+6x1234x+2x+3x123v2x+xx+3x0（j二123,4）j用图解法求对偶问题的解；利用（b）的结果及对偶性质求原问题解。答案：（对偶问题的最优解为y*二（5,5）；（依据z*=w*及互补松弛性，有x=0，且2x+3x+5x=19/51234123452x一x+3x+x+x312345x0,j=1,2,5j已知其对偶问题的最优解为y;=yj，最优值为z*=5。试用对偶理论找出原问题的最优解。先写出它的对偶问题miXZ二4y1+3

41、y2s.t.y+2y2122y1+3y35y+y21231+y20将y1*,y2*的值代入约束条件，得，为严格不等式；设原问题的最优解为2x；=x4二0。因y；,y20；原问题的两个约束条,x*），由互补松弛性得x*二5件应取等式，故有3x*+x*=42x*+x*=3求解后得到x*=1,x=1;故原问题的最优解为2 #2 X*二10001；最优值为W*=5。4、已知下列问题的最优解为X*=(l/7,ll/7),用互补松弛定理求其对偶问题的最优解。LP:maxz=x+2x123x+x212x+2x312x一3x0解：第一步，写出对偶问题第二步，将LP,DP都化为标准型LP:maxz=x+2x12

42、1233y-y+y1i23y+2y3y20v1y02y03DP:minw=2y+3y+y3x+x+x=2121S一x+2x+x=30 x,0J1S2S3S第三步：将最优解代入标准型中，3y-y+y一y=1i231Sy+2y一3y一y=2011y02y03y,1S2S0DP:minw=2y+3y+y123确定松弛变量取值c111771c11F2x7713113x771Sx1Sx2S+x3Sx3S第四步：利用互补松弛定理Y*X=(Y*,Y*,Y*)23(X)1SX2SIX丿3S=Y*X11SFY*X22SFY*X33S=0Y*=03YX*=(YS1S,Y2S*=YX1S1*FYX*=02S2Y=0

43、Y=01S2S 第五步：将Y3*=0Y1S=0Y2S=0代入约束条件则有3yi-y2yi+2y2对偶问题的最优解为Y*=（4/7,5/7,0）maxz二x+x厂x11+22x2+x32x+xx01235、已知线性规划问题：，试用对偶理论证明上述线性规划问题无最优解。证明：首先看到该问题存在可行解，例如X=（000）,而上述问题的对偶问题为:minwi2y+y12一y1一2y21y+y10Iy1,y20由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。5、已知线性规划问题minz=2x+3x+5x+6x1234x+2x+3x+x22x+xx+3x0（ji1,2,3,4）4

44、j（1）（2）（3）解：（1）原线性规划问题可化为写出其对偶问题；用图解法求对偶问题的解；利用（2）的结果及对偶性质求原问题解。minzi2x+3x+5x+6x1234x+2x+3x+x21234s.t.31234x0(j=1,2,3,4丿j其对偶问题为：maxw=2y+3y12y+2y2122y-y312s.t.3y+y512y-3y61281用图解法解得Y*=（yi,y2）=（5,5）3）由互补松弛性定理知道，y-3y1219w*=-51231123x01-3解：先化为标准型maxz=-15x一24x一5x+0-x12346x+x一x=22345x+2x+x一x=11235x015约束条件

45、两边同乘(-1)TOC o 1-5 h z一6x一x+x=一2234一2x一x+x=一1235X*=(0,1/4,1/2)Y*=(7/2,3/2)列单纯形表c-15-24-500cBXBbx1x2x3x4x50 x4-20-6-1100 xE1-5-2-101-15-24-50045-240 x2x51/3-1/30-5101/62/3-1/6-1/301-150-1-4033/212-24x21/4-5/410-1/41/4-5xo1/215/2011/2-3/2-15/200-7/2-3/22、用对偶单纯形法解下列线性规划问题minz=4x+12x+18xTOC o 1-5 h z23x+

46、3x31353x0 HYPERLINK l bookmark104 V1-3解：改写为标准形式maxz=-4x112x18x+0 x+0 x2345x3x+x=3134v2x2x+x=523x0515列单纯形表如下：c.4121800cXbxx2x3xxox4310-310oxE50-2-201-4-12-180069ox4-3-10-310-12xc5/20110-1/2-40-60-64212-18-12x3X。13/21/3-1/30110-1/31/30-1/2-200-2-6X*=(0,3/2,1)Y*=(2,6)3、用对偶单纯形法求解下面的问题minz=12x+8x+16x+12x

47、2x1234+x+4x21232x+2x+4x3124x,x,x,x01234解：令z=-z，则问题可以标准化为:maxz=-12x-8x-16x-12x12342xx4x+x=212352x2x4x+x=31246x,x,x,x,x,x0123456取(P5P)=60）、1为初始基，则1丿（一2）一3）其余X,=0是非基可行解，但Y=CB-1是对偶可行解，建立单纯形表（见表4-1）B=0,最优值z=14.。X计算结果如下：最优解2X3X或最优解1X21其余Xj=。，最优值z=咏X)8本例如果用单纯形法计算,确定初始基可行解时，还需要引入两个人工变量3计算量要多于对欧单纯形法。表3-1：C-1

48、2一8一16-12009备注CBXBB-1bX1X2XX34X5X60X5-2-2一1一4010L=20X6一3-2-20(3013/4K=4-121612000X5X4-2-240102L=1-123/41/21/20101/43/2K=2一6-216003一8-12X2X421/4210402111/201/4L=2K=1或3-208023一8X101一4431-125X11/2104一211/2灵敏度分析1、已知线性规划的标准形式为maxz二一x+2x+x+0-x+0-x12345x+x+x+x-6123401一5其最优单纯形表如下C.-12100CBXBbx1x2x3x4x52x261

49、11100 x51030111Z1230120问：(1)当q由一1变为4时，求新问题的最优解(2)讨论C2在什么范围内变化时，原有的最优解仍是最优解解：由表可知，C1是非基变量的价值系数，因此q的改变只影响Q=c一z=(c+Ac)一CB-1p-(c一CB-1p)+Ac=+Ac=一3+5=2011111B11B1111可见最优性准则已不满足，继续迭代C.42100CXbxx2x3xx2x261111060 x5103011110/3Z12201202x28/3012/32/31/34x110/3101/31/31/3Z-56/3005/38/32/3(2)要使原最优解仍为最优解，只要在新的条件下

50、满足OW0成立，因为x2是基变量，所以所有的。值都将发生变化2o=CCB-1AB-(c,c,c,c,c)一CB-1(p,p,p,p,p)51012345B.(1*=(-1,c20，)-22；叩12oY113411一10-(T，c2，1，0，0)一(叮)(1311100111丿-(-1,c,1,0,0)-(c,c,c,c,0)22222-(-1c,0,1c,-c,0)0222一1-c02即1-C02-c02则C三1c+c1c-12222所以当x2的系数c22-1时，原最优解仍能保持为最优解。解：X=B-1(b+Ab)=B102_-13_1/30-2/33_-1_11-12二0112二500131

51、/301/3322已知线性规划问题及其最优单纯形表maxz=XX+4x123X+X+2x9i23X+XX2123X+X+X01-5最优单纯形表如下：c.23100CBXBbx1x2x3x4x52x1110-14-163xo2012-1110/3-Z-800-3-5-1若p由原来的31/3-7/3T1/101/3，最优解将如何改变(4-1丫1/10)仃/15)解：计算p=B-1p!_=33-11丿(1/3丿(7/30丿继续迭代a=(23门5=1/60I7/30丿C,23100CBXBbx1x2x3x4x52x11101/154-1153xo2017/30-1160/7-Z-8001/6-5-12

52、x13/71-2/7030/7-9/7151x360/70-30/71-30/7-30/760/7-Z-66/70-5/70-30/7-12/7X*=(3/7,0,60/7,0,0)Z*=66/7例4(仍以例2为例)已知线性规划问题及其最优单纯形表maxz=-x一x+4x123x+x+2x9123x+xx2123一x+x+x4123c.114000CBXBbx1x2x3xx5x1x11/31-1/301/30-2/30 x560200114x313/302/311/301/3-Z-170-40-10-2现增加一个新变量x7，且c7=3,p7=(3,l,-3)，求新问题的最优解。1/30-2/3

53、、解：由表知：B-1=011J/301/3丿=c-CB-1p7B=3-(-1,0,4)7=6“1/30-2/3勺、勺、=B一1p=70111=-2J/301/3丿一3丿0丿7继续迭代C.1140003CBXBbx1x2x3xx5xx71x11/31-1/301/30-2/330 x56020011-24x313/302/311/301/30-Z-170-40-10-263x71/91/3-1/901/90-2/910 x556/92/316/902/915/90 5、线性规划问题 4x313/302/311/301/30-Z-53/3-2-10/30-5/30-2/30X*=(0,0,13/3

54、,0,56/9,0,1/9)Z*=53/35已知线性规划问题及其最优单纯形表C114000CJXbxxxxxx2351x11/31-1/301/30-2/30 x560200114xo13/302/311/301/3-Z-170-40-10-2现增加新约束-3Xi+X2+6学17，求新问题的最优解。TOC o 1-5 h z113解：将原问题的最优解代入新增约束-3x3+0+6二=2517不满足新增加的约束条件，因此引入松弛变量x7后，新增约束变为-3X1+X2+6X3+X7-17，加进最优表得:C.1140000CBXBbx1x2x3xx5xx71x11/31-1/301/30-2/330

55、x56020011-24x313/302/311/301/300 x717-3160001-Z-170-40-10-201x11/31-1/301/30-2/300 x5602001104x313/302/311/301/300 x7-80-46-10-41-Z-170-40-10-20b/ajrj111/21x15/311/301/200-1/60 x54010-1/4101/44x311/301/311/4001/120 x20101/401-1/4-Z-130-20-1/200-1/2TOC o 1-5 h zX*=(5/3,0,ll/3,0,4,2,0)Z*=13maxZ=2xx+x1

56、23厂x+x+x6123x+2x0123用单纯形法求解得最终单纯形表如下表所示。x1x2x3x4x5x1611110XE1003111c-zjj10-3-1-20试说明分别发生如下变化时，新的最优解是什么？(l)目标函数变为maxZ=2xi+3x2+x3；2)约束条件右端项由变为增添一个新的约束-+2x32。2)因为B1=1011。所以B-1b=111111c.2-11000iCxbxx2x3xx2x3111100 x703111c-zjj10-3-1-20因为所有的检验数均小于等于零，故最优解为X*=(3,0,0,0,7)解：(1)c.231000iCxbxx2x3xx2x61111020

57、x10031110c-z01-1-202x18/3102/32/3-1/323Xc10/3011/31/31/30c-zjj100-4/3-7/3-1/3因为所有的检验数均小于等于零。故最优解为X*=(8/3,10/3,0,0,0)(3)由于一x+2x=6+2x0=62左右两端同时乘以“-1”并加上松弛变量x,136得到x一2x+x=一2136C.2-110000iCxbxx2x3xxx2x61111000 x100311100 x-210-2001C-Z0-3-1-2002x161111000 x100311100 x-80-1-3-101C-z0-3-1-2002x110/312/302/

58、301/30 x522/308/302/311/31x28/301/311/30-1/3C-zjj10-8/30-5/30-1/3因为所有的检验数均小于等于零，故最优解为X*二(10/3,0,8/3,0,22/3)第三章运输问题（15）1、安排一个使总运费最低的运输计划，并求出最低运费。一运-价-龙肖地产地TA1A2A3A4产量产161110950210761470312881130需求量30405030要求：先用最小元素法求出一个初始方案，再用闭回路法，求检验数。如果不是最优，改进为最优。解：1）先用最小费用法（最小元素法）求此问题的初始基本可行解：销产地用地A1A2A3A4Si611109

59、5030XX20210761470X2050X312881130X20X10dj30405030150150初始方案：Z=6X30+9X20+7X20+6X50+8X20+11X10=10702）用闭回路法，求检验数：费销*A1A2A3A4Si1611510595030XX20210-37614470X2050X312-48811130X20X10j该指派问题的最优方案就是上面用“最小费用法”求得的初始方案求出最小费用Z=6X30+9X20+7X20+6X50+8X20+11X10=10702、给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）B1B2B3B4siA1123410A2

60、876580A391011915dj82212181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）ii2）用闭回路法，求检验数:选x34作为入基变量迭代调整。用表上闭回路法进行迭代调整：j最优方案为:4822441220A2运销价产A】A2A3A4产量19129650273776036591150需求量40406020。要求：（i）用最小费用法建立运输计划的初始方案;用位势法做最优解检验；求最优解和最优方案的运费。最小运费Z=1X8+2X2+6X12+5X8+10X20g9X10=4143、下列是将产品从三个产地运往四