运筹学运输问题

1第四章运输问题•运输问题与有关概念•运输问题的求解—表上作业法•运输问题应用—建模本章内容重点21.运输问题模型及有关概念问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。31.运输问题模型及有关概念例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？4解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：1.运输问题模型及有关概念5Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）1.运输问题模型及有关概念6111000000111100100010010001001系数矩阵1.运输问题模型及有关概念7模型系数矩阵特征1.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。1.运输问题模型及有关概念8一般运输问题的线性规划模型及求解思路一般运输问题的提法：假设A1,A2,…,Am表示某物资的m个产地；B1,B2,…,Bn表示某物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价（表4-3）。如果s1+s2+…+sm=d1+d2+…+dn则称该运输问题为产销平衡问题；否则，称产销不平衡。首先讨论产销平衡问题。1.运输问题模型及有关概念9表4-3运输问题数据表1.运输问题模型及有关概念销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇sm销量d1d2…dn设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表（表4-4）。10表4-4运输问题变量表1.运输问题模型及有关概念销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmns1s2┇sm销量d1d2…dn11mnMinf=cijxij（4-1）i=1j=1ns.t.xijsii=1,2,…,m（4-2）j=1mxij(=,)djj=1,2,…,n（4-3）i=1xij0(i=1,2,…,m;j=1,2,…,n)（4-4）1.运输问题模型及有关概念于是得到下列一般运输问题的模型：在模型（4-1）—（4-4）中，式（4-2）为m个产地的产量约束；式（4-3）为n个销地的销量约束。12mnMinf=cijxiji=1j=1ns.t.xij=sii=1,2,…,m(4-5)j=1mxij=djj=1,2,…,n(4-6)i=1xij≥0(i=1,2,…,m;j=1,2,…,n)1.运输问题模型及有关概念对于产销平衡问题，可得到下列运输问题的模型：13在产销平衡问题中，仔细观察式（4-2）、（4-3）分别变为（4-5）、（4-6），约束条件成为等式。在实际问题建模时，还会出现如下一些变化：（1）有时目标函数求最大，如求利润最大或营业额最大等；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；1.运输问题模型及有关概念14(3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（4-2）每一式中加上1个松弛变量，共m个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（4-3）每一式中加上1个松弛变量，共n个。1.运输问题模型及有关概念15运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图4-1所示。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。在这里需要讨论基本可行解、检验数以及基的转换等问题。1.运输问题模型及有关概念161.运输问题模型及有关概念基本可行解是否最优解结束换基是否图4-1运输问题的求解思路17运输问题求解的有关概念考虑产销平衡问题，由于我们关心的量均在表4-3与表4-4中，因此考虑把表4-3与表4-4合成一个表,如下表4-5表4-5运输问题求解作业数据表(下页）1.运输问题模型及有关概念181.运输问题模型及有关概念销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1na1A2c21x21c22x22…c2nx2na2┇┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnam销量b1b2…bn19运输问题的基变量共有m+n-1个，A的秩为m+n-1。运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路。重要概念:闭回路、闭回路的顶点特点运输问题基变量的1.运输问题模型及有关概念20定义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各不相同，我们称之为变量集合的一个闭回路，并将式（4-7）、式（4-8）中的变量称为这个闭回路的顶点。为了说明这个特征，我们不加证明的给出一些概念和结论。下面的讨论建立在表4-5中决策变量格的基础上。1.运输问题模型及有关概念21例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x21；x11,x14,x34,x31等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：1.运输问题模型及有关概念闭回路示意图22根据定义可以看出闭回路的一些明显特点：(1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；(2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。1.运输问题模型及有关概念23关于闭回路有如下的一些重要结论：(1)设xab,xac,xdc,xde,…,xst,xsb是一个闭回路，那么该闭回路中变量所对应的系数列向量pab,pac,pdc,pde,…,pst,psb线性相关；(2)若变量组xab,xcd,xef,…,xst中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量pab,pcd,pef,…,pst线性相关。根据上述结论以及线性规划基变量的特点，可以得到下面重要定理及其推论。1.运输问题模型及有关概念24定理4.1变量组xab,xcd,xef,…,xst所对应的系数列向量pab,pcd,pef,…,pst线性无关的充分必要条件是这个变量组中不包含闭回路。推论产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是它不含闭回路。这个推论给出了运输问题基本解的重要性质，也为寻求基本可行解提供了依据。1.运输问题模型及有关概念252.运输问题求解—表上作业法上一节已经分析了，对于产销平衡问题，我们关心的量均可以表示在表4-5中。因此可以建立基于表4-5的求解运输问题的方法——表上作业法。这里求解运输问题的思想和单纯形法完全类似，即首先确定一个初始基本可行解，然后根据最优性判别准则来检查这个基本可行解是不是最优的。如果是则计算结束；如果不是，则进行换基，直至求出最优解为止。262.运输问题求解—表上作业法一、初始基本可行解的确定根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到m+n–1个不构成闭回路的基变量。一般的方法步骤如下：(1)在运输问题求解作业数据表中任选一个单元格xij(Ai行Bj列交叉位置上的格),令xij=min{ai,bj}272.运输问题求解—表上作业法即从Ai向Bj运最大量(使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足),填入xij的相应位置；(2)从ai或bj中分别减去xij的值，即调整Ai的拥有量及Bj的需求量；282.运输问题求解—表上作业法(3)若ai=0，则划去对应的行（把拥有的量全部运走），若bj=0则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；(4)若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量，转(4)。29上述计算过程可用流程图描述如下（图4-2）取未划去的单元格xij,令xij=min{ai,bj}ai’=ai-xijbj’=bj-xijai’=0?划去第i行划去第j列是否bj’=0否所有行列是否均被划去是找到初始基本可行解图4-2求运输问题的初始基本可行解过程302.运输问题求解—表上作业法按照上述方法所产生的一组变量的取值将满足下面条件：(1)所得的变量均为非负，且变量总数恰好为m+n–1个；(2)所有的约束条件均得到满足；(3)所得的变量不构成闭回路。312.运输问题求解—表上作业法因此，根据定理4.1及其推论，所得的解一定是运输问题的基本可行解。在上面的方法中，xij的选取方法并没有给予限制，若采取不同的规则来选取xij，则得到不同的方法，较常用的方法有西北角法和最小元素法。下面分别举例予以说明。322.运输问题求解—表上作业法1、初始基本可行解的确定（1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。33（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。2.运输问题求解—表上作业法34注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。2.运输问题求解—表上作业法352.运输问题求解—表上作业法表1362.运输问题求解—表上作业法372.运输问题求解—表上作业法38最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法。二、基本可行解的最优性检验2.运输问题求解—表上作业法391、闭回路法为了方便，我们以表1给出的初始基本可行解方案为例，考察初始方案的任意一个非基变量，比如x24。根据初始方案，产地A2的产品是不运往销地B4的。如果现在改变初始方案，把A2的产品运送1个单位给B4，那么为了保持产销平衡，就必须使x14或x34减少1个单位；而如果x14减少1个单位，第1行的运输量就必须增加1个单位，例如x13增加1个单位，那么为了保持产销平衡，就必须使x23减少1个单位。2.运输问题求解—表上作业法40这个过程就是寻找一个以非基变量x24为起始顶点的闭回路——{x24，x14，x13，x23}，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为8–10+3–2＝-1，即总的运费减少1个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。2.运输问题求解—表上作业法41可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