《运筹学》题库.pdf

运筹学习题库运筹学习题库数学建模题（数学建模题（5 5）1、某厂生产甲、乙两种产品，这两种产品均需要A、B、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：甲乙A94360B46200C31030070120试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为x1、x2，则 x1、x20，设 z 是产品售后的总利润，则max z=70 x1+120 x2.9 9x x1 1 4 4x x2 2 360360 4 4x x1 1 6 6x x2 2 200200 3 3x x1 1 1010 x x2 2 300300 x x1 1，x x2 2 0 02、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：原材料（吨/件）工时（工时/件）零件（套/件）产品利润（元/件）甲乙2 251 4 3可用量3000 吨4000 工时500 套建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为x1 1、x2 2，设 z 为产品售后总利润，则max z=4x1 1+3x2 2.2x1 2x2 30005x 2.5x 400012x 5001x1,x2 03 3、一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：甲乙技术服务11劳动力104行政管理22单位利润106丙资源储备量1100560063004建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则 x1、x2、x30，设 z 是产品售后的总利润，则max z=10 x1+6x2+4x3.x1 x2 x310010 x 4x 5x 6001232x12x26x3300 x1，x2，x3 04、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号物品重量/Kg重要性系数152025153218461451286照相器材247通信设备410食品氧气冰镐绳索帐篷试建立队员所能携带物品最大量的线性规划模型，不求解。解：引入 01 变量xi,xi=1 表示应携带物品i，,xi=0 表示不应携带物品Inaxz 20 x115x218x314x48x5 4x610 x75x15x2 2x3 6x412x5 2x6 4x7 25xi 0或1,i 1,2,.,75、工厂每月生产 A、B、C 三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：资源产品ABC资源限量材料（kg）1441225001400设备（台时）3利润（元/件）10根据市场需求，预测三种产品最低月需求量分别是150、260、120，最高需求量是 250、310、130，试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产 A、B、C 数量为x1,x2,x3。MaxZ 10 x114x212x31.5x11.2x2 4x3 25003x11.6x21.2x31400150 x1 250260 x2 310120 x3130 x1,x2,x3 06、A、B 两种产品，都需要经过前后两道工序，每一个单位产品A 需要前道工序 1 小时和后道工序 2 小时，每单位产品 B 需要前道工序 2 小时和后道工序 3 小时。可供利用的前道工序有 11 小时，后道工序有 17 小时。每加工一个单位产品 B 的同时，会产生两个单位的副产品 C，且不需要任何费用，产品 C 一部分可出售盈利，其余只能加以销毁。出售 A、B、C的利润分别为 3、7、2 元，每单位产品C 的销毁费用为 1 元。预测表明，产品C 最多只能售出 13 个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产 A、B 数量为x1,x2,销毁的产品 C 为x3。MaxZ 3x1 7x2 2(2x2 x3)x3x1 2x2112x13x2172x2 x313x1,x2,x3 07、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天 500m，在两个工厂之间有一条流量为200 万m的支流。第一化工厂每天排放有某种优化物质的工业污水 2 万m，第二化工厂每天排放该污水万m。从第一化工厂的出来的污水在流至第二化工厂的过程中，有 20%可自然净化。根据环保要求，河流中的污水含量不应大于%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000 元/万m，第二化工厂的为 800 元/万m。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少列出数学模型，不求解。附图：工厂 1工厂 2333333 500 万m 200 万m解：设第一化工厂和第二化工厂的污水处理量分别为每天x1m和 x2万m，3333min Z 1000 x1800 x21 x1 20.8x x 1.612stx21.4x1,x2 08、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这 3 种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物营养成分ABCD甲4112125乙610720丙20233545至少需要的营养成分数量806570450价格问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为x1、x2和x3，则根据题意可得如下线性规划模型：minz 25x1 20 x2 45x3 4x16x2 20 x380 x x 2x 65123s.t.x13x3 7021x 7x 35x 450231x1,x2,x3 09、某公司生产的产品 A，B，C 和 D 都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：ABC刨立铣.钻孔装配.D可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下：产品ABCD最少销售需要单位100600500400元/单位2314问该公司该如何安排生产使利润收入为最大（只需建立模型）解：设生产四种产品分别x1,x2,x3,x4单位则应满足的目标函数为：max z=2 x1+3 x2+x3+x4满足的约束条件为：0.5x1 x2 x30.5x418002x x x x 280012340.5x10.5x2 x3 x4 30003x1 x22x33x4 6000 x1100 x2 600 x3 500 x 400410、某航空公司拥有10 架大型客机、15 架中型客机和 2 架小型客机，现要安排从一机场到 4 城市的航行计划，有关数据如表1-5，要求每天到D 城有 2 个航次（往返），到A,B,C城市各 4 个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18 小时，求利润最大的航班计划。客机类型大型到达城市ABCDABCDABCD飞行费用（元/次）60007000800010000100020004000-200035006000-飞行收入（元/次）500070001000018000300040006000-400055008000-飞行时间（h/d）125102482012619中型小型解：设大型客机飞往 A 城的架次为 x1A，中型客机飞往 A 城的架次为 x2A，小型客机飞往 A城的架次为 x3A，其余依此类推。资源限制派出的大型客机架次不能超过10 架，表示为x1A x1B x1C x1D10同理x2A x2B x2C15x3A x3B x3C 2班次约束飞往各城的班次要满足x1A x2A x3A 4x1B x2B x3B 4x1C x2C x3C 4x1D x2D x3D 2非负性约束xij 0且为整数；（i=1,2,3;j=A,B,C,D）目标函数为maxz 1000 x1A0 x1B2000 x1C8000 x1D+2000 x2A2000 x2B2000 x2C2000 x3A2000 x3B2000 x3C11、CRISP 公司制造四种类型的小型飞机：AR1 型（具有一个座位的飞机）、AR2 型（具有两个座位的飞机）、AR4 型（具有四个座位的飞机）以及 AR6 型（具有六个座位的飞机）。AR1和 AR2 一般由私人飞行员购买，而AR4 和 AR6 一般由公司购买，以便加强公司的飞行编队。为了提高安全性，联邦航空局（）对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进行的，因此小型飞机的制造是以月为单位进行的。表说明了 CRISP 公司的有关飞机制造的重要信息。联邦航空局的最大产量（每月生产的飞机数目）建造飞机所需要的时间（天）每架飞机所需要的生产经理数目每架飞机的盈利贡献（千美元）AR184162AR2177184AR41192103AR615112125CRISP 公司下个月可以得到的生产经理的总数是 60 人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30，每月按 30 天计算）。Jonathan Kuring 是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设x1表示下个月生产 AR1 型飞机的数目，x2表示 AR2 型，x3表示 AR4 型，x4表示 AR6型目标函数：max z 62x184x2103x3125x44x17x29x311x4 270 x1 x22x32x4 60 x18约束条件：x217x311x415x1,x2,x3,x4 0 x1,x2,x3,x4为整数12、永辉食品厂在第一车间用1 单位原料 N 可加工 3 单位产品 A 及 2 单位产品 B，产品A 可以按单位售价 8 元出售，也可以在第二车间继续加工，单位生产费用要增加6 元，加工后单位售价增加 9 元。产品 B 可以按单位售价 7 元出售，也可以在第三车间继续加工，单位生产费用要增加 4 元，加工后单位售价可增加6 元。原料 N 的单位购入价为 2 元，上述生产费用不包括工资在内。3 个车间每月最多有 20 万工时，每工时工资元，每加工 1 单位 N 需要工时，若A 继续加工，每单位需3 工时，如B 继续加工，每单位需2 工时。原料N 每月最多能得到 10 万单位。问如何安排生产，使工厂获利最大解：设x1为产品 A 的售出量；x2为 A 在第二车间加工后的售出量；x3表示产品 B 的售出量；x4表示 B 在第三车间加工后的售出量；x5为第一车间所用原材料的数量，则目标函数为：max z 8x19.5x27x38x42.75x5x51000003x 2x 1.5x 200000245约束条件：x1 x23x5 0 x x 2x 0534x1,x2,x3,x4,x5 0化标准形式（化标准形式（5 5）1、将下列线性规划模型化为标准形式解：min z x12x23x3 x1x 13x1x1 0 x2x37x2x32x22x35x2 0 x3无约束maxz x12x23(x4 x5)0 x60 x7 x1x2x4 x5 x67x x x x x 2124572x353x1x2x17 02、将下列线性规划模型化为标准形式min z x12x23x32x13x 14x1x1 0解：x2x39x22x342x23x36x2 0 x3无约束maxz x12x23x33x3x3x3 x492x1x23x x 2x 2x x 4123353x33x364x12x2x15 03、将下列线性规划变为最大值标准形。min z 3x14x22x35x44x1 x22x3 x4 2x x 3x x 141234st2x13x2 x32x4 2x1,x2,x3 0,x4无约束解：max z 3x14x22x35x45x44x1 x22x3 x4 x4 2x1 x23x3 x4 x4 x514st2x13x2 x32x42x4 x6 2x,x,x,x,x,x x 0123445,6图解法（图解法（5 5）1、用图解法求解下面线性规划min z=3x1+2x22x14x2 22 x 4x 10122x1 x2 7x 3x 121x1,x2 0解：可行解域为 abcda，最优解为 b 点。2 2x x1 1 4 4x x2 2 2222由方程组 解出 x=11，x=0 x x 0 02 2 x1X=x=（1111，0 0）212*Tmin z=31111+20 0=332、用图解法求解下面线性规划min z=2x1+x2x14x2 24x x 8125 x110 x2 0解：从上图分析，可行解域为abcde，最优解为 e 点。由方程组x1 x28x 5解出 x1=5，x2=31xX*=1Tx=（5，3）2min z=Z*=25+3=133、已知线性规划问题如下：Max Z=x13x25x110 x2 50 x1 x21x2 4x1,x2 0用图解法求解，并写出解的情况解：x2 6 Z 4 x2=4 2Zx10 2 4 6 8 105x1+10 x2=50 x1+x2=1由图可知：5x110 x2 50解之得：x1 2x2 4x2 4则 max Z=2+3*4=144、用图解法求解下面线性规划问题maxz 2x1 x25x1156x 2x 242st.1x2 x2 5x1,x2 0解：5、用图解法求解下面线性规划问题max z 2x13x2x12x284x 161s.t4x212xj 0,j 1,2图解如下：可知，目标函数在 B(4,2)处取得最大值，故原问题的最优解为X (4,2)，目标函数最大值为z*T 2*4 3*2 14。二、单纯型法（二、单纯型法（1515）1、用单纯型法求解下面线性规划问题的解max z=3x1 1+3x2 2+4x3 33x1 4x25x3 406x 4x23x3 66.1x,x，x 0123解：加入松弛变量 x4，x5，得到等效的标准模型：max z=3x1 1+3x2 2+4x3 3+0 x4+0 x53x1 4x25x3 x4 40 x5 66.6x1 4x23x3x 0,j 1,2,.,5j列表计算如下：CB004 404 43 3XBx4x5x3x5x3x1b40668422103x136033/5（21/521/5）12/53/501 1338380*T3x244034/58/516/51/54/78/2124/73/74x3（5 5）3 3041 10 04010400 x410001/53/54/54/52/71/75/75/70 x5010001001/75/211/71/7L82240/310X=（10，0，2，0，0）max z=max z=310+42=38=382、用单纯型法求解下面线性规划问题的解max z=70 x1+120 x2 9 9x x1 1 4 4x x2 2 360360 4 4x x1 1 6 6x x2 2 200200.3 3x x 1010 x x 3003002 2 1 1 x x1 1，x x2 2 0 0解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z=70 x1+120 x2+0 x3+0 x4+0 x5.360360 9 9x x1 1 4 4x x2 2 x x3 3 x x4 4 200200 4 4x x1 1 6 6x x2 2 x x5 5 300300 3 3x x1 1 1010 x x2 2 x xj j 0 0,j j 1 1,2 2,.,.,5 5 列表计算如下：CB0000012012007070120120XBx3x4x5x3x4x2x2x3x1x1x2x2b36020030024020301860/11100/11300/1170 x194307039/5（11/511/5）3/10363401 10700120 x246（1010）0120001 1120000112000 x31000010000100000 x4010000100039/11 5/11-3/22170/11-170/110 x500100-2/5-3/5 1/10121219/11-3/11 2/1130/1130/11L90100/330400/13100/111004300011X=（*1003001860T，0，0）11111110030043000+120+120=111111max z=70max z=703、用单纯型法求解下面线性规划问题的解2x1 2x2 30005x 2.5x 400012max z=4x1 1+3x2 2.x 5001x1,x2 0解：加入松弛变量 x3 3，x4 4，x5 5，得到等效的标准形式：2x1 2x2 x3 30005x 2.5x x 4000124max z=4x1 1+3x2 2+0 x3 3+0 x4 4+0 x5 5.x x 50051xj 0,j 1,2,.,5用表解形式的单纯形法求解，列表计算如下：4CBXBbx1 125（1 1）0 4 4001 1400014000143x2 220032（）（）00 3 301 103001030 x3 3100001000010000110 x4 4010000100000 x5 500100-2-514-4（2 2）-21-2 2 21 1000L000004034034x3 3x4 4x5 5x3 3x4 4x1 1x3 3x2 2x1 1x5 5x2 2x1 130004000500200015005008006005004001400100460046003000/2 =15004000/5 =800500/1 =5002000/2 =10001500/=600800/2 =400500/1 =50000-10*T据上表，X=（100，1400，0，0，400）max z=max z=4100+31400=460=4604、用单纯型法求解下面线性规划问题的解max z=10 x1+6x2+4x3.x1 x2 x310010 x 4x 5x 6001232x12x26x3300 x1，x2，x3 0解：加入松弛变量 x4，x5，x6，得到等效的标准模型：max z=10 x1+6x2+4x3+0 x4+0 x5+0 x6100 x1 x2 x3 x410 x 4x 5x x 6001235.2x 2x 6x x6300231xj 0,j 1,2,.,6列表计算如下：CB0000101006 610100XBx4x5x6x4x1x1x6x2x2x1x1x6b1006003004060180200/3100/310010 x11（1010）201001 101000101006x2142064x3156040 x410000100005/30 x5010001/101/101/5111/61/602/32/30 x6001000010000100L10060150200/3150150（3/53/5）1/22/56/5421 100601/25515/61/62/3422200320/310/38/3 10/3100200TX=（，0，0，0，100）33*2002200100max z=max z=10+6=3335、用单纯型法求解下面线性规划问题的解Max Z 4x1-2x2 2x33x1 x2 x3 60 x1 x2 2x3102x1 2x2 2x3 40 x1,x2,x3 0用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：MaxZ 4x1 2x2 2x3 0 x4 0 x5 0 x63x1 x2 x3 x4=60 x1 x2 2x3 x5102x1 2x2 2x3 x6 40 x1,x2,x3,x4,x5,x6 0Cj4b-22000CBXB000 x1x21x312222x4x51000001000 x600100 x4x5x6603101-140244b-2-2-2jCjCBXB040 x1x24-14x3-52-6x4x5100-31-2x6001x4x1x6300101200jCj04b2-2-6200-4000CBXB04-2x1x20010 x311/2x4x510-11/2x6-11/4x4x1100151500Tx2-3/20-1/21/4-30-3-1/2j所以 X=（15，5，0，10，0，0）为唯一最优解Max Z=4*15-2*5=506 6、用单纯形法求解下述 LP 问题。max z 2.5x1 x23x15x215s.t5x12x210 x,x 012解：引入松弛变量x3、x4，化为标准形式：max z 2.5x1 x23x15x2 x315s.t5x12x2 x410 x,x,x,x 01234构造单纯形表，计算如下：cj100cB00XBb1510 x135x252119/5x31001x40103/5ix3x45245/19j0 x390 x12102/50100005/192/1901/51/23/195/191/25j1x2x145/1920/19010(1)j由单纯形表，可得两个最优解X(2,0,9,0)T、X(2)(20/19,45/19,0,0)T，所以(1)两点之间的所有解都是最优解，即最优解集合为：X7、用单纯形法解线性规划问题(1)X(2)，其中0 1。max z 2x1 x25x26x 2x12x2x1x1 0解：化为标准型15 24 5x2 0maxz 2x1 x20 x30 x40 x55x26x 2x12x2x1列出单纯形表CjCB000020XBb1524501541-821000453123/2 x315 x4 24 x55x15 0 x106120100 x2521151/32/31/3x310001000 x4010001/6-1/6-1/3x500100010 x3x4x5-Zx3x1x5-Z021x3x1x2-Z15/27/23/2-200100001010005/41/4-1/4-1/4-15/2-1/23/2-1/2Z*=17/2,X*=(7/2,3/2,15/2,0,0)8、用单纯型法求解下面线性规划问题的解maxz x1 x22x2 x12x x12x2 x1x1 0解：CjCB000100XBb2240266-2110002 2 2 4x2 0 x11-2-111000 x212111-2-3-13x31000121-1x401000100 x500100010 x3x4x5-Zx1x4x5-Z把表格还原为线性方程maxz 3x2 x3 2x12x23x2 x2 x3 2x3 x3 x4 x5 2 6 6x12 2x2x463x2x 6 x25令x 3=0 x3 2x3 x3x12 2x2x463x2x 6 x25此时，若让x2进基，则会和基变量x1同时增加，使目标函数值无限增长，所以本题无界9 9、用单纯型法求解下面线性规划问题的解max z 2x14x2 x12x2x1x2x1 0CjCB000004204204XBb8430243-12223-20412-202400043248 4 3x2 0 x11102110210001000 x22014001000100010 x3100010001-10-20-1/21/2-2x401000100010011/2-1/20 x50010-201-4-22100100 x3x4x5-Zx3x4x2-Zx1x4x2-Zx1x5x2-ZZ*=20,X*=(2,3,0,2,0)Z*=20,X*=(4,2,0,0,1)10、用单纯型法求解下面线性规划问题的解max z 3x15x2 x12x23x12x2x1 0解：列表如下CjCB000XBb4121803500069 41218x2 0 x11033x20225x31000 x40100 x50010 x3x4x5-Z050053x3x2x5-Z466-30622-2010330010010001001000100001/2-1-5/21/31/2-1/3-3/20010-1/301/3-143x3x2x1-ZX*=(2,6,6,0,0)Z*=3611、用单纯型法求解下面线性规划问题的解maxz 2x1 x25x1156x 2x 242st.1x2 x2 5x1,x2 0解：化为标准型max z 2x1 x25x1 x3156x 2x x 24124st.x2 x2 x5 5x1,x2,x3,x4,x5 0单纯型表如下：CjCB000020021XBx3x4x5Zx3x1x5Zx3x1x2Zb1524501541015/27/23/217/221000453123/2x1061201000100 x2521151/32/31/30010 x3100010001000 x4010001/6-1/6-1/35/41/4-1/4-1/4x500100010-15/2-1/23/2-1/2由些可得，问题的最优解为x1=7/2，x2=3/2，最优值 max z=17/212、用大 M 法求解如下线性规划模型：min z=5x12x24x33x1 x22x3 46x13x25x310 x,x,x 0123解：用大用大 M M 法法，先化为等效的标准标准模型：/max z =5x12x24x3.3x1 x2 2x3 x4 4 x5106x13x25x3y 0,j 1,2,.,5j增加人工变量 x x6 6、x x7 7，得到：/max z =5x12x24x3Mx x6 6Mx x7 73x1 x2 2x3 x4 x6 4 x5 x7106x13x25x3x 0,j 1,2,.,7jCBM MM M5M5052大 M 法单纯形表求解过程如下：52XBbx1x2x6x7x1x1x7x7x1x1x4x4x1x1x2x24104/325/312/32（3 3）69M9M51 1050105010134M4M21/31-M5/3M1/31/2（1/21/2）5/21/201 14x3257M7M42/310 x410MM1/3（2 2）0 x501MM01MM1/61/25/65/61/31M Mx610M01/322M5/33M+5/3010M12M Mx701M001-M01/61/25/6M+5/61/31L4/35/3110/32-M10/3-2M+5/3M2/32M5/35/61/225/61/61/3101 10012502011/31/3111/31/31M+11/3M+1/3223*2x=（，2，0，0，0）3T最优目标函数值 min z=min z=max z=（13、用大大 M M 法法求解如下线性规划模型：min z=540 x1450 x2720 x3/2222）=333x15x29x3 709x15x23x3 30 x,x,x 0123解：用大用大 M M 法法，先化为等效的标准标准模型：/max z =540 x1450 x2720 x3.3x15x29x3 x4 70 x5309x15x23x3y 0,j 1,2,.,5j增加人工变量 x6、x7，得到：/max z =540 x1450 x2720 x3Mx6Mx73x15x29x3 x4 x6 70 x5 x7309x15x23x3x 0,j 1,2,.,5jCBM MM MM大 M 法单纯形表求解过程如下：540450XBbx1x2x6x7x67030603（9 9）12M5510M720 x39312M0 x410MM10 x501MM1/3M Mx610M01M Mx701M01/3L70/330/9=10/360/8=12M54010M45012M720010/3（8 8）540 x110/31 105/91/30MM1/9M/3+60M/3600M01/9M/360M/3+6010/3/1/3=10-300+10/3M-8M180-150+10/3M8M-540720 x315/205/1211/81/241/8540 x1720450 x3x25/620/3215400112/5360（5/125/12）57212501450001/241/81/2415/2/5/11/242=185/6/5/121/8=2720135/2475/12135/275/20135/2475/12135/2M M75/2M M1072001/61/1075751/63/1015151/61/107575M M1/63/101515M M5700570018020该对偶问题的最优解是x=（0，2，0，0）3*T最优目标函数值 min z=min z=（57005700）=5700=570014、用单纯形法求解线性规划问题maxz 3x1 x3 x12x 1x1 0化成标准形式有x2x34x2x313x2x39x2 0 x3 0maxz 3x1 x30 x40 x5x2 x12x x 123x2x15 0加入人工变量则为x3x3x3x4 x5 419maxz 3x1 x30 x40 x5Mx6Mx7x2 x12x x 123x2x17 0列出单纯形表CjCB0-M-M00-M00-3001XBb41910M3166M031305/23/2-3/230100M-Mx3x3x3x4 x5 x6 41 x7 9x11-20-2M-33-266M-300100-1/23/2-9/2x21134M010001000100 x31-1112-144M+101/32/330010 x41000100010001000 x50-10-M1-133M-1/201/23/2-1/2-1/43/4-3/4x60100-11-3-4M-1/20-1/2-M-3/21/21/4-3/4-M+3/4001001x7x4x6x7-Z0 x4x2x7-Z01/21/31/6-M+1/2-1/21/41/4-M-1/4x4x2x1-Zx4x2x3-Z人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0)Z*=3/215、用单纯形法求解线性规划问题max z 3x12x22x1x23x 4x12x1 0解化为标准形式有 212x2 0max z 3x12x20 x30 x4 Mx5x2 x32x13x 4x x x1245x15 0列表计算CjCB0M-2MXBb212-12M244-4M3200M23 212x1233M+32-5-5M-1x2144M+2100 x31001-4-4M-2x40-1-M0-1-Mx5010010 x3x5-Zx2x5-ZX*=(0,2,0,0,4)Z*=4M-4说明原问题无解写对偶问题（写对偶问题（1010）1、写出下列线性绘画问题的对偶问题max z 2x1 x23x3 x4 x1 x2 x3 x4 52x x 3x 4123x x x 1341x1,x3 0,x2,x4无约束解解：min 5y1 4y2 y3y1 2y2 y3 21y1 y2y13y2 y3 3y y311y1 0,y2无约束,y3 02、写出下述线性规划的对偶问题max z x1 4x23x35x322x13x23x x26x311x2x34x1x1 0 x2 0 x3无约束解minw 2y1 y24y3 2y13y 15y1y1 03y2y26y2y2 0y3y314y33y3无约束3、写出下列线性规划的对偶问题min z 25x12x23x3x2x31 x1x 2x x3112x312x1x2x1 0 x2 0 x3无约束解：maxw y1 y2 y3 y1y 1 y1y1 0y22y2y2y2 02y3y3y3y3无约束25234 4、写出下列线性规划的对偶问题max z 2x1 x24x3x312x13x23x x2x341x33x1x1 0 x2 0 x3无约束解解minw y14y23y32y13y 1y1y1 03y2y2y2y2 0y321y34y3无约束对偶性质对偶性质1、已知线性规划问题如下：Max Z=x13x25x110 x2 50 x1 x21x2 4x1,x2 0已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为：MinZ 50y1 y2 4y35y1 y2110y1 y2 y3 3y1,y3 0;y2 0将 X=（2，4）代入原问题可知：x1 x21 为严格不等式，所以y2 0T由对偶问题性质可知：50y1 4y314解之得：y11/510y1 y3 3y2 0y31所以 Y=（1/5，0，1）2、已知线性规划问题TMin Z=14min z 2x13x25x3 6x4 x1 2x23x3 x4 2 2x1 x2 x33x4 3xj 0(j 1,2,3,4)用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。答案答案：(对偶问题的最优解为Y*8 1(,)；5 5(依据 z*=w*及互补松弛性，有x4=0,且2x13x25x319/5x1 2x23x3 22x x x 3231解得愿问题最优解X*=(7/5,0,1/5,0)。3 3、已知线性规划问题min 2x1 3x2 5x3 2x4 3x5s.t.x1 x2 2x3 x43x5 42x1 x23x3 x4 x5 3xj 0,已知其对偶问题的最优解为y1的最优解。解先写出它的对偶问题max*j 1,2,54*3,y2，最优值为z*5。试用对偶理论找出原问题55z 4y13y2 .y1 2y2 2y1 y2 32y13y3 5y1 y2 23y1 y2 3y1,y2 0将y1,y2的值代入约束条件，得，为严格不等式；设原问题的最优解为*,y2 0；原问题的两个约束x*(x1,x5)，由互补松弛性得x2 x3 x4 0。因y1*条件应取等式，故有*3x1 x5 4*2x1 x5 3*求解后得到x11,x51；故原问题的最优解为X10*001；最优值为w*5。4、已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。DP:minw 2y13y2 y3LP:max z x12x23x1 x2 2 x 2x 312x13x21x1,x2 0解：第一步，写出对偶问题第二步，将 LP，DP 都化为标准型3y1y 1y1 0y22y2y2 0y33y3y3 012LP:maxz x1 2x2 x1S 23x1 x2 x 2x x2S 312 x3S1x13x2x1S,2S,3S 0 x1,x2 0DP:minw 2y13y2 y33y1y 1y1 0y22y2y2 0y33y3y3 0 y1S1 y2S 2y1S,2S 0第三步：将最优解代入标准型中，确定松弛变量取值111 x1S 2377x1S 0111 2 x 3x2S 02S7739111x3S x3S17737第四步：利用互补松弛定理 X1SY*XS(Y1*,Y2*,Y3*)X2S Y1*X1SY2*X2SY3*X3S 0X3SY3*=0X1*YSX*(Y1S,Y2S)X*Y1SX1*Y2SX2*02Y1S=0Y2S=0第五步：将Y3*=0Y1S=0Y2S=0代入约束条件则有3y1 y214y17y1 2y2 2y257对偶问题的最优解为Y*=(4/7,5/7,0)maxz x1 x25 5、已知线性规划问题：x12x1x,1x2x3x3021x2x2,x3，试用对偶理论证明上述线性规划问题无最优解。证明：证明：首先看到该问题存在可行解，例