线性规划运输问题

线性规划运输问题第1页/共93页2主要内容运输问题的特点及模型描述网络图线性规划模型表上作业表上作业法平衡运输问题不平衡运输问题第2页/共93页3一、运输问题的特点及模型原问题：产地到销地之间运送货物的最佳路径特点：多个产地和多个销地；每个产地的产量不同，每个销地的销量也不同；各产销两地之间的运价不同。目标合理组织调运，既满足各销地的要求，又使总的运输费用（或里程、时间等）最小。第3页/共93页4运输问题

设有同一种货物从m个出发地1，2，…，m运往n个到达地1，2，…，n。第i个出发地的供应量（Supply）为si（si≥0），第j个到达地的需求量（Demand）为dj（dj≥0）。每单位货物从产地i运到销地j的运价为Cij。求一个使总运费最小的运输方案。

123…n供应

1c11c1ns1

2c21成本

c2ns2

…cij……mcm1cmnsm

需求d1dn∑出发地到达地第4页/共93页5运输问题引例：设某电视机厂有三个分厂，生产同一种彩色电视机，供应该厂在市内的四个门市部销售。已知三个分厂的日生产能力分别是50，60，50台，四个门市部的日销量分别为40，40，60，20台。从各个分厂运往各门市部的运费如下表所示，试安排一个运费最低的运输计划。第5页/共93页6

门市部工厂1234供应量总计12397612359796711506050需求量总计40406020160单位：元/台第6页/共93页7

2321341s2=60s3=50d1=40d2=40d3=60d4=20s1=50供应量供应地运价需求量需求地91296737765911运输问题网络图第7页/共93页8运输问题线性规划模型设xij为由第i个工厂运到第j个门市部的电视机台数，cij为由第i个工厂运到第j个门市部的运费，则原运输问题的线性规划模型为：第8页/共93页9MinZ=9x11+12x12+9x13+6x14+7x21+3x22+7x23+7x24+6x31+5x32+9x33+11x34x11+x12+x13+x14=50x21+x22+x23+x24=60s.t.x31+x32+x33+x34=50x11+x21+x31=40x12+x22+x32=40x13+x23+x33=60x14+x24+x34=20xij≥0i=1,2,3;j=1,2,3,4供应地约束需求地约束m×n个变量，m+n个条件第9页/共93页运输问题的表格表示1234供应量19129650X11X12X13X142737760X21X22X23X2436591150X31X32X33X34需求量40406020xijcij第10页/共93页11运输问题

三类运输问题：产销平衡：产大于销：产小于销：第11页/共93页12运输问题产销平衡的运输问题模型令xij为从i地运到j地的数量

MinZ=（Cij≥0)

（i=1,2,…,m)供应约束

(j=1,2,…,n)需求约束

xij≥0，i=1,1,…,m;j=1,2,…,n

由cij、si、dj

组成的（m+1)×(n+1)矩阵称为运输矩阵第12页/共93页13约束方程共有m+n个，由于∑si=∑dj，因此约束方程只有m+n-1个方程是线性独立的。因此运输问题的基本可行解有m+n-1个分量。第13页/共93页14引例——方程组中方程的线性独立问题：

x1+x2+x3=32x1+x2+x4=63x1+2x2+x3+x4=9系数的增广矩阵为：

111031110321016→210163214900000第14页/共93页15运输问题产大于销时约束条件

（j=1,2,…,n)

产小于销时约束条件

（i=1,2,…,m)（i=1,2,…,m)（j=1,2,…,n)产销不平衡的运输问题模型第15页/共93页16不平衡的运输问题

