线性规划运输问题教育课件.ppt

第二级,第三级,第四级,第五级,*,第四章 线性规划的扩展(II),第二级,第三级,第四级,第五级,第四章 线性规划的扩展(II),*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性规划运输问题PPT讲座,2,主要内容,运输问题的特点及模型描述,网络图,线性规划模型,表上作业,表上作业法,平衡运输问题,不平衡运输问题,3,一、运输问题的特点及模型,原问题：,产地到销地之间运送货物的最佳路径,特点：,多个产地和多个销地；,每个产地的产量不同，每个销地的销量也不同各产销两地之间的运价不同。,目标,合理组织调运，既满足各销地的要求，又使总的运输费用（或里程、时间等）最小。,4,运输问题,设有同一种货物从,m,个出发地,1,，,2,，,，,m,运往,n,个到达地,1,，,2,，,，,n,。第,i,个出发地的供应量（,Supply,）为,s,i,（,s,i,0,），第,j,个到达地的需求量（,Demand,）为,d,j,（,d,j,0,）。每单位货物从产地,i,运到销地,j,的运价为,C,ij,。求一个使总运费最小的运输方案。,1 2 3 n,供应,1 c,11,c,1n,s,1,2 c,21,成本,c,2n,s,2,c,ij,m c,m1,c,mn,sm,需求,d,1,d,n,出,发,地,到达地,5,运输问题,引例：设某电视机厂有三个分厂，生产同一种彩色电视机，供应该厂在市内的四个门市部销售。已知三个分厂的日生产能力分别是,50,，,60,，,50,台，四个门市部的日销量分别为,40,，,40,，,60,，,20,台。从各个分厂运往各门市部的运费如下表所示，试安排一个运费最低的运输计划。,6,门市部,工厂,1,2,3,4,供应量总计,1,2,3,9,7,6,12,3,5,9,7,9,6,7,11,50,60,50,需求量总计,40,40,60,20,160,单位：元,/,台,7,2,3,2,1,3,4,1,s,2,=60,s,3,=50,d,1,=40,d,2,=40,d,3,=60,d,4,=20,s,1,=50,供应量,供应地,运价,需求量,需求地,9,12,9,6,7,3,7,7,6,5,9,11,运输问题网络图,8,运输问题线性规划模型,设,x,ij,为由第,i,个工厂运到第,j,个门市部的电视机台数，,c,ij,为由第,i,个工厂运到第,j,个门市部的运费，则原运输问题的线性规划模型为：,9,Min,Z=,9x,11,+12x,12,+9x,13,+6x,14,+7x,21,+3x,22,+7x,23,+7x,24,+6x,31,+5x,32,+9x,33,+11x,34,x,11,+x,12,+x,13,+x,1450,x,21,+x,22,+x,23,+x,24,=60,s.t.,x,31,+x,32,+x,33,+x,34,=50,x,11,+x,21,+x,31,=40,x,12,+x,22,+x,32,=40,x,13,+x,23,+x,33,=60,x,14,+x,24,+x,34,=20,x,ij,0,i=,1,2,3;,j=1,2,3,4,供应地约束,需求地约束,mn,个变量，,m+n,个条件,运输问题的表格表示,1,2,3,4,供应量,1,9,12,9,6,50,X,11,X,12,X,13,X,14,2,7,3,7,7,60,X,21,X,22,X,23,X,24,3,6,5,9,11,50,X,31,X,32,X,33,X,34,需求量,40,40,60,20,x,ij,c,ij,11,运输问题,三类运输问题：,产销平衡：,产大于销：,产小于销：,12,运输问题,产销平衡的运输问题模型,令,x,ij,为 从,i,地运到,j,地的数量,Min Z=,（,C,ij,0,),（,i=1,2,m),供应约束,(j=1,2,n),需求约束,x,ij,0,，,i=1,1,m;j=1,2,n,由,c,ij,、,s,i,、,d,j,组成的（,m+1)(n+1),矩阵,称为运输矩阵,13,约束方程共有,m+n,个，由于,s,i,=d,j,，因此约束方程只有,m+n-1,个方程是线性独立的。因此运输问题的基本可行解有,m+n-1,个分量。,14,引例,方程组中方程的线性独立问题：,x,1,+x,2,+x,3,=3,2x,1,+x,2,+x,4,=6,3x,1,+2x,2,+x,3,+x,4,=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),产小于销时约束条件,（,i=1,2,m),（,i=1,2,m),（,j=1,2,n),产销不平衡的运输问题模型,16,不平衡的运输问题,门市部,工 厂,1,2,3,供应量总计,1,2,9,7,12,3,9,7,50,60,需求量总计,40,40,60,17,平衡运输问题的表上作业法,(,一,),运输问题初始可行解的获得,西北角法,从西北角的第一格开始安排运输计划,具体步骤,18,平衡运输问题的表上作业法,具体步骤,取其相应的供应量和需求量中的最小值作为初始基本可行解的第一个分量,如果第一个工厂的生产量大于第一个销售点的需求，那么就由第一个工厂全部满足第一个销售点的需要，工厂商品的剩余部分运八第二个销售点；,如果第一个工厂的生产量小于第一个销售点的需求量，则先将第一个工厂的全部产品运往第一个销售点，不足的需求由第二个补足。,19,产,地,销地,x,11,x,12,x,22,x,23,x,33,x,34,6,个变量构成一个基本初始可行解。,1,2,3,4,供应量,1,9,12,9,6,50,2,7,3,7,7,60,3,6,5,9,11,50,需求量,40,40,60,20,40,10,30,30,30,20,10,30,30,30,20,20,西北解法的特点,优点：简单易行，容易得到基本初始可行解；,缺点：没有考虑运费的因素，因此距离最优解较远。,21,最小元素法,（最小费用法）,：“就近供应”,从单位运价表中选取最低运价的空格开始供求分配：,当供应量大于需求量，取值为需求量，划去该空格所在的列,当供应量小于需求量，取值为供应量，划去该空格所在的行,重复上述步骤，直到把所有的空格都划去为止。,如果这样选出的空格共有,m+n-1,个，则构成一个初始基本可行解。,22,初始可行解的获得,前例中：最小元素法求初始解,1,2,3,4,s,i,1,9,12,9,6,50,2,7,3,7,7,60,3,6,5,9,11,50,d,j,40,40,60,20,20,10,30,20,40,40,20,30,10,40,10,0,0,0,0,0,0,0,伏格尔法,思路：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而，对差额最大处，就应当采用最小运费调运。,步骤：,1.,分别计算各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行；,2.,从行或列差额中选出最大者，选择它所在行或列中的最小元素；,3.,对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第,1,、,2,步。直至给出初始解为止。,销地,产地,B,1,B,2,B,3,B,4,行差额,A,1,3,11,3,10,0,A,2,1,9,2,8,1,A,3,7,4,10,5,1,列差额,2,5,1,3,例：,P80,（表,3-3,，,3-4,）。表中,B,2,列是最大差额所在列，,B,2,列中最小元素为,4,，可确定,A,3,的产品先供应,B,2,的需要。同时将运价表的,B,2,列数字划去。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,6,9,销量,3,6,5,6,销地,产地,B,1,B,2,B,3,B,4,行差额,A,1,3,11,3,10,0,A,2,1,9,2,8,1,A,3,7,4,10,5,2,列差额,2,1,3,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,5,2,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比最小元素法给出的初始解更接近最优解。,30,最优解检验,(,二,),最优解检验依旧是根据检验数,ij,的值来判断其是否为最优解。方法有两种：,位势法,闭回路法,31,位势法：假设每一行都有一个位势，记为,u,i,每一列有一个位势，记为,v,j,，它们有如下关系：,如果,x,ij,是基变量，则有,c,ij,-u,i,-v,j,=0,如果是非基变量，则有：,c,ij,-u,i,-v,j,=,ij,由于基变量有,m+n-1,个，位势有,m+n,个，我们可以从,m+n,个位势变量中任设其中一个为任意值，就可以求出其他位势值，进而求得检验数,ij,。,32,位势的计算过程如下：,设,u,1,=0,由,c,11,-u,1,-v,1,=0,v,1,=c,11,=9,由,c,12,-u,1,-v,2,=0,v,2,=c,12,=12,由,c,22,-u,2,-v,2,=0,u,2,=c,22,-v,2,=-9,由,c,23,-u,2,-v,3,=0,v,3,=c,23,-u,2,=16,由,c,33,-u,3,-v,3,=0,u,3,=,c,33,-v,3,=-7,由,c,34,-u,3,-v,4,=0,v,4,=,c,34,-u,3,=18,33,进一步，求得各非基变量的检验数：,13,=c,13,-u,1,-v,3,=9-0-16=-7,14,=c,14,-u,1,-v,4,=6-0-18=-12,21,=c,21,-u,2,-v,1,=7-(-9)-9=7,24,=c,24,-u,2,-v,4,=7-(-9)-18=-2,31,=c,31,-u,3,-v,1,=6-(-7)-9=4,32,=c,32,-u,3,-v,2,=5-(-7)-12=0,具体计算过程在表中进行,34,位势及检验数的计算,注：格子中，带,数字,为基本可行解，不带,数字,为检验数,1,2,3,4,u,i,1,9,12,9,6,2,7,3,7,7,3,6,5,9,11,v,j,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)个,空格,。从一个空格出发，沿水平或竖直方向前进，遇到一个适当的,实格,时按与前进方向,垂直,的方向前进，再遇到适当的,实格,时再,转向,前进，这样继续转向和前进若干次后必然回到原来出发的那个,空格,，这就形成一条由水平线段和竖直线段所组成的封闭折线，称之为,闭回路,。,36,闭回路的性质：,m+n-1,个变量构成基变量的充要条件是它不含闭回路,在,m+n-1,个基变量,(,实格，也称为基格,),中加入任何一个非基变量，则加入空格后的,m+n,个格子必含有惟一的闭回路,37,在闭回路中，转向之处称为顶点。从空格算起第奇数转向的称为,奇数顶点,，第偶数次转向的称为,偶数顶点,。,定义空格所对应的非基变量,x,ij,的,检验数,为：,ij,=,奇数顶点的运价之和,-,偶数顶点的运价之和,其中 表示对“奇数顶点”上的元素取和，表示对“偶数顶点”上的元素取和。,现在用前例的初始方案表作为例子加以说明。,38,利用闭回路法求检验数,1,2,3,4,供应量,1,9,12,9,6,50,2,7,3,7,7,60,3,6,5,9,11,50,需求量,40,40,60,20,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,，那么对施行变换,E,时空格变为实格，总运费将减少,(-,ij,),单位。,41,检验数的含义,1,2,3,4,供应量,1,9,12,9,6,50,2,7,3,7,7,60,3,6,5,9,11,50,需求量,40,40,60,20,-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),调整。设所选调出实格的运量为,P(,称为调整量,),，则在调入空格闭回路的各偶转角点的运量都减少,P,，各奇转角点的运量都增加,P,，得到新方案。,(4),计算新方案检验数后判定是否为最优方案，若还不是，重复上述步骤。,43,1,2,3,4,u,i,1,9,12,9,6,0,2,7,3,7,7,-9,3,6,5,9,11,-7,v,j,9,12,16,18,40,10,30,30,30,20,-12,-7,7,4,0,-2,44,1,2,3,4,u,i,1,9,12,9,6,0,2,7,3,7,7,3,3,6,5,9,11,5,v,j,9,0,4,6,40,40,20,40,10,5,-5,-8,0,-2,10,12,10,45,1,2,3,4,u,i,1,9,12,9,6,0,2,7,3,7,7,3,3,6,5,9,11,5,v,j,9,0,4,6,40,40,20,40,10,5,-5,-8,0,-2,10,12,46,1,2,3,4,u,i,1,9,12,9,6,2,7,3,7,7,3,6,5,9,11,v,j,40,40,20,40,10,-3,3,8,0,6,10,4,10,20,30,0,-5,-3,9,8,12,6,47,1,2,3,4,u,i,1,9,12,9,6,0,2,7,3,7,7,-5,3,6,5,9,11,-3,v,j,9,8,12,6,30,40,20,40,-3,3,8,0,6,4,10,20,48,1,2,3,4,u,i,1,9,12,9,6,2,7,3,7,7,3,6,5,9,11,v,j,0,30,40,20,40,-2,0,6,9,5,6,3,5,0,3,7,10,20,3,40,10,30,49,此时，所有空格内的检验数都已非负，表明上述解就是最优解。,即：,x,13,=30,x,12,=20,x,22,=40,x,23,=20,x,31,=40,x,33,=10,这种最优方案的运费为：,Z,min,=9*30+6*20+3*40+7*20+6*40+9*10,=980,50,由于非基变量的检验数为,0,，以该格的变量为换入变量，继续迭代还可以求得另一组最优解：,51,1,2,3,4,u,i,1,9,12,9,6,2,7,3,7,7,3,6,5,9,11,v,j,0,40,20,-2,0,6,9,5,6,3,5,0,3,7,20,3,40,10,30,52,相应的运费为：,930,620,330,730,640,510,980,1,2,3,4,u,i,1,9,12,9,6,2,7,3,7,7,3,6,5,9,11,v,j,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,1,2,s,i,1,8,7,30,2,6,9,20,d,j,20,30,20,10,20,产地,销地,-4,1,2,s,i,1,8,7,30,2,6,9,20,d,j,20,30,30,20,产地,销地,1,2,s,i,1,8,7,30,2,6,9,20,d,j,20,30,0,30,20,产地,销地,1,2,s,i,1,8,7,30,2,6,9,20,d,j,20,30,20,30,0,产地,销地,56,1,2,3,4,5,s,i,1,7,6,9,3,5,5,2,8,2,3,5,7,6,3,5,4,10,6,9,5,d,j,2,3,5,2,4,2,3,5,1,1,4,0,0,不可估值空格,可估值空格,产地,销地,57,平衡运输问题解题步骤小结,列出关于供给、需求及运费的表格,寻找初始基本可行解,西北角法,最小费用法,伏格尔法,求检验数,位势法,闭回路法,解的最优性检验,对解进行闭回路调整（如果必要）,58,产销不平衡运输问题的表上作业,产大于销：设立虚拟的销地,产小于销：设立虚拟的产地,59,运输模型的活用,例,1.6,2,求以下运输问题的初始解,B,1,B,2,B,3,产量,A,1,1,2,3,6,A,2,6,5,4,8,需求,4,32,14,9,这是一个产大于销,的问题，差额为,5,。,表上作业是假想一个,销地,B,0,需求量为,5,，,从,A,1,A,2,到,B,0,的运价,为,0,。这样就将此转,化为产销平衡问题。,60,产大于销,B,1,B,2,B,3,B,0,产量,A,1,1,2,3,0,6,A,2,6,5,4,0,8,需求,4,3,2,5,14,61,计算过程：,B,1,B,2,B,3,B,0,s,i,u,i,A,1,1,2,3,0,6,A,2,6,5,4,0,8,d,j,4,3,2,5,14,v,j,4,2,2,1,5,2,1,6,5,0,3,1,2,1,-3,2,2,3,62,产小于销,例：某农场获得大丰收，四块土地,A,1,、,A,2,、,A,3,、,A,4,的产量分别,2,、,3,、,4,、,6,千吨。现在准备把这批粮食贮藏到,B,1,B,2,B,3,等,3,个仓库里，已知这三个仓库的最大容量分别为,7,、,5,、,7,千吨，每块土地和各仓库的距离如下表所示，试求出最合理的调运方案。,(,距离以公里为单位,),63,距离,B,1,B,2,B,3,产量,A,1,2,10,7,2,A,2,11,3,8,3,A,3,3,2,1,4,A,4,4,9,2,6,最大容量,7,5,7,15,19,64,产小于销,距离,B,1,B,2,B,3,产量,A,1,2,10,7,2,A,2,11,3,8,3,A,3,3,2,1,4,A,4,4,9,2,6,A,0,0,0,0,4,最大容量,7,5,7,19,65,1,2,3,s,i,u,i,1,2,10,7,2,2,11,3,8,3,3,3,2,1,4,4,4,9,2,6,5,0,0,0,4,d,j,7,5,7,19,v,j,4,3,2,3,3,2,2,3,5,3,2,2,66,1,2,3,s,i,u,i,1,2,10,7,2,2,11,3,8,3,3,3,2,1,4,4,4,9,2,6,5,0,0,0,4,d,j,7,5,7,19,v,j,4,3,2,3,3,2,2,0,2,2,-2,2,1,0,1,8,7,7,8,0,-1,5,2,67,1,2,3s,i,u,i,1,2,10,7,2,2,11,3,8,3,3,3,2,1,4,4,4,9,2,6,5,0,0,0,4,d,j,7,5,7,19,v,j,2,5,2,3,1,4,2,0,68,1,2,3,s,i,u,i,1,2,10,7,2,0,9,7,2,11,3,8,3,2,7,6,3,3,2,1,4,1,0,4,4,9,2,6,2,6,5,0,0,0,4,-2,1,2,d,j,7,5,7,19,v,j,2,1,0,2,5,2,3,1,4,2,69,得最优调运方案：,x,11,=2,x,22,=3,x,32,=2,x,33,=2,x,41,=1,x,43,=5,x,51,=4,70,例：设有三个化肥厂，供应四个地区的农用化肥。除第四个地区不宜用第三个厂生产的化肥外，假定各厂的化肥在这些地区使用的效果是一样的。各化肥厂的年产量、各地区的年需要量以及各化肥厂到各地区运送化肥的单价如下表，试求总费用最少的化肥调拨方案。,71,需求地,化肥厂,1,2,3,4,产量,(,万吨,),1,2,3,16,14,19,13,13,20,22,19,23,17,15,M,50,60,50,最低需求量（万吨）,30,70,0,10,最高需求量（万吨）,50,70,30,不限,72,解，这个问题要解决如下几个难点：,第四个地区的最大需求量应该等于各厂在供给其他地区的最低需求后的最大剩余量：,160-30+70+0)=60,产量小于最大需求量，应该设立一个虚拟的产地（第四个产地），其产量为供需之间的缺口：,210-160=50,由于第一个地区存在最低需求和最高需求，我们将其需求量视为两个部分，第一个为必须满足的，意味着该部分的需求不能从虚拟产地获得，因此我们设从虚拟产地向第一地区第一部分供给的运输费用为大,M,，而第二个部分则既可从实产地获得，也可以从虚产地获得。其他地区类似处理，得下表：,73,需求地,化肥厂,1,2,3,4,产量,(,万吨,),I,II,I,II,1,2,3,4,（虚）,16,14,19,M,16,14,19,0,13,13,20,M,22,19,23,0,17,15M,M,17,15,M,0,50,60,50,50,需求量,(,万吨,),30,20,70,30,10,50,74,1,2,3,4,s,i,u,i,I,II,I,II,1,16,16,13,22,17,17,50,0,2,14,14,13,19,15,15,60,0,3,19,19,20,23,M,M,50,5,4(,虚,),M,0,M,0,M,0,50,-17,d,j,30,20,70,30,10,50,v,j,14,14,13,18,M-5,17,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,21,75,1,2,3,4,s,i,u,i,I,II,I,II,1,16,16,13,22,17,17,50,0,2,14,14,13,19,15,15,60,0,3,19,19,20,23,M,M,50,M-15,4(,虚,),M,0,M,0,M,0,50,-17,d,j,30,20,70,30,10,50,v,j,14,-M+34,13,-M+38,15,17,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,M-19,M-20,0,76,1,2,3,4,s,i,u,i,I,II,I,II,1,16,16,13,22,17,17,50,0,2,14,14,13,19,15,15,60,0,3,19,19,20,23,M,M,50,5,4(,虚,),M,0,M,0,M,0,50,-17,d,j,30,20,70,30,10,50,v,j,14,14,13,18,15,17,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,1,2,3,4,s,i,u,i,I,II,I,II,1,16,16,13,22,17,17,50,0,2,14,14,13,19,15,15,60,0,3,19,19,20,23,M,M,50,5,4(,虚,),M,0,M,0,M,0,50,-15,d,j,30,20,70,30,10,50,v,j,14,14,13,18,15,15,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,1,2,3,4,s,i,u,i,I,II,I,II,1,16,16,13,22,17,17,50,0,2,14,14,13,19,15,15,60,0,3,19,19,20,23,M,M,50,8,4(,虚,),M,0,M,0,M,0,50,-15,d,j,30,20,70,30,1050,v,j,11,11,13,15,15,15,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,1,2,3,4,s,i,u,i,I,II,I,II,1,16,16,13,22,17,17,50,0,2,14,14,13,19,15,15,60,0,3,19,19,20,23,M,M,50,7,4(,虚,),M,0,M,0,M,0,50,-15,d,j,30,20,70,30,10,50,v,j,12,12,13,15,15,15,最优,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,万吨，以满足该地区的最低需求量（也即最低需求量能够得到满足）,81,1,2,3,4,s,i,u,i,I,II,1,16,16,13,22,17,50,0,2,14,14,13,19,15,60,0,3,19,19,20,23,M,50,5,4(,虚,),M,0,M,0,M,50,M-5,d,j,30,20,70,30,60,v,j,14,14,13,18,M-550,20,30,10,10,30,10,2,2,0,9,-M-9,-8,-M-13,4,-M+22,-M+20,2,1,50,82,1,2,3,4,s,i,u,i,I,II,1,16,16,13,22,17,50,0,2,14,14,13,19,15,60,0,3,19,19,20,23,M,50,5,4(,虚,),M,0,M,0,M,50,-M+5,d,j,30,20,70,30,60,v,j,14,14,13,M-5,M-5,50,20,30,10,10,30,40,2,2,0,2M-19,M-19,2M-18,-M+27,-M+22,-M+20,2,-M+24,20,-M+23,831,2,3,4,s,i,u,i,I,II,1,16,16,13,22,17,50,0,2,14,14,13,19,15,60,0,3,19,19,20,23,M,50,M-15,4(,虚,),M,0,M,0,M,50,-15,d,j,30,20,70,30,60,v,j,14,-M+34,13,15,15,50,20,30,20,30,30,M-18,2,-M+20,M+1,M-19,M+2,7,2,-M+22,4,20,-M+23,10,M-20,84,1,2,3,4,s,i,u,i,I,II,1,16,16,13,22,17,50,0,2,14,14,13,19,15,60,0,3,1919,20,23,M,50,5,4(,虚,),M,0,M,0,M,50,-15,d,j,30,20,70,30,60,v,j,14,14,13,15,15,最优,50,20,0,20,30,2,2,M+1,1,M+2,7,2,2,4,20,3,40,0,30,M-20,应用举例,例：某厂按合同规定须于当年每季度末分别提供,10,15,25,20,台同一规格的柴油机。已知该厂各季度的,生产能力,及生产每台柴油机的,成本,如下表所示，又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用,0.15,万元。要求在完成合同的情况下，作出使该厂每年生产（包括储存、维护）费用最小的决策。表3-29,季度,生产能力（台）,单位成本（万元）,1,25,10.8,2,35,11.1,3,30,11.0,4,10,11.3,解：设,x,ij,为第,i,季度生产的用于第,j,季度交货的柴油机数，则必须满足：,第,i,季度生产的用于第,j,季度交货的每台柴油机的实际成本,c,ij,应该是该季度,单位成本,加上,储存维护等费用,，故,c,ij,的具体数值可表示如下：,j,i,1,2,3,4,1,10.8,10.95,11.10,11.25,2,11.10,11.25,11.40,3,11.00,11.15,4,11.30,设用,a,ij,表示该厂第,i,季度的生产能力，,b,j,表示第,j,季度的合同供应量，则问题可写成：,Minz=,i=1,4,j=1,4,c,ij,x,ij,满足：,以上规划问题可看成一个产大于销的运输问题模型，需加上一个假想的需求,D,，以转化为平衡的产销运输模型，其产销平衡表和单位运价表如下：,j,i,1,2,3,4,D,产量,1,10.8,10.95,11.10,11.25,0,25,2,M,11.10,11.25,11.40,0,35,3,M,M,11.00,11.15,0,30,4,M,M,M,11.30,0,10,销量,10,15,25,20,30,100,计算结果为：,销售,j,生产,i,1,2,3,4,D,产量,1,10,15,0,25,2,5,30,35,3,20,10,30,4,10,10,销量,10,15,25,20,30,100,