《运筹学》第三章 运输问题.ppt

《《运筹学》第三章 运输问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运输问题(TransportationProblem)运输问题及其数学模型表上作业法应用问题举例本章讨论一类重要的线性规划问题——运输问题研究单一物资的调运问题：将某种物资从若干个产地调运到若干个销地，在每个产地的供应量和销地的需求量已知的前提下，如何在多个可行的调运方案中，确定一个使总的运输费用最少的方案。重点内容：产销平衡运输问题数学模型表上作业法例：某运输问题的资料如下：单位销地运价产地产量2910291342584257销量3846一、运输问题及其数学模型如何调运物品，使总的运输费用最小？数学模型的一般形式已

2、知资料如下：销产地地产量供需平衡销量运价当产销平衡时，其模型如下：当产大于销时，模型当产小于销时，模型特征：1、平衡运输问题必有可行解，也必有最优解；2、运输问题的基本可行解中应包括m+n－1个基变量。运输问题约束条件的系数矩阵运输问题具有的特点：（1）约束条件系数矩阵的元素等于0或1；（2）约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个方程中也出现一次。对产销平衡运输问题，还有以下特点：（1）所有结构约束条件都是等式约束；（2）各产地产量之和等于各销地销量之和。计算步

3、骤：(1)找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。(最小元素法、西北角法或伏格尔法）(2)求检验数。（闭回路法或位势法）判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。对方案进行改善，找出新的调运方案。（表上闭回路法调整）确定m+n-1个基变量(4)重复（2）、（3），直到求得最优调运方案。空格二、表上作业法例一、某运输资料如下表所示：单位销地运价产地产量311310719284741059销量36561、求初始方案B1B2B3B4产量A17A24A39销量365631131

4、0192741058341633（1）最小元素法：基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元14333（2）西北角法（或左上角法）：此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：365674934490656404902562029005620090036360000000340002200036总的运费＝(3×3)＋(

5、4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元.分别计算各行、各列次小、最小运价的差额，优先在最大差额处进行供需搭配。步骤：10计算未划去行、列的差额；20找出最大差额对应的最小元素cij进行供需分配；30在未被划去的行、列重新计算差额。（3）沃格尔法销产B1B2B3B4供量A17A24A39销量36566B1B2B3B4行差额A13113100A219281A3741051列差额2513销产B1B2B3B4供量A17A24A39销量36566B1B2B3B4行差额A13113100A2192

6、81A3741052列差额2133销产B1B2B3B4供量A17A24A39销量36566B1B2B3B4行差额A13113100A219281A374105列差额21233销产B1B2B3B4供量A17A24A339销量36566B1B2B3B4差额A13113107A219286A374105差额123512（1）闭合回路法：σij≥0（因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。σij<0表示运费减少，σij>0表示运费增加。2、

7、解的最优性检验（检验数的求法）两种常用方法：闭回路法、对偶变量法闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在惟一闭回路。B1B2B3B4产量A17A24A39销量3656313463（＋1）（＋1）（－1）（－1）①②③③1最小元素法X11（空格处（A1B1））为换入变量，x11增加1，运费的变化为：。这个变化就是x11的检验数，故σ11=1B1B2B3B4产量A17A24A39销量3656313631

8、24B1B2B3B4产量A17A24A39销量36563136312-14B1B2B3B4产量A17A24A39销量365631363121-14B1B2B3B4产量A17A24A39销量365631363121-1124B1B2B3B4产量A17A24A39销量365631363121-112104检验数中有负数，说明原方案不是最优解。B1B