统筹安排 　　成本最低.

Presentation on theme: "统筹安排 　　成本最低."— Presentation transcript:

1 统筹安排 　　成本最低

2 第七章 运输问题 §1 运 输 模 型 §2 运输问题的计算机求解 §3 运输问题的应用 §4 运输问题的表上作业法

3 §1 运输模型 例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？

4 解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：

5 Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23

6 产地A1运出的运输量等于其产量： x11+ x12 + x13 = 200
运到销地B1的运输量等于其需求量： x11 + x21 = 150 运到销地B2的运输量等于其需求量： x12 + x22 = 150 运到销地B3的运输量等于其需求量： x13 + x23 = 200 运输量非负： xij≥ 0 (i=1,2；j=1,2,3)

7 §1 运输模型 整理得： Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
§1 运输模型 整理得： Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 1、2；j = 1、2、3）

8 §1 运 输 模 型 一般运输模型：产销平衡 A1、 A2、…、 Am 表示某物资的m个产地； B1、B2、…、Bn 表示某物资的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。 设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：

9 §1 运 输 模 型 运价 运输问题及其数学模型 销地 B1 B2 … Bn am a2 a1 产量 A1 A2 Am 产销平衡 bn …
§1 运 输 模 型 运输问题及其数学模型 销地 产地 B1 B2 … Bn am a2 a1 产量 A1 运价 A2 Am 产销平衡 bn … b2 b1 销量

10 §1 运 输 模 型 运输问题及其数学模型 求使总的运输费用最小的调运方案？ cmn cm2 cm1 c2n c22 c21 c1n c12
§1 运 输 模 型 产 销 平 衡 表 运输问题及其数学模型 销地 产地 cmn cm2 cm1 c2n c22 c21 c1n c12 c11 … B1 B2 Bn am a2 a1 产量 A1 A2 Am bn … b2 b1 销量 求使总的运输费用最小的调运方案？

11 §1 运 输 模 型 运输问题线性规划模型 总费用最小 产地Ai发量之和等于其产量 销地Bj收量之和等于其销量 运量不能为负数

12 §1 运 输 模 型 运输问题网络图 例： 需求地 供应地 运价 d1=22 需求量 6 1 s1=14 1 7 供应量 5 3 d2=13
§1 运 输 模 型 运输问题网络图 例： 需求地 供应地 运价 d1=22 需求量 6 1 s1=14 1 7 供应量 5 3 d2=13 2 8 4 2 2 s2=27 7 5 3 d3=12 9 10 3 6 s3=19 4 d4=13

13 §1 运 输 模 型 运输问题线性规划模型 供应地约束 需求地约束

14 §2 运输问题的计算机求解 将上述问题用以下运价表： 　　销地 产地 1 2 3 4 产量 6 7 5 14 8 27 9 10 19 销量 22 13 12

15 §2 运输问题的计算机求解 运行管理运筹学计算机软件： 点击运输问题模块

16 §2 运输问题的计算机求解 点击新建 选择Min 输入3 输入4 点击确定

17 §2 运输问题的计算机求解 销地 产地 1 2 3 4 产量 6 7 5 14 8 27 9 10 19 销量 22 13 12

18 §2 运输问题的计算机求解 点击解决

19 §2 运输问题的计算机求解

20 思考题： 运输问题的特点是什么？ 既然运输问题是线性规划的一种特殊情况，为什么不用线性规划的方法求解？ 要求： 　　对以上例子分别应用计算机软件的线性规划模块和运输问题的模块进行计算、分析后回答。　

21

22 分析 用线性规划程序求解运输问题的优缺点： 优点：线性规划程序块输出信息多，可以进行灵敏度分析
缺点：输入较为麻烦（决策变量太多），求解线性规划问题的程序较为复杂，能够解决的运输问题的规模不大 因此，专门有求解运输问题的程序。 只需输入：产地数，产量，销点数，销量，运输单价，即可。

23 运输模型的说明 （1）实际建模时，只需给出产销平衡的运费表即可； （2）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）；
（3）有时目标函数求最大：如求利润最大或营业额最大等； （4）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束）。

