运筹学胡运权第3章课件

1、第三章 运输问题Transportation Problem3.1 运输问题的典例和数学模型例例 某食品公司经营糖果业务，公司下设三个加工厂某食品公司经营糖果业务，公司下设三个加工厂A A1 1、A A2 2、A A3 3，四个销售门市部，四个销售门市部B B1 1、B B2 2、B B3 3、B B4 4。已知每天各自的生。已知每天各自的生产量、销售量及调运时的单位糖果的运输费用等情况。产量、销售量及调运时的单位糖果的运输费用等情况。问：如何调运可使总费用最小？问：如何调运可使总费用最小？生产量：生产量：A A1 177吨，吨，A A2 244吨，吨，A A3 399吨吨销售量：销售量：B

2、B1 133吨，吨，B B2 266吨，吨，B B3 355吨，吨，B B4 466吨吨加工厂加工厂单位运价单位运价门市部门市部B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5单位：元单位：元/ /吨吨解：用解：用cij表示从第表示从第i个加工厂到第个加工厂到第j个门市部的单位糖果的运价，个门市部的单位糖果的运价， 设设xij表示第表示第i个加工厂到第个加工厂到第j个门市部调运糖果的数量，个门市部调运糖果的数量， （i=1=1，2 2，3 3；j=1=1，2 2，3 3，4 4）则总费用为：则总费用为：min z = cijxij34i=1j=1x11

3、+x12+x13+x14=7x11+x21+x31=3xij 0,(i=1,2, 3；j=1,2,3,4)产量限制产量限制销量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6s.t.1、运输问题产量产量 每个产地提供物资的数量，用每个产地提供物资的数量，用a1, a2, , am 表示；表示；销量销量 每个销地需要物资的数量，用每个销地需要物资的数量，用b1, b2, , bn 表示；表示；单位物资运价单位物资运价 从产地从产地i到销地到销地j单位物资的运价为单位物资的运价为cij一般

