5-运输问题(运筹学)

03:16第五章运输问题一、运输问题•1，运输问题的模型表示•2，运输问题的求解方法•3，各种运输问题变体二、转运问题三、指派问题第五章运输、转运和指派问题03:16物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）一、运输问题你怎么去分析这类问题呢？想想看！03:161、运输问题的模型表示SourcesDestinations03:162321341s2=10s3=15d1=13d2=21d3=9d4=7s1=25供应量供应地运价需求量需求地6753842759106运输问题的网络表示03:16运输问题的表格表示需求地供应地1234合计1675325284271035910615合计13219703:160≥7=++9=++21=++13=++15=+++10=+++25=+++6+10+9+5+7+2+4+8+3+5+7+6=min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxz供应地约束需求地约束运输问题线性规划模型03:16运输问题的一般数学模型设从第i产地到第j销地的物资运输量为xij，则目标函数：约束条件：由于产销平衡，因此有minjijijxcz11minnjmixinjbxmiaxjmijijnjiij,...,2,1;,...,2,1,0,...,2,1,,...,2,1,11njjmiiba1103:16实例分析：仓库罐头厂一二三四合计一3113107二19284三741059合计3656x11x12x13x14x21x22x23x24x34x31x32x333141minijijijxcz4,...,2,1;3,...,2,1,04,...,2,1,3,...,2,1,3141jixijbxiaxjijijjiijs.t.a1a2a3b1b2b3b403:161.每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品2.需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足3.成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量4.整数解性质：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件运输问题的特征03:162、运输问题的求解方法步骤1，确定初始基可行解—最小元素法就近运输，即从单位运价表中最小的运价处开始确定运输关系，以此类推，直到给出全部方案为止2，求各非基变量（在表格中即为空格）的检验数，判别是否达到最优。是，则停止；否则转下一步3，确定换入变量和换出变量，利用闭回路法对检验数为负的格进行调整，找出新的基可行解4，重复以上步骤，直到找到最优解03:161、初始基可行解的确定--最小元素法从单位运价表中最小的运价处开始确定运输关系，依此类推，直到给出全部方案销地3113101928741052065964A1A2bjB13产地A3aiB2B37B4③④①⑥③③例1865310334214613Z03:162、求检验数--闭回路法:例1销地31131019287410520A17A24A3965bjB13产地6aiB2B3B4③①③③④⑥121-11012注:1)数字格检验数均为0偶奇量的检验数。格对应变点。根据回路计算该空回到起，然后继续前进，直到。数字格转线往前划，每碰到一个平或垂直以某空格为起点，用水空格检验数ijijijcc90)2解。时，运输问题达到最优当所有最优性判别准则：0ij显然该问题至此尚未达到最优解。03:163、调整从最小负检验数所对应的空格进行调整例1对由最小元素法得出的初始解进行调整调整方法：销地311310192874105产地aiB2B3B4B1A39A17A24③④①⑥③③121-110121）找出具有负检验数的闭回路2）使最小负检验数所对应的空格达到最大的调整量1514;110;213;011即②⑤①再按调整后的解由位势法计算空格的检验数03:16用计算机求解1，线性规划方法2，WINQSB软件的NET程序03:16供应总量超出了需求总量供应总量小于需求总量一个目的地同时存在着最小需求和最大需求在配送中不能使用特定的出发地——目的地组合目标是与配送量有关的总利润最大不是成本最小3、各种运输问题变体03:16（1）运输不平衡问题如果销地产地B1B2B3产量A1646300A2655300销量150150200销地产地B1B2B3产量A1646200A2655300销量250200200或者65050050060003:16产大于销的运输方案可设为建模销地产地B1B2B3产量A1X11X12X13300A2X21X22X23300销量150150200300,300232221131211xxxxxx200,150,150231322122111xxxxxxjiijijxc,min03:16销大于产的运输模型销地产地B1B2B3产量A1X11X12X13200A2X21X22X23300销量250200200300,200232221131211xxxxxx200,200,250231322122111xxxxxxjiijijxc,min03:16（2）有区间约束的需求例：石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生取暖用煤3000t，1000t，2000t，由河北临城，山西孟县两处煤矿负责供应。两处煤矿能供应北方研究院的煤的数量，山西孟县为4000t，河北临城为1500t。由于需大于供，经院研究平衡决定一区供应量可减少0～300t，二区需要量应全部满足，三区供应量不少于1500t。由煤矿至北方研究院的单位运价(百元／t)如下表所示。试求总运费为最低的调运方案。运费一区二区三区供应量山西盂县1.651.71.754000河北临城1.61.651.71500需求量2700-300010001500-200003:16运输方案运量运费一区二区三区供应量山西盂县1.651.71.754000河北临城1.61.651.71500需求量2700-300010001500-200003:16模型：Min1.65x11+1.7x12+1.75x13+1.6x21+1.65x22+1.7x23S.t.x11+x12+x13=4000x21+x22+x23=1500x11+x21≤3000x11+x21≥2700x12+x22=1000x13+x23≤2000x13+x23≥1500xij≥003:16用网络优化软件运费一区1一区2二区三区1三区2供应量山西盂县1.651.651.71.751.754000河北临城1.61.61.651.71.71500假想地点M0MM0500需求量2700300100015005006000600003:16（3）具有出发地约束的问题例：设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调拨方案。销地B1B2B3B4产量产地A11613221750A21413191560A3192023-50最低需求3070010最高需求50703003:16方法1：线性规划方法03:16方法2：用网络优化软件这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限，根据现有产量，在满足I，II，IV三个地区的最低需求量的前提下，第IV地区的最高需求改为60万吨，总的最高需求为210万吨。为了求得平衡，在产销平衡表上增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两个部分，如地区I其中30万吨是最低需求，必须满足，不能由假想的化肥厂D供给，令其运价为M；而另一部分20万可以不满足，故可以由假想化肥厂D供给，令其运价为零。对需求分两种情况的地区，实际上可按两个地区看待，这样得到下表所示的产销平衡与运价表。03:16销地B11B12B2B3B41B42产量产地A116161322171750A214141319151560A319192023MM50A4(虚拟)M0M0M050需求302070301050二、转运问题一些运输问题中常常涉及到中间转运站的问题，这些转运在起点和最终目的地之间起到一个暂时存放货物的作用，这些转运站既是起点同时也是目的地。这些问题的目标和运输问题是一样的：转运成本最小化。转运问题可以用线性规划模型来建模和求解，其中需要注意的是转运节点的进和出的量要相等。书P104页，例5-203:1603:16现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂三、指派问题（分配问题）还有哪些这样的问题呢？想想看！03:16指派问题的形式表述:给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务？指派问题模型03:16例：员工分配临时工每项任务所需要的时间每小时工资文字处理幻灯片材料准备记录ABCD354127404745325139563643325125461412131503:16设xij＝1或0分别表示第i人做或不做第j项工作，i,j=1,2,3,4则其数学模型为)4,...2,1(1或0)4,...2,1(1)4,...2,1(1..min41414141jxjxixtsxwcijiijjijijijiij临时工每项任务所需要的时间每小时工资文字处理1幻灯片2材料准备3记录41A2B3C4D3541274047453251395636433251254614(w1)12(w2)13(w3)15(w4)(c11)(c12)(c13)(c14)03:16指派问题的假设:被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小指派问题一般模型03:16指派问题的常见模型对于有n个工人和n项工作的指派问题，设xij＝1或0分别表示第i人做或不做第j项工作，则其数学模型为),...2,1(1或0),...2,1(1),...2,1(1..min1111njxnjxnixtsxcijniijnjijninjijij03:16指派问题的变形指派问题的变形:有一些被指派者并不能进行某一些的任务任务比被指派者多被指派者比要完成的任务多每个被指派者可以同时被指派给多于一个的任务每一项任务都可以由多个被指派者共同完成03:16例1：考虑四种不同类型的机器和五项任务的分配问题。可利用的四种类型机器的台数是25，30，20和30。五项任务中的工作量（需要的机器台数）是20，20，30，10和25。不能把第4类机