第3章+线性规划(运输问题).ppt

1、1,第3章 运输问题,线性规划续,2,主要内容,运输问题的特点及模型描述 网络图 线性规划模型 表上作业 表上作业法 平衡运输问题 不平衡运输问题,3,一、运输问题的特点及模型,原问题：产地到销地之间运送货物的最佳路径 特点： 多个产地和多个销地； 每个产地的产量不同，每个销地的销量也不同； 各产销两地之间的运价不同。 目标 合理组织调运，既满足各销地的要求，又使总的运输费用（或里程、时间等）最小。,4,运输问题,设有同一种货物从m个出发地1，2，m运往n个到达地1，2，n。第i个出发地的供应量（Supply）为si（si0），第j个到达地的需求量（Demand）为 dj（dj0）。 每单位货

2、物从产地 i 运到销地 j 的运价为Cij。求一个使总运费最小的运输方案。 1 2 3 n 供应 1 c11 c1n s1 2 c21 成本 c2n s2 cij m cm1 cmn sm 需求 d1 dn ,出 发 地,到达地,5,运输问题,引例：设某电视机厂有三个分厂，生产同一种彩色电视机，供应该厂在市内的四个门市部销售。已知三个分厂的日生产能力分别是50，60，50台，四个门市部的日销量分别为40，40，60，20台。从各个分厂运往各门市部的运费如下表所示，试安排一个运费最低的运输计划。,6,单位：元/台,7,2,3,2,1,3,4,1,s2=60,s3=50,d1=40,d2=40,d

3、3=60,d4=20,s1=50,供应量,供应地,运价,需求量,需求地,9,12,9,6,7,3,7,7,6,5,9,11,运输问题网络图,8,运输问题线性规划模型,设xij为由第i个工厂运到第j个门市部的电视机台数，cij为由第i个工厂运到第j个门市部的运费，则原运输问题的线性规划模型为：,9,供应地约束,需求地约束,mn个变量，m+n个条件,运输问题的表格表示,xij,cij,11,运输问题,三类运输问题： 产销平衡： 产大于销： 产小于销：,12,运输问题,产销平衡的运输问题模型 令xij为 从i地运到j地的数量 Min Z = （Cij0) （i= 1,2,m) 供应约束 (j= 1,

4、2,n) 需求约束 xij0，i=1,1,m; j=1,2,n 由 cij、si、dj 组成的 （m+1)(n+1) 矩阵称为运输矩阵,13,约束方程共有m+n个，由于si=dj，因此约束方程只有m+n-1个方程是线性独立的。因此运输问题的基本可行解有m+n-1个分量。,14,引例方程组中方程的线性独立问题： x1+x2+x3=3 2x1+x2+x4=6 3x1+2x2+x3+x4=9 系数的增广矩阵为： 1 1 1 0 3 1 1 1 0 3 2 1 0 1 6 2 1 0 1 6 3 2 1 4 9 0 0 0 0 0,15,运输问题,产大于销时约束条件,（j= 1,2,n),产小于销时约

5、束条件,（i= 1,2,m),（i= 1,2,m),（j= 1,2,n),产销不平衡的运输问题模型,16,不平衡的运输问题,17,平衡运输问题的表上作业法,(一)运输问题初始可行解的获得 西北角法从西北角的第一格开始安排运输计划 具体步骤,18,平衡运输问题的表上作业法,具体步骤 取其相应的供应量和需求量中的最小值作为初始基本可行解的第一个分量 如果第一个工厂的生产量大于第一个销售点的需求，那么就由第一个工厂全部满足第一个销售点的需要，工厂商品的剩余部分运八第二个销售点； 如果第一个工厂的生产量小于第一个销售点的需求量，则先将第一个工厂的全部产品运往第一个销售点，不足的需求由第二个补足。,19

6、,产 地,销地,x11,x12,x22,x23,x33,x346个变量构成一个基本初始可行解。,40,10,30,30,30,20,10,30,30,30,20,20,西北解法的特点 优点：简单易行，容易得到基本初始可行解； 缺点：没有考虑运费的因素，因此距离最优解较远。,21,最小元素法（最小费用法）：“就近供应” 从单位运价表中选取最低运价的空格开始供求分配： 当供应量大于需求量，取值为需求量，划去该空格所在的列 当供应量小于需求量，取值为供应量，划去该空格所在的行 重复上述步骤，直到把所有的空格都划去为止。 如果这样选出的空格共有m+n-1个，则构成一个初始基本可行解。,22,初始可行解

7、的获得,前例中： 最小元素法求初始解,20,10,30,20,40,40,20,30,10,40,10,0,0,0,0,0,0,0,伏格尔法 思路：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而，对差额最大处，就应当采用最小运费调运。,步骤： 1. 分别计算各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行； 2. 从行或列差额中选出最大者，选择它所在行或列中的最小元素； 3. 对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第1、2步。直至给出

