大学运筹学经典课件第七章-运输问题

1第七章运输问题§1运输模型§2运输问题的计算机求解§3运输问题的应用§4*运输问题的表上作业法2例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）

§1运输模型3§1运输模型一般运输模型：产销平衡

A1、A2、…、Am

表示某物资的m个产地；B1、B2、…、Bn

表示某物质的n个销地；si

表示产地Ai的产量；dj

表示销地Bj的销量；cij

表示把物资从产地Ai运往销地Bj的单位运价。设xij

为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：

mnMinf=cijxiji=1j=1n

s.t.

xij=sii=1,2,…,m

j=1m

xij=djj=1,2,…,ni=1

xij≥0(i=1,2,…,m;j=1,2,…,n)变化：

1）有时目标函数求最大。如求利润最大或营业额最大等；

2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；

3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。4§2运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为05§2运输问题的计算机求解例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为06§3运输问题的应用一、产销不平衡的运输问题例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。解：根据题意，作出产销平衡与运价表：这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。7§3运输问题的应用一、产销不平衡的运输问题例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：

试求总费用为最低的化肥调拨方案。解：根据题意，作出产销平衡与运价表：

最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量

50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。

8§3运输问题的应用二、生产与储存问题例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。9§3运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：x11=10生产：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x4410§3运输偏问题陕的应需用二、恩生产浮与储抽存问急题例7、光明沫仪器嫩厂生夹产电叹脑绣踩花机旷是以剩产定孔销的排。已毒知1至6月份揉各月亮的生社产能型力、悠合同粪销量达和单沉台电蝇脑绣词花机袜平均味生产迎费用男见下瓶表：已知清上年协末库剃存10踢3台绣需花机品，如仁果当确月生倚产出签来的症机器西当月兵不交惭货，则需返要运淡到分吗厂库柄房，别每台版增加该运输本成本0.的1万元,每台鸟机器刚每月宏的平有均仓储费像、维故护费盘为0.匹2万元迹。在7-窝-8月份芬销售浑淡季汁，全屋厂停瘦产1个月区，因场此在6月份睁完成倘销售虑合同既后还垮要留雁出库覆存80台。留加班端生产兰机器懒每台步增加挡成本1万元。拆问应筹如何织安排1-还-6月份铺的生项产，器可使假总的系生产臂费用寻（包栏括运志输、捞仓储、免维护边）最爽少？11§3运输勉问题遇的应欲用解：这个掀生产临存储班问题壶可化讨为运盐输问冻题来暑做。甜考虑勾：各月手生产暑与交辨货分撕别视沿为产劫地和令销地1）1-登-6月份丹合计晋生产顽能力隔（包熟括上愉年末择储存奶量）倾为74轻3台，裁销量教为70砖7台。墨设一吴假想砌销地绪销量啦为36；2）上万年末穗库存10牵3台，炸只有刮仓储示费和户运输饶费，裙把它班列为骗第0行；3）6月份境的需碎求除70台销多量外集，还男要80台库牌存，煤其需咐求应语为70拣+8视0=把15胡0台；4）1-夺-6表示1-键-6月份庆正常鸟生产举情况评，1’治--槽6’表示1-丝式-6月份腿加班锯生产较情况纸。产销爱平衡灭与运印价表谁：12§3运输江问题赴的应伴用用“灿管理矮运筹榆学”佣软件途解得嫌的结骗果是日：1-岭6月最银低生捡产费萝用为83良07垂.5万元纲，每器月的滩销售裙安排份如下演表所眉示13§3运输强问题按的应签用三、拼转运仓问题菠：在原阔运输珠问题晋上增积加若批干转序运站粘。运任输方访式有篮：产富地参转运轨站、宪转运站泉燥销史地、轮产地宵摆产怀地、栋产地恳沃销猾地、的销地陆头转反运站款、销梢地灶傍产地等。例8、腾飞葱电子攀仪器膜公司涌在大指连和链广州有两避个分咳厂生敢产同嘉一种暖仪器杨，大访连分略厂每月拌生产40煌0台，捐广州叛分厂祖每月索生产60染0台。镜该公饺司在夜上海拥和天沾津有迎两个竞销售口公司负穴责对壶南京走、济抽南、刻南昌井、青遍岛四歪个城市堤的仪秀器供洞应。后另外范因为衰大连丛距离爸青岛较炮近，盘公司电同意毛大连亩分厂惊向青济岛直旁接供货析，运漆输费趴用如棉图，辩单位蓝是百根元。钓问应摄该如喂何调撇运仪广器，可使葬总运赛输费筐用最以低？图中1-广州城、2票-大连兰、3漆-上海蜡、4端-天津养、5夜-南京谊、6摸-济南仓、7派-南昌细、8津-青岛14§3运输谁问题异的应洽用解：设xij为从i到j的运你输量眠，可如得到西有下渔列特结点的顺线性杠规划泊模型靠：目标按函数硬：Mi碌n尸f趴=所有助可能秧的运甲输费抓用（蛛运输局单价蓝与运辽输量无乘积廊之和启）约束债条件响：对产换地（差发点零）i：输科出量-输入荣量=产量对转阀运站霞（中储转点所）：碗输入均量-输出烛量=贼0对销百地（简收点柳）j：输佛入量-输出嫩量=销量例8．（王续）目标机函数疮：Mi它n菊f患=挥2x13+辆3x14+纤3x23+x24+序4x28+群2x35+封6x36+犹3x37+曾6x38+份4x45+羡4x46+调6x47+券5x48约束它条件普：s.肆t.x13+x14≤途60域0控(广州免分厂男供应娇量限景制）x23+x24+x28≤猫40甲0愤(大连突分厂报供应远量限吴制）-x13-x23+x35+x36+x37+x38=菊0（上迷海销葱售公唯司，暴转运眼站）-x14-x24+x45+x46+x47+x48=酿0（天帜津销头售公触司，州转运电站）x35+x45=签20灾0（南仙京的欲销量絮）x36+x46=勉15独0（济页南的带销量过）x37+x47=塞35侄0（南虚昌的吹销量苍）x38+x48+x28=理30砍0（青双岛的程销量轻）xij≥带0狱,乱i歌,j遍=惜1夏,2蛾,3尽,4采,5优,6柳,7训,815§3运输贷问题描的应壮用用“遍管理规运筹绒学”缓软件洗求得塑结果蹈：x13=砍55病0x14=5称0；x23=旁0x24=衣10视0x28=隔30毒0；x35=泥20耗0x36=调0x37=骑35干0x38=桃0；x45=歪0x46=卧15宋0x47=趁0x48=竭0。最小口运输餐费用萍为：46制00百元例9、某公匀司有A1、A2、A3三个绩分厂洽生产福某种哥物资境，分桌别供绑应B1、B2、B3、B4四个鸽地区育的销途售公隶司销杠售。岔假设朽质量至相同膏，有旁关数材据如他下表序：试求题总费棍用为歼最少爷的调威运方祸案。假设挨：1.每个困分厂万的物碍资不肝一定棉直接夜发运方到销碍地，察可以塔从其辰中几朋个产辆地集卖中一往起运帅；2.运往屠各销速地的你物资开可以震先运筋给其瞎中几伙个销讯地，算再转运运给精其他府销地详；3.除产滨销地更之外奶，还担有几伪个中傻转站蠢，在燃产地侄之间晋、销偿地之蛾间或茄在产压地与升销地丢之间争转运垒。16§3运输皱问题胸的应调用运价探如下低表：解：把此争转运谋问题革转化套为一娇般运陪输问种题：1、把剃所有辈产地苦、销宗地、春转运句站都悬同时垂看作衡产地俱和销娇地；2、运俩输表僵中不厌可能效方案焦的运倚费取剪作M，自卸身对六自身弹的运侮费为0；3、Ai：滤产量叶为20捷+原产积量，俱销贡量为20；Ti：鞭产量直、销责量均博为20；Bi：挨产芳量为20，著销骂量为20松+原销海量，斧其中20为各烫点可甚能变砍化的拴最大砍流量兵；4、对衬于最杨优方卫案，昼其中xi吗i为自久身对师自身遇的运梯量，旬实际麦上不养进行偶运作窜。17§3运输帖问题才的应闭用扩大诵的运寒输问速题产岸销平迎衡与禁运价碌表：18§4*运输值问题闸的表昏上作宜业法表上厅作业顾法是蓬一种返求解渗运输氧问题参的特震殊方流法，息其实质瞒是单感纯形皱法。运输靠问题砖都存蝇在最正优解资。计算赏过程清（假最设产茅销平盛衡）托：1.找出限初始混基本辱可行蔽解。送对于脸有m个产锤地n个销梢地的科产销贪平衡尾问题池，则袋有m个关楚于产羞量的剧约束摧方程苏和n个关内于销免量的茄约束董方程乎。由僚于产王销平酿衡，朱其模饲型最决多只训有m+戏n-斧1个独奥立的张约束钞方程勾，即私运输怪问题查有m+畅n-纱1个基拍变量票。在m×n的产朴销平踏衡表格上给莲出m+坚n-海1个数游字格斜，其辉相对听应的亮调运棍量的封值即腊为基党变量贤的值掏。2.求各棚非基挣变量慨的检胡验数感，即耻检验腔除了攻上述m+匀n-腐1个基材变量摇以外轮的空忧格的仗检验匀数判率别是弦否达岂到最泽优解龟，如喂果已船是最岛优，今停止安计算婚，否获则转罪到下朝一步个。3.确定愁入基潜变量灰和出贤基变举量，仅找出金新的延基本坏可行页解。鼓在表牌上用面闭回损路法虏调整邮。4.重复2、3直到子得到豆最优瞧解。19§4*运输秋问题箭的表恒上作肥业法例10缠.喜庆障食品苹公司米有三手个生宪产面泡包的勒分厂A1，A2，A3，有代四个贩销售准公司B1，B2，B3，B4，其欠各分评厂每鸭日的宫产量海、各少销售垂公司东每日发的销起量以鼻及各员分厂佳到各博销售搞公司当的单恋位运尼价如友表所岁示，洽在表图中产承量与曾销量滴的单侵位为能吨，职运价桥的单淘位为能百元/吨。有问该贝公司弹应如脉何调驰运产登品在浑满足蓝各销宾点的状需求分量的泳前提哥下总宋运费款最少驱？这是剪一个牲产销电平衡狼的运号输问葱题，唉因此馋不需点要再炮设假柱想产顶地和闷销地午了。

销地产地B1B2B3B4产量A13113107A219284A3741059销量3656202020§4*运输详问题驻的表逝上作飞业法一、郑确定甩初始影基本第可行勺解为了冷把初邻始基岸本可误行解宽与运句价区纱分开衡，我灵们把运价放在计每一笛栏的右上馒角，每一栏寄的中厅间写援上初豆始基捞本可菌行解边（调介运量柴）。1.西北塞角法：先忙从表批的左讲上角忙（即凉西北济角）唯的变归量x11开始寒分配呜运输滩量，污并使x11取尽总可能留大的箩值，缘瑞即x11=m聋in尸(7算,3锤)=思3,则x21与x31必为敌零。到同时索把B1的销肾量与A1的产量截都减毁去3填入蚂销量振和产锻量处最，划榜去原桑来的偏销量住和产跪量。取同理勤可得哀余下虚的初零始基本可班行解风。

销地产地B1B2B3B4

产量A134740A222420A336960

销量3062053060202031131085102947121§4*运输扎问题躁的表怨上作都业法2.最小联元素渣法西北塞角法响是对遥西北圾角的理变量激分配巾运输沃量，轻而最阳小元妖素法棵是就象近供依应，泰即对画单位锁运价坑最小验的变持量分灶配运蚊输量辜。在森表上蓄找到斑单位客运价扫最小心的x21，并猴使x21取尽朽可能发大的曾值，闯即x21=m使in建(4盟,3蜡)=张3,把A1的产翼量改叼为1，B1的销爸量改稠为0，并输把B1列划巷去。艺在剩裹下的3×3矩阵翁中再遣找最弱小运轻价，盼同理可可得度其他岸的基靠本可昂行解屯。一般迷来说惯用最茶小元御素法团求得伶的初慎始基漫本可领行解毛比西误北角矩法求薪得的注总运嫁价要绣少。盖这样浑从用渗最小霉元素犁法求屋得的喷初始它基本享可行捏解出享发求屋最优潜解的战迭代碎次数爹可能象少一复些。

销地产地B1B2B3B4

产量A1

43730A23

1410A363930

销量3060

540630202031131085102947122§4*运输姻问题介的表孕上作院业法在求借初始鬼基本扫可行纺解时堡要注摆意的榆两个羊问题办：1.当我基们取早定xij的值标之后沾，会速出现Ai的产腰量与Bj的销园量都邪改为骑零的雹情况召，这还时只广能划认去Ai行或Bj列，仓但不诸能同侧时划染去Ai行与Bj列。2.用最细小元棋素法削时，广可能长会出僵现只下剩下衣一行患或一其列的挽所有睁格均康未填岩数或受未被阳划掉棵的情业况，画此时款在这精一行茅或者储一列桶中除还去已喊填上糊的数沙外均还填上织零，迎不能漆按空矮格划并掉。如这样孤可以键保证翁填过唱数或培零的暖格为m+米n-倾1个，莫即保琴证基糕变量核的个条数为m+交n-尿1个。23§4*运输遮问题桐的表蓝上作漆业法二、判最优依解的波判别1.闭回数路法所谓闭回券路是在匙已给嗽出的侄调运此方案生的运收输表尤上从牙一个发代表坊非基防变量衫的空讨格出贯发，导沿水差平或稍垂直无方向娘前进眼，只脂有遇条到代污表基箭变量驴的填隐入数妖字的翼格才债能向育左或裹右转90度（翻当然替也可胃以不拍改变泉方向寒）继幕续前哲进，塌这样普继续棉下去难，直料至回胖到出庙发的酒那个月空格销，由怒此形胡成的夏封闭辅折线习叫做寻闭回新路。丑一个尺空格雀存在县唯一监的闭疗回路妙。所谓闭回寨路法，就像是对踪蝶于代灭表非垒基变毕量的微空格狡（其小调运钢量为加零）饰，把裳它的折调运脉量调喜整为1，由轮于产敌销平昏衡的误要求,我们乎必须北对这市个空爷格的望闭回少路的罢顶点馒的调糟运量词加上谣或减员少1。最准后我献们计越算出次由这睛些变明化给赛整个获运输陕方案笼的总唉运输裳费带跌来的乒变化短。如左果所欺有代朗表非岗基变过量的澡空格币的检木验数隐也即嚷非基快变量惠的检展验数颗都大尝于等龙于零怠，则爆已求皆得最宜优解滨，否租则继栏续迭延代找趋出最她优解扶。24§4*运输藏问题驼的表熊上作睡业法从非蠢基变壳量x11出发狼，找坡到一形个闭路回路挖如上绝表所似示。含回路键有四织个顶的点，途除x11外，帮其余企都为伐基变封量。聚现在震把x11的调备运量军从零馋增加纵为1吨，锁运费龙也增伤加了3元，钢为了猜使A1产量电平衡牢，x13必须御减少1吨，鹅运费床减少3元。泽为了B3的销的量平丝式衡，x23必须饿增加1吨，慈运费书增加2元。尺同理干把x21减少1吨，残运费荐减少1元。庆调整贺后，砍总运葛费增蓝加了3-冈3+油2-垃1=弱1元。笛说明罢如果便让x11为基鹅变量理，运顿费就励会增纤加，玻其增额加值1作为x11的检验充数，为雄了区构别调蜜整量昼，我仍们把1加圈右。用同葬样的吨方法胡可以芬找出奸所有爽空格准（即榆非基腥变量常）的现检验颗数。

销地产地B1B2B3B4

产量A11

47A23

14A39

销量3656202031131085102947125§4*运输陆问题草的表忍上作颗业法2.位势直法所谓燃位势井法，镰我们复对运逼输表波上的售每一雕行赋酬予一捕个数衣值ui，对巧每一粘列赋予一模个数惭值vj，它巡寿们的温数值附是由卧基变煤量xij的检快验数骄所兵决定的边，则岁非基旗变量xij的检泰验数冲就可拔以用武公式肌求出亦。我们毯先给u1赋个肉任意膜数值伙，不叨妨设u1=0，则腊从基痛变量x13的检若验数辆求得v3=c13-u1=3脖-0专=3。同公理可怒以求孟得v4=1也0，u2=-乎1等等石见上报表。袭检验跌值的残求法牙即用杰公式恩，烟如呜。

销地产地B1B2B3B4uiA1

1

2430A23

11

-1-1A3

106

123-5vj29310202031131085102947126§4*运输脖问题老的表押上作臂业法三、疗改进激运输超方案霉的办事法——闭回处路调序整法当表巧中的嗓某个阁检验每数小递于零服时，健方案涨不为应最优她，需肚要调役整。笛方法按是：玻选取散所有负检叹验数集最小申的非兔基变做量作府为入偶基变驴量，突以求酬尽快屡实现息最优活。本婶例中师取错，表明挠增加遗一个蹄单位慌的x24运输爪量，杜可使座得总规运费津减少1。在包以x24为出忆发点敢的闭跳回路中，裙找出斧所有它偶数豪的顶碗点的覆调运羡量：x14=3，x23=1，x24=m村in限(3派,1若)=兆1。把孤所有烤闭回路上扑为偶理数顶启点的饭运输题量都监减少鲜这个境值，缓奇数看顶点近的运甜输量稍都增羽加这迷个值(见下表)。

销地产地B1B2B3B4uiA1

4(+1)3(-1)0A23

1(-1)

+1-1A3

6