运筹学第三版之第三章运输问题.ppt

《运筹学第三版之第三章运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学第三版之第三章运输问题.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运输问题运输问题运输问题运输问题(Transportation Problem)(Transportation Problem)是一类特殊的线性是一类特殊的线性是一类特殊的线性是一类特殊的线性规划问题规划问题规划问题规划问题.最早研究这类问题的是美国学者希奇柯克最早研究这类问题的是美国学者希奇柯克最早研究这类问题的是美国学者希奇柯克最早研究这类问题的是美国学者希奇柯克(Hitchcock)(Hitchcock)，后来由柯普曼，后来由柯普曼，后来由柯普曼，后来由柯普曼(Koopman)(Koopman)详细加以讨论。详细加以讨论。详细加以讨论。详细加以讨论。在第一章线性规划模型的应用中，我们介绍

2、了运输问在第一章线性规划模型的应用中，我们介绍了运输问在第一章线性规划模型的应用中，我们介绍了运输问在第一章线性规划模型的应用中，我们介绍了运输问题，建立了其数学模型，这类问题属线性规划问题，题，建立了其数学模型，这类问题属线性规划问题，题，建立了其数学模型，这类问题属线性规划问题，题，建立了其数学模型，这类问题属线性规划问题，当然可以使用单纯形法进行求解，但是，由于运输问当然可以使用单纯形法进行求解，但是，由于运输问当然可以使用单纯形法进行求解，但是，由于运输问当然可以使用单纯形法进行求解，但是，由于运输问题的约束系数矩阵有其特殊的结构和性质，因而有比题的约束系数矩阵有其特殊的结构和性质，因

3、而有比题的约束系数矩阵有其特殊的结构和性质，因而有比题的约束系数矩阵有其特殊的结构和性质，因而有比单纯形法更有效的方法来求解。单纯形法更有效的方法来求解。单纯形法更有效的方法来求解。单纯形法更有效的方法来求解。2021/9/242021/9/241 1第三章第三章 运运 输输 问题问题运输问题的数学模型运输问题的数学模型表上作业法表上作业法产销不平衡的运输问题产销不平衡的运输问题求初始基可行解的方法：求初始基可行解的方法：西北角法、最小元素法、西北角法、最小元素法、元素差额法元素差额法基可行解的改进方法：基可行解的改进方法：闭回路调整法、位势法闭回路调整法、位势法2021/9/242021/9

4、/242 2例：某运输问题的资料如下：例：某运输问题的资料如下：单位 销地 运价产地产量2910791342584257销量3846一、运输问题的数学模型一、运输问题的数学模型试制定一个调运方案，使得总运费最省？试制定一个调运方案，使得总运费最省？试制定一个调运方案，使得总运费最省？试制定一个调运方案，使得总运费最省？2021/9/242021/9/243 32021/9/242021/9/244 4 数学模型的一般形式数学模型的一般形式 已知资料如下：已知资料如下：单位单位单位单位 销销销销 运运运运 价价价价 地地地地产地产地产地产地产产产产量量量量销销销销 量量量量2021/9/2420

