管理运筹学讲义：运输问题

1、1,第五章 运输问题,运输问题是线性规划问题的特例。 产地：货物发出的地点。 销地：货物接收的地点。 产量：各产地的可供货量。 销量：各销地的需求数量。 运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小,2,第一节 运输模型,某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案,一、 运输问题举例,3,第一节 运输模型,1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数 minZ=6

2、x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件。产量之和等于销量之和,故要满足： 供应平衡条件,x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3,销售平衡条件,x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=1,非负性约束 xij0 (i=1,2,3；j=1,2,3,4,运输问题的LP模型,4,第一节 运输模型,二、表式运输模型,5,第一节 运输模型,产销平衡,三、运输问题的三种类型,6,第

3、一节 运输模型,产大于销,7,第一节 运输模型,产小于销,8,第一节 运输模型,决策变量mn 约束方程m+n 系数矩阵的结构如下,四、运输模型的特点,9,第二节 表上作业法,表上作业法适合于产销平衡的运输问题 求解步骤： 找出初始方案（初始基可行解）：在mn维产销平衡表上给出m+n-1个数字。 最优性检验：计算各非基变量的检验数，当ij0最优。 方案调整与改进：确定进基变量和离基变量，找出新的基可行解,10,第二节 表上作业法,最小元素法 “就近运给”， 从单位运价表中最小运价开始确定供销关系， 逐次挑选最小元素，安排运量minai , bj。 最大差额法 不能按最小运费就近供应，就考虑次小运

4、费。 各行(各列)的最小运费与次小运费之差称为行差(列查)。 差额越大，说明不能按最小运费调运时，运费增加最多。 对最大差额处就采用最小运费调运,一、确定初始方案,11,第二节 表上作业法,从单位运价表中逐次挑选最小元素，安排运量 minai,bj。 然后，划去该元素所在行或列： 当产大于销，划去该元素所在列； 当产小于销，划去该元素所在行,最小元素法,初始基可行解：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=38,12,第二节 表上作业法,判别方法是计算非基变量的检验数： ij= cij CBPij= cij CBB-1Pij 运输问题的目标函数要求为最小，即

5、当ij0视为最优。 位势法计算检验数 ij= cij CBPij= cij CBB-1Pij ij = cij (ui+vj ) ui代表产地Ai的位势量，vj代表销地Bj的位势量。 基变量的检验数为0，即ij= cij ui vj =0， 并令u1 =0，计算各行各列的位势量,二、最优性检验,13,第二节 表上作业法,基变量的检验数ij= cij ui vj =0， 即cij =ui +vj ， 且令u1 =0，计算位势量ui和vj,位势法,14,第二节 表上作业法,计算非基变量的检验数ij= cij ui vj,位势法（续,2,2,1,7,10,5,非基变量x12的检验数12= c12 u

6、1 v2 =-2，即让非基变量x12从0增到1，可使总运费减少2个单位,15,第二节 表上作业法,确定进基变量 检查非基变量xij的检验数ij ，按 minij| ij 0= lk 确定xlk进基。 确定离基变量 非基变量xlk进基之后，能让它的运量增加多少呢？ 就要求它所在行和列的运量保持产销平衡。 保持产销平衡的方法是闭回路法。 闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。 闭回路的画法：从进基变量xlk所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90，继续前进，直到返回始点。 奇偶点： 始点是偶点，依次奇偶相间标注；偶点标“+” ，表示运量增加量

7、；奇点标“-” ，表示运量减少量。 调整量：最小可减少的运量，即奇点运量的最小值。 奇点运量的最小值所在格的基变量离基,三、改进的方法（闭回路调整法,16,第二节 表上作业法,x12 进基 最小调整量为2， x11 离基,17,第二节 表上作业法,非最优方案的调整 所有偶点的值都加上调整量； 所有奇点的值都减去调整量； 获得一个新的运输方案,基可行解：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=34,18,第二节 表上作业法,基变量的检验数ij= cij ui vj =0，且令u1 =0，计算位势量ui和vj,四、最优性检验,所有非基变量xij的检验数ij= c

8、ij ui vj0，即得最优解,19,第三节 产销不平衡问题,产销平衡的运输问题采取表上作业法求解。 产销不平衡的运输问题需划成产销平衡问题再求解。 产大于销： 虚设一个销地 Bk (多于物资在产地存储)，其运价为0， 销量(存储量)为产销量之差 bk =ai- bj。 产小于销： 虚设一个产地 Al (不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差 ak = bj - ai,20,第三节 产销不平衡问题,增加一个销地,一、产大于销,50-46,50 46,50 50,21,第三节 产销不平衡问题,初始基可行解,12,15,6,12,1,4,初始基可行解：x13=15,x21=6,

9、x22=12,x31=12,x33=1,x34=4，Z=140,22,第三节 产销不平衡问题,最优性检验,0,2,6,3,2,5,11,6,2,3,2,非基变量x32的检验数32= -2，即让非基变量x32进基,23,第三节 产销不平衡问题,闭回路调整,x32 进基 最小调整量为12， x31 离基,24,第三节 产销不平衡问题,非最优方案的调整 所有偶点的值都加上调整量；所有奇点的值都减去调整量,基可行解：x13=15,x21=18,x31=0,x32=12,x31=1,x34=4，Z=34,25,第三节 产销不平衡问题,基变量的检验数ij= cij ui vj =0，且令u1 =0，计算位

10、势量ui和vj,最优性检验,所有非基变量xij的检验数ij= cij ui vj0，即得最优解,0,2,6,3,5,13,6,2,3,2,26,第三节 产销不平衡问题,增加一个产地,二、产小于销,23-22,22 23,23 23,27,第三节 产销不平衡问题,初始基可行解,10,0,5,7,1,初始基可行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=46,28,第三节 产销不平衡问题,最优性检验,0,1,2,2,2,2,1,0,检验数ij0，得最优解:x12=10, x13=0, x21=7, x23=5, x31=1，Z=46 由于非基变量 x33 的检验数33=0

11、，为多最优解。 让x33进基,x31离基,得另一最优解:x12=10, x13=0, x21=8, x23=4, x33=1,29,第四节 运输模型的应用,短缺资源分配，“产小于销”，需注意产销配比问题。 上例x12=10, x13=0, x21=7, x23=5, x31=1，表示销地B1脱销1个单位； 然而x12=10, x13=0, x21=8, x23=4, x33=1 ，则表示销地B3 脱销1个单位； 但销地B3 的销量为5，本身就很少，不允许脱销，如何处理呢？ 自来水分配问题：水价90元/kt，管理费45元/kt，引水费如下表,一、短缺资源的分配问题,如何分配供水量，保障各区最低需

12、求，获利最大,30,第四节 运输模型的应用,利润=收入-成本，收入最大，成本最小，则利润最大。 收入： 每天供水总量是一常数，水价也是常数，则每天总收入也是常数。 每天供水总量若能全部售出，每天总收入则能达到最大。 丁区最高需求不限，每天总供水量能全售出。 每天总收入是常数，与水量分配无关，可以不与考虑。 成本： 各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。 各区引水费不同，如果总的引水费达到最小，总成本则最低。 如何分配水量，既满足最低需求，又使总的引水费最低？ 最大需求量： 供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求

13、量160-110+10=60。 四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于销的不平衡问题,分析,31,第四节 运输模型的应用,产小于销的运输问题化为平衡问题，虚设水库D，供水量50。 各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单位引水费（运费）为M。 各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故单位引水费（运费）为0,32,第四节 运输模型的应用,用表上作业法求得最优方案,最优分配方案：水库A向乙区供水50，水库B分别向乙区、丁区供水20和40，水库C向甲区供水50，不给丙区供水。 最小引水费：1350+1320+ 15(10+30)+19(30+20) =2460 引水管理费：45(50+60+50)=7200 总成本：2460+7200=9600 总收入：90(50+60+50)=14400 最大获利：14400-9600=4740,33,第四节 运输模型的应用,产地与销地之间存在转运站。 面粉转运问题：三个面粉加工厂，两个糕点生产厂，两个中转站,二、资源转运问题,如何调运，总运费最低,34,第四节 运输模型的应用,最