24 §2 运输问题的计算机求解 例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？

25 x14 x24 解：增加一个虚设的销地,运输费用为0. B4看作是产地A1,A2的仓库，因此A1,A2到B4的运费为0 供 大 于 求
x24 B4看作是产地A1,A2的仓库，因此A1,A2到B4的运费为0 产量有剩余，所以运输量X14，X24至少有一个不为0，

26 没有虚设B4销地 产地A1放在自己仓库里的物品数量 产地A2放在自己仓库里的物品数量

27 §2 运输问题的计算机求解 例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 供 小于 求

28 解：增加一个虚设的产地运输费用为0 运输量X31，X32，X33表示B1，B2，B3销量中欠缺的数量

29 分别为B1，B2，B3欠缺的物品数量

30 思考题1 在例3中，即某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，如果增加条件：B3的需求不能满足则需以高价（每单位10元）在本地购买，问：应如何调运可使总运输费用最小？ 供小于求 B1 B2 B3 产量 A1 6 4 200 A2 5 300 销量 250 500 650 新加一个假想产地

31 思考题1 在例3中，即某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，如果增加条件：B3的需求不能满足则需以高价（每单位10元）在本地购买，问：应如何调运可使总运输费用最小？ 明确表明是B3地的需求不满足，前两个销地的需求是可以满足的 B1 B2 B3 产量 A1 6 4 200 A2 5 300 A3 销量 250 500 650 M很大，意图是使 x31=0 x32=0 M M 10 150 650

32 §2 运输问题的计算机求解

33 §2 运输问题的计算机求解 √ B3缺少150的物品从当地购买 如果两个M处改为运价为0 解不合理

34 §3 运输问题的应用 思考题2 考虑一运输问题，有关产品的单位运价（元/千克）如下表所示，假设A1、A2处产品要求全部运走, A3处产品就地储存的费用为每千克16元，试写出该问题的产销平衡表。 销地 产地 B B2 供应量（千克） A1 A2 A3 40 30 65 需求量（千克） 新 加 一 个 销 地

35 §3 运输问题的应用 思考题2 该问题的产销平衡表为： 销地产地 B1 B2 B3 供应量（千克） A1 A2 A3 35 23 M
§3 运输问题的应用 明确表明是A3地的产量剩余，所以有剩余物品屯在A3处 思考题2 假想的销地B3(A3处的仓库) 该问题的产销平衡表为： 销地产地 B B B3 供应量（千克） A1 A2 A3 M M 40 30 65 需求量（千克）

36 M 在产地处屯着 解不合理

37 §3 运输问题的应用 一、产销不平衡的运输问题
§3 运输问题的应用 有1500吨必须满足，500吨是可以不满足的 一、产销不平衡的运输问题 例4、石家庄北方研究院有一、二、三共三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为： 由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨, 试求总费用为最低的调运方案。 最多有300吨是可以不满足的

38 假想点运出的数量是正数，说明实际中这部分数量是不能满足的
该处对应的运输量可以为正数 解： 根据题意，作出产销平衡与运价表： 这里 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。 假想点运出的数量是正数，说明实际中这部分数量是不能满足的 必须满足的 可以不满足的 必须满足的 必须满足的 可以不满足的 该处对应的运输量为0

39 §3 运输问题的应用 应用运筹学软件计算得：

40 §3 运输问题的应用 一、产销不平衡的运输问题
§3 运输问题的应用 一、产销不平衡的运输问题 例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设使用效果相同，有关数据如下表： 试求总费用为最低的化肥调拨方案。 C厂不供应第4个地区 60 最高需求量只能比最低需求量多50 总的最高需求变为210

41 分析： 1）产销不平衡，差多少？总产量160，总销量计算是关键 最低需求与最高需求该怎么处理？最低需求必须满足，和最高需求的差值可以从假想生产点供货，因此，将每个区的需求分为2部分处理（和例4相似）； 2）运费设置 最低需求必须满足，但这部分货物不可能是假想供应点供应的，所以将从假想供应点到相应区的运费设为M（无穷大），强迫使得运输数量为0； 最高需求和最低需求的差额的部分，可以不满足，从假想点运输的数量可以为正，但事实从假想点没有货物运出，所以运费设置为0。

