第5章_运输问题a

1、1第五章第五章 运输问题运输问题5.1 运输问题的数学模型运输问题的数学模型5.2 初始基可行解的确定初始基可行解的确定5.3 最优性检验与基可行解的改进最优性检验与基可行解的改进5.4 其他运输问题其他运输问题25.1 运输问题的数学模型及其特征运输问题的数学模型及其特征有有m个产地个产地A1, A2, , Am生产某种物资，另有生产某种物资，另有n个销个销地地B1, B2, , Bm 需要该类物资；需要该类物资；令令a1, a2, , am表示各产地产量，表示各产地产量， b1, b2, , bn表示各表示各销地的销量销地的销量, 若若 ai= bj ，则称则称产销平衡产销平衡；设设xij

2、表示产地表示产地 i 运往销地运往销地 j 的物资量，的物资量，cij表示对应的表示对应的单位运费。单位运费。3如何调运，使总的运输费用最小？如何调运，使总的运输费用最小？供需平衡表供需平衡表bnb2b1销量销量BnB2B1 需方需方供方供方AmA2A1ama2a1产量产量 njjmiiba11cmncm2cm1c2nc22c21c1nc12c114 销销产产B1B2Bn产量产量A1c11 x11c12 x12c1n x1na1A2c21 x21c22 x22c2n x2na2Amcm1 xm1cm2 xm2cmn xmnam销量销量b1b1bn平衡表、运价表合二为一平衡表、运价表合二为一5(

3、1) (1) 运输问题数学模型运输问题数学模型xij 供应节点供应节点i至需求节点至需求节点j的运输量；的运输量；aij 供应节点供应节点i的可供应量，的可供应量，i=1,2, ,m；bij 需求节点需求节点j的需求量，的需求量，j=1,2,n；cij 供应节点供应节点i至需求节点至需求节点j的单位运输成本。的单位运输成本。jixnjbxmiaxtsxczMinijmijijinjijminjijij和和对所有的对所有的, 0, 2 , 1, 2 , 1.1111 6 根据运输问题中总供应量与总需求量的关系可将根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：运输问题分为两类： 平衡

4、型运输问题和不平衡型运输问题。平衡型运输问题和不平衡型运输问题。平衡型运输问题：平衡型运输问题： n1jjm1iiba不平衡型运输问题：不平衡型运输问题： n1jjm1iibal对于不平衡型运输问题通常通过设立虚拟供应节点或对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。虚拟需求节点将其转化为平衡型运输问题求解。(2) (2) 运输问题的分类运输问题的分类7 njmiijijxcz11min产销平衡产销平衡运输问题的数学模型：运输问题的数学模型： njjmiiba11Ai的产品全的产品全部供应出去部供应出去 miaxinjij, 2 , 11 njbxj

5、miij, 2 , 11 Bj的需求全的需求全部得到满足部得到满足 njmixij, 2 , 1;, 2 , 10 8jixnjbxmiaxtsxczMinijmijijinjijminjijij和和对对所所有有的的, 0, 2, 1, 2, 1.1111 平衡型运输问题的数学模型平衡型运输问题的数学模型 111111111111111111A模型包含模型包含变量：变量：mn个个约束方程：约束方程：m+n个个秩：秩：r(A)=m+n-1 m 行行n 行行稀疏矩阵稀疏矩阵9 njmiijijxcz11min产大于销产大于销运输问题的数学模型：运输问题的数学模型： njjmiiba11Ai的产品没

6、有的产品没有全部供应出去全部供应出去 miaxinjij, 2 , 11 njbxjmiij, 2 , 11 Bj的需求全的需求全部得到满足部得到满足 njmixij, 2 , 1;, 2 , 10 10 njmiijijxcz11min销大于产销大于产运输问题的数学模型：运输问题的数学模型： njjmiiba11Ai的产品全的产品全部供应出去部供应出去 miaxinjij, 2 , 11 njbxjmiij, 2 , 11 Bj的需求没有的需求没有全部得到满足全部得到满足 njmixij, 2 , 1;, 2 , 10 以下主要讨论产销平衡运输问题的数学模型以下主要讨论产销平衡运输问题的数学

7、模型11例例1. 现有现有A1，A2，A3三个产地，可供应物资分别为三个产地，可供应物资分别为10，8，5个个单位，现将物资运往单位，现将物资运往B1，B2，B3，B4四个销地，销量分别为四个销地，销量分别为5，7，8，3个单位。产地到销地的单位运价个单位。产地到销地的单位运价 cij 如表如表1所示，问如何所示，问如何安排一个运输计划，使总的运输费用最少。安排一个运输计划，使总的运输费用最少。销地销地产地产地B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323表表1 112解：设解：设xij ( i =1,2,3；j =1,2,3,4)为为i个产粮地运

