1、1第第4 4章章 运输问题运输问题2运输问题与有关概念运输问题与有关概念运输问题的求解运输问题的求解表上作业法表上作业法运输问题应用运输问题应用建模建模本章内容重点本章内容重点34.1 4.1 运输问题模型及有关概念运输问题模型及有关概念 4.1.1 4.1.1 问题的提出问题的提出 一般的运输问题就是要解决把某一般的运输问题就是要解决把某种产品从若干个产地调运到若干个种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定间的运输单价的前提下，如何确定一个使得总的运输费
2、用最小的方案。一个使得总的运输费用最小的方案。44.1 运输问题模型及有关概念运输问题模型及有关概念 例例4.1:某公司从两个产地某公司从两个产地A1、A2将物将物品运往三个销地品运往三个销地B1、B2、B3，各产地的，各产地的产量、各销地的销量和各产地运往各销产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？如何调运可使总运输费用最小？B1 B2 B3 产量产量 A1 6 4 6 200 A2 6 5 5 300 销量销量 150 150 200 5解：解：产销平衡问题：产销平衡问题：总产量总产量 =总销量总销量
3、 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输的运输量，得到下列运输量表：量，得到下列运输量表：B1 B2 B3 产量产量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 销量销量 150 150 200 4.1 运输问题模型及有关概念运输问题模型及有关概念6 Min f=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1,2；j=1,2,3）4.1 4.1 运输问题模型及有关概念运
4、输问题模型及有关概念7 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系数矩阵系数矩阵4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念8 模型系数矩阵特征模型系数矩阵特征 1.共有共有m+n 行，分别表示各产地和行，分别表示各产地和销地；销地；m n 列，分别表示各决策变列，分别表示各决策变量；量；2.每列只有两个每列只有两个 1，其余为，其余为 0，分别，分别表示只有一个产地和一个销地被使表示只有一个产地和一个销地被使用。用。4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念9一般运输问题的提法：
5、一般运输问题的提法：假设假设 A1,A2,Am 表示某物资的表示某物资的m个个产地；产地；B1,B2,Bn 表示某物资的表示某物资的n个销地；个销地；si表示产地表示产地 Ai 的产量；的产量；dj 表示销地表示销地 Bj 的的销量；销量；cij 表示把物资从产地表示把物资从产地 Ai 运往销地运往销地 Bj 的单位运价（表的单位运价（表4-3）。如果）。如果 s1+s2+sm=d1+d2+dn则称为产销平衡问题；否则，称产销不则称为产销平衡问题；否则，称产销不平衡。首先讨论产销平衡问题。平衡。首先讨论产销平衡问题。4.1.2 一般运输问题的线性规划模型及求解思路一般运输问题的线性规划模型及求
6、解思路10表表4-3 运输问题数据表运输问题数据表4.1 运输问题模型及有关概念运输问题模型及有关概念 销地销地产地产地B1 B2 Bn产量产量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmns1 s2 sm销量销量d1 d2 dn 设设 xij 为从产地为从产地 Ai 运往销地运往销地 Bj 的运输量，的运输量，根据这个运输问题的要求，可以建立运输根据这个运输问题的要求，可以建立运输变量表（表变量表（表 4-4）。）。11表表4-4 运输问题变量表运输问题变量表4.1 运输问题模型及有关概念运输问题模型及有关概念 销地销地产地产地B1 B2 Bn产量产量A
7、1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xmns1 s2 sm销量销量d1 d2 dn m n Min Min f =cij xij i=1 j=1 n s.t.s.t.xij =si i=1,2,m (4-5)(4-5)j=1 m xij =dj j=1,2,n (4-6)(4-6)i=1 xij 0 (i=1,2,m;j=1,2,n)4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念 对于产销平衡问题，可得到下列运输对于产销平衡问题，可得到下列运输问题的模型：问题的模型：13 运输问题是一种特殊的线性规划问题，运输问题是一种特殊的线性规划问题，
8、在求解时依然可以采用单纯形法的思路，在求解时依然可以采用单纯形法的思路，如图如图4-14-1所示所示。由于运输规划系数矩阵的特殊性，如果由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运规划系数矩阵特征的基础上建立了针对运输问题的输问题的表上作业法表上作业法。下面主要讨论下面主要讨论基本可行解、检验数基本可行解、检验数以及以及基的转换基的转换等问题。等问题。产销平衡运输模型求解产销平衡运输模型求解14产销平衡运输模型求解过程产销平衡
9、运输模型求解过程基本可行解是否最优解结束换基是否图图4-1 4-1 运输问题的求解思路运输问题的求解思路返回15 运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的量均在表4-3与表4-4中，因此考虑把表4-3与表4-4合成一个表,如下表4-5表4-5 运输问题求解作业数据表(下页）16产销平衡运输模型数据表产销平衡运输模型数据表 销地销地产地产地B1B2Bn产量产量A1 c11 x11c12 x12c1n x1na1 A2 c21 x21c22 x22c2n x2na2 Amcm1 xm1cm2 xm2cmn xmnam销量销量b1b2bn 17 运输问题的基变量共有运输问题的基变量共
10、有 m+n-1 个，系数矩阵个，系数矩阵A的秩为的秩为 m+n-1。运输问题的运输问题的 m+n-1 个变量构成个变量构成基变量的充分必要条件是不含闭基变量的充分必要条件是不含闭回路。回路。闭回路、闭回路的顶点闭回路、闭回路的顶点运输运输模型模型的基变量的基变量18 定义定义4.1 在表在表4-5的决策变量格中，凡是能的决策变量格中，凡是能够排列成下列形式的够排列成下列形式的 xab,xac,xdc,xde,xst,xsb (4-7)或或 xab,xcb,xcd,xed,xst,xat (4-8)其中，其中，a,d,s 各不相同；各不相同；b,c,t 各不相同，各不相同，我们称之为变量集合的一
11、个闭回路，并将式我们称之为变量集合的一个闭回路，并将式（4-7）、式（）、式（4-8）中的变量称为这个闭回路）中的变量称为这个闭回路的顶点。的顶点。为了说明这个特征，我们不加证明的给为了说明这个特征，我们不加证明的给出一些概念和结论。下面的讨论建立在表出一些概念和结论。下面的讨论建立在表4-54-5中决策变量格的基础上。中决策变量格的基础上。4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念19例如，例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x21；x11,x14,x34,x31等都是闭回路。等都是闭回路。若把闭回路的各变量格看作节
12、点，在表若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：中可以画出如下形式的闭回路：4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念 闭回路示意图闭回路示意图20 根据定义可以看出闭回路的一些根据定义可以看出闭回路的一些明显特点：明显特点：(1)(1)闭回路均为一封闭折线，它闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的每一条边，或为水平的，或为垂直的；的；(2)(2)闭回路的每一条边（水平的闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的或垂直的）均有且仅有两个闭回路的顶点（变量格）。顶点（变量格）。4.1 4.1 运输问题模型及有关概念运输问题
13、模型及有关概念21(1)设设 xab,xac,xdc,xde,xst,xsb 是一是一个闭回路，那么该闭回路中变量所对应个闭回路，那么该闭回路中变量所对应的系数列向量的系数列向量 pab,pac,pdc,pde,pst,psb 线性相关；线性相关；(2)若变量组若变量组 xab,xcd,xef,xst 中包含中包含一个部分组构成闭回路，那么该变量组一个部分组构成闭回路，那么该变量组所对应的系数列向量所对应的系数列向量 pab,pcd,pef,pst 线性相关。线性相关。根据上述结论以及线性规划基变量根据上述结论以及线性规划基变量的特点，可以得到下面重要定理及其推的特点，可以得到下面重要定理及其
14、推论。论。关于闭回路有如下的一些重要结论关于闭回路有如下的一些重要结论定理定理4.1 变量组变量组 xab,xcd,xef,xst 所所对应的系数列向量对应的系数列向量 pab,pcd,pef,pst 线性无关的充分必要条件是这个变量线性无关的充分必要条件是这个变量组中组中不包含闭回路不包含闭回路。推论推论 产销平衡运输问题的产销平衡运输问题的 m+n-1 个变量构成基变量的充分必要条件是个变量构成基变量的充分必要条件是它不含闭回路。它不含闭回路。这个推论给出了运输问题基本解这个推论给出了运输问题基本解的重要性质，也为寻求基本可行解提的重要性质，也为寻求基本可行解提供了依据。供了依据。4.1
15、4.1 运输问题模型及有关概念运输问题模型及有关概念4.2 4.2 运输问题求解运输问题求解表上作业法表上作业法 表上作业法求解运输问题的思想和表上作业法求解运输问题的思想和单纯形法完全类似：单纯形法完全类似：确定一个初始基本可行解确定一个初始基本可行解 根根据最优性判别准则来检查这个基本可行据最优性判别准则来检查这个基本可行解是不是最优的？解是不是最优的？如果是，则计算结束；如果是，则计算结束；如果不是，则进行换基。如果不是，则进行换基。直至求出最优解为止。直至求出最优解为止。244.24.2运输问题求解运输问题求解表上作业法表上作业法 一、初始基本可行解的确定一、初始基本可行解的确定 根据
16、上面的讨论，要求得运输问根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找题的初始基本可行解，必须保证找到到 m+n 1 个不构成闭回路的基变个不构成闭回路的基变量。量。一般的方法步骤如下：一般的方法步骤如下：254.24.2运输问题求解运输问题求解表上作业法表上作业法(1)在运输问题求解作业数据表中在运输问题求解作业数据表中任选任选一个单元格一个单元格 xij(Ai 行行 Bj 列交叉位置上列交叉位置上的格的格),令令 xij=min ai,bj 即从即从 Ai 向向 Bj 运最大量运最大量(使行或列使行或列在允许的范围内尽量饱和，即使一个在允许的范围内尽量饱和，即使一个约束方程得以
17、满足约束方程得以满足),填入填入 xij 的相应的相应位置；位置；26运输问题求解运输问题求解表上作业法表上作业法(2)从从 ai 和和 bj 中分别减去中分别减去 xij 的值，修的值，修正为新的正为新的ai 和和 bj 即调整即调整 Ai 的拥有量及的拥有量及 Bj 的需求量；的需求量；(3)若若 ai=0，则划去对应的行（已经，则划去对应的行（已经把拥有的量全部运走），若把拥有的量全部运走），若 bj=0 则划则划去对应的列（已经把需要的量全部运去对应的列（已经把需要的量全部运来），且每次只划去一行或一列（即每来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；次要去掉且只去掉
18、一个约束）；27运输问题求解运输问题求解表上作业法表上作业法(4)当最终的运输量选定时，其所在当最终的运输量选定时，其所在行、列同时满足，此时要同时划去行、列同时满足，此时要同时划去一行和一列。这样，运输平衡表中一行和一列。这样，运输平衡表中所有的行与列均被划去，则得到了所有的行与列均被划去，则得到了一个初始基本可行解。一个初始基本可行解。否则在剩下的运输平衡表中选下否则在剩下的运输平衡表中选下一个变量，返回一个变量，返回(1)。28上述计算过程可用流程图描述如下（图上述计算过程可用流程图描述如下（图4-2）取未划去的单元格取未划去的单元格xij,令令xij=min ai,bj ai=ai-x
19、ijbj=bj-xijai=0?划去第划去第i行行划去第划去第j列列是是否否 bj=0否否所有行列是所有行列是否均被划去否均被划去是是找到初始基找到初始基本可行解本可行解图图4-2 求运输问题的初始基本可行解过程求运输问题的初始基本可行解过程注：为了方便，这注：为了方便，这里总记剩余的产量里总记剩余的产量和销量为和销量为ai,bj294.24.2运输问题求解运输问题求解表上作业法表上作业法 按照上述方法所产生的一组变量的按照上述方法所产生的一组变量的取值将满足下面条件：取值将满足下面条件：(1)所得的变量均为非负，且变量所得的变量均为非负，且变量总数恰好为总数恰好为 m+n 1 个；个；(2)
20、所有的约束条件均得到满足；所有的约束条件均得到满足；(3)所得的变量不构成闭回路。所得的变量不构成闭回路。304.24.2运输问题求解运输问题求解表上作业法表上作业法 在上面的方法中，在上面的方法中，xij 的选取方的选取方法并没有给予限制，若采取不同的规法并没有给予限制，若采取不同的规则来选取则来选取 xij，则得到不同的方法，则得到不同的方法，较常用的方法有西北角法和最小元素较常用的方法有西北角法和最小元素法。下面分别举例予以说明法。下面分别举例予以说明。314.24.2运输问题求解运输问题求解表上作业法表上作业法 1 1、初始基本可行解的确定、初始基本可行解的确定 （1 1）西北角法）西
21、北角法：从西北角（左上：从西北角（左上角）格开始，在格内的右下角标上允角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得其他格划去。如此进行下去，直至得到一个基本可行解。到一个基本可行解。32 （2）最小元素法最小元素法：从运价最小：从运价最小的格开始，在格内的右下角标上允的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产到大
22、顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直的其他格划去。如此进行下去，直至得到一个基本可行解。至得到一个基本可行解。4.24.2运输问题求解运输问题求解表上作业法表上作业法33 注注:应用西北角法和最小元素应用西北角法和最小元素法，每次填完数，都只划去一行或法，每次填完数，都只划去一行或一列，只有一列，只有最后一个元例外最后一个元例外（同时（同时划去一行和一列）。当填上一个数划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）去一行（列），在保留的列
23、（行）中没被划去的格内标一个中没被划去的格内标一个0 0。4.24.2运输问题求解运输问题求解表上作业法表上作业法4.2运输问题求解运输问题求解表上作业法表上作业法354.2 运输问题求解运输问题求解表上作业法表上作业法364.24.2运输问题求解运输问题求解表上作业法表上作业法37 最优性检验就是检查所得到的方案最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最数都大于或等于零
24、时该调运方案就是最优方案；否则就不是最优，需要进行调优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法整。下面介绍两种求检验数的方法:闭闭回路法回路法和和位势法位势法二、基本可行解的最优性检验二、基本可行解的最优性检验 4.24.2运输问题求解运输问题求解表上作业法表上作业法381、闭回路法、闭回路法 为了方便，我们以表为了方便，我们以表1给出的初始基本可给出的初始基本可行解方案为例，考察初始方案的任意一个非行解方案为例，考察初始方案的任意一个非基变量，比如基变量，比如 x24。根据初始方案，产地。根据初始方案，产地 A2 的的产品是不运往销地产品是不运往销地 B4 的。如果现在
25、改变初始的。如果现在改变初始方案，把方案，把 A2 的产品运送的产品运送1 个单位给个单位给 B4，那么，那么为了保持产销平衡，就必须使为了保持产销平衡，就必须使 x14 或或 x34 减少减少 1 个单位；而如果个单位；而如果 x14 减少减少 1 个单位，第个单位，第 1 行行的运输量就必须增加的运输量就必须增加 1 个单位，例如个单位，例如 x13 增加增加 1 个单位，那么为了保持产销平衡，就必须使个单位，那么为了保持产销平衡，就必须使 x23 减少减少 1 个单位。个单位。4.24.2运输问题求解运输问题求解表上作业法表上作业法39 这个过程就是寻找一个以非基变量这个过程就是寻找一个
26、以非基变量x24为为起始顶点的闭回路起始顶点的闭回路x24，x14，x13，x23，这个闭回路的其他顶点均为基变量这个闭回路的其他顶点均为基变量(对应着对应着填上数字的格填上数字的格)。容易计算出上述调整使总。容易计算出上述调整使总的运输费用发生的变化为的运输费用发生的变化为 8 10+3 2 -1，即总的运费减少，即总的运费减少 1 个单位，这就说明原个单位，这就说明原始方案不是最优方案，可以进行调整以得到始方案不是最优方案，可以进行调整以得到更好的方案。更好的方案。4.24.2运输问题求解运输问题求解表上作业法表上作业法40 可以证明，如果对闭回路的方向不加区可以证明，如果对闭回路的方向不
27、加区别（即只要起点及其他所有顶点完全相同，别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯对每一个非基变量可以找到而且只能找到唯一的一个闭回路。一的一个闭回路。表表4-10中用虚线画出以非基变量中用虚线画出以非基变量 x22 为起为起始顶点的闭回路。始顶点的闭回路。4.24.2运输问题求解运输问题求解表上作业法表上作业法41表表4-10 以非基变量以非基变量 x22 为起始顶点的闭回路为起始顶点的闭回路销地销地产
28、地产地B1B2B3B4产量产量3 11 3 410 371 39 2 18 47 4 610 5 39销量销量365620(产销平衡产销平衡)A1A2A342 可以计算出以非基变量可以计算出以非基变量 x22 为起始为起始顶点的闭回路调整使总的运输费用发生顶点的闭回路调整使总的运输费用发生的变化为的变化为 9 2+3 10+5 4 1 即总的运费增加即总的运费增加 1 个单位，这就说明这个单位，这就说明这个调整不能改善目标值。个调整不能改善目标值。从上面的讨论可以看出，当某个非基从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量变量增加一个单位时，有若干个基变量的取值受其影响。
29、的取值受其影响。4.24.2运输问题求解运输问题求解表上作业法表上作业法43 这样，利用单位产品变化（运输这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也称这个方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的综合影响为该非基变量对应的检验数检验数。上面计算的两个非基变量的检验数为上面计算的两个非基变量的检验数为 24=-1，22=1。闭回路方法原理就是闭回路方法原理就是通过寻找闭回路来找到非基变量的检验通过寻找闭回路来找到非基变量的检验数。
30、数。4.24.2运输问题求解运输问题求解表上作业法表上作业法44 如果规定作为起始顶点的非基变量如果规定作为起始顶点的非基变量为第为第 1 个顶点，闭回路的其他顶点依次为个顶点，闭回路的其他顶点依次为第第 2 个顶点、第个顶点、第 3 个顶点个顶点那么就有那么就有 ij=(闭回路上的奇数次顶点单位运费之闭回路上的奇数次顶点单位运费之和和)-(闭回路上的偶数次顶点单位运费之闭回路上的偶数次顶点单位运费之和和)其中其中 ij 为非基变量的下角指标。为非基变量的下角指标。4.24.2运输问题求解运输问题求解表上作业法表上作业法45 按上述作法，可计算出表按上述作法，可计算出表1的所有非基的所有非基变
31、量的检验数，把它们填入相应位置的变量的检验数，把它们填入相应位置的方括号内，如图方括号内，如图4-11所示。所示。销地销地产地产地B1B2B3B4产量产量A13 111 23 410 37A21 39 12 18-14A37 104 610125 39销量销量365620(产销平衡产销平衡)表表4-11 初始基本可行解及检验数初始基本可行解及检验数46 显然，当所有非基变量的检验显然，当所有非基变量的检验数均大于或等于零时，现行的调运数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运行方案作任何调整都将导致总的运输费用增加。
32、输费用增加。闭回路法的闭回路法的主要缺点主要缺点是：当是：当变量个数较多时，寻找闭回路以及变量个数较多时，寻找闭回路以及计算两方面都会产生困难。计算两方面都会产生困难。4.24.2运输问题求解运输问题求解表上作业法表上作业法 2.2.位势法位势法 位势：设对应位势：设对应基变量基变量xij 的的 m+n-1 个个 ij，存在，存在ui,vj 满足满足 ui+vj=cij，i=1,2 ,m;j=1,2 ,n.称这些称这些 ui,vj 为该基本可行解对应的为该基本可行解对应的位势。位势。4.24.2运输问题求解运输问题求解表上作业法表上作业法48由于有由于有m+n 个变量（个变量（ui,vj），）
33、，m+n-1 个方程（基变量个数），个方程（基变量个数），故有一个自由变量，位势不唯一。故有一个自由变量，位势不唯一。利用位势求检验数：利用位势求检验数：ij=cij-ui-vj i=1,m;j=1,n4.2运输问题求解运输问题求解表上作业法表上作业法49前例，位势法求检验数：前例，位势法求检验数：step 1 从任意基变量对应的从任意基变量对应的 cij 开始开始,任任取取 ui 或或 vj，然后利用，然后利用cij=ui+vj 公式公式依次找出依次找出 m+n 个个 ui、vj,我们我们 从从 c14=10 开始开始 step 2 计算非基变量的检验数计算非基变量的检验数 ij=cij-u
34、i-vj；填入圆圈内；填入圆圈内4.2运输问题求解运输问题求解表上作业法表上作业法504.2运输问题求解运输问题求解表上作业法表上作业法51 当非基变量的检验数出现负当非基变量的检验数出现负值时，则表明当前的基本可行解不值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，新的基本可行解使目标函数值下降，这一过程通常称为这一过程通常称为换基换基(或主元变换或主元变换)过程过程。4.24.2运输问题求解运输问题求解表上作业法表上作业法三、求新的基本可行解三、求新的基本可
35、行解52 （1）选负检验数中最小者选负检验数中最小者 rk，那么，那么 xrk 为为主元，作为进基变量（上页图中主元，作为进基变量（上页图中 x24）;（2）以以 xrk 为起点找一条闭回路，除为起点找一条闭回路，除 xrk 外外其余顶点必须为基变量格（上页图中的回其余顶点必须为基变量格（上页图中的回路）路）;4.2运输问题求解运输问题求解表上作业法表上作业法 在运输问题的表上作业法中，换基的过程在运输问题的表上作业法中，换基的过程是如下进行：是如下进行：53（3）为闭回路的每一个顶点标号，为闭回路的每一个顶点标号，xrk 为为 1，沿一个方向（顺时针或逆时针），沿一个方向（顺时针或逆时针）依
36、次给各顶点标号；依次给各顶点标号；（4）求求 =Minxij xij对应闭回路上的对应闭回路上的偶数标号格偶数标号格=xpq 那么确定那么确定 xpq为出基为出基变量，变量，为调整量；为调整量；4.24.2运输问题求解运输问题求解表上作业法表上作业法54（5）对闭回路的各奇标号顶点调对闭回路的各奇标号顶点调整为：整为：xij+，对各偶标号顶点，对各偶标号顶点 调调整为：整为：xij-，特别，特别 xpq-=0，xpq变为非基变量。变为非基变量。重复重复(2)、(3)步，直到所有检验步，直到所有检验数均非负，得到最优解。数均非负，得到最优解。4.24.2运输问题求解运输问题求解表上作业法表上作业
37、法554.2运输问题求解运输问题求解表上作业法表上作业法 ij 0，得到，得到最优解最优解 x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余其余 xij=0;最优值最优值：f*=35+102+13+81+46+53=8556例题求解过程总结：例题求解过程总结：初始基本可行解初始基本可行解位势法求检验数：位势法求检验数：58 选择负检验数，找出闭回路，确定选择负检验数，找出闭回路，确定调整运输量调整运输量59 计算新的基本可行解，重新计算，检验计算新的基本可行解，重新计算，检验数均为非负，即得到最优解：数均为非负，即得到最优解：；最优值为；最优值为85850,3,6,
38、1,3,2,4343224211413 ijxxxxxxx其它其它60产销不平衡问题的处理产销不平衡问题的处理 实践中的运输问题常常非产销平衡，为下列实践中的运输问题常常非产销平衡，为下列的一般运输问题模型的一般运输问题模型njmixnjdxmisxtsxcfijmijijnjiijminjijij,.,2,1;,.,2,1,0,.,2,1,),(,.,2,1,)(.min1111 611.产量大于销量的情况产量大于销量的情况考虑考虑 si dj 情况，得到的数学模型为情况，得到的数学模型为njmixnjdxmisxtsxcfijmijijnjiijminjijij,.,2,1;,.,2,1,
39、0,.,2,1,.,2,1,.min1111 62 我们只须在模型中的产量限制约束我们只须在模型中的产量限制约束(前前m个不等式约束个不等式约束)中引入中引入m个松弛变量个松弛变量xin+1 i=1,2,m 即可，变为：即可，变为：xij+xin+1=si i=1,2,m 然后，需设一个销地然后，需设一个销地 Bn+1,它的销量它的销量为：为：dn+1=si -dj 由于实际不运送由于实际不运送,它们的运费为它们的运费为 cin+1=0 i=1,2,m。于是，这个运输问题就转化成了一于是，这个运输问题就转化成了一个产销平衡的问题个产销平衡的问题63 B1 B2 B3 产产量量 A1 6 4 6
40、 300 A2 6 5 5 300 销销量量 150 150 200 例例4.3 某公司从两个产地某公司从两个产地A1、A2将物品运往三个将物品运往三个销地销地B1、B2、B3，各产地的产量、各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运费如下表所示，问：应如何调运可使总运输费用最小？输费用最小？64 解：增加一个虚设的销地运输费用解：增加一个虚设的销地运输费用为为0 0652.销量大于产量的情况销量大于产量的情况考虑考虑 si dj 情况，得到的数学模型为情况，得到的数学模型为njmixnjdxmisx
41、tsxcfijmijijnjiijminjijij,.,2,1;,.,2,1,0,.,2,1,.,2,1,.min1111 66 我们只须在模型中的销量限制约束我们只须在模型中的销量限制约束(后后n个不等式约束个不等式约束)中引入中引入n个松弛变量个松弛变量xm+1j j=1,2,n 即可，变为：即可，变为：xij+xm+1j=dj j=1,2,n然后，需设一个销地然后，需设一个销地 BAm+1,它的它的c产量产量为：为：dm+1=dj -si 由于实际不运送由于实际不运送,它们的运费为它们的运费为 cm+1j=0 j=1,2,n。于是，这个运输问题就转化成了一于是，这个运输问题就转化成了一个
42、产销平衡的问题个产销平衡的问题67 某公司从两个产地某公司从两个产地A1、A2将物品运往三将物品运往三个销地个销地B1、B2、B3，各产地的产量、各，各产地的产量、各销地的销量和各产地运往各销地每件物销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运品的运费如下表所示，问：应如何调运可使总运输费用最小？可使总运输费用最小？例例4.468解：增加一个虚设的产地运输费用为解：增加一个虚设的产地运输费用为0 04.3 运输问题的应用运输问题的应用例例4.5:某研究院有三个区。每年分别需要用某研究院有三个区。每年分别需要用煤煤3000、1000、2000吨，由河北临城、山西盂吨，由河
43、北临城、山西盂县两处煤矿供应，价格、质量相同。供应能力县两处煤矿供应，价格、质量相同。供应能力分别为分别为1500、4000吨，运价如下表。由于需求吨，运价如下表。由于需求大于供给，经研究提出，大于供给，经研究提出，1区供应量可减少区供应量可减少0300吨，吨，2区必须满足需求量，区必须满足需求量，3区供应量不少区供应量不少于于1700吨，试求总费用为最低的调运方案。吨，试求总费用为最低的调运方案。70 解解:根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表：取取 M 代表一个很大的正数，其作用是强迫相代表一个很大的正数，其作用是强迫相应的应的 x31、x33、x34取值为取值为
44、0。71例例4.6:设有设有A、B、C三个化肥厂供应三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效四个地区的农用化肥。假设效果相同，有关数据如下表。试求总果相同，有关数据如下表。试求总费用为费用为最低最低的化肥调拨方案。的化肥调拨方案。72首先，作出产销平衡运价表首先，作出产销平衡运价表:最低要求必须满最低要求必须满足，因此把相应的虚设产地运费取为足，因此把相应的虚设产地运费取为M；最；最高要求与最低要求的差允许按需要安排，因高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为此把相应的虚设产地运费取为 0。对应。对应 4”的的销量销量 50 是考虑问题本身适当取的数据，根
45、据是考虑问题本身适当取的数据，根据产销平衡要求确定产销平衡要求确定 D的产量为的产量为 50。解：解：生产与储存问题生产与储存问题例例4.7:某厂按合同规定须于当年每个季度末分某厂按合同规定须于当年每个季度末分别提供别提供10、15、25、20台同一规格的柴油机。台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费交货，每台每积压一个季度需储存、维护等费用用0.15 万元。试求在完成合同的情况下，使该万元。试求在完成合同的情况下
46、，使该厂全年生产总费用为最小的决策方案厂全年生产总费用为最小的决策方案交货：交货：生产：生产：x11 =10 x11+x12+x13+x14 25x12+x22 =15 x22+x23+x24 35x13+x23+x33 =25 x33+x34 30 x14+x24+x34+x44=20 x44 10解：解：设设 xij 为第为第 i 季度生产的第季度生产的第 j 季度交季度交货的柴油机数目，那么应满足货的柴油机数目，那么应满足把第把第 i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i 个生产个生产厂的产量；把第厂的产量；把第 j 季度交货的柴油机数目看作季度交货的柴油机数目看作第
47、第 j 个销售点的销量；成本加储存、维护等费个销售点的销量；成本加储存、维护等费用看作运费。用看作运费。可构造下列产销平衡问题：可构造下列产销平衡问题：目标函数：目标函数：Min f=10.8x11+10.95x12+11.1x13+11.25 x14+11.1 x22+11.25 x23+11.4 x24 +11.0 x33+11.15 x34 +11.3 x44 76转运问题转运问题:实践中，还会有转运站，那么常出现的运实践中，还会有转运站，那么常出现的运输方式就会有：输方式就会有：产地产地转运站、转运站转运站、转运站销地、产地销地、产地产地、产地产地、产地销地、销地销地、销地转运站、销地
48、转运站、销地产地等。产地等。为此，可把有输出时称为此，可把有输出时称发点发点、有输入时称有输入时称收点收点。此时，产地、销地与转运站均可视为此时，产地、销地与转运站均可视为既是发点又是收点，于是有如下关系既是发点又是收点，于是有如下关系 产地：产地：输出量输出量-输入量输入量=产量产量 转运站：输入量转运站：输入量-输出量输出量=0 销地：销地：输入量输入量-输出量输出量=销量销量77例例4.7:某仪器公司在大连和广州有两个分某仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产厂生产同一种仪器，大连分厂每月生产450台台,广州分厂每月生产广州分厂每月生产600台。该公司台。该公司在
49、上海和天津有两个销售公司负责对南在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？调运仪器，可使总运输费用最低？78图中图中 1 广州、广州、2 大连、大连、3 上海、上海、4 天津、天津、5 南京、南京、6 济南、济南、7 南昌、南昌、8 青岛青岛79 设设 xij 为从为从 i 到到 j 的运输量，可得到的运
50、输量，可得到有下列特点的线性规划模型：有下列特点的线性规划模型：目标函数：目标函数：Min f=所有可能的运输费所有可能的运输费用用（运输单价与运输量乘积之和）（运输单价与运输量乘积之和）约束条件：产地、销地与转运站的运约束条件：产地、销地与转运站的运输限制输限制 产地产地 i ：输出量：输出量-输入量输入量=产量产量 转运站：输入量转运站：输入量-输出量输出量=0 销地销地 j ：输入量：输入量-输出量输出量=销量销量解：解：80s.t.x13+x14 600 (广州分厂供应量限制）广州分厂供应量限制）x23+x24+x28 450(大连分厂供应量限制）大连分厂供应量限制）-x13-x23+