门市部工厂123供应量总计1297123975060需求量总计404060第16页/共93页17平衡运输问题的表上作业法(一)运输问题初始可行解的获得西北角法——从西北角的第一格开始安排运输计划具体步骤第17页/共93页18平衡运输问题的表上作业法具体步骤取其相应的供应量和需求量中的最小值作为初始基本可行解的第一个分量如果第一个工厂的生产量大于第一个销售点的需求，那么就由第一个工厂全部满足第一个销售点的需要，工厂商品的剩余部分运八第二个销售点；如果第一个工厂的生产量小于第一个销售点的需求量，则先将第一个工厂的全部产品运往第一个销售点，不足的需求由第二个补足。第18页/共93页19产地销地x11,x12,x22,x23,x33,x346个变量构成一个基本初始可行解。1234供应量19129650273776036591150需求量404060204010303030201030303020第19页/共93页20西北解法的特点优点：简单易行，容易得到基本初始可行解；缺点：没有考虑运费的因素，因此距离最优解较远。第20页/共93页21最小元素法（最小费用法）：“就近供应”从单位运价表中选取最低运价的空格开始供求分配：当供应量大于需求量，取值为需求量，划去该空格所在的列当供应量小于需求量，取值为供应量，划去该空格所在的行重复上述步骤，直到把所有的空格都划去为止。如果这样选出的空格共有m+n-1个，则构成一个初始基本可行解。第21页/共93页22初始可行解的获得前例中：最小元素法求初始解1234si19129650273776036591150dj4040602020103020404020301040100000000第22页/共93页伏格尔法思路：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而，对差额最大处，就应当采用最小运费调运。第23页/共93页步骤：

1.分别计算各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行；2.从行或列差额中选出最大者，选择它所在行或列中的最小元素；3.对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第1、2步。直至给出初始解为止。第24页/共93页销地产地B1B2B3B4行差额A13113100A219281A3741051列差额2513例：P80（表3-3，3-4）。表中B2列是最大差额所在列，B2列中最小元素为4，可确定A3的产品先供应B2的需要。同时将运价表的B2列数字划去。第25页/共93页销地产地B1B2B3B4产量A17A24A369销量3656第26页/共93页销地产地B1B2B3B4行差额A13113100A219281A3741052列差额213第27页/共93页销地产地B1B2B3B4产量A1527A2314A3639销量3656第28页/共93页伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比最小元素法给出的初始解更接近最优解。第29页/共93页30最优解检验(二)最优解检验依旧是根据检验数ij的值来判断其是否为最优解。方法有两种：位势法闭回路法第30页/共93页31位势法：假设每一行都有一个位势，记为ui,每一列有一个位势，记为vj，它们有如下关系：如果xij是基变量，则有cij-ui-vj=0如果是非基变量，则有：cij-ui-vj=σij由于基变量有m+n-1个，位势有m+n个，我们可以从m+n个位势变量中任设其中一个为任意值，就可以求出其他位势值，进而求得检验数ij

。第31页/共93页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第32页/共93页33进一步，求得各非基变量的检验数：13=c13-u1-v3=9-0-16=-714=c14-u1-v4=6-0-18=-1221=c21-u2-v1=7-(-9)-9=724=c24-u2-v4=7-(-9)-18=-231=c31-u3-v1=6-(-7)-9=432=c32-u3-v2=5-(-7)-12=0具体计算过程在表中进行第33页/共93页34位势及检验数的计算注：格子中，带数字为基本可行解，不带数字为检验数1234ui19129627377365911vj0401030303020-9-71816129-12-7740-2第34页/共93页35闭回路法一个可以作为表上作业法初始方案的表中，共有m+n-1个实格和mn-(m+n-1)个空格。从一个空格出发，沿水平或竖直方向前进，遇到一个适当的实格时按与前进方向垂直的方向前进，再遇到适当的实格时再转向前进，这样继续转向和前进若干次后必然回到原来出发的那个空格，这就形成一条由水平线段和竖直线段所组成的封闭折线，称之为闭回路。第35页/共93页36闭回路的性质：m+n-1个变量构成基变量的充要条件是它不含闭回路在m+n-1个基变量(实格，也称为基格)中加入任何一个非基变量，则加入空格后的m+n个格子必含有惟一的闭回路第36页/共93页37在闭回路中，转向之处称为顶点。从空格算起第奇数转向的称为奇数顶点，第偶数次转向的称为偶数顶点。定义空格所对应的非基变量xij的检验数为：ij=奇数顶点的运价之和-偶数顶点的运价之和其中表示对“奇数顶点”上的元素取和，表示对“偶数顶点”上的元素取和。现在用前例的初始方案表作为例子加以说明。第37页/共93页38利用闭回路法求检验数1234供应量19129650273776036591150需求量40406020401030303020-126+3+9-12-7-11=-12

77+12-9-3=7

40

