03运输问题

1. 运输问题概述

设表示由到的物品数量，数学模型为

• 约束条件系数矩阵每一列只有两个 1，其余为 0
• 约束条件均为等式，且产量之和=销量之和
• 约束条件的独立方程最多有个，即

2. 表上作业法

3. 解的最优性检验

3.1 闭回路法

3.2 对偶检验法

运输问题的对偶问题为

4. 解的改进

1. 以为换入变量，找出其在运输表中的闭回路
2. 以空格为第一个奇数顶点，沿闭回路的顺（逆）时针方向前进，对闭回路上的顶点依次编号
3. 在闭回路上的所有偶数顶点集合中，找到运输量最小的的顶点，以该格中的变量为换出变量
4. 以换出变量的运输量为调整量，将该闭回路上所有奇数顶点处的运输量都增加该数值，所有偶数顶点处的运输量减少该数值
5. 检验是否为最优解，如果不是则重复该操作

5. 特殊运输问题

5.1 产销不平衡

若

构造

5.2 有转运的运输问题

发送地点和接收地点都有个，不能直达的用表示。