42 1. 最低要求必须满足，因此把相应的虚设产地运费取为M。 2. 最高要求与最低要求的差，可以不满足，因此把相应的虚设产地运费取为 0 。
解： 根据题意，作出产销平衡与运价表： 1. 最低要求必须满足，因此把相应的虚设产地运费取为M。 2. 最高要求与最低要求的差，可以不满足，因此把相应的虚设产地运费取为 0 。 3. 根据产销平衡要求确定D的产量为 50 。 1’ 1” 2 3 4’ 4” 产量 A 16 13 22 17 50 B 14 19 15 60 C 20 23 M D 销量 30 70 10 210

43

44 §3 运输问题的应用 季度 生产能力(台) 单位成本(万元) 1 25 10.8 2 35 11.1 3 30 11.0 4 10 11.3
§3 运输问题的应用 二、生产与储存问题 例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。 季度 生产能力(台) 单位成本(万元) 1 25 10.8 2 35 11.1 3 30 11.0 4 10 11.3

45 解1. 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；
2. 把第j季度交货的柴油机数目看作第j个销售点的销量； 3. 成本加储存、维护等费用看作运费。 可构造下列产销平衡表: 季度 1 2 3 4 D 产量 25 35 30 10 销量 15 20 100 70 10.80 10.95 11.10 11.25 M 11.10 11.25 11.40 M M 11.00 11.15 M M M 11.30 100

46 设 xij为第i季度生产的第j季度交货的柴油机数目，则 交货: x11 =10 x12+x22 =15 x13+x23+x33 =25
生产: x11+x12+x13+x14≤25 x22+x23+x24≤35 x33+x34≤30 x44≤10 目标函数: Minf=10.8x x x x14+ +11.1x x x x x x44 季度 1 2 3 4 D 产量 10.80 10.95 11.10 11.25 25 M 11.40 35 11.00 11.15 30 11.30 10 销量 15 20 100

47

48 例7.光明仪器厂生产电脑绣花机是以销定产的。已知 1 至 6 月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用如表 7-13 所示。 已知上年末库存 103 台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本 0.1 万元,每台机器每月的平均仓储费、维护费为 0.2 万元。在 7-8 月份销售淡季，全厂停产 1 个月，因此在 6 月份完成销售合同后还要留出库存 80 台。加班生产机器每台增加成本 1 万元。问应如何安排 1-6 月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？

49

50 分析： 1）产地分为正常生产和加班生产2种，上年末库存看做0号产地，所以共有产地13个。 2）销地为每月需求，所以共有销地6个。 3）总产量： =743 总销量： =707 产销不平衡，增加假想销地（空头支票），销量36 4）运费计算 正常生产：本月生产，本月需要，应为生产成本，以后第一个月，加运输和储存、维护费用，共0.3，再往后的月份每月只增加0.2的储存、维护费用； 加班生产：生产成本加1

51 P137 70+80库存

52 可以不安排生产

53 §3 运输问题的应用 三、转运问题： 在原运输问题上增加若干转运站。运输方式有: 产地 转运站、转运站 销地、产地 产地、产地 销地、销地 转运站、销地 产地等。 每一个发点供应量一定，每一个收点需求量一定，每两个点之间的运输单价已知，怎样使得运输费用最小。

54 例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？

55 应该如何调运仪器，可使总运输费用最低？ 图中1-广州、2-大连、3-上海、4-天津、5-南京、6-济南、7-南昌、8-青岛。

56 线性规划模型求解 设Xij表示从i到j的调运量，如x24代表从大连运到天津的仪器台数，则目标函数为：
f=2X13+3X14+3X23+X24+2X35+6X36+4X45+3X37+6X38+4X46+6X47+5X48+4X28 约束条件： X13+X14 ≤600, X23+X24+X28 ≤400 X23+X13=X35+X36+X37+X38 X14+X24=X45+X46+X47+X48 X35+X45=200，X36+X46=150， X37+X47=350，X38+X48=300， Xij≥0 供应量 中转站 需求量

