03运输问题

Lingfeng 2025-03-26

03运输问题

1. 运输问题概述

设 $x_{ij}$ 表示由 $A_{i}$ 到 $B_{j}$ 的物品数量，数学模型为 $\begin{align*} \min z & =\sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij}x_{ij} \\ & \mathrm{s.t.}\begin{cases} \sum_{j = 1}^{m} x_{ij}=a_{i}, & i=1,2,\dots,m \\ \sum_{i = 1}^{m} x_{ij}=b_{j}, & j=1,2,\dots,n \\ x_{ij}\geq 0,i=1,2,\dots,m ,j=1,2,\dots,m \end{cases} \end{align*}$

约束条件系数矩阵每一列只有两个 1，其余为 0
约束条件均为等式，且产量之和=销量之和
约束条件的独立方程最多有 $m+n-1$ 个，即 $r(A)\leq m+n-1$

2. 表上作业法

Definition (表上作业法)

表上给出 $m+n-1$ 个数字格
计算表中空格检验数
判断是否最优解
表上调整（闭回路调整）
重复 2、3 直至最优解

Theorem (闭回路性质)

运输问题一组基变量构成闭回路的充要条件是这组变量对应的系数向量线性相关。
运输问题一个解是基本可行解的充要条件是：

元素个数为 $m+n-1$ 个
这 $m+n+1$ 个数字格不构成闭回路

Definition (最小元素法)

从单价中最小运价确定供应量，逐步次小，直至得到 $m+n-1$ 个数字格。

Definition (伏格尔法)

对差额最大处，采用最小运费调运。

3. 解的最优性检验

3.1 闭回路法

Definition (闭回路法)

通过闭回路计算检验数
找到负的最小检验数，在闭回路中令最小正数为 0
重复 1、2 直至最优解

3.2 对偶检验法

运输问题的对偶问题为 $\begin{align*} & \max w = \sum_{i = 1}^{m} a_{i}u_{i}+\sum_{j = 1}^{n} b_{j}v_{j} \\ & \mathrm{s.t.}\begin{cases} u_{i}+v_{j}\leq c_{ij}, &i=1,\dots,m,j=1,\dots,n \\ u_{i},v_{j}\text{无约束} \end{cases} \end{align*}$

Theorem (对偶变量与检验数的关系)

\sigma_{ij}=c_{ij}-(u_{i}+v_{j})

4. 解的改进

以 $x_{ij}$ 为换入变量，找出其在运输表中的闭回路
以空格 $(A_{i},B_{j})$ 为第一个奇数顶点，沿闭回路的顺（逆）时针方向前进，对闭回路上的顶点依次编号
在闭回路上的所有偶数顶点集合中，找到运输量最小的 $(\min x_{ij})$ 的顶点，以该格中的变量为换出变量
以换出变量的运输量为调整量，将该闭回路上所有奇数顶点处的运输量都增加该数值，所有偶数顶点处的运输量减少该数值
检验是否为最优解，如果不是则重复该操作

03运输问题

03运输问题

1. 运输问题概述

2. 表上作业法

3. 解的最优性检验

3.1 闭回路法

3.2 对偶检验法

4. 解的改进

5. 特殊运输问题

5.1 产销不平衡

5.2 有转运的运输问题