运输问题的单纯形解法

问题:用一辆车运50批货，有3个仓库，各存有18，12，20，运到4个地方，他们各需要12，8，16，14，时间分别为：
50 30 90 50
60 80 40 10
90 70 100 20
做运输方案。

问题的抽象

设三个仓库分别为$M_i$，$i=1,2,3$
四个目的地分别为$A_j$，$j=1,2,3,4$
从仓库$M_i$运送到目的地$A_j$的单位成本（花费时间）为$c_{ij}$
则有：
$$\sum _{i=1}^3{M}_i=\sum _{j=1}^4{A}_j=50$$
需要求解的运输方案即：从仓库$M_i$运送到目的地$A_j$的货物数目，记它为$x_{ij}$
则问题等价于求解线性规划问题：
$$\begin{gathered} min\sum _{i=1}^3\sum _{j=1}^4{c}_{ij}{x}_{ij} \\ s.t.\sum _{i=1}^3{x}_{ij}=A_j \\ \sum _{j=1}^4{x}_{ij}=M_i \end{gathered}$$

用表格表示如下：

问题求解

1. 寻找基础可行解
2. 计算单纯形乘子
3. 计算相对成本系数
4. 若相对成本系数都非负，stop，得到最优解。否则，进行第5步
5. 选择相对成本系数为负的非基变量进入基变量（通常挑选最小的相对成本系数对应的变量），计算调整回路，得到新解，返回第2步。

1 寻找基础可行解

方法：西北角法则。

1. 从左上角开始
2. 在不超过行和 或者 列和 的前提下，给这个单元格指定一个最大的数值。
3. 如果这一行仍然有任意的剩余需求，考虑该单元格右边的单元格，否则就考虑这个单元格下方的单元格，如果此行此列都得到了满足，stop。否则回到第2步。

例

1. 首先填写左上角$x_{11}$，行和为18，列和为12，则$x_{11}$最大为12

2. 第一列 列和 已经得到满足，第一行还没有，则考虑$x_{11}$右边单元格$x_{12}$，最大为6

3. 第一行 行和 已经得到满足，考虑第二列，考虑$x_{12}$下方单元格$x_{22}$，最大为2

4. 同上步骤

得到最终的基础可行解为：

注：此表代表：$x_{11}=12,x_{12}=6,x_{13}=0,\cdots$

2 计算单纯形乘子

首先写出成本矩阵：
$$C=\left[\begin{array}{cccc}50& 30& 90& 50\\ 60& 80& 40& 10\\ 90& 70& 100& 20\end{array}\right]$$
将基础可行解对应的数值圈出：

3 计算相对成本系数

4 判断是否最优

5 调整回路

今天的文章运输问题的单纯形解法分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。