产销不平衡的运输问题及其应用解析

1、第三章 运输问题,3.1 运输问题及其数学模型 3.2 表上作业法 3.3 产销不平衡的运输问题及其应用,表上作业法,得到最优方案算出的总运价,分析实际问题 列出产销平衡表 及单位运价表,求检验数 （闭回路法或位势法）,确定初始调运方案 （西北角法、最小元素法 或Vogel法）,找出绝对值最大的负的检验数用闭回路调整，得出新的调运方案,求解 步 骤,3.3产销不平衡运输问题及其应用,一、产销不平衡问题,1产销,2销产,二、一些变形和推广,三、有转运的运输问题,在实际问题中，产大于销意味着某些产品被积压在仓库中。可以这样设想，如果把仓库也看成是一个假想的销地，并令其销量刚好等于总产量与总销量的差

2、；那么，产大于销的运输问题就转换成产销平衡的运输问题 假想一个销地，相当于在原产销关系表上增加一列。 由于假想的销地代表的是仓库，实际上没有产生运输，所以假想列所对应的运价应取为“0”。 至此，我们又将销大于产的运输问题转换成了产销平衡的运输问题。,一、产销不平衡的问题 1、产大于销的运输问题,产地,销地,A1 A2 Am,B1B2Bn,C11C12C1n C21C22C2n Cm1Cm2Cmn,Bn+1, ,销量,产量,b1b2bn,a1 a2 am,aibj,相当于：增加一个假想销地,产销问题单位运价表,m+n+1个约束条件,m(n+1)个决策变量,表一,解 此运输问题的总产量为23、总销

3、量为20，所以假设一个销地戊并令其销量刚好等于总产量与总销量的差“3”。取假想的戊列所对应的运价都为“0”，可得下表所示的产销平衡运输问题。,例1 将表一所示的产大于销的运输 问题转换成产销平衡的运输问题,因为有：,例2 求下列表中极小化运输问题的最优解。,所以是一个产大于销的运输问题。,表中A2不可达B1，用一个很大的正数M表示运价C21。虚 设一个销量为b5=180160=20的销地B5，Ci5=0，i=1，2， 3，4。表的右边增添一列,这样可得新的运价表：,下表为计算结果。可看出：产地A4还有20个单位 没有运出。,2.销大于产的运输问题,可以这样设想，假想一个产地，并令其产量刚好等于

4、总销量与总产量的差；那么，销大于产的运输问题同样可以转换成产销平衡的运输问题 假想一个产地，相当于在原产销关系表上增加一行。 由于假想的产地与各销地之间并不存在实际的运输，所以假想的产地行所有的运价都应该是“0” 至此，我们又将销大于产的运输问题转换成了产销平衡的运输问题。,产地,销地,A1 A2 Am,B1B2Bn,C11C12C1n C21C22C2n Cm1Cm2Cmn,Am+1,0 0 0,销量,产量,b1b2bn,a1 a2 am,bjai,销产问题单位运价表,相当于：增加一个假想产地,m+n+1个约束条件,(m+1)n个决策变量,表二,解 此运输问题的总产量为20、总销量为28，所

5、以假设一个产地D并令其产量刚好等于总销量与总产量的差“8”。令假想的D行所对应的运价都为“0”，可得下表所示的产销平衡运输问题。,例3 将表二所示的销大于产的运输问题 转换成产销平衡的运输问题,产销不平衡问题 小结 （变成产销平衡问题） 当总产量总销量时，可增加一个假想销地Bn+1, 销量 ai bj，Ci,n+1=0， 当总产量总销量时，可增加一个假想产地Am+1,产量 bj ai ，Cm+1，j=0,二、一些变形和推广 销量不确定（有最高需求和最低需求） 设销地Bk的最低需求为bk，最高需求为bk” ，这时可把看作Bk和Bk”两个销地， Bk需求量bk ，Bk”的需求量bk” - bk,例

6、2中，假定B1的需要量是20到60之间，B2的需要量 是50到70，试求极小化问题的最优解。,例4 需求量不确定的运输问题,先作如下分析： （1）总产量为180，B1，B4的最低需求量 20+50+35+45=150，这时属产大于销；,（2）B1，B4的最高需求是60+70+35+45=210，这时属销大于产,（3）虚设一个产地A5，产量是210180=30，A5的产量只能供应B1或B2。,（4）将B1与B2各分成两部分 的需求量是20， 的需求量是40， 的需求量分别是50与20，因此 必须由A1，A4供应， 可由 A1、A5供应。,（5）上述A5不能供应某需求地的运价用大M表示，A5到 的

