《运筹学》题库12954.pdf

《《运筹学》题库12954.pdf》由会员分享，可在线阅读，更多相关《《运筹学》题库12954.pdf（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、甲 乙 可用量 原材料（吨/件）工时（工时/件）零件（套/件）2 2 5 1 3000 吨 4000 工时 500 套 产品利润（元/件）4 3 建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为 x1、x2，设 z 为产品售后总利润，则 max z=4x1+3x2.0,50040005.253000222112121xxxxxxx 3、一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务 劳动力 行政管理 单位利润 甲 1 10 2 10 乙 1 4 2

3、 6 丙 1 5 6 4 资源储备量 100 600 300 建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为 x1、x2、x3，则 x1、x2、x30，设 z 是产品售后的总利润，则 max z=10 x1+6x2+4x3.03006226005410100321321321321xxxxxxxxxxxx，4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号 1 2 3 4 5

4、6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10 试建立队员所能携带物品最大量的线性规划模型，不求解。解：引入 01 变量xi,xi=1 表示应携带物品i，,xi=0 表示不应携带物品I 7,.,2,1,10254212625510481418152076543217654321ixxxxxxxxxxxxxxxnaxzi或 5、工厂每月生产 A、B、C 三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：A B C 资源限量 材料（kg）4 2500 设备

5、（台时）3 1400 利润（元/件）10 14 12 根据市场需求，预测三种产品最低月需求量分别是 150、260、120，最高需求量是 250、310、130，试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产 A、B、C 数量为321,xxx。321121410 xxxMaxZ 250042.15.1321xxx 产 品 资 源 14002.16.13321xxx 2501501 x 3102602 x 1301203 x 0,321xxx 6、A、B 两种产品，都需要经过前后两道工序，每一个单位产品 A 需要前道工序 1 小时和后道工序 2 小时，每单位产品 B 需要前道工序

