物流运筹学 课件 第4章 物流运输

运输问题

运输问题是线性规划问题，由于其约束条件的特殊性，产生了特殊的解法。4.1运输问题的典型数学模型例：某公司从两个产地A1、A2、A3将物品运往三个销地B1,B2,B3，B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最少？B1B2B3B4产量A165344A244756A376583销量243413解：产销平衡问题：总产量=总销量＝13设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：B1B2B3B4产量A165344A244756A376583销量243413B1B2B3B4产量A1x11x12x13x144A2x21x22x23x246A3x31x32x33x343销量243413minz=6x11+5x12+3x13+4x14+4x21+4x22+7x23+5x24+7x31+6x32+5x33+8x34x11+x12+x13+x14=4x21+x22+x23+x24=6x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=4x13+x23+x33=3x14+x24+x34=4xij≥0,i=1,2,3;j=1,2,3,4运输问题的提出A1、A2、…、Am

表示某物资的m个产地；B1、B2、…、Bn

表示某物资的n个销地；ai

表示产地Ai的产量；

bj

表示销地Bj

的销量；cij

表示把物资从产地Ai运往销地Bj的单位运价。设

xij

为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：当发点的发量总和为

ai，收点的收量总和为

bj相等时，称此运输问题为平衡运输问题（产销平衡问题）。否则称此运输问题为非平衡运输问题。

产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。运输问题的图表形式运输问题解的结构：

由于

ai=

bj成立

m+n个约束方程并不是独立的。实际上只有m+n-1个是独立的。即约束方程系数矩阵的秩为m+n-1。4.2表上作业法表上作业法其实质是单纯形法，是一种求解运输问题的特殊方法。（1）找出初始基可行解。即在()产销平衡表上用最小元素法或元素差值法给出个数字，称为数字格。它们就是初始基变量的取值。（2）求各非基变量的检验数。用闭回路法和位势法。若表上空格的检验数符合要求，则为最优解；否则转到下一步。（3）确定换入变量和换出变量，找出新的基本可行解，在表上用闭回路法调整。重复（2），（3）直到得到最优解为止。1.最小元素法4.2.1确定初始基本可行解

发点收点B1B2B3B4发量A165344A244756A376583收量243413（1）从最小元素开始“3”即A1优先满足B33个单位，B3已经满足，划去B3列。发点收点B1B2B3B4发量A165344A244756A376583收量2434133（2）再从最小元素开始“4”即A1优先满足B41个单位，A1已经满足，划去A1行。发点收点B1B2B3B4发量A165344A244756A376583收量24341331（3）再从最小元素开始“4”即A2优先满足B12个单位，B1已经满足，划去B1列。

发点收点B1B2B3B4发量A165344A244756A376583收量243413312（4）再从最小元素开始“4”即A2优先满足B24个单位，B2A2已经满足，划去B2列A2

行。发点收点B1B2B3B4发量A165344A244756A376583收量2434133124表格中要有(m+n-1)个数字格，但有时在分配运量时则需要同时划去一行和一列，这时需要补一个“0”（4）最后把A3满足B43个单位，得到初始方案。发点收点B1B2B3B4发量A165344A244756A376583收量24341331243（5）得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3总运费=3*3+4*1+4*2+4*4+6*0+8*3=61（元）发点收点B1B2B3B4发量A165344A244756A376583收量243413312432.差值法（沃格尔法）

每次从当前运价表上，计算各行各列中两个运价(次最小和最小运价)之差值（行差值hi，列差值kj），优先取最大差值的行或列中对应最小运价的格来确定运输关系，直到求出初始方案。收点发点B1B2B3B4发量行罚数A1653441A2447560A3765831收量243413

列罚数2121

2收点发点B1B2B3B4发量行罚数A16534411A24475601A37658311收量243413

列罚数2112211

23收点发点B1B2B3B4发量行罚数A165344111A244756011A376583112收量243413

列罚数211122111

233收点发点B1B2B3B4发量行罚数A1653441111A2447560111A376583112收量243413

列罚数21111221111

2331收点发点B1B2B3B4发量行罚数A16534411110A24475601110A376583112收量243413

列罚数211112211111

23311收点发点B1B2B3B4发量行罚数A16534411110A24475601110A376583112收量243413

列罚数211112211111

