chap 5运输问题是线性特例

第五章 运输问题1运输问题是线性规划问题的特例。产地：货物发出的地点。销地：货物接收的地点。产量：各产地的可供货量。销量：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。第一节运输模型一、运输问题举例某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。销地产地B1B2B3B4产量A163255A275842A332973销量23142第一节运输模型3供应平衡条件①②③销售平衡条件④⑤⑥⑦非负性约束x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34

=3x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4xij≥0

(i=1,2,3；j=1,2,3,4)运输问题的LP模型决策变量

设从Ai到Bj的运输量为xij，目标函数min

Z

=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34约束条件

产量之和等于销量之和,故要满足：第一节运输模型二、表式运输模型销地产地B1B2…Bn产量A1c11

x11c12

x12…c1n

x1na1A2c21x21c22x22…c2nx2na2………………Amcm1

xm1cm2

xm2…cmn

xmnam销量b1b2…bn∑ai∑bj4产销平衡5第一节运输模型三、运输问题的三种类型m

n

ai

=

bji=1

j

=1

‡

0

xj

=

1,2,...,nx

b

,i

=

1,2,...,ms.t.

ij

i

=1

ij

=

j

n

j

=1

m

xij

=

ai

,m

nmin

z

=

cij

xiji

=1

j

=1第一节运输模型产大于销6mnjii=1

a

>

bj

=1

‡

0

xj

=

1,2,...,nx

b

,

x

£

a

, i

=

1,2,...,ms.t.

ij

m

i

=1

ij

=

j

n

j

=1iijm

nmin

z

=

cij

xiji

=1 j

=1第一节运输模型7产小于销m

nji

a

<

bi=1

j

=1

‡

0

xj

=

1,2,...,nx

b

,

x

=

a

, i

=

1,2,...,ms.t.

ij

m

i

=1

ij

£

j

n

j

=1iijm

nmin

z

=

cij

xiji

=1 j

=1第一节运输模型系数矩阵的结构如下：四、运输模型的特点决策变量m·n

约束方程m+n

1

1111111

11

1

1

1

1

1A

=

…

…x11

x12

x1n

x21

x22

x2n

1

1

1

…

…

…

…xm1

xm2…

xmn

m

行

n

行稀

疏阵

8第二节表上作业法9表上作业法：适合于产销平衡的运输问题求解步骤：找出初始方案（初始基可行解）：在m·n维产销平衡表上给出m+n-1个数字。最优性检验：计算各非基变量的检验数，当sij‡0最优。方案调整与改进：确定进基变量和离基变量，找出新的基可行解。第二节表上作业法10最小元素法“就近运给”，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量min{ai

,bj}。最大差额法不能按最小运费就近供应，就考虑次小运费。

各行(各列)的最小运费与次小运费之差称为行差(列差)。差额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。一、确定初始方案第二节表上作业法销地产地B1

B2

B3

B4产量A163

2

55A275

842A332

973销量2

3

1

4③0②①

②②初始基可行解：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=3811最小元素法从单位运价表中逐次挑选最小元素，安排运量min{ai

,bj}。然后，划去该元素所在行或列：有两个最小元素，当产大于销，划去该元素所在任列选；其一，当产小于销，划去该元素所在比行如。选c13第二节表上作业法12最大差额法

对每行每列的运价cij

分别计算两最小元素之差（取正值），将行差记于表右侧，将列差记于表下端。在所有行差、列差中选一最大差额，若几个同时最大，任选其一。在最大差额所在行（列）中选一最小运价，若几个同时最小，任选其一。在(3)中所确定的最小运价格内，确定基变量数值并画圈，然后划去所在行或列，具体做法同最小元素法。对剩余未划去的行列重复上述步骤，但当只剩下最后一行（列）时，不再计算行（列）差，而直接按最小元素法分配运量，并

划去相应的行或列。第二节表上作业法最大差额法销地产地B1B2B3B4产量

行差A163255

1A275842

1A33297销量231461①221

1②

