- 上一篇：C语言在初等数论中的应用
- 下一篇：多目标规划的解法比较
根据以上讨论我们可以得到一类运输问题，通过归纳总结可以得出其一般性的规律，我们采用数学模型对其进行研究.
2.1 运输问题的数学模型
如果用 代表从第 个产地调运给第 个销地的物资的单位数量，那么在产销平衡的条件下，使得总的运费支出最小，可以建立以下数学模型：
目标函数
约束条件
这就是运输问题的数学模型，它共有 个变量， 个约束条件.但我们研究的是产销平衡的运输问题（对于产销不平衡的运输问题，我们可以利用增加虚拟销地或者增加虚拟产地使其达到平衡.在此，我们不作讨论），所以系数矩阵中线性独立的列向量最多为（ ）个，即运输问题的解中基变量数一般为（ ）个.求解线性规划问题的基本方法是单纯形法，运输问题作为一种特殊的线性规划问题，也可以用单纯形法，但因为其变量很多，直接应用单纯形法十分麻烦，所以，我们需要一种改进的单纯形法来求解运输问题.因此，对于变量较多的线性规划模型,可以采用表上作业法,我们通常使用最小元素法求解运输问题的初始方案，它的原理与单纯形法一致，是一种改进的单纯形法.同时它又比单纯形法解决运输问题更为方便；对于具有更多变量的运输问题的模型,若采用表上作业法的手工算法进行求解则会发现,求解过程非常繁琐,不仅运算量大,而且极容易出错.这种情况下,为了提高解题速度,通常会借助一些数学软件,例如LINGO，MATLAB，EXCEL等软件.
2.2 运输问题的求解
模型讨论后,我们对运输问题的求解方法进行分析，常用的方法有三种:西北角法、最小元素法、Vogel(伏格尔)法.在这里，我们着重使用最小元素法求解运输问题的最佳方案，其他两种不做讨论.
使用最小元素法来确定初始基可行解,再用位势法来求出非基变量的检验数,最后用闭回路法调整得出新的调运方案.其中,最小元素法是从运价最小的格开始,在格内的右下角标上允许取得的最大数.然后按运价从小到大顺序填数.若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去,如果某一行和某一列恰好同时满足则同时划去这一行和这一列并在这行或者这列的任意一个方格上填0.如此进行下去,直至得到一个基本可行解;得到一组基可行解后，我们需要用位势法来检验此可行解是否满足最优方案即非基变量的检验数是否为非负的.具体做法是我们对运输表上的每一行赋予一个数值 ,对每一列赋予一个数值 ,我们首先可以令其中一个基变量的 为0，则其另一个位势就为 ，相应的其他位势可以通过公式 ( 为单位运价)得出，进而求出每一个非基变量的检验数.若每一个检验数都 0则方案达到最优，否则要用闭合回路法进行调整.闭回路法,就是对代表非基变量的空格(其调运量为零),把它的调运量调整为1,由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加或减1,最后计算出由于这些变化给运输方案总运费带来的变化.其增加或减小的值填入该空格作为非基变量的检验数,若这些检验数都大于等于零,那么原本的基可行解就是最优解,否则要再次一步一步迭代直至最终找出最优解.
所以,我们可以概括出运输问题求解步骤为:(1)找出初始基本可行解;(2)求各非基变量的检验数;(3)确定入基变量与出基变量（找出绝对值最大的负检验数用闭合回路调整）,找出新的基本可行解（新的调运方案）;(4)重复(2)和(3)直至得到最优解.