第3章运输问题.ppt

《第3章运输问题.ppt》由会员分享，可在线阅读，更多相关《第3章运输问题.ppt（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第3章章 运输问题运输问题1.运输问题的数学模型运输问题的数学模型有有m个生产地点可供应某种物资个生产地点可供应某种物资各个产地的供应量（产量）各个产地的供应量（产量）有有n个销地销售这种物资个销地销售这种物资各个销地的需求量（销量）各个销地的需求量（销量）从从Ai到到Bj运输单位物资的运价（单价）为运输单位物资的运价（单价）为1.运输问题的数学模型运输问题的数学模型 销地销地产地产地B1B2Bn产量产量A1a1A2a2Amam销量销量b1b2bn产产销销平平衡衡表表1.运输问题的数学模型运输问题的数学模型 销地销地产地产地B1B2BnA1c11c12c1nA2c21c22c2nAmcm1c

2、m2cmn单单位位运运价价表表1.运输问题的数学模型运输问题的数学模型 决策变量决策变量 表示从表示从Ai到到Bj的运量，那么在的运量，那么在产销平衡产销平衡条件条件下，要求得总运费最小的调运方案，可求解以下数学下，要求得总运费最小的调运方案，可求解以下数学模型：模型：2.表上作业法表上作业法1.找出初始调运方案，即在找出初始调运方案，即在mn维的产销平衡表上给出维的产销平衡表上给出m+n-1个数字格；个数字格；最小元素法最小元素法伏格尔法（伏格尔法（Vogel法）法）或或2.判别是否为最优调运方案，求判别是否为最优调运方案，求检验数检验数；闭回路法闭回路法位势法位势法或或3.求解新的调运方案

3、；求解新的调运方案；闭回路调整法闭回路调整法【例例】销地销地产地产地B1B2B3B4产量产量A170A280A350销量销量40307060 销地销地产地产地B1B2B3B4A13624A25334A31752最最小小元元素素法法40700103050总运费总运费490元元【练习练习】销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656最小元素法最小元素法【例例】销地销地产地产地B1B2B3B4产量产量A170A280A350销量销量40307060 销地销地产地产地B1B2B3B4行差额行差额A13624A25334A31752列差额列差额

4、伏伏格格尔尔法法101231230111212402131210211070050【练习练习】销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656伏格尔法伏格尔法调运方案是否最优？调运方案是否最优？v 在给出调运方案的计算表上，从每一空格在给出调运方案的计算表上，从每一空格出发找一条闭回路。它是以某空格为起点，出发找一条闭回路。它是以某空格为起点，用水平或垂直线向前划；当碰到一个用水平或垂直线向前划；当碰到一个数字数字格格时可以转时可以转90，继续前进；直到回到起始，继续前进；直到回到起始空格为止。空格为止。闭回路法闭回路法 销地销地产地产地

5、B1B2B3B4产量产量A170A280A350销量销量4030706040700103050 销地销地产地产地B1B2B3B4A13624A25334A31752闭闭回回路路法法【例例】（1）（4）（1）（2）（6）（4）销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656最最小小元元素素法法【练习练习】销地销地产地产地B1B2B3B4产量产量A1437A2314A3639销量销量3656闭闭回回路路法法 销地销地产地产地B1B2B3B4产产量量A170A280A350销量销量4030706040700103050 销地销地产地产地B1B2

6、B3B4A13624A25334A31752位位势势法法【例例】销地销地产地产地B1B2B3B4行位势行位势A1A2A3列位势列位势23341202123-12（1）（4）（1）（2）（6）（4）销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656伏伏格格尔尔法法【练习练习】销地销地产地产地B1B2B3B4产量产量A1527A2314A3639销量销量3656位位势势法法 销地销地产地产地B1B2B3B4A1311310A21928A374105 销地销地产地产地B1B2B3B4产量产量A1437A2314A3639销量销量3656【例例】闭

7、闭回回路路调调整整法法（1）（2）（1）（-1）（10）（12）销地销地产地产地B1B2B3B4产量产量A1437A2314A3639销量销量3656（-1）闭闭回回路路调调整整法法+-+-销地销地产地产地B1B2B3B4产量产量A17A234A3639销量销量3656125 销地销地产地产地B1B2B3B4产量产量A19A25A37销量销量3846 销地销地产地产地B1B2B3B4行差额行差额A129107A21342A38425列差额列差额512112321252358421315 销地销地产地产地B1B2B3B4产产量量A13519A255A3347销量销量3846 销地销地产地产地B1

8、B2B3B4A129107A21342A38425 销地销地产地产地B1B2B3B4行位势行位势A1A2A3列位势列位势207-597-52（3）97242（4）（-1）（2）（11）（3）销地销地产地产地B1B2B3B4产产量量A13519A255A3347销量销量3846+销地销地产地产地B1B2B3B4产产量量A1369A2505A3347销量销量3846 销地销地产地产地B1B2B3B4产产量量A1369A2505A3347销量销量3846 销地销地产地产地B1B2B3B4A129107A21342A38425 销地销地产地产地B1B2B3B4行位势行位势A12(1)(4)70A2(4

9、)3(3)2-5A3(10)42(2)-4列位势列位势2867总运费总运费3.产销不平衡运输问题产销不平衡运输问题总产量大于总销量总产量大于总销量总销量大于总产量总销量大于总产量假想销地假想销地假想产地假想产地各产地到假想销地的各产地到假想销地的单位运价单位运价一般一般为为0该假想产地到各销地该假想产地到各销地的单位运价的单位运价一般一般为为0 销地销地产地产地B1B2B3B4产量产量A170A280A365销量销量40307060【例例】销地销地产地产地B1B2B3B4B5产量产量A170A280A365销量销量4030706015 销地销地产地产地B1B2B3B4A13624A25334A

10、31752 销地销地产地产地B1B2B3B4B5A136240A253340A317520【例例】设有三个化肥厂（设有三个化肥厂（A、B、C）供应四个地区（）供应四个地区（I、II、III、IV）的农用化肥。假定等量的化肥在这些地区使用效果相同，）的农用化肥。假定等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地区需求量及从各化肥厂到各地区运送各化肥厂年产量、各地区需求量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥单位化肥的运价如下表所示。试求出总的运费最节省的化肥调拨方案。调拨方案。需求地区需求地区化肥厂化肥厂IIIIIIIV产量产量（万吨）（万吨）A1613221750B1413191560C19202350最低需求最低需求3070010最高需求最高需求507030不限不限 销地销地产地产地IIIIIIIIVIV产量产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量销量302070301050