管理运筹学讲义第7讲运输问题.pptx

《管理运筹学讲义第7讲运输问题.pptx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1中山大学南方学院工商管理系王甜源第7讲运输问题2运输问题及其数学模型表上作业法产销不平衡的运输问题目录3在线性规划问题中，有一类特殊类型的问题－－运输问题。这类问题主要研究把某种物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个总运费最少的方案。在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是

2、物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。4但是由于在运输问题的数学模型中，约束方程的系数矩阵具有特殊的结构。因此，存在一种比单纯形法更为简便的方法——表上作业法。表上作业法通过定制的运输表确定最优调运方案，但其本质仍然是单纯形法，其主要步骤是：首先需要确定一个初始调运方案（初始基本可行解），然后检验现行调运方案（现行基本可行解）是否最优，若非最优，则需对现行调运方案（现行基本可行解）进行改进等几个阶段。只是表上作业法对单纯形法作了适当的修改，从而提高了计算的效率。

3、5运输问题的一般提法是：某种物质（粮食、棉花、煤炭等）有m个产地，其产量是；有n个销地,其销量（或需求量）是。现在需要把这种物质从m个产地运送到n个销地。若从运到的单位运价为。又限定产销平衡，即，问应如何制定调运方案可使总费用最小？运输问题及其数学模型6上述已知条件可用下面的表格来表示。销量产量销地产地7如果用代表从第ｉ产地运往第ｊ销地的物质单位数量（i=1，2m；j＝1，2n），Ｚ为总运费，那么求解上述使总运费最小的运输问题。可以用下列数学模型描述：从每一个产地运往各个销地的物质数量之和等于该产地的产量从各个产地运往每

4、一个销地的物质数量之和等于该销地的销量使总运费达到最小运输量非负8运输问题的线性规划模型具有特殊的结构，其约束方程组的系数矩阵A具有如下形式：m×n个决策变量，m＋n个约束条件。经证明：产销平衡的运输问题的非零变量为m+n-1个。具体证明如下：A=111111111111m行n行1111119A=111111111111m行n行111111该矩阵的元素全部为0或1。每一列只有2个元素为1，其余为0。若用表示决策变量的系数列向量，则在中第i个和第m＋j个元素为1，其余为0。我们也可以用两个单位向量之和来表示。即：其中和分别

5、为第i个元素和第m＋j个元素为1的单位向量。10通过对运输问题的数学模型约束矩阵Ａ的特殊结构作进一步分析，还可以发现矩阵Ａ的秩为m＋n－1，即Ｒ(Ａ)＝m+n-1。这是因为系数矩阵A的前m个行向量之和减去后n个行向量之和恰好为零向量。即矩阵Ａ的m＋n个行向量线性相关。因此Ｒ(Ａ)

6、可行解（2）用闭回路法求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同表上作业法换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否13确定初始基本可行解求运输问题的初始基本可行解有多种方法。在此我们只介绍最小元素法和伏格尔法两种方法。为了确定初始基本可行解，首先必须画出运输问题的基本表格。即调运表和运价表。销地产地产量销量销地产地调运表运价表14在实际计算中，为了方便通常将

7、调运表和运价表合二为一，综合为下列运输表。销地产地产量c11c12c1nc21c22c2ncm1cm2cmn销量运输表151，最小元素法最小元素法的基本思路是以运价最低者优先为原则安排初始的调运方案，即从单位运价表中最小运价处开始确定供销关系。若产量大于销量，则用加工厂的产量满足对应销地的全部日销量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的日产量中减去调运量。反之，若产量小于销售量。则把加工厂的日产量全部分配给对应的销售地。在对应空格填入调运量。用水

8、平直线划去加工厂所在行，并从对应销地的日销量中减去调运量。依次类推，逐步推出初始方案。由于最小元素法已经考虑到了运价最低者优先为原则，因此所求的初始基本可行解通常比较接近最优解。经过若干次调整即可求得最优解。运输问题最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格——即一组可行解，这里