运输问题-下载课件.ppt

1、2023-5-61一、运输问题的数学模型一、运输问题的数学模型例：某运输问题的资料如下：例：某运输问题的资料如下：单位单位 销地销地 运价运价产地产地B1B2B3B4产量产量A1291029A213425A384257销量销量38462023-5-62 )4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 约约束束条条件件：目目标标函函数数

2、：为为运运量量设设n 某种物品有某种物品有m个产地个产地A1,A2,Am，各产地的产，各产地的产量分别是量分别是a1,a2,am；有；有n个销地个销地B1,B2,Bn，各，各销地的销量分别为销地的销量分别为b1,b2,bn。n 假设从产地假设从产地Ai(i=1,2,m)向销地向销地Bj(j=1,2,n)运输单位物运输单位物品的运价是品的运价是cij，怎样调运，怎样调运这些物品才能使总运费最这些物品才能使总运费最小？小？运输问题的数学模型111111min.1,2,.,1,2,.,01,2,.,;1,2,.,mnijijijnijijmijjimnijijijZc xstxaimxbjnabxi

3、m jn，min.0Zcxs tAxdx2023-5-65运输问题数学模型的特点运输问题数学模型的特点1.运输问题有有限个最优解运输问题有有限个最优解2.运输问题约束条件的特点：运输问题的数学模型包含运输问题约束条件的特点：运输问题的数学模型包含mn个变量，个变量，(m+n)个约束方程，其系数矩阵的结构比个约束方程，其系数矩阵的结构比较松散且特殊。较松散且特殊。行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112112023-5-66运输问题的解运输问题的解运输问题也是一个线性规划问题，其求解时仍然运输问题也是一个线性规划问题，

4、其求解时仍然可以先找一个基可行解，进行解的最优性检验可以先找一个基可行解，进行解的最优性检验，若不是最优，就进行迭代，继续检验和调整，若不是最优，就进行迭代，继续检验和调整直到最优，因此要求每步得到的解都是基可行直到最优，因此要求每步得到的解都是基可行解，需满足解，需满足(1)满足所有约束条件；满足所有约束条件；(2)基变量基变量对应的系数列向量线性无关；对应的系数列向量线性无关；(3)解中非零变解中非零变量的个数不能大于量的个数不能大于m+n-1个，原因是运输问个，原因是运输问题中虽有题中虽有m+n个约束条件，但由于总产量等个约束条件，但由于总产量等于总销量，故只有于总销量，故只有m+n-1

5、个约束条件是线性个约束条件是线性独立的；独立的；(4)保持基变量的个数在迭代过程中保持基变量的个数在迭代过程中为为m+n-1个。个。2023-5-67二、表上作业法二、表上作业法表上作业法是单纯形法在求解运输问题时的一种简化表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法方法，其实质是单纯形法,但具体计算和术语有所不同但具体计算和术语有所不同，其步骤可归纳为：，其步骤可归纳为：(1)(1)找出初始基可行解：即在找出初始基可行解：即在(m(mn)n)产销平衡表上产销平衡表上用最用最小元素法或西北角法给出小元素法或西北角法给出m+n-1个数字，称为数字格个数字，称为数字格，它们

