《运筹学》题库

运筹学习题库

数学建模题（5）

1、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：

甲 乙 A 9 4 360 B 4 6 200 C 3 10 300 70 120 试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。

解：设甲、乙产品的生产数量应为x1、x2，则x1、x2≥0，设z是产品售后的总利润，则

max z =70x1+120x2

s.t.

?9x1?4x2?360??4x1?6x2?200? ?3x1?10x2?300??x1，x2?02、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：

原材料（吨/件） 工时（工时/件） 零件（套/件） 产品利润（元/件） 建立使利润最大的生产计划的数学模型，不求解。 解：设甲、乙两种产品的生产数量为x、x，

1

2

甲 乙 2 2 5 2.5 1 4 3 可用量 3000吨 4000工时 500套 设z为产品售后总利润，则max z = 4x+3x

1

2

s.t.

?2x1?2x2?3000?5x?2.5x?4000?12?

x?5001???x1,x2?03、一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：

甲 乙 丙 资源储备量 技术服务 1 1 1 100 劳动力 10 4 5 600 行政管理 2 2 6 300 单位利润 10 6 4 建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。

1

解：建立线性规划数学模型：

设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则x1、x2、x3≥0，设z是产品售后的总利润，则

max z =10x1+6x2+4x3

s.t.

?x1?x2?x3?100?10x?4x?5x?600?123? 2x?2x?6x?300123???x1，x2，x3?04、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。

序号 物品 重量/Kg 重要性系数 1 食品 5 20 2 氧气 5 15 3 冰镐 2 18 4 绳索 6 14 5 帐篷 12 8 6 照相器材 2 4 7 通信设备 4 10 试建立队员所能携带物品最大量的线性规划模型，不求解。

解：引入0—1变量xi, xi=1表示应携带物品i，,xi=0表示不应携带物品I

naxz?20x1?15x2?18x3?14x4?8x5?4x6?10x7?5x1?5x2?2x3?6x4?12x5?2x6?4x7?25??xi?0或1,i?1,2,...,7

5、工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：

产 资 源 A B C 资源限量 品 材料（kg） 设备（台时） 利润（元/件） 1.5 3 10 1.2 1.6 14 4 1.2 12 2500 1400 根据市场需求，预测三种产品最低月需求量分别是150、260、120，最高需求量是250、310、130，试建立该问题数学模型，使每月利润最大，为求解。

解：设每月生产A、B、C数量为

x1,x2,x3。

MaxZ?10x1?14x2?12x3 1.5x1?1.2x2?4x3?2500 3x1?1.6x2?1.2x3?1400

150?x1?250 260?x2?310

2

120?x3?130 x1,x2,x3?0

6、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)?x3

x1?2x2?11 2x1?3x2?17

2x2?x3?13 x1,x2,x3?0

7、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500

m3，在两个工厂之间有一条流量为200万m3的支流。第一

化工厂每天排放有某种优化物质的工业污水2万

m3，第二化工厂每天排放该污水1.4万m3。从第一化工厂的出来的污水在流至第二化工厂的

过程中，有20%可自然净化。根据环保要求，河流中的污水含量不应大于0.2%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理

成本是1000元/万

m3，第二化工厂的为800元/万m3。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污

水处理费用最少？列出数学模型，不求解。

附图： ¤工厂1 ¤工厂2 500万m3 200万m3

解：设第一化工厂和第二化工厂的污水处理量分别为每天

x1m3和x万m3，

2

minZ?1000x1?800x2

3

?1?x1?2?0.8x?x?1.6?12st? ?x2?1.4??x1,x2?08、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。

营养物 营养成分 A B C D 价格 甲 4 1 1 21 25 6 1 0 7 20 20 2 3 35 45 80 65 70 450 乙 丙 至少需要的营养成分数量 问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。

解：设购买甲、乙、丙三种营养物的数量分别为

x1、x2和x3， 则根据题意可得如下线性规划模型：

minz?25x1?20x2?45x3?4x1?6x2?20x3?80?x?x?2x?65123? ?s.t.?x1?3x3?70?21x?7x?35x?45023?1?x1,x2,x3?0?9、某公司生产的产品A，B，C和D都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示： A B C D 可用生产时间（小时）

又知四种产品对利润贡献及本月最少销售需要单位如下：

产品 A B C D 最少销售需要单位 100 600 500 400 元/单位 2 3 1 4 刨 0.5 1.0 1.0 0.5 1800 立铣 2.0 1.0. 1.0 1.0 2800 钻孔 0.5 0.5 1.0 1.0 3000 装配 3.0 1.0. 2.0 3.0 6000 问该公司该如何安排生产使利润收入为最大？（只需建立模型）

解：设生产四种产品分别x1,x2,x3,x4单位

则应满足的目标函数为：max z=2 x1+3 x2+ x3+ x4

4

满足的约束条件为：

?0.5x1?x2?x3?0.5x4?1800?2x?x?x?x?2800?1234

?0.5x1?0.5x2?x3?x4?3000?

?3x1?x2?2x3?3x4?6000

?

x?100?1

?x2?600?

?x3?500?x?400?4

10、某航空公司拥有10架大型客机、15架中型客机和2架小型客机，现要安排从一机场到4城市的航行计划，有关数据如表1-5，要求每天到D城有2个航次（往返），到A,B,C城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班计划。

客机类型 大型 到达城市 A B C D 中型 A B C D 小型 A B C D 飞行费用（元/次） 6000 7000 8000 10000 1000 2000 4000 ---- 2000 3500 6000 ---- 飞行收入（元/次） 5000 7000 10000 18000 3000 4000 6000 ---- 4000 5500 8000 ---- 飞行时间（h/d） 1 2 5 10 2 4 8 20 1 2 6 19 解：设大型客机飞往A城的架次为x1A，中型客机飞往A城的架次为x2A，小型客机飞往A城的架次为x3A，其余依此类推。 资源限制 派出的大型客机架次不能超过10架，表示为

x1A?x1B?x1C?x1D?10

同理

x2A?x2B?x2C?15x3A?x3B?x3C?2

班次约束 飞往各城的班次要满足

x1A?x2A?x3A?4

x1B?x2B?x3B?4x1C?x2C?x3C?4x1D?x2D?x3D?2

非负性约束

（i=1,2,3;j=A,B,C,D） xij?0 且为整数；

5

目标函数为

maxz?－1000x1A?0x1B?2000x1C?8000x1D+2000x2A?2000x2B?2000x2C?2000x3A?2000x3B?2000x3C

11、 CRISP公司制造四种类型的小型飞机：AR1型（具有一个座位的飞机）、AR2

型（具有两个座位的飞机）、AR4型（具有四个座位的飞机）以及AR6型（具有六个座位的飞机）。AR1和AR2一般由私人飞行员购买，而AR4和AR6一般由公司购买，以便加强公司的飞行编队。为了提高安全性，联邦航空局（F.A.A）对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进行的，因此小型飞机的制造是以月为单位进行的。表说明了CRISP公司的有关飞机制造的重要信息。 AR1 AR2 AR4 AR6 联邦航空局的最大产量（每月生产的8 17 11 15 飞机数目） 4 7 9 11 建造飞机所需要的时间（天） 1 1 2 2 每架飞机所需要的生产经理数目 62 84 103 125 每架飞机的盈利贡献（千美元） CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30，每月按30天计算）。Jonathan Kuring是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。 解：设x1表示下个月生产AR1型飞机的数目，x2表示AR2型，x3表示AR4型，

x4 表示AR6型

目标函数：maxz?62x1?84x2?103x3?125x4

4x1?7x2?9x3?11x4?270x1?x2?2x3?2x4?60x1?8 约束条件：x2?17x3?11x4?15x1,x2,x3,x4?0

