第4章运输问题

57第四章运输问题运输问题（transportationproblem）一般是研究把某种商品从若干个产地运至若干个销地而使总运费最小的一类问题。然而从更广义上讲，运输问题是具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可以解决诸多非商品调运问题。运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，这正是单独研究运输问题的目的所在。§1运输问题的数学模型[例4-1]某公司经营某种产品，该公司下设A、B、C三个生产厂，甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，由于各工厂到各销售点的路程不同，所以单位产品的运费也就不同。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表4-1所示。问该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。表4-1甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656设ijx代表从第i个产地到第j个销地的运输量（3,2,1i；4,3,2,1j），用ijc代表从第i个产地到第j个销地的运价，于是可构造如下数学模型：ijijijxcw3141minijijax41（3,2,1i；运出的商品总量等于其产量）jiijbx31（4,3,2,1j；运来的商品总量等于其销量）0ijx通过该引例的数学模型，我们可以得出运输问题是一种特殊的线性规划问题的58结论，其特殊性就在于技术系数矩阵是由“1”和“0”两个元素构成的。将该引例的数学模型做一般性推广，即可得到有m个产地、n个销地的运输问题的一般模型。注意：在此仅限于探讨总产量等于总销量的产销平衡运输问题，而产销不平衡运输问题将在本章的后续内容中探讨。ijminjijxcw11mininjijax1（mi,,2,1；运出的商品总量等于其产量）jmiijbx1（nj,,2,1；运来的商品总量等于其销量）0ijx供应约束确保从任何一个产地运出的商品等于其产量，需求约束保证运至任何一个销地的商品等于其需求。除非负约束外，运输问题约束条件的个数是产地与销地的数量和，即nm；而决策变量个数是二者的积，即nm。由于在这nm个约束条件中，隐含着一个总产量等于总销量的关系式，所以相互独立的约束条件的个数是1nm个。§2运输问题的求解运输问题的求解采用表上作业法，该方法是单纯形法求解运输问题的一种特定形式，其实质是单纯形法。既然表上作业法是一种特定形式的单纯形法，它自然与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。表上作业法的基本步骤可参照单纯形法归纳如下：1．找出初始基可行解：即要在nm阶产销平衡表上给出“1nm”个数字格（基变量）；2．求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；3．确定入基变量，若lkijij}0min{，那么选取lkx为入基变量；4．确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量；5．在表上用闭合回路法调整运输方案；6．重复2、3、4、5步骤，直到得到最优解。592.1确定初始基可行解与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解），这一点是显然的。确定初始基可行解的方法有很多，在此介绍比较简单但能给出较好初始方案的最小元素法（theleastcostrule）和伏格尔法（Vogel’sapproximationmethod）。1．最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。下面就用例4-1说明最小元素法的应用。第一步：从表4-1中找出最小运价“1”，这表示先将B生产的产品供应给甲。由于B每天生产4个单位产品，甲每天需求3个单位产品，即B每天生产的产品除满足甲的全部需求外，还可多余1个单位产品。在（B，甲）的交叉格处填上“3”，形成表4-2；将运价表的甲列运价划去得表4-3，划去甲列表明甲的需求已经得到满足。表4-2甲乙丙丁产量（ai）A7B34C9销量（bj）3656表4-3甲乙丙丁A311310B1928C74105第二步：在表4-3的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（B，丙），即将B余下的1个单位产品供应给丙，表4-2转换成表4-4。划去B行的运价，划去B行表明B所生产的产品已全部运出，表4-3转换成表4-5。表4-4甲乙丙丁产量（ai）A7B314C9销量（bj）3656第三步：在表4-5中再找出最小运价“3”，这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。最后在产销平衡表上得到一个调运方案，见表4-6。这一方案的总运费为86个单位。60表4-5甲乙丙丁A311310B1928C74105表4-6甲乙丙丁产量（ai）A437B314C639销量（bj）3656最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有“1nm”个数字格（基变量）的初始基可行解。然而，问题并非总是如此，有时也会出现这样的情况：在供需关系格（ji,）处填入一数字，刚好使第i个产地的产品调空，同时也使第j个销地的需求得到满足。按照前述的处理方法，此时需要在运价表上相应地划去第i行和第j列。填入一数字同时划去了一行和一列，如果不加入任何补救措施的话，那么最终必然无法得到一个具有“1nm”个数字格（基变量）的初始基可行解。为了使在产销平衡表上有“1nm”个数字格，这时需要在第i行或第j列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。表4-7甲乙丙丁产量（ai）A3113104B19284C7410512销量（bj）3656将例4-1的各工厂的产量做适当调整（调整结果见表4-7），就会出现此类特殊情况。第一步在（B，甲）处填入“3”，划去甲列运价；第二步在（B，丙）处填入“1”，划去B行运价，此二步的结果见表4-8和表4-9。表4-8甲乙丙丁产量（ai）A4B314C12销量（bj）365661表4-9甲乙丙丁产量（ai）A3113104B19284C7410512销量（bj）3656表4-10甲乙丙丁产量（ai）A044B314C12销量（bj）3656表4-11甲乙丙丁产量（ai）A3113104B19284C7410512销量（bj）3656表4-9中剩下的最小元素为“3”，其对应产地A的产量是4，销地丙的剩余需要量也是4，在格（A，丙）中填入“4”，需同时划去A行和丙列。在填入“4”之前A行和丙列中除了（A，丙）之外，还有（A，乙）、（A，丁）和（C，丙）三个空格未被划去；因此，可以在（A，乙）、（A，丁）和（C，丙）任选一格填加一个“0”，不妨选择（A，乙），结果可见表4-10和表4-11。注意这个“0”是不能填入（A，甲）或（B，丙）的，因为在填入“4”之前它们已经被划去了（见表4-9）。2．伏格尔法最小元素法的缺点是只考虑了就近的问题却没有考虑就近所付出的机会成本。伏格尔法通过计算每一行、每一列在没有选择最小元素（选择次小元素）时的费用增加，可给出最优或近似最优的方案，因此它是一种十分有效的方法。伏格尔法把费用增量定义为给定行或列次小元素与最小元素的差（如果存在两个或两个以上的最小元素费用增量定义为零）。最大差对应的行或列中的最小元素确定了产品的供应关系，即优先避免最大的费用增量发生。当产地或销地中的一方在数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤，即可得到一个初始的基可行解。仍以例4-1来说明伏格尔法。第一步：在表4-1中找出每行、每列两个最小元素的差额，并填入该表的最右列和最下行，见表4-12。62表4-12甲乙丙丁两最小元素之差A3113100B19281C741051两最小元素之差2513第二步：从行和列的差额中选出最大者，选择它所在的行或列中的最小元素的位置确定供应关系。在表4-12中乙列是最大差额“5”所在的列，乙列中的最小元素是“4”，从而确定了C与乙间的供应关系，表4-13即反应了这一供应关系。同最小元素法一样，由于乙的需求已得到了满足，将运价表中的乙列划去。第三步：对运价表中未划去的元素再分别计算出各行、各列两个最小运费的差，并填入该表的最右列和最下行，见表4-14。重复第一、第二两步，直到给出一个初始基可行解，处理过程见表4-15~表4-23。表4-13甲乙丙丁产量（ai）A7B4C69销量（bj）3656表4-14甲乙丙丁两最小元素之差A3113100B19281C741052两最小元素之差213表4-15甲乙丙丁产量（ai）A7B4C639销量（bj）3656在表4-16中两个最小元素的最大差是“2”，但最大差“2”并不唯一，在此应按最大差所对应的最小元素最小的原则确定供应关系，即选择B生产的产品运输给甲。63表4-16甲乙丙丁两最小元素之差A3113100B19281C74105两最小元素之差212表4-17甲乙丙丁产量（ai）A7B34C639销量（bj）3656表4-18甲乙丙丁两最小元素之差A3113107B19286C74105两最小元素之差12表4-19甲乙丙丁产量（ai）A57B34C639销量（bj）3656表4-20甲乙丙丁两最小元素之差A311310B1928C74105两最小元素之差2表4-21甲乙丙丁产量（ai）A57B314C639销量（bj）365664表4-22甲乙丙丁两最小元素之差A311310B1928C74105两最小元素之差表4-23甲乙丙丁产量（ai）A527B314C639销量（bj）3656由以上可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤是完全相同的。伏格尔法给出的初始解比最小元素法给出的初始解一般来讲会更接近于最优解。2.2基可行解的最优性检验对初始基可行解的最优性检验有闭合回路法和位势法两种基本方法。闭合回路法具体、直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。1．闭合回路法判断基可行解的最优性，需计算空格（非基变量）的检验数。闭合回路法即通过闭合回路求空格检验数的方法。下面就以表4-6中给出的初始基可行解（最小元素法所给出的初始方案）为例，讨论闭合回路法。表4-24甲乙丙丁产量（ai）A（+3）4（-3）37B3（-1）1（+2）4C639销量（bj）3656从表4-6给定的初始方案的任一空格出发寻找闭合回路，如对于空格（A，甲）在初始方案的基础上将A生产的产品调运一个单位给甲，为了保持新的平衡，就要依次在（A，丙）处减少一个单位、（B，丙）处增加一个单位、（B，甲）处减少一个单位；即要寻找一条除空格（A，甲）之外其余顶点均为有数字格（基变量）组成的闭合回路。表4-24中用虚线画出了这条闭合回路。闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的“+”、“-”号表示运量的调整方向。对应这样的方案调整，运费会有什么变化呢？可以看出（A，甲）处增加一个65单位，运费增加3个单位；在（A，丙）处减少一个单位，运费减少3个单位；在（B，丙）处增加一个单位，运费增加2个单位；在（B，甲）处减少一个单位，运费减少1个单位。增减相抵后，总的运费增加了1个单位。由检验数的经济含义可以知道，（A，甲）处单位运量调整所引起的运费增量就是（A，甲）的检验数，即111。仿照此步骤可以计算初始方案中所有空格的检验数，表4-25~表4-30展示了各检验数的计算过程，表4-30给出了最终结果。可以证明，对初始方案中的每一个空格来说“闭合回路存