-2-7第38页/共93页39最优判定法则表上作业法的最优判定法则是：一个可以直接作为表上作业法的初始方案的调运方案，如果它所有的检验数均为非负数，则这个方案是最优的。第39页/共93页40检验数的含义检验数ij的意义：对任意空格施行如下变换(称为变换E)：在它闭回路的奇转角点上增加1单位物资，而在偶转角点上减少1单位物资。易见，经变换E后方案仍是平衡的。一般地，ij就是施行变换E时总运费的增加量。如果某一空格的ij<0，那么对施行变换E时空格变为实格，总运费将减少(-ij)单位。第40页/共93页41检验数的含义1234供应量19129650273776036591150需求量40406020-12740-2-740103030302021=(7+12)-(3+9)=713=(9+3)-(12+7)=-7第41页/共93页42闭回路调整对存在负检验数的方案必须进行调整，调整方法如下：(1)选取调入空格。任何检验数为负数的空格都可作为调入空格。如果有多个检验数为负的空格，一般选取绝对值最大的格。(2)选取调出实格。调出实格在调整后的新方案中将成为空格。调出实格可选择这样的实格：在调入空格闭回路的各个偶转角点中运量最小的格。如果有多个这样的实格，任选其一。(3)调整。设所选调出实格的运量为P(称为调整量)，则在调入空格闭回路的各偶转角点的运量都减少P，各奇转角点的运量都增加P，得到新方案。(4)计算新方案检验数后判定是否为最优方案，若还不是，重复上述步骤。第42页/共93页431234ui191296027377-9365911-7vj9121618401030303020-12-7740-2第43页/共93页441234ui19129602737733659115vj904640402040105-5-80-2101210第44页/共93页451234ui19129602737733659115vj904640402040105-5-80-21012第45页/共93页461234ui19129627377365911vj4040204010-338061041020300-5-398126第46页/共93页471234ui191296027377-5365911-3vj9812630402040-3380641020第47页/共93页481234ui19129627377365911vj030402040-2069563503710203401030第48页/共93页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第49页/共93页50由于非基变量的检验数为0，以该格的变量为换入变量，继续迭代还可以求得另一组最优解：第50页/共93页511234ui19129627377365911vj04020-20695635037203401030第51页/共93页52相应的运费为：9×30＋6×20＋3×30＋7×30＋6×40＋5×10＝9801234ui19129627377365911vj03030-206956353720340030100第52页/共93页53解的退化问题基本可行解中的一个或数个分量为0。此时，基本可行解的非零分量数目少于m+n-1个，无法再用位势法或闭回路法计算检验数。第53页/共93页54解的退化问题解决的办法：将退化为零的两个空格中的任一个填入一个零，把它当成退化的基本解，然后按以前的步骤进行迭代计算。应当注意的是，零要加在不可估值的空格中：可估值空格：能构成闭回路不可估值空格：不能构成闭回路第54页/共93页5512si1873026920dj2030201020产地销地-412si1873026920dj20303020产地销地12si1873026920dj203003020产地销地12si1873026920dj203020300产地销地第55页/共93页5612345si1769355282357635410695dj2352423511400不可估值空格可估值空格产地销地第56页/共93页57平衡运输问题解题步骤小结列出关于供给、需求及运费的表格寻找初始基本可行解西北角法最小费用法伏格尔法求检验数位势法闭回路法解的最优性检验对解进行闭回路调整（如果必要）第57页/共93页58产销不平衡运输问题的表上作业产大于销：设立虚拟的销地产小于销：设立虚拟的产地第58页/共93页59运输模型的活用例1.6－2求以下运输问题的初始解B1B2B3产量A11236A26548需求432149

