第四章 运输问题 4.1 运输问题 4.2 运输问题的表上作业法 4.3 运输问题的进一步讨论.

Presentation on theme: "第四章 运输问题 4.1 运输问题 4.2 运输问题的表上作业法 4.3 运输问题的进一步讨论."— Presentation transcript:

1 第四章 运输问题 4.1 运输问题 4.2 运输问题的表上作业法 4.3 运输问题的进一步讨论

2 第一节 运输问题 及其数学模型 运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶变量与原问题检验数的关系。

3 典型背景——单一物资运输调度问题 设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 。
从产地 到销地 的单位运价是 。 求总运费最小的调度方案。 运输问题

4 决策变量 表示由 到 的物品数量。 销地 产地 销量 产量 运输问题

5 产销平衡问题——总产量=总销量 即 产销不平衡问题——总产量=总销量 运输问题

6 产销平衡问题的数学模型 运输问题

7 运输问题数学模型的特点 运输问题有有限最优解 运输问题约束条件的系数矩阵（下页） 对产销平衡问题
约束条件系数矩阵每一列只有两个1，其余为0； 对产销平衡问题 约束条件均为等式，且产量之和=销量之和； 约束条件的独立方程最多有m+n-1个，即 运输问题

8 m n 运输问题

9 i j 其中 运输问题

10 运输问题的对偶问题 ——对偶变量与原问题检验数的关系
对产销平衡运输问题，若用 分别表示前m个约束等式相应的对偶变量， 用 分别表示后n个约束等式相应的对偶变量，即对偶变量为 运输问题

11 运输问题的对偶问题 ——对偶变量与原问题检验数的关系
运输问题的对偶问题可写为 运输问题

12 运输问题的对偶问题 ——对偶变量与原问题检验数的关系
线性规划问题变量 的检验数为 变量 的检验数为 运输问题

13 运输问题的对偶问题 ——对偶变量与原问题检验数的关系
设运输问题的一个基可行解的变量为 由于基变量的检验数为零，故有 运输问题

14 运输问题的对偶问题 ——对偶变量与原问题检验数的关系
方程组含有m+n-1个方程，m+n个变量 可证明方程组有解，且不唯一。 求出方程组的解（称为位势） 求运输问题检验数的一种方法 则变量 的检验数为 运输问题

15 第二节 运输问题的 表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。

16 表上作业法是单纯形法在求解运输问题的一种简便方法。 单纯形法与表上作业法的关系：
（1）找出初始基可行解 （2）求各非基变量的检验数 （3）判断是否最优解 表上给出m+n-1个数字格 计算表中空格检验数 判断方法相同 运输问题

17 ？ 换基： 停止 （4）确定换入变量和换出变量找出新的基可行解。 （5）重复（2）、（3）直至求出最优解。 最优解 表上调整（闭回路调整）
是 否 停止 换基： （4）确定换入变量和换出变量找出新的基可行解。 （5）重复（2）、（3）直至求出最优解。 表上调整（闭回路调整） （运输问题必有最优解） 运输问题

18 举例说明表上作业法 例1、某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表： 销量 产量 4 12 2 8 5 3 9
销地 产地 4 12 2 8 5 3 9 6 11 10 运输问题

19 第一步：确定初始基可行解 ——最小元素法、伏格尔法
第一步：确定初始基可行解 ——最小元素法、伏格尔法 最小元素法思路： 从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。 运输问题

20 最小元素法举例 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 10 6 6 8 2 2 14 8 8 10 6 运输问题

21 8 2 10 14 6 最小元素法缺点：会出现顾此失彼 最小元素法举例 考虑运价差 （运费差额问题） 4 12 2 8 5 3 9 6 11
销量 产量 销地 产地 8 2 10 14 6 考虑运价差 最小元素法缺点：会出现顾此失彼 （运费差额问题） 运输问题

22 伏格尔法思路： 罚数（即差额）=次小运价-最小运价 对差额最大处，采用最小运费调运。 罚数（或差额）的解释：
差额大，则不按最小运费调运，运费增加大。 差额小，则不按最小运费调运，运费增加不大。 运输问题

