第六讲运输问题.ppt

湖州师范学院 解：先作出这问题的产销平衡表和单位运价表，见下表： 第六讲 运输规划 二、运输模型的求解 运输问题的无穷多最优解和退化解 1. 无穷多最优解 由前可知，产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多最优解?如何判断？ 即某个非基变量(空格)的检验数为0时，该问题有无穷多最优解。上表中空格(1，1)的检验数是0，表明例1有无穷多最优解。结果如下表。 第六讲 运输规划 6 5 6 3 销量 9 4 7 产量 3 1 2 B4 5 B3 6 B2 3 B1 A3 A2 A1 销地 加工厂 二、运输模型的求解 运输问题的无穷多最优解和退化解 6 5 6 3 销量 9 4 7 产量 3 3 B4 5 B3 6 B2 1 2 B1 A3 A2 A1 销地 加工厂 5 8 10 B4 10 2 3 B3 4 9 11 B2 7 1 3 B1 A3 A2 A1 销地 加工厂 第六讲 运输规划 2. 退化 二、运输模型的求解 运输问题的无穷多最优解和退化解 用表上作业法求解运输问题当出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。有以下两种情况： (1) 当确定初始解的各供需关系时，若在(i,j)格填入某数字后，出现Ai处的余量等于Bj处的需量。这时在产销平衡表上填一个数，而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格。这时需要添一个“0”。它的位置可在对应同时划去的那行或那列的任一空格处。 第六讲 运输规划 二、运输模型的求解 运输问题的无穷多最优解和退化解 15 20 40 60 销量 75 25 35 产量 10 13 16 B4 15 7 8 B3 9 14 15 B2 11 5 7 B1 A3 A2 A1 销地 加工厂 15 20 40 60 销量 75 25 35 产量 B4 B3 B2 B1 A3 A2 A1 销地 加工厂 例题 25 35 0 40 15 20 第六讲 运输规划 2. 退化 二、运输模型的求解 运输问题的无穷多最优解和退化解 (2) 在用闭回路法调整时，在闭回路上出现两个和两个以上的具有(-)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时另一个数字格必须填入一个0，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记为(-1)的取值为0的数字格，这时应取调整量θ=0。 第六讲 运输规划 三、运输模型的扩展 最大化运输模型 1. 将极大化问题转化为极小化问题 对于极大化运输问题，可以用一个较大的数M减去运输表中的各个单位运价，得到新的单位运价： 变换后的目标函数为： 第六讲 运输规划 三、运输模型的扩展 1. 将极大化问题转化为极小化问题——例题 某公司去外地采购A、B、C、D四种规格的商品，数量分别为A250t、B300t、C400t、D450t，有三个城市可供应上述规格商品，供应量分别为：Ⅰ350t、Ⅱ350t、Ⅲ700t。由于这些城市的商品质量、运价不完全相同，预计售出后的利润也不同，如下表。确定一个预期盈利最大的采购方案。 450 400 300 250 销量 700 350 350 产量 8 6 7 D 4 7 6 C 3 2 5 B 9 8 10 A Ⅲ Ⅱ Ⅰ 销地 加工厂 第六讲 运输规划 1. 将极大化问题转化为极小化问题——例题 450 400 300 250 销量 700 350 350 产量 8 6 7 D 4 7 6 C 3 2 5 B 9 8 10 A Ⅲ Ⅱ Ⅰ 销地 加工厂 450 400 300 250 销量 700 350 350 产量 2 4 3 D 6 3 4 C 7 8 5 B 1 2 0 A Ⅲ Ⅱ Ⅰ 销地 加工厂 450 400 300 250 销量 700 350 350 产量 D C B A Ⅲ Ⅱ Ⅰ 销地 加工厂 250 450 350 50 50 250 第六讲 运输规划 1. 将极大化问题转化为极小化问题——例题 Vj Ui 450 D 350 50 C 250 50 B 250 A Ⅲ Ⅱ Ⅰ 销地 加工厂 0 5 4 3 2 8 3 4 1 7 6 2 0 0 5 4 -1 2 0