6、就是初始基变量的取值。，它们就是初始基变量的取值。(2)(2)求各非基变量的检验数，即在表上计算空格的检验求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。算，否则转到下一步。(3)(3)确定换入变量和换出变量，找出新的基可行解。在确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。表上用闭回路法调整。(4)重复重复(2)，(3)直到得到最优解为止。直到得到最优解为止。确定初始确定初始方案方案(初初 始始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否 判定

7、是否判定是否 最最 优？优？是是结结 束束最优方案最优方案运输问题求解思路图运输问题求解思路图（一）初始基本可行解的确定初始基本可行解的确定 例题有关信息表例题有关信息表 450 200 150 100 日销量（需求量）250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量）（供应量）C B A运距运距 城市城市煤矿煤矿;3,2,1;2,1,0200150100250200.7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxt sxxxxxxZij需求约束日产量约束总运输量（1）最小

8、元素法：从运价最小的格开始，在格）最小元素法：从运价最小的格开始，在格内标上允许取得的最大数。然后按运价从小到内标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。行下去，直至得到一个基本可行解。调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用

9、最小元素法确定初始调运方案用最小元素法确定初始调运方案 15010010010010010010038750100*100150*65100*100100*90总运价为：2023-5-615练习单位单位 销地销地 运价运价 产地产地产量产量311310719284741059销量销量3656产销平衡321AAA例：某食品公司下属的A1、A2、A3，3个厂生产方便食品，要运输到B1、B2、B3、B4，4个销售点，数据如下：用表上作业法求最初运输方案。4321 BBBB2023-5-616B1B2B3B4产量产量A17,3,0A2 4,1,0A39销量销量3,06,05,1,06,3,031131

10、0192741058341633总的运输费用（总的运输费用（3 31 1）（）（6 64 4）（）（4 43 3）（1 12 2）（）（3 31010）（）（3 35 5）8686元元（2 2）西北角法）西北角法不是优先考虑具有最小单位运价的供销业不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左务，而是优先满足运输表中西北角（左上角）上空格的供销要求上角）上空格的供销要求调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 15

11、0 200 450 用西北角法确定初始调运方案用西北角法确定初始调运方案 100100100 50 50200200 39250100*20065*50100*70100*90总运价为：（二）最优性检验最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解.思路：要判定运输问题的初始基可行解是否为最思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般单纯形法，检验这个解的各非优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数。基变量（对应于运输表中的空格）的检验数。

12、检验数检验数：运输问题中非基变量（对应于空格）的运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总费用检验数定义为给某空格增加单位运量导致总费用的增加量。的增加量。如果有某空格（如果有某空格（i、Bj）的检验数为负，说明将）的检验数为负，说明将Xij变为基变量将使运输费用减少，故当前这个变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负，解不是最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，即目则不管怎样变换，均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。标函数值已无法改进，这个解就是最优解。闭回路：

13、在给出的调运方案的运输表上，闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转字格才能向左或向右转90继续前进，直继续前进，直至最终回到初始空格而形成的一条回路。至最终回到初始空格而形成的一条回路。从每一空格出发，一定可以找到一条且只从每一空格出发，一定可以找到一条且只存在唯一一条闭回路存在唯一一条闭回路。、闭回路法、闭回路法以以xij空格为第一个奇数顶点，沿闭回路的顺空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个（或逆

14、）时针方向前进，对闭回路上的每个折点依次编号；折点依次编号；非基变量非基变量 xij 的检验数：的检验数：现在，在现在，在用最小元素法确定例用最小元素法确定例2初始调运方初始调运方案的基础上，案的基础上，计算非基变量计算非基变量X12的检验数的检验数：ij调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 45010010010015012212 2、对偶变量法（位势法）、对偶变量法（位势法）检验数公式：分别表示前m个约束等式对应的

15、对偶变量；分别表示后n个约束等式对应的对偶变量。jiijijvuc(1,2,)iu imL，(1,2,)jvjnL，初始调运方案对偶变量对应表初始调运方案对偶变量对应表 调调 销地销地 运运 量量产地产地 B1 B2 B3产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450对偶变量对偶变量vj v1 v2 v3100100100150对偶对偶变量变量 ui u1 u2iujv7565100902332222213311111cvucvucvucvu 这个时这个时候方程的解可以称为

16、位势。候方程的解可以称为位势。ij2023-5-633练习2023-5-634空格 闭 回 路 检验数(11)(12)(22)(24)(31)(33)(11)-(13)-(23)-(21)-(11)(12)-(14)-(34)-(32)-(12)(22)-(23)-(13)-(14)-(34)-(32)-(22)(24)-(23)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)1 2 1-1 10 12 （三）解的改进（三）解的改进闭回路调整法闭回路调整法如检验出初始解不是最优解，即某非基如检验出

17、初始解不是最优解，即某非基变量检验数为负，说明将这个非基变量变量检验数为负，说明将这个非基变量变为基变量时运费会下降。根据表上作变为基变量时运费会下降。根据表上作业法的第三步，需对初始方案进行改进。业法的第三步，需对初始方案进行改进。解改进的步骤解改进的步骤1（如存在多个非基变量的检验数为负时，以最（如存在多个非基变量的检验数为负时，以最小负检验数所在空格对应的变量）为换入变量，小负检验数所在空格对应的变量）为换入变量，找出它在运输表中的闭回路；找出它在运输表中的闭回路；2以这个空格为第一个奇数顶点，沿闭回路的顺以这个空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点

