运筹学基础运输问题PPT课件

1,第三章运输问题,运输问题是线性规划问题的特例。是在几个供应点与几个需求点之间，运输品种、规格、质量等相同的货物时，选择最佳的运输方案，以达到总的运输费用最低或获利的利润最大等目标,产地：货物发出的地点。,销地：货物接收的地点。,产量：各产地的可供货量。,销量：各销地的需求数量。,运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。,2,例1：某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,第一节运输模型,一、运输问题举例,3,运输问题的LP模型,(1)决策变量：设从Ai到Bj的运输量为xij，,x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3,销售平衡条件,供应平衡条件,x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4,非负性约束,xij0(i=1,2,3；j=1,2,3,4),(2)目标函数,(3)约束条件：产量之和等于销量之和,故要满足：,minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34,4,例2：某公司下属三个工厂（甲厂、乙厂、丙厂）生产同类产品，供应不同地区的3个城市（A城、B城、C城），工厂的供应量、城市的需求量及工厂到不同城市的单件运费如表，写出本例数学模型,运输问题举例（续）,5,运输问题的LP模型,(1)决策变量：设从i厂到j地的供应量为xij，,x11+x12+x136000 x21+x22+x234000 x31+x32+x3310000,销售平衡条件,供应平衡条件,x11+x21+x31=5000 x12+x22+x32=7500 x13+x23+x33=7500,非负性约束,xij0(i=1,2,3；j=1,2,3,4),(2)目标函数,minZ=8x11+6x12+7x13+4x21+3x22+5x23+7x31+4x32+6x33,(3)约束条件：产量之和大于销量之和,故要满足：,6,二、表式运输模型,运价表,单位运价,7,产销平衡表,运量,8,运输模型表合二为一,求xij=?,9,三、运输问题的三种类型,产销平衡,10,产大于销,11,产小于销,12,第二节运输问题的求解方法表上作业法,表上作业法适合于产销平衡的运输问题,求解步骤：,建立运输模型表找出初始方案：（一般来说这个方案不是最优的）最优性检验方案调整与改进,13,例1：设有一采石公司，它有3个采石厂：W厂、X厂、Y厂，它们每周的采石能力（供应量）如下：W厂56车/周，X厂82车/周，Y厂为77车/周；三个采石厂每周的供应量总和为215车。该采石公司已与某筑路公司订阅了供应石子的合同。筑路公司现有3个工程段：A段、B段、C段；3个工程段每周的石子需要量如下：A段为72车/周，B段为102车/周，C段为41车/周，三个工程段每周的石子需要量总和为215车。现求一个最佳的运输方案，以达到运输费用最低的目的。,一、建立运输模型图,14,二、确定初始的运输方案,最小元素法:最小运费“就近运给”,从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量minai,bj。,最大差额法（伏格尔法）:次小运费“就近运给”,各行(各列)的最小运费与次小运费之差称为行差(列查)。差额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。,西北角法:,从运输图的西北角出发，将第一行的供应量先分配给第一列，当供应量需求量，剩余往第二列分；当供应量需求量，不够的由第二行分配，以此类推。,15,1、西北角法,（1）从运输图的西北角出发，将第一行（W厂）的供应量先分配给第一列（A段），当W厂的供应量A段的需求量，剩余往第二列（B段）分，由西往东分配，直至W厂供应量全部分完为止；,（2）当W厂的全部供应量A段的需求量时，不够的转由第二行（X厂）分配，将X厂的部分或全部先分配给A段，以初中A段的短缺数量，若有剩余，再往B段分配，如此等等。,16,西北角法图示,56,16,66,36,41,初始基可行解：x11=56,x21=16,x22=66,x32=36,x33=41,（3）检查最初的运输方案图，看是否都已满足，即得到一初始解,（4）有数字的格叫数字格或石方格，其数目mn1，无数字的格叫空格或无石方格,此时运费Z=31240,本题有5个,17,注：石方格数目mn1的原因,可验证其秩为5，9个决策变量中有5个基变量，4个非基变量（非基变量在解中取值为零），所以只有5个变量得到数字解。,x11+x12+x13=56x21+x22+x23=82x31+x32+x33=77x11+x21+x31=72x12+x22+x32=102x13+x23+x33=41,按线性规划来说，产销平衡可列出6个约束方程,行平衡,列平衡,18,（5）将数字格中数字用圆圈圈上，用虚线从上到下，从左到右联接起来，形成一个台阶，此法也叫阶石法或登石法。,（6）最初运输方案的总运输费为：Z=31240（未必最优，还需判断）,19,另例：,56,0,82,20,57,用0占位，保证有数字的数目mn1,特点：找初始解很简单容易，但收敛速度很慢，调整的计算量过大,20,2、最小元素法（获得初始方案的另一种方法）,从单位运价表中逐次挑选最小元素，安排运量minai,bj。然后，划去该元素所在行或列：,当产大于销，划去该元素所在列；,当产小于销，划去该元素所在行。,61,41,41,56,16,初始可行解：x11=56,x31=16,x22=41,x32=61,x23=41,此时运费Z=25800,21,另例：,77,25,57,56,0,初始可行解：x11=56,x31=0,x22=25,x32=77,x23=57,优点：找初始解也很容易，距最优解近，计算量小得多，缺点：额外造成多运费,22,3、伏格尔法,一产地的产品如不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明如不能按最小运费调动，运费增加就越多，为避免损失，因而对差额最大处，就应当采用最小运费调运，其步骤是：,(1)计算差额,56,46,31,41,41,初始可行解：x12=56,x21=41,x23=41,x31=31,x23=46,此时运费Z=21810,(2)分配运量,23,另例,初始可行解：x12=2,x13=1,x14=2，x24=2,x31=2，x3,2=1,1,2,1,2,2,2,优点：距最优解更近，计算量小得多，常替代最优解缺点：找初始解不容易，,此时运费Z=34,24,三、判定是否最优及改进,阶石法闭合回路法,修正分配法位势法,如何判定初始方案是否最优，如果不是最优将能否调整，具体方法如下：,25,(一)闭回路法判定是否最优,闭回路法是指寻求一条闭合的改进路线，求出改进指数。,改进路线：,是指从某一个空格开始，所寻求的那一条企图改变原来的运输方案的路线，即闭合回路。,改进指数：,是指循着改进路线，当货物的运输量作一个单位的变化时，会引起总运输费用的改变量。用来判定改进路线的优劣。,闭回路法的步骤,(1)对每个空格求改进路线（闭合回路）和改进指数,(2)将改进路线画在运输图上,(3)计算改进指数,26,闭回路的画法,闭回路,以空格为始点和终点，其余顶点均为数字格的封闭回路。,闭回路的画法：,从空格开始，用水平或垂直线向前划，每碰到一个数字格转90，继续前进，直到返回始点。,奇偶点：,始点是偶点，依次奇偶相间标注；偶点标“”，表示运量增加运量；奇点标“”，表示减少运量。,27,改进路线和改进指数寻求方法图示,本例有四个空格：WB、WC、XC、YA,因而有四个改进方案,28,寻求WB格的改进路线,注：这种改进方法，无论从水平或垂直方向调整，都必须有增有减,改进路线WB,WB,XB,XA,WA,费用改变量WB70元240元120元40元90元,-90,29,寻求WC格的改进路线,改进路线WC,WC,YC,YB,XB,费用改变量WC140元160元130元240元120元40元50元,XA,XA,-90,-50,30,寻求XC格的改进路线,改进路线XC,XC,YC,YB,XB,费用改变量XC110元240元130元160元160元,-90,-50,-160,31,寻求YA格的改进路线,改进路线YA,YA,XA,XB,YB,费用改变量YA80元120元240元130元70元,-90,-50,-160,70,以XC空格的改进指数160为绝对值最大，寻求XC空格的闭合改进路线LXC,32,（二）闭合回路调整法建立改进方案,确定调整格,IWB90元，IWC50元，IXC160元，IYA70元,挑选XC格为调整格，因为这样节减的运输费用最大,确定调整路线,LXCXCYCYBXB,确定调整运量,挑选负号格（即减少运量格）的最小运量为调整运量，以保证改进路线上所有各格才能合理调整,注：1）改进后，原做为出发点的空格变为数字格，运输量最小的数字格变为空格，仍然保持数字格数目行数列数1,2）在改进路线中，除了出发点的空格外，不能再有其它空格，否则就会出现数字格数目行数列数1,如不满足怎么办,33,1、调整运输方案（西北角法）,56,16,66,36,41,41,41,77,25,第二个运输方案：x11=56,x21=16,x22=25,x32=77,x23=41,此时运费Z=24680,初始运费Z=31240,调整量为41,34,2、判定是否最优,56,16,41,77,25,IWB70元240元120元40元90元,寻求WB格的改进路线,-90,35,寻求WC格的改进路线,56,16,41,77,25,IWC140元110元120元40元110元,-90,110,36,寻求YC格的改进路线,56,16,41,77,25,IYC160元130元240元110元160元,-90,110,160,37,寻求YA格的改进路线,56,16,41,77,25,IYA80元120元240元130元70元,-90,110,70,160,以WB空格的改进指数90为绝对值最大，寻求WB空格的闭合改进路线LWB,38,3、调整运输方案（得第二方案）,56,16,41,77,25,25,16,41,56,31,第三个运输方案：x11=31,x21=41,x12=25,x32=77,x23=41,此时运费Z=22430,25,此时运费Z=24680,调整量为25,39,4、再次判定是否最优,41,77,25,41,31,IWC140元110元120元40元110元,寻求WC格的改进路线,110,40,寻求XB格的改进路线,41,77,25,41,31,IXB240元120元40元70元90元,110,90,41,寻求YA格的改进路线,41,77,25,41,31,IYA80元40元70元130元20元,110,90,-20,42,寻求YC格的改进路线,41,77,25,41,31,IYC160元130元70元40元120元110元70元,110,70,90,-20,以YA空格的改进指数20为绝对值最大，寻求YA空格的闭合改进路线LYA,43,调整L