8、往第个产粮地运往第j个需求地的个需求地的运量，这样得到下列运输问题的数学模型：运量，这样得到下列运输问题的数学模型： 38755810.342414332313322212312111343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxtsMin z = 3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+ 8x23+ 2x24 + 4x31+ x32+ 2x33+ 9x34xij 0, i =1, 2, 3; j =1, 2, 3, 413有些问题表面上与运输问题没有多大关系，但经过转换，也有些问题表面上与运输问题没有多大关系，但

9、经过转换，也可以建立与运输问题形式相同的数学模型。可以建立与运输问题形式相同的数学模型。例例2. 有三台机床加工三种零件，计划第有三台机床加工三种零件，计划第i台的生产任务为台的生产任务为ai (i=1,2,3)个零件，第个零件，第j种零件的需要量为种零件的需要量为bj (j=1,2,3)，第，第i台机床台机床加工第加工第j种零件需要的时间为种零件需要的时间为cij ，如表，如表2所示。问如何安排生产所示。问如何安排生产任务使总的加工时间最少？任务使总的加工时间最少？ 零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150表表214

10、 解：解： 设设 xi j (i=1,2,3；j=1,2,3,)为第为第i台机床加工第台机床加工第j种零件的数量，种零件的数量，则此问题的数学模型为则此问题的数学模型为 3 , 2 , 13 , 2 , 1, 050 30 70 40 60 50 . .43746325min332313322212312111333231232221131211333231232221131211jixxxxxxxxxxxxxxxxxxxtsxxxxxxxxxzij；15(3) 平衡型运输问题的对偶问题平衡型运输问题的对偶问题ji,xn,jbxm,iax. t . sxcZMinijmijijinjijmin

11、jijij和和对所有的对所有的021211111n,jmiv ,ucvu. t . svbuaWMaxjiijjinjjjmiii212111，无无符符号号限限制制由于由于r(A)=m+n-1，独立的约束方程独立的约束方程个数为个数为m+n-1;而变量个数为而变量个数为m+n，则其中有一个自则其中有一个自由变量由变量 njjmiiba1116(4) (4) 运输问题的特征运输问题的特征定理定理1：平衡运输问题必有可行解与最优解。：平衡运输问题必有可行解与最优解。证：对于平衡运输问题证：对于平衡运输问题令：令： n1jjm1iibaQji,0 xn,2 , 1jbxm,2 , 1iax. t .

12、 sxcZMinijm1ijijin1jijm1in1jijij和和对所有的对所有的 n,2 , 1jm,2 , 1iQbaxjiij 17则有则有 n,2 , 1j;m,2 , 1i0 xij n,2 , 1jbaQbQbaxm1ijijm1ijim1iij m,2 , 1iabQaQbaxn1jijin1jjin1jij 所以所以 是运输问题的一个可行解。是运输问题的一个可行解。 n,2 , 1jm,2 , 1iQbaxjiij 又由于又由于 n,2 , 1j;m,2 , 1i0cij 所以所以0 xcZm1in1jijij 且为极小化问题，且为极小化问题，故一定存在最优解。故一定存在最优

13、解。18定理定理2 平衡运输问题的约束方程系数矩阵平衡运输问题的约束方程系数矩阵A的秩的秩 r(A)=m+n-1。证：因为产销平衡，即证：因为产销平衡，即 ，将前，将前m个约束方程两个约束方程两边相加得边相加得 mimjiiba11 minjmiiijax111再将后再将后n个约束相加得个约束相加得 njminjjijbx111显然前显然前m个约束方程之和等于后个约束方程之和等于后n个约束方程之和，个约束方程之和，m+n个约个约束方程是相关的束方程是相关的, 所以所以A中任意中任意 m + n 阶子式等于零阶子式等于零.19A中任意中任意m+n阶子式等于零阶子式等于零. 再取第一行到再取第一行

14、到m+n1行与行与对应的列（共对应的列（共m+n-1列）组成的列）组成的m+n1阶子式阶子式B1, 1121121, nmnnnxxxxxx， 111111111111111111Am 行行n 行行mnmnnxxxxxxx122111211200111111111 B故故r(A)=m+n1.1,1121121, nmnnnxxxxxx推论推论1 平衡运输问题的基可行解中应包含平衡运输问题的基可行解中应包含 m+n-1个基变量。个基变量。21为了在为了在mn个变量中找出个变量中找出m+n1个变量作为一组基变量，就是个变量作为一组基变量，就是要在要在A中找出中找出m+n-1个线性无关的列向量，下面

