文档介绍：物流运输问题
一、设计目的
熟悉物流规划中的运输问题。
求解最优方案,即如何组织调运才能使总运费最省。
二、设计内容
根据题给条件和要求,采用最小元素法确定最佳调运方案。
采用位势法求解检验数。
采用闭回路法调整运输方案。
三、例题
(一)已知条件
设有一伐木场,林木采伐后,运往两个木材加工厂A1,A2进行加工,然后运往三个木材交易中心B1、B2及B3。加工厂的供应量A1是140单位,A2是170单位。另一方面,交易中心的需求量B1为100单位,B2为80单位,B3为130单位。从各加工工厂到各交易中心每单位木材的运费如表1所示。此时,从各加工厂分别向交易中心运送多少单位的木材,可使总运费最小。
表1 费用矩阵(Cij)(单位:元)
B1
B2
B3
供应量
A1
4
5
7
140
A2
6
8
9
170
需求量
100
80
130
310
(二)问题的简化
对上述问题,记A1的供应量为a1,A2的供应量为a2,B1、B2、B3的需求量分别为b1b2b3,Ai到Bj到的运送量为Xij,对应的单位运费为:Cij,则问题可化解为以下形式:
目标函数(总运费) ………………①
约束条件有:(1),(2),(3)
(1)关于供应量
(i=1,2)
(2)关于需求量(j=1,2,3)
(3) (运量不可为负)
(三)求解方法
对上述线性规划问题,可以用比较简单的最小元素法(最小元素法的基本思想就是使运输的单位运价最小的优先供应),首先求出一个初始方案,其次依据判别准则判别初始方案是否为最优,若不是最优解,则对方案进行调整改进,反复循环直至求得问题的最优解。
(1)具体做法是,从表一中最小元素那一空格开始,先确定该空格上的基变量Xij的数值,同时也确定了它们在那一行(或那一列)的其余量为零,也就是使表中减少了一行或一列空格。依此类推,每次总在表的其余空格中选最小元素的空格作为基变量,并为该Xij确定数值。
(2)具体过程如下:从所有Cij找到最小的那个元素,若有几个同时取最小值,则可以从中任选一个。在表1中,Cmin =C11,首先确定X11=min(a1 b1)= b1=100,并且X21=0,;在剩余的Cij中,Cmin =C12,再确定X12,依次可确定其他的Xij,结果
见表2
表2初始调运方案
B1
B2
B3
供应量
A1
100
40
140
A2
40
130
170
需求量
100
80
130
310
(3)总运费计算如下:把表1和表2中的数值代入目标总函数①得
表2中的初始方案是线性规划的一个基础可行解。但是,这样得到的初始方案是否为最优解呢?还需进行检验。
最小元素法求得初始解后,就要用检验数去判别该初始解是否为最优解。当一个方案存在负检验数时,表明该方案非最优。在此我们用位势法求解检验数,具体步骤:
(1)作一个(2+1)×(3+1)的表,第(2+1)=3行为Vj 行,第(3+1)=4列为Ui列,见表2在中间m×n(及2×3)个空格中,在每一个空格的右上角写出Cij的值。为了区别起见,对非基变量的Cij,我们画圈表示
见表3
表3 Ui 及Vj表
B1
B2
B3
Ui
A1
4
5
⑦
A2
⑥
8
9
Vj
(2)然后令V3= 0,即在空格(3,3)处填上0。我们将基变量Xij所对应的(i,j)称为基格,则有表2知,表三中(1,1),(1,2),(2,2)(2,3)为基格。对应于基格公式
Cij=Ui+Vj …………………………………………②
现在V3=0用到基格(2,3)上,有
C23=U2+V3=U2+0
因此有 U2=C23=9
从而可以再空格(2,4)上填9。而C22=U2+V2,因此V2=C22-U2=8-9=-1,在空格(3,2)处填上-1(V2的值)。同理依次可以求出空格(3,2)处的V1=-2和空格(1,4)处的U1=6至此Ui,Vj的值全部求出。见表4,计算的顺序是,在两个未知量Ui,Vj中有一个已求出(或已知,如令V3=0)
表4 计算Ui及Vj表
B1
B2
B3
Ui
A1
4
5
⑦
6
A2
⑥
8
9
9
Vj
-2
-1
0
在求出Ui,Vj后利用公式
λi j = ci j –(ui + vj) …………………………………………③
因此对非基变量格完成计算工作:
λ13=C13-(U1+V3)=7-(6+0)=1
λ21=C21-(U2+V1)=6-(9-2)=-1
由于存在λij小于零,此方