运筹学-3运输问题

1、统计学院统计学院运筹学第三章运筹学第三章运输问题运输问题张张 红红 历历本章内容4.4.应用问题举例应用问题举例3.3.运输问题的进一步讨论运输问题的进一步讨论2.2.表上作业法表上作业法1.1.运输问题及其数学模型运输问题及其数学模型第一节第一节 运输问题及其数学模型运输问题及其数学模型一、运输问题的提出例：某运输问题的资料如下：例：某运输问题的资料如下：单位单位 销地销地 运价运价产地产地产量产量2910291342584257销量销量38464321 BBBB321AAA21 二、数学模型的一般形式 1. 已知资料如下：已知资料如下：p 设某种物品有设某种物品有m m个产地个产地A A1

2、 1，A A2 2，A Am m，产量，产量 分别是分别是 a a1 1，a a2 2，a am m个单位个单位p 有有n n个销地个销地B B1 1，B B2 2，B Bn n，销量分别为，销量分别为b b1 1， b b2 2，b bn n个单位；个单位；p 从从A Ai i 到到B Bj j运输单位物品运输单位物品 的运价是的运价是c cijij；2. 运输问题的几种类型：p 产销平衡问题产销平衡问题p 产销不平衡问题产销不平衡问题u 产大于销产大于销u 销大于供销大于供p当产销平衡时，其模型如下：当产销平衡时，其模型如下：p当产大于销时，其模型是：当产大于销时，其模型是： ) ( 0m

3、in11ijjijijiijminjijijxbabxaxxcZp 当销大于产时，其模型是：当销大于产时，其模型是：0, 0, 0)(0min ijjijjiijjijiijijijcbabaxbxaxxcZ并假设：并假设： 三、运输问题数学模型的特点 （1 1）运输问题有有限最优解。）运输问题有有限最优解。 定理定理. . 运输问题有可行解的充要条件运输问题有可行解的充要条件 是：产销平衡是：产销平衡 njjmiiba11其中其中：（2）运输问题约束条件的系数矩阵记变量记变量x xijij对应对应A A中向量为中向量为 A Aij ij Aij=0. 1 .0. 1.0第第 i分量分量第第

4、m+j分分量量矩阵的元素均为矩阵的元素均为1 1或或0 0； 每一列只有两个元素为每一列只有两个元素为1 1，其，其余元素均为余元素均为0 0； 列向量列向量P Pijij =(0, =(0,，0 0，1 1，0 0，,0,1,0,0,1,0,0)T0)T，其中两，其中两个元素个元素1 1分别处于第分别处于第i i行和第行和第m+jm+j行。行。 将该矩阵分块，特点是：将该矩阵分块，特点是：前前m m行构成行构成m m个个m mn n阶矩阵，而阶矩阵，而且第且第k k个矩阵只有第个矩阵只有第k k行元素全行元素全为为1 1，其余元素全为，其余元素全为0 0（k=1k=1，m m）；后）；后n

5、n行构成行构成m m个个n n阶单位阵。阶单位阵。（3）运输问题的解定义定义1. 1. 闭回路闭回路 闭回路是能折成闭回路是能折成 形式的变量组集合。其中形式的变量组集合。其中 i1 , i2 , ， is 互不相同，互不相同，j1 , j2 , ， js 互不相互不相同。每个变量称为同。每个变量称为闭回路的顶点闭回路的顶点，连接闭回路相邻两顶点的直线段叫做，连接闭回路相邻两顶点的直线段叫做闭闭回路的边回路的边。xxxxxxisjisjsjijijiji132222111,.,例：例：x11，x12，x32，x34，x24，x21 就是一个闭回路。就是一个闭回路。B1 B2 B3 B4A1A2

6、A3x11x12x21x32x24x34闭回路的特点：1.每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的；每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的；2.每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向；每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向；3.每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数；每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数；4.从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻 顶点，如此继续下去，

7、经过闭回路的所有顶点和边，最后又回到开始的顶点，顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点， 但每一定和边在闭回路中只经过一次。但每一定和边在闭回路中只经过一次。B1 B2 B3 B4A1A2A3x11x12x21x32x24x34有关闭回路的一些重要定理有关闭回路的一些重要定理 132222111,jijijijijijisssxxxxxx132222111,jijijijijijisssPPPPPP0132222111 jijijijijijisssPPPPPP定理定理2:2: 若变量组若变量组中有一个部分组构成闭回路，则该变量组对应中有一个部分组构成闭回路，则该变

8、量组对应的系数列向量线性相关。的系数列向量线性相关。rrjijijixxx,2211定理定理3 3 r r个变量个变量 对对应的系数列向量线性无关应的系数列向量线性无关充要条件充要条件是该变量组是该变量组不包不包含闭回路。含闭回路。rrjijijixxx,2211 推论：推论：m+n-1 m+n-1 个个变量变量 构成基的充要条件是它不含闭回路。构成基的充要条件是它不含闭回路。xxxnmnmjijiji112211, 第二节第二节 表上作业法表上作业法一、表上作业法的基本思想寻找初始基本可行解寻找初始基本可行解给出基本可行解为最优解的判别准则给出基本可行解为最优解的判别准则给出从目前基本可行解

9、转移到新基本给出从目前基本可行解转移到新基本 可行解的方法可行解的方法ReviewReview Step4. .重复重复2. 32. 3，直到找到最优解为止。，直到找到最优解为止。二、表上作业法的步骤 Step1. .找出初始基本可行解（在找出初始基本可行解（在m m* *n n产销平衡产销平衡表上寻找初始调运方案，一般表上寻找初始调运方案，一般m+n-1m+n-1个数字格），个数字格），用最小元素法、西北角法、伏格尔法；用最小元素法、西北角法、伏格尔法； Step2. .求出各非基变量的检验数，判别是否求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，达到最优解。如

10、果是停止计算，否则转入下一步，用闭回路或位势法计算；用闭回路或位势法计算； Step3. .改进当前的基本可行解（确定换入、改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；换出变量），用闭合回路法调整； 1.求初始方案（寻找初始基可行解）求初始方案（寻找初始基可行解）Step1.Step1. 选择一个选择一个x xijij， 对对x xijij的选择采用不同的规则就形成各种不的选择采用不同的规则就形成各种不同的方法同的方法，比如每次总是在作业表剩余的格子中，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的选择运价（或运距）最小者对应的x xijij，则构成，则构成最

11、最小元素法小元素法，若每次都选择，若每次都选择左上角格子左上角格子对应的对应的x xijij就就形成形成西北角法西北角法（也称（也称左上角法左上角法）。）。 Step2.Step2. 调整产销剩余数量：调整产销剩余数量：从从a ai i和和b bj j中分别减去中分别减去x xijij的值，若的值，若a ai i-x-xijij=0=0，则划去产地，则划去产地A Ai i所在的行，即该产所在的行，即该产地产量已全部运出无剩余，而销地地产量已全部运出无剩余，而销地B Bj j尚有需求缺口尚有需求缺口b bj j- -a ai i；若；若b bj j-x-xijij =0 =0，则划去销地，则划去

12、销地B Bj j所在的列，说明该销所在的列，说明该销地需求已得到满足，而产地地需求已得到满足，而产地A Ai i尚有存余量尚有存余量a ai i-b-bj j； Step3.Step3.当作业表中当作业表中所有的行或列均被划去所有的行或列均被划去，说明所说明所有的产量均已运到各个销地，需求全部满足，有的产量均已运到各个销地，需求全部满足，x xijij的取的取值构成初始方案。否则，在作业表剩余的格子中选择值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（下一个决策变量，返回步骤（2 2）。）。 按照上述步骤产生的一组按照上述步骤产生的一组变量必定不构成闭变量必定不构成闭回

13、路回路，其取值非负，且，其取值非负，且总数是总数是m+n-1m+n-1个个，因此构成，因此构成运输问题的基本可行解运输问题的基本可行解。 p 从单位运价表中选最小元素，然后比较从单位运价表中选最小元素，然后比较产量和销量，产量和销量，如果产如果产 销，则划去列，若销销，则划去列，若销 产，则划去行；产，则划去行；p 修改修改a ai i或或b bj j的值；的值；p 再从划去一列和一行后的单位运价表中再从划去一列和一行后的单位运价表中找最小元素，找最小元素，继续下去；，继续下去；p 直到单位运价表的所有元素划去为止。直到单位运价表的所有元素划去为止。步步 骤：骤：就近供应。就近供应。按单位运价

14、的大小决定供按单位运价的大小决定供应的先后，优先满足单位运价最小者应的先后，优先满足单位运价最小者的供销要求。的供销要求。基本思想基本思想 ：最小元素法最小元素法单位单位 销地销地 运价运价 产地产地产量产量311310719284741059销量销量36564321 BBBB321AAA例例3 3124433 436供供销销 B1 B2 B3 B4 产量产量A1A2A3销量销量3113101794210853 6 5 6 74911865346211310334 Z353366西北角法西北角法基本思想：基本思想： 优先满足运输表中左上角（即西北优先满足运输表中左上角（即西北角）空格的供销要求

15、。角）空格的供销要求。3 34142222 433566供供销销 B1 B2 B3 B4 产量产量A1A2A3销量销量3113101794210853 6 5 6 749663213556103229211433 Z伏格尔法（伏格尔法（Vogel Vogel 逼近法逼近法. VAM. VAM） 最小元素法的缺点：最小元素法的缺点：为了节省一处的费用，有时造成在为了节省一处的费用，有时造成在其它处要多花几倍的运费。其它处要多花几倍的运费。若不能按最小运费就近供应，就若不能按最小运费就近供应，就选择次最小运费，差额越大，说明不能按最小运费调运时，选择次最小运费，差额越大，说明不能按最小运费调运时，

16、运费增加越多。运费增加越多。 每行（列）中次最小价格元素与最小价格元素的数值之差，每行（列）中次最小价格元素与最小价格元素的数值之差，称为该行（列）的行（列）称为该行（列）的行（列）罚数罚数最大差额费用最大差额费用。 对罚数最大处，采用最小运费调运。对罚数最大处，采用最小运费调运。在求一个可行解的过程中注意到包含在矩阵模型中在求一个可行解的过程中注意到包含在矩阵模型中的成本信息。它通过建立的成本信息。它通过建立“罚数罚数”来达到此目的。来达到此目的。罚数表示对一方格不进行分配的可能的成本罚款。罚数表示对一方格不进行分配的可能的成本罚款。步 骤：Step1.Step1. 给定一个平衡的运输矩阵，

17、分别计算行罚数和列罚数；给定一个平衡的运输矩阵，分别计算行罚数和列罚数；Step2.Step2. 确定具有确定具有最大罚数最大罚数的行或列，然后在罚数所在行（或的行或列，然后在罚数所在行（或 列）中选择列）中选择最小价格最小价格元素，将可能的最大单位数分配元素，将可能的最大单位数分配 给此方格，将相应的行（或列）的供应量和需求量减给此方格，将相应的行（或列）的供应量和需求量减 去这个量，并划去完全满足的行（或列）；去这个量，并划去完全满足的行（或列）；Step3Step3. . 重复重复step1step1，step2step2，直到给出初始解为止。，直到给出初始解为止。例例见下页！见下页！0

18、 11供供销销 B1 B2 B3 B4 产量产量 行罚数行罚数 A1A2A3销量销量3113101794210853 6 5 6 20 749列列 罚罚 数数 2 5 1 3 60 12 2 1 3 13012 1 232376 1 2 00 2331152267542Z=5 3+2 10+3 1 +1 8+6 4+ 3 5 = 852. 解的最优性检验（1 1）闭回路法）闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。作为起始顶点，寻求闭回路。 该闭回路的特点是：该闭回路的特点是：除了起始顶点是非基变量外

19、，其他顶除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。变量而言，以其为起点的闭回路存在且唯一。n 判别的方法是计算空格判别的方法是计算空格( (非基变量非基变量) )的检验数，的检验数，因运输问题的目标函数是要求实现最小化，故当所因运输问题的目标函数是要求实现最小化，故当所有的检验数有的检验数0 0时，为最优解。时，为最优解。n 常用两种求空格检验数的方法为：闭回路法和常用两种求空格检验数的方法

20、为：闭回路法和位势法。位势法。ij= =（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）- -（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和） ccccccujuslslkikijij xujxijxlkxlsxusxik检验数检验数 对调运方案中每一空格按闭回路法求出检验数对调运方案中每一空格按闭回路法求出检验数 若所有检验数大于等于零若所有检验数大于等于零，则此方案为最优方案；，则此方案为最优方案； 若存在若存在检验数小于零，检验数小于零，则需对此方案进行调整。则需对此方案进行调整。供供销销 B1 B2 B3 B4 产量产量A1A2A3销量销

21、量3113101794210853 6 5 6 749 364133112332123131111 cccc 124510113234141212 cccc 21451032932341413232222 cccccc 11231082313142424 cccc -110510321734141323213131 cccccc 10123105101314343333 cccc 12不是最优解不是最优解此种此种颜色颜色代表代表检验检验数数经济含义经济含义：在保：在保持产销平衡的条持产销平衡的条件下，该非基变件下，该非基变量增加一个单位量增加一个单位运量而成为基变运量而成为基变量时量时目标函数

22、值目标函数值的变化量的变化量。（2 2）对偶变量法（位势法）对偶变量法（位势法）定理：任何基可行解对应的方程组都有解。定理：任何基可行解对应的方程组都有解。 cvucvucvunmnmnmnmjijijijijiji111122221111 运输问题的基可行解运输问题的基可行解 在这一组基变量下，建立求解在这一组基变量下，建立求解ui，vj的方程组：的方程组：TjijijinmnmxxxX),(112211 位势位势：方程组的任意一组解叫做位势方程组的任意一组解叫做位势。 对于运输问题的一个基可行解对于运输问题的一个基可行解，用位势法得用位势法得到的检验数是唯一的到的检验数是唯一的（位势可能不

23、同位势可能不同）。对基变量对基变量，反复利用公式反复利用公式 jijiiijjvcuucv jiijijvuc 求出空格的检验数求出空格的检验数。求出位势后求出位势后，就可由公式就可由公式B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表成本表CijB1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令：令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+vj) 按按ij=cij(ui+vj) 计算检验数，并