15、引用闭回路的个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。概念寻找这些基变量。定义定义1 凡能排列成凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个的图形称之为一个闭回路闭回路。构成回路的诸变量称为闭回路的构成回路的诸变量称为闭回路的顶点顶点；连接相邻两个顶点的线段称为闭回路的连接相邻两个顶点的线段称为闭回路的边边。1sss232111jijijijijix,x,x,x,x或或s1ss321211jijijijijix,x,x,x,x互不相同互不相同其中：其中：s321s321j ,j ,j ,ji ,i ,i

16、 ,i22 闭闭回回路路集集合合 132222111,jijijijijijisssxxxxxx x23 B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12 x25x31 x42表表3表表3中闭回路的变量集合是中闭回路的变量集合是x11,x12,x42, x 43, x 23, x 25, x 35, x 31共共有有8个顶点，个顶点， 这这8个顶点间用水平或垂直线段连接起来，组成个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。一条封闭的回路。 一条回路中的顶点数一条回路中的顶点数一定是偶数，回路遇一定是偶数，回路遇到顶点必须转到顶点必须转90度与度与另一顶点连接，表

17、另一顶点连接，表3中的变量中的变量x 32及及x33不不是回闭路的顶点，只是回闭路的顶点，只是连线的交点。是连线的交点。 23表表4中闭回路是中闭回路是 123233434111,xxxxxx 121131352521,xxxxxxA 2111123233,xxxxxB 例如变量组例如变量组A不能组成一条闭回路，但不能组成一条闭回路，但A中包含有闭回路中包含有闭回路 31352521,xxxxB的变量数是奇数，显然不是闭回路，也不含有闭回路的变量数是奇数，显然不是闭回路，也不含有闭回路. x11x12x32x33x41 B1B2B3A1 A2 A3 A4 x43表表424（1）每个顶点都是转角

18、点；）每个顶点都是转角点；（2）每一条边都是水平线段或垂直线段；）每一条边都是水平线段或垂直线段；（3）每一行（或列）若有闭回路的顶点，则必有两个）每一行（或列）若有闭回路的顶点，则必有两个.闭回路的闭回路的几何性质几何性质：x11x12x32x33x41 B1B2B3A1 A2 A3 A4 x43表表425性质性质1 若变量组若变量组B 包含有闭回路包含有闭回路 ，则，则B中中的变量对应的列向量线性相关。的变量对应的列向量线性相关。 12111,jijijisxxxC 证：证：由线性代数知，向量组中部分向量组线性相关则该向量由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将

19、组线性相关，显然，将C中列向量分别乘以正负号线性组合中列向量分别乘以正负号线性组合后等于零，即后等于零，即01222111 jijijijisPPPP因而因而C中的列向量线性相关，所以中的列向量线性相关，所以B中列向量线性相关。中列向量线性相关。闭回路的闭回路的代数性质代数性质：推论：若一个变量组对应的系数列向量线性无关，则该变量推论：若一个变量组对应的系数列向量线性无关，则该变量组一定不包含闭回路。组一定不包含闭回路。26定义定义2 在变量组在变量组 中，若有某一变量中，若有某一变量xij是它所在的行（第是它所在的行（第i行）或列（第行）或列（第j列）中出现在该变量组中列）中出现在该变量组中

20、的唯一变量，则称该变量为的唯一变量，则称该变量为孤立点孤立点。x12x32x41 B1B2B3A1 A2 x21 x23A3 A4 性质性质2 若变量组若变量组C中不包含任何闭回路，则该变量组中必有孤中不包含任何闭回路，则该变量组中必有孤立点。立点。s2211,jijijisxxx27求运输问题的一组基变量，就是要找到求运输问题的一组基变量，就是要找到m+n1个变量，使得它个变量，使得它们对应的系数列向量线性无关，由们对应的系数列向量线性无关，由性质性质1，找这样的一组变量是，找这样的一组变量是很容易的，只要很容易的，只要m+n1个变量中不包含闭回路，就可得到一组个变量中不包含闭回路，就可得到

21、一组基变量。因而有：基变量。因而有：定理定理3 平衡运输问题中的一组平衡运输问题中的一组 m+n1 个变量个变量构成基变量的构成基变量的充要条件充要条件是它不包含任何闭回路。（证略）是它不包含任何闭回路。（证略）定理定理3告诉了一个求基变量的简单方法，同时也可以判断一组告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个平衡运输问题的基变量。这种方法是变量是否可以作为某个平衡运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而中去寻找，从而给运输问题求初始基可行解带来极大的方便。给运输问题求初始基可行解带来极大