6、2 小时和后道工序 3 小时。可供利用的前道工序有 11 小时，后道工序有 17 小时。每加工一个单位产品 B 的同时，会产生两个单位的副产品 C，且不需要任何费用，产品 C 一部分可出售盈利，其余只能加以销毁。出售 A、B、C的利润分别为 3、7、2 元，每单位产品 C 的销毁费用为 1 元。预测表明，产品 C 最多只能售出 13 个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产 A、B 数量为,21xx销毁的产品 C 为3x。33221)2(273xxxxxMaxZ 11221 xx 173221 xx 13232 xx 0,321xxx 7、靠近某河流有两个化工厂（参见

7、附图），流经第一化工厂的河流流量为每天 5003m，在两个工厂之间有一条流量为 200 万3m的支流。第一化工厂每天排放有某种优化物质的工业污水 2 万3m，第二化工厂每天排放该污水万3m。从第一化工厂的出来的污水在流至第二化工厂的过程中，有 20%可自然净化。根据环保要求，河流中的污水含量不应大于%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是 1000 元/万3m，第二化工厂的为 800 元/万3m。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少列出数学模型，不求解。附图：工厂 1 工厂 2 500 万3m 200 万3m 解：

8、设第一化工厂和第二化工厂的污水处理量分别为每天1x3m和 x2万3m，218001000minxxZ st0,4.16.18.021212211xxxxxx 8、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这 3 种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。甲 乙 丙 至少需要的营养成分数量 A 4 6 20 80 B 1 1 2 65 C 1 0 3 70 D 21 7 35 450 价格 25 20 45 问：消费者怎么购买营

9、养物，才能既获得必要的营养成分，而花钱最少只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为321xxx和、，则根据题意可得如下线性规划模型：0,45035721703652802064.452025min32132131321321321xxxxxxxxxxxxxxtsxxxz 9、某公司生产的产品 A，B，C 和 D 都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨 立铣 钻孔 装配 A B .C 营养物 营养成分 D 可用生产时间（小时）1800 2800 3000 6000 又知四种产品对利润贡献及本月最少销售需要单位

10、如下：产品 最少销售需要单位 元/单位 A 100 2 B 600 3 C 500 1 D 400 4 问该公司该如何安排生产使利润收入为最大（只需建立模型）解：设生产四种产品分别 x1,x2,x3,x4单位 则应满足的目标函数为：max z=2 x1+3 x2+x3+x4 满足的约束条件为：123412341234123412340.50.51800228000.50.530003236000100600500400 xxxxxxxxxxxxxxxxxxxx 10、某航空公司拥有 10 架大型客机、15 架中型客机和 2 架小型客机，现要安排从一机场到 4 城市的航行计划，有关数据如表 1-

11、5，要求每天到 D 城有 2 个航次（往返），到 A,B,C城市各 4 个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为 18 小时，求利润最大的航班计划。客机类型 到达城市 飞行费用（元/次）飞行收入（元/次）飞行时间（h/d）大型 A 6000 7000 8000 10000 5000 7000 10000 18000 1 2 5 10 B C D 中型 A 1000 2000 4000-3000 4000 6000-2 4 8 20 B C D 小型 A 2000 3500 6000-4000 5500 8000-1 2 6 19 B C D 解：设大型客机飞往 A 城的架

12、次为 x1A，中型客机飞往 A 城的架次为 x2A，小型客机飞往 A城的架次为 x3A，其余依此类推。资源限制 派出的大型客机架次不能超过 10 架，表示为 111110ABCDxxxx 同理 222333152ABCABCxxxxxx 班次约束 飞往各城的班次要满足 1231231231234442AAABBBCCCDDDxxxxxxxxxxxx 非负性约束 0ijx 且为整数；（i=1,2,3;j=A,B,C,D）目标函数为 111222333max100002000200020002000200020002000ABCABCABCzxxxxxxxxx1D8000 x+11、CRISP 公

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

14、理数目 每架飞机的盈利贡献（千美元）8 4 1 62 17 7 1 84 11 9 2 103 15 11 2 125 CRISP 公司下个月可以得到的生产经理的总数是 60 人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30，每月按 30 天计算）。Jonathan Kuring 是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设1x表示下个月生产 AR1 型飞机的数目，2x表示 AR2 型，3x表示 AR4 型，4x 表示 AR6型 目标函数：1234max6284103125zxxx

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

16、时工资元，每加工 1 单位 N 需要工时，若 A 继续加工，每单位需 3 工时，如 B 继续加工，每单位需 2 工时。原料 N 每月最多能得到 10 万单位。问如何安排生产，使工厂获利最大 解：设1x为产品 A 的售出量；2x为 A 在第二车间加工后的售出量；3x表示产品 B 的售出量；4x表示 B 在第三车间加工后的售出量；5x为第一车间所用原材料的数量，则目标函数为：12345max89.5782.75zxxxxx 约束条件：524512534512345100000321.52000003020,0 xxxxxxxxxxx xx xx 化标准形式（5）1、将下列线性规划模型化为标准形式

17、解：2、将下列线性规划模型化为标准形式 解：3、将下列线性规划变为最大值标准形。12341234123412341234min34254223142322,0,zxxxxxxxxxxxxstxxxxx xxx 无约束 解：无约束3213213213213210063244239232minxxxxxxxxxxxxxxxz无约束321321321321321005232732minxxxxxxxxxxxxxxxz05232700)(32max713217542165421765421xxxxxxxxxxxxxxxxxxxxz06 33244 2239 2 332max51332153321433

18、213321xxxxxxxxxxxxxxxxxxxz1234412344123445123446123445,6max3425542231423222,0zxxxxxxxxxxxxxxxxstxxxxxxx x x xxx x 图解法（5）1、用图解法求解下面线性规划 min z=3x1+2x2 0,137210422422121212121xxxxxxxxxx 解：可行解域为 abcda，最优解为 b 点。由方程组02242221xxx 解出 x1=11，x2=0 X*=21xx=（11，0）T min z=311+20=33 2、用图解法求解下面线性规划 min z=2x1+x2 0105

19、8244212121xxxxxx 解：从上图分析，可行解域为 abcde，最优解为 e 点。由方程组 58121xxx 解出 x1=5，x2=3 X*=21xx=（5，3）T min z=Z*=25+3=13 3、已知线性规划问题如下：Max Z=213xx 5010521xx 121 xx 42x 0,21xx 用图解法求解，并写出解的情况 解：x2 6 Z 4 x2=4 2 Z x1 0 2 4 6 8 10 5x1+10 x2=50 x1+x2=1 由图可知：5010521xx 解之得：21x 42x 42x 则 max Z=2+3*4=14 4、用图解法求解下面线性规划问题 12112

20、2212max25156224.5,0zxxxxxstxxx x 解：5、用图解法求解下面线性规划问题 121212max 2328416.4120,1,2jzxxxxxstxxj 图解如下：可知，目标函数在 B(4,2)处取得最大值，故原问题的最优解为*(4,2)TX，目标函数最大值为*2*43*214z。二、单纯型法（15）1、用单纯型法求解下面线性规划问题的解 max z=3x1+3x2+4x3.0,6634640543321321321xxxxxxxxx，解：加入松弛变量 x4，x5，得到等效的标准模型：max z=3x1+3x2+4x3+0 x4+0 x5.5,.,2,1,06634

21、64054353214321jxxxxxxxxxj 列表计算如下：CB XB b 3 3 4 0 0 L x1 x2 x3 x4 x5 0 x4 40 3 4（5）1 0 8 0 x5 66 6 4 3 0 1 22 0 0 0 0 0 3 3 4 0 0 4 x3 8 3/5 4/5 1 1/5 0 40/3 0 x5 42（21/5）8/5 0 3/5 1 10 12/5 16/5 4 4/5 0 3/5 1/5 0 4/5 0 4 x3 2 0 4/7 1 2/7 1/7 3 x1 10 1 8/21 0 1/7 5/21 38 3 24/7 4 5/7 1/7 0 3/7 0 5/7

22、1/7 X*=（10，0，2，0，0）T max z=310+42=38 2、用单纯型法求解下面线性规划问题的解 max z=70 x1+120 x2.0300103200643604921212121xxxxxxxx，解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z=70 x1+120 x2+0 x3+0 x4+0 x5.5,.,2,1,03001032006436049521421321jxxxxxxxxxxj 列表计算如下：CB XB b 70 120 0 0 0 L x1 x2 x3 x4 x5 0 x3 360 9 4 1 0 0 90 0 x4 200 4 6 0

23、 1 0 100/3 0 x5 300 3（10）0 0 1 30 0 0 0 0 0 70 120 0 0 0 0 x3 240 39/5 0 1 0-2/5 400/13 0 x4 20（11/5）0 0 1 -3/5 100/11 120 x2 30 3/10 1 0 0 1/10 100 36 120 0 0 12 34 0 0 0 12 0 x3 1860/11 0 0 1 39/11 19/11 70 x1 100/11 1 0 0 5/11-3/11 120 x2 300/11 0 1 0-3/22 2/11 1143000 70 120 0 170/11 30/11 0 0 0

24、-170/11 30/11 X*=（11100，11300，111860，0，0）T max z=70 11100+12011300=1143000 3、用单纯型法求解下面线性规划问题的解 max z=4x1+3x2.0,50040005.253000222112121xxxxxxx 解：加入松弛变量 x3，x4，x5，得到等效的标准形式：max z=4x1+3x2+0 x3+0 x4+0 x5.5,.,2,1,050040005.2530002251421321jxxxxxxxxxj 用表解形式的单纯形法求解，列表计算如下：CB XB b 4 3 0 0 0 L x1 x2 x3 x4 x5

25、 0 x3 3000 2 2 1 0 0 3000/2 =1500 0 x4 4000 5 0 1 0 4000/5 =800 0 x5 500（1）0 0 0 1 500/1 =500 0 0 0 0 0 4 3 0 0 0 0 x3 2000 0 2 1 0-2 2000/2 =1000 0 x4 1500 0（）0 1-5 1500/=600 4 x1 500 1 0 0 0 1 4 0 0 0 4 0 3 0 0-4 0 x3 800 0 0 1 （2）800/2 =400 3 x2 600 0 1 0 -2 4 x1 500 1 0 0 0 1 500/1 =500 4 3 0 -2

26、 0 0 0 2 0 x5 400 0 0 1 3 x2 1400 0 1 1 0 4 x1 100 1 0 0 4600 4 3 1 0 0 0-1 0 据上表，X*=（100，1400，0，0，400）T max z=4100+31400=460 4、用单纯型法求解下面线性规划问题的解 max z=10 x1+6x2+4x3.03006226005410100321321321321xxxxxxxxxxxx，解：加入松弛变量 x4，x5，x6，得到等效的标准模型：max z=10 x1+6x2+4x3+0 x4+0 x5+0 x6.6,.,2,1,030062260054101006321

27、53214321jxxxxxxxxxxxxxj 列表计算如下：CB XB b 10 6 4 0 0 0 L x1 x2 x3 x4 x5 x6 0 x4 100 1 1 1 1 0 0 100 0 x5 600（10）4 5 0 1 0 60 0 x6 300 2 2 6 0 0 1 150 0 0 0 0 0 0 10 6 4 0 0 0 0 x4 40 0（3/5）1/2 1 1/10 0 200/3 10 x1 60 1 2/5 1/2 0 1/10 0 150 0 x6 180 0 6/5 5 0 1/5 1 150 10 4 5 0 1 0 0 2 1 0 1 0 6 x2 200/

28、3 0 1 5/6 5/3 1/6 0 10 x1 100/3 1 0 1/6 2/3 1/6 0 0 x6 100 0 0 4 2 0 1 32200 10 6 20/3 10/3 2/3 0 0 0 8/3 10/3 2/3 0 X*=（3100，3200，0，0，0，100）T max z=103100+63200=32200 5、用单纯型法求解下面线性规划问题的解 3212x2x-4xMax Z 603321xxx 102321xxx 40222321xxx 0,321xxx 用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：654321000224xxxxx

29、xMaxZ 43213xxxx=60 1025321xxxx 402226321xxxx 0,654321xxxxxx jC 4-2 2 0 0 0 BC BX b 1x 2x 3x 4x 5x 6x 0 4x 60 3 1 1 1 0 0 0 5x 10 1-1 2 0 1 0 0 6x 40 2-2 2 0 0 1 j 4-2 2 0 0 0 jC 4-2 2 0 0 0 BC BX b 1x 2x 3x 4x 5x 6x 0 4x 30 0 4-5 1-3 0 4 1x 10 1-1 2 0 1 0 0 6x 20 0 4-6 0-2 1 j 0 2-6 0-4 0 jC 4-2 2 0

30、 0 0 BC BX b 1x 2x 3x 4x 5x 6x 0 4x 10 0 0 1 1-1-1 4 1x 15 1 0 1/2 0 1/2 1/4-2 2x 5 0 1-3/2 0-1/2 1/4 j 0 0-3 0-3-1/2 所以 X=（15，5，0，10，0，0）T 为唯一最优解 Max Z=4*15-2*5=50 6、用单纯形法求解下述 LP 问题。12121212max 2.53515.5210,0zxxxxstxxx x 解：引入松弛变量3x、4x，化为标准形式：121231241234max 2.53515.5210,0zxxxxxstxxxx x x x 构造单纯形表，计

31、算如下：jc 1 0 0 i Bc BX b 1x 2x 3x 4x 0 3x 15 3 5 1 0 5 0 4x 10 5 2 0 1 2 j 1 0 0 0 3x 9 0 19/5 1 3/5 45/19 1x 2 1 2/5 0 1/5 5 j 0 0 0 1/2 1 2x 45/19 0 1 5/19 3/19 1x 20/19 1 0 2/19 5/19 j 0 0 0 1/2 由单纯形表，可得两个最优解(1)(2,0,9,0)TX、(2)(20/19,45/19,0,0)TX，所以两点之间的所有解都是最优解，即最优解集合为：(1)(2)(1)XX，其中01。7、用单纯形法解线性规划

32、问题 解：化为标准型 列出单纯形表 Cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 15 24 5 0 6 1 5 2 1 1 0 0 0 1 0 0 0 1 4 5 -Z 0 2 1 0 0 0 0 2 0 x3 x1 x5 15 4 1 0 1 0 5 1/3 2/3 1 0 0 0 1/6-1/6 0 0 1 3 12 3/2 -Z-8 0 1/3 0-1/3 0 00524261552max212121221xxxxxxxxxz0524261550002max515214213254321xxxxxxxxxxxxxxz0 2 1 x

33、3 x1 x2 15/2 7/2 3/2 0 1 0 0 0 1 1 0 0 5/4 1/4-1/4-15/2-1/2 3/2 -Z-20 0 0 0-1/4-1/2 Z*=17/2,X*=(7/2,3/2,15/2,0,0)8、用单纯型法求解下面线性规划问题的解 解：Cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 2 2 4 1-2-1 12 1 1 1 0 0 0 1 0 0 0 1 2 -Z 0 1 1 0 0 0 1 0 0 x1 x4 x5 2 6 6 1 0 0-2-3-1 1 2 1 0 1 0 0 0 1 -Z-2 0 3-

34、1 0 0 把表格还原为线性方程 66232223max53243232132xxxxxxxxxxxz 325324321623622xxxxxxxxx 令x 3=0 25242163622xxxxxx 此时，若让x2进基，则会和基变量x1同时增加，使目标函数值无限增长，所以本题无界 9、用单纯型法求解下面线性规划问题的解 0042222max2121212121xxxxxxxxxxz Cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 8 4 3 1 1 0 2 0 1 1 0 0 0 1 0 0 0 1 4 3 -Z 0 2 4 0 0 0

35、 0 0 4 x3 x4 x2 2 4 3 1 1 0 0 0 1 1 0 0 0 1 0-2 0 1 2 4 -Z-12 2 0 0 0-4 2 0 4 x1 x4 x2 2 2 3 1 0 0 0 0 1 1-1 0 0 1 0-2 2 1 -Z-20 0 0-2 0 0 2 0 4 x1 x5 x2 4 1 2 1 0 0 0 0 1 0-1/2 1/2 1 1/2-1/2 0 1 0 -Z-20 0 0-2 0 0 Z*=20,X*=(2,3,0,2,0)Z*=20,X*=(4,2,0,0,1)10、用单纯型法求解下面线性规划问题的解 解：列表如下 Cj 3 5 0 0 0 CB XB

36、 b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 4 12 18 1 0 3 0 2 2 1 0 0 0 1 0 0 0 1 6 9 -Z 0 3 5 0 0 0 00348242max21212121xxxxxxxxz001823122453max21212121xxxxxxxxz0 5 0 x3 x2 x5 4 6 6 1 0 3 0 1 0 1 0 0 0 1/2-1 0 0 1 4 3 -Z-30 3 0 0-5/2 0 0 5 3 x3 x2 x1 6 2 2 0 0 1 0 1 0 1 0 0 1/3 1/2-1/3-1/3 0 1/3 -Z-20 0 0 0-3/

37、2-1 X*=(2,6,6,0,0)Z*=36 11、用单纯型法求解下面线性规划问题的解 121122212max25156224.5,0zxxxxxstxxx x 解：化为标准型 121312422512345max25156224.5,0zxxxxxxxstxxxx xx xx 单纯型表如下：Cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 15 24 5 0 6 1 5 2 1 1 0 0 0 1 0 0 0 1 4 5 Z 0 2 1 0 0 0 0 2 0 x3 x1 x5 15 4 1 0 1 0 5 1/3 2/3 1 0 0

38、0 1/6-1/6 0 0 1 3 12 3/2 Z 0 0 1/3 0-1/3 0 0 2 1 x3 x1 x2 15/2 7/2 3/2 0 1 0 0 0 1 1 0 0 5/4 1/4-1/4-15/2-1/2 3/2 Z 17/2 0 0 0-1/4-1/2 由些可得，问题的最优解为 x1=7/2，x2=3/2，最优值 max z=17/2 12、用大 M 法求解如下线性规划模型：min z=5x12x24x3 0,10536423321321321xxxxxxxxx 解：用大 M 法，先化为等效的标准模型：max z/=5x12x24x3.5,.,2,1,0105364235321

39、4321jyxxxxxxxxj 增加人工变量 x6、x7，得到：max z/=5x12x24x3Mx6Mx7 7,.,2,1,0105364237532164321jxxxxxxxxxxxj 大 M 法单纯形表求解过程如下：CB XB b 5 2 4 0 0 M M L x1 x2 x3 x4 x5 x6 x7 M x6 4（3）1 2 1 0 1 0 4/3 M x7 10 6 3 5 0 1 0 1 5/3 9M 4M 7M M M M M 9M5 4M2 7M4 M M 0 0 5 x1 4/3 1 1/3 2/3 1/3 0 1/3 0 M x7 2 0 1 1（2）1 2 1 1 5

40、-M5/3-M10/3-2M+5/3 M 2M5/3-M 0 M1/3 M2/3 2M5/3 M 3M+5/3 0 5 x1 5/3 1 1/2 5/6 0 1/6 0 1/6 10/3 0 x4 1 0（1/2）1/2 1 1/2 1 1/2 2 5 5/2 25/6 0 5/6 0 5/6 0 1/2 1/6 0 5/6 M M+5/6 5 2 x1 2/3 1 0 1/3 1 1/3 1 1/3 x2 2 0 1 1 2 1 2 1 322 5 2 11/3 1 1/3 1 1/3 0 0 1/3 1 1/3 M+1 M+1/3 x*=（32，2，0，0，0）T 最优目标函数值 min

41、z=max z/=（322）=322 13、用大 M 法求解如下线性规划模型：min z=540 x1450 x2720 x3 0,3035970953321321321xxxxxxxxx 解：用大 M 法，先化为等效的标准模型：max z/=540 x1450 x2720 x3.5,.,2,1,0303597095353214321jyxxxxxxxxj 增加人工变量 x6、x7，得到：max z/=540 x1450 x2720 x3Mx6Mx7 5,.,2,1,030359709537532164321jxxxxxxxxxxxj 大 M 法单纯形表求解过程如下：CB XB b 540 4

42、50 720 0 0 M M L x1 x2 x3 x4 x5 x6 x7 M x6 70 3 5 9 1 0 1 0 70/3 M x7 30（9）5 3 0 1 0 1 30/9=10/3 12M 10M 12M M M M M 12M540 10M450 12M720 M M 0 0 M x6 60 0 10/3（8）1 1/3 1 1/3 60/8=540 x1 10/3 1 5/9 1/3 0 1/9 0 1/9 10/3/1/3=10 -300+10/3M-8M180 M M/3+60 M M/360 0-150+10/3M 8M-540 M M/360 0 M/3+60 720

43、x3 15/2 0 5/12 1 1/8 1/24 1/8 1/24 15/2/5/12=18 540 x1 5/6 1（5/12）0 1/24 1/8 1/24 1/8 5/6/5/12=2 540 572 720 135/2 475/12 135/2 75/2 0 125 0 135/2 475/12 135/2M 75/2M 720 450 x3 20/3 1 0 1 1/6 1/6 1/6 1/6 x2 2 12/5 1 0 1/10 3/10 1/10 3/10 5700 360 450 720 75 15 75 15 180 0 0 75 15 75M 15M 该对偶问题的最优解是

44、 x*=（0，2，320，0，0）T 最优目标函数值 min z=（5700）=5700 14、用单纯形法求解线性规划问题 化成标准形式有 加入人工变量则为 000931243max3213232132131xxxxxxxxxxxxxz093124003max5132532143215431xxxxxxxxxxxxxxxz 列出单纯形表 Cj 3 0 1 0 0 M-M CB XB b x1 x2 x3 x4 x5 x6 x7 0-M-M x4 x6 x7 4 1 9 1-2 0 1 1 3 1-1 1 1 0 0 0-1 0 0 1 0 0 0 1 -Z 10M-2M-3 4M 1 0-M

45、0 0 0 0-M x4 x2 x7 3 1 6 3-2 6 0 1 0 2-1 4 1 0 0 1-1 3-1 1-3 0 0 1 -Z 6M 6M-3 0 4M+1 0 3M-4M 0 0 0-3 x4 x2 x1 0 3 1 0 0 1 0 1 0 0 1/3 2/3 1 0 0-1/2 0 1/2-1/2 0-1/2 1/2 1/3 1/6 -Z 3 0 0 3 0 3/2-M-3/2-M+1/2 0 0 1 x4 x2 x3 0 5/2 3/2 0-1/2 3/2 0 1 0 0 0 1 1 0 0-1/2-1/4 3/4 1/2 1/4-3/4-1/2 1/4 1/4 -Z-3/2

46、-9/2 0 0 0-3/4-M+3/4-M-1/4 人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0)Z*=3/2 15、用单纯形法求解线性规划问题 解 化为标准形式有 093124003max71732653214321765431xxxxxxxxxxxxxMxMxxxxxz0012432223max21212121xxxxxxxxz 列表计算 Cj 3 2 0 0 M CB XB b x1 x2 x3 x4 x5 0 M x3 x5 2 12 2 3 1 4 1 0 0-1 0 1 2 3 -Z-12M 3M+3 4M+2 0-M 0 -2 M x2 x5 2 4 2-