8、初始解为止。,例：P80（表3-3，3-4）。表中B2列是最大差额所在列，B2列中最小元素为4，可确定A3的产品先供应B2的需要。同时将运价表的B2列数字划去。,伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比最小元素法给出的初始解更接近最优解。,30,最优解检验,(二)最优解检验 依旧是根据检验数ij的值来判断其是否为最优解。方法有两种： 位势法 闭回路法,31,位势法：假设每一行都有一个位势，记为ui,每一列有一个位势，记为vj，它们有如下关系： 如果xij是基变量，则有 cij-ui-vj=0 如果是非基变量，则有： cij-ui-vj=ij 由于

9、基变量有m+n-1个，位势有m+n个，我们可以从m+n个位势变量中任设其中一个为任意值，就可以求出其他位势值，进而求得检验数ij 。,32,位势的计算过程如下： 设u1=0 由c11-u1-v1=0v1=c11=9 由c12-u1-v2=0v2=c12=12 由c22-u2-v2=0u2=c22-v2=-9 由c23-u2-v3=0v3=c23-u2=16 由c33-u3-v3=0u3=c33-v3=-7 由c34-u3-v4=0v4=c34-u3=18,33,进一步，求得各非基变量的检验数： 13 =c13-u1-v3=9-0-16=-7 14 =c14-u1-v4=6-0-18=-12 2

10、1 =c21-u2-v1=7-(-9)-9=7 24 =c24-u2-v4=7-(-9)-18=-2 31 =c31-u3-v1=6-(-7)-9=4 32 =c32-u3-v2=5-(-7)-12=0 具体计算过程在表中进行,34,位势及检验数的计算,注：格子中，带数字为基本可行解，不带数字为检验数,0,40,10,30,30,30,20,-9,-7,18,16,12,9,-12,-7,7,4,0,-2,35,闭回路法 一个可以作为表上作业法初始方案的表中，共有m+n-1个实格和mn-(m+n-1)个空格。从一个空格出发，沿水平或竖直方向前进，遇到一个适当的实格时按与前进方向垂直的方向前进，

11、再遇到适当的实格时再转向前进，这样继续转向和前进若干次后必然回到原来出发的那个空格，这就形成一条由水平线段和竖直线段所组成的封闭折线，称之为闭回路。,36,闭回路的性质： m+n-1个变量构成基变量的充要条件是它不含闭回路 在m+n-1个基变量(实格，也称为基格)中加入任何一个非基变量，则加入空格后的m+n个格子必含有惟一的闭回路,37,在闭回路中，转向之处称为顶点。从空格算起第奇数转向的称为奇数顶点，第偶数次转向的称为偶数顶点。 定义空格所对应的非基变量xij的检验数为： ij=奇数顶点的运价之和-偶数顶点的运价之和 其中 表示对“奇数顶点”上的元素取和， 表示对“偶数顶点”上的元素取和。

12、现在用前例的初始方案表作为例子加以说明。,38,利用闭回路法求检验数,40,10,30,30,30,20,-12,6+3+9-12-7-11=-12,7,7+12-9-3=7,4,0,-2,-7,39,最优判定法则,表上作业法的最优判定法则是：一个可以直接作为表上作业法的初始方案的调运方案，如果它所有的检验数均为非负数，则这个方案是最优的。,40,检验数的含义,检验数ij的意义： 对任意空格施行如下变换(称为变换E)：在它闭回路的奇转角点上增加1单位物资，而在偶转角点上减少1单位物资。易见，经变换E后方案仍是平衡的。 一般地， ij就是施行变换E时总运费的增加量。如果某一空格的ij 0，那么对

13、施行变换E时空格变为实格，总运费将减少(- ij)单位。,41,检验数的含义,-12,7,4,0,-2,-7,40,10,30,30,30,20,21=(7+12)-(3+9) =7,13=(9+3)-(12+7) =-7,42,闭回路调整,对存在负检验数的方案必须进行调整，调整方法如下： (1)选取调入空格。任何检验数为负数的空格都可作为调入空格。如果有多个检验数为负的空格，一般选取绝对值最大的格。 (2)选取调出实格。调出实格在调整后的新方案中将成为空格。调出实格可选择这样的实格：在调入空格闭回路的各个偶转角点中运量最小的格。如果有多个这样的实格，任选其一。 (3)调整。设所选调出实格的运

14、量为P(称为调整量)，则在调入空格闭回路的各偶转角点的运量都减少P，各奇转角点的运量都增加P，得到新方案。 (4)计算新方案检验数后判定是否为最优方案，若还不是，重复上述步骤。,43,40,10,30,30,30,20,-12,-7,7,4,0,-2,44,40,40,20,40,10,5,-5,-8,0,-2,10,12,10,45,40,40,20,40,10,5,-5,-8,0,-2,10,12,46,40,40,20,40,10,-3,3,8,0,6,10,4,10,20,30,0,-5,-3,9,8,12,6,47,30,40,20,40,-3,3,8,0,6,4,10,20,48,

