《运筹学04运输问题》由会员分享，可在线阅读，更多相关《运筹学04运输问题（39页珍藏版）》请在金锄头文库上搜索。
1、1.运输模型 Transport Model 2.运输问题的表上作业法 Table Method of TP3.运输问题的进一步讨论 Further Discussion of TP4.运输问题的思考题及练习题Questions and Exercises for TP运输问题Transportation Problem1 运输模型v一般的运输问题就是要解决把某种产品从若干个产地Ai(i=1,2,m)调运到若干个销地Bj(j=1,2,n)，在每个产地的供应量ai(i=1,2,m)、每个销地的需求量bj(j=1,2,n)、Ai运输到Bj的单位运价cij已知的前提下，如何确定一个运输方案，使总运价
2、最低。v设xij为从Ai运输到Bj的产品数量，若ai=bj，则称为产销平衡的运输规划问题，数学模型为vmin f=c11x11+c1nx1n+c21x21+cmnxmnxi1+xi2+xin=ai (i=1,2,m)x1j+x2j+xmj=bj (j=1,2,n)xij0 (i=1,2,m;j=1,2,n)v有时运输问题的一般模型会有一些变化，如求目标函数的最大值某些运输线路的运输能力有一定限制生产地产量有所限制销售地销量有所限制总产量不等于总销量，即产销不平衡某些地方只是中转站v这些问题也可以转化为平衡运输问题v对产销平衡运输问题，若用u1,u2,um分别表示前m个约束等式相应的对偶变量，用
3、v1,v2,vn分别表示后n个约束等式相应的对偶变量，即对偶变量为Y=(u1,u2,um,v1,v2,vn)Tv运输问题的对偶问题可以写成vmax f=a1u1+amum+b1v1+bnvnui+vjcij (i=1,2,m;j=1,2,n)ui,vj任意v原问题变量xj的检验数j=cj-zj=cj-CBB-1Pj=cj-YPjv变量xij的检验数ij=cij-zij=cij-YPij=cij-(u1,u2,um,v1,v2,vn)Pij=cij-(ui+vj)2 运输问题的表上作业法v运输问题的数学模型及其约束方程组的系数矩阵结构具有特殊性，使用表上作业法解决运输问题，比单纯形法更为简便。v
4、表上作业法的步骤：第1步：确定初始基可行解第2步：解的最优性检验第3步：解的调整，转第2步v例1：某集团公司3个工厂A1、A2、A3生产同一产品的产量、4个销售点B1、B2、B3、B4的销量及单位产品的运价如下表。试确定使总运费最低的运输方案。工厂B1B2B3B4产量A141241116A22103910A38511622销量8141214第1步：确定初始基可行解v最小元素法(最低运价法)步骤：运价表中找出一个最低运价(即最小元素)cij在该处确定运量xij=min(ai,bj)计算剩余产量ai=ai-xij和剩余销量bj=bj-xij，则出现(1)ai=0，bj0划去第i行运价；(2)ai0
5、，bj=0划去第j列运价；(3)ai=0，bj=0划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量工厂B1B2B3B4产量A141241116A22103910A38511622销量8141214工厂B1B2B3B4产量A110616A28210A314822销量8141214(1)(2)(3)最低运价234运价标号c21c23c13线路x21x23x13数量比较8,102,1216,10运输数量8210新产量a2=2a2=0a1=6新销量b1=0b3=10b3=0划去第1列第2行第3列v西北角法步骤运价表中找出西北角(左上角)运价cij在该处确定运量xij=min(ai,bj
6、)计算剩余产量ai=ai-xij和剩余销量bj=bj-xij，则出现(1)ai=0，bj0划去第i行运价；(2)ai0，bj=0划去第j列运价；(3)ai=0，bj=0划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量v伏格尔法步骤运价表中计算每行和每列最小和次小运价之差，从差值最大的行或列中找出最小运价cij在该处确定运量xij=min(ai,bj)计算剩余产量ai=ai-xij和剩余销量bj=bj-xij，则出现(1)ai=0，bj0划去第i行运价；(2)ai0，bj=0划去第j列运价；(3)ai=0，bj=0划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量v
7、罗素法步骤运价表中找出每行和每列的最大值ui和vj，每个单元格计算ij=cij-ui-vj，找到最小值ij在该处确定运量xij=min(ai,bj)计算剩余产量ai=ai-xij和剩余销量bj=bj-xij，则出现(1)ai=0，bj0划去第i行运价；(2)ai0，bj=0划去第j列运价；(3)ai=0，bj=0划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量v任意方法也能获得初始运输方案，自己思考第2步：解的最优性检验v运输问题是否达到最优，可以这样考虑：在现有运输方案基础上作一点点调整，看看总成本作如何改变。如，某运输线路上原先没有运输数量，现在增加一个单位的运输数量，成本
8、该如何改变？为了保证数量平衡，这就要用到闭合回路思路了。v闭回路法思路选定一个空格(非基变量)，顺次从垂直和水平两个方向交替寻找闭合回路(该空格和大于零的数字构成封闭多边形，只有横直线)从空格开始，把对应运价交替相加和相减，得到的结果填入该空格，即为检验数检验数0，方案不能调整；检验数0，方案不能调整；检验数总销量，属于产大于销的产销不平衡运输问题。增加一个销地，销量b5=22-18=4；运价为0。得到产销平衡表如左表。表上作业法结果见右表。产地 B1B2B3B4B5产量产地 B1B2B3B4B5产量A141241108A11-4048A22103905A24-1-15A38511609A31
9、039659销量43564销量43564v例3：设3个化肥厂供应4个地区的农用化肥。各化肥厂年产量(万吨)、各地区年需求量(万吨)以及各化肥厂到各地区单位运价(万元/万吨)见表。试求总运费最低的化肥调拨方案。产地产量A1613221750B1413191560C192023M50最低需求3070010最高需求507030解答v总产量=50+60+50=160(万吨)；最低需求量=30+70+0+10=110(万吨)，最高需求=。根据现有产量，地区最多需求数量=160-110+10=60(万吨)，这样最高需求=50+70+30+60=210(万吨)，大于总产量，产销不平衡。v假定有一家化肥厂D生
10、产化肥，产量=210-160=50(万吨)。地区最低需求30万吨，不能由D提供，运价设定为M；类似，所有地区最低需求都不能由D提供。而超过最低需求的部分可以由D提供，这时表明所需数量不能满足，设定运价为0。这样得到产销平衡的运输问题(如上表)，并求得其最优解(如下表)。产地产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量302070301050产地产量A5050B20103060C3020050D302050销量302070301050有存储费用的运输问题v例4：对下表所示的运输问题，若产地有一个单位物资没运出就发生存储费用，假设
11、3个产地单位物资存储费用分别为4、4、3；又假设产地2的物资最多运出35，产地3的物资最少运出28。试求最优运输方案。产地123产量112220214540323330销量302020产地123123产量11224MM202145M4M403233MM330销量3020201352产地123123产量181202022218403208230销量3020201352216目标函数求最大值的运输问题v例5：某农场有土地900亩，分为3类(A1,A2,A3)，计划种植3种作物(B1,B2,B3)，各类型土地面积、各作物所需面积、每种作物单位产值如表。求使农作物总产值最多的布局方案。土地类型B1B2
12、B3供给量A1700500480100A2850700600400A3400300500400需求量300200400土地类型B1B2B3供给量A1700500480100A2850700600400A3400300500400需求量300200400土地类型B1B2B3供给量A1501000100A2300100-400A3-270-220400400需求量300200400575000土地类型B1B2B3供给量A1700500480100A2850700600400A3400300500400需求量300200400土地类型B1B2B3供给量A1100-400100A2200200-304
13、00A3-420-270400400需求量300200400580000有转运的运输问题v中转站运输问题存在中途临时储存的设施，即中转站。这类运输问题称为转运问题(Transshipment problem)。v建模思路从发送及接受角度考虑产地只有发送而无接受销地只有接受而无发送中转站既有发送又有接受，且发送和接受数量相等此路不通者运价为无穷大(大M表示)4 运输问题的思考题及练习题v判断题(概念)1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含(m+n-1)个非零的xij，且满足xij=ai(i=1,2,n)，xij=bj(j=1,2,n)，就可以作为一个初
14、始基可行解。3、按最小元素法(或伏格尔法)给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。 4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。5、如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k，最优调运方案将不会发生变化。6、如果运输问题单位运价表的某一个(或某一列)元素分别乘上一个常数k，最优调运方案将不会发生变化。v运输问题的对偶问题某运输问题可以叙述如下：有n个地区需要某种物资，需要量分别为b1,b2,bn，这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别为a1,a2,am，已知从i地区工厂至第j个需要地区单位物资的运价
15、为cij，又供需平衡(即a1+am=b1+bn)。如何调运物资使总运输费用最低？阐述其对偶问题，并解释对偶变量的经济意义。v运输问题的灵敏度分析已知某运输问题的产量、销量及单位运价如下表。要求：(1)用表上作业法找出最优调运方案。(2)分别讨论c11和c23使最优方案不变的变化范围。产地B1B2B3产量A14258A23537A31324销量485v可转化为运输问题来求解v求解下列线性规划问题vmin z=100x11+140x12+110x13+180x21+150x22+160x23x11+x12+x13=30x21+x22+x23=20x11+x21=10x12+x22=15x13+x23=25x11,x12,x13,x21,x22,x230v下表给出一个运输问题及它的一个解(左边运量，右边运价)。试问：(1)表中给出的解是否为最优解？(2)若c24由1变为3，最优解是否改变？如何改变？(3)若所有运价均增加1，最优解是否改变？为什么？(4)若所有运价均减去1，最优解是否改变？为什么？(5)写出该问题的对偶问题，并给出其最优解。产地B1B2B3B4产量A14513468A281262110A33735114销量8563
