管理运筹学-运输问题.pptxVIP

管理运筹学华国伟北京交通大学经管学院物流管理系

第三章运输问题TransportationProblem

202X本节内容提要3.1运输问题的数学模3.2表上作业法

A1AiAm产地产量销地B1BjBn销量3.1运输问题的数学模型

例：某运输问题的资料如下：单位销地运价产地产量2910291342584257销量3846一、运输问题的数学模型

数学模型的一般形式已知资料如下：单销产量产地产量销量运价供需平衡

当产销平衡时，其模型如下：Ai的产品全部供应出去Bj的需求全部得到满足产销平衡的运输问题必定存最优解.

当产大于销时，其模型是：

当产小于销时，其模型是：

mn

平衡表、运价表和二为一：

约束条件或解可用产销平衡表表示:

21ui?vj无约束（i=1,2,…,m;j=1,2,…,n)vjn个ui设ui,vj为对偶变量，对偶问题模型为m个4365

平衡运输问题必有可行解，也必有最优解；01运输问题的基本可行解中应包括m+n－1个基变量。02特征：

⑷.重复⑵.⑶，直到找到最优解为止。步骤：⑴.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；⑵.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；⑶.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；二、表上作业法确定m+n-1个基变量空格

3.2求解运输问题的算法:表上作业法开始01求各非基变量的检验数02是否达到最优解03结束04确定换入变量与换出变量05新的基可行解06求初始基可行解07N08Y09最小元素法，伏格尔法10闭回路法，位势法11闭回路调整法12

例一、某运输资料如下表所示：单位销地运价产地产量311310719284741059销量36561、求初始方案：

西北角发也就是从运价表的西北角位置开始,依次安排m个产地和n个销地之间的运输业务,从而得到一个初始调运方案的方法.西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则.初始基可行解的确定—西北角法

⑴.西北角法(或左上角法):此法是纯粹的人为的规定,没有理论依据和实际背景,但它易操作,特别适合在计算机上编程计算,因而受欢迎.方法如下：总的运费＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元

B1B2B3B4产量A17A24A39销量3656311310192741058341633⑵.初始基可行解的确定--最小元素法：基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元

分别计算各行、各列次小、最小运价的差值,优先在最大差值处进行供需搭配.差值=次小-最小01步骤：02计算未划去行、列的差额;03找出最大差额对应的最小元素cij进行供需分配;04在未被划去的行、列重新计算差额.05初始基可行解的确定--最大差值法(伏格尔法)Vogel06

6销产B1B2B3B4供量A17A24A39销量3656B1B2B3B4供量219284A3741059销量3656列差值2513行差值011

63销产B1B2B3B4供量A17A24A39销量3656B1B2B3B4行差值219281A3741052列差值213

363销产B1B2B3B4供量A17A24A39销量3656B1B2B3B4行差值219281A374105列差值212

51263B1B2B3B4差值219286A374105差值12销产B1B2B3B4供量A17A24A339销量3656

01以上方法得到的初始解为基可行解02每次行(需求)或列(供应)达到饱和03每次必划掉一行或一列04得到的元素个数必为m+n-1个05西北角法最小元素法最大差值法

01练习02P973.12

σij≥0（因为目标函数要求最小化）表格中有调运量的地方为基变量,空格处为非基变量.基变量的检验数σij＝0,非基变量的检验数σij≥0.σij0表示运费减