22、的方便。)1(,s2211 nmsxxxjijijis28例如，例如，m=3, n=4，在运价表，在运价表cij的格子的右上方填上相应的的格子的右上方填上相应的xij，如表如表5所示。所示。表表5 BjAiB1B2B3B4aiA1 x11 x12 x13 x14 a1C11C12C13C14A2 x21 x22 x23 x24a2C21C22C23C24A3 x31 x32 x33 x34a3C31C32C33C34bjb1b2b3b4 343332222111,xxxxxx基变量：基变量：29这个运输问题的基变量数目是这个运输问题的基变量数目是3+41=6。变量组中。变量组中有有7个变量，显

23、然不能构成一组基变量，又如个变量，显然不能构成一组基变量，又如中有中有6个变量，但包含有一条闭回路个变量，但包含有一条闭回路故不能构成一组基变量。变量组故不能构成一组基变量。变量组有有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。个变量且不含有任何闭回路，故可以构成此问题的一组基变量。22121324323111,xxxxxxx,342413322221xxxxxx24343222,xxxx 343332222111,xxxxxx30 运输问题是一类特殊的线性规划问题运输问题是一类特殊的线性规划问题 对于平衡型运输问题：对于平衡型运输问题： 约束方程数为约束方程数为m+n个，但有一

24、个冗余方程，所以独个，但有一个冗余方程，所以独立方程数为立方程数为m+n-1个，即秩个，即秩r(A)=m+n-1。 存在最优解存在最优解 当供应量和需求量均为整数时，存在整数最优解。当供应量和需求量均为整数时，存在整数最优解。 基可行解中基变量个数为基可行解中基变量个数为m+n-1个个 基可行解中基变量的重要特征：不含闭回路。基可行解中基变量的重要特征：不含闭回路。小结：运输问题的基本性质小结：运输问题的基本性质31本节介绍了具有本节介绍了具有m个产地个产地n个销地的平衡运输问题个销地的平衡运输问题1.具有具有m+n1个基变量个基变量2. 闭回路的概念闭回路的概念3.怎样判断怎样判断m+n1个

25、变量是否构成一组基变量个变量是否构成一组基变量 1、单纯形法（为什么？）、单纯形法（为什么？） 2、表上作业法、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法由于问题的特殊形式而采用的更简洁、更方便的方法运输问题的解法运输问题的解法:32(1) (1) 找出初始调运方案（找出初始调运方案（初始基可行解初始基可行解）。即在）。即在(m(mn)n)产销平衡表上给出产销平衡表上给出m+n-1m+n-1个数字格。个数字格。 (4) (4) 重复（重复（2 2）、（）、（3 3），直到求得最优调运方案。），直到求得最优调运方案。计算步骤：计算步骤：(2) (2) 求求检验数检验数。（闭回路法

26、或位势法）。（闭回路法或位势法） 判别是否达判别是否达到最优解。如已是最优解，则停止计算，否则转到下到最优解。如已是最优解，则停止计算，否则转到下一步。一步。(3) (3) 对方案进行改善（对方案进行改善（改进当前的基可行解改进当前的基可行解），找出新），找出新的调运方案（新的基可行解）。（表上闭回路法调整）的调运方案（新的基可行解）。（表上闭回路法调整）运输问题的解法运输问题的解法表上作业法表上作业法335.2 初始基可行解的求法初始基可行解的求法获得获得初始基可行解（初始方案）初始基可行解（初始方案）的常用方法的常用方法:(1)西北角法西北角法(2)最小元素法最小元素法(3)*元素差额法（

27、元素差额法（Vogel近似法）近似法）34 例例3 运输问题供需平衡表和运价表如下，求初始调运方案。运输问题供需平衡表和运价表如下，求初始调运方案。 供供需需B1B2B3B4产量产量A13113107A219284A3741059销量销量36562035（1） 西北角法西北角法-“-“就近供应就近供应” 该方案总运费该方案总运费Z=33 + 411 + 29 + 22 + 310 + 65 =135优先满足运输表中西北角优先满足运输表中西北角( (即左上角即左上角) )上空格的供销需求上空格的供销需求7-3=46-4=24-2=25-2=39-3=6修正量修正量修正量修正量例例3初始调运方案初

28、始调运方案: x11=3, x12=4, x22=2, x23=2, x33=3, x34=6 (基变量基变量) 36813131466(1) (1) 西北角法西北角法西北角法的缺点：没有考虑运价大小，不尽合理西北角法的缺点：没有考虑运价大小，不尽合理总运费总运费 Z = 35037（2） 最小元素法最小元素法 优先安排单位运价最小的产销之间的业务优先安排单位运价最小的产销之间的业务销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633该方案总运费该方案总运费Z=43 + 310

29、+31+12+64+35=86例例338最小元素法实施步骤口诀最小元素法实施步骤口诀运价表运价表上找最小，上找最小，平衡表平衡表上定产销；上定产销； 满足销量划去满足销量划去“列列”，修改，修改“行产行产”要记牢；要记牢； （满足产量划去（满足产量划去“行行”，修改，修改“列销列销”要记牢）要记牢） 划去列划去列( (行行) )对对运价运价， 修改修改“行产行产( (列销列销)”)”在在产销产销； 余表再来找最小，方案很快就找到。余表再来找最小，方案很快就找到。39 1 2 3 4 6 7 5 3 A 14 14 8 4 2 7 B 27 27 5 9 10 6 C 19 19 22 13 1

30、2 13 22 13 12 13 (2) (2) 最小元素法最小元素法( (0) )40 1 2 3 4 6 7 5 3 A 14 14 8 4 2 7 B 12 27 15 5 9 10 6 C 19 19 22 13 12 13 22 13 0 13 (2) (2) 最小元素法最小元素法( (1) )41(2) (2) 最小元素法最小元素法( (2) ) 1 2 3 4 6 7 5 3 A 13 14 1 8 4 2 7 B 12 27 15 5 9 10 6 C 19 19 22 13 12 13 22 13 0 0 42(2) (2) 最小元素法最小元素法( (3) ) 1 2 3 4

31、 6 7 5 3 A 13 14 1 8 4 2 7 B 13 12 27 2 5 9 10 6 C 19 19 22 13 12 13 22 0 0 0 43(2) (2) 最小元素法最小元素法( (4) ) 1 2 3 4 6 7 5 3 A 13 14 1 8 4 2 7 B 13 12 27 2 5 9 10 6 C 19 19 0 22 13 12 13 3 0 0 0 44(2) (2) 最小元素法最小元素法( (5) )45(2) (2) 最小元素法最小元素法( (6) ) 1 2 3 4 6 7 5 3 A 1 13 14 0 8 4 2 7 B 2 13 12 27 0 5

32、9 10 6 C 19 19 0 22 13 12 13 0 0 0 0 总运费总运费 Z = 22246课堂练习课堂练习1 1用最小元素法求下列运输问题的初始方案用最小元素法求下列运输问题的初始方案 销地销地 产地产地A AB BC C产量产量甲甲8574乙乙9464丙丙1323销量销量326 111147课堂练习解答课堂练习解答 销地销地 产地产地A AB BC C产量产量甲甲8574乙乙9464丙丙1323销量销量326 11114220348课堂练习答案课堂练习答案 销地销地 产地产地A AB BC C产量产量甲甲8574乙乙9464丙丙1323销量销量326 111142203运费运

33、费 z = 51 退化的基可行解退化的基可行解 (x33=0)49（3 3）( (元素差额法元素差额法)Vogel)Vogel法法分别计算各行、各列分别计算各行、各列最小与次小最小与次小运价的差额，优先在最大差运价的差额，优先在最大差额处进行供需搭配。额处进行供需搭配。步骤：步骤：1 10 0 计算未划去行、列的差额；计算未划去行、列的差额； 2 20 0 找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配；进行供需分配；3 30 0 在未被划去的行、列重新计算差额。在未被划去的行、列重新计算差额。例例350 销销 产产B1B2B3B4供量供量A17A24A39销量销量 3

34、656 6B1B2B3B4行差额行差额A13113100A219281A3741051列差额列差额251351 销销 产产B1B2B3B4供量供量A17A24A3 9销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A3741052列差额列差额213 352 销销产产B1B2B3B4供量供量A17A24A3 9销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A374105列差额列差额212 3 353 销销产产B1B2B3B4供量供量A17A24A3 39销量销量 3656 6B1B2B3B4差额差额A13113107A2192

35、86A374105差额差额12 3 5 1 2该方案总运费该方案总运费Z=1Z=13+43+46+36+35+105+102+82+81+51+53=853=8554(3) (3) Vogel 法（元素差额法）法（元素差额法）2211333123311331314413131912总运费总运费 Z = 22255课堂练习课堂练习2 销地销地 产地产地ABC产量产量甲甲51710乙乙64680丙丙32520销量销量402050 110110用用Vogel法求下列运输问题的初始方案法求下列运输问题的初始方案56课堂练习课堂练习2解答解答 销地销地 产地产地ABC产量产量甲甲51710乙乙64680

36、丙丙32520销量销量402050 110110行差额行差额421211*1032*2000020501057课堂练习课堂练习2答案答案 销地销地 产地产地ABC产量产量甲甲51710乙乙64680丙丙32520销量销量402050 1101101020205010运费运费 Z = 530585.3 5.3 最优性检验与基可行解的改进最优性检验与基可行解的改进1. 最优性检验最优性检验njmiPBCcijBijij, 2 , 1, 2 , 101 充要条件充要条件l由于基变量的检验数由于基变量的检验数ij= 0,只需确定非基变量的检验数！只需确定非基变量的检验数！l确定非基变量检验数的常用方法

37、主要是：确定非基变量检验数的常用方法主要是：l闭回路法闭回路法非基变量与基变量构成唯一闭回路非基变量与基变量构成唯一闭回路l位势法位势法利用对偶变量利用对偶变量59（1）闭回路法）闭回路法 以确定了初始调运方案的作业表为基础，以一以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。外，其他顶点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对可以证明，如果对闭回路的方向不加区别，对于

38、每一个非基变量而言，以其为起点的闭回路存在于每一个非基变量而言，以其为起点的闭回路存在且唯一。且唯一。60检验数的求法检验数的求法:闭回路：从空格出发顺时针闭回路：从空格出发顺时针( (或逆时针或逆时针) )画水平画水平( (或垂直或垂直) )直线，直线，遇到填有运量的方格遇到填有运量的方格可转可转9090，然后继续前进，直到到达出发然后继续前进，直到到达出发的空格所形成的闭合回路。的空格所形成的闭合回路。 销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656差额法方案差额法方案(1) 闭回路法闭回路法例例3ij=闭回路上奇点运价之和闭回路上奇点运价之和

39、- - 闭回路上偶点运价之和闭回路上偶点运价之和61调运方案的任意空格存在调运方案的任意空格存在唯一唯一闭回路。闭回路。 销销 产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 365662销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633最小元素法方案最小元素法方案+-+-经济解释经济解释：若：若x11为换入变量，则为换入变量，则x11增加增加1， x13减少减少1, 运费的运费的变化为变化为(+1)3+(-1)3+(+1)2+(-1)1=c11

40、- -c13+c23- -c21=1 ，总总运费将增加，不合理运费将增加，不合理。这个变化就是。这个变化就是x11的检验数，故的检验数，故11=1例例363空格空格闭闭 回回 路路检验数检验数ij (11)(11)(12)(12)(22)(22)(24)(24)(31)(31)(33)(33)(11)-(13)-(23)-(21)-(11) (11)-(13)-(23)-(21)-(11) (12)-(14)-(34)-(32)-(12) (12)-(14)-(34)-(32)-(12) (22)-(23)-(13)-(14)-(34)-(32)-(22) (22)-(23)-(13)-(14

41、)-(34)-(32)-(22) (24)-(23)-(13)-(14)-(24)(24)-(23)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)(33)-(34)-(14)-(13)-(33)1 12 21 1-1-110101212 销销 产产B B1 1B B2 2B B3 3B B4 4产量产量A A1 1A A2 2A A3 33 36 6 4 4 1 13 33 37 74 49 9销量销量3 36 65 56 6例