15、0,30,40,20,40,-2,0,6,9,5,6,3,5,0,3,7,10,20,3,40,10,30,49,此时，所有空格内的检验数都已非负，表明上述解就是最优解。 即：x13=30,x12=20,x22=40,x23=20,x31=40,x33=10 这种最优方案的运费为： Zmin=9*30+6*20+3*40+7*20+6*40+9*10 =980,50,由于非基变量的检验数为0，以该格的变量为换入变量，继续迭代还可以求得另一组最优解：,51,0,40,20,-2,0,6,9,5,6,3,5,0,3,7,20,3,40,10,30,52,相应的运费为：930620330730640

16、510980,0,30,30,-2,0,6,9,5,6,3,5,3,7,20,3,40,0,30,10,0,53,解的退化问题,基本可行解中的一个或数个分量为0。此时，基本可行解的非零分量数目少于m+n-1个，无法再用位势法或闭回路法计算检验数。,54,解的退化问题,解决的办法：将退化为零的两个空格中的任一个填入一个零，把它当成退化的基本解，然后按以前的步骤进行迭代计算。 应当注意的是，零要加在不可估值的空格中： 可估值空格：能构成闭回路 不可估值空格：不能构成闭回路,55,20,10,20,产地,销地,-4,30,20,产地,销地,0,30,20,产地,销地,20,30,0,产地,销地,56

17、,2,3,5,1,1,4,0,0,不可估值空格,可估值空格,产地,销地,57,平衡运输问题解题步骤小结,列出关于供给、需求及运费的表格 寻找初始基本可行解 西北角法 最小费用法 伏格尔法 求检验数 位势法 闭回路法 解的最优性检验 对解进行闭回路调整（如果必要）,58,产销不平衡运输问题的表上作业,产大于销：设立虚拟的销地 产小于销：设立虚拟的产地,59,运输模型的活用,例1.62 求以下运输问题的初始解,这是一个产大于销 的问题，差额为5。 表上作业是假想一个 销地B0,需求量为5， 从A1,A2到B0的运价 为0。这样就将此转 化为产销平衡问题。,60,产大于销,61,计算过程：,4,2,

18、2,1,5,2,1,6,5,0,3,1,2,1,-3,2,2,3,62,产小于销,例：某农场获得大丰收，四块土地A1、A2、A3、A4的产量分别2、3、4、6千吨。现在准备把这批粮食贮藏到B1,B2,B3等3个仓库里，已知这三个仓库的最大容量分别为7、5、7千吨，每块土地和各仓库的距离如下表所示，试求出最合理的调运方案。(距离以公里为单位),63,64,产小于销,65,4,3,2,3,3,2,2,3,5,3,2,2,66,4,3,2,3,3,2,2,0,2,2,-2,2,1,0,1,8,7,7,8,0,-1,5,2,67,2,5,2,3,1,4,2,0,68,2,5,2,3,1,4,2,69,

19、得最优调运方案： x11=2, x22=3, x32=2, x33=2, x41=1, x43=5, x51=4,70,例：设有三个化肥厂，供应四个地区的农用化肥。除第四个地区不宜用第三个厂生产的化肥外，假定各厂的化肥在这些地区使用的效果是一样的。各化肥厂的年产量、各地区的年需要量以及各化肥厂到各地区运送化肥的单价如下表，试求总费用最少的化肥调拨方案。,71,72,解，这个问题要解决如下几个难点： 第四个地区的最大需求量应该等于各厂在供给其他地区的最低需求后的最大剩余量： 160-(30+70+0)=60 产量小于最大需求量，应该设立一个虚拟的产地（第四个产地），其产量为供需之间的缺口： 21

20、0-160=50 由于第一个地区存在最低需求和最高需求，我们将其需求量视为两个部分，第一个为必须满足的，意味着该部分的需求不能从虚拟产地获得，因此我们设从虚拟产地向第一地区第一部分供给的运输费用为大M，而第二个部分则既可从实产地获得，也可以从虚产地获得。其他地区类似处理，得下表：,73,74,50,20,30,10,10,30,10,50,0,2,2,0,M+3,3,M+4,-1,22,M-22,4,-M+22,-M+20,-2,2,1,75,50,20,30,20,30,10,50,0,M-18,2,-M+20,M+3,M-17,M+4,M-21,M+2,-2,M-16,2,-2,-M+22

21、,M-19,M-20,0,76,50,20,30,20,30,10,50,0,2,2,M+3,3,M+4,-1,M+2,M-22,4,2,-2,2,1,0,0,2,M-20,77,50,20,30,20,30,10,50,0,2,2,M+1,1,M+2,-3,M,M-20,4,2,2,1,0,0,2,M-20,78,50,20,20,0,10,20,30,5,5,M+1,1,M+2,M,M-20,7,2,4,3,30,-1,M-23,30,3,79,50,20,20,0,10,20,30,4,4,M+3,3,M+2,M,M-22,7,2,4,2,30,M-22,30,2,1,80,下面是将需求地4看成一个整体来求解的情形 原因：虚产地的最大产量是50万吨，而第四个地区的最大需求量是60万吨，所以该地区至少可以从其他三个实产地获得10万吨，以满足该地区的