233113差值法初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，总费用=3*3+4*1+4*2+4*1+5*3+6*3=58（元）收点发点B1B2B3B4发量A165344A244756A376583收量243413233113最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3，总运费=3*3+4*1+4*2+4*4+8*3=61（元）差值法初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，总运费=3*3+4*1+4*2+4*1+5*3+6*3=58（元）1.运输规划问题的数学模型2.求运输规划问题初始基本可行解，用最小元素法或者元素差额法。小结求最优方案闭回路在初始调运方案表中，从任意空格出发，沿着纵向或横向行进，遇到适当填有数据的方格90度转弯或者继续前进，总能回到原来空格。这个封闭的曲线称为闭回路。可以证明：每个空格对应着唯一的闭回路。如下表：求检验数

判断一个调运方案是否已是最优，就要判断方案所对应的基础可行解是否最优。在单纯形法中，根据非基变量（空格）的检验数来判别的。若检验数中没有正值，则已求得最优。如何根据初始调运表求得检验数？（1）闭回路法

空格Xij的检验数=（第奇数次拐角点运价之和减去第偶数次拐角点运价之和）注意：奇、偶次拐角点的概念是相对的，不同教材上可能会不同。空格X21的检验数=6-5+4-4=1空格X14的检验数=5-4+5-4=2空格X31的检验数=6-5+4-5+8-7=1检验数都为正值，原方案不是最优解调整方案

从一个方案调整到最优方案的过程，就是单纯形法的过程。选择检验数（一般取最大）为正值的空格所对应的变量为进基变量，在进基变量的回路中，比较奇数拐角点的运量，选择一个具有最小运量的基变量作为出基变量；调整运量=min(奇数拐角点的运量)选择（A1，B3）（检验数最大）调整，最小运量=min(2,3)=2最小运量=min(2,3)=2,奇数点减去2，偶数点加上2，得到新的方案。总运费=6*2+3*2+4*4+7*1+5*1+8*3=70（元）原方案运费为80（元）继续求检验数。继续调整运量。继续调整运量。最小运量=1总运费=6*1+3*3+4*1+4*4+5*1+8*3=64（元）继续计算检验数。继续调整运量。最小运量=1得到新的调运方案，总运费=3*3+4*1+4*2+4*4+8*3=61（元）继续计算检验数总运费=4*4+4*2+4*4+5*3=55（元）计算检验数：空格的检验数全为非正，此时是最优解。最优调运方案：X21=2，X22=4，X14=4，X33=3。最小运费55（元）。minz=6x11+5x12+3x13+4x14+4x21+4x22+7x23+5x24+7x31+6x32+5x33+8x34x11+x12+x13+x14=4x21+x22+x23+x24=6x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=4x13+x23+x33=3x14+x24+x34=4xij≥0,i=1,2,3;j=1,2,3,4设u1、u2、u3、v1、v2、v3、v4分别表示对偶变量2.对偶变量法（位势法）u1u2u3v1v2v3v44.2.2最优解的判别对偶问题∵基变量检验数σij=0∴cij=ui+vj检验数：σij

=cij

–CBB-1Pij=cij–y*Pij=cij–(u1…

um,v1…vn)Pij=cij–(ui+vj)st

ui

+vj

≤cij

i=1,…,3j=1,…,4

ui

,vj无约束∴非基变量检验数σij

=cij–(ui+vj)……..(1)………(2)u1=0u2=2u3=4v1=2v2=2v3=3v4=4令c13=u1+v3=3c14=u1+v4=4c21=u2+v1=4c22=u2+v2=4c32=u3+v2=6c34=u3+v4=8公式cij=ui+vj非基变量检验数σij

=cij

–(ui

+vj)σ11=

c11

-(u1+v1)=6-(0+2)=4σ12=c12

-(u1+v2)=5-(0+2)=3σ23=c23

-(u2+v3)=7-(2+3)=2σ24=c24-(u2+v4)=5-(2+4)=-1σ31=c31

-(u3+v1)=7-(4+2)=1σ33=c33

-(u3+v3)=5-(4+3)=-2收点发点B1B2B3B4发量A165344A244756A376583收量243413204313

u1=0

u2=2

u3=4V1=2(4)(3)(2)(-1)(1)(-2)V2=2V3=3V4=4收点发点B1B2B3B4发量A165344A244756A376583收量243413空格的检验数204313(4)(3)(2)(-1)(1)(-2)存在检验数<0，上述调运方案不是最优选择空格检验数负数且最小(A3B3)调整，奇数顶点的运量中取最小运量=min(3,3)=3收点发点B1B2B3B4发量A165344A244756A376583收量243413204313(4)(3)(2)(-1)(1)(-2)3040新的调运方案收点发点B1B2B3B4发量A165344A244756A376583收量2434132043041、给出运输问题的初始基可行解（初始调运方案）