7、运价为零。得到下表的产销平衡表。,得到这样的平衡表后，计算得到最优方案表2。,表2,表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,例5：设某种材料有A1、 A2、 A3三个生产厂家，其产品供应 B1、 B2、 B3 、 B4四个城市，假定等量的材料在这些城市的 使用效果相同，已知各建材厂的年产量、各城市的年需求量 以及各厂到各城市运送单位建材的运价如表所示，求使运费 最少的调运方案？,B1,B1,B2,B3,B4,B4,销量,30,20,70,30,10,50,A1,A2,A3,A4,

8、产量,50,60,50,50,16,14,19,M,16,14,19,0,13,13,20,M,22,19,23,0,17,15,M,M,17,15,M,0,三、有转运的运输问题,几点说明： 1.所有的产地、销地、中间站均视作产地、销地； 2.所有中转站的转运量等于总的产量之和； 3.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为Cij=0； 4.实际产地产量为转运量与该产地实际产量之和，实际销地 销量为转运量与实际销量之和。,三、有转运的运输问题,1、运输表的构成 1）产地：原产地、中间转运站、转运物资的销地 2）销地：原销地、中间转运站、转运物资的产地 3）设各转运站转运物资的数

9、量均为 ai 这样专职转运站的产量和销量均为 ai 而原产地Ai的产量均为（ai+ ai） 原销地Bj的销量均为（ bj+ ai） 4)将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用M表示。,例6 扩大的运输问题,例：在前面的糖果例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称扩大的运输问题。,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,0 1 3 1 0 - 3 - 0,2 1 4 3 3 5 - 2 1 - 2 3,3 11 3 10 1

10、 9 2 8 7 4 10 5,2 3 1 1 5 - 4 - 2 3 2 3,3 1 7 11 9 4 3 2 10 10 8 5,0 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0,2 8 4 6 4 5 2 7 1 8 2 4 1 - 2 6,2 4 1 1 8 5 8 - 4 2 2 2 6 7 4 6,0 1 4 2 1 0 2 1 4 2 0 3 2 1 3 0,产,销,产量,销量,27 24 29,20 20 20 20,20 20 20 20,20 20 20,20 20 20 20,23 26 25 26,产销平衡表,例7 A、B两个化肥厂每年各生产磷肥900万吨

11、、600万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口C、D、E每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间均有公路相通，且已知单位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？,P,发量,收量,2400,2100,1500,1500,1500,1500,1500,2200,1900,1800,100,0,0,0,0,0,例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需

12、要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。,季度,生产能力,(台),单位成本,(万元/台),25353010,10.811.111.011.3,运输问题案例1,数学模型：,设 xij第i季度生产，用于第j季度交货的数量。,目标函数： min z= cij xij,i=1j=1,4 4,x11+x12+x13+x1425,x22+x23+x2435,x33+x3430,x4410,x11 =10,x12+x22 =15,x13+x23+x33 =25,x14+x24+x34+x44=20,xij 0 ,(i=1,4;j=1,4),供应：,需求：,某工厂按合

13、同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。,合同要求,交货不得超过生产力,产销,数学模型：,每台每积压一个季度需要存储维护费用0.15万元。,当ij时，必须xij=0，令cij=M(很大的正数)，加以惩罚,产销,例二 有A、B、C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区最高50万吨，最低30万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。,设 xij-第i工厂调至第j需求地区的化肥数量,运输问题案例

14、2,销产,上限50,运输问题案例2,设 xij-第i工厂调至第j需求地区的化肥数量,销产,某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？,运输问题案例3,设xj第j天使用新毛巾的数量；yij第i天送第j

15、天使用快洗餐巾的数量；zij第i天送第j天使用慢洗餐巾的数量；,第一天：x1=1000,第二天：x2+y12=700,第三天：x3+z13+y23=800,第四天：x4+z14+z24+y34=1200,第五天：x5+z15+z25+z35+y45=1500,需求约束,供应约束,新购餐巾： x1+x2+x3+x4+x55200,第一天送洗：y12+z13+z14+z151000,第二天送洗：y23+z24+z25700,第三天送洗：y34+z35800,第四天送洗：y451200,xj0，yij0，zij0，（i=1,4；j=1,5）,Min z=xj+0.2yij+0.1zij,数学模型：,第一天：x1=1000,第二天：x2+y12=7