1、运筹学运筹学Operations ResearchChapter 5 运输与指派问题运输与指派问题Transportation and Assignment Problem5.1运输模型运输模型 Mathematical Model of Transportation Problems5.2 运输单纯形法运输单纯形法 Transportation Simplex Method5.3 运输模型的应用运输模型的应用 Aplication of Transportation Model5.4 指派问题指派问题 Assignment problem 5.1 运输模型运输模型 Mathematical
2、Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 3 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三人们在从事生产活动中，不人们在从事生产活动中，不可避免地要进行物资调运工可避免地要进行物资调运工作。如某时期内将生产基地作。如某时期内将生产基地的煤、钢铁、粮食等各类物的煤、钢铁、粮食等各类物资，分别运到需要这些物资资，分别运到需要这些物资的地区，根据各地的的地区，根据各地的生产量生产量和和需要量需要量及各地之间的及各地之间的运输运输费用费用，如何制定一个运输方，如何制定一个运输方
3、案，使总的运输费用最小。案，使总的运输费用最小。这样的问题称为这样的问题称为运输问题运输问题。5.1 运输模型运输模型 Model of Transportation Problems5.1.1 数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图5.1 制作与教学 武汉理工大学管理学院 熊伟 Page 4 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三【例例5-1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应 粮食分别为粮食分别为10，8，5（万吨），现将
4、粮食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需四个地区，其需要量分别为要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用所示，问如何安排一个运输计划，使总的运输费用最少。最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表（元运价表（元/T）表表5-15.1 运输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 5
5、Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三11121314212223243132333441424344xxxxxxxxXxxxxxxxx设设xij(i=1,2,3；j=1,2,3,4)为为i个产粮地运往第个产粮地运往第j个需求地的运量（个需求地的运量（万吨），得到下列运输问题的数学模型：万吨），得到下列运输问题的数学模型：34333231242322211413121192428353623minxxxxxxxxxxxxZ5810343332312423222114131211xxxxxxxxxxxx387534241433231332
6、2212312111xxxxxxxxxxxx运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 4,3,2,13,2,1,0jixij；5.1 运输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 6 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三 有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型看一个例子：看一个例子：【例例5-2】有三台机床加
7、工三种零件，计划第有三台机床加工三种零件，计划第i台的生产任务台的生产任务为为a i (i=1,2,3)个零件，第个零件，第j种零件的需要量为种零件的需要量为bj (j=1,2,3)，第，第i台台机床加工第机床加工第j种零件需要的时间为种零件需要的时间为cij，如表，如表52所示。问如何安所示。问如何安排生产任务使总的加工时间最少？排生产任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150表表525.1 运输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工
8、大学管理学院 熊伟 Page 7 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三 【解解】设设 xi j (i=1,2,3；j=1,2,3,)为第为第i台机床加工第台机床加工第j种零件的种零件的数量，则此问题的数学模型为数量，则此问题的数学模型为3,2,13,2,1,050307040605043746325min332313322212312111333231232221131211333231232221131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxZij；5.1 运输模型运输模型 Model of Transpo
9、rtation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 8 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地（记作个产地（记作A1，A2，A3,Am），生产某种物资，其产），生产某种物资，其产量分别为量分别为a1,a2，am；有；有n个销地（记作个销地（记作B1，B2，Bn），），其需要量分别为其需要量分别为b1,b2，bn；且产销平衡，即；且产销平衡，即 。从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij，在满足各地需要的前提，在满足
10、各地需要的前提下，求总运输费用最小的调运方案。下，求总运输费用最小的调运方案。设设xij(i=1,2,，m；j=1,2,n)为第为第i个产地到第个产地到第j个销地的运量，则数学模型为：个销地的运量，则数学模型为：njjmiiba115.1 运输模型运输模型 Model of Transportation Problemsnjijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,1;,1,0,1,111 制作与教学 武汉理工大学管理学院 熊伟 Page 9 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三niijijmix
11、cz11minnjmixnjbxmiaxijjmiijnjiij,1;,1,0,1,111设平衡运输问题的数学模型为：设平衡运输问题的数学模型为：5.1.2 模型特征模型特征5.1 运输模型运输模型 Model of Transportation Problems1.运输问题存在可行解，也一定存在最优解运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解当供应量和需求量都是整数时，则一定存在整数最优解3.有有m+n个约束，个约束，mn个变量个变量4.有有m+n1个基变量个基变量 制作与教学 武汉理工大学管理学院 熊伟 Page 10 Chapter 5 运
12、输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三【证证】因为产销平衡，即因为产销平衡，即 ，将前，将前m个约束方程两边相个约束方程两边相加得加得minjiiba11minjmiiijax111再将后再将后n个约束相加得个约束相加得njminjjijbx111显然前显然前m个约束方程之和等于后个约束方程之和等于后n个约束方程之和，个约束方程之和，m+n个约束个约束方程是相关的，系数矩阵方程是相关的，系数矩阵5.1 运输模型运输模型 Model of Transportation Problems【定理定理5.1】设有设有m个产地个产地n个销地且产销平衡的运输问题，则基个
13、销地且产销平衡的运输问题，则基变量数为变量数为m+n-1。制作与教学 武汉理工大学管理学院 熊伟 Page 11 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三中任意中任意m+n阶子式等于零，取第一行到阶子式等于零，取第一行到m+n1行与行与对应的列（共对应的列（共m+n-1列）组成的列）组成的m+n1阶子式阶子式1,1121121,nmnnnxxxxxx，m 行行n 行行5.1 运输模型运输模型 Model of Transportation Problems111212122212111111111111111111nnmmmnxxxxxx
14、xxxA 制作与教学 武汉理工大学管理学院 熊伟 Page 12 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三0111111111故故r(A)=m+n1所以运输问题有所以运输问题有m+n1个基变量。个基变量。为了在为了在mn个变量中找出个变量中找出m+n1个变量作为一组基变量，就是个变量作为一组基变量，就是要在要在A中找出中找出m+n-1个线性无关的列向量，下面引用闭回路的概个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。念寻找这些基变量。5.1 运输模型运输模型 Model of Transportation Problems 制作
15、与教学 武汉理工大学管理学院 熊伟 Page 13 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三),(,2121132222111互不相同；称集合ssjijijijijijijjjiiixxxxxxsss为一个闭回路为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表的连线为闭回路的边。在表53及表及表54中的变量组构成两个中的变量组构成两个闭回路。闭回路。x25 x23 B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12x31 x42表表53表表53中闭
16、回路的变量集中闭回路的变量集合是合是x11,x12,x42,x 43,x 23,x 25,x 35,x 31共有共有8个顶点，个顶点，这这8个顶点间用水平或垂直个顶点间用水平或垂直线段连接起来，组成一条线段连接起来，组成一条封闭的回路。封闭的回路。5.1 运输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 14 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三x11x12x32x33x41 B1B2B3A1 A2 A3 A4 x43表表54 一条回路中的顶点数一定是
17、一条回路中的顶点数一定是偶数，回路遇到顶点必须转偶数，回路遇到顶点必须转90度度与另一顶点连接，表与另一顶点连接，表53中的变中的变量量x 32及及x33不是回闭路的顶点，不是回闭路的顶点，只是连线的交点。只是连线的交点。表表54中闭回路是中闭回路是123233434111,xxxxxx;,121131352521xxxxxxA;,2111123233xxxxxB 例如变量组例如变量组A不能组成一条闭回路，但不能组成一条闭回路，但A中包含有闭回路中包含有闭回路;,31352521xxxxB的变量数是奇数，显然不是闭回路，也不含有闭回路；的变量数是奇数，显然不是闭回路，也不含有闭回路；5.1 运
18、输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 15 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三333211122321,xxxxxxC C是一条闭回路，若把是一条闭回路，若把C重新写成重新写成 就不难看出就不难看出C仍是一条闭回路。仍是一条闭回路。111232332321,xxxxxxC【定理定理5.2】若变量组若变量组B 包含有闭回路包含有闭回路 ，则，则B中的变量对应的列向量线性相关。中的变量对应的列向量线性相关。12111,jijijisxxxC【证
19、证】由线性代数知，向量组中部分向量组线性相关则该向量组由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将线性相关，显然，将C中列向量分别乘以正负号线性组合后等于中列向量分别乘以正负号线性组合后等于零，即零，即1 11 22 210si ji ji ji jPPPP因而因而C中的列向量线性相关，所以中的列向量线性相关，所以B中列向量线性相关。中列向量线性相关。5.1 运输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 16 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2
20、023年3月1日星期三由定理由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。的系数向量线性无关。求运输问题的一组基变量，就是要找到求运输问题的一组基变量，就是要找到m+n1个变量，使得它们个变量，使得它们对应的系数列向量线性无关，由定理对应的系数列向量线性无关，由定理2，找这样的一组变量是很容，找这样的一组变量是很容易的，只要易的，只要m+n1个变量中不包含闭回路，就可得到一组基变量。个变量中不包含闭回路，就可得到一组基变量。因而有：因而有：【定理定理3】m+n1个变量组构成基变量的充要条件是它不包含个变量组构成基
21、变量的充要条件是它不包含任何闭回路。任何闭回路。定理定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始中去寻找，从而给运输问题求初始基可行解带来极大的方便。基可行解带来极大的方便。5.1 运输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 17 Chapter
22、5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三表表5-5 BjAiB1B2B3B4aiA1c11 c12c13c14 a1x11x12x13x14A2c21c22 c23c24a2x21x22x23x24A3c31c32c2c34a3x31x32x33x34bjb1b2b3b45.1 运输模型运输模型 Model of Transportation Problems例如，例如，m=3,n=4，将，将xij与运价与运价Cij放在同一张表中，如表放在同一张表中，如表5-5所示。所示。制作与教学 武汉理工大学管理学院 熊伟 Page 18 Chapter 5 运输与
23、指派问题运输与指派问题T&A Problem 2023年3月1日星期三这个运输问题的基变量数目是这个运输问题的基变量数目是3+41=6。变量组中。变量组中有有7个变量，显然不能构成一组基变量，又如个变量，显然不能构成一组基变量，又如中有中有6个变量，但包含有一条闭回路个变量，但包含有一条闭回路故不能构成一组基变量。变量组故不能构成一组基变量。变量组有有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。个变量且不含有任何闭回路，故可以构成此问题的一组基变量。22121324323111,xxxxxxx,342413322221xxxxxx24343222,xxxx343332222111
24、,xxxxxx5.1 运输模型运输模型 Model of Transportation Problems 制作与教学 武汉理工大学管理学院 熊伟 Page 19 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三本节介绍了具有本节介绍了具有m个产地个产地n个销地的平衡运输问题时：个销地的平衡运输问题时：1.具有具有m+n1个基变量个基变量2.闭回路的概念闭回路的概念3.怎样判断怎样判断m+n1个变量是否构成一组基变量个变量是否构成一组基变量5.1 运输模型运输模型 Model of Transportation Problems下一节：运输单纯形法
25、下一节：运输单纯形法作业：教材习题作业：教材习题 5.5，5.6 建立数学模型建立数学模型5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 21 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三njijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,1;,1,0,1,111设平衡运输问题的数学模型为：设平衡运输问题的数学模型为：5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与
26、教学 武汉理工大学管理学院 熊伟 Page 22 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三运输单纯形法也称为表上作业法，是直接在运价表上求最优解运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：的一种方法，它的步骤是：第一步：第一步：求初始基行可行解（初始调运方案）。求初始基行可行解（初始调运方案）。常用的方法有常用的方法有最小元素法、元素差额法（最小元素法、元素差额法（Vogel近似法）、左上角法。近似法）、左上角法。第二步：第二步：求检验数并判断是否得到最优解。常用求检验的方法求检验数并判断是否得到最优解。
27、常用求检验的方法有闭回路法和位势法，当非基变量的检验数有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最全都非负时得到最优解，若存在检验数优解，若存在检验数lk0，说明还没有达到最优，转第三步。，说明还没有达到最优，转第三步。第三步：第三步：调整运量，即换基。选一个变量出基，对原运量进行调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。调整得到新的基可行解，转入第二步。5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 23 Chapter 5 运输与指派问题运输与
28、指派问题T&A Problem 2023年3月1日星期三5.2.1初始基可行解初始基可行解1.最小元素法最小元素法 最小元素法的思想是就近优先运送，即最小运价最小元素法的思想是就近优先运送，即最小运价Cij对应的变量对应的变量xij优先赋值优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。依次下去，直到最后得到一个初始基可行解。jiijbax,min5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Pa
29、ge 24 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三【例例5-3】求表求表56所示的运输问题的初始基可行解。所示的运输问题的初始基可行解。表表56 销销 地地产地产地B1B2B3B4产量产量A1A2A39723610859412705020销销 量量106040301405.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 25 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三 BjAiB1B2B3B4
30、产产 量量A1938 470A2765 150A32109 220销销 量量10604030140表表5759【解解】301010605.2 运输单纯形法运输单纯形法 Transportation Simplex Method2010 制作与教学 武汉理工大学管理学院 熊伟 Page 26 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三到一组基可行解可用矩阵到一组基可行解可用矩阵601020301010X表示，矩阵表示，矩阵X 中空白处对应的变量是非基变量，运量等于零，中空白处对应的变量是非基变量，运量等于零，这组解就是初始调运方案总运费这组解
31、就是初始调运方案总运费Z=360+810+520+130+210+910=500 制作与教学 武汉理工大学管理学院 熊伟 Page 27 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三【例例5-4】求表求表5-10给出的运输问题的初始基本可行解给出的运输问题的初始基本可行解 B1B2B3B4aiA14104420A2773815A31210615bj510251050表表5-105.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 28 Chapter 5
32、 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三表表5-11 BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解解】510 01510105.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 29 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三初始基本可行解可用下列矩阵表示初始基本可行解可用下列矩阵表示0101015510表表511中，基变量恰好是中，基变量恰好是3+41
33、=6个且不包含闭回路，个且不包含闭回路，是一组基变量，其余标有符号是一组基变量，其余标有符号的变量是非基变量的变量是非基变量 323123141312,xxxxxx5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 30 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三2元素差额法（元素差额法（Vogel近似法）近似法）最小元素法只考虑了局部运输费最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很用最小。有时为了节省某一处的
34、运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案运价先调运，否则会增加总运费。例如下面两种运输方案10515108520211515C10155108520211515C前一种按最小元素法求得，总运费是前一种按最小元素法求得，总运费是Z1=108+52+151=105后一种方案考虑到后一种方案考虑到C11与与C21之间的差额是之间的差额是82=6，先调运
35、，先调运x21，再是再是x22，其次是，其次是x12这时总运费这时总运费Z2=105+152+51=85Z1。5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 31 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三 基于以上思路，元素差额法求初始基本可行解的步骤是：基于以上思路，元素差额法求初始基本可行解的步骤是：第一步第一步：求出每行次小运价与最小运价之差，记为：求出每行次小运价与最小运价之差，记为ui，i=1,2,m；同时求出每列次小运价与最小运价之
36、差，记为；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n；第二步第二步：找出所有行、列差额的最大值，即：找出所有行、列差额的最大值，即L=maxui，vi，差，差额额L对应行或列的最小运价处优先调运；对应行或列的最小运价处优先调运；第三步第三步：这时必有一列或一行调运完毕，在剩下的运价中再求：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。完毕，就得到一个初始调运方案。用元素差额法求得的基本可行解更接近最优解，所以也称为近用元素差额法求得的基
37、本可行解更接近最优解，所以也称为近似方案。似方案。5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 32 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三表表5-6【例例5-5】用元素差额法求表用元素差额法求表56运输问题的初始基本可行解。运输问题的初始基本可行解。【解解】求行差额求行差额 ui,i=1,2,3及列差额及列差额vj,j=1,2,3,4.计算公式为计算公式为 ui=i行次小运价行次小运价i行最小运价行最小运价 vj=j列次小运价列次小运价j
38、例最小运价例最小运价5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 销销 地地产地产地B1B2B3B4产量产量A1A2A39723610859412705020销销 量量10604030140 制作与教学 武汉理工大学管理学院 熊伟 Page 33 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三表表512 BjAiB1B2B3B4aiuiA19384701A27651504A321092207bj10604030140vj5331【】105.2 运输单纯形法运输单纯形法 Transportation
39、 Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 34 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三表表5-13105.2 运输单纯形法运输单纯形法 Transportation Simplex Method BjAiB1B2B3B4aiuiA19384701A27651504A32109220710bj10604030140vj331【】制作与教学 武汉理工大学管理学院 熊伟 Page 35 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三5.2 运输单纯形法运
40、输单纯形法 Transportation Simplex Method BjAiB1B2B3B4aiuiA19384701A27651504A321092201010bj10604030140vj333表表5-14【】20 制作与教学 武汉理工大学管理学院 熊伟 Page 36 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三表表5-15【】6030105.2 运输单纯形法运输单纯形法 Transportation Simplex Method BjAiB1B2B3B4aiuiA19384705A2765150120A321092201010bj
41、10604030140vj33 制作与教学 武汉理工大学管理学院 熊伟 Page 37 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三基本可行解为基本可行解为601030201010X总运费总运费Z=360+810530+120+210+210=470比最小元素法的总运费（比最小元素法的总运费（500）要小）要小30 5.2 运输单纯形法运输单纯形法 Transportation Simplex Method3.左上角法左上角法。左上角法。左上角法(亦称西北角法亦称西北角法)是优先从运价表的左上角的是优先从运价表的左上角的变量赋值，当行或列分配
42、完毕后，再在表中余下部分的左上角赋变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同时分配完一值，依次类推，直到右下角元素分配完毕当出现同时分配完一行和一列时，仍然应在打行和一列时，仍然应在打“”的位置上选一个变量作基变量，以的位置上选一个变量作基变量，以保证最后的基变量数等于保证最后的基变量数等于m+n1 制作与教学 武汉理工大学管理学院 熊伟 Page 38 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三【例例5-6】用左上角法求例用左上角法求例5-3中表中表5-6的初始基本可行解的初始基本
43、可行解 表表5-161060010205.2 运输单纯形法运输单纯形法 Transportation Simplex Method BjAiB1B2B3B4产产 量量A1938 470A2765 150A32109 220销销 量量1060403040 制作与教学 武汉理工大学管理学院 熊伟 Page 39 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三基本可行解为基本可行解为10600401020X用左上角法求得的基本可行解对应的目标函数值（总运费）是用左上角法求得的基本可行解对应的目标函数值（总运费）是Z91036080540110+220
44、=520 制作与教学 武汉理工大学管理学院 熊伟 Page 40 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三求出一组基可行解后，判断是否为最优解，仍然是用检验数来判求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记断，记xij的检验数为的检验数为ij由第一章知，求最小值的运输问题的最优由第一章知，求最小值的运输问题的最优判别准则是：判别准则是：所有非基变量的检验数都非负，则运输方案最优（即为最优解）。所有非基变量的检验数都非负，则运输方案最优（即为最优解）。求检验数的方法有两种，闭回路法和位势法。求检验数的方法有两种，闭回路法和
45、位势法。1闭回路法求检验数闭回路法求检验数 求某一非基变量的检验数的方法是：在基求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。这个非基变量的检验数。5.2 运输单纯形法运输单纯形法 Transportation Simplex Method5.2.2求检验数求检验
46、数 制作与教学 武汉理工大学管理学院 熊伟 Page 41 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三【解解】用最小元素法用最小元素法 求得的检验数求得的检验数【例例5-7】用闭回路法求例用闭回路法求例53表表59的检验数。的检验数。5.2 运输单纯形法运输单纯形法 Transportation Simplex Method BjAiB1B2B3B4产产 量量A1938 470A2765 150A32109 220销销 量量10604030140301010602010表表59 制作与教学 武汉理工大学管理学院 熊伟 Page 42 Cha
47、pter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三矩阵中打矩阵中打“”的位置是非基变量，其余是基变量，这里只求的位置是非基变量，其余是基变量，这里只求非基变量的检验数。非基变量的检验数。求求11，先找出，先找出x11的闭回路的闭回路 ，对应的运价为，对应的运价为再用正负号分别交替乘以运价有再用正负号分别交替乘以运价有直接求代数和得直接求代数和得31331311,xxxx31331311,CCCC31331311,CCCC829893133131111CCCC5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作
48、与教学 武汉理工大学管理学院 熊伟 Page 43 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三 BjAiB1B2B3B4aiA19384706010A27651502030A321092201010bj10604030831331311,xxxx31331311,CCCC829893133131111CCCC0966-35.2 运输单纯形法运输单纯形法 Transportation Simplex Method395126983106385692957085143323243434331312323212132322223133232121
49、1323244114CCCCCCCCCCCCCCCCCCCC 制作与教学 武汉理工大学管理学院 熊伟 Page 44 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三同理可求出其它非基变量的检验数：同理可求出其它非基变量的检验数：3951269831063856929570851433232434343313123232121323222231332321211323244114CCCCCCCCCCCCCCCCCCCC这里这里340，说明这组基本可行解不是最优解。，说明这组基本可行解不是最优解。只要求得的基变量是正确的且数目为只要求得的基变量是正
50、确的且数目为m+n1，则某个非基变量的，则某个非基变量的闭回路存在且唯一，因而检验数唯一。闭回路存在且唯一，因而检验数唯一。5.2 运输单纯形法运输单纯形法 Transportation Simplex Method 制作与教学 武汉理工大学管理学院 熊伟 Page 45 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2023年3月1日星期三2位势法求检验位势法求检验 位势法求检验数是根据对偶理论推导出来的一位势法求检验数是根据对偶理论推导出来的一种方法。种方法。设平衡运输问题为设平衡运输问题为minjjiijxcZ11minnjmixnjbxmiaxijmijijn
