运输问题

运输问题的引例设有三个产地(记为A1，A2，A3)，产量分别为7，4，9，四个销地(记为B1，B2，B3，B4)其销量分别为3，6，5，6，若已知从Ai到Bj的单位运价，则应如何调运，可使总运费最小？B1B2B3B4产量A1A2A3317119432101085749销量3656运输问题的模型设xij是从Ai运往Bj的数量，i=1,2,3;j=1,2,3,44,3,2,1;3,2,1,06563947..510478291103113S342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxxxMinij当总产量等于总销量时，称为产销平衡问题，否则称为产销不平衡问题运输问题模型的特点模型中的变量多，m个产地n个销地就有m×n变量。约束条件中变量的系数不是1就是0，于是约束条件系数矩阵的元素特别简单。在产销平衡的条件下，所有约束可写成等式约束。约束条件系数矩阵A的秩为m+n-1.由于这些特点，我们可用特殊的方法来求解。运输问题的求解基本方法与单纯形法相似，先求出初始调运方案；判别该方案是否最优；若不是最优，则进行调整；直到找到最优方案。求运输问题的初始调运方案用最小元素法求初始调运方案，按运费最小优先安排运输的原则进行3146333113101928741057493656B1B2B3B4A1A2A3B1B2B3B4确定初始调运方案的注意事项在方案表中每填一个数字,在对应的运价表中划去一条线;当需求量满足划竖线,生产量满足划横线;当需求量与生产量同时满足时也只划去一条线;一个初始调运方案表中填数字的格子应为m+n-1,(因为约束条件系数矩阵A的秩为m+n-1)确定初始调运方案的注意事项如果方案表中填数字的格子不足m+n-1,则应在适当的位置补零.一个初始调运方案就是线性规划的一个基本可行解.最优方案的判定建立位势表;用运价表减去位势表得检验数表;当检验数表中每个数都大于零,则对应的方案是最优方案.建立位势表位势表的结构类似方案表,在方案表中填数字的位置上填入相应的运价.然后填入位势:cij=ui+vjui和vj中可事先确定一个数.按cij=ui+vj将填数的格子全部填满.B1B2B3B4uiA1A2A31432105vj01128-372398-29B1B2B3B4产量A1A2A3364133749销量3656最优方案表：得位势表B1B2B3B4uiA1A2A321-398432-2109521-3vj0718位势表B1B2B3B4A1A2A3317119432101085运价表运价表-位势表=检验数表524392811039251047829110311301201010100021负数的位置在A2到B4一般有多个负数,则可选一个最小的负数.调运方案的调整检验数表中负数的位置对应于方案表中的一个空格;在方案表中从该空格出发,沿水平方向或垂直方向前进,遇到数字可拐弯,作一闭回路.(即从空格出发回到空格)理论上证明这样的闭回路只有一条;对闭回路上的数字进行调整,可得一个新方案.调运方案的调整B1B2B3B4产量A1A2A3364133749销量3656原方案表中作闭回路调整后得新方案.B1B2B3B4产量A1A2A3365213749销量3656调整后的新方案的位势表B1B2B3B4A1A2A3317119432101085A1A2A3B1B2B3B4143105vjui8017-23063-2971-2易知,检验数表的每个元素都大于零.于是可知下述新方案是最优方案:B1B2B3B4产量A1A2A3365213749销量3656其最小运费为:855381102354613产销不平衡的运输问题当产量大于销量时,可在调运方案表中增加一列为虚销地,其相应的运价为零;当销量大于产量时,可在调运方案表中增加一行为虚产地,其相应的运价为零;然后按产销平衡的方法来求出最优方案.注:在确定初始调运方案时,不把零运价作为最小元素.产销不平衡的运输问题B1B2B3B4产量A1A2A331711956481068789销量4556求解如下的运输问题:总产量=7+8+9=24总销量=4+5+5+6=20B1B2B3B4库产量A1A2A3789销量45564088570649101061134451424B1B2B3B4库位势A1A2A315641080位势0133714-3315748-2-2B1B2B3B4库产量A1A2A34514244789销量45564方案表08857064910106113B1B2B3B4库位势A1A2A315641080位势0133714-3315748-2-2204042204000040检验数的负数在A2到B4的位置B1B2B3B4库产量A1A2A3789销量45564B1B2B3B4库产量A1A2A3789销量455644451424B1B2B3B4库产量A1A2A34532244789销量45564得新方案B1B2B3B4库位势A1A2A31564680位势088570649101061130133532333568-3-20检验数表为:002042006002060最优方案表为B1B2B3B4库产量A1A2A34532244789销量45564最小运费为:0885706491010611399846242635514运输问题应用实例有四个煤产地A1，A2，A3，A4，今年产量分别为35,45,55,65(万吨)，另有六个煤销地B1，B2B3，B4，B5，B6。今年销量将分别达到45,25，35,45,35,45。产量缺口为30万吨，打算增加一套采煤设备，如果这套采煤设备放在A1，A2，A3，A4，其各产地增加的生产成本分别为20,30，15,25。试作决策该设备应放在何处，可使总成本(运输成本和生产成本)最小？各产地至各销地的单位运价如下表：单位运价表B1B2B3B4B5B6A1572418A2913567A3248135A4761249问题的求解将采煤设备分别放在四个产地，得出四个最优调运方案，并可算出最小运费，再加上增加的生产成本，可从中找出最优方案。有A、B两种产品，都需要经过两道化学反应过程，每一单位A产品需前道过程2小时，后道过程3小时，每一单位B产品需前道过程3小时，后道过程4小时，可供利用的前道过程有16小时，后道过程24小时，每生产一单位B产品同时得到了2个单位的副产品C，A产品的每单位利润为4元，B产品每单位的利润为10元，副产品的每单位利润为3元，副产品C如果卖不出去，则每单位的销毁费用为2元，由市场预测可知，最多可售出5个单位的C产品，问如何安排这两种产品的生产，可使利润最大？设x1,x2分别是A产品和B产品的生产量，x3是C产品的销售量，x4是C产品的销毁量。设x1,x2分别是A产品和B产品的生产量，x3是C产品的销售量，x4是C产品的销毁量。0,,,2443163250222..231044321212134324321xxxxxxxxxxxxtsxxxxZMax某车间在一周五天工作日所需的刀具数量如下：周一周二周三周四周五刀具数12085160145300每一把刀具成本6元，用过的刀具送到机修车间研磨每一把需化费2元，刀具用过后，如果立即送去磨，两天后可以磨好送回，供当天需要，若第五天后刀具全部换新的，问该车间需多少刀具才能满足需要而又使成本最少？设xi为第i天使用的新刀具，Si为第i天用过后送去磨的刀具数。第i天取回第i-2天送磨的刀具5,...,1,0,0160851208512012030014516085,120..)(2)(62131213524132132154321iSxSSSSSSSxSxSxxxtsSSSxxxxxMinSii