57 X13=550,X14=50,X23=0,X24=100 X35=200,X36=0,X37=350,X38=0 X45=0,X46=150,X47=0,X48=0 X28=300 最小运输费用为4600百元。

58 需求量 供应量 广州 上海 南京 济南 南昌 天津 大连 青岛 600 2 3 M M M M 400 3 1 M M M 4 1000
中转地：上海、天津的产量和销量相等 运价表 上海 天津 南京 济南 南昌 青岛 产量 广州 M M M M M M M M M 600 400 1000 大连 上海 天津 销量

59

60 分析结果 上海 天津 南京 济南 南昌 青岛 广州 大连 上海 天津
在1000的产量都运往上海或天津的情况时，上海或天津可能有剩余,即实际转运量没达到1000，所以运费系数不能为M，只能为0 分析结果 上海 天津 南京 济南 南昌 青岛 广州 大连 上海 天津

61 §3 运输问题的应用 例9、某公司有A1、 A2、 A3三个分厂生产某种物资，分别供应B1、 B2、 B3、 B4四个地区的销售公司销售。假设质量相同，有关数据如下表，试求总费用为最少的调运方案。

62 §3 运输问题的应用 假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；
§3 运输问题的应用 假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运； 2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。

63 A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 1 3 2 4 11 10 --- 5 9 8 7 6 中转站 销地 产地
A1—B2， A1—A3—B2， A1—T2—B2， A1—A2—B1—B2， 中转站 产地 销地 A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 1 3 2 4 11 10 --- 5 9 8 7 6

64 解：把此转运问题转化为一般运输问题： 1. 把所有产地、销地、转运站都同时看作产地，也同时看作销地，如此共有11个产地，11个销地； 2. 运输表中不可能方案的运费取作M,自身对自身的运费为0； 3. 中转站产量等于销量（流入等于流出），不可能来回倒运，每个中转站的转运量不超过20t；

65 4. 扩大了运输问题中，原来的产地和销地均可作为中转站做转运（中转站既有产量又有销量），所以将原来产地的产量和销量，原来销地的产量和销量均加20，即：
原来的产地Ai : 产量：原产量+20；销量：原销量（0）+20; 原来的销地Bi : 产量:原产量（0）+20, 销量：原销量+20； 中转站Ti : 产量、销量均为20； 5. 对于最优方案,其中xii为自身对自身的运量（实际上是剩余在自己站点的量）, 20- xii是每个中转站的实际运量，即每个中转站不一定每次都转运了20。因此，运价表中对应的系数不能为M应为0。 其中20为各点可能变化的最大流量

66 扩大的运输问题产销平衡与运价表： A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 1 3 2 4 11 10 27
1 3 2 4 11 10 27 M 5 9 8 24 7 29 6 20 销量 23 26 25 240

67 §7.4 运输问题的表上作业法 运输问题较为复杂，包含产地和销地较多时，求解该类问题的特殊方法——表上作业法（实质仍为单纯形法，使用前提：产销平衡）。 1）找出初始基本可行解 (西北角法、最小元素法) （m个产地，n个销地，m+n个约束方程，产销平衡—前m个约束方程的和等于后n个约束方程的和，如：）

68 X X X X21 X X23

69 很有规律 最多有m+n-1个独立的约束方程，即最多m+n-1个解，证明（证明过程略过）后发现正好有m+n-1个独立方程，即正好m+n-1个解。 因此，产销平衡的运输问题有m+n-1个基变量。

70 §7.4 运输问题的表上作业法 2）求各非基变量的检验数，如果已是最优，停止计算，否则转到下一步
§7.4 运输问题的表上作业法 2）求各非基变量的检验数，如果已是最优，停止计算，否则转到下一步 3）确定入基变量和出基变量，找出新的基本可行解 4）重复2）、3），直到得到最优解。

