5-运输问题(运筹学)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第五章,运输问题,一、运输问题,1,，运输问题的模型表示,2,，运输问题的求解方法,3,，各种运输问题变体,二、转运问题,三、指派问题,第五章,运输、转运和指派问题,2024/9/10,1,物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（,sources,）（如工厂、仓库）运输到一系列终点地（,destinations,）（如仓库、顾客）,一、运输问题,你怎么去分析这类问题呢？,想想看！,2024/9/10,2,1,、运输问题的模型表示,2024/9/10,3,2,3,2,1,3,4,1,s,2,=10,s,3,=15,d,1,=13,d,2,=21,d,3,=9,d,4,=7,s,1,=25,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,运输问题的网络表示,2024/9/10,4,运输问题的表格表示,需求地,供应地,1,2,3,4,合计,1,6,7,5,3,25,2,8,4,2,7,10,3,5,9,10,6,15,合计,13,21,9,7,2024/9/10,5,供应地约束,需求地约束,运输问题线性规划模型,2024/9/10,6,运输问题的一般数学模型,设,从第,i,产地到第,j,销地的物资运输量为,x,ij,，则,目标函数：,约束条件：,由于产销平衡，因此有,2024/9/10,7,实例分析：,仓库,罐头厂,一,二,三,四,合计,一,3,11,3,10,7,二,1,9,2,8,4,三,7,4,10,5,9,合计,3,6,5,6,x,11,x,12,x,13,x,14,x,21,x,22,x,23,x,24,x,34,x,31,x,32,x,33,s.t.,a,1,a,2,a,3,b,1,b,2,b,3,b,4,2024/9/10,8,每一个出发地都有一定的,供应量（,supply,）,配送到目的地，每一个目的地都有需要从一定的,需求量（,demand,）,，接收从出发地发出的产品,需求假设,：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足,成本假设,：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成,线性比例,关系，因此这个成本就等于,配送的单位成本乘以所配送的数量,整数解性质,：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件,运输问题的特征,2024/9/10,9,2,、运输问题的求解方法,步骤,1,，确定初始基可行解,最小元素法,就近运输，即从单位运价表中最小的运价处开始确定运输关系，以此类推，直到给出全部方案为止,2,，求各非基变量（在表格中即为空格）的检验数，判别是否达到最优。是，则停止；否则转下一步,3,，确定换入变量和换出变量，利用闭回路法对检验数为负的格进行调整，找出新的基可行解,4,，重复以上步骤，直到找到最优解,2024/9/10,10,1,、初始基可行解的确定,-,最小元素法,从单位运价表中最小的运价处开始确定运输关系，依此类推，直到给出全部方案,例,1,2024/9/10,11,2,、求检验数,-,闭回路法,:,例,1,1,2,1,-1,10,12,注,: 1),数字格检验数均为,0,显然该问题至此尚未达到最优解。,2024/9/10,12,3,、 调整,从最小负检验数所对应的空格进行调整,例,1,对由最小元素法得出的初始解进行调整,调整方法：,1,2,1,-1,10,12,1,）找出具有负检验数的闭回路,2,）使最小负检验数所对应的空格达到最大的调整量,1,再按调整后的解由位势法计算空格的检验数,2024/9/10,13,用计算机求解,1,，线性规划方法,2,，,WINQSB,软件的,NET,程序,2024/9/10,14,供应总量超出了需求总量,供应总量小于需求总量,一个目的地同时存在着最小需求和最大需求,在配送中不能使用特定的出发地,目的地组合,目标是与配送量有关的总利润最大不是成本最小,3,、各种运输问题变体,2024/9/10,15,（,1,）运输不平衡问题,如果,销地,产地,B1,B2,B3,产量,A1,6,4,6,300,A2,6,5,5,300,销量,150,150,200,销地,产地,B1,B2,B3,产量,A1,6,4,6,200,A2,6,5,5,300,销量,250,200,200,或者,650 500,500 600,2024/9/10,16,产大于销的运输方案可设为,建模,销地,产地,B1,B2,B3,产量,A1,X11,X12,X13,300,A2,X21,X22,X23,300,销量,150,150,200,2024/9/10,17,销大于产的运输模型,销地,产地,B1,B2,B3,产量,A1,X11,X12,X13,200,A2,X21,X22,X23,300,销量,250,200,200,2024/9/10,18,（,2,）有区间约束的需求,例：石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生取暖用煤,3000t,，,1000t,，,2000t,，由河北临城，山西孟县两处煤矿负责供应。两处煤矿能供应北方研究院的煤的数量，山西孟县为,4000t,，河北临城为,1500t,。由于需大于供，经院研究平衡决定一区供应量可减少,0,300t,，二区需要量应全部满足，三区供应量不少于,1500t,。由煤矿至北方研究院的单位运价,(,百元,t),如下表所示。试求总运费为最低的调运方案。,运费,一区,二区,三区,供应量,山西盂县,1.65,1.7,1.75,4000,河北临城,1.6,1.65,1.7,1500,需求量,2700-3000,1000,1500-2000,2024/9/10,19,运输方案,运量,运费,一区,二区,三区,供应量,山西盂县,1.65,1.7,1.75,4000,河北临城,1.6,1.65,1.7,1500,需求量,2700-3000,1000,1500-2000,2024/9/10,20,模型：,Min 1.65x11+1.7x12+1.75x13+1.6x21+1.65x22+1.7x23,S.t.,x11+x12+x13=4000,x21+x22+x23=1500,x11+x21 3000,x11+x21 2700,x12+x22=1000,x13+x23 2000,x13+x23 1500,x,ij,0,2024/9/10,21,用网络优化软件,运费,一区,1,一区,2,二区,三区,1,三区,2,供应量,山西盂县,1.65,1.65,1.7,1.75,1.75,4000,河北临城,1.6,1.6,1.65,1.7,1.7,1500,假想地点,M,0,M,M,0,500,需求量,2700,300,1000,1500,500,6000,6000,2024/9/10,22,（,3,）具有出发地约束的问题,例：设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调拨方案。,2024/9/10,23,方法,1,：线性规划方法,2024/9/10,24,方法,2,：用网络优化软件,这是一个产销不平衡的运输问题，总产量为,160,万吨，四个地区的最低需求为,110,万吨，最高需求为无限，根据现有产量，在满足,I,，,II,，,IV,三个地区的最低需求量的前提下，第,IV,地区的最高需求改为,60,万吨，总的最高需求为,210,万吨。,为了求得平衡，在产销平衡表上增加一个假想的化肥厂,D,，其年产量为,50,万吨。由于各地区的需要量包含两个部分，如地区,I,其中,30,万吨是最低需求，必须满足，不能由假想的化肥厂,D,供给，令其运价为,M,；而另一部分,20,万可以不满足，故可以由假想化肥厂,D,供给，令其运价为零。,对需求分两种情况的地区，实际上可按两个地区看待，这样得到下表所示的产销平衡与运价表。,2024/9/10,25,2024/9/10,26,二、转运问题,一些运输问题中常常涉及到中间转运站的问题，这些转运在起点和最终目的地之间起到一个暂时存放货物的作用，这些转运站既是起点同时也是目的地。这些问题的目标和运输问题是一样的：转运成本最小化。,转运问题可以用线性规划模型来建模和求解，其中需要注意的是转运节点的进和出的量要相等。,书,P104,页，例,5-2,2024/9/10,27,现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂,三、 指派问题（分配问题）,还有哪些这样的问题呢？,想想看！,2024/9/10,28,指派问题的形式表述,:,给定了一系列所要完成的任务（,tasks,）以及一系列完成任务的被指派者（,assignees,），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务？,指派问题模型,2024/9/10,29,例：员工分配,临时工,每项任务所需要的时间,每小时,工资,文字处理 幻灯片 材料准备 记录,A,B,C,D,35 41 27 40,47 45 32 51,39 56 36 43,32 51 25 46,14,12,13,15,2024/9/10,30,设,x,ij,1,或,0,分别表示第,i,人做或不做第,j,项工作，,i,j,=1,2,3,4,则其数学模型为,临时工,每项任务所需要的时间,每小时,工资,文字处理,1,幻灯片,2,材料准备,3,记录,4,1 A,2 B,3 C,4 D,35 41 27 40,47 45 32 51,39 56 36 43,32 51 25 46,14(,w,1,),12(,w,2,),13(,w,3,),15(,w,4,),(c,11,),(c,12,),(c,13,),(c,14,),2024/9/10,31,指派问题的假设,:,被指派者的数量和任务的数量是相同的,每一个被指派者只完成,一项,任务,每一项任务只能由一个被指派者来完成,每个被指派者和每项任务的组合有一个相关成本,目标是要确定怎样进行指派才能使得总成本最小,指派问题一般模型,2024/9/10,32,指派问题的常见模型,对于,有,n,个工人和,n,项工作的指派问题，设,x,ij,1,或,0,分别表示第,i,人做或不做第,j,项工作，则其数学模型为,2024/9/10,33,指派问题的变形,指派问题的变形,:,有一些被指派者并不能进行某一些的任务,任务比被指派者多,被指派者比要完成的任务多,每个被指派者可以同时被指派给多于一个的任务,每一项任务都可以由多个被指派者共同完成,2024/9/10,34,例,1,：考虑四种不同类型的机器和五项任务的分配问题。可利用的四种类型机器的台数是,25,，,30,，,20,和,30,。五项任务中的工作量（需要的机器台数）是,20,，,20,，,30,，,10,和,25,。不能把第,4,类机器分配到第,4,项任务上。各类机器分配到各项任务时所发生的成本如下表,(,方框中的数字,),。求把各类机器分配到各项任务上的最优分配。,2024/9/10,35,定义决策变量,x,ij,为整数变量，,i,=1,2,3,4;,j,=1,2,3,4,5,c,44,=100,(c,11,),2024/9/10,36,用,WINQSB,软件来求解,2024/9/10,37,总 结,运输问题考虑（确实的或是比喻的）从出发地运送货物到目的地。每一个出发地都有一个固定的供应量，每一个目的地都有一个固定的需求量,指派问就要处理应当将哪一项任务指派给哪一个被指派者，才能使完成这些任务的总达到最小,把可能会面临的问题描述为一个运输问题或者指派问题或者它们的变形并进行分析,2024/9/10,38,本章作业,P116：Ex1（其中b用Lindo求解）,P 121：EX16 （其中b用Lindo求解）,2024/9/10,39,