42、例3最小元素法最小元素法方案方案24= -10，当前方案，当前方案 不是最优方案。不是最优方案。64(1) (1) 闭回路法闭回路法(0)22136857495210376ABC14271912131234148131366655(1) (1) 闭回路法闭回路法(1)12= c12-c11+c21-c22=7-6+8-4=522136857495210376ABC1427191213123414813136666-55(1) (1) 闭回路法闭回路法(2)13= c13-c11+c21-c23=5-6+8-2=522136857495210376ABC142719121312341481313

43、6667557(1) (1) 闭回路法闭回路法(3)14= c14-c11+c21-c23 +c33-c34 =3-6+8-2+10-6=722136857495210376ABC1427191213123414813136668755924= c24-c23+c33-c34=7-2+10-6=922136857495210376ABC14271912131234148131366(1) (1) 闭回路法闭回路法(4)697955-1131= c31-c33+c23-c21=5-10+2-8=-11(1) (1) 闭回路法闭回路法(5)22136857495210376ABC142719121

44、31234148131366707559-11-332= c32-c33+c23-c22=9-10+2-4=-322136857495210376ABC14271912131234148131366(1) (1) 闭回路法闭回路法(6)71(2) (2) 位势法位势法n,jmiv ,ucvu. t . svbuaWMaxjiijjinjjjmiii212111，无无符符号号限限制制对偶规划对偶规划jiijnmijjijjBijijvucvvvuuucYPcPBcc011021211 由于对偶变由于对偶变量的个数为量的个数为m+n，而系，而系数矩阵的秩数矩阵的秩为为m+n-1，我们可以通我们可以

