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

第三章运输问题3.1运输问题及其数学模型

3.2表上作业法3.3产销不平衡的运输问题及其应用表

上

作

业

法得到最优方案算出的总运价分析实际问题列出产销平衡表及单位运价表求检验数（闭回路法或位势法）

是确定初始调运方案（西北角法、最小元素法或Vogel法）

找出绝对值最大的负的检验数用闭回路调整，得出新的调运方案否循环所有检验数≥0求

解步骤3.3产销不平衡运输问题及其应用一、产销不平衡问题1产销2销产二、一些变形和推广三、有转运的运输问题在实际问题中，产大于销意味着某些产品被积压在仓库中。可以这样设想，如果把仓库也看成是一个假想的销地，并令其销量刚好等于总产量与总销量的差；那么，产大于销的运输问题就转换成产销平衡的运输问题

假想一个销地，相当于在原产销关系表上增加一列。由于假想的销地代表的是仓库，实际上没有产生运输，所以假想列所对应的运价应取为“0”。至此，我们又将销大于产的运输问题转换成了产销平衡的运输问题。一、产销不平衡的问题1、产大于销的运输问题

产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnBn+1０

０┆０销量产量b1 b2 ┈

bna1a2┊amaibj相当于：增加一个假想销地产销问题单位运价表产量约束销量约束m+n+1个约束条件m×(n+1)个决策变量表一甲乙丙丁产量（ai）A3113107B19284C7410512销量（bj）3656解此运输问题的总产量为23、总销量为20，所以假设一个销地戊并令其销量刚好等于总产量与总销量的差“3”。取假想的戊列所对应的运价都为“0”，可得下表所示的产销平衡运输问题。例1

将表一所示的产大于销的运输问题转换成产销平衡的运输问题甲乙丙丁戊产量（ai）A31131007B192804C74105012销量（bj）36563B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因为有：

例2

求下列表中极小化运输问题的最优解。所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180－160=20的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列这样可得新的运价表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表为计算结果。可看出：产地A4还有20个单位没有运出。2.销大于产的运输问题

可以这样设想，假想一个产地，并令其产量刚好等于总销量与总产量的差；那么，销大于产的运输问题同样可以转换成产销平衡的运输问题假想一个产地，相当于在原产销关系表上增加一行。

由于假想的产地与各销地之间并不存在实际的运输，所以假想的产地行所有的运价都应该是“0”至此，我们又将销大于产的运输问题转换成了产销平衡的运输问题。

产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+10 0 ┈ 0销量产量b1 b2 ┈

bna1a2┊ambjai销产问题单位运价表相当于：增加一个假想产地产量约束销量约束m+n+1个约束条件(m+1)×n个决策变量表二甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）11656解此运输问题的总产量为20、总销量为28，所以假设一个产地D并令其产量刚好等于总销量与总产量的差“8”。令假想的D行所对应的运价都为“0”，可得下表所示的产销平衡运输问题。例3

将表二所示的销大于产的运输问题转换成产销平衡的运输问题甲乙丙丁产量（ai）A3113107B19284C741059D00008销量（bj）11656产销不平衡问题小结（变成产销平衡问题）当总产量>总销量时，可增加一个假想销地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’例2中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～210例4

需求量不确定的运输问题先作如下分析：

（1）总产量为180，B1，…，B4的最低需求量

20+50+35+45=150，这时属产大于销；（2）B1，…，B4的最高需求是60+70+35+45=210，这时属销大于产（3）虚设一个产地A5，产量是210－180=30，A5的产量只能供应B1或B2。（4）将B1与B2各分成两部分的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，…，A4供应，可由A1、…、A5供应。（5）上述A5不能供应某需求地的运价用大M表示，A5到的运价为零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到这样的平衡表后，计算得到最优方案表2。表2

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。B1B2B3B4产量A11613221750

A21413191560A3192023M50最低需求3070010最高需求507030不限例5：设某种材料有A1、A2、A3三个生产厂家，其产品供应B1、B2、B3、B4四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？B1B2B3B4产量A11613221750

A21413191560A3192023M50最低需求3070010最高需求507030不限B1’B1’’B2B3B4’B4’’销量302070301050A1A2A3A4产量50605050161419M1614190131320M22192301715MM1715M0三、有转运的运输问题几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.所有中转站的转运量等于总的产量之和；3.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为Cij=0；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。三、有转运的运输问题1、运输表的构成1）产地：原产地、中间转运站、转运物资的销地2）销地：原销地、中间转运站、转运物资的产地3）设各转运站转运物资的数量均为∑ai这样专职转运站的产量和销量均为∑ai而原产地Ai的产量均为（ai+∑ai）原销地Bj的销量均为（

bj+∑ai）4)将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用M表示。例6

扩大的运输问题例：在前面的糖果例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称扩大的运输问题。A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130产销产量销量2724292020

20

202020

20

202020

202020

20

2023262526产销平衡表例7A、B两个化肥厂每年各生产磷肥900万吨、600万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口C、D、E每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间均有公路相通，且已知单位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？ABCDEA029107B2071010C97034D1010302E710420ABCDEA029107B2071010C97034D1010302E710420P发量收量240021001500150015001500150022001900180010000000例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ2535301010.811.111.011.3运输问题案例1数学模型：设xij第i季度生产，用于第j季度交货的数量。目标函数：

minz=cijxiji=1j=1

44x11+x12+x13+x1425

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20xij0,(i=1,····,4;j=1,····,4)供应：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ2535301010.811.111.011.3某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。合同要求交货不得超过生产力产>销数学模型：季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ2535301010.811.111.011.3每台每积压一个季度需要存储维护费用0.15万元。单位运价表：ⅠⅡⅢⅣ销量ⅠⅡ Ⅲ ⅣD产量10.8 10.95 11.1011.25025

M11.1011.25

11.40035

M

M 11.00

11.15030单位：万元供应需求10 15 25

2030M MM

11.30010当i>j时，必须xij=0，令cij=M(很大的正数)，加以惩罚产>销

例二有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化肥，三个工厂每年各自的产量为A--50万吨，B--60万吨，C--50万吨。四个地区的需求量分别是Ⅰ地区最高50万吨，最低30万吨，Ⅱ地区为70万吨，Ⅲ地区为30万吨以下，Ⅳ地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地A1A2A3B1B2B3B4产量销量1613221714131915192023―单位运价表50605030-50700-3010-单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量运输问题案例2销产上限50运输问题案例2ABCDⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ

16 16 13 22 17 17

14 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供应需求产量销量50605050

30

20

70

30

10

50修正运价表产地销地A1A2A3B1B2B3B4产量销量1613221714131915192023―单位运价表50605030-50700-3010-单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量销产

某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？运输问题案例3设xj—第j天使用新毛巾的数量；yij—第i天送第j天使用快洗餐巾的数量；zij—第i天送第j天使用慢洗餐巾的数量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14