1）最小元素法3146332)沃格尔法列罚数行罚数25130116213012321212017635200126

314331σ11=

c11-c13+c23-c21=3-3+2-1=12、解的最优性检验

1)闭回路法126

3

3413σ12=

c12-c14+c34-c34=11-10+5-4=26

33413121σ22=

c22-c23+c13-c14+c34-c34=9-2+3–10+5-4=16

3

3413121-1σ24=

c24-c23+c13-c14=8-2+3-10=-163

3413121-110σ31=

c31-c21+c23-c13+c14-c34=7-1+2–3+10-5=10633413121-11012σ33=

c33-c13+c14-c34=10-3+10-5=12121-11012因为σ24=-1<0，所以可行解不是最优解所以要重新调整，寻找另一可行解minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24

+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0,i=1,2,3;j=1,2,3,4设u1、u2、u3、v1、v2、v3、v4分别表示对偶变量2)对偶变量法（位势法）u1u2u3v1v2v3v4对偶变量法（位势法）63

34130310-1-529121-11012vj

ui基变量：cij=ui+vj非基变量：σij=cij–(ui+vj)3、解的改进（闭回路法）

334136+Δ-Δ+Δ-ΔΔ=1413x24521x231

52-14、再进行检验3351261912022因为σij

≥0，所以此运输方案是最优方案，而σ11=0说明还有另一最优解3.2产销不平衡运输问题

1.一般产销不平衡运输问题1)总产量>总销量假想一销地Bn+1，令销量为

,运价c=0总产量>总销量

AAA销量

B11B2

B33

3

12

3

11

11

2

5

22

6

7

1

33

43

5

B4

4

9

5

6

产量

8

5

9

B5

0

0

0

4

43542222)总产量<总销量假想一产地Am+1，令产量为，运价c=02.带弹性需求的产销不平衡运输问题

需求地化肥厂B1B2B3B4产量A11613221750A21413191560A3192023—50最低需求最高需求3050707003010不限

B1B1′B2B3B4B4′产量A116161322171750A214141319151560A319192023MM50A4M0M0M050需求量30207030105021050200302030103020（海南大学2021年研究生）1、甲、乙、丙三个地区每年分别需要农用化肥320、250、350万吨，由A、B两个化肥厂负责供应。已知化肥年供应量为A厂400万吨，B厂450万吨，由化肥厂到各地区的单位运价（万元/万吨）见下表。（18分）

甲乙丙A151822B212516需求大于产量，经协商平衡，甲地区供应量可减少0至30万吨，乙地区需求量应全部满足，丙地区供应量不少于270万吨。试求将供应量分配完又使总运费最低的调运方案。（只需要列出线性规划模型，不要求计算）4.3.3两种特殊的情况(1)某供应地不能供应某销地例：有一批物资在三个供应点，供应给四个需求点，运价如表所示，第三供应点不能向第四需求点运送该物资，求总运费最少调运方案。对策：在对应的运价表格中，运价做+∞处理（一般用M表示）。(2)某供应地至少供应某销地量A例：有一批物资在三个供应点，供应给四个需求点，运价如表所示，第A3供应点必须调拨20单位物资给需求点B2，求总运费最少的调运方案。B1B2B3B4产量A1A2A3161419131320221923171516506050销售量30705010对策：在对应供应地和需求地，同时减去A。B1B2B3B4产量A1A2A3161419131320221923171516506030(50-20)销售量3050(70-20)5010表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负（对偶变量法），在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取σij<0中最小者对应的变量为换入变量。（2）多个最优解

产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有多个最优解。4、再进行检验335126(0)(2)(2)(1)(9)(12)因为σij≥0，得到最优方案：X13=5，X14=2，X21=3，X24=1，X32=6，X34=3总运费=3*5+10*2+1*3+8*1+4*6+5*3=85(元)4、再进行检验335126(0)(2)(2)(1)(9)(12)2031得到另一最优方案：X11=2，X13=5，X21=1，X24=3，X32=6，X34=3总运费=3*2+5*3+1*1+8*3+4*6+5*3=85（元）另外最优解4、再进行检验335126(0)(2)(2)(1)(9)(