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 是 产品售后的总利润，则 maxz=70x1+120x2 s.t. 2、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有 关数据如下： 甲乙 可用量 原材料（吨/
2、件） 工时（工时/件） 零件（套/件） 22 52.5 1 3000 吨 4000 工时 500 套 海量资源，欢迎共阅 2 产品利润（元/件） 43 建立使利润最大的生产计划的数学模型，不求解。 解：设甲、乙两种产品的生产数量为 x1、x 2， 设 z 为产品售后总利润，则 maxz=4x1+3x2 s.t. 3、一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、 劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能 获得的利润值以及这三种资源的储备量如下表所示： 技术服务 劳动力 行政管理 单位利润 甲 1 10 2 10 乙 1 4 2 6 丙 1 5 6 4 资源储备 量 1
3、00 600 300 建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。 解：建立线性规划数学模型： 设甲、乙、丙三种产品的生产数量应为 x1、x 2、x 3，则 x1、x 2、x 30，设 z 是产品售后的总利润，则 maxz=10x1+6x2+4x3 s.t. 海量资源，欢迎共阅 4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通 信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg, 试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 物品 食 品 氧 气 冰 镐 绳 索 帐 篷 照相器 材 通信设 备 重
4、量/Kg 5 5 2 6 12 2 4 重要性系 数 20 15 18 14 8 4 10 试建立队员所能携带物品最大量的线性规划模型，不求解。 解：引入 01 变量 xi,xi=1 表示应携带物品 i，, xi=0 表示不应携带 物品 I 5、工厂每月生产 A、B、C 三种产品，单件产品的原材料消耗量、设 备台时的消耗量、资源限量及单件产品利润如下图所示： A B C 资源限量 材料 （kg） 1.5 1.2 4 2500 设备（台 时） 3 1.6 1.2 1400 利润（元/ 件） 10 14 12 根据市场需求，预测三种产品最低月需求量分别是 150、260、120，最高需求量是 25
5、0、310、130，试建立该问题数学 产 品资 源 海量资源，欢迎共阅 4 模型，使每月利润最大，为求解。 解：设每月生产 A、B、C 数量为 。321,x 6、A、B 两种产品，都需要经过前后两道工序，每一个单位产品 A 需要前道工序 1 小时和后道工序 2 小时，每单位产品 B 需要前道工 序 2 小时和后道工序 3 小时。可供利用的前道工序有 11 小时，后道 工序有 17 小时。每加工一个单位产品 B 的同时，会产生两个单位的 副产品 C，且不需要任何费用，产品 C 一部分可出售盈利，其余只 能加以销毁。出售 A、B、C 的利润分别为 3、7、2 元，每单位产品 C 的销毁费用为 1
6、元。预测表明，产品 C 最多只能售出 13 个单位。 试建立总利润最大的生产计划数学模型，不求解。 解：设每月生产 A、B 数量为 销毁的产品 C 为 。,21x3x 7、靠近某河流有两个化工厂（参见附图） ，流经第一化工厂的河流 流量为每天 500 ，在两个工厂之间有一条流量为 200 万 的支流。3m3m 第一化工厂每天排放有某种优化物质的工业污水 2 万 ，第二化工 厂每天排放该污水 1.4 万 。从第一化工厂的出来的污水在流至第3 二化工厂的过程中，有 20%可自然净化。根据环保要求，河流中的 污水含量不应大于 0.2%。这两个工厂的都需要各自处理一部分工业 污水。第一化工厂的处理成本
7、是 1000 元/万 ，第二化工厂的为3m 800 元/万 。现在要问满足环保的条件下，每厂各应处理多少工业3m 污水，才能使两个工厂的总的污水处理费用最少？列出数学模型， 不求解。 海量资源，欢迎共阅 附图：工厂 1工厂 2 500 万 200 万3m3 解：设第一化工厂和第二化工厂的污水处理量分别为每天 和 x2万 ，133 st 0,4.16.82x 8、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等） ， 希望获得其中的营养成分（如：蛋白质、脂肪、维生素等） 。设市面 上现有这 3 种营养物，其分别含有各种营养成分数量，以及各营养 物价格和根据医生建议消费者这段时间至少需要的各种
8、营养成分的 数量（单位都略去）见下表。 甲 乙 丙 至少需要的营养成 分数量 A 4 6 20 80 B 1 1 2 65 C 1 0 3 70 D 21 7 35 450 价格 25 20 45 问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱 最少？只建立模型，不用计算。 解：设购买甲、乙、丙三种营养物的数量分别为 ，则根据321x和、营养物营养成分 海量资源，欢迎共阅 6 题意可得如下线性规划模型： 9、某公司生产的产品 A，B，C 和 D 都要经过下列工序：刨、立铣、 钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时 间如下表所示： 刨 立铣 钻孔 装配 A 0.5
9、 2.0 0.5 3.0 B 1.0 1.0. 0.5 1.0. C 1.0 1.0 1.0 2.0 D 0.5 1.0 1.0 3.0 可用生产时 间（小时） 1800 2800 3000 6000 又知四种产品对利润贡献及本月最少销售需要单位如下： 产 品 最少销售需要单位 元/单位 A 100 2 B 600 3 C 500 1 D 400 4 问该公司该如何安排生产使利润收入为最大？（只需建立模型） 解：设生产四种产品分别 x1,x2,x3,x4单位 则应满足的目标函数为：maxz=2x 1+3x2+x3+x4 满足的约束条件为： 海量资源，欢迎共阅 10、某航空公司拥有 10 架大型
10、客机、15 架中型客机和 2 架小型 客机，现要安排从一机场到 4 城市的航行计划，有关数据如表 1- 5，要求每天到 D 城有 2 个航次（往返） ，到 A,B,C 城市各 4 个航 次（往返） ，每架飞机每天只能完成一个航次，且飞行时间最多为 18 小时，求利润最大的航班计划。 客机类型 到达城市 飞行费用（元/ 次） 飞行收入（元/ 次） 飞行时间（h/d） A B C 大型 D 6000 7000 8000 10000 5000 7000 10000 18000 1 2 5 10 A B C 中型 D 1000 2000 4000 - 3000 4000 6000 - 2 4 8 20
11、 A B C 小型 D 2000 3500 6000 - 4000 5500 8000 - 1 2 6 19 解：设大型客机飞往 A 城的架次为 x1A，中型客机飞往 A 城的架 次为 x2A，小型客机飞往 A 城的架次为 x3A，其余依此类推。 资源限制派出的大型客机架次不能超过 10 架，表示为 同理 223315ABCx 班次约束飞往各城的班次要满足 非负性约束 且为整数；（i=1,2,3;j=A,B,C,D）0ijx 目标函数为 11222333ma0020ABCABCABCzxxx1D 8+ 11、 AR1 AR2 AR4 AR6 联邦航空局的最大产量（每月生产的飞机数目） 8 17
12、 11 15 海量资源，欢迎共阅 8 建造飞机所需要的时间（天） 每架飞机所需要的生产经理数目 每架飞机的盈利贡献（千美元） 4 1 62 7 1 84 9 2 103 11 2 125 CRISP 公司下个月可以得到的生产经理的总数是 60 人。该公司 的飞机制造设施可以同时在任何给定的时间生产多达 9 架飞机。因 此，下一个月可以得到的制造天数是 270 天（9*30，每月按 30 天计 算） 。JonathanKuring 是该公司飞机制造管理的主任，他想要确定 下个月的生产计划安排，以便使盈利贡献最大化。 解：设 表示下个月生产 AR1 型飞机的数目， 表示 AR2 型， 表1x 2x
13、3x 示 AR4 型， 表示 AR6 型4x 目标函数： 1234ma68015zx 约束条件： 1234234124479785,0xxx 为整数1234,x 12、永辉食品厂在第一车间用 1 单位原料 N 可加工 3 单位产品 A 及 2 单位产品 B，产品 A 可以按单位售价 8 元出售，也可以在第二车间 继续加工，单位生产费用要增加 6 元，加工后单位售价增加 9 元。 产品 B 可以按单位售价 7 元出售，也可以在第三车间继续加工，单 位生产费用要增加 4 元，加工后单位售价可增加 6 元。原料 N 的单 位购入价为 2 元，上述生产费用不包括工资在内。3 个车间每月最 多有 20
14、万工时，每工时工资 0.5 元，每加工 1 单位 N 需要 1.5 工时， 海量资源，欢迎共阅 若 A 继续加工，每单位需 3 工时，如 B 继续加工，每单位需 2 工时。 原料 N 每月最多能得到 10 万单位。问如何安排生产，使工厂获利最 大？ 解：设 为产品 A 的售出量； 为 A 在第二车间加工后的售出量；1x2x 表示产品 B 的售出量； 表示 B 在第三车间加工后的售出量；3 4 为第一车间所用原材料的数量，5x 则目标函数为： 12345max89.5782.zxx 约束条件： 5245132450.0,xx 海量资源，欢迎共阅 10 化标准形式（5） 1、将下列线性规划模型化为
15、标准形式 解： 2、将下列线性规划模型化为标准形式 解： 3、将下列线性规划变为最大值标准形。 解： 无 约 束32132105327minxxxz052370)(ma7132154621 76541xxxxz 海量资源，欢迎共阅 图解法（5） 1、用图解法求解下面线性规划 minz=3x 1+2x2 解： 可行解域为 abcda，最优解为 b 点。 由方程组 解出 x1=11，x 2=0 02421x X *= =（11，0） T21x minz=311+20=33 2、用图解法求解下面线性规划 minz=2x1+x2 解： 从上图分析，可行解域为 abcde，最优解为 e 点。 由方程组
16、解出 x1=5，x 2=3 5812x X *= =（5，3） T2 minz=Z *=25+3=13 3、已知线性规划问题如下： MaxZ= 21x 用图解法求解，并写出解的情况 解： 海量资源，欢迎共阅 12 x2 6 Z 4x2=4 2 Z x1 0246810 5x1+10x2=50 x1+x2=1 由图可知： 解之得：5012x1x 则 maxZ=2+3*4=14 4、用图解法求解下面线性规划问题 解： 海量资源，欢迎共阅 5、用图解法求解下面线性规划问题 图解如下： 可知，目标函数在 B(4,2)处取得最大值，故原问题的最优解为 ，目标函数最大值为 。*(4,2)TX*2431z
17、二、单纯型法（15） 1、用单纯型法求解下面线性规划问题的解 maxz=3x1+3x2+4x3 s.t. 0,64645321x， 解：加入松弛变量 x4，x 5，得到等效的标准模型： maxz=3x1+3x2+4x3+0x4+0x5 s.t. 5,.21,06460331jxxj 列表计算如下： 3 3 4 0 0 CB XB b x1 x2 x3 x4 x5 L 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 海量资源，欢迎共阅 14 0 x5 42 （21
18、/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 3 24/7 4 5/7 1/7 38 0 3/7 0 5/7 1/7 X *=（10，0，2，0，0） Tmaxz=310+42=38 2、用单纯型法求解下面线性规划问题的解 maxz=70x1+120x2 s.t. 0313640922xx， 解：加入松弛变量 x3，x 4，x 5，得到等效的标准模型： maxz=70x1+120x2+0x3+0x4+0x5 s.t. 列表计算如下： 70
19、 120 0 0 0 CB XB b x1 x2 x3 x4 x5 L 0 x3 360 9 4 1 0 0 90 0 x4 200 4 6 0 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/1 3 0 x4 20 （11/5 ） 0 0 1 -3/5 100/1 1 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 x
20、1 100/11 1 0 0 5/11 -3/11 120 x2 300/11 0 1 0 -3/22 2/11 70 120 0 170/11 30/11143 0 0 0 -170/11 30/11 X *=（ ， ， ，0，0） T086 maxz=70 +120 =1134 3、用单纯型法求解下面线性规划问题的解 maxz=4x1+3x2s.t. 0,54.253211xx 解：加入松弛变量 x3，x 4，x 5，得到等效的标准形式： 海量资源，欢迎共阅 16 maxz=4x1+3x2+0x3+0x4+0x5s.t. 5,.21,004.32121jxxxj 用表解形式的单纯形法求解，
21、列表计算如下： 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 L 0 x3 3000 2 2 1 0 0 3000/2=1500 0 x4 4000 5 2.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 （2.5 ） 0 1 -5 1500/2.5=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 -0.8 （2） 800/
22、2=400 3 x2 600 0 1 0 0.4 -2 4 x1 500 1 0 0 0 1 500/1=500 海量资源，欢迎共阅 4 3 0 1.2 -2 0 0 0 -1.2 2 0 x5 400 0 0 0.5 -0.4 1 3 x2 1400 0 1 1 -0.4 0 4 x1 100 1 0 -0.5 0.4 0 4 3 1 0.4 0 4600 0 0 -1 -0.4 0 据上表，X *=（100，1400，0，0，400） Tmaxz=4100+31400=460 4、用单纯型法求解下面线性规划问题的解 maxz=10x1+6x2+4x3 s.t. 解：加入松弛变量 x4，x
23、5，x 6，得到等效的标准模型： maxz=10x1+6x2+4x3+0x4+0x5+0x6 s.t. 6,.21,030254163152431jxxxxj 列表计算如下： 10 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 L 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 海量资源，欢迎共阅 18 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
24、 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/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 10 6 20/3 10/3 2/3 032 0 0 8/3 10/ 3 2/3 0 X *=（ ， ，0，0，0，100） T312 maxz=10 +6 =32 5、用单纯型法求解下面线性规划问题的解 用单纯形法求解，并指出问题的解属于哪一类。 解：（1） 、将原问题划为标准形得： =60432xxjC
25、 4 -2 2 0 0 0 海量资源，欢迎共阅 BCX b 1x234x56x 0 46 0 3 1 1 1 0 0 0 5x1 0 1 -1 2 0 1 0 0 6x4 0 2 -2 2 0 0 1j 4 -2 2 0 0 0jC 4 -2 2 0 0 0BX b 1x34x56x 0 43 0 0 4 -5 1 -3 0 4 1x1 0 1 -1 2 0 1 0 0 6x2 0 0 4 -6 0 -2 1j 0 2 -6 0 -4 0jC 4 -2 2 0 0 0BX b 1x34x56x 0 41 0 0 0 1 1 -1 -1 4 1x1 1 0 1/2 0 1/2 1/4 海量资源，
26、欢迎共阅 20 5 -2 2x5 0 1 - 3/2 0 - 1/2 1/4j 0 0 -3 0 -3 - 1/2 所以 X=（15，5，0，10，0，0） T为唯一最优解 MaxZ=4*15-2*5=50 6、用单纯形法求解下述 LP 问题。 解：引入松弛变量 、 ，化为标准形式：3x4 构造单纯形表，计算如下： jc 2.5 1 0 0BBXb1x23x4i 0 3x15 3 5 1 0 5 0 410 5 2 0 1 2j 2.5 1 0 0 0 3x9 0 19/5 1 3/5 45/19 2.5 12 1 2/5 0 1/5 5j 0 0 0 1/2 1 2x45/19 0 1 5/
27、19 3/1 9 2.5 1x20/19 1 0 2/1 9 5/19 海量资源，欢迎共阅 j 0 0 0 1/2 由单纯形表，可得两个最优解 、(1)2,9)TX ，所以两点之间的所有解都是最优解，即最(2)0/19,45,)TX 优解集合为： ，其中 。(1(2)X01 7、用单纯形法解线性规划问题 解：化为标准型 列出单纯形表 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 x3 15 0 5 1 0 0 3 0052
28、461max21121xxxz52426150max1135421xxxxz 海量资源，欢迎共阅 22 2 0 x1 x5 4 1 1 0 1/3 2/3 0 0 1/6 -1/6 0 1 12 3/2 -Z -8 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 -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
29、 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 x1 2 1 -2 1 0 0 0422max211xxz 海量资源，欢迎共阅 0 0 x4 x5 6 6 0 0 -3 -1 2 1 1 0 0 1 -Z -2 0 3 -1 0 0 把表格还原为线性方程 令 x3=0 此时，若让x 2进基，则会和基变量x 1同时增加，使目标函数值无限增长，所以本题无界 9、用单纯型法求解下面线性规划问题的解 Cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x
30、3 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 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 x1 x5 4 1 1 0 0 0 0 -1/2 1 1/2 0 1 海量资源，欢迎共阅 24 4 x2 2 0 1 1/2 -1/2 0 -Z -20 0 0 -2 0 0
31、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 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 0 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/
32、2 -1/3 -1/3 0 1/3 00182345max112xxxz 海量资源，欢迎共阅 -Z -20 0 0 0 -3/2 -1 X*=(2,6,6,0,0)Z*=36 11、 用单纯型法求解下面线性规划问题的解 解：化为标准型 单纯型表如下： 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
33、/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，x 2=3/2，最优值 maxz=17/2 海量资源，欢迎共阅 26 12、用大 M 法求解如下线性规划模型： minz=5x12x 24x 3 解：用大 M 法，先化为等效的标准模型： maxz/=5x 12x 24x 3 s.t. 增加人工变量 x6、x 7，得到： maxz/=5x 12x 24x 3Mx 6Mx
34、 7 s.t 大 M 法单纯形表求解过程如下： 5 2 4 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 L 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 -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
35、 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 x1 2/3 1 0 1/3 1 1/3 1 1/35 2 x2 2 0 1 1 2 1 2 1 5 2 11/3 1 1/3 1 1/3 3 0 0 1/3 1 1/3 M+1 M+1/3 x *=（ ，2，0，0，0） T 最优目标函数值 minz=maxz /=（ ）=32 13、用大 M 法求解如下线性规划模型： minz=540x1450x 2720x 3 解：用大 M 法，
36、先化为等效的标准模型： maxz/=540x 1450x 2720x 3 s.t. 增加人工变量 x6、x 7，得到： maxz/=540x 1450x 2720x 3Mx 6Mx 7 s.t 大 M 法单纯形表求解过程如下： 540 450 720 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 L 海量资源，欢迎共阅 28 M x6 70 3 5 9 1 0 1 0 70/3 M x7 30 （9） 5 3 0 1 0 1 30/9=1 0/3 12M 10M 12M M M M M 12M540 10M450 12M72 0 M M 0 0 M x6 60 0
37、10/3 （8） 1 1/3 1 1/3 60/8=2 .5 54 0 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+6 0 M M/360 0 - 150+10/3M 8M- 540 M M/360 0 M/3+6 0 72 0 x3 15/2 0 5/12 1 1/8 1/24 1/8 1/24 15/2/5 /12 =18 54 0 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/
38、12 135/2 75/2 0 125 0 135/2 475/1 2 135/2 M 75/2M x3 20/3 1 0 1 1/6 1/6 1/6 1/6720 450 x2 2 12/5 1 0 1/10 3/10 1/10 3/10 360 450 720 75 15 75 1557 00 180 0 0 75 15 75M 15M 该对偶问题的最优解是 x*=（0，2， ，0，0） T3 最优目标函数值 minz=（5700）=5700 14、用单纯形法求解线性规划问题 化成标准形式有 加入人工变量则为 列出单纯形表 Cj 3 0 1 0 0 M -M CB XB b x1 x2 x
39、3 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 0 0 0 x4 3 3 0 2 1 1 -1 0 海量资源，欢迎共阅 30 0 -M x2 x7 1 6 -2 6 1 0 -1 4 0 0 -1 3 1 -3 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
40、/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 -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、用单纯形法求解线性规划问题 解化为标准形式有 列表计算 Cj 3 2 0 0 M CB XB b x1 x2 x3 x4 x5 0 x3 2 2 1 1 0
41、0 2 海量资源，欢迎共阅 M x5 12 3 4 0 -1 1 3 -Z -12M 3M+3 4M+2 0 -M 0 -2 M x2 x5 2 4 2 -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、 写出下列线性绘画问题的对偶问题 解： 2、写出下述线性规划的对偶问题 解 3、写出下列线性规划的对偶问题 无 约 束32132104163254maxxxxz无 约 束3213211015minxxxz 海量资源，欢迎共阅 32 解： 4、写出下列线性规划的对偶问
42、题 解 无 约 束321321025maxyyyw无 约 束3213210431maxxxxz 海量资源，欢迎共阅 对偶性质 1、已知线性规划问题如下： MaxZ= 213x 已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解。 解：该问题的对偶问题为： 将 X=（2，4） T代入原问题可知： 1 为严格不等式，所以2x0y 由对偶问题性质可知： 解之得：14531y5/1y 所以 Y=（1/5，0，1） TMinZ=14 2、已知线性规划问题 用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问 题解。 答案：(对偶问题的最优解为 ；)51,8(*Y (依据 z*=w*及互补松弛
43、性，有 x4=0,且 解得愿问题最优解 X*=(7/5,0,1/5,0)。 3、已知线性规划问题 已知其对偶问题的最优解为 ，最优值为 。试用对53,4*2*1y5*z 偶理论找出原问题的最优解。 解先写出它的对偶问题 s.t. 21y 海量资源，欢迎共阅 34 321y 5321y 21y 将 的值代入约束条件，得，为严格不等式；设原问题*, 的最优解为 ，由互补松弛性得 。因),(*51*xx 0*43*2x ；原问题的两个约束条件应取等式，故有0,*21y 求解后得到 ；故原问题的最优解为,*51x ；最优值为 。*X5*w 4、已知下列问题的最优解为X*=(1/7,11/7),用互补松
44、弛定理求其对偶问题的最优解。 解：第一步，写出对偶问题 第二步，将 LP，DP 都化为标准型 第三步：将最优解代入标准型中，确定松弛变量取值 第四步：利用互补松弛定理 Y3*=0 Y1S=0Y2S=0 第五步：将 Y3*=0Y1S=0Y2S=0 代入约束条件 则有 75421211 yy 对偶问题的最优解为 Y*=(4/7,5/7,0) 02,132max:211xzLP,133SS0,02321min: 21321121SSyyywDP 海量资源，欢迎共阅 5、已知线性规划问题： ，试用对 0,122max31321xz 偶理论证明上述线性规划问题无最优解。 证明：首先看到该问题存在可行解，
45、例如 ，而上述X 问题的对偶问题为： 0,12min211yyw 由第一约束条件可知对偶问题无可行解，因而无最优解。由此， 原问题也无最优解。 5、已知线性规划问题 （1）写出其对偶问题； （2）用图解法求对偶问题的解； （3）利用（2）的结果及对偶性质求原问题解。 解：（1）原线性规划问题可化为： 其对偶问题为： （2）用图解法解得 )51,8(,(21*yY9*w （3）由互补松弛性定理知道， 0,63421xy 又由 3259x,11*wz可 得 ： 解之，可得原问题最优解 。)0,517(*X 海量资源，欢迎共阅 36 对偶单纯形法（15） 1、用对偶单纯形法解下列线性规划问题 解：先
46、化为标准型 约束条件两边同乘(-1) 列单纯形表 Cj 15 24 5 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 2 1 0 5 -6 -2 -1 -1 1 0 0 1 -15 -24 -5 0 0 - 4 5 -24 0 x2 x5 1/3 -1/3 0 -5 1 0 1/6 - 2/3 -1/6 -1/3 0 1 -15 0 -1 -4 0 3 3/2 12 -24 -5 x2 x3 1/4 1/2 -5/4 15/2 1 0 0 1 -1/4 1/2 1/4 -3/2 - 15/2 0 0 -7/2 -3/2 X*=(0,1/4,1/2)Y*=(7/2,3
47、/2) 01256541min3132xxw54 海量资源，欢迎共阅 2、用对偶单纯形法解下列线性规划问题 解：改写为标准形式 列单纯形表如下： Cj 4 12 18 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 3 5 1 0 0 -2 -3 -2 1 0 0 1 -4 -12 -18 0 0 - 6 9 0 -12 x4 x2 -3 5/2 -1 0 0 1 -3 1 1 0 0 -1/2 -4 0 -6 0 -6 4 2 12 - -18 -12 x3 x2 13/2 1/3 -1/3 0 1 1 0 -1/3 1/3 0 -1/2 -2 0 0 -2 -6 X*=(0,3/2,1)Y*=(2,6) 3、用对偶单纯形法求解下面的问题： 解：令 ，则问题可以标准化为：z 取 为初始基，则 是非基可行1065P 0,3265jxx其 余 解，但 ，1,8,2431 是对偶可行解，建立单纯形表（见表 4-1）1BCY 海量资源，欢迎共阅 38 计算结果如下：最优解 。.140,8/1232
