第7章运筹学 运输问题

.,1,第七章运输问题,1运输模型2运输问题的计算机求解3运输问题的应用4*运输问题的表上作业法,.,2,.,3,.,4,.,5,.,6,.,7,.,8,.,9,.,10,.,11,第四季度可以加班生产，生产能力为10台，加班费用1万元每台,原有库存15台，年末需要留有10台库存？,.,12,生产与存储问题,.,13,某造船厂根据合同需连续三年提供五艘大型货轮给客户，该厂三年内的生产情况如表所示。,加班生产比正常生产高出10%，每艘货轮积压一年的损失为60万元，签合同时，该厂已积压两艘货轮，该厂希望在三年后有一艘备用，问应该如何安排生产，总的费用最小？,.,14,生产问题,某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元/台季，三、四季度可以加班生产，加班生产能力8台/季，加班费用3万元/台问如何安排生产使得总费用最低？,.,15,分析：,可用线性规划，但用运输问题更简单要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度需求量合计115台，生产能力合计126台，供需不平衡，因此，增加一个虚拟的需求点。,.,16,建模：,.,17,结果：,.,18,.,19,三、转运问题,例8、腾飞公司有1、2两个分厂生产产品，1、2分厂每月分别生产400台和600台。有3、4两个分销商负责四个城市的供应。运输网络和运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？,.,20,三、转运问题,解：设xij为从i到j的运输量，可得到有下列特点的线性规划模型：目标函数：Minf=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量-输入量=产量对转运站（中转点）：输入量-输出量=0对销地（收点）j：输入量-输出量=销量,.,21,三、转运问题,目标函数：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48约束条件：s.t.x13+x14600(1分厂供应量限制）x23+x24+x28400(2分厂供应量限制）-x13-x23+x35+x36+x37+x38=0（3转运站）-x14-x24+x45+x46+x47+x48=0（4转运站）x35+x45=200 x36+x46=150 x37+x47=350 x38+x48+x28=300 xij0,i,j=1,2,3,4,5,6,7,8,.,22,三、转运问题,用“管理运筹学”软件求得结果：x13=550 x14=50；x23=0 x24=100 x28=300；x35=200 x36=0 x37=350 x38=0；x45=0 x46=150 x47=0 x48=0。最小运输费用为：4600百元如何把转运问题转化为运输问题？,.,23,举例说明表上作业法,例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：,.,24,第一步：确定初始基可行解最小元素法、伏格尔法,最小元素法思路：按单位运价的大小决定供应的先后，优先满足单位运价最小者的供销要求。即从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。,.,25,最小元素法举例,8,2,2,0,10,10,0,6,14,8,6,8,0,0,0,0,6,0,.,26,最小元素法举例,最小元素法缺点：有时为了优先考虑某一最小元素，却可能使其他供销点的运输费用大大增加，会出现顾此失彼。,考虑运价差,.,27,罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。,对差额最大处，采用最小运费调运。,伏格尔法思路：,.,28,结合例1说明这种方法。,0,4-4=0,第一次,.,29,结合例1说明这种方法。,1,3-2=1,第一次,.,30,结合例1说明这种方法。,1,第一次,.,31,结合例1说明这种方法。,4-2=2,2,1,5,3,第一次,.,32,结合例1说明这种方法。,14,8,0,优先安排销地，否则运价会更高,下次不考虑该列,第一次,.,33,第二次,结合例1说明这种方法。,优先安排销地，否则运价会更高,8,0,6,下次不考虑该行,.,34,结合例1说明这种方法。,下次不考虑该列,8,0,2,第三次,.,35,结合例1说明这种方法。,4,12,0,下次不考虑该列,第四次,.,36,结合例1说明这种方法。,4,2,0,0,0,第五次,.,37,例1用伏格尔法得到的初始基可行解,目标函数值,用最小元素法求出的目标函数z=246,一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。,.,38,第二步：解的最优性检验,闭回路法思路：计算空格（非基变量）的检验数,若令则,如何求检验数？,分析：,即增加1个单位的检验数=相应的运费增量,.,39,从初始表分析：,要保证产销平衡，则,称为闭回路,+1,-1,+1,-1,.,40,2,1,.,41,检验数表,2,1,1,-1,10,12,表中的解不是最优解。,.,42,第三步：解的调整,从检验数为负值的格出发，做一条除该空格外其余顶点均为有数字格组成的闭回路。在这条闭回路上对空格的运量作最大可能的调整。,（-2）,（-2）,（+2）,（+2）,.,43,调整后的解为：,此时的解为最优解。,最优解不唯一,.,44,运输问题练习1,求解运输问题,.,45,运输问题练习2,有甲乙丙三个商品产地，商品的运出量分别为25t、18t、5t，ABCD四个销售地，运入量分别为16t、20t、5t、7t，运输费用与各地之间的运输距离成正比，运输距离和运输量如下表所示，求合理的调运方案及最小吨公里。,.,46,2.位势法所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值vj，它们的数值是由基变量xij的检验数所决定的，则非基变量xij的检验数就可以用公式求出。,4,8,7,5,3,6,9,4,5,4,5,3,最优解的判定,.,47,四、如何找多个最优方案,识别是否有多个最优解的方法,只需看最优方案中是否存在非基变量的检