x1,x2,x3,x为整数 412、永辉食品厂在第一车间用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每月最多能得到

6

10万单位。问如何安排生产，使工厂获利最大？

解：设x1为产品A的售出量；x2为A在第二车间加工后的售出量；x3表示产品B的售出量；x4表示B在第三车间加工后的售出量；x5为第一车间所用原材料的数量，

则目标函数为：maxz?8x1?9.5x2?7x3?8x4?2.75x5

??x5?1000003x2?2x4?1.5x5?200000约束条件：???x1?x2?3x5?0

??x3?x4?2x5?0??x1,x2,x3,x4,x5?0

化标准形式（5）

1、将下列线性规划模型化为标准形式 解：

minz?x1?2x2?3x3??x1?x2?x3?7??x1?x2?x3?2??3x1?x2?2x3??5??x1?0x2?0x3无约束

maxz'??x1?2x2?3(x4?x5)?0?x6?0?x7?xx?1?x2?4?x5?x6?7??x1?x2?x4?x5?x7?2?3x1?x2?2x3?5??x1?7?02、将下列线性规划模型化为标准形式

minz?x1?2x2?3x3???2x1?x2?x3?9???3x1?x2?2x3?4?4x1?2x2?3x3??6??x1?0x2?0x3无约束解：

maxz'?x1'?2x2?3x3'?3x3''??2x1'?x2?x3'?x3''?x4?9 ??3x1'?x2?2x3?2x3''?x5?4?4x1'?2x2?3x3'?3x3''?6??x1?5?07

3、将下列线性规划变为最大值标准形。

minz??3x1?4x2?2x3?5x4??4x1?x2?2x3?x4??2st??x1?x2?3x3?x4?14 ??2x1?3x2?x3?2x4?2??x1,x2,x3?0,x4无约束解：

maxz'?3x'\1?4x2?2x3?5x4?5x4???4x1?x2?2x3?x'4?x\4?2st?'\ ?x1?x2?3x3?x4?x4?x5?14??2x1?3x2?x3?2x'4?2x\4?x6?2??x1,x2,x3,x'4,x\4,x5,x6?0

图解法（5）

1、用图解法求解下面线性规划 min z =－3x1+2x2

?2x?1?4x2?22???x1?4x2?10?2x?1?x2?7 ?x1?3x2?1??x1,x2?0解：

8

可行解域为abcda，最优解为b点。

?2x1?4x2?22由方程组??x 解出x1=11，x2=0

2?0∴X*=??x?1?T

?x??=（11，0）

2?∴min z =－3×11+2×0=－33 2、用图解法求解下面线性规划 min z =2x1+x2

???x1?4x2?24??x1?x2?85?x ?1?10??x2?0解：

从上图分析，可行解域为abcde，最优解为e点。 由方程组

??x1?x2?8?x 解出x1=5，x2=3 1?5∴X*

=??x?1?T

?x??=（5，3）

2?∴min z =Z*= 2×5+3=13 3、已知线性规划问题如下： Max Z= x1?3x2

5x1?10x2?50

x1?x2?1 x2?4

9

x1,x2?0

用图解法求解，并写出解的情况 解： x2 6 Z’ 4 x2=4

2 Z’ x1 0 2 4 6 8 10 5x1+10x2=50 x1+x2=1 由图可知：

5x1?10x2?50 解之得：x1?2

x2?4 x2?4

则max Z=2+3*4=14 4、用图解法求解下面线性规划问题

maxz?2x1?x2?5x1?15?st.??6x1?2x2?24 ?x2?x2?5??x1,x2?0解：

10

11

5、用图解法求解下面线性规划问题

max z?2x1?3x2??x1?2x2?8s.. t??4x1?16 ?4x2?12??xj?0,j?1,2图解如下：

可知，目标函数在B(4, 2)处取得最大值，故原问题的最优解为X*?(4,2)T，目

标函数最大值为z*?2*4?3*2?14。

二、单纯型法（15）

1、用单纯型法求解下面线性规划问题的解 max z= 3x1+3x2+4x3

??3x1?4x2?5x3?40s.t.?6x1?4x2?3x3?66?

?x1,x2，x3?0解：加入松弛变量x4，x5，得到等效的标准模型：

max z= 3x1+3x2+4x3+0 x4+0 x5

12

?3x1?4x2?5x3?x4?40??x5?66 s.t.?6x1?4x2?3x3?x?0,j?1,2,...,5?j列表计算如下： CB 0 0 4 0 4 3 XB x4 x5 x3 x5 x3 x1 b 40 66 8 42 2 10 38 0 －3/7 0 －5/7 －1/7 3 x1 3 6 0 3 3/5 （21/5） 12/5 3/5↑ 0 1 3 3 x2 4 4 0 3 4/5 8/5 16/5 －1/5 4/7 8/21 24/7 4 x3 （5） 3 0 4↑ 1 0 4 0 1 0 4 0 x4 1 0 0 0 1/5 －3/5 4/5 －4/5 2/7 －1/7 5/7 0 x5 0 1 0 0 0 1 0 0 －1/7 5/21 1/7 θL 8 22 40/3 10 ∴X*=（10，0，2，0，0）T ∴max z =3×10+4×2 =38 2、用单纯型法求解下面线性规划问题的解 max z =70x1+120x2

?9x1?4x2?360??4x1?6x2?200s.t.?3x?10x?300

2?1??x1，x2?0解：加入松弛变量x3，x4，x5，得到等效的标准模型：

max z =70x1+120x2+0 x3+0 x4+0 x5

s.t.

?360?9x1?4x2?x3??x4?200?4x1?6x2??x5?300 ?3x1?10x2?xj?0,j?1,2,...,5?列表计算如下：

13

CB 0 0 0 0 0 120 0 70 120 XB x3 x4 x5 x3 x4 x2 x3 x1 x2 b 360 200 300 240 20 30 1860/11 100/11 300/11 70 x1 9 4 3 0 70 39/5 （11/5） 3/10 36 34↑ 0 1 0 70 0 120 x2 4 6 （10） 0 120↑ 0 0 1 120 0 0 0 1 120 0 x3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 x4 0 1 0 0 0 0 1 0 0 0 －39/11 5/11 - 3/22 170/11 0 x5 0 0 1 0 0 - 2/5 - 3/5 1/10 12 －12 19/11 - 3/11 2/11 30/11 θL 90 100/3 30 400/13 100/11 100 43000110 0 -170/11 －30/11 ∴X=（

*

1003001860，，111111，0，0）

T

∴max z =70×

10030043000+120×=111111

3、用单纯型法求解下面线性规划问题的解

?2x1?2x2?3000?5x?2.5x?4000?12max z = 4x+3xs.t.?

x?500?1??x1,x2?01

2

解：加入松弛变量x，x4，x5，得到等效的标准形式：

3

?2x1?2x2?x3?3000?5x?2.5x?x?4000?124max z= 4x+3x+0 x+0 x+0 xs.t.?

x?x?50015??xj?0,j?1,2,...,5?1

2

3

4

5

用表解形式的单纯形法求解，列表计算如下： CB XB b 4

3

0

0

0

θL 14

x 1x 2x 3x4 x5 0 x 33000 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 x 3 0 4↑ 0 3 0 0 0 0 0 0 0 2000 0 2 1 0 -2 2000/2 =1000 0 x4 1500 0 （2.5） 0 1 -5 1500/2.5 =600 4 x 1500 1 0 0 0 1 —— 4 0 0 3↑ 0 0 0 0 4 -4 0 x 3800 0 0 1 -0.8 （2） 800/2 =400 3 x 2600 0 1 0 0.4 -2 —— 4 x 1500 1 0 0 0 1 500/1 =500 4 0 3 0 0 0 1.2 -1.2 -2 2↑ 0 x5 400 0 0 0.5 -0.4 1 3 x 21400 0 1 1 -0.4 0 4 x 1100 1 0 -0.5 0.4 0 *