71 例10. 喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如下表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？

72

73 一.确定基本初始可行解 西北角法 先从表的西北角的变量开始分配运量 x11 x12 x13 x14 3 11 3 10 7 4 3 4 基变量有m+n-1=6个，即：x11=3, x12=4, x22=2, x23=2, x33=3, x34=6 总运费为135 Min(3,7) Min(4,6) x21 1 x22 9 x23 2 x24 8 4 2 Min(4,2) 2 Min(2,5) 2 x31 7 x32 4 x33 10 x34 5 9 6 Min(9,3) 3 Min(6,6) 6 3 6 5 6 3 2

74 一.确定基本初始可行解 最小元素法 取单位运价最小的变量开始分配运量 x11 3 x12 11 x13 3 x14 10 7 3 Min(7,4) 4 3 Min(3,3) 基变量有m+n-1=6个，即：x13=4, x14=3, x21=3, x23=1, x32=6, x34=3 总运费为86 x21 1 x22 9 x23 2 x24 8 4 1 Min(4,3) 3 1 Min(1,5) x31 7 x32 4 x33 10 x34 5 9 3 Min(9,6) 6 3 Min(3,6) 3 6 5 6 4 3

75 注意事项 （1）当我们取定 xij 的值之后，会出现 Ai 的产量与 Bj 的销量都改为零的情况，这时只能划去 Ai 行或 Bj 列，但不能同时划去 Ai 行与 Bj 列。 （2）用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外填上一个零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1 个，即保证基变量的个数为 m+n-1 个。

76 二. 最优解的判别 闭回路法、位势法 闭回路：是在已给出调运方案的运输表上，从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转 90°（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。

77 二. 最优解的判别 闭回路法，就是对于代表非基变量的空格（其调运量为零），把它的运输量调整为 1，由于产销平衡的要求, 必须对这个空格的闭回路的顶点的调运量加上或减少 1。最后计算出由这些变化给整个运输方案的总运费带来的变化。 由于目标要求极小，因此当所有的检验数都大于或等于零时，该调运方案就是最优方案。

78 3 -3 -1 +2 =1 产销点很多时，该法很繁琐 运费的变化： ① 4 3 1 3 3 7 1 2 4
说明如果X11是基变量，增加1t的运量，总运费要增加1百元。 9 3 6 5 6 让该变量为非基变量(即为0)是正确的。 产销点很多时，该法很繁琐

79 二. 最优解的判别 位势法（理论依据略，只需了解计算过程）
二. 最优解的判别 位势法（理论依据略，只需了解计算过程） 即：对运输表上的每一行赋予一个数值 ui，对每一列赋予一个数值vj，它们的数值是由基变量 xij 的检验数 λij = cij− ui −v j = 0决定的。 ui 和vj的值确定后，则非基变量 xij的检验数即可用公式 λij = cij − ui − v j 求出。 如果所有代表非基变量的空格的检验数，也即非基变量的检验数都大于等于零，则已求得最优解。

80 u1=0 λij=cij−ui−vj 4 3 3 1 6 3 基变量x13 的检验数 1) λ13=c13−u1−v3
=0,则v3=c13−u1 =c13=3. 2) λ14=c14−u1−v4 =0,则v4=c14−u1 =c14=10. 3) λ23=c23−u2−v3 =0,则u2 =c23− v3 =2-3=-1. 3 11 3 10 u1=0 4 3 1 9 2 8 3 1 7 4 10 5 6 3 4) λ34=c34−u3−v4=0,则u3=c34−v4=5-10=-5. 5) λ21=c21−u2−v1=0,则v1=c21−u2=1-(-1)=2. 6) λ32=c32−u3−v2=0,则v2=c32−u3=4-(-5)=9. 依照求出的u1,u2,u3和v1,v2,v3,v4分别求出非基变量的检验数。与闭回路法求得的检验数一致。