①②1②②此时只剩下最后一列，不列差再计3算行差、列1差，直接按最小元素法分配运量x24=2，划去第二行，再分配x14=2，2得到一个初始方案。初始基可行解：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=34后面将会验证，这里给出13的初3始方案1是最优1方案。5最大差额法并不一定对所有平衡问题都给出最优方1案0，但一般说来，它给出的方案比最小元素法要好。第二节表上作业法位势法计算检验数检验数：ui代表产地Ai的位势量，vj代表销地Bj的位势量。基变量的检验数为0，即二、最优性检验判别方法是计算非基变量的检验数：运输问题的目标函数要求为最小，即当sij‡0视为最优。将基变量（画圈数字）所在格的运价分解为两部分：cij=ui+vj并令u1

=0，计算各行各列的位势量。位势量ui、vj

的总数为m+n

个，而由m+n-1个基变量的运价限定的关于ui、vj

的方程cij=ui+vj

只有m+n-1个，所以ui、vj

有无穷组解。任选一个ui

或vj并赋予任一数值，就可确定所有的ui、

vj

的值。一般的，令u1

=0。14σij

=

cij

-

(ui

+

v

j

)σij

=

cij

-(ui

+

v

j

)

=

0,第二节表上作业法位势法基变量的检验数sij=cij

–ui

–vj

=0，即cij

=ui

+vj

，且令u1

=0，计算位势量ui

和vj销地产地产量A16B1

B2

B3

B43

2

5②

①

②5A275②2A3302③8

49

73销量2314uivj0625-1-3515第二节表上作业法位势法（续）计算非基变量的检验数sij=cij

–ui

–vj填在每个非基变量空格的右下角销地产地B1B2B3B4产量uiA16②3-22①5②50A27251874②2-1A3302③910753-3销量2314vj652516非基变量x12的检验数s12=c12–u1–v2=-2，即让非基变量x12从0增到1，可使总运费减少2个单位，故可以断定最小元素法给出的初始方案非最优。第二节表上作业法17三、改进的方法（闭回路调整法）确定进基变量检查非基变量xij的检验数sij

，按min{sij|

sij

<0}=

slk

确定xlk进基。确定离基变量非基变量xlk进基之后，能让它的运量增加多少呢？就要求它所在行和列的运量保持产销平衡。保持产销平衡的方法是闭回路法。闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。闭回路的画法：从进基变量xlk所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90º，继续前进，直到返回始点。奇偶点：始点是偶点，依次奇偶相间标注；偶点标“+”，表示运量增加量；奇点标“-”，表示运量减少量。调整量：最小可减少的运量，即奇点运量的最小值。 奇点运量的最小值所在格的基变量离基。第二节表上作业法销地产地B1B2B3B4产量A1632①5②5A27584②2A30973销量

2

3x12

进基最小调整量为2，x11

离基14+

x1218-

②3+2-③第二节表上作业法非最优方案的调整所有偶点的值都加上调整量；所有奇点的值都减去调整量；获得一个新的运输方案。基可行解：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=3419销地产地B1B2B3B4产量A16②3②2①5②5A27584②2A33②02③①973销量2314第二节表上作业法四、最优性检验基变量的检验数sij

=cij

–ui

–vj

=0，且令u1

=0，计算位势量ui和vj所有非基变量xij的检验数sij=cij

–ui–vj≥0，即得最优解。20销地产地B1B2B3B4产量uiA1623②2①5②50A27453874②2-1A33②2①98733-1销量2314vj4325第三节产销不平衡问题21产销平衡的运输问题采取表上作业法求解。产销不平衡的运输问题需划成产销平衡问题再求解。产大于销：虚设一个销地Bk(多余物资的存储)，其运价为0，销量(存储量)为产销量之差bk

=

ai

-

bj。产小于销：虚设一个产地Al

(不足物资的脱销量)，其运价为0，产量

(脱销量)为销产量之差ak

=

bj

-

ai

。第三节产销不平衡问题增加一个销地一、产大于销销地产地B1B2B3产量50-4622B4销地产地B1B2B3产量A159215A231718A362817销量1812165046A1592015A2317018A3628017销量1812164

50

