《运筹学习题库.pdf》由会员分享，可在线阅读，更多相关《运筹学习题库.pdf（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学习题库数学建模题（5）1、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲9437 0乙461 01 2 03 6 02 0 03 0 0试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为x l、x 2,则 x l、x 2 0,设 z是产品售后的总利润，则m ax z =7 0XI+1 2 0X2s.t.9x,+4X2 3604巧+6X22003X,+10X2 02、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量
2、原 材 料（吨/件）223 0 0 0 吨工 时（工时/件）52.54 0 0 0 工时零 件（套/件）15 0 0 套产品利润（元/件）43建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为、x2）设 z为产品售后总利润，则 m ax z=4 X+3 Xzs.t.2X|+2X2 30005/+2.5X2 4000%03、一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲11 021 0乙1426丙1564资源储备量1 0 06
3、0 03 0 0建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为XI、X2、X3,则 XI、X2、X3 0,设 Z 是产品售后的总利润，贝！Jm ax z =10XI+6X2+4X3%+%2 +%3 4 I。1 Ox1+4X2+5匕46002占 +2X2+6X3 04、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为2 5 k g,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镉绳索帐篷照相器材通信设备重量/
4、K g55261 224重要性系数2 01 51 81 4841 0试建立队员所能携带物品最大量的线性规划模型，不求解。解：引入0 1 变量的 生=1 表示应携带物品了,生=0表示不应携带物品/naxz-20 x,+15x2+18x3+14x4+8x5+4x6+l 0 x75X1+5X2+2X3+6 4 +1 2/+2X6+4X7 25Xj=0 或 l,i=1,2,.,75、工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：资、/品源ABC资源限量材 料（k g）1.51.242 5 0 0设 备（台时）31.61.21 4 0 0利
5、润（元/件）101112根据市场需求，预测三种产品最低月需求量分别是1 5 0、2 6 0、1 2 0,最高需求量是2 5 0、3 1 0、1 3 0,试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产A、B、C数量为七,2，/。MaxZ=10X1+14X2+12X3C 1.5x,+1.2X2+4X3 25003X I+1.6X2+1.2X3 1400150 Vxi 250260 x2 310120 x3 06、A、B两种产品，都需要经过前后两道工序，每一个单位产品A需要前道工序1小时和后道工序2 小时，每单位产品B需要前道工序2 小时和后道工序3 小时。可供利用的前道工序有 11小
6、时，后道工序有17小时。每加工一个单位产品B 的同时，会产生两个单位的副产品 C,且不需要任何费用，产 品 C 一部分可出售盈利，其余只能加以销毁。出 售 A、B、C的利润分别为3、7、2 元，每单位产品C的销毁费用为1元。预测表明，产品C最多只能售出 13个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产A、B数量为为,，销毁的产品C为七。MaxZ-3X|+7/+2(2/-x3)-x3“项+2X2 112X+3X2 172X2-X3 1307、靠近某河流有两个化工厂(参见附图)，流经第一化工厂的河流流量为每天500机3,在两个工厂之间有一条流量为200万/的支流。第一化工厂每
7、天排放有某种优化物质的工业污 水 2 万m 3 ,第二化工厂每天排放该污水1.4 万团之。从第一化工厂的出来的污水在流至第二化工厂的过程中，有 20%可自然净化。根据环保要求,河流中的污水含量不应大于0.2机这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000元/万加3,第二化工厂的为800元/万。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。附图：ai r 1 e r m500万加3 200万解：设第一化工厂和第二化工厂的污水处理量分别为每天当机3和X2万加3,m inZ =W O O%,+8 0 0尤2s
8、t1 X j 20.8 xl+1 2 M L 6x2 08、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3 种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。养物营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为玉、和七，则根据题意可得如下线性规划模型
9、:min z=2 5%1 +2 0 x2+4 5 x34 3 +6X2+2 0X3 8 0%+%+2X3 6 5s.t.7 02 1 M 4-7X2+3 5X3 4 5 0 xpx2,x3 0单位产品所需工时及本月四道工序可用生产时间如卜表所示:9、某公司生产的产品A,B,C 和 D 都要经过下列工序：刨、立铳、钻孔和装配。已知每刨立铳钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下:产品最少销售需要单位元/单位A1002B60
10、03C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别X 1,X 2,X 3,X 4 单位则应满足的目标函数为：max z=2 x,+3 x2+x3+x4满足的约束条件为：0.5Xj+x2+x3+OS%-18002X|+x2+x3+x4 28000.5X1+0.5X2+占+%30003X 1+x2+2X3+3X4 100 x2 600七 500 x4 4001 0、某航空公司拥有1 0 架大型客机、1 5 架中型客机和2架小型客机，现要安排从一机场到 4城市的航行计划，有关数据如表1-5,要求每天到D城 有 2 个 航 次（往返），到 A,B,C
11、城 市 各 4个 航 次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为1 8 小时,求利润最大的航班计划。解：设大型客机飞往A城的架次为XIA，中型客机飞往A城的架次为X 2A，小型客机飞往A城的架次为X 3 A，其余依此类推。客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d）A600050001大型B700070002C8000100005D100001800010A100030002中型B200040004C400060008D-20A200040001小型B350055002C600080006D-19资源限制派出的大型客机架次不能超过1 0 架，表示为+X
12、8+c+m-1同理%+%+”4 15X3A +X3B +X3C 2班次约束飞往各城的班次要满足X J/A+X3 A =4xtB+x2B+xiB=4XIC +X2C +X3C =4x1D+x2D+x3D=2非 负 性 约 束/2 0 且为整数；（i=l,2,3;j=A,B.C,D）目标函数为max z-1000 xw+0 x1B+2000 xlc+8000 x1D+2000 x2A+2000 x2g+2000X2C+2000%+2000 x3B+2000 x3C1 1、C R I S P 公司制造四种类型的小型飞机：A R I 型（具有一个座位的飞机）、A R 2型（具有两个座位的飞机）、A R
13、 4 型（具有四个座位的飞机）以及A R 6 型（具有六个座位的飞机）。A R 1和 A R 2一般由私人飞行员购买，而 A R 4 和 A R 6 一般由公司购买，以便加强公司的飞行编队。为了提高安全性，联邦航空局（F.A.A）对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进行的，因此小型飞机的制造是以月为单位进行的。表说明了 C R I S P 公司的有关飞机制造的重要信息。AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）8171115建 造 机所需要的时间（天）47911每架飞机所需要的生产经理数目1122每 架 机的盈利贡献（下美元）
14、6284103125C R I S P 公司下个月可以得到的生产经理的总数是6 0 人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9 架飞机。因此，下一个月可以得到的制造天数是27 0 天（9*3 0,每月按3 0 天计算）。J o n a tha n Ku rin g是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设玉表示下个月生产A R 1 型飞机的数目，表 示 A R 2 型，毛表示A R 4 型，表示A R 6 型目标函数：max z=62项 +84x2+103x3+125x44x1+7%+9x3+1 lx4 270%+2X3+2X4 6
15、0X j 8约束条件：X2 17X3 11X4 0士,工 2，工 3，4 为整数1 2、永辉食品厂在第一车间用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每月
16、最多能得到1 0 万单位。问如何安排生产，使工厂获利最大？解：设玉为产品A的售出量；为 A在第二车间加工后的售出量；须表示产品B的售出量；5表示B在第三车间加工后的售出量；/为第一车间所用原材料的数量，则目标函数为：max z=8X 1+9.5x,+7%+8x4-2.75x5约束条件：x5 1000003x2+2x4+1.5x5 0 化标准形式（5）1、将下列线性规划模型化为标准形式解：min z=-2 x,+3 x3*+x2+X3 W7X 一X2 +尤3 223 Y +X2+2%=-5x2 0均无约束ma x z=-%1 +2X2-3(x4-x5)+0 x6+0 -x7Xj+x2 4-x4-
17、x5+x6=玉 一+Xj 3%|x2 _ 2X3=芭-7 N 02、将下列线性规划模型化为标准形式725min z=+2x2+3 x3-2xt+x2+x3 44 x j 2/3 w =-6%1 0七无约束解：ma x z=x-2X2 3x3 +3 x32 x,+%2+七/一七”+冗4=93%|+x2+2鼻 2X3一%=44 x+2X9+3.-3 无3”=6x-5 2 03、将下列线性规划变为最大值标准形。min z=一3玉 +4 x2-2 x3+5 x4 9+2X3-X4=-2X1+尤2+3/-x4-1 4st 2.当,2，3 N O,乙无约束解:max z=3%j-4x2+2x3-5x4+5
18、x4st0 图 解 法(5)1、用图解法求解下面线性规划min z=-3XI+2X22X+4X2 22一 芭 +4X2 10,2xl-x2 7%)3X2 0解：可行解域为ab cd a,最优解为b 点。2xj+4X2=22由方程组 _ n解出xi=ii,xa=o、X2 U T.X*=(11,0)T1*2 JAmin z=-3X ll+2X O=-332、用图解法求解卜面线性规划min z=2XI+X2一$+4X2 85 Xj 0解:玉+工2 =84-解出 Xi=5,X 2=3 玉=5X J=(5,3)TX2JAmin z=Z*二 2X5+3=133、已知线性规划问题如下：M ax Z=x,+3
19、X2 5X J+10 x2 Ix2 0由图可知：5x,+10 x2=50 解之得：pq=2x2=4 x2=4 1则 ma x Z=2+3*4=1 44、用图解法求解下面线性规划问题max z=2玉+x25x(156尤1 +2X2 24x2+x2 0解：5、用图解法求解下面线性规划问题max z=2玉+3x2%1 +2X2 84x,16s.t.4%0,y=1,2图解如下：大值为 z*=2*4+3*2=14。二、单纯型法(15)1、用单纯型法求解下面线性规划问题的解max z=3XJ+3X2+4X33玉+4+640s t 16%+4%2+3%3466%,x2,x3 0解：加入松弛变量x”X 5,得
20、到等效的标准模型:max z=3X+3X2+4X3+0 xi+0 xss.列表C Bt.计 夸3 x j-+6 玉 TT如下X B-4X2+5,-4%2 +3.：0=1,bJ +Z 4 0r3+匕=6 62,.,53 3 4 0 0 x l x 2 x 3 x 4 x 50L00 x 4x 54 06 63 4 (5)1 06 4 3 0 182 20 0 0 0 03 3 4 t 0 040 x 3x 584 23/5 4/5 1 1/5 0(2 1/5)8/5 0 -3/5 14 0/31 01 2/5 1 6/5 4 4/5 03/5 t -1/5 0 -4/5 043x 3x l21
21、00 4/7 1 2/7 -1/71 8/2 1 0 -1/7 5/2 13 83 2 4/7 4 5/7 1/70 -3/7 0 -5/7 -1/7；.X*=(2、用单ma x z=s.t.解:加/0,0,2,0,0)T.ma x z=3 X 1 0+4 X 2 =3 8纯型法求解下面线性规划问题的解7 0 x i+1 2 0 x 29xi+4X2 3604*1+6X2 2003%1+10%2 0(松弛变量X”X ，X 5,得到等效的标准模型：ma x z=7 0 x 1+1 2 0 x 2+0 X 3+O x.)+0 X 59Xj+4x2+x3=3604xj+6X2+X4=2003xj+1
22、0 x2+*5=300 xj-0,j=1,2,.,5列表计算如下:3、用单纯型法求解下面线性规划问题的解C BX Bb7 0 x l1 2 0 x 20 x 30 x 40 x 50 L0 x 33 6 0941009 00 x 42 0 0460101 0 0/30 x 53 0 03(1 0)0013 0000007 01 2 0 t0000 x 32 4 03 9/5010-2/54 0 0/1 30 x 42 0(1 1/5)001-3/51 0 0/1 11 2 0 x 23 03/1 01001/1 01 0 03 61 2 0001 23 4 1000-1 20 x 31 8 6
23、 0/1 1001-3 9/1 11 9/1 17 0 x l1 0 0/1 11005/1 1-3/1 11 2 0 x 23 0 0/1 1010-3/2 22/1 14 3 0 0 07 01 2 001 7 0/1 13 0/1 11 1000-1 7 0/1 1-3 0/1 1*1 0 0X*=(，1 13 0 0 1 8 6 0，,0,1 1 1 10)T“1 0 0 3 0 0ma x z=7 0 X-1 2 0 X-=1 1 1 14 3 0 0 01 1ma x z=4 x j3 x 2 S.t.”2x,+2x2 30005$+2.5X2 4000的 0解：加入松弛变量X3,
24、X4,X5,得到等效的标准形式:+2X2+=3000ma x z=4X1+3X2+0 X3+0 x4+0 X 5 S.t.5x+2.5X2+乙=4000 xx+x5=500Xj0,j=1,2,.,5用表解形式的单纯形法求解，列表计算如下:max z=10 x1+6x2+4x34 3 0 0 0C BX Bb0 LX】x2 x3 x4 x50X33 0 0 02 2 10 03 0 0 0/2 =1 5 0 00X44 0 0 05 2.5 0 1 04 0 0 0/5 =8 0 00X55 0 0(1)0 0 0 15 0 0/1 =5 0 00 0 0 0 04 t 3 0 0 00X32
25、0 0 00 2 1 0 -22 0 0 0/2 =1 0 0 00X41 5 0 00 (2.5)0 1 -51 5 0 0/2.5 =6 0 04X15 0 01 0 0 0 14 0 0 0 40 3 t 0 0 -40X38 0 00 0 1 -0.8 (2)8 0 0/2 =4 0 03X26 0 00 1 0 0.4 -24X15 0 01 0 0 0 15 0 0/1 =5 0 04 3 0 1.2 -20 0 0 -1.2 2 t0X54 0 00 0 0.5 -0.4 13X21 4 0 00 1 1 -0.4 04X.1 0 01 0 -0.5 0.4 04 3 1 0.4
26、 04 6 0 00 0 -1 -0.4 0据上表，X*=(1 0 0,1 4 0 0,0,0,4 0 0)ma x z=4 X 1 0 0+3 X 1 4 0 0=4 6 04、用单纯型法求解下面线性规划问题的解s.t.否 +%2+%31 0010%1+4+0,j=1,2,.,6列表计算如下：10 6 4 0 0 0CBX BbOLxl x2 x3 x4 x5 x60 x410011110 01000 x5600(10)450 1 0600 x63002 2 6 0 0 11500 0 0 0 0 010 f 6 4 0 0 00 x4400(3/5)1/2 1 -1/1 0 0200/31
27、0 xl601 2/5 1/2 0 1/10 01500 x61800 6/5 5 0-1/5 115010 4 5 0 1 00 2 t-1 0-1 06x2200/30 1 5/6 5/3-1/6 010 xl100/31 0 1/6-2/3 1/6 00 x61000 0 4-2 0 1220010 6 20/3 10/3 2/3 0300-8/3 -1 0/3 -2/3 0100200.X*=（亍3,0,0,100)1100200 2200/.max z=10X-+6X33 3Max Z=4 X j-2X2+2X3r 3%|+x2+x3 60X -x2 4-2X3 10+2X2-2X3
28、 400用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：MaxZ=4/-2X2+2x3+0 x4+0 x5+0 x6,3工+工2+%3+尤4=60X -x2+2X3+15=102X+2X2-2X3+X6=40Cj4-22000CBXBb修x2X3尤 4%06 031110001 0 1-12010044 02-22001%4-22000Cj4-22000CBX“bX x2x3匕40X43 004-51-304修1 01-12010042 00 4-60-2102-60-40C,4-22000CBXBbx2X3X4X50100011-1-14不15101/201/21
29、/4-2x2501-3/20-1/21/400-30-3-1/2所以X=(15,5,0,10,0,0)T 为唯一最优解Max Z=4*15-2*5=506、用单纯形法求解下述L P问题。max z=2.5X+x23%1+5X2 155再 +2X2 0解：引入松弛变量七、%,化为标准形式:maxs.t.z=2.5/+x23%1+5+x3=155*+2X2+X4=10 x,x2,x3,x4 0构造单纯形表，计算如下:J2.5100aCBXBb玉x2X3X40X315351050X4105201242.51000X39019/51-3/545/192.5*212/501/55%000-1/2145/
30、19015/19-3/192.520/1910-2/195/19000-1/2由单纯形表，可得两个最优解X=(2,0,9,01、X=(2 0/1 9,4 5/1 9,0,0)、所以两点之间的所有解都是最优解，即最优解集合为：aX+(1 a)X，其中0以W 1。7、用单纯形法解线性规划问题ma x z=2%+x2 1 56 x j+2X2 2 4斗+x2 0解：化为标准型ma x z=2项+w+0 x3+0 x4+0 x55 x,+x3=1 56匹+2X2+x4=2 4+x2+%5 =5%i.5 2 0列出单纯形表Cj21000CBXBbXX2A 3XX50Xz15051000X24620104
31、0X55110015-z0210000150510032X411/301/60120XR102/30-1/613/2-z-801/30-1/300X31 5/20015/4-1 5/22X7/21001/4-1/21X23/2010-1/43/2-Z-2 0000-1/4-1/2Z*=1 7/2,X*=(7/2,3/2,1 5/2,0,0)8、用单纯型法求解下面线性规划问题的解maxz=X1+/2西-2X2 22%1+X2 2x+X20 x2 0解:C j11000CBXBbXX2x3为不0X32 1 1 210020必2-210100X54-11001-z0110001X21-21000X6
32、0-32100X560-1101-z-203-100把表格还原为线性方程max z=3X2 +2X|-2X2+X3-23X2+2与+x4=6-2+X3+X5=6$=2+2X2-x3（冗4=6+3X2-2X3x5=6+X2-X3令%3=0%1 =2+2X2 x4=6+3X2x5=6+X2此时，若让X 2进基，则会和基变量XI同时增加，使目标函数值无限增长，所以本题无界9、用单纯型法求解下面线性规划问题的解max z=2%+4x2%1 +2X2 8X 4x2 0 x2 0Z*=2 0,X*=(2,3,0,2,0)Z*=2 0,X*=(4,2,0,0,1)1 0、用单纯型法求解下面线性规划问题的解C
33、 j24000CBXBbXXlX3Xs0照81210040X4100100Xs301 0013-z0240000照21 010-220X41001044X2301001-z-1 22000-42X21010-20X200-1124X2301001-z-2 000-2002X4100100照100-1/21/214Xt2011/2-1/20-z-2 000-200max z=3x+5x2%42X2 123X+2X2 0解：列表如下C j35000CBXBbXX2冬XiX50X-341010001 202 01060A 51 8320019-z035000X*=(2,6,6,0,0)Z*=3 61
34、 1、用单纯型法求解下面线性规划问题的解0不41010045X260101/200篇63 00-113-Z-3 0300-5/200X360011/3-1/35X220101/203X2100-1/31/3-z-2 0000-3/2-1max z=2%+x25%|15st.6再 +2X2 24x2+x2 0解：化为标准型max z=2芭 +x2st.0单纯型表如卜.:C j21000CBXBbXX2X3Xi照0X31 505100-0X42 46 201040X55110015Z0210000X31 50510032Xi411/301/601 20X5102/3 0-1/613/2z001/3
35、0-1/300X31 5/20015/4-1 5/22Xi7/21001/4-1/21X23/2010-1/43/2z1 7/2000-1/4-1/2山些可彳导，问题的最优解为x =7 X2=3/2,最优值m a x z=1 7/21 2、用大M 法求解如下线性规划模型：m i nz=5XI+2X2+4X33 X1 +.+2%3 4 1 0 xi,x2,x3 0解：用大M法，先化为等效的标准模型:max z=-5 x i-2x2-4x3s.t.3%+%2 +2%3 _%4=46%1+3%2+5%3 5=1 匕 0,J =1,2,.,5增加人工变量加、X 7,得到：m a xz 二 一 5 x
36、i-2 x 2-4x 3-MX6-Mx 7s.t3 玉 +%2 +2%3 4 +%6 =46 玉 +3%2 +5X3-X5+%7 =1 0Xj 2 0,/=1,2,.,7大 M 法单纯形表求解过程如下：5 2 4 0 0 M-MC BXBb0 Lx l x 2 x 3 x 4 x 5 x 6 x 7-Mx 64(3)1 2-101 04/3-Mx 71 06 3 5 0 -1 0 15/3-9 M-4M-7 M M M-M -M9 M-5 f 4M-2 7 M-4-M -M 0 0-5x l4/31 1/3 2/3 -1/3 0 1/3 0-Mx 720 1 1 (2)-1 -2 11-5 -
37、M-5/3 -M-1 0/3 -2 M+5/3 M 2 M-5/3 -M0 M-l/3 M-2/3 2 M-5/3 t -M -3 M+5/3 0-5x l5/31 1/2 5/6 0 -1/6 0 1/61 0/30 x 410 (1/2)1/2 1 -1/2 -1 1/22-5 -5/2 -2 5/6 0 5/6 0 -5/60 1/2 t 1/6 0 -5/6 -M -M+5/6-5x l2/31 0 1/3 -1 1/3 1 -1/3-2x 220 1 1 2-1-215 2-1 1/311/3-1-1/322T0 0-1/3-1-1/3-M+1-M+1/3/.x*=2(-,2,0,0
38、,0)T最优目标函数值m i n z=m a x z=(-)=一3 31 3、用大M法求解如下线性规划模型：m i nz=540XI+450X2+7 2 0 x 33%+5X2+9刍 2 7 0 3 0%,尤2，龙3 2 0解：用大M法，先化为等效的标准模型：m a x z=-540XI450X2720X3s.t.3%+5%+9/一%4=7 00,j =1,2,.,5增加人工变量X 6、X7,得到:m a x z=-5 40 x 1 45 0 x 27 2 0 x 3Mx(i Mx 7s.t3 X+5+M-4 +JC6=7 09 x,+5%2+3X3-x5+%7 =3 0X.0,J =1,2,
39、.,5C BXB大M法Eb自纯形表求解过程如下：-5 40 -45 0 -7 2 0 0 0 -M -Mx l x 2 x 3 x 4 x 5 x 6 x 70L-M-Mx 6x 77 03 03 5 9 -1 0 1 0(9)5 3 0 -1 0 17 0/33 0/9=1 0/31 2 M 1 0 M 1 2 M M M M M1 2 M-5 40 f 1 0 M-45 0 1 2 M-7 2 0 -M -MOO-Mx 66 00 1 0/3 (8)-1 1/3 1 -1/36 0/8=2.510/3/1/3-540 xl10/31 5/9 1/3 0-1/9 0 1/9=10-300+1
40、0/3M-8M-180-M-M/3+60-M M/3-600-150+10/3M 8M-540 f M M/3-60 0-M/3+6015/2/5/1-720 x315/20 5/12 1 -1/8 1/24 1/8-1/2 42=18-540 xl5/61 (5/12)0 1/24-1/8 -1/2 4 1/85/6/5/12二 2-540-572-720-135/2 475/12-135/2-7 5/20 125 t 0 135/2-475/12 135/2-M 75/2-Mx320/3-1 0 1 1/6 1/6 1/6-1/6一 720-450 x2212/5 1 0 1/10-3/1
41、 0 -1/1 0 3/10-360-450-720 75 15-7 5 -1 5一 5700-180 0 0-7 5 -1 5 75-M 15-M20.该对偶问题的最优解是X*=(0,2,0,0)最优目标函数值min z=-(-5700)=570014、用单纯形法求解线性规划问题max z=-3X+x3玉+x2+W4 +X2 七 13X2+X3 =9x.00 x.Q化成标准形式有max z=-3的 +x3+0 x4+Ox5$+x,+x3+x4=42%1 +%*5=1V3X2+x3=9/t-5 2 0加入人工变量则为max z=_3X|+x3+0 x4+0 x5 Mxb Mx1X|+x2+x3
42、+x4=4 2 ji+%2-X3 X 5+4 =13X2+X3+毛=9,X1-7-0列出单纯形表C j-30100-M-MCBXBbXX2X3Xi照X6Xi0用41111000-M施1-21-10-110Xi90310001-z1 0 M-2 M-34M10-M000X i330211-100Xz1-21-10-110-MXi66 0403-31-z6 M6 M-304M+103 M-4M00X00001-1/2-1/21/20X23011/30001/3-3X1102/3 01/2-1/21/6-z300303/2-M-3/2-M+l/20X00001-1/21/2-1/20X?5/2-1/
43、2100-1/41/41/41%3/23/20103/4-3/41/4-z-3/2-9/2000-3/4-M+3/4-MT/4人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0)Z*=3/21 5、用单纯形法求解线性规划问题max z=-3 2x22x1 4-X212xROx2 0解化为标准形式有m a x z=-3x-2x2+Ox3+Ox4+Mx52x1+x2+x3=23芭 +4X2-匕+毛=1 2 写对偶 问 题(1 0)1、写出下列线性绘画问题的对偶问题m a x z=2为 +%+3 x3+x4X|+x2 4-x3+x4 1X1,X32 0,%2，工4无约束解:m i n
44、 0 =5%-4y2+y3J i +y2+y3 2H -2 =1,月 +3 y 2 一%2 3%+为=1 2 0,力无约束,y 3 V o2、写出卜述线性规划的对偶问题max z=*+4X2+3x32x+3X2 5当W2一X2+6七1X 1 +x2 4-=4-0X2 3=3J?02 0 x2 0X3无约束解:4、写出下列线性规划的对偶问题max w=M+%+为f+%+2乃2 2 0%无约束max z=2xt+x2+4x32xl+3X2+13X j-九2+x3 0 x2对偶性质1、已知线性规划问题如下：Ma x Z=Xj+3X25 xl+10 x2 1x2 0I已知该问题的解为(2,4)利用对偶
45、性质写出对偶问题的最优解。解：该问题的对偶问题为：MinZ=5 0 y l +为+4y 3+为 2 1 3，乃？0；乃 4将乂=(2,4)T代入原问题可知：为+乙 1为严格不等式，所以为=。山对偶问题性质可知：”50%+4%=14 解之得：，y,=1/5,1 0%+乃=3 为=2v 2 X+X2-七+3X4 W -3勺 2 0 (j =l,2,3,4)用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。一，8 1、答案：(对偶问题的最优解为丫=(-,-)；(依据Z*二瞬及互补松弛性，有禹二 0,且2xj+3X2+5X3=1 9/5 xx+2X2+3X3=22%j -x2+/=3解得愿
46、问题最优解=(7/5,0,1/5,0)o3、已知线性规划问题m i n 6 9 =2 x,4-3x2+5x3+2x4+3 x5s.t.xi+/+2X3+Z+3X5 42xl-x2 4-3X3+x4+x5 3.N O,j =1,2,-,5*4*3 *已知其对偶问题的最优解为=y,y2=-,最优值为z=5。试用对偶理论找出原问题的最优解。解先写出它的对偶问题m a x%=4必+3 y 2s-1.乃+2为42 y,-y23 5 y,+y2 0；原问题的两个约束条件应取等式，故有3 x；+x；=42 x：+x；=3求解后得到x：=l,匕=1；故原问题的最优解为X*=1 0 0 0 1 ；最优值为w*=
47、5。4、已知下列问题的最优解为X*=(l/7,11/7),用互补松弛定理求其对偶问题的最优解。D P:m i n w=2 y +3y2+y3LP:m a x z=X+2 x23%-为+%2 13 X+x2 2M +2 y 2-3%2 2一 九i+2X2 3玉一 3X2 2 N O为2 0 xl,x2 0解：第一步，写出对偶问题第二步，将 LP,DP都化为标准型LP:m a x z=$+2X2 DP:m i n w=2y+3 y2+y33%j +x2+Xs =23乃-乃+为-J i s =1一2 +2%2+%2S=3X+2 y 2 -3 y 3 _ y 2 s =2X-3X2+%3S=1x l,
48、x 2 0%1S，2 s，3S-0.0*0 y30 加，2 2 0第三步：将最优解代入标准型中，确定松弛变量取值第四步：利用互补松弛定理 1 1 13 x +M、7 7 1 5=2X =01 -1 1 一+2 x3 =2 S=07 7 2 s1 1 13 x +7 7 3 53 9=1飞=7 X/y *Xs =（X*,八*，八*）x?s=y,*X +为*X2S+L*X3S=0.K*=0%X*=（%，%）X,*=*+身2*=0*Ks=O%s=0第五步：将*=0 压=0心=0 代入约束条件则有，3y -%=17 1+2为=25力=亍，对偶问题的最优解为性=(4/7,5/7,0)ma x z =X
49、+工25、已知线性规划问题：一/再 +X27 +X o3v 2%+x”x2,x3 0述线性规划问题无最优解。2,i -2y2 1%+为 2 1必一为 2 0J，乃？由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。5、一知线性规划问题min z=2工+3x2+5x3+6 x4x+2X2+3X3+x4 22X|+犬？一九3+3工4 -3X j 2 0 0 =1,2,3,4)(1)写出其对偶问题；(2)用图解法求对偶问题的解；(3)利 用(2)的结果及对偶性质求原问题解。解：(1)原线性规划问题可化为：min z =2玉+3x2+5x3+6 x4s.t.22X|x2+3X4
50、 3.20(j=l,2,3,4)其对偶问题为:ma x w =2y1+3%s.t.+2%22 y L y 2 w 33到 +%W 5y,-3y2 6.%，%2 0（2）用图解法解得丫*=（%,必）=（*/=（3）由互补松弛性定理知道，.%一3%=1 1解：先化为标准型max z=-15x,-24x2-5x3+0-x4+0-x56X2+5工1+2X2+x3-x4=23-5=1x,_5 0约束条件两边同乘(T)62 一七+尤4=-2 3 5尤解：改写为标准形式max z*=-4x 12x2-18x3+0-x4+0-x5X|-3X3+z=3v 22 213+/=5.X-2 0列单纯形表如下:-4-1