运筹学运输问题表上作业法

运筹学,李细霞2013物流工程1班20142015学年第二学期,课程主要内容,Transportationproblem,3,第三章运输问题,学习目标,主要内容,思考,运输问题要解决什么？什么叫一个运输方案？什么叫一个最优的运输方案？若用xij表示从Si到Dj的运量，那么在产销平衡的条件下，求总运费最小的方案。,问题描述,7,表格模型,8,生产量：A1-7吨，A2-4吨，A3-9吨销售量：B1-3吨，B2-6吨，B3-5吨，B4-6吨,举例,产销平衡？,9,调运示意图,10,此问题是线性规划问题吗？,请建立此问题的模型,目标？约束条件？,思考,11,二、建立模型,设：xij第i产地到第j销地之间的调运量，则有,Minz=cijxij,3,4,i=1,j=1,x11+x12+x13+x14=7,x11+x21+x31=3,xij0,(i=1,2,3；j=1,2,4),产量限制,销量限制,x21+x22+x23+x24=4,x31+x32+x33+x34=9,x12+x22+x32=6,x13+x23+x33=5,x14+x24+x34=6,可否用单纯形法求解？,12,ai=bj,产销平衡运输问题的一般表示,13,调运模型为：,mn个变量,m个约束,n个约束,共有m+n个约束条件？,14,约束条件展开,15,约束条件的系数矩阵,有何特点？,16,1.变量数：mn个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：,产销平衡运输问题模型的特点,Why?,01.1.0,17,定理,平衡条件下的运输问题一定有最优解,唯一最优解？无穷多最优解？,18,基本可行解,检验数,基变换,用单纯形法求解线性规划问题的步骤,表上作业法,19,单纯形法在求解运输问题时的一种简化方法,20,1.西北角法2.最小元素法3.伏格尔法,1.闭回路法2.位势法,闭回路法,表上作业法步骤,举例,产量,产地,销地,A1A2A3,B1B2B3B4,销量,4,1,3,10,2,5,3656,749,3,11,9,8,7,10,运价,总产=总销,22,23,西北角法,3,4,2,2,3,6,有何疑问？,24,西北角法的优劣？,太简单咯！,最优解有点望尘莫及呢,25,几点疑问,为什么要从西北角开始？,为什么每次填数一定要填最大允许量，然后划掉一行（或一列）？,为什么有数格只有6个？（总共有12个格）,26,基本可行解,一个基本可行解：有m+n-1个基变量（有数格），其余为非基变量（空格）,m+n-1个变量不能构成闭回路,充要条件,运输问题的m+n个约束方程中，有且只有m+n-1个有效方程,举例,下面这些有数格组成了闭回路（不能作为基本可行解）,什么是闭回路？,下面这些有数格没有组成闭回路（可以作为基本可行解）,29,几点疑问的解答,为什么要从西北角开始？,为什么每次填数一定要填最大允许量，然后划掉一行（或一列）,为什么有数格只有6个？（总共有12个格）,m+n-1个变量不能构成闭回路,只有6个有数格,基变量的个数为m+n-1（3+4-1）,30,所有问题答案归结一句话：保证初始方案是运输问题（线性规划问题）的基本可行解,Why？随便一个可行解不行么？,31,最小元素法,3,11,3,10,1,9,2,8,7,4,10,5,3,1,4,6,3,3,32,最小元素法的优劣？,也很简单哦,最优解可望，但还是有一定距离的,33,伏格尔法,34,产地,销地,A1A2A3,B1B2B3B4,行差额,列差额,311310192874105,011,2513,012,2-13,01-,2-12,76-,-12,Vogel法:,产地,销地,A1A2A3,B1B2B3B4,749,产量,销量,3656,6,3,5,2,1,3,产销平衡表,单位运价表,伏格尔法（差额法）,对最小元素法的改进,35,伏格尔法的优劣？,离最优解貌似很近了哦,求解过程有点麻烦呢！,用Vogel法求出的初始解叫做“近似最优解”,36,课堂练习：用最小元素法求初始解,37,只有5个有数格，不是基本可行解吗？,5,3,4,1,7,课堂练习答案,38,应用举例：用最小元素法或伏格尔法求初始解,“总利润最大”而不是“运费最小”，“最小元素”怎么找？,39,最优性检验闭回路法,表示什么？,每个空格都能找到闭回路吗？有的话，是否唯一？,每个空格有且只有一条闭回路！,46,如何判断初始方案是否达到最优？,若存在某些检验数小于0，则说明调整后运价将减少。（不是最优解）若存在某些检验数等于0，则说明调整后运价将不发生改变。（多个最优解）若所有检验数大于0，说明调整后运价将增加。（唯一最优解）,最优方案：所有检验数0,注意是目标最小化的问题,思考,如果将运输问题的运价表改为利润表，则应如果求初始方案，如何判断方案是否最优？,48,最优性检验位势法（对偶变量法）,设U1,U2,Um,V1,V2,Vn是对应m+n个约束条件的对偶变量其中Ui对应第i个产地的产量约束，Vj对应第j个销地的销量约束称Ui为行位势，Vj为列位势,49,2.令u1=0，则依cij=ui+vj计算各ui和vj,3.计算空格处位势；ij=cij-（ui+vj）,1.在表中增加一行一列,填上行位势ui,列位势vj,在对应初始方案有数格处写0（基变量检验数为0）；,位势法的图表形式:,ui,产地,销地,A1A2A3,B1B2B3B4,vj,u3=-5,3,11,3,10,1,9,2,8,7,4,10,5,0,0,0,0,0,0,v3=3,v4=10,u1=0,u2=-1,v1=2,v2=9,1,2,1,-1,10,12,50,位势法计算非基变量xij检验数的公式ij=cij-（ui+vj）,比较检验数计算的两种方法,51,52,三、方案改进（闭回路法）当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。步骤：1.若检验数ij小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量,若有多个检验数小于零，则取其中最小的负数,53,继续上例，因24=-1，画出以x24为起始变量的闭回路,54,计算调整量：=Min（3，1）=12.按照下面的方法调整调运量：闭回路上，奇数次顶点的调运量减去，偶数次顶点（包括起始顶点）的调运量加上；闭回路之外的变量调运量不变。,55,3.得到调整后的调运方案：,4.计算新方案的检验数，重复上述步骤，直至所有检验数都0，即得到最优方案。,56,最优调运方案,相应的最小总运费为：,运输问题的应用,产销不平衡问题生产与存储问题转运问题,由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。,设有三个化肥厂(A，B，C)供应四个地区(，)的农用化肥。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调拨方案。,产销不平衡问题,这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两部分，如地区，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表和单位运价表。,产销平衡表,单位运价表,根据表上作业法计算，可以求得这个问题的最优方案,请简单描述此方案,生产与储存问题,某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产费用(包括储存、维护费用)最小的方案。,解：由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足,又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：,第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。cij的具体数值见下表：,设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成：,目标函数：约束条件：,显然，这是一个产大于销的运输问题模型。注意到这个问题中当ij时，xij=0，所以应令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，见下表)。,经用表上作业法求解，可得多个最优方案，下表是最优方案之一。,即第季度生产25台，10台当季交货，15台季度交货；季度生产5台，用于季度交货；季度生产30台，其中20台于当季交货，10台于季度交货。季度生产10台，于当季交货。按此方案生产，该厂总的生产费用(包括储存、维护费用)为773万元。,转运问题,每个产地的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；运往各销地的产品可以先运给其中几个销地，再转运给其他销地；除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间进行转运。,71,产地：原产地、中间转运站、转运物资的销地销地：原销地、中间转运站、转运物资的产地如果是产销不平衡问题，先通过增加虚拟的产地或销地转化为产销平衡问题。设各转运站转运物资的数量均为总产量ai（或总销量bj）专职转运站的产量和销量均为ai原产地Ai的产量均为（ai+ai）原销地Bj的销量均为（bj+ai）将各条线路实际的运输单价列成单位运价表，其中不可能的运输其单位运价用M表示。,扩展运输表的构建步骤,举例：A、B两个化肥厂每年各生产磷肥900万吨和600万吨，这些化肥要运到三个港口，已知三个港口C、D、E每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间单位运价如下表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？,73,表1,表2,表3,产销平衡运输表的构建,F,发量,收量,900+1500=2400,600+1500=2100,1500,1500,1500,1500,1500,700+1500=2200,400+1500=1900,300+1500=1800,100,0,0,0,0,0,将表2和表3合并为一张表（加上单位运价）,例：已知各产地、销地、中间转运站及相互之间每吨产品的运价如表所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。,(1)由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。因此把整个问题当作有11个产地和11个销地的扩大的运输问题。(2)对扩大的运输问题建立单位运价表。方法将表中不可能的运输方案的运价用任意大的正数M代替。,(3)所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过20吨。可以规定T1，T2，T3，T4的产量和销量均为20吨。由于实际的转运量,可以在每个约束条件中增加一个松弛变量xii，xii相当于一个虚构的转运站，意义就是自己运给自己。(20-xii)就是每个转运站的实际转运量，xii的对应运价cii=0。,(4)扩大的运输问题中原来的产地与销地因为也有转运站的作用，所以同样在原来产量与销量的数字上加20吨，即三个厂每天糖果产量改成27，24，29吨，销量均为20吨；四个销售点的每天销量改为23，26，25，26吨，产量均为20吨，同时引进xii作为松弛变量。,下面写出扩大运输问题的产销平衡表与单位运价表，由于这是一个产销平衡的运输问题，所以可以用表上作业法求解(计算略),带有约束的运输问题及推广应用,在某军供点B1处有10车物资，4车运往A1点，6车运往A2点；在B2处有2车物资运往A3点；在B3处有3车物资运往A4点。车队只有两辆卡车、两辆加载车可供使用，空车送货前集中在A0处,并要求:1)B2处两车特种物资需要提前用加载车运往A3点；2)送完所有物资后，所有车辆返回到A0点。问如何运输，才能使空车行驶里程最少？已知各供需点间的距离如表所示。,某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表。,假定各条航线使用相同型号的船只，又各城市间的航程天数见下表：,又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求?,解该公司所需配备船只分两部分。(1)载货航程需要的周转船只数。例如航线1，在港口E装货1天，ED航程17天，在D卸货1天，总计19天。每天3航班，故该航线周转