50第三节产销不平衡问题初始基可行解销地产地B1B2B3B4产量A1592015A2317018A36280171215⑥12①④23销量

18

12

16

4初始基可行解：x13=15,

x21=6,

x22=12,

x31=12,

x33=1,

x34=4，Z=140第三节产销不平衡问题最优性检验销地产地B1B2B3B4产量uiA15591121506150A23⑥1127203183A36122-28①0④176销量1812164vj0-22-624非基变量x32的检验数s32=-2，即让非基变量x32进基。第三节产销不平衡问题闭回路调整销地产地B1B2B3B4产量A159215015A2317018A368①0④17销量

18

12x32

进基最小调整量为12，x22

离基164-

1225+⑥-

122+x32第三节产销不平衡问题非最优方案的调整所有偶点的值都加上调整量；所有奇点的值都减去调整量。基可行解：x13=15,x21=18,x31=0,x32=12,x33=1,x34=4，Z=116销地产地B1B2B3B4产量A159215015A231⑥81127018A361022128①0④17销量181216426第三节产销不平衡问题最优性检验基变量的检验数sij=cij

–ui

–vj

=0，且令u1

=0，计算位势量ui

和vj所有非基变量xij的检验数sij

=cij

–ui–vj

≥0，即得最优解。销地产地B1B2B3B4产量uiA15591321506150A2318127203183A3602128①0④176销量1812164vj0-42-627第三节产销不平衡问题增加一个产地二、产小于销23-2228销地产地B1B2B3产量A141210A234312销量81052223销地产地B1B2B3产量A141210A234312A30001销量81052323第三节产销不平衡问题初始基可行解销地产地B1B2B3产量A141210A234312A30001销量100⑤⑦①8

10

5初始基可行解：x12=10,

x13=0,

x21=7,

x23=5,

x31=1，Z=4629第三节产销不平衡问题最优性检验销地产地B1B2B3产量ui23⑦423⑤121A30①01001-2销量8105vj21230–

检验数sij≥0，得最优解:x12=10,x13=0,x21=7,x23=5,x31=1，Z=46–

由于非基变量x33

的检验数s33=0，为多重最优解。让x33进基,x31离基,得另一最优解:x12=10,x13=0,x21=8,x23=4,x33=1第四节运输模型的应用31一、短缺资源的分配问题短缺资源分配，“产小于销”，需注意产销配比问题。上例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，引水费如下表：供区水库甲乙丙丁供水量kt/dA1613221750B1413191560C192023--50最低需求kt/d3070010最高需求kt/d507030不限32如何分配供水量，保障各区最低需求，获利最大？第四节运输模型的应用33分析利润=收入-成本，收入最大，成本最小，则利润最大。收入：每天供水总量是一常数，水价也是常数，则每天总收入也是常数。每天供水总量若能全部售出，每天总收入则能达到最大。丁区最高需求不限，每天总供水量能全售出。每天总收入是常数，与水量分配无关，可以不予考虑。成本：各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。各区引水费不同，如果总的引水费达到最小，总成本则最低。如何分配水量，既满足最低需求，又使总的引水费最低？最大需求量：

供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求量160-110+10=60。

四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于销的不平衡问题。第四节运输模型的应用产小于销的运输问题化为平衡问题,虚设水库D,供水量50.各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单位引水费（运费）为M。

各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故单位引水费（运费）为0

。供区水库甲1甲2乙丙丁1丁2供水量A16161322171750B14141319151560C19192023MM50DM0M0M050销量30207030105034第四节运输模型的应用用表上作业法求得最优方案（用最大差额法给出的初始方案即为最优）供区水库甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050D302050销量30207030105035–

最优分配方案：水库A向乙区供水50，水库B分别向乙区、丁区供水20和40，水库C向甲区供水50，不给丙区供水。–

最小引水管理费：13

50+13 20+

15(10+30)+19(30+20)

=2460其他管理费：45

(50+60+50)=7200–

总成本：2460

=9600总收入：90(50+60+50)=14400–

最大获利：14400-9600=4740第四节运输模型的应用二、资源转运问题产地与销地之间存在转运站。