这是一个产大于销的问题，差额为5。表上作业是假想一个销地B0,需求量为5，从A1,A2到B0的运价为0。这样就将此转化为产销平衡问题。第59页/共93页60产大于销B1B2B3B0产量A112306A265408需求432514第60页/共93页61计算过程：B1B2B3B0siuiA112306A265408dj432514vj42215216503121-3223第61页/共93页62产小于销例：某农场获得大丰收，四块土地A1、A2、A3、A4的产量分别2、3、4、6千吨。现在准备把这批粮食贮藏到B1,B2,B3等3个仓库里，已知这三个仓库的最大容量分别为7、5、7千吨，每块土地和各仓库的距离如下表所示，试求出最合理的调运方案。(距离以公里为单位)第62页/共93页63距离B1B2B3产量A121072A211383A33214A44926最大容量7571519第63页/共93页64产小于销距离B1B2B3产量A121072A211383A33214A44926A00004最大容量75719第64页/共93页65123siui121072211383332144492650004dj75719vj432332235322第65页/共93页66123siui121072211383332144492650004dj75719vj4323322022-2210187780-152第66页/共93页67123siui121072211383332144492650004dj75719vj25231420第67页/共93页68123siui1210720972113832763321410449262650004-212dj75719vj2102523142第68页/共93页69得最优调运方案：x11=2,x22=3,x32=2,x33=2,x41=1,x43=5,x51=4第69页/共93页70例：设有三个化肥厂，供应四个地区的农用化肥。除第四个地区不宜用第三个厂生产的化肥外，假定各厂的化肥在这些地区使用的效果是一样的。各化肥厂的年产量、各地区的年需要量以及各化肥厂到各地区运送化肥的单价如下表，试求总费用最少的化肥调拨方案。第70页/共93页71

需求地化肥厂1234产量(万吨)1231614191313202219231715M506050最低需求量（万吨）3070010最高需求量（万吨）507030不限第71页/共93页72解，这个问题要解决如下几个难点：第四个地区的最大需求量应该等于各厂在供给其他地区的最低需求后的最大剩余量：

160-(30+70+0)=60产量小于最大需求量，应该设立一个虚拟的产地（第四个产地），其产量为供需之间的缺口：

210-160=50由于第一个地区存在最低需求和最高需求，我们将其需求量视为两个部分，第一个为必须满足的，意味着该部分的需求不能从虚拟产地获得，因此我们设从虚拟产地向第一地区第一部分供给的运输费用为大M，而第二个部分则既可从实产地获得，也可以从虚产地获得。其他地区类似处理，得下表：第72页/共93页73

需求地化肥厂1234产量(万吨)IIIIII1234（虚）161419M1614190131320M22192301715MM1715M050605050需求量(万吨)302070301050第73页/共93页741234siuiIIIIII11616132217175002141413191515600319192023MM5054(虚)M0M0M050-17dj302070301050vj14141318M-51750203010103010500220M+33M+4-122M-224-M+22-M+20-221第74页/共93页751234siuiIIIIII11616132217175002141413191515600319192023MM50M-154(虚)M0M0M050-17dj302070301050vj14-M+3413-M+381517502030203010500M-182-M+20M+3M-17M+4M-21M+2-2M-162-2-M+22M-19M-200第75页/共93页761234siuiIIIIII11616132217175002141413191515600319192023MM5054(虚)M0M0M050-17dj302070301050vj14141318151750203020301050022M+33M+4-1M+2M-2242-221002M-20第76页/共93页771234siuiIIIIII11616132217175002141413191515600319192023MM5054(虚)M0M0M050-15dj302070301050vj14141318151550203020301050022M+11M+2-3MM-204221002M-20第77页/共93页781234siuiIIIIII11616132217175002141413191515600319192023MM5084(虚)M0M0M050-15dj302070301050vj111113151515502020010203055M+11M+2MM-20724330-1M-23303第78页/共93页791234siuiIIIIII11616132217175002141413191515600319192023MM5074(虚)M0M0M050-15dj302070301050vj121213151515最优502020010203044M+33M+2MM-22724230M-223021第79页/共93页80下面是将需求地4看成一个整体来求解的情形原因：虚产地的最大产量是50万吨，而第四个地区的最大需求量是60万吨，所以该地区至少可以从其他三个实产地获得10万吨，以满足该地区的最低需求量（也即最低需求量能够得到满足）第80页/共93页811234siuiIII1161613221750021414131915600319192023M5054(虚)M0M0M50M-5dj3020703060vj14141318M-5502030101030102209-M-9-8-M-134-M+22-M+202150第81页/共93页821234siuiIII1161613221750021414131915600319192023M5054(虚)M0M0M50-M+5dj3020703060vj141413M-5M-5502030101030402202M-19M-192M-18-M+27-M+22-M+202-M+2420-