运筹学：运输问题.docxVIP

运输问题运输问题（transportation problem）一般是研究把某种商品从若干个产地运至若干个销地而使总运费最小的一 类问题。然而从更广义上讲，运输问题是具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可以解决诸多非商品调运问题。运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，这正是单独研究运输问题的目的所在。§1运输问题的数学模型[例4-1] 某公司经营某种产品，该公司下设A、B、C三个生产厂，甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，由于各工厂到各销售点的路程不同，所以单位产品的运费也就不同案。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表4-1所示。问该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。表4-1?甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656?设代表从第个产地到第个销地的运输量（；），用代表从第个产地到第个销地的运价，于是可构造如下数学模型：?? （；运出的商品总量等于其产量）?? （；运来的商品总量等于其销量）通过该引例的数学模型，我们可以得出运输问题是一种特殊的线性规划问题的结论，其特殊性就在于技术系数矩阵是由“1”和“0”两个元素构成的。将该引例的数学模型做一般性推广，即可得到有个产地、个销地的运输问题的一般模型。注意：在此仅限于探讨总产量等于总销量的产销平衡运输问题，而产销不平衡运输问题将在本章的后续内容中探讨。?（；运出的商品总量等于其产量）?（；运来的商品总量等于其销量）供应约束确保从任何一个产地运出的商品等于其产量，需求约束保证运至任何一个销地的商品等于其需求。除非负约束外，运输问题约束条件的个数是产地与销地的数量和，即；而决策变量个数是二者的积，即。由于在这个约束条件中，隐含着一个总产量等于总销量的关系式，所以相互独立的约束条件的个数是个。§2运输问题的求解运输问题的求解采用表上作业法，该方法是单纯形法求解运输问题的一种特定形式，其实质是单纯形法。既然表上作业法是一种特定形式的单纯形法，它自然与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。表上作业法的基本步骤可参照单纯形法归纳如下：1．? 找出初始基可行解：即要在阶产销平衡表上给出“”个数字格（基变量）；2．? 求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；3．? 确定入基变量，若，那么选取为入基变量；4．? 确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量；5．? 在表上用闭合回路法调整运输方案；6．? 重复2、3、4、5步骤，直到得到最优解。?2.1确定初始基可行解与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解），这一点是显然的。确定初始基可行解的方法有很多，在此介绍比较简单但能给出较好初始方案的最小元素法（the least cost rule）和伏格尔法（Vogel’s approximation method）。1．最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。下面就用例4-1说明最小元素法的应用。第一步：从表4-1中找出最小运价“1”，这表示先将B生产的产品供应给甲。由于B每天生产4个单位产品，甲每天需求3个单位产品，即B每天生产的产品除满足甲的全部需求外，还可多余1个单位产品。在（B，甲）的交叉格处填上“3”，形成表4-2；将运价表的甲列运价划去得表4-3，划去甲列表明甲的需求已经得到满足。表4-2?甲乙丙丁产量（ai）A????7B3???4C????9销量（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）A????7B3?1?4C????9销量（bj）3656??第三步：在表4-5中再找出最小运价“3”，这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。最后在产销平衡表上得到一个调运方案，见表4-6。这一方案的总运费为86个单位。表4-5?甲乙丙丁A311310B1928C74105?表4-6?甲乙丙丁产量（ai）A??437B3?1?4C?6?39销量（b