4600 T

4 0 3 0 1 -1 0.4 -0.4 0 0 据上表，X=（100，1400，0，0，400）max z =4×100+3×1400=460 4、用单纯型法求解下面线性规划问题的解

max z =10x1+6x2+4x3

s.t.

?x1?x2?x3?100?10x?4x?5x?600?123? 2x?2x?6x?300123???x1，x2，x3?0

15

解：加入松弛变量x4，x5，x6，得到等效的标准模型：

max z =10x1+6x2+4x3+0 x4+0 x5+0 x6

?100?x1?x2?x3?x4?10x?4x?5x?x?600?1235?s.t.2x?2x?6x?x6?300

23?1?xj?0,j?1,2,...,6?列表计算如下：

10 CB XB b x1 0 0 0 0 10 0 6 10 0 x4 x5 x6 x4 x1 x6 x2 x1 x6 100 600 300 40 60 180 200/3 100/3 100 1 （10） 2 0 10↑ 0 1 0 10 0 0 1 0 10 0 0 －8/3 －10/3 －2/3 0 x2 1 4 2 0 6 （3/5） 2/5 6/5 4 2↑ 1 0 0 6 x3 1 5 6 0 4 1/2 1/2 5 5 －1 5/6 1/6 4 20/3 x4 1 0 0 0 0 1 0 0 0 0 5/3 －2/3 －2 10/3 6 4 0 0 x5 0 θL x6 0 0 1 0 0 0 0 1 0 0 0 0 1 0 100 60 150 200/3 150 150 0 1 0 0 0 －1/10 1/10 －1/5 1 －1 －1/6 1/6 0 2/3 22003100200∴X=（，

33*

，0，0，0，100）

T

∴max z =10×

2002200100+6×=333

5、用单纯型法求解下面线性规划问题的解

Max Z?4x1-2x2?2x3 3x1?x2?x3?60 x1?x2?2x3?10

16

2x1?2x2?2x3?40

x1,x2,x3?0

用单纯形法求解，并指出问题的解属于哪一类。 解：（1）、将原问题划为标准形得：

MaxZ?4x1?2x2?2x3?0x4?0x5?0x6 3x1?x2?x3?x4 =60 x1?x2?2x3?x5?10 2x1?2x2?2x3?x6?40

x1,x2,x3,x4,x5,x6?0

C4 -2 2 0 0 0 j Cb B XB x1 x2 x3 x4 x5 x6 0 x60 3 1 1 1 0 0 4 0 x10 [1] -1 2 0 1 0 5 0 x40 2 -2 2 0 0 1 6 ?4 -2 2 0 0 0 j 4 -2 2 0 0 0 Cj Cb B XB x1 x2 x3 x4 x5 x6 0 x30 0 4 -5 1 -3 0 4 4 x10 1 -1 2 0 1 0 1 0 x20 0 [4] -6 0 -2 1 6 ?0 2 -6 0 -4 0 j C4 -2 2 0 0 0 j Cb B XB x1 x2 x3 x4 x5 x6

17

0 x4 10 0 0 1 1 -1 -1 4 x1 x2 15 1 0 1/2 0 1/2 1/4 -2 5 0 1 -3/2 0 -1/2 1/4 ?j T

0 0 -3 0 -3 -1/2 所以X=（15，5，0，10，0，0） 为唯一最优解 Max Z=4*15-2*5=50 6、用单纯形法求解下述LP问题。

max z?2.5x1?x2?3x1?5x2?15 ?s.. t?5x1?2x2?10?x,x?0?12解：引入松弛变量

x3、x4，化为标准形式：

max z?2.5x1?x2?3x1?5x2?x3?15 ?s.. t?5x1?2x2?x4?10?x,x,x,x?0?1234构造单纯形表，计算如下：

cj 2.5 1 0 0 cB 0 XB x3 b 15 x1 3 x2 5 x3 1 x4 0 ?i 5 0 x4 10 [5] 2 0 1 2 ?j 0 2.5 1 0 0 x3 x1 9 0 [19/5] 1 －3/5 45/19 2.5 2 1 2/5 0 1/5 5 ?j 1 0 0 0 －1/2 x2 45/19 0 1 5/19 －3/19 18

2.5 x1 20/19 1 0 －2/19 5/19 ?j 由单纯形表，可得两个最优解

0 0 0 －1/2 X(1)?(2,0,9,0)T、X(2)?(20/19,45/19,0,0)T，所以两点之间的所有解都是

最优解，即最优解集合为：

?X(1)?(1??)X(2)，其中0???1。

7、用单纯形法解线性规划问题

maxz?2x1?x2??5x2?15??6x1?2x2?24?x1?x2?5??x1?0x2?0

解：化为标准型

maxz?2x1?x2?0x3?0x4?0x5??5x2?x3?15??6x1?2x2?x4?24?x1?x2?x5?5??x1?5?0列出单纯形表

Cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 15 0 5 1 0 0 0 x4 24 [6] 2 0 1 0 4 0 x5 5 1 1 0 0 1 5 -Z 0 2 1 0 0 0 0 x3 15 0 5 1 0 0 3 2 x1 4 1 1/3 0 1/6 0 12 0 x5 1 0 [2/3] 0 -1/6 1 3/2 -Z -8 0 1/3 0 -1/3 0 0 x3 15/2 0 0 1 5/4 -15/2 2 x1 7/2 1 0 0 1/4 -1/2 1 x2 3/2 0 1 0 -1/4 3/2 -Z -20 0 0 0 -1/4 -1/2

Z*=17/2, X*=(7/2,3/2, 15/2,0,0)’

19

8、用单纯型法求解下面线性规划问题的解

maxz?x1?x2??x1?2x2?2???2x1?x2?2??x1?x2?4??x1?0x2?0解：

Cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 2 [1] 12 1 0 0 2 0 x4 2 -2 1 0 1 0 0 x5 4 -1 1 0 0 1 -Z 0 1 1 0 0 0 1 x1 2 1 -2 1 0 0 0 x4 6 0 -3 2 1 0 0 x5 6 0 -1 1 0 1 -Z -2 0 3 -1 0 0 把表格还原为线性方程

maxz?3x2?x3?2??x1?2x2?x3?2

??3x?2?2x3?x4?6??x2?x3?x5?6

??x1?2?2x2?x3?x4?6?3x?2x?23

?x5?6?x2?x3令x 3=0

??x1?2?2x2?x4?6?3x

?2?x5?6?x2此时，若让x2进基，则会和基变量x1同时增加，使目标函数值无限增长，所以本题无界

9、用单纯型法求解下面线性规划问题的解

20

maxz?2x1?4x2?x1?2x2?x?1?x2???x1?0

?8?4?3x2?0Cj CB 0 0 0 0 0 4 2 0 4 2 0 4 XB b 8 4 3 0 2 4 3 -12 2 2 3 -20 4 1 2 -20 2 4 0 0 0 4 3 2 4 x1 1 1 0 2 [1] 1 0 2 1 0 0 0 1 0 0 0 x2 2 0 [1] 4 0 0 1 0 0 0 1 0 0 0 1 0 x3 1 0 0 0 1 0 0 0 1 -1 0 -2 0 -1/2 1/2 -2 x4 0 1 0 0 0 1 0 0 0 1 0 0 1 1/2 -1/2 0 x5 0 0 1 0 -2 0 1 -4 -2 2 1 0 0 1 0 0 x3 x4 x5 -Z x3 x4 x2 -Z x1 x4 x2 -Z x1 x5 x2 -Z Z*=20, X*=(2,3,0,2,0)’Z*=20, X*=(4,2,0,0,1)’ 10、用单纯型法求解下面线性规划问题的解