47、5 1 0 1-4 0-1 0 1 -Z 4-4M-5M-1 0-4M-2-M 0 X*=(0,2,0,0,4)Z*=4M-4 说明原问题无解 写对偶问题（10）1、写出下列线性绘画问题的对偶问题 432132maxxxxxz 无约束42314313214321,0,14325xxxxxxxxxxxxxx 解：32145minyyy 0,01331223213132121321yyyyyyyyyyyyy无约束 2、写出下述线性规划的对偶问题 01243220023max51542132154321xxxxxxxxMxxxxxz解 3、写出下列线性规划的对偶问题 解：4、写出下列线性规划的对偶问

48、题 解 无约束321321321321321004163253234maxxxxxxxxxxxxxxxxz无约束321321321321321003654313242minyyyyyyyyyyyyyyyw无约束32132132132132100121213225minxxxxxxxxxxxxxxxz无约束32132132132132100322252maxyyyyyyyyyyyyyyyw无约束321313213213210034313242maxxxxxxxxxxxxxxxz 无约束321321213213210041323234minyyyyyyyyyyyyyyw 对偶性质 1、已知线性规划

49、问题如下：Max Z=213xx 5010521xx 121 xx 42x 0,21xx 已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为：321450yyyMinZ 1521 yy 310321yyy 0;0,231yyy 将 X=（2，4）T代入原问题可知：21xx 1 为严格不等式，所以02y 由对偶问题性质可知：1445031yy 解之得：5/11y 31031 yy 02y 13y 所以 Y=（1/5，0，1）T Min Z=14 2、已知线性规划问题 43216532minxxxxz )4,3,2,1(033223243214321jxxxxxxx

50、xxj 用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。答案：(对偶问题的最优解为)51,58(*Y；(依据 z*=w*及互补松弛性，有x4=0,且 322325/19532321321321xxxxxxxxx 解得愿问题最优解X*=(7/5,0,1/5,0)。3、已知线性规划问题 5432132532minxxxxx 432.54321xxxxxts 33254321xxxxx 5,2,1,0jxj 已知其对偶问题的最优解为53,54*2*1yy，最优值为5*z。试用对偶理论找出原问题的最优解。解 先写出它的对偶问题 2134maxyyz .2221yy 321 yy 5323