81 改进运输方案的办法——利用闭回路进行调整的方法
当某个非基变量的检验数为负值时，表明未得最优解，需要调整。 方法：在所有负的检验数中，选择最小的检验数对应的非基变量，将其入基。 λ24=-1，则非基变量X24入基，以X24所在格为出发点找一个闭回路。

82 1）λ24=−1，表明增加一个单位的 x24 运输量，可使得总运费减少 1。在以 x24 为出发点的闭回路中，找出所有偶数序号的顶点的调运量：x14 = 3，x23 = 1，令x24 = min（3, 1）=1。2）把所有闭回路上序号为偶数的顶点运输量都减少这个值，序号为奇数的顶点的运输量都增加这个值。（产量、销量平衡） 5 2 3 11 3 10 3 4 1 9 2 8 3 1 1 7 4 10 5 6 3

83 该解用位势法进行检验，即计算非基变量的检验数，均为大于等于0，因此为最优解。
总运费为85百元。 5 2 3 1 6 3

84 如何找多个最优方案 识别是否有多个最优解的方法和单纯形表 法一样，只需看最优方案中是否存在非基 变量的检验数为零。
如在本题中给出的最优运输方案中： x11 的检验数为 0，可知此运输问题有多 个最优解。 怎样求得另外的最优解？ 只要把 x11 作为入基变量，调整运输方案 ， 就可得到另一个最优方案。

85 2 5 2 1 3 1 3 6 3

86 3 11 3 10 2 5 1 9 2 8 1 3 总运费依然为最优值85百元。 7 4 10 5 6 3

87 本章作业 建模： 1、3、4 求解： 6

88 第1题 销地 产地 甲 乙 丙 丁 500 400 300 产量 1分厂 21 17 23 25 2分厂 10 15 30 19 3分厂 23 21 20 22 200 350 250 400 销量 1200 产销平衡

89 第1题 销地 产地 甲 乙 丙 丁 戊 500 600 300 产量 1分厂 21 17 23 25 2分厂 10 15 30 19 3分厂 23 21 20 22 200 350 250 400 销量 200 1400 增加一个销地戊，看作是各分厂的仓库。 运费最小为19050元。 此时分厂1剩余50箱，分厂3剩余150箱。 89

90 销地 产地 甲 乙 丙 丁 500 400 300 产量 1分厂 21 17 23 25 2分厂 10 15 30 19 3分厂 23 21 20 22 4分厂 150 200 350 250 550 销量 增加一个产地4分厂，运到各个销地的运费均为0。 运费最小为19600元。 此时销地1有100箱欠缺，销地4有50箱欠缺。

91 第3题 销售月 生产月 1 2 3 假想销地 产量 60 120 180 600 660 720 1’ 780 M 700 760 4 2’ 770 830 650 3’ 715 销量 5 6 19 每年正常生产和加班生产分别讨论

92 不安排生产的剩余生产能力

93 第4题 转运问题 甲运给A300，B200 乙运给C600，C又运给D100 甲 乙 A B C D 产量 100 150 200 180
原来的产地和销地均同时看作产地和销地 甲 乙 A B C D 产量 100 150 200 180 240 1600 80 210 60 170 1700 M 110 1100 70 140 50 130 90 85 销量 1400 1300 1200 500 600 甲运给A300，B200 乙运给C600，C又运给D100 300 200 500 100

94 最小元素法 第6题 8 7 4 3 5 9 1 2 3 产量 15 25 10 20 甲 乙 丙（假想产地） 销量 15
销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 10 销量 20 8 7 4 15 Min(15,20) 3 5 9 10 10 5 15 5 Min(10,25) Min(15,10) Min(5,5) 10 Min(10,20) 10 5

95 不是最优解，选择x33入基 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x23—x21—x11 8-4+9-3=10 x12
15 10 10 5 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x23—x21—x11 =10 x12 x12—x13—x23—x22—x12 =7 x32 x32—x22—x21—x31—x32 = -2 x33 x33—x23—x21—x31—x33 = -6 10 不是最优解，选择x33入基