24、以计算检验数，并以ijij0 0 检验，或检验，或用用(ui+vj) cij 0 检验。检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120表中还有负数，表中还有负数，说明还未得到最说明还未得到最优解，应继续调优解，应继续调整。整。ij0-1-5121 -11012此种此种颜色颜色代表代表检验检验数数10311310179421085供供销销 B1 B2 B3 B4 uiA1A2A3 Vj 364133此种此种颜色颜色代表代表初始初始解解2933. 3

25、. 解的改进解的改进闭回路调整法闭回路调整法当当 ijij 0 0 时，调运方案需要改进时，调运方案需要改进00minjiijijo min 下下调调顶顶点点的的调调整整量量 121 -11012311310179421085供供销销 B1 B2 B3 B4 aiA1A2A3 bj 3641337493 6 5 6(-1)(+1)(-1)(+1)闭回路的偶闭回路的偶数顶点的最数顶点的最小值小值偶次顶点偶次顶点 “ “调整量调整量”；奇次顶点；奇次顶点 “ “ + +调整量调整量”供供销销 B1 B2 B3 B4 uiA1A2A3 Vj3113101794210853 9 3 10 0-2-5

26、36 5123022 1 912 ij 0 得到最优解得到最优解4. 4. 几点说明几点说明（1 1） 换入变量的选择换入变量的选择 若运输问题的某一基可行解有多个非基变量的检验若运输问题的某一基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取入变量均可使目标函数值得到改善，但通常取 ijij 0总销量总销量供供销销 B1 B2 B3 B4 产量产量A1A1A2销量销量2 43M21453 60M10 4 6 5 6 5 7 332244M0A3A3 4 3 在下列不平衡运输问题中

27、，已知三个收点的需求量一在下列不平衡运输问题中，已知三个收点的需求量一旦不能满足，就要承担缺货损失费。单位物资的缺货损失旦不能满足，就要承担缺货损失费。单位物资的缺货损失费分别为费分别为4 4、3 3 和和 7,7,试建立运输模型。试建立运输模型。供供销销 B1 B2 B3 产量产量A1A2销量销量4 52683 8 7 14 1015例例8 8供供销销 B1 B2 B3 产量产量A1A2A3销量销量4 5264833 7 8 7 14 1015 4解：解：增加虚拟产地增加虚拟产地 A3航线航线 起点城市起点城市 终点城市终点城市 每天航班数每天航班数 1 E D 3 2 B C 2 3 A F 1 4 D B 1 某航运公司承担六个港口城市某航运公司承担六个港口城市A A、B B、C C、D D、E E、F F的的四条固定航线的物资运输任务。已知四条固定航线的物资运输任务。已知(1)(1)各条航线的起各条航线的起点、终点城市及每天航班数（表点、终点城市及每天航班数（表1 1）;(2);(2)各城市间的航各城市间的航行时间（表行时间（表2 2）；（）；（3 3）所有航线都使用同一种