表上作业法

---

解运输问题的一个方法。

运输问题是指一种物资的分配问题，设在m个发点A₁，A₂，…，A_m有某种物资，数量分别为a₁，a₂，…a_m要将物资发往n个收点B₁，B₂，…B_n，各收点的需要量分别为b₁，b₂，…b_n，从发点A_i到收点B_j运送单位物资的运费为C_ij，要制定一个运输方案，使总运费最小。

表上作业法是在以下运输表格上进行运输问题的求解。表格形式为：

上面表格中共有m×n个空格，每一格都表示一个决策变量值x_ij，另外，每一格都有其相应的目标函数系数C_ij。

表上作业法的步骤是：

1．在m+n－1个格中填上X_ij，X_ij非负并且满足运输问题方程式要求，这m+n－1个数不形成闭回路。

这m+n－1个格就代表基可行解的基变量。

2．计算没有填数的格(非基变量)的检验数，其方法是要计算的这一格和m+n－1个基变量格合在一起共有m+n个格，在这m+n个格中一定可以找到一条闭回路，用回路法位势法计算各非基变量格的检验数。

3．检查所有的检验数，看它是否满足最优解判别准则，如所有，那么这个基可行解就是最优解。否则通过基可行解的迭代，替换一个基变量出基，得到新的基可行解，再返到第二步，继续计算。