§2 运输问题

特殊的规划问题之一，有特殊的求解方式

C1 问题模型

1）$m$个产地常量$a_1,\dots ,a_m,n$个销地销量$b_1,\dots ,b_n$，产地 $i$ 到销地 $j$ 运价$a_{ij}$

• 产销平衡问题：

$$\begin{gathered} \min z=\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij} \\ \{\begin{array}{l}{\sum }_{i=1}^m{x}_{ij}=b_j,j=1,2,\dots ,n\\ {\sum }_{j=1}^n{x}_{ij}=a_i,j=1,2,\dots ,n\\ x_{ij}\ge 0\end{array} \end{gathered}$$

• 产销不均衡问题：增加销地$b_{n+1}=\sum a_i-\sum b_i$，转化为产销平衡问题
  $$\begin{gathered} \min z=\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij} \\ \{\begin{array}{l}{\sum }_{i=1}^m{x}_{ij}=b_j,j=1,2,\dots ,n\\ {\sum }_{j=1}^{n+1}{x}_{ij}=a_i,j=1,2,\dots ,n,n+1\\ x_{ij}\ge 0\end{array} \end{gathered}$$

C2 表上作业法

1）确定初始基可行解：应当有m+n-1个基

• 最小元素法：最近供应优先。
  • 按运价表中运价依次填充最大可能运量，产大于销，划去一列，产小于销，划去一行
  • 可能同时划去一行一列，此时出现退化
• 伏格尔法：计算每一行与每一列中最小运费和次小运费之差。选择运费差最大的一列中的最小运费位置填充。产大于销，划去一列，产小于销，划去一行

2）最优解判别：

• 回路判别法：从任何一个空格出发可以找到一条矩形回路，计算回路上运费交错和作为该空格检验数。最优解不存在负检验数

• 位势法：

  引入人工变量$x_{\alpha }$，构成$m+n$阶初始基矩阵$B$

  对偶问题的解为$C_B{B}^{-1}=(u_1,\dots ,u_m;v_1,\dots ,v_n)$

  基向量$P_{ij}$对应的系数矩阵列向量为$e_i+e_{m+j}$，

  基向量检验数为$c_{ij}-C_B{B}^{-1}{P}_{ij}=c_{ij}-(u_i+v_j)=0$

  令$u_1=0$，依次可求得所有$u_i,v_j$，即可求得非基向量检验数${\sigma }_{ij}=c_{ij}-(u_i+v_j)$

  计算所有检验数，若有负检验数，说明不是最优解

3）最优解调整：

• 换入变量：检验数最小者
• 换出变量：换入空格作一闭合回路，回路上具有$-1$的空格中数字最小的为换出变量

4）无穷解：存在检验数0

※ 运输问题一定有有界最优解

5）退化：

• 确定初始解时，出现产销均衡，需要在同行或列的任一空格处取一个填0，可以选择运价最小的
• 回路调整时，出现两个带$-1$标记且同样的最小值，此时只有一个最小值变为空格，其余最小值处补0