23 结合例1说明这种方法。 第一次 4-4=0 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 行罚数 ① 运输问题

24 结合例1说明这种方法。 第一次 3-2=1 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 行罚数 ① 1 运输问题

25 结合例1说明这种方法。 第一次 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 ① 1 行罚数 1 运输问题

26 4-2=2 结合例1说明这种方法。 第一次 销量 产量 行罚数 ① 1 ① 2 5 1 3 列 罚 数 4 12 2 8 5 3 9 6
11 10 销量 产量 销地 产地 行罚数 ① 1 4-2=2 列 罚 数 ① 2 5 1 3 运输问题

27 结合例1说明这种方法。 第一次 销量 产量 行罚数 ① 1 14 8 2 1 5 3 ① 下次不考虑该列 列 罚 数 优先安排销地
12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 行罚数 ① 1 14 8 列 罚 数 2 1 5 3 ① 优先安排销地 ，否则运价会更高 运输问题

28 结合例1说明这种方法。 下次不考虑该行 第二次 销量 产量 14 行罚数 ② 1 2 8 6 2 1 3 ② 列 罚 数 优先安排销地
12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 14 行罚数 ② 1 2 8 6 列 罚 数 2 1 3 ② 优先安排销地 ，否则运价会更高 运输问题

29 结合例1说明这种方法。 下次不考虑该列 第三次 8 销量 产量 14 行罚数 ③ 1 8 2 2 1 ③ 列 罚 数 4 12 2 5 3
9 6 11 10 销量 产量 销地 产地 14 行罚数 ③ 1 8 2 列 罚 数 2 1 ③ 运输问题

30 结合例1说明这种方法。 下次不考虑该列 第四次 8 销量 产量 14 行罚数 ④ 7 6 12 4 1 2 ④ 列 罚 数 4 12 2 5
3 9 6 11 10 销量 产量 销地 产地 14 行罚数 ④ 7 6 12 4 列 罚 数 1 2 ④ 运输问题

31 结合例1说明这种方法。 第五次 8 销量 产量 14 行罚数 ⑤ 4 2 2 ⑤ 列 罚 数 4 12 2 5 3 9 6 10 销地 产地
11 10 销量 产量 销地 产地 14 行罚数 ⑤ 4 2 列 罚 数 2 ⑤ 运输问题

32 一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。
例1用伏格尔法得到的初始基可行解 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 4 8 14 12 2 用最小元素法 求出的目标函数z=246 一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。 目标函数值 运输问题

33 第二步：解的最优性检验 如何求检验数？ 闭回路法 思路：计算空格（非基变量）的检验数 分析： 若令 则 ——运费的增量 即 增加1个单位
即 增加1个单位 的检验数=相应的运费增量 分析： 若令 则 ——运费的增量 运输问题

34 从初始表分析： 8 2 10 14 6 要保证产销平衡，则 称为闭回路 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地
+1 -1 8 2 10 14 6 -1 +1 要保证产销平衡，则 称为闭回路 运输问题

35 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 14 2 1 运输问题

36 14 检验数表 4 12 2 8 5 3 9 6 11 10 销量 产量 1 2 1 -1 10 12 表中的解不是最优解。 销地 产地
运输问题

37 第三步：解的调整 14 调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。 4 12 2 8 5 3 9 6 11 10
销量 产量 销地 产地 14 （-2） （+2） -1 （-2） （+2） 运输问题

38 调整后的解为： 有无穷多最优解 4 12 2 8 5 3 9 6 11 10 销量 产量 销地 产地 8 2 12 14 4 2 9 1 12 此时的解为最优解。 运输问题

39 几点说明： 当检验数为的负的变量超过两个，选择最小者对应的变量换入； 在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；
迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。 运输问题

40 根据第一节运输问题对偶问题与原问题的检验数的关系
还有其它的方法吗 ？ 讨论内容： 初始调运方案（初始基可行解） ——西北角法 解的最优性检验——对偶变量法（或称位势法） 根据第一节运输问题对偶问题与原问题的检验数的关系 运输问题