96 第6题 8 7 4 3 5 9 1 2 3 产量 15 25 10 20 甲 乙 丙（假想产地） 销量 15 (+5) (-5) 10 10
销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 10 销量 20 8 7 4 15 (+5) (-5) 3 5 9 10 10 5 (-5) 10 (+5) 96

97 第6题 销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 10 销量 20 8 7 4 15 3 5 9 15 10 5 5 97

98 不是最优解，选择x32入基 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x31—x11 8-4+0-0=6 x12
15 10 15 5 5 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x31—x11 =6 x12 x12—x13—x33—x31—x21—x22—x12 =1 x23 x23—x33—x31—x21—x23 = 6 x32 x32—x31—x21—x22—x32 = -2 不是最优解，选择x32入基

99 第6题 8 7 4 3 5 9 1 2 3 产量 15 25 10 20 甲 乙 丙（假想产地） 销量 15 (+5) (-5) 15 10
销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 10 销量 20 8 7 4 15 (+5) (-5) 3 5 9 15 10 (-5) 5 5 (+5) 99

100 第6题 销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 10 销量 20 8 7 4 15 3 5 9 20 5 5 5 100

101 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x32— x22—x21—x11 8-4+0-0+5-3=6 x12
15 5 20 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x32— x22—x21—x11 =6 x12 x12—x13—x33—x32—x12 =3 x23 x23—x33—x32—x22—x23 = 4 x31 x31—x21—x22—x32—x31 = 2 5 5 为最优解，运输费用为：15*4+20*3+5*5=145 非基变量的检验数均大于0，只有唯一最优解

102 最小元素法 第6题（4） 8 7 4 3 5 9 1 2 3 产量 15 25 20 30 10 甲 乙 丙（假想产地） 销量 15
销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 20 销量 30 10 8 7 4 15 Min(15,20) 3 5 9 10 10 5 5 15 Min(10,25) Min(15,10) Min(5,5) 20 Min(20,30) 10 5

103 6.（4） 销地 运输单价 产地 1 2 3 产量 甲 15 乙 10 5 25 丙（假想产地） 20 销量 30 8 7 4 3 5 9

104 检验数 不是最优解，选择x33入基 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x23—x21—x11 8-4+9-3=10
=7 x32 x32—x22—x21—x31—x32 = -2 x33 x33—x23—x21—x31—x33 = -6 不是最优解，选择x33入基

105 第6题 8 7 4 3 5 9 1 2 3 产量 15 25 20 30 10 甲 乙 丙（假想产地） 销量 15 (+5) (-5) 10
销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 20 销量 30 10 8 7 4 15 (+5) (-5) 3 5 9 10 10 5 (-5) 20 (+5) 105

106 第6题 销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 10 销量 20 8 7 4 15 3 5 9 15 10 15 5 106

107 不是最优解，选择x32入基 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x31—x11 8-4+0-0=6 x12
15 10 15 15 5 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x31—x11 =6 x12 x12—x13—x33—x31—x21—x22—x12 =1 x23 x23—x33—x31—x21—x23 = 6 x32 x32—x31—x21—x22—x32 = -2 不是最优解，选择x32入基

108 第6题 8 7 4 3 5 9 1 2 3 产量 15 25 10 20 甲 乙 丙（假想产地） 销量 15 (+10) (-10) 15
销地 运输单价 产地 1 2 3 产量 甲 15 乙 25 丙（假想产地） 10 销量 20 8 7 4 15 (+10) (-10) 3 5 9 15 10 (-10) 15 5 (+10) 108

109 第6题 8 7 4 3 5 9 1 2 3 产量 15 25 10 20 甲 15 乙 25 丙（假想产地） 5 5 销量 销地 运输单价
5 5 109

110 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x31—x11 8-4+0-0=6 x12
15 25 空格 (非基变量) 闭回路 检验数 x11 x11—x13—x33—x31—x11 =6 x12 x12—x13—x33—x32—x12 =3 x22 x22—x32—x31—x21—x22 = 2 x23 x23—x33—x31—x21—x23 = 6 5 10 5 为最优解，运输费用为：15*4+25*3=135