45、通过设定自由过设定自由变量的值得变量的值得到所有对偶到所有对偶变量。变量。jivu ,位势位势72基变量基变量(xij)的检验数为：的检验数为： ij= cij - (ui + vj)= 0(2) 位势法位势法 标准型运输问题的对偶问题：标准型运输问题的对偶问题： 得得m+n-1个方程，令某个个方程，令某个ui (或或vj)=0，可解出，可解出m+n个个ui 和和vj；由此得非基变量的检验数由此得非基变量的检验数:n,jmiv ,ucvu. t . svbuaWMaxjiijjinjjjmiii212111，无无符符号号限限制制非基变量非基变量(xij)的检验数为的检验数为: ij= cij

46、- (ui + vj) 73 销销 产产B B1 1B B2 2B B3 3B B4 4产量产量A A1 1A A2 2A A3 33 36 6 4 4 1 13 33 37 74 49 9销量销量3 36 65 56 6例例3在例在例3的由最小元素法得到的初始解中的由最小元素法得到的初始解中x23，x34，x21，x32，x13，x14是基变量。是基变量。最小元素法最小元素法方案方案74 基变量基变量 检验数检验数 x23 c23-(u2+v3)=0 即即 2-(u2+v3)=0 x34 c34-(u3+v4)=0 5-(u3+v4)=0 x21 c21-(u2+v1)=0 1-(u2+v1

47、)=0 x32 c32-(u3+v2)=0 4-(u3+v2)=0 x13 c13-(u1+v3)=0 3-(u1+v3)=0 x14 c14-(u1+v4)=0 10-(u1+v4)=0 从以上从以上7个方程中个方程中,由由u1=0可求得可求得 u2= -1, u3= -5, v1=2, v2=9, v3=3, v4=10因非基变量的检验数因非基变量的检验数 )(jiijijvuc 这就可以从已知的这就可以从已知的ui，vj值中求得。这些值中求得。这些计算可在表格中进行计算可在表格中进行。 75销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2

48、4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633（2）位势法）位势法 令令v1=0, 由由c21=1= u2 +v1，得，得 u2=1最小元素法最小元素法方案方案例例376B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2例例3最小元素法最小元素法（2）位势法）位势法基变量基变量77 0 1 1 28-3 7位势表位势表2989-3-2)(jiijijvuc 检验数检验数(空格中数字为空格中数字为ui + vj )例例378B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7检验数表检验数表121-

49、1101224= -10，当前方案，当前方案 不是最优方案。不是最优方案。例例379(2) (2) 位势法位势法(0)v1v26857495210376ABCu1u2u3v3v4123414813136680选择含基变量最多的行或列，令相应的选择含基变量最多的行或列，令相应的u u或或v v为零。为零。v1v26857495210376ABCu1u2=0u3v3v41234148131366(2) (2) 位势法位势法(1)81v1=c21- u2=8-0=8, v2=c22- u2=4-0=4, v3=c23- u2=2-0=2(2) (2) 位势法位势法(2)82u1=c11-v1=6-8

50、=-2, u3 =c33- v3=10-2=8(2) (2) 位势法位势法(3)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4123414813136683v4=c34-u3=6-8=-2(2) (2) 位势法位势法(4)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-2123414813136684(2) (2) 位势法位势法(5)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366512 =c12-(u1+ v2) =7-(-2+4)=5855

51、(2) (2) 位势法位势法(6)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366513 =c13-(u1+ v3) =5-(-2+2)=586(2) (2) 位势法位势法(7)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366514 =c14-(u1+ v4) =3-(-2-2)=787(2) (2) 位势法位势法(8)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366524 =c

52、24-(u2+ v4) =7-(0-2)=9988(2) (2) 位势法位势法(9)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-212341481313665931 =c31-(u3+ v1) =5-(8+8)=-11-1189(2) (2) 位势法位势法(10)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-2123414813136659-1132 =c32-(u3+ v2) =9-(8+4)=-3-3902.2.基可行解的改进（闭回路调整法）基可行解的改进（闭回路调整法）l选择检验数绝对值最大

53、的非基变量为选择检验数绝对值最大的非基变量为进基变量进基变量( (存在多个时任选一个存在多个时任选一个) )确定进基变量确定进基变量确定离基变量确定离基变量l选择包含进基变量的闭回路上距进选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基变基变量奇次的变量中运量最小的基变量为离基变量。量为离基变量。运量调整运量调整 奇奇次次的的基基变变量量闭闭回回路路上上距距进进基基变变量量为为:xxminxttl 奇奇次次的的基基变变量量闭闭回回路路上上距距进进基基变变量量为为偶偶次次的的基基变变量量闭闭回回路路上上距距进进基基变变量量为为：离离基基变变量量：进进基基变变量量；lktlktktlj

54、ljxxxxxxxxx重复上述步骤直至所有检验数大于零，即获得最优解。重复上述步骤直至所有检验数大于零，即获得最优解。91B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7检验数表检验数表121-1101224= -10，当前方案，当前方案 不是最优方案。不是最优方案。例例392闭回路调整法改进方案（基可行解）闭回路调整法改进方案（基可行解）pqijj , i)(min 0 xpq为换入变量为换入变量 从从( (p,q) )空格开始画闭回路，其它转角点都是填有空格开始画闭回路，其它转角点都是填有运量的方格，并从运量的方格，并从( (p,qp,q) )空

55、格开始给闭回路上的点按空格开始给闭回路上的点按+1+1，-1-1，+1+1，-1-1编号编号，-1-1格的最小运量格的最小运量为为调整量调整量。换出变量换出变量销销地地 产产地地 B1 B2 B3 B4 产产量量 A1 A2 A3 3 6 4(+1) 1(- -1) 3(- -1) (+1) 3 7 4 9 销销量量 3 6 5 6 换换出出变变量量93851)1(862401 zz新的调运方案为：新的调运方案为：销销地地 产产地地 B1 B2 B3 B4 产产量量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销销量量 3 6 5 6 初始方案为：初始方案为：94 需供B1B2B3B

56、4uiA10210A2218A39125Vj -7-1-70713491110231085销销 地地 产产 地地 B1 B2 B3 B4 产产 量量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销销 量量 3 6 5 6 所有所有ij 0, 方案最优方案最优95表上作业法计算中的问题表上作业法计算中的问题(1)(1)有无穷多最优解有无穷多最优解 最终解中有非基变量检验数为零时，则该问题有无穷最终解中有非基变量检验数为零时，则该问题有无穷多个最优解。多个最优解。 以此非基变量为换入变量，可求得另一基最优解。基以此非基变量为换入变量，可求得另一基最优解。基最优解的任一凸组合都是最优解。如

57、例最优解的任一凸组合都是最优解。如例3 3另一基最优解是：另一基最优解是： 96(2) 退化退化 解中非零基变量个数小于解中非零基变量个数小于m+n-1时，为退化解。时，为退化解。 求初始解时，当求初始解时，当minai，bj=ai=bj，在第，在第i行或行或第第j列任一空格上加列任一空格上加0,表示这个格中的基变量的取表示这个格中的基变量的取值是值是0。 97已知已知 运输问题供需表和运价表如下，求最优调运方案。运输问题供需表和运价表如下，求最优调运方案。课堂练习课堂练习销销 产产 B1 B2 B3 B4 产产量量 2 11 3 4 A1 7 10 3 5 9 A2 5 7 8 1 2 A3

58、 7 销销量量 2 3 4 6 9822136857495210376ABC142719121312341481313669755-11-3确定进基变量确定进基变量选择检验数绝对值最大的非基变量为进基变量选择检验数绝对值最大的非基变量为进基变量9922136857495210376ABC142719121312341481313669755-11-3确定闭回路确定闭回路10022136857495210376ABC142719121312341481313669755-11-366 , 8min,min3321xxxl确定离基变量确定离基变量10122136857495210376ABC142

59、7191213123414213131209755-3调整运量调整运量6x31=6, x21=8-6=2, x23=6+6=1210222136857495210376ABC142719121312341421313126-2-4558进一步优化进一步优化(0)1110322136857495210376ABC142719121312341421313126-2-4558进一步优化进一步优化(1)11x13 进基，进基， x34离基。离基。10422136857495210376ABC14271912131234121313121924558进一步优化进一步优化(2)11所有非基变量的检验数均

60、大于零，即为最优解。所有非基变量的检验数均大于零，即为最优解。1051. 产销不平衡的运输问题产销不平衡的运输问题 在很多运输问题中，总产量不等于在很多运输问题中，总产量不等于总销量。这时，为了使用前述表上作总销量。这时，为了使用前述表上作业法求解，就需将产销不平衡运输问业法求解，就需将产销不平衡运输问题化为产销平衡运输问题。题化为产销平衡运输问题。 5.4 其他运输问题其他运输问题106这时的数学模型是这时的数学模型是 ：如果总产量大于总销量，即如果总产量大于总销量，即 njjmiiba11 minjijijxcz11min0,2,1,2,1,11 ijjmiijinjijxnjbxmiax