maxz?3x1?5x2?x1?2x2???3x1?2x2??x1?0解：列表如下

Cj CB 0 0 0 XB b 4 12 18 0 3 5 0 0 0 6 9 ?4?12?18x2?0x1 1 0 3 3 x2 0 [2] 2 5 x3 1 0 0 0 x4 0 1 0 0 x5 0 0 1 0 x3 x4 x5 -Z 21

0 5 0 0 5 3 x3 x2 x5 -Z 4 6 6 -30 6 2 2 -20 1 0 [3] 3 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1/2 -1 -5/2 1/3 1/2 -1/3 -3/2 0 0 1 0 -1/3 4 3 x3 x2 x1 -Z 0 1/3 -1 X*=(2,6,6,0,0)’ Z*=36

11、用单纯型法求解下面线性规划问题的解

maxz?2x1?x2?5x1?15?6x?2x?24?12 st.??x2?x2?5??x1,x2?0解：化为标准型

maxz?2x1?x2?5x1?x3?15?6x?2x?x?24 ?124st.??x2?x2?x5?5??x1,x2,x3,x4,x5?0单纯型表如下：

Cj CB 0 0 0 0 2 0 0 2 1 XB x3 x4 x5 Z x3 x1 x5 Z x3 x1 x2 Z b 15 24 5 0 15 4 1 0 15/2 7/2 3/2 17/2 2 1 0 0 0 – 4 5 3 12 3/2 x1 0 [6] 1 2 0 1 0 0 0 1 0 0 x2 5 2 1 1 5 1/3 [2/3] 1/3 0 0 1 0 x3 1 0 0 0 1 0 0 0 1 0 0 0 x4 0 1 0 0 0 1/6 -1/6 -1/3 5/4 1/4 -1/4 -1/4 x5 0 0 1 0 0 0 1 0 -15/2 -1/2 3/2 -1/2 由些可得，问题的最优解为x1=7/2，x2=3/2，最优值max z=17/2 12、用大M法求解如下线性规划模型：

min z =5x1＋2x2＋4x3

22

?3x1?x2?2x3?4??6x1?3x2?5x3?10 ?x,x,x?0?123解：用大M法，先化为等效的标准模型：

max z =－5x1－2x2－4x3

s.t.

/

?3x1?x2?2x3?x4?4??x5?10 ?6x1?3x2?5x3?y?0,j?1,2,...,5?j增加人工变量x6、x7，得到：

max z =－5x1－2x2－4x3－Mx6－Mx7

s.t

/

?3x1?x2?2x3?x4?x6?4??x5?x7?10 ?6x1?3x2?5x3?x?0,j?1,2,...,7?j大M法单纯形表求解过程如下：

－5 CB XB b x1 －M －M －5 －M x6 x7 x1 x7 4 10 4/3 2 （3） 6 －9M 9M－5↑ 1 0 －5 x2 1 3 －4M 4M－2 1/3 1 -M－5/3 x3 2 5 －7M 7M－4 2/3 1 -M－10/3 x4 －1 0 M －M －1/3 （2） -2M+5/3 x5 0 －1 M －M 0 －1 M x6 1 0 －M 0 1/3 －2 2M－5/3 x7 0 1 －M 0 0 1 -M 4/3 5/3 —— 1 －2 －4 0 0 －M －M θL 0 M－1/3 M－2/3 2M－5/3↑ －M －3M+5/3 0 －5 0 x1 x4 5/3 1 1 0 －5 0 1/2 （1/2） －5/2 1/2↑ 5/6 1/2 －25/6 1/6 0 1 0 0 －1/6 －1/2 5/6 －5/6 0 －1 0 －M 1/6 1/2 －5/6 －M+5/6 10/3 2 x1 －5 －2 x2 2/3 1 0 1/3 －1 1/3 1 －1/3 2 0 1 1 2 －1 －2 1 23

－223－5 0 －2 －11/3 1 1/3 －1 －1/3 0 －1/3 －1 －1/3 －M+1 －M+1/3 2∴x=（

3*

，2，0，0，0）

T

最优目标函数值min z =－max z =－（－

/

223）=

223

13、用大M法求解如下线性规划模型：

min z =540x1＋450x2＋720x3

?3x1?5x2?9x3?70??9x1?5x2?3x3?30 ?x,x,x?0?123解：用大M法，先化为等效的标准模型：

max z =－540x1－450x2－720x3

s.t.

/

?3x1?5x2?9x3?x4?70??x5?30 ?9x1?5x2?3x3?y?0,j?1,2,...,5?j增加人工变量x6、x7，得到：

max z =－540x1－450x2－720x3－Mx6－Mx7

s.t

/

?3x1?5x2?9x3?x4?x6?70??x5??x7?30 ?9x1?5x2?3x3?x?0,j?1,2,...,5?j大M法单纯形表求解过程如下：

－540 CB XB b x1 －M －M －M x6 x7 x6 70 30 60 3 （9） －12M 12M－540↑ 0 x2 5 5 －10M 10M－450 10/3 x3 9 3 －12M 12M－720 （8） x4 －1 0 M －M －1 x5 0 －1 M －M 1/3 x6 1 0 －M 0 1 x7 0 1 －M 0 －1/3 70/3 30/9=10/3 60/8=2.5 －450 －720 0 0 －M －M θL 24

10/3/1/3 －540 x1 10/3 1 5/9 1/3 0 －1/9 0 1/9 =10 -300+10/3M -8M－180 －M －M/3+60 －M M/3－60 0 -150+10/3M 8M-540↑ M M/3－60 0 －M/3+60 15/2/5/12 －720 x3 15/2 0 5/12 1 －1/8 1/24 1/8 －1/24 =18 5/6/5/12 －540 x1 5/6 1 （5/12） 0 1/24 －1/8 －1/24 1/8 =2 －540 0 －572 125↑ －720 0 －135/2 135/2 475/12 －475/12 －135/2 135/2－M －75/2 75/2－M x3 －720 －450 x2 20/3 －1 0 1 1/6 1/6 1/6 －1/6 2 12/5 1 0 1/10 －3/10 －1/10 3/10 －360 －5700 －180 －450 －720 75 15 －75 －15 0 0 －75 －15 75－M 15－M 20∴该对偶问题的最优解是x=（0，2，

3*

，0，0）

T

最优目标函数值min z =－（－5700）=5700 14、用单纯形法求解线性规划问题

maxz??3x1?x3?x1???2x??1????x1?0化成标准形式有

x2?x2?3x2?x3?x3?x3?419x2?0x3?0maxz??3x1?x3?0x4?0x5x2??x1???2x?x??12?3x2????x1?5?0

加入人工变量则为

x3?x3x3x4?x5?4?1?9 25

maxz??3x1?x3?0x4?0x5?Mx6?Mx7??x1?x2?x3?x4?4???2x1?x2?x3?x5?x6?1?3x2?x3?x7?9??x1?7?0

列出单纯形表

Cj －3 0 1 0 0 －M -M CB XB b x1 x2 x3 x4 x5 x6 x7 0 x4 4 1 1 1 1 0 0 0 -M x6 1 -2 [1] -1 0 -1 1 0 -M x7 9 0 3 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 0 x2 1 -2 1 -1 0 -1 1 0 -M x7 6 [6] 0 4 0 3 -3 1 -Z 6M 6M-3 0 4M+1 0 3M -4M 0 0 x4 0 0 0 0 1 -1/2 -1/2 1/2 0 x2 3 0 1 1/3 0 0 0 1/3 -3 x1 1 1 0 [2/3] 0 1/2 -1/2 1/6 -Z 3 0 0 3 0 3/2 -M-3/2 -M+1/2 0 x4 0 0 0 0 1 -1/2 1/2 -1/2 0 x2 5/2 -1/2 1 0 0 -1/4 1/4 1/4 1 x3 3/2 3/2 0 1 0 3/4 -3/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、用单纯形法求解线性规划问题