41 第三节 运输问题的 进一步讨论 上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论： 一、产销不平衡的运输问题
第三节 运输问题的 进一步讨论 上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论： 二、有转运的运输问题 一、产销不平衡的运输问题 并附有运输问题的思考题及练习题

42 一、产销不平衡的运输问题 （Ⅰ）若总产量大于总销量，即 令假象销地的销量为： 运输问题

43 注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。 决策变量 表示由 到 的物品数量。
决策变量 表示由 到 的物品数量。 销地 产地 销量 产量 运输问题

44 原产大于销平衡问题的数学模型 运输问题

45 修改后产大于销平衡问题的数学模型 运输问题

46 一、产销不平衡的运输问题 （Ⅱ）若总产量小于总销量，即 令假象产地的销量为： 仿照上述类似处理。 运输问题

47 举例说明 某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表： 4 12 2 8 5 3 9 6 11 10 销量 产量
销地 产地 运输问题

48 二、有转运的运输问题 中间转运站——产地、销地、中转站。 建模思路：从发送及接受角度考虑。 产地 转运 销地 发送量 产地 转运 销地
产地 转运 销地 发送量 产地 转运 销地 接受量 运输问题

49 应用问题举例 例1、水泥调运的产销不平衡情况及运价如下表，求最好的调运方案。 2 11 10 7 8 3 5 9 1 4 销量 产量 销地
产地 运输问题

50 最优方案为： 销地 产量 产地 2 11 3 4 10 3 5 9 7 8 1 2 销量 运输问题

51 例2、某农场有土地900亩，分为三类，计划种植三种作物，情况如下表，求使作物总产量最多的布局方案。
500 销量 产量 销地 产地 700 850 480 600 300 400 运输问题

52 解：目标函数最大，可用最大元素法，即是按产量高的优先安排的原则。
500 销量 产量 销地 产地 700 850 480 600 300 400 50 100 300 400 运输问题

53 调整： 500 销量 产量 销地 产地 700 850 480 600 300 400 100 200 可验证此时为最优解。 运输问题

54 运输问题 讨论

55 一、概念题（判断） 1、运输问题是一种LP问题，其求解结果有四种情况。 2、在运输问题中，只要给出一组含（m+n-1）个非零的 ，且满足 就可以作为一个初始基可行解。 运输问题

56 3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。 4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。 5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。 6、如果…...分别乘上一个常k,…...不会发生变化。 运输问题

57 二、运输问题的对偶问题 某一实际的运输问题可以叙述如下： 有n个地区需要某种物资，需要量分别为 ，这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别为 ，已知从 i地区工厂至第j个需要地区单位物资的运价为 ，又 试阐述其对偶问题，并解释对偶变量的经济意义。 运输问题

58 三、运输问题的灵敏度分析 已知某运输问题的供需关系及单价表如下表， 销量 产量 2 4 5 3 1 要求（1）用表上作业法找出最优调运方案。
销地 产地 2 4 5 3 1 要求（1）用表上作业法找出最优调运方案。 （2）分别讨论 使最优方案不变 的变化范围 运输问题

59 四、求解线性规划问题 可转化为运输问题来求解 运输问题

60 练习： 下表给出一个运输问题及它的一个解， 销地 产量 产地 4 1 3 7 6 5 2 5 3 8 2 3 1 销量 运输问题

61 （2）若 由1变为3，所给的解是否仍为最优解？若不是，求出新的最优解。 （3）若所有价值系数均增加1，最优解是否改变？为什么？
试问： （1）表中给出的解是否为最优解？ （2）若 由1变为3，所给的解是否仍为最优解？若不是，求出新的最优解。 （3）若所有价值系数均增加1，最优解是否改变？为什么？ （4）若所有价值系数均增加1，最优解是否改变？为什么？ （5）写出该问题的对偶问题，并给出其对偶问题的最优解。 运输问题