4、满足产销平衡：一般满足产销平衡：与物资调运有关的问题。与物资调运有关的问题。2、已知条件11mnijijab已知条件的表格形式已知条件的表格形式单单 销销 价价 地地产地产地产产量量销销 量量平衡平衡nBB 1mAA 1maa 1nbb 1mnmncccc 1111产销平衡表产销平衡表单位运价表单位运价表本例中：本例中： , 2 , 1, 2 , 10)( , 2 , 1)( , 2 , 1. .min1111njmixnjbxmiaxtsxczijjmiijnjiijminjijij，销量约束产量约束对于对于m m产产n n销销运输问题运输问题，设设xij表示产地表示产地 i 运往销地运往销

5、地 j 的物资的物资数量，则数量，则其其数学模型如下：数学模型如下：3、运输问题的数学模型注：运输问题是特殊的线性规划问题。注：运输问题是特殊的线性规划问题。4、模型的特点已知运输问题有已知运输问题有m m个产地、个产地、n n个销地，个销地，（1 1）决策变量的个数：）决策变量的个数：m n（2 2）约束方程的个数：）约束方程的个数：m+n 其中独立方程的个数：其中独立方程的个数：m+n-1 基变量的个数：基变量的个数：m+n-1 非基变量的个数：非基变量的个数：mn-(m+n-1)x11 x12 x1n x21 x22 x2n , , xm1 xm2 xmn1 1 1 0 0 0 0 0

6、00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1i=1i=2i=mj=1j=2j=n（3 3）系数矩阵：）系数矩阵：5 5、运输问题解的情况、运输问题解的情况运输问题有最优解运输问题有可行解产销平衡 3.2 表上作业法初始调运方案初始调运方案的确定的确定是否最优？结束结束Y调整方案调整方案使目标函数值更小使目标函数值更小N基本原理：基本原理：2-12-1 初始方案的确定初始方案的确定1 1、 最小元素法最小元素法销地销地3 311113 310101 19 92 28 8

7、7 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 例例 用最小元素法确定初始方案。用最小元素法确定初始方案。865310334214613 Z就近供应就近供应“找便宜找便宜”有多少有多少要多少要多少运多少运多少销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 得到初始调运方案表：得到初始调运方案表：（1 1） 有数字格（基格）有数字格（基格） 填写了调运量的格子，对应填写了调运量的格子，对应解

8、中的基变量。（用白圈表示）解中的基变量。（用白圈表示）（2 2） 空格空格 未填写调运量的格子，对应解中的非基变未填写调运量的格子，对应解中的非基变量，其对应变量在该方案中取值为量，其对应变量在该方案中取值为0。（用蓝圈表示）。（用蓝圈表示）在调运方案表中，在调运方案表中，12个格子分成两类：个格子分成两类：例例 用最小元素法确定初始方案。用最小元素法确定初始方案。注意：注意： 在调运方案表中，每次填入一个数字，都在在调运方案表中，每次填入一个数字，都在满足供需关系下划去相应的一列或一行。满足供需关系下划去相应的一列或一行。 若填入的一个数字既满足产量要求又满足销若填入的一个数字既满足产量要求

9、又满足销量要求，则应同时划去这一列和这一行，并在划去量要求，则应同时划去这一列和这一行，并在划去的所在列或行的任一个空格内填入一个的所在列或行的任一个空格内填入一个0 0，以保持，以保持有数字格的总数不变（即基变量的个数不变）。有数字格的总数不变（即基变量的个数不变）。2. 2. 沃格尔法（沃格尔法（Vogel）销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 401101225132-1301-2-1201-2-1- 85538335461132 Z例例每行两个最每

10、行两个最小元素之差小元素之差每列两个最每列两个最小元素之差小元素之差“找大差找大差”注意：由沃格尔法得出的解比最小元素注意：由沃格尔法得出的解比最小元素法得出的解更接近最优解。法得出的解更接近最优解。2-2 最优性检验与方案的调整1 1、闭回路的概念、闭回路的概念在调运方案表中以一个空格和若干个有数字格作为顶点，以及在调运方案表中以一个空格和若干个有数字格作为顶点，以及水平、垂直连线围成的封闭回路，称为该空格对应的闭回路。水平、垂直连线围成的封闭回路，称为该空格对应的闭回路。销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1

11、A2bjB13 3产地产地A36 65 59 96 64 4 例如例如 分别找出下列空格的闭回路。分别找出下列空格的闭回路。销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 销地销地3 311113 310101 19 92 28 87 74 410105 520206 65 59 96 64 4A1A2bjB13 3产地产地A3aiB2B37 7B4 空格（空格（A A1 1,B,B1 1）的闭回路）的闭回路销地销地3 311113 310101 19 92 2

12、8 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A2 2,B,B2 2）的闭回路）的闭回路 销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A1 1,B,B2 2）的闭回路）的闭回路销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96

13、64 4 空格（空格（A A2 2,B,B4 4）的闭回路）的闭回路销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A3 3,B,B1 1）的闭回路）的闭回路销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A3 3,B,B3 3）的闭回路）的闭回路注意：调运表中每个空格有且只有一个闭回路。注意：调运

14、表中每个空格有且只有一个闭回路。2、利用闭回路计算检验数 令空格令空格（Ai,Bj）对应的非基变量的值对应的非基变量的值为为1 1，沿着闭沿着闭回路，相应顶点的基变量的回路，相应顶点的基变量的值依次值依次-1-1，+1+1，-1-1，+1+1，得到新可行解。得到新可行解。 将新可行解与原可行解相比，得到的将新可行解与原可行解相比，得到的运费变化量运费变化量称为该空格处的检验数，记做称为该空格处的检验数，记做ij。即即偶奇ijijijcc例例 求下列调运方案表中各个空格的检验数。求下列调运方案表中各个空格的检验数。销地销地3 311113 310101 19 92 28 87 74 410105

15、 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 1)31()23(11 销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 销地销地3 311113 310101 19 92 28 87 74 410105 520206 65 59 96 64 4A1A2bjB13 3产地产地A3aiB2B37 7B4 空格（空格（A A1 1,B,B1 1）的闭回路）的闭回路表示新方案的费用要增加表示新方案的费用要增加1 1元元

16、销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A2 2,B,B2 2）的闭回路）的闭回路1)2104()359(22 表示新方案的费用要增加表示新方案的费用要增加1 1元元 销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A1 1,B,B2 2）的闭回路）的闭回路2)104()511(12 表示新

17、方案的费用要增加表示新方案的费用要增加2 2元元销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A3 3,B,B1 1）的闭回路）的闭回路10)135()2107(31 表示新方案的费用要增加表示新方案的费用要增加1010元元销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A3 3,B,B3 3）的

18、闭回路）的闭回路12)35()1010(33 表示新方案的费用要增加表示新方案的费用要增加1212元元销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4 空格（空格（A A2 2,B,B4 4）的闭回路）的闭回路1)102()38(24 表示新方案的费用要减少表示新方案的费用要减少1 1元元综上，得到检验数表如下：综上，得到检验数表如下：B1B2B3B4A11200A20101A3100120注意：有数字格（基变量）的检验数为注意：有数字格（基变量）的检验数为0 0

19、。B1B2B3B4A10200A20210A390120销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2bjB13 3产地产地A36 65 59 96 64 4例例 已知运输问题的调运方案如下，已知运输问题的调运方案如下，用闭回路法求检验数表用闭回路法求检验数表。解：检验数表为解：检验数表为3、利用检验数表判断最优性解。解。时，运输问题达到最优时，运输问题达到最优当所有当所有最优性判别准则：最优性判别准则：0 ij（1 1）若有负检验数，则该方案需要改进；）若有负检验数，则该方案需要改进；（2 2）若空格的检验数全为正

20、数，则该问题有唯）若空格的检验数全为正数，则该问题有唯一最优方案；一最优方案；（3 3）若检验数全非负，且有空格的检验数为）若检验数全非负，且有空格的检验数为0 0，则该问题有无穷多最优解。则该问题有无穷多最优解。 在检验数表中，确定绝对值最大的负检在检验数表中，确定绝对值最大的负检验数对应的空格，利用该空格的闭回路在满足验数对应的空格，利用该空格的闭回路在满足供需关系下调整各顶点的运量，得到费用更小供需关系下调整各顶点的运量，得到费用更小的调运方案。的调运方案。4、改进方案的方法-闭回路法例调整方法：调整方法：销地销地3 311113 310101 19 92 28 87 74 410105

21、 5A1A2A3B1产地产地B2B3B4 121-11012（1 1）找出绝对值最大的负检验数对应的闭回路）找出绝对值最大的负检验数对应的闭回路（2 2）使所对应的空格达到最大的调整量）使所对应的空格达到最大的调整量1 1 242313141,0,5,2xxxx此时此时x23=0，可看成非基变量。可看成非基变量。注：格子右上角注：格子右上角数字为单位物资数字为单位物资运价，左下角数运价，左下角数字为检验数，圆字为检验数，圆圈内数字为调运圈内数字为调运物资数量。物资数量。销地销地3 311113 310101 19 92 28 87 74 410105 52020aiB2B37 7B4A1A2b

22、jB13 3产地产地A36 65 59 96 64 4 得到新的调运方案：得到新的调运方案：该方案就是用沃格尔法得到的初始方案。该方案就是用沃格尔法得到的初始方案。B1B2B3B4A10200A20210A390120其检验数表为其检验数表为故该方案为最优方案，且有无穷多最优方案，故该方案为最优方案，且有无穷多最优方案，Zmin=85=85元。元。5、用位势法求检验数（2 2）计算行位势）计算行位势ui和列位势和列位势vj 不妨令不妨令u u1 1=1=1，则依，则依cij=ui+vj 计算各计算各ui和和vj （3 3）计算空格处位势和）计算空格处位势和ui+vj（4 4）计算空格处检验数）

23、计算空格处检验数ij=cij -（ui+vj）（1 1）列一张只含有数字格单位运价）列一张只含有数字格单位运价cij的表；的表；注意：注意： 行位势、列位势可能不唯一，但检验数是相同的。行位势、列位势可能不唯一，但检验数是相同的。 产地销地A1 A2 A3B1 B1 B3 B4 3 10 1 8 4 5 (3)(9)(7)(-2)(1)(-2)行位势列位势 12-1-4289销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 产地单位运价表单位运价表位势表位势表产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 6635213

24、调运方案表调运方案表A1 A2 A3B1 B1 B3 B40229112检验数表检验数表ijB1B2B3B4A10200A20210A390120检验数表：检验数表：故该方案为最优方案，且该问题有无穷多最优方案。故该方案为最优方案，且该问题有无穷多最优方案。 总费用总费用Zmin=85元。元。2-3 小结（1 1）分析问题，列出产销平衡表和单位运价表。分析问题，列出产销平衡表和单位运价表。（2 2）利用最小元素法或沃格尔法求初始调运方案。）利用最小元素法或沃格尔法求初始调运方案。 注：沃格尔法是近似最优解。注：沃格尔法是近似最优解。（3 3）用闭回路法或位势法求检验数表。）用闭回路法或位势法求

25、检验数表。 注：位势法比较简单。注：位势法比较简单。（4 4）判断最优性）判断最优性 若无负检验数，则该方案为最优方案，计算相若无负检验数，则该方案为最优方案，计算相应的总运费，结束；应的总运费，结束； 否则，利用绝对值最大的负检验数对应的闭回否则，利用绝对值最大的负检验数对应的闭回路调整方案，并转入（路调整方案，并转入（3 3）。）。1 1、表上作业法的前提：产销平衡、表上作业法的前提：产销平衡2 2、表上作业法的步骤、表上作业法的步骤已知某运输问题的资料如下表：已知某运输问题的资料如下表：B B1 1B B2 2B B3 3B B4 4发量发量A A1 12 26 65 53 31515A

26、 A2 21 13 32 21 11212A A3 33 32 27 74 41313收量收量1010131312125 5 表中的发量、收量单位为：吨，运价表中的发量、收量单位为：吨，运价单位为：元单位为：元/ /吨，吨， 试求出最优运输方案。试求出最优运输方案。 例例解：解：1 1、用最小元素法求初始方案、用最小元素法求初始方案B1B2B3B4发量发量A1012315A210212A31313收量收量1013125 用沃格尔法求初始方案用沃格尔法求初始方案B1B2B3B4发量发量A1100515A21212A301313收量收量1013125总费用总费用z z=107=107元元总费用总费

27、用z z=85=85元元B1B2B3B4A15A2251A3102 2、用位势法求由沃格尔法得到的方案的检验数、用位势法求由沃格尔法得到的方案的检验数3 3、结论：、结论： 表中无负检验数且有非基变量的检验数表中无负检验数且有非基变量的检验数为为0 0，本问题有无穷多最优方案。，本问题有无穷多最优方案。一个最优调运方案为：一个最优调运方案为：B1B2B3B4发量发量A1100515A21212A301313收量收量1013125综上所述，综上所述，总费用总费用Zmin=85元。3.3 产销不平衡的运输问题及其应用一、原理一、原理 njjmiiijjmiijinjijbanjmixbxax1111), 1;, 1( , 000有解的充要条件是：有解的充要条件是：定理：方程组定理：方程组。则虚设一个销地销）若产（111),( 1nnjjmiiBba。则虚设一个产地销）若产（111),( 2mnjjmiiAba1110mnnijijBab该销地的销量为，各产地至该销地的单位物资运价为 。注：该销地的作用相当于多余物资就地库存。注：该销地的作用相当于多余物资就地库存。1110MnmmjijiAba该产地的产量为，该产地至各销地的单位物资运价为 或。注：当销地需要刚性物资时，相应单价为注：当销地需要刚性物资时，相应单价为M M； 当销地需要弹性物资时，相应单价为当销地需要弹性物资时