maxz??3x1?2x2??2x1?x2?2??3x1?4x2?12???x1?0x2?0

解 化为标准形式有

26

maxz??3x1?2x2?0x3?0x4?Mx5??2x1?x2?x3?2??3x1?4x2?x4?x5?12???x1?5?0

列表计算

Cj －3 －2 0 0 M CB XB b x1 x2 x3 x4 x5 0 x3 2 2 [1] 1 0 0 2 M x5 12 3 4 0 -1 1 3 -Z -12M 3M+3 4M+2 0 -M 0 -2 x2 2 2 1 1 0 0 M x5 4 -5 0 -4 -1 1 -Z 4-4M -5M-1 0 -4M-2 -M 0

X*=(0,2,0,0,4)’ Z*=4M-4 说明原问题无解 ?

写对偶问题（10）

1、 写出下列线性绘画问题的对偶问题

maxz?2x1?x2?3x3?x4

??x1?x2?x3?x4?52x

??1?x2?3x3??4?x1?x3?x4?1 ??x1,x3?0,x2,x4无约束解：

min??5y1?4y2?y3

??y1?2y2?y3?2?

?y1?y2?1?y1?3y2?y3?3 ??y1?y3?1??y1?0,y2无约束,y3?02、写出下述线性规划的对偶问题

27

maxz?x1?4x2?3x3??2x1?3x2?5x3?2??3x1?x2?6x3?1?x1?x2?x3?4??x1?0x2?0x3无约束解

minw?2y1?y2?4y3??2y1?3y2?y3?1??3y1?y2?y3?4??5y1?6y2?y3?3??y1?0y2?0y3无约束

3、写出下列线性规划的对偶问题解：

minmaxz?25x1?2???xw?yx2?3x31x?y2?y32?x3?1???1??xy?1??2yx2?2y3?12?x3125??2yx1??2xy2?y?3?2?x3?12???xy11?y2?y3?3??y1?0x2?0x3无约束1?0y2?0y3无约束4、写出下列线性规划的对偶问题

maxz?2x1?x2?4x3??2x1?3x2?x3?1??3x1?x2?x3?4?x1?x3?3??x1?0x2?0x3无约束解

minw?y1?4y2?3y3??2y1?3y2?y3?2??3y1?y2?1?y1?y2?y3?4??y1?0y2?0y3无约束 28

? 对偶性质

1、已知线性规划问题如下：

Max Z=

x1?3x2

5x1?10x2?50

x1?x2?1

x2?4

x1,x2?0

已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解。 解：该问题的对偶问题为：

MinZ?50y1?y2?4y3 5y1?y2?1

10y1?y2?y3?3 y1,y3?0;y2?0 将X=（2，4）T

代入原问题可知：x1?x2〉1 为严格不等式，所以y2?0由对偶问题性质可知：

50y1?4y3?14 解之得： y1?1/5 10y1?y3?3 y2?0

y3?1

所以Y=（1/5，0，1）

T

Min Z=14 2、已知线性规划问题

minz?2x1?3x2?5x3?6x4

?x1?2x2?3x3?x4?

?2??2x1?x2?x3?3x4??3??xj?0(j?1,2,3,4)用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。