18、（或逆）时针方向前进，对闭回路上的每个折点依次编号；依次编号；3在闭回路的所有偶数折点中，找出运输量最小在闭回路的所有偶数折点中，找出运输量最小的一个折点，以该格中的变量为换出变量；的一个折点，以该格中的变量为换出变量；4将闭回路上所有奇数折点的运输量都增加这一将闭回路上所有奇数折点的运输量都增加这一换出变量值，所有偶数折点处的运输量都减去这换出变量值，所有偶数折点处的运输量都减去这一数值，最终得出一个新的运输方案。一数值，最终得出一个新的运输方案。对得出的新方案再进行最优性检验，如不是最优对得出的新方案再进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出解，就重复以上步骤继

19、续进行调整，一直到得出最优解为止。最优解为止。调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150+-020050100 调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 45034250100100200 50调调 销地销地 运运 量量产

20、地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450150 50200 502023-5-642练习练习 销产B1B2B3B4产量A241241116A22103910A38511622销量8141214482023-5-644（四）产销不平衡的运输问题（四）产销不平衡的运输问题 前面所讲表上作业法，都是以产销平衡为前提条件的，但是实际问题中产销往往是不平衡的，这就需要设法把产销不平衡的问题化成产销平衡的问题。1、总产量大于总销量总产量大于总销量即此时，

21、运输问题的数学模型可写为minjjiba112023-5-645 )(0min11ijjijijiijminjijijxbabxaxxcZ要求解此问题，需要先将原问题变成平衡问要求解此问题，需要先将原问题变成平衡问题，可以假设一个销地题，可以假设一个销地Bn+1(即实际问题中考即实际问题中考虑产地的存量虑产地的存量)，即：，即：2023-5-646 0)min1111111ijminjnjjnjijijnjiijijijxbbbabxaxxcZm1i(01,nic单位运价表中的单位运价单位运价表中的单位运价2、销大于产：、销大于产：同样假设一个产地即可，变化同上。同样假设一个产地即可，变化同上

22、。B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5 A121134070A210359050A378120702030406040例题：例题：（五）需要说明的几个问题（五）需要说明的几个问题 无穷多最优解：产销平衡的运输问题必定存在最无穷多最优解：产销平衡的运输问题必定存在最优解。如果非基变量的优解。如果非基变量的ij0，则该问题有无穷多最，则该问题有无穷多最优解。优解。退化：表格中一般要有退化：表格中一般要有(m+n-1)个数字格。但有时，个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需在分配运量时则需要同时划去一行和一列

23、，这时需要补一个要补一个0，以保证有，以保证有(m+n-1)个数字格。一般可在个数字格。一般可在划去的行和列的任意空格处加一个划去的行和列的任意空格处加一个 0 即可。即可。在用闭回路法调整时，在闭回路上出现两个或两在用闭回路法调整时，在闭回路上出现两个或两个以上的具有个以上的具有(-)标记的相等的最小值。这时只能选标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。择其中一个作为调入格。而经调整后，得到退化解。这时另一个数字格必须填入一个这时另一个数字格必须填入一个0，表明它是基变量。，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回当出现退化解后，并作改

24、进调整时，可能在某闭回路上有标记为路上有标记为(-)的取值为的取值为0的数字格，这时应取调整的数字格，这时应取调整量量=0。三、具有特殊调度约束的运输问题三、具有特殊调度约束的运输问题供给量约束供给量约束比如，某个供应商给某个需求方的供应量不超过百分之几。中转运输问题中转运输问题增加几个配送中心（或者物流网点），但是限制其吞吐能力。6B6B 226B6B 222B1B2B3B4供给量A116132217500A214131915600A319202310400需求量5007003002002023-5-663B1B2B3B4产量产量A1500500A2 400 200600400A310030

25、0400A40 200200销量销量500100700200300200170016132217141319192023M15M+1412230MM0M-4M-1912023-5-664单位单位 销地销地 运价运价产地产地B1B2B3B4产量产量A1291029A213425A384257销量销量384621A1A2A3A1013A210MA33M0B1B2B3B4B10142B21021B34203B421302023-5-666B1B2B3B4产量产量A13693A2 3252A33473销量销量384621291021348425233-56862023-5-667B1B2B3B4产量产量A1369A2 055A3347销量销量3846212910213484252835631阅读推荐1 1、物流工程物流工程，齐二石，方庆，齐二石，方庆琯琯.机械工业出版机械工业出版社，社，20062006。2 2、运筹学运筹学