5、21/9/245 5当产销平衡时，其模型如下：当产销平衡时，其模型如下：(3.1(3.1)2021/9/242021/9/246 6当产大于销时，其模型是：当产大于销时，其模型是：(3.2(3.2)2021/9/242021/9/247 7当产小于销时，其模型是：当产小于销时，其模型是：(3.3(3.3)2021/9/242021/9/248 8 运输问题的特征：运输问题的特征：1 1、平衡运输问题必有可行解，也必有最优解；、平衡运输问题必有可行解，也必有最优解；证证 设设2021/9/242021/9/249 9m m m m行行行行n n n n行行行行第第第第i i i i行行行行第第第

6、第m+jm+jm+jm+j行行行行2021/9/242021/9/2410102021/9/242021/9/2411113、运输问题的基可行解中应包括运输问题的基可行解中应包括 m+n1 个基变量。个基变量。2021/9/242021/9/241212前前前前2m2m行行行行后后后后n n行行行行2021/9/242021/9/241313闭回路闭回路：凡是能排列成凡是能排列成形式的变量形式的变量形式的变量形式的变量集合，若用一条封闭折线将它们连接起来形成的图形称集合，若用一条封闭折线将它们连接起来形成的图形称集合，若用一条封闭折线将它们连接起来形成的图形称集合，若用一条封闭折线将它们连接起

7、来形成的图形称为一个闭回路，其中诸变量称为为一个闭回路，其中诸变量称为为一个闭回路，其中诸变量称为为一个闭回路，其中诸变量称为闭回路的顶点闭回路的顶点闭回路的顶点闭回路的顶点，连接相，连接相，连接相，连接相邻两个顶点及最后一个顶点与第一个顶点的线段称为邻两个顶点及最后一个顶点与第一个顶点的线段称为邻两个顶点及最后一个顶点与第一个顶点的线段称为邻两个顶点及最后一个顶点与第一个顶点的线段称为闭闭闭闭回路的边回路的边回路的边回路的边。B1B1B2B2B3B3B4B4B5B5A1A1x x1111x x1414A2A2x x2121x x2222A3A3x x3232x x3535A4A4x x444

8、4x x45452021/9/242021/9/241414闭回路具有以下性质：闭回路具有以下性质：(1)(1)每一个顶点都是转角点；每一个顶点都是转角点；基格：闭回路的顶点基格：闭回路的顶点闭回路在基格处可以直行，也可以拐弯，在空格处必闭回路在基格处可以直行，也可以拐弯，在空格处必须直行，不能拐弯。须直行，不能拐弯。(2)(2)每一条边都是水平线或垂直线，闭回路是由这每一条边都是水平线或垂直线，闭回路是由这 些水平线或垂直线构成的一条封闭折线；些水平线或垂直线构成的一条封闭折线；(3)(3)每一行每一行(或列或列)若有闭回路的顶点，则必有两个。若有闭回路的顶点，则必有两个。空格：基格外的格。

9、空格：基格外的格。2021/9/242021/9/241515闭回路的性质：闭回路的性质：充要条件是它不含闭回路。充要条件是它不含闭回路。充要条件是它不含闭回路。充要条件是它不含闭回路。则加入空格后的则加入空格后的则加入空格后的则加入空格后的m+nm+nm+nm+n个格中必含有唯一的闭回路。个格中必含有唯一的闭回路。个格中必含有唯一的闭回路。个格中必含有唯一的闭回路。2021/9/242021/9/241616二、初始基可行解的求法二、初始基可行解的求法(表上作业法表上作业法)运输问题运输问题运输问题运输问题(3.1)(3.1)(3.1)(3.1)的解法主要有图上作业法和表上作业法两的解法主要

10、有图上作业法和表上作业法两的解法主要有图上作业法和表上作业法两的解法主要有图上作业法和表上作业法两种。表上作业法又称为运输单纯形法，它是根据单纯形种。表上作业法又称为运输单纯形法，它是根据单纯形种。表上作业法又称为运输单纯形法，它是根据单纯形种。表上作业法又称为运输单纯形法，它是根据单纯形法的原理和运输问题的特征，设计出来的一种便于在表法的原理和运输问题的特征，设计出来的一种便于在表法的原理和运输问题的特征，设计出来的一种便于在表法的原理和运输问题的特征，设计出来的一种便于在表上运算的方法，作为一种迭代方法，它的主要步骤：上运算的方法，作为一种迭代方法，它的主要步骤：上运算的方法，作为一种迭代

11、方法，它的主要步骤：上运算的方法，作为一种迭代方法，它的主要步骤：(1)(1)(1)(1)求一个初始基可行解求一个初始基可行解求一个初始基可行解求一个初始基可行解(又称初始调运方案又称初始调运方案又称初始调运方案又称初始调运方案)；(2)(2)(2)(2)判别当前的基可行解是否为最优解，若是，则迭代判别当前的基可行解是否为最优解，若是，则迭代判别当前的基可行解是否为最优解，若是，则迭代判别当前的基可行解是否为最优解，若是，则迭代停止；否则，转下一步；停止；否则，转下一步；停止；否则，转下一步；停止；否则，转下一步；(3)(3)(3)(3)改进当前的基可行解，得新的基可行解，再返回改进当前的基可

12、行解，得新的基可行解，再返回改进当前的基可行解，得新的基可行解，再返回改进当前的基可行解，得新的基可行解，再返回(2)(2)(2)(2)2021/9/242021/9/241717 此法是纯粹的人为的规定，没有理论依据和实际背此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因景，但它易操作，特别适合在计算机上编程计算，因而备受欢迎。而备受欢迎。1 1、西北角法（或左上角法）：、西北角法（或左上角法）：遵循的原则：优先安排运价表上编号最小的产地和销遵循的原则：优先安排运价表上编号最小的产地和销遵循的原则：优先安排运价表上编号最小的产地和销遵循的原则：优先安

13、排运价表上编号最小的产地和销地之间地之间地之间地之间(即运价表的西北角位置即运价表的西北角位置即运价表的西北角位置即运价表的西北角位置)的运输业务。的运输业务。的运输业务。的运输业务。2021/9/242021/9/241818例例1 设有某物资共有设有某物资共有3个产地个产地A1,A2,A3,其产量分别为其产量分别为9,5,7个单位，另有个单位，另有4个销地个销地B1,B2,B3,B4,其销量分别为其销量分别为3,8,4,6,已知由产地已知由产地Ai运往销地运往销地Bj的单位运价见下表，的单位运价见下表，问应如何调运问应如何调运,才能使总运费最省？才能使总运费最省？1 1、求初始调运方案：、

14、求初始调运方案：单单位位 销销地地 运价运价产产地地B1B2B3B4产产量量A1 2 9 10 79A2 1 3 4 25A3 8 4 2 57销销量量38462021/9/242021/9/241919 单单位位 销销地地 运价运价产产地地B1B2B3B4产产量量A1 2 9 10 79A2 1 3 4 25A3 8 4 2 57销销量量3846首先安排产地首先安排产地首先安排产地首先安排产地A A A A1 1 1 1与销地与销地与销地与销地B B B B1 1 1 1之间的运输业务，即从运价表上西北角之间的运输业务，即从运价表上西北角之间的运输业务，即从运价表上西北角之间的运输业务，即从

15、运价表上西北角(或左上角或左上角或左上角或左上角)位置位置位置位置x x1111开始分配运输量，并使开始分配运输量，并使开始分配运输量，并使开始分配运输量，并使x x1111取尽可能大的数值。取尽可能大的数值。取尽可能大的数值。取尽可能大的数值。现在产地现在产地现在产地现在产地A A A A1 1 1 1的产量为的产量为的产量为的产量为9,9,9,9,而销地而销地而销地而销地B B B B1 1 1 1的需求量为的需求量为的需求量为的需求量为3.3.3.3.故安排产地故安排产地故安排产地故安排产地A A A A1 1 1 1运送运送运送运送3 3 3 3个单位的货物给销地个单位的货物给销地个单

16、位的货物给销地个单位的货物给销地B B B B1 1 1 1,即取即取即取即取x x1111=mina1,b1=min3,9=3=mina1,b1=min3,9=3，当产地，当产地，当产地，当产地A A A A1 1 1 1运出运出运出运出3 3 3 3个单位货物后，还剩个单位货物后，还剩个单位货物后，还剩个单位货物后，还剩9-3=69-3=69-3=69-3=6个单位，此时销地个单位，此时销地个单位，此时销地个单位，此时销地B B B B1 1 1 1的需求量的需求量的需求量的需求量已得到满足，此时已得到满足，此时已得到满足，此时已得到满足，此时A A2 2,A,A3 3不可能再运送货物给销

17、地不可能再运送货物给销地不可能再运送货物给销地不可能再运送货物给销地B B B B1 1 1 1了，此时将了，此时将了，此时将了，此时将B B B B1 1 1 1列划去；再在剩下的运价表上，重复上述过程，即决定列划去；再在剩下的运价表上，重复上述过程，即决定列划去；再在剩下的运价表上，重复上述过程，即决定列划去；再在剩下的运价表上，重复上述过程，即决定x x x x121212123 30 06 6 6 66 60 0 0 02 2 2 22 20 0 0 03 3 3 33 30 0 0 01 1 1 11 16 6 6 60 0 0 06 60 0 0 00 0 0 02021/9/24

18、2021/9/242020A A1 1运送运送运送运送6 6个单位货物给个单位货物给个单位货物给个单位货物给B B2 2,此时此时此时此时A A1 1的供应量为的供应量为的供应量为的供应量为0 0，划去，划去，划去，划去A A1 1行，行，行，行，B B2 2的需求量为的需求量为的需求量为的需求量为2.2.用同样的方法得初始基可行解用同样的方法得初始基可行解用同样的方法得初始基可行解用同样的方法得初始基可行解X X(0)(0)的各分量为：的各分量为：的各分量为：的各分量为：相应的目标函数值相应的目标函数值相应的目标函数值相应的目标函数值2021/9/242021/9/2421212 2、最小元

19、素法、最小元素法遵循原则：优先安排单位运价最小的产地与销地之间的遵循原则：优先安排单位运价最小的产地与销地之间的遵循原则：优先安排单位运价最小的产地与销地之间的遵循原则：优先安排单位运价最小的产地与销地之间的运输业务。运输业务。运输业务。运输业务。依次安排最小元素、次小元素，从而得到一个初始依次安排最小元素、次小元素，从而得到一个初始依次安排最小元素、次小元素，从而得到一个初始依次安排最小元素、次小元素，从而得到一个初始基可行解。用此方法制定出来的调运方案，其总运费基可行解。用此方法制定出来的调运方案，其总运费基可行解。用此方法制定出来的调运方案，其总运费基可行解。用此方法制定出来的调运方案，

20、其总运费一般会比用西北角法制定的调运方案要省。一般会比用西北角法制定的调运方案要省。一般会比用西北角法制定的调运方案要省。一般会比用西北角法制定的调运方案要省。2021/9/242021/9/242222 单位 销地 运价产地B1B2B3B4产地A1 2 9 10 79A2 1 3 4 25A3 8 4 2 57销地3846例例例例2 2 2 2 用最小元素法制定例用最小元素法制定例用最小元素法制定例用最小元素法制定例1 1 1 1的初始调运方案。的初始调运方案。的初始调运方案。的初始调运方案。第第第第1 1 1 1个最小元素为个最小元素为个最小元素为个最小元素为c c2121=1=1,此时比

21、较此时比较此时比较此时比较A A2 2的产量和的产量和的产量和的产量和B B1 1的销量此时取其的销量此时取其的销量此时取其的销量此时取其最小值，最小值，最小值，最小值，x x2121=min5,3=3,=min5,3=3,则安排则安排则安排则安排A A2 2运送运送运送运送3 3个单位货物给个单位货物给个单位货物给个单位货物给B B1 1,此时此时此时此时A A2 2剩余剩余剩余剩余2 2个单位，个单位，个单位，个单位，B1B1的需求量已满足，将的需求量已满足，将的需求量已满足，将的需求量已满足，将B B1 1列划去；再在剩余列划去；再在剩余列划去；再在剩余列划去；再在剩余表格中找最小元素表

22、格中找最小元素表格中找最小元素表格中找最小元素c c2424=2,=2,此时令此时令此时令此时令x x2424=min2,6=2=min2,6=2则安排则安排则安排则安排A A2 2运送运送运送运送2 2个个个个单位货物给单位货物给单位货物给单位货物给B B4 4,则则则则A A2 2的供应量已尽，的供应量已尽，的供应量已尽，的供应量已尽，B B4 4余余余余4 4个单位，则将个单位，则将个单位，则将个单位，则将A A2 2行划行划行划行划去；再在剩余表格中重复以上过程，最终得初始调运方案。去；再在剩余表格中重复以上过程，最终得初始调运方案。去；再在剩余表格中重复以上过程，最终得初始调运方案。

23、去；再在剩余表格中重复以上过程，最终得初始调运方案。3 30 0 0 02 2 2 22 20 0 0 04 4 4 44 40 0 0 03 3 3 33 30 0 0 05 5 5 54 45 5 5 50 0 0 05 50 0 0 00 0 0 02021/9/242021/9/242323西北角法与最小元素法的比较西北角法与最小元素法的比较西北角法与最小元素法的比较西北角法与最小元素法的比较西北角法西北角法西北角法西北角法的最大优点是实现简单，特别适合编制程的最大优点是实现简单，特别适合编制程的最大优点是实现简单，特别适合编制程的最大优点是实现简单，特别适合编制程序上机计算，但缺点是

24、所制定的初始方案往往离最序上机计算，但缺点是所制定的初始方案往往离最序上机计算，但缺点是所制定的初始方案往往离最序上机计算，但缺点是所制定的初始方案往往离最优解较远，后面的调整量较大。优解较远，后面的调整量较大。优解较远，后面的调整量较大。优解较远，后面的调整量较大。而而而而最小元素法最小元素法最小元素法最小元素法的最大优点是制定的初始方案一般离的最大优点是制定的初始方案一般离的最大优点是制定的初始方案一般离的最大优点是制定的初始方案一般离最优解较近，后面调整量较小。但要在一张大型的最优解较近，后面调整量较小。但要在一张大型的最优解较近，后面调整量较小。但要在一张大型的最优解较近，后面调整量较

25、小。但要在一张大型的运价表上每次搜索最小元素，其计算量也是很可观运价表上每次搜索最小元素，其计算量也是很可观运价表上每次搜索最小元素，其计算量也是很可观运价表上每次搜索最小元素，其计算量也是很可观的。当然，当问题的规模不大，用手工计算时，可的。当然，当问题的规模不大，用手工计算时，可的。当然，当问题的规模不大，用手工计算时，可的。当然，当问题的规模不大，用手工计算时，可以通过人的判断力，很快找到最小元素，因此，用以通过人的判断力，很快找到最小元素，因此，用以通过人的判断力，很快找到最小元素，因此，用以通过人的判断力，很快找到最小元素，因此，用手工计算时，一般采用最小元素法求初始调运方案手工计算

26、时，一般采用最小元素法求初始调运方案手工计算时，一般采用最小元素法求初始调运方案手工计算时，一般采用最小元素法求初始调运方案较好。较好。较好。较好。2021/9/242021/9/2424242021/9/242021/9/2425252021/9/242021/9/2426263 3、元素差额法元素差额法 元素差额法是在元素差额法是在元素差额法是在元素差额法是在最小元素法的基础最小元素法的基础最小元素法的基础最小元素法的基础上改进的一种求上改进的一种求上改进的一种求上改进的一种求初始方案的方法，在分配运量以确定产销关系时，不初始方案的方法，在分配运量以确定产销关系时，不初始方案的方法，在分配

27、运量以确定产销关系时，不初始方案的方法，在分配运量以确定产销关系时，不是从最小元素开始，而是从运价表中各行和各列的最是从最小元素开始，而是从运价表中各行和各列的最是从最小元素开始，而是从运价表中各行和各列的最是从最小元素开始，而是从运价表中各行和各列的最小元素和次小元素之差额来确定产销关系，小元素和次小元素之差额来确定产销关系，小元素和次小元素之差额来确定产销关系，小元素和次小元素之差额来确定产销关系，(按最大按最大按最大按最大差额所在行或列中的最小元素安排产地与销地之间的差额所在行或列中的最小元素安排产地与销地之间的差额所在行或列中的最小元素安排产地与销地之间的差额所在行或列中的最小元素安排

28、产地与销地之间的运输业务运输业务运输业务运输业务)因此称为元素差额法。因此称为元素差额法。因此称为元素差额法。因此称为元素差额法。2021/9/242021/9/242727 单位 销地 运价产地B1B2B3B4产地差额A1 2 9 10 7 9A2 1 3 4 2 5A3 8 4 2 5 7销地3846差额 3 30 0 0 06 6 6 61 1 1 15 5 5 51 1 1 12 2 2 21 1 1 11 1 1 12 2 2 22 2 2 21 1 1 12 2 2 21 1 1 12 2 2 23 3 3 33 3 3 35 5 5 58 8 8 82 2 2 22 2 2 22

29、 2 2 25 50 0 0 00 0 0 03 3 3 34 45 5 5 52 2 2 22 2 2 21 1 1 13 30 0 0 05 5 5 59 9 9 97 7 7 72 2 2 25 50 0 0 01 1 1 11 10 0 0 00 0 0 0初始调运方案为初始调运方案为初始调运方案为初始调运方案为2021/9/242021/9/2428281 1 闭回路求检验数闭回路求检验数对于给定的调运方案对于给定的调运方案对于给定的调运方案对于给定的调运方案(基可行解基可行解基可行解基可行解)，从非基变量，从非基变量，从非基变量，从非基变量x xij ij出发作出发作出发作出发作一

30、条一条一条一条闭回路，要求该闭回路上其余的顶点均为基变量，闭回路，要求该闭回路上其余的顶点均为基变量，闭回路，要求该闭回路上其余的顶点均为基变量，闭回路，要求该闭回路上其余的顶点均为基变量，并从并从并从并从x xij ij开始将该闭回路上的顶点顺序编号开始将该闭回路上的顶点顺序编号开始将该闭回路上的顶点顺序编号开始将该闭回路上的顶点顺序编号(顺时针或逆顺时针或逆顺时针或逆顺时针或逆时针均可时针均可时针均可时针均可)称编号为奇数的点为奇点，编号为偶数的点称编号为奇数的点为奇点，编号为偶数的点称编号为奇数的点为奇点，编号为偶数的点称编号为奇数的点为奇点，编号为偶数的点为偶点，则为偶点，则为偶点，则

31、为偶点，则x xij ij处对应的检验数为奇点处运价的总和与偶处对应的检验数为奇点处运价的总和与偶处对应的检验数为奇点处运价的总和与偶处对应的检验数为奇点处运价的总和与偶点处运价的总和之差。点处运价的总和之差。点处运价的总和之差。点处运价的总和之差。(理论依据：理论依据：理论依据：理论依据：x xij ij处的运量增加一处的运量增加一处的运量增加一处的运量增加一个单位，则闭回路同行中顶点处运量减少一个单位个单位，则闭回路同行中顶点处运量减少一个单位个单位，则闭回路同行中顶点处运量减少一个单位个单位，则闭回路同行中顶点处运量减少一个单位,同同同同列中顶点处运量增加一个单位，依此类推，直至考虑闭列

32、中顶点处运量增加一个单位，依此类推，直至考虑闭列中顶点处运量增加一个单位，依此类推，直至考虑闭列中顶点处运量增加一个单位，依此类推，直至考虑闭回路所有顶点回路所有顶点回路所有顶点回路所有顶点.).)闭回路的做法闭回路的做法闭回路的做法闭回路的做法：从空格出发，遇基格可直行亦可拐弯，：从空格出发，遇基格可直行亦可拐弯，：从空格出发，遇基格可直行亦可拐弯，：从空格出发，遇基格可直行亦可拐弯，遇空格必须直行不可拐弯，目的是保证闭回路的顶点遇空格必须直行不可拐弯，目的是保证闭回路的顶点遇空格必须直行不可拐弯，目的是保证闭回路的顶点遇空格必须直行不可拐弯，目的是保证闭回路的顶点为基格。为基格。为基格。为

33、基格。最优性判别与基可行解的改进最优性判别与基可行解的改进检验数的求法检验数的求法2021/9/242021/9/2429292021/9/242021/9/2430302021/9/242021/9/243131 单位 销地 运价产地B1B2B3B4产地A1 2 9 10 79A21 3 4 25A38 4 2 57销地38463 32 24 43 34 45 5用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例1 1 1 1的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表-4-4x x1111的检验数为的检验数为的检验数为的检验

34、数为2-7+2-1=-42-7+2-1=-42021/9/242021/9/243232 单位 销地 运价产地B1B2B3B4产地A1 2 9 10 79A21 3 4 25A38 4 2 57销地38463 32 24 43 34 45 5用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例1 1 1 1的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表x x1313的检验数为的检验数为的检验数为的检验数为10-2+4-9=310-2+4-9=33 32021/9/242021/9/243333 单位 销地 运价产地B1B2B3B4产

35、地A1 2 9 10 79A21 3 4 25A38 4 2 57销地38463 32 24 43 34 45 5用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例1 1 1 1的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表x x2222的检验数为的检验数为的检验数为的检验数为3-9+7-2=-13-9+7-2=-1-1-12021/9/242021/9/243434 单位 销地 运价产地B1B2B3B4产地A1 2 9 10 79A21 3 4 25A38 4 2 57销地38463 32 24 43 34 45 5用最小元素法

36、求出的例用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例1 1 1 1的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表x x2323的检验数为的检验数为的检验数为的检验数为4-2+7-9+4-2=24-2+7-9+4-2=22 22021/9/242021/9/243535 单位 销地 运价产地B1B2B3B4产地A1 2 9 10 79A21 3 4 25A38 4 2 57销地38463 32 24 43 34 45 5用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例1 1 1 1的初始调运方案见下表的初始调运方案

37、见下表的初始调运方案见下表的初始调运方案见下表x x3131的检验数为的检验数为的检验数为的检验数为8-1+2-7+9-4=78-1+2-7+9-4=77 72021/9/242021/9/243636 单位 销地 运价产地B1B2B3B4产地A1 2 9 10 79A21 3 4 25A38 4 2 57销地38463 32 24 43 34 45 5用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例1 1 1 1的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表x x3434的检验数为的检验数为的检验数为的检验数为5-7+9-4=

38、35-7+9-4=33 32021/9/242021/9/243737 单位 销地 运价产地B1B2B3B4产地A1 2 9 10 79A21 3 4 25A38 4 2 57销地38463 32 24 43 34 45 5用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例用最小元素法求出的例1 1 1 1的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表的初始调运方案见下表-4-43 3-1-12 27 73 32021/9/242021/9/2438382 2 位势法求检验数位势法求检验数首先写出运输问题的对偶问题首先写出运输问题的对偶问题首先写出运输问题的对偶问题首先

39、写出运输问题的对偶问题 由于运输问题的约束条件共有由于运输问题的约束条件共有由于运输问题的约束条件共有由于运输问题的约束条件共有m+nm+n个，前个，前个，前个，前mm个是关个是关个是关个是关于产地的产量限制，后于产地的产量限制，后于产地的产量限制，后于产地的产量限制，后n n个是关于销地销量的限制。因个是关于销地销量的限制。因个是关于销地销量的限制。因个是关于销地销量的限制。因此对偶问题中的对偶变量也应有此对偶问题中的对偶变量也应有此对偶问题中的对偶变量也应有此对偶问题中的对偶变量也应有m+nm+n个，前个，前个，前个，前mm个记为个记为个记为个记为u u1 1,u,u2 2,u,umm,后

40、后后后n n个记为个记为个记为个记为v v1 1,v,v2 2,v,vn n,并记并记并记并记运输问题的对偶问题运输问题的对偶问题运输问题的对偶问题运输问题的对偶问题2021/9/242021/9/243939单纯形法中有一个重要的规定，即基变量对应的检验单纯形法中有一个重要的规定，即基变量对应的检验单纯形法中有一个重要的规定，即基变量对应的检验单纯形法中有一个重要的规定，即基变量对应的检验数为零，根据这一原理，可以建立关于数为零，根据这一原理，可以建立关于数为零，根据这一原理，可以建立关于数为零，根据这一原理，可以建立关于u ui i,v,vj j的方程组，的方程组，的方程组，的方程组，可以

41、很快求出可以很快求出可以很快求出可以很快求出ui,vj.设给定了一个初始调运方案，其基变量为设给定了一个初始调运方案，其基变量为设给定了一个初始调运方案，其基变量为设给定了一个初始调运方案，其基变量为2021/9/242021/9/244040于是得到如下的方程组于是得到如下的方程组于是得到如下的方程组于是得到如下的方程组这个方程组共有这个方程组共有这个方程组共有这个方程组共有m+n-1m+n-1m+n-1m+n-1个方程，可以证明此方程有解个方程，可以证明此方程有解个方程，可以证明此方程有解个方程，可以证明此方程有解，而要确定的未知数共有而要确定的未知数共有而要确定的未知数共有而要确定的未知

42、数共有m+nm+n个，故其中必有一个自由个，故其中必有一个自由个，故其中必有一个自由个，故其中必有一个自由未知量，取它为任意常数，就可以把其余的未知量解未知量，取它为任意常数，就可以把其余的未知量解未知量，取它为任意常数，就可以把其余的未知量解未知量，取它为任意常数，就可以把其余的未知量解出来。例如取出来。例如取出来。例如取出来。例如取u uij ij=0,=0,就可以决定其余的就可以决定其余的就可以决定其余的就可以决定其余的u ui i和和和和v vj j2021/9/242021/9/244141 vjui单位 产地 运价销地B1B2B3B4产地 0 A1 2 9 10 79 A21 3

43、4 25 A38 4 2 57 销地38463 32 24 43 34 45 5用位势法求例用位势法求例1 1中的初始基可行解对应的检验数中的初始基可行解对应的检验数9 95 57 77 75 56 62021/9/242021/9/244242由于闭回路法和位势法中，检验数的定义方式与单纯形由于闭回路法和位势法中，检验数的定义方式与单纯形由于闭回路法和位势法中，检验数的定义方式与单纯形由于闭回路法和位势法中，检验数的定义方式与单纯形法完全一致，因此最优性判别条件也完全一致。注意运法完全一致，因此最优性判别条件也完全一致。注意运法完全一致，因此最优性判别条件也完全一致。注意运法完全一致，因此最

44、优性判别条件也完全一致。注意运输问题中的目标函数是求极小值，于是输问题中的目标函数是求极小值，于是输问题中的目标函数是求极小值，于是输问题中的目标函数是求极小值，于是定理定理定理定理 对于运输问题的一个基可行解，若所有的检验数对于运输问题的一个基可行解，若所有的检验数对于运输问题的一个基可行解，若所有的检验数对于运输问题的一个基可行解，若所有的检验数则此基可行解必为最优解。则此基可行解必为最优解。则此基可行解必为最优解。则此基可行解必为最优解。2021/9/242021/9/244343基可行解的改进基可行解的改进确定出基变量的方法利用确定出基变量的方法利用闭回路调整法：闭回路调整法：从进基变

45、量从进基变量从进基变量从进基变量x xrsrs出发作一条闭回路，并从出发作一条闭回路，并从出发作一条闭回路，并从出发作一条闭回路，并从x xrsrs出发将该闭出发将该闭出发将该闭出发将该闭回路上的顶点顺序编号，则调整量为回路上的顶点顺序编号，则调整量为回路上的顶点顺序编号，则调整量为回路上的顶点顺序编号，则调整量为调整的方法是：在该闭回路上，将奇点处的运量加上调整的方法是：在该闭回路上，将奇点处的运量加上调整的方法是：在该闭回路上，将奇点处的运量加上调整的方法是：在该闭回路上，将奇点处的运量加上，偶点处的运量减去，偶点处的运量减去，偶点处的运量减去，偶点处的运量减去，而表中的其余点处的运量不变

46、，而表中的其余点处的运量不变，而表中的其余点处的运量不变，而表中的其余点处的运量不变，这样得到新的基可行解，这样得到新的基可行解，这样得到新的基可行解，这样得到新的基可行解，进基变量的选择和单纯形法一样进基变量的选择和单纯形法一样2021/9/242021/9/244444 vjui单位 产地 运价销地B1B2B3B4产地 0 A1 2 9 10 79 A21 3 4 25 A38 4 2 57 销地38463 32 24 43 34 45 5对例对例1 1继续求解继续求解9 95 57 77 75 56 62021/9/242021/9/244545 vjui单位 产地 运价销地B1B2B3

47、B4产地 0 A1 2 9 10 79 A21 3 4 25 A38 4 2 57 销地38464 43 31 15 59 95 57 77 76 62 23 35 52021/9/242021/9/244646 vjui单位 产地 运价销地B1B2B3B4产地 0 A1 2 9 10 79 A21 3 4 25 A38 4 2 57 销地38464 43 36 60 09 95 57 77 76 62 23 35 5由于检验数全非负，故现有的基可行解即为最优解，且由于检验数全非负，故现有的基可行解即为最优解，且由于检验数全非负，故现有的基可行解即为最优解，且由于检验数全非负，故现有的基可行解

48、即为最优解，且最优调运方案为最优调运方案为最优调运方案为最优调运方案为2021/9/242021/9/244747 1 1、产大于销：模型、产大于销：模型 方法是先将原问题变成平衡问题，需假设一个销地方法是先将原问题变成平衡问题，需假设一个销地(Bn+1)(实际上考虑产地的存量实际上考虑产地的存量)，三、产销不平衡的运输问题及其求解方法三、产销不平衡的运输问题及其求解方法2021/9/242021/9/244848 模型为：模型为：2 2、销大于产：同样假设一个产地即可，变化同上。、销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为单位运价表中的单位运价为2021/9/2420

49、21/9/244949B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5 A121134070A210359050A378120702030406040B1B2B3B4B5 A170A250A370203040604040303020302020用最小元素法用最小元素法求初始方案求初始方案例题：2021/9/242021/9/245050 已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4产量产量A1265315A2132112A3327413销量销量1013125 1 1、表中的产量、销量单位为：吨，运价单位为：

50、、表中的产量、销量单位为：吨，运价单位为：元元/吨吨,试求出最优运输方案试求出最优运输方案.练习1：2 2、如将、如将A2的产量改为的产量改为1717，其它资料不变，试求，其它资料不变，试求最优调运方案。最优调运方案。2021/9/242021/9/245151B B1 1B B2 2B B3 3B B4 4产量产量产量产量A A1 112123 31515A A2 210102 21212A A3 313130 01313销量销量销量销量1010131312125 5B B1 1B B2 2B B3 3B B4 4产量产量产量产量A A1 12 26 65 53 31515A A2 21 1