答案Y*?(81：(对偶问题的最优解为

5,5)；

(依据z*=w*及互补松弛性，有x4=0,且

29

?2x1?3x2?5x3?19/5? ?x1?2x2?3x3?2?2x?x?x?323?1解得愿问题最优解X*=(7/5,0,1/5,0)。 3、已知线性规划问题

min??2x1?3x2?5x3?2x4?3x5

s.t.x1?x2?2x3?x4?3x5?4 2x1?x2?3x3?x4?x5?3

xj?0,*y1?

j?1,2,?,5

已知其对偶问题的最优解为

4*3,y2?，最优值为z*?5。试用对偶理论找出原问题的最优解。 55解 先写出它的对偶问题

maxz?4y1?3y2

y1?2y2?2 ①

y1?y2?3 ②

s.t.

2y1?3y3?5 ③

y1?y2?2 ④ 3y1?y2?3 ⑤ y1,y2?0

**x*?(x1,?,x5)，由互补松弛性得

将

**y1,y2的值代入约束条件，得②，③，④为严格不等式；设原问题的最优解为

*****,y2?0；原问题的两个约束条件应取等式，故有 x2?x3?x4?0。因 y1**3x1?x5?4 **2x1?x5?3

**x1?1,x5?1；故原问题的最优解为

求解后得到

X*?[10001]' ；最优值为w*?5。

30

4、已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。

LP:maxz?x1?2x2DP:minw?2y1?3y2?y3??3x1?x2?2???3y1?y2?y3?1??x1?2x2?3??x?y1?2y2?3y3?21?3x2?1???x1,x2?0??y1?0y2?0y3?0

解：第一步，写出对偶问题

第二步，将LP，DP都化为标准型

LP:maxz?x1?2x2DP:minw?2y1?3y2?y3??3x1?x2?x1S?2?y3?y1S?1??3y1?y2???x1?2x2?x2S?3?3y3?y2S?2?x?y1?2y2?1?3x2?x3S?1???x1,x2?0x1S,2S,3S?0??y1?0y2?0y3?0y1S,2S?0

第三步：将最优解代入标准型中，确定松弛变量取值

??3?1?11?77?x1S?2???x1S???1?2?11?x?0?772S?3??x2S?0??111?39?7?3?7?x?x3S?1?3S?7

第四步：利用互补松弛定理

?X1SY*X(Y???S?1*,Y2*,Y3*)?X2S??Y1*X1S?Y2*X2S?Y3*X3S?0

??X3S??∴ Y3*=0

Y*?(Y?X1*?SX1S,Y2S)??X*???Y1SX1*?Y2SX2*?0

?2?

∴ Y1S=0 Y2S=0

第五步：将Y3*=0 Y1S=0 Y2S=0 代入约束条件

31

则有

?3y1?y2?14???y1??7?y1?2y2?2?y2?5 7

∴ 对偶问题的最优解为Y*=(4/7,5/7,0)’

maxz?x1?x2??x15、已知线性规划问题：??x2?x3?2，试用对偶理论证明上述线性规划问题无最优解。

??2x?xx?12?3?1?x1,x2,x3?0证明：首先看到该问题存在可行解，例如

X??00minw?2y1?y2???y1?2y2?1??y1?y2?1 ?y1?y2?0??y1,y2?0由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。 5、已知线性规划问题

minz?2x1?3x2?5x3?6x4?x1?2x?x2?3x3?x4?2s.t.???2x 12?x3?3x4??3??xj?0?j?1,2,3,4?（1）写出其对偶问题；

（2）用图解法求对偶问题的解；

（3）利用（2）的结果及对偶性质求原问题解。 解：（1）原线性规划问题可化为：

minz?2x1?3x2?5x3?6x4?x1?2x2?3x3?x4?2s.t.?

?2x?1?x2?x3?3x4?3?xj?0?j?1,2,3,4?其对偶问题为：

maxw?2y1?3y2??y1?2y2?22y1?y?3s.t.??2

?3y?1?y2?5?y1?3y2?6??y1,y2?0 0?，而上述问题的对偶问题为：32

（2）用图解法解得

8119Y*?(y1,y2)?(,) w*?

555（3）由互补松弛性定理知道，

?y1?3y2?1?6,?x4?0

??2x?3x192?5x?又由z*?w*,可得：?135?x1?2x2?3x?3?2

?2x?x??12x3?3解之，可得原问题最优解X*?(75,0,15,0)。

对偶单纯形法（15

1、用对偶单纯形法解下列线性规划问题

minw?15x1?24x2?5x3??6x2?x3?2?5x1?2x?2?x3?1?x1?3?0

解：先化为标准型

maxz??15x1?24x2?5x3?0?x4?0?x5??6x2?x3?x4?2?5x2xx?1?2?3?x5?1?x1?5?0

约束条件两边同乘(-1)

???6x2?x3?x4??2??5x?2x1?12?x3?x5???列单纯形表

Cj －15 －24 －5 0 0 CB XB b x1 x2 x3 x4 x5 0 x4 －2 0 [-6] -1 1 0 0 x5 －1 －5 -2 -1 0 1 -15 -24 -5 0 0 --- 4 5 -24 x2 1/3 0 1 1/6 -1/6 0 0 x5 -1/3 -5 0 [-2/3] -1/3 1 -15 0 -1 -4 0 33

3 3/2 12 -24 x2 1/4 -5/4 1 0 -1/4 1/4 -5 x3 1/2 15/2 0 1 1/2 -3/2 -15/2 0 0 -7/2 -3/2

X*=(0,1/4,1/2)’ Y*=(7/2,3/2)

2、用对偶单纯形法解下列线性规划问题

minz?4x1?12x2?18x3??x1?3x3?3?2x2x?2?3?5?x1?3?0

解：改写为标准形式

maxz'??4x1?12x2?18x3?0?x4?0?x5???x1?3x3?x4??3??2x?2?2x3?x5??5

?x1?5?0

列单纯形表如下：

Cj －4 －12 －18 0 0 CB XB b x1 x2 x3 x4 x5 0 x4 －3 －1 0 -3 1 0 0 x5 －5 0 [-2] -2 0 1 -4 -12 -18 0 0 --- 6 9 0 x4 -3 -1 0 [-3] 1 0 -12 x2 5/2 0 1 1 0 -1/2 -4 0 -6 0 -6 4 2 12 --- -18 x3 1/3 0 1 -1/3 0 13/2 -12 x2 -1/3 1 0 1/3 -1/2 -2 0 0 -2 -6

X*=(0,3/2,1)’ Y*=(2,6) 3、用对偶单纯形法求解下面的问题：

minz?12x1?8x2?16x3?12x4??2x1?x2?4x3?2?2x?2x?12?4x4?3

?x1,x2,x3,x4?0

34

解：令

z??z，则问题可以标准化为：

??maxz??12x1?8x2?16x3?12x4??2x1???2x1?x,?1取

?x2?2x2x2,x3,?4x3?4x4x4,x5,??x6x5x6???2??30

?P5?10?P6????01????为初始基，则

?x5???2??x?????3??,其余xj?0?6???是非基可行解，但

?1??12,?2??8,?3??16,?4??12，

?Y?CBB?1是对偶可行解，建立单纯形表（见表4-1）

计算结果如下：最优解

?x2??3/2??x????1/8??,其余xj?0，最优值z?14.。

??3???x1??1/2?或最优解

?x????1??,其余xj?0，最优值z?14.。

??2??本例如果用单纯形法计算，确定初始基可行解时，还需要引入两个人工变量

表3-1：

?x7x8?，计算量要多于对欧单纯形法。

C ?12?8?16?1200 ? 备注 CB 0 0XB x5x6 B?1b ?2?3 x1x2x3x4x5x6 ??3/4 K=4 L=2 ?2?1?4010 ?2?20?401-4 ? 0?12 ?12?8?16?1200 -1 x5 x4?23/4 ?2?11/21/2?4010100 ?1/423/2 L=1 K=2 ? ?8?12 ?62?1/4 ?2?160040?1?211/2?3 0 ?1/4 x2 x421?-1/21/ 20L=2 K=1或3 ? ?20?80?2?3 35

?8?12 ?

灵敏度分析 x5x1 1 1/201?44?3?1 104?2?11/2 1、已知线性规划的标准形式为

maxz??x1?2x2?x3?0?x4?0?x5?x1??2x1??

Cj CB 2 0

问：(1)当C1由－1变为4时，求新问题的最优解

(2)讨论C2在什么范围内变化时，原有的最优解仍是最优解

解：由表可知，C1是非基变量的价值系数，因此C1的改变只影响σ1

XB b 6 10 -12 －1 2 1 0 0 ?x2?x2?x3x1?5?0?x4?x5?6?4

其最优单纯形表如下

x1 1 3 -3 x2 1 0 0 x3 1 1 -1 x4 1 1 -2 x5 0 1 0 x2 x5 -Z ?1'?c1'?z1'?(c1??c1)?CBB?1p1?(c1?CBB?1p1)??c1??1??c1??3?5?2?0可见最优性准则已不满足，继续迭代

Cj CB 2 0 2 4 XB b 6 10 -12 8/3 10/3 -56/3 4 2 1 0 0 6 10/3 x1 1 [3] 2 0 1 0 x2 1 0 0 1 0 0 x3 1 1 -1 2/3 1/3 -5/3 x4 1 1 -2 2/3 1/3 -8/3 x5 0 1 0 -1/3 1/3 -2/3 x2 x5 -Z x2 x1 -Z (2)要使原最优解仍为最优解，只要在新的条件下满足σ≤0成立，因为x2是基变量，所以所有的σ值都将发生变化

σ＝C-CBBA

-1

36

?(c?11,c2',c3,c4,c5)?CBB(p1,p2,p3,p4,p5)?(?1,c',1,0,0)?(c?10??11110?22',c5)???11??????2?1001????(?1,c?(c?11110?2',1,0,0)2',0)???30111?? ??(?1,c2',1,0,0)?(c2',c2',c2',c2',0)?(?1?c2',0,1?c2',?c2',0)?0

??1?c2'?0即 ??1?c2'?0

???c2'?0

则c2’≥1 c2+△c2≥1 △c2≥-1

所以当x2的系数△c2≥-1时，原最优解仍能保持为最优解。

2．已知线性规划问题及其最优单纯形表

maxz??x1?x2?4x3??x1?x2?2x3?9??x1?x2?x3?2??x1?x2?x3?4??x1?3?0

Cj －1 －1 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 －1 x1 1/3 1 -1/3 0 1/3 0 -2/3 0 x5 6 0 2 0 0 1 1 4 x3 13/3 0 2/3 1 1/3 0 1/3 -Z -17 0 -4 0 -1 0 -2

?9??3?若右端列向量b???2??????2??，求新问题的最优解。 ?4????3??

??1解：X?1?b)??102??3??1/30?2/3??3???1??11?1??2???01??2?B?B(b?1??5? ?001??????????????3????1/301/3????3????2??

37

因为－1小于0，因此继续迭代

Cj －1 －1 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 －1 x1 －1 1 -1/3 0 1/3 0 [-2/3] 0 x5 5 0 2 0 0 1 1 4 x3 2 0 2/3 1 1/3 0 1/3 -Z -9 0 -4 0 -1 0 -2 σj/arj 12 3 0 x6 3/2 -3/2 1/2 0 -1/2 0 1 0 x5 7/2 3/2 3/2 0 1/2 1 0 4 x3 3/2 1/2 1/2 1 1/2 0 0 -Z -6 -3 -3 0 -2 0 0

∴新问题的最优解为X*=(0,0,3/2,0,7/2,3/2)’ Z*=6

3、已知线性规划问题及其最优单纯形表

maxz?2x1?3x2?x3??1x?1x2?1x3?x4?1??31?133x1?4x?7x?x?332335?3

?x1?5?0??最优单纯形表如下：

Cj 2 3 1 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 1 1 0 －1 4 －1 6 3 x2 2 0 1 2 －1 1 10/3 -Z -8 0 0 -3 -5 －1

?1/3??1/10?若p3

由原来的

?7/3???1/3?，最优解将如何改变？ ????

p1p?4?1???1/10解：计算

???1/15?3'?B?3'????11???1/3???????7/30??

???

38

???23????1/15??7/30????1/6?0 ∴ 继续迭代

Cj 2 3 1 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 1 1 0 1/15 4 －1 15 3 x2 2 0 1 [7/30] －1 1 60/7 -Z -8 0 0 1/6 -5 －1 2 x1 3/7 1 -2/7 0 30/7 －9/7 15 1 x3 60/7 0 -30/7 1 -30/7 -30/7 60/7 -Z -66/7 0 -5/7 0 -30/7 －12/7

X*=(3/7,0,60/7,0,0) Z*=66/7 例4

(仍以例2为例) 已知线性规划问题及其最优单纯形表

maxz??x1?x2?4x3??x1?x2?2x3?9??x1?x2?x3?2??x1?x2?x3?4??x1?3?0

Cj －1 －1 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 －1 x1 1/3 1 -1/3 0 1/3 0 -2/3 0 x5 6 0 2 0 0 1 1 4 x3 13/3 0 2/3 1 1/3 0 1/3 -Z -17 0 -4 0 -1 0 -2

现增加一个新变量x7，且c7=3，p7=(3,1,-3)’，求新问题的最优解。

?1/30?2/3解：由表知：

B?1????011?? ??1/301/3??

??1/30?2/3????3????3??∴ pB?17'?p7??011???1????2? ?1/301/3?????3????0??

39

?3????17?c7?CBB?p7?3?(?1,0,4)??2??6?0

??0??∴ 继续迭代

Cj －1 －1 4 0 0 0 3 CB XB b x1 x2 x3 x4 x5 x6 x7 －1 x1 1/3 1 -1/3 0 1/3 0 -2/3 [3] 0 x5 6 0 2 0 0 1 1 -2 4 x3 13/3 0 2/3 1 1/3 0 1/3 0 -Z -17 0 -4 0 -1 0 -2 6 3 x7 1/9 1/3 -1/9 0 1/9 0 -2/9 1 0 x5 56/9 2/3 16/9 0 2/9 1 5/9 0 4 x3 13/3 0 2/3 1 1/3 0 1/3 0 -Z -53/3 -2 -10/3 0 -5/3 0 -2/3 0

∴ X*=(0,0,13/3,0,56/9,0,1/9)’ Z*=53/3

5．已知线性规划问题及其最优单纯形表 Cj －1 －1 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 －1 x1 1/3 1 -1/3 0 1/3 0 -2/3 0 x5 6 0 2 0 0 1 1 4 x3 13/3 0 2/3 1 1/3 0 1/3 -Z -17 0 -4 0 -1 0 -2 现增加新约束?3x1?x2?6x3?17，求新问题的最优解。

解：将原问题的最优解代入新增约束?3?13?0?6?133?25?17

不满足新增加的约束条件，因此引入松弛变量x7后，新增约束变为 ?3x1?x2?6x3?x7?17 ，加进最优表得：

Cj －1 －1 4 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 x7 －1 x1 1/3 1 -1/3 0 1/3 0 -2/3 [3] 0 x5 6 0 2 0 0 1 1 -2 4 x3 13/3 0 2/3 1 1/3 0 1/3 0 0 x7 17 -3 1 6 0 0 0 1 -Z -17 0 -4 0 -1 0 -2 0 －1 x1 1/3 1 -1/3 0 1/3 0 -2/3 0 0 x5 6 0 2 0 0 1 1 0 40

4 0 x3 x7 -Z 13/3 -8 -17 0 0 0 2/3 -4 -4 1 6 0 1/3 -1 -1 0 0 0 1/3 [-4] -2 0 1 0 ?j/arj' －1 0 4 0

∴ X*=(5/3,0,11/3,0,4,2,0)’ Z*=13

5、线性规划问题

1 1 1/2 x1 x5 x3 x6 -Z 5/3 4 11/3 2 -13 1 0 0 0 0 1/3 1 1/3 1 -2 0 0 1 0 0 1/2 -1/4 1/4 1/4 -1/2 0 1 0 0 0 0 0 0 1 0 -1/6 1/4 1/12 -1/4 -1/2 maxZ?2x1?x2?x3

?x1?x2?x3?6???x1?2x2?4?x,x,x?0?123

用单纯形法求解得最终单纯形表如下表所示。

x1 6 10 1 0 0 x2 1 3 -3 x3 1 1 -1 x4 1 1 -2 x5 0 1 0 x1 X5 cj-zj 试说明分别发生如下变化时，新的最优解是什么？

（1）目标函数变为

maxZ?2x1?3x2?x3；

?6??3?（2）约束条件右端项由

?4?变为?4?； ????（3）增添一个新的约束解：（1）

cj→ CB 2 0 xB b 6 10 2 3 1 0 0 θi ?x1?2x3?2。

x1 1 0 0 x2 1 [3] 1 0 1 0 x3 1 1 -1 2/3 1/3 -4/3 x4 1 1 -2 2/3 1/3 -7/3 x5 0 1 0 -1/3 1/3 -1/3 2 0 2 0 x1 x5 cj-zj 2 3 x1 X2 cj-zj 8/3 10/3 1 0 0 因为所有的检验数均小于等于零。故最优解为

X*?(8/3,10/3,0,0,0)

41

（2）因为

?10???3???3??1。所以Bb? B?1??,?b????????3??11??0?cj→ 2 b 3 7 -1 1 0 0 θi xB CB 2 0 x1 1 0 0 x2 1 3 -3 x3 1 1 -1 x4 1 1 -2 x5 0 1 0 x1 x5 cj-zj 因为所有的检验数均小于等于零，故最优解为

X*?(3,0,0,0,7)

（3）由于

?x1?2x3??6?2?0??6?2，

所以原问题的最优解不是该问题的最优解。

，并加上松弛变量x6， ?x1?2x3?2左右两端同时乘以“-1”

在约束条件

得到

x1?2x3?x6??2

cj→ 2 b 6 10 -2 -1 1 0 0 0 θi xB CB 2 0 0 x1 1 0 1 0 x2 1 3 0 -3 1 3 -1 -3 2/3 8/3 1/3 -8/3 x3 1 1 -2 -1 1 1 [-3] -1 0 0 1 0 x4 1 1 0 -2 1 1 -1 -2 2/3 2/3 1/3 -5/3 x5 0 1 0 0 0 1 0 0 0 1 0 0 x6 0 0 1 0 0 0 1 0 1/3 1/3 -1/3 -1/3 x1 x5 x6 cj-zj 2 0 0 x1 x5 x6 cj-zj 6 10 -8 1 0 0 0 2 0 1 x1 x5 x3 cj-zj 10/3 22/3 8/3 1 0 0 0 因为所有的检验数均小于等于零，故最优解为

X*?(10/3,0,8/3,0,22/3)

42

第三章 运输问题（15）

1、安排一个使总运费最低的运输计划，并求出最低运费。

运 产 价 1 2 3 需求量 销地 A1 A2 A3 A4 产量 产 地 6 10 12 30 11 7 8 40 10 6 8 50 9 14 11 30 50 70 30 要求：先用最小元素法求出一个初始方案，再用闭回路法，求检验数。如果不是最优，改进为最优。

解：1）先用最小费用法（最小元素法）求此问题的初始基本可行解： 费 销 A 1 A 2 A 3 A 4 Si 用 产 地 地 6 1 11 10 9 50 30 × × 20 10 2 7 6 14 70 × 20 50 × 12 3 8 8 11 30 × 20 × 10 150 dj 30 40 50 30 150 ∴初始方案：Z=6×30+9×20+7×20+6×50+8×20+11×10=1070 2）用闭回路法，求检验数：

费 用 销 地 A 1 A 2 A 3 A 4 Si 产 地 6 1 30 × × 20 11 －5 10 －5 9 50 10 2 －3 7 6 14 －4 70 × 20 50 × 12 3 －4 8 8 －1 11 30 × 20 × 10 43

dj 30 40 50 30 150 150 从上表可看出，所有检验数?j≤0，已得最优解。

∴该指派问题的最优方案就是上面用“最小费用法”求得的初始方案 求出最小费用Z=6×30+9×20+7×20+6×50+8×20+11×10=1070 2、给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费） B1 B2 B3 B4 si A1 A2 A3 1 2 3 4 8 7 6 5 9 10 11 9 10 80 15 dj 8 22 12 18 1）用最小费用法求初始运输方案，并写出相应的总运费；（5分） 2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分） 解：用“表上作业法”求解。

1）先用最小费用法（最小元素法）求此问题的初始基本可行解：

费 用 销 地 B1 B2 B3 B4 Si 产 地 1 A1 8 2 × × 2 3 4 10 8 A2 7 6 5 20 × × 2 18 9 A3 10 11 9 30 × 20 10 × 60 60 dj 8 22 12 18 ∴初始方案：

2

8

B1

B3

A3

20

B2

Z=1×8+2×2+6×2+5×18+10×20+11×10=424

A1

A2

18

2 B2

B4

10 44 3

B

2）①用闭回路法，求检验数：

费 用 销 地 B1 B2 B3 B4 Si 产 地 1 A1 8 2 × × 2 3 0 4 －2 10 8 A2 －4 7 －2 6 5 20 × × 2 18 9 A3 0 10 11 9 1 30 × 20 10 × 60 60 dj 8 22 12 18 ∵

?34=1＞0，其余?j≤0

x34作为入基变量迭代调整。

∴选

②用表上闭回路法进行迭代调整：

费 用 销 地 B1 B2 B3 B4 Si 产 地 1 A1 8 2 × × 2 3 －1 4 －3 10 8 A2 －3 7 －1 6 5 20 × × 12 8 9 A3 0 10 11 －1 9 30 × 20 × 10 60 60 dj 8 22 12 18 调整后，从上表可看出，所有检验数

?j≤0，已得最优解。

∴最优方案为：

8

B1

45

A1

最小运费Z=1×8+2×2+6×12+5×8+10×20+9×10=414 3、下列是将产品从三个产地运往四个销地的运输费用表。 12 B3 A3 20 B2 A2 8 B4 A3 A4 10 B4 产量 运 价 销 地 A1 A2 产 1 9 12 9 6 50 产 地 2 7 3 7 7 60 3 6 5 9 11 50 需求量 40 40 60 20 要求：?用最小费用法建立运输计划的初始方案；

?用位势法做最优解检验； ?求最优解和最优方案的运费。

解：?先用最小费用法（最小元素法）求此问题的初始基本可行解：

费 用 销 地 A 1 A 2 A 3 A 4 Si 产 地 9 1 × × 30 20 12 9 6 50 7 2 3 7 7 60 × 40 20 × 6 3 5 9 11 50 40 × 10 × 160 dj 40 40 60 20 160 ∴最小费用法初始方案：

30

A3

2

40

A2

3

40

A1

1

20 20

A4

A3

10 46

A3

初始方案总运费Z=9×30+6×20+3×40+7×20+6×40+9×10=980

?按题目要求用位势法，作最优解检验：

费 用 销 地 A 1 A 2 A 3 A 4 ui 产 地 9 1 × × 30 20 0 12 0 9 6 0 7 2 7 3 7 7 －2 －9 × 40 20 × 6 3 5 0 9 11 0 －7 40 × 10 × Vj 9 12 16 18 所有检验数如下：

?11＝c11?u1?v1＝9－0－9＝0 ， ?12＝c12?u1?v2＝12－0－12＝0 ，

?21＝c21?u2?v1＝7－（－9）－9＝7 ， ?24＝c24?u2?v4＝7－（－9）－18＝－2 ， ?32＝c32?u3?v2＝5－（－7）－12＝0 ，?34＝c34?u3?v4＝11－（－7）－18＝0。

?再用闭回路法求最优解和最优方案的运费，先检验：

费 用 销 地 A 1 A 2 A 3 A 4 Si 产 地 9 1 × × 30 20 －3 12 －7 9 6 50 7 2 －3 3 7 7 －3 60 × 40 20 × 3 6 5 0 9 11 －5 50 47

40 × 10 × 160 Dj 40 40 60 20 160 ∵所有检验数

?ij≤0， ∴该方案已是最优方案，不需要再调整。

30

最优方案的运费Z=9×30+6×20+3×40+7×20+6×40+9×10=980

4、给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）

B1 B2 B3 B4 si A3

2

40

A2

3

40

A1

1

20 A4

20 A3

10 A3

A1 A2 A3 20 11 8 6 5 9 10 2 18 7 4 1 10 5 15 dj 3 3 12 12 1）用最小费用法求初始运输方案，并写出相应的总运费；（4分） 2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分） 解：用“表上作业法”求解。

1）先用最小费用法（最小元素法）求此问题的初始基本可行解：

费 用 销 地 B1 B2 B3 B4 Si 产 地 20 A1 3 2 × × 11 8 6 5 5 A2 9 10 2 10 × × × 10 A3 18 7 4 1 15 48

× 1 12 2 30 30 Dj 3 3 12 12 ∴初始方案： 3 B1 1 10 B2 12 Z=20×3+11×2+2×10+7×1+4×12+1×2=159 1，求检验数： 2）①用闭回路法 A 地 A2 B4 A3 2 B3 B4 Si 费 用 销 2 B1 B2 B2 B3 B4 产 地 20 A1 3 2 × × 11 8 0 6 －1 5 5 A2 12 9 －1 10 －5 2 10 × × × 10 18 A3 －2 7 4 1 15 × 1 12 2 30 30 Dj 3 3 12 12 ∵

?21=12＞0，其余?j≤0

∴选

x21作为入基变量迭代调整。

②用表上闭回路法进行迭代调整：

费 用 销 地 B1 B2 B3 B4 Si 产 地 20 A1 2 3 × × 11 8 12 6 11 5 5 A2 9 －13 10 －15 2 10 1 × × 9 49

18 A3 －14 7 －12 4 1 15 × × 12 3 30 30 Dj 3 3 12 12 再选

x13作为入基变量迭代调整。

地 B1 B2 B3 B4 Si 费 用 销 产 地 20 A1 × 3 2 × －12 11 8 6 －1 5 5 A2 9 －1 10 －5 2 10 3 × × 7 18 A3 －14 7 0 4 1 15 × × 10 5 30 30 Dj 3 3 12 12 调整后，从上表可看出，所有检验数

?j≤0，已得最优解。

3 ∴最优方案为：

最小运费Z=11×3+8×2+5×3+2×7+4×10+1×5=123 B1 A

10

B3

5、某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为A——1500套，B——2000套，C——3000套，D——3500套，有三个城市可供23应上述规格服装，供应数量为Ⅰ——25002套，Ⅱ——2500套，Ⅲ——5000套。由于这些城市的服装质量、运价情况不一，运输成本（元/套）也不一样，详见下表： 3

B A A 10 8 9 A1

7 B 5 2 3 C 6 7 4 BD 4 7 6 8 5 B4

2 B3

Ⅰ Ⅱ Ⅲ 请帮助该公司确定一个成本最小的采购方案。(用伏格尔法)（12分） 解：用伏格尔法确定初始调运方案为：

Ⅰ Ⅱ Ⅲ 销 A 1500 1500 =5；

B 2000 2000 C 3000 3000 D 2500 500 500 3500 供 2500 2500 5000 ?

11

=2；

?12

=-2；

?13

=3；

?21

=1；

?23

?32

=-1 （5分）

50

本文来源：https://www.bwwdw.com/article/m81o.html