运筹学-7运输问题

1问

题§1§2§3§4*模型问题的计算机求解问题的应用问题的表上作业法2例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总费用最小？B1B2B3产量A1646200A2655300销量150150200解：

产销平衡问题：

总产量

=

总销量设

xij

为从产地Ai运往销地Bj的

量，得到下列

量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200Min f

=

6x11+

4x12+

6x13+

6x21+

5x22+

5x23s.t.

x11+

x12

+

x13

=

200x21

+

x22+

x23=

300x11

+

x21

=150x12

+

x22=

150x13

+

x23=

200xij≥0

(i=1、2；j=1、2、3）§1模型§1

模型一般 模型：产销平衡A1、A2、…、Am

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

表示某物质的

n个销地；si

表示产地Ai的产量；dj

表示销地Bj

的销量；cij

表示把物资从产地

Ai运往销地Bj的单位运价。设

xij

为从产地Ai运往销地Bj的

量，得到下列一般

量问题的模型：m

nMin f

=

ciji

=1

j

=1ns.t.

xij

=

sixiji

=

1,2,…,mj

=

1

m

xij

=

dj

j

=

1,2,…,ni

=

1xij

≥

0 (i

=

1,2,…,m

;

j

=

1,2,…,n)变化：有时目标函数求最大。如求利润最大或营业额最大等；当某些

线

的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；

3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。34§2

问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总

费用最小？解：增加一个虚设的销地费用为0B1B2B3产量A1646300A2655300销量150150200600500B1B2B3B4产量A16460300A26550300销量1501502001006006005§2

问题的计算机求解例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总

费用最小？解：增加一个虚设的产地费用为0B1B2B3产量A1646200A2655300销量250200200500650B1B2B3产量A1646200A2655300A3000150销量250200200650650§3

问题的应用一、产销不平衡的例4、石家庄北方问题有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：山西盂县河北临城需要量山西盂县河北临城假想生产点需要量由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。解：根据题意，作出产销平衡与运价表：这里

M

代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。6§3

问题的应用一、产销不平衡的问题例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：1234产量A1613221750B1413191560C192023---50最低需要量3070010最高需要量507030不限1’1”234’4”产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量302070301050210210试求总费用为最低的化肥调拨方案。解：根据题意，作出产销平衡与运价表：最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0

。对应4”的销量

50

是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。78§3

问题的应用三、转运问题：在原

问题上增加若干转运站。方式有：产地

转运站、转运站

销地、产地

产地、产地

销地、销地

转运站、销地

产地等。例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在

和

有两个销售公

司负责对

、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，可使总3-费用如图，单位是百元。问应该如何调运仪器，费用最低？图中1-广州、2-大连、、4

-

、5

-

、6

-济南、7

-南昌、8

-

青岛9§3问题的应用解：设

xij

为从

i

到

j

的 量，可得到有下列特点的线性规划模型：目标函数：Min f

=

所有可能的 费用（ 单价与 量乘积之和）约束条件：对产地（发点）

i ：输出量

-

输入量

=

产量对转运站（中转点）：输入量

-输出量

=0

对销地（收点）

j

：输入量

-

输出量

=

销量例8．（续）目标函数： Min

f

=

2x13+

3x14+

3x23+

x24+

4x28

+

2x35+

6x36+

3x37+

6x38+4x45+

4x46+

6x47+

5x48约束条件：x13+

x14s.t. ≤

600(广州分厂供应量限制）x23+

x24+

x28≤400 (大连分厂供应量限制）+

x35

+

x36+

x37

+

x38

=

0

（+

x45

+

x46+

x47

+

x48

=

0

（销售公司，转运站）销售公司，转运站）=200

（ 的销量）=150（济南的销量）=350（南昌的销量）-x13-

x23-x14-

x24x35+

x45x36+

x46x37+

x47x38+

x48xij+x28

=300

（青岛的销量）≥

0 ,i,j

=

1,2,3,4,5,6,7,810§3用“管理运筹学”=550=

0=200=

0x14x24x36x46问题的应用求得结果：=50

；=

100

x28

=

300

；=

0=

150x37x47=

350=

0x38x48=0；=0。x13

x23

x35

x45最小费用为：4600百元§3

问题的表上作业法确定初始调运方案:

(初始基本可行解)最小元素法、西北角法检验，判断已确定的方案是否最优位势法方案调整，寻找更好的方案．闭回路调整法A1问题网络图A2=27

A2A3=19

A3B1

B1=22B2

B2=13B3

B3=12B4

B4=13A1=供应量供应地运价需求量需求地9106问题线性规划模型

13

22

14

2734333231232221

24141211

1333231332221234333231xxxxxx0xxxxxx

12+

x34

13+

x24x14+

x+

xx+

x+

xxx31x21x11++x+xxx

19++x+x24x2x32221++x1x4x1x31211s.t.x32

+91+05x+337+26+x434x23

x24

x31x11

x12

x13

x14

x21

x22z

供应地约束需求地约束问题的表格表示B1B2B3B4A114A227A36753x11x12x13x148427x21x22x23x2459106x31x32x33x34192213121315表上作业法确定初始调运方案:

(初始基本可行解)最小元素法、西北角法检验，判断已确定的方案是否最优位势法方案调整，寻找更好的方案．闭回路调整法B1B2B3B4A114A227675384271259106A31922131213初始基础可行解—1.最小元素法(1)B1B2B3B4A114A22767531384271259106A31922131213最小元素法(2)A2A3最小元素法(3)A3最小元素法(4)A2A3最小元素法(5)A3最小元素法(6)A2A313131466运费z=6*14+8*8+4*13+2*6+10*6+6*13=350初始基础可行解—2.西北角法位势法是任意给出一组数ui和vj，称之为位势.有数字的格（数格）满足：ui+vj=cij没数字的格（空格）计算：σij=cij-(ui+vj)检验:

计算非基变量xij的检验数—

位势法B1B2B3B4A1u1A2u2A36753148427813659106613u3v1v2v3v4=0v4=0位势法(1)—位势计算（数格ui+vj＝

cij

）B1

B2

B3

B4A1u1A2u2A36753148427813659106613u3=6v1v2v3v4=0u3+v4=c34u3=6位势法(2)—位势计算（ui+vj＝

cij

）B1B2B3B4A1u1A2u2A36753148427813659106613u3=6v1v2v3=4v4=0u3+v3=c33v3=4位势法(3)—位势计算（ui+vj＝

cij

）B1B2B3B4A1u1A2u2=-2A36753148427813659106613u3=6v1v2v3=4v4=0u2+v3=c23u2=-2位势法(4)—位势计算（ui+vj＝

cij

）B1B2B3B4A1u1A2u2=-2A36753148427813659106613u3=6v1v2=6v3=4v4=0u2+v2=c22v2=6位势法(5)—位势计算（ui+vj＝

cij

）B1B2B3B4A1u1A2u2=-2A36753148427813659106613u3=6v2=6v3=4v4=0u2+v1=c21v1=10v1=10位势法(6)—位势计算（ui+vj＝

cij

）B1B2B3B4A1u1=-4A2u2=-2A36753148427813659106613u3=6v2=6v3=4v4=0u1+v1=c11v1=10u1=-4位势法(7)—位势计算（ui+vj＝

cij

）B1B2B3B4A1u1=-4A2u2=-2A3u3=6v4=0v1=10

v2=6

v3=4检验数σ12

=c12

–(u1+v2)=7-((-4)+6)=567531458427813659106613位势法(8)—位势计算（ui+vj＝

cij

）B1B2B3B4A1u1=-4A2u2=-2A3u3=6v4=0v1=10

v2=6

v3=4检验数σ13

=c13

–(u1+v3)=5-((-4)+4)=5675314558427813659106613位势法(9)—检验数计算：σij=cij-(ui+vj)B1B2B3B4A1u1=-4A2u2=-2A3u3=6v4=0v1=10

v2=6

v3=4检验数σ14

=c14

–(u1+v4)=3-((-4)+0)=76753145578427813659106613位势法(10)—检验数计算：σij=cij-(ui+vj)B1B2B3B46753A114u1=-48427A28136u2=-259106A3u3=6v1=10

v2=66v3=413v4=0检验数σ24

=c24

–(u2+v4)=7-((-2)+0)=99557位势法(11)—检验数计算：σij=cij-(ui+vj)B1

B2

B3

B46753A114u1=-48427A28136u2=-259106A3u3=6v1=10

v2=66v3=413v4=0检验数σ31

=c31

–(u3+v1)=5-(6+10)=-11-115579位势法(12)—检验数计算：σij=cij-(ui+vj)B1

B2

B3

B46753A114u1=-48427A2813659106A3u3=6v1=10

v2=66v3=413v4=0检验数σ32

=c32

–(u3+v2)=9-(6+6)=-3-35579

u2=-2-11位势法(13)—检验数计算：σij=cij-(ui+vj)若表中空格处出现负检验数(ij

<

0）,表明未得到最优调运方案，在ij

<

0

处，增加

量，可节约运费若有两个或两个以上的负检验数时，取最小的ij对应的空格为调入格变量（xij为进基变量）。以所选的空格(xij)为顶点作闭回路，该闭回路除xij外，其余顶点都是数格（基变量），并排序。以顺序为偶数的顶点的基变量最小值作为调整量，在顺序为奇数的顶点上加上该调整量，在顺序为偶数的顶点上减去该调整量，即可得到新的调运方案（基本可行解）。方案调整—闭回路法B1B2B3B46753A114u1=-48427A28136u2=-259106A36u3=613v4=0v1=10

v2=6

v3=4x31进基,min{x21,x33}=min{8,6}=6,

x33离基-35579-