09级运筹学4章

- - 60 第四章 运输问题(Transportution Problem) 4.1运输问题的数学模型 属于特殊类型的LP问题。 例1 某森工局所属有三个储木厂和四个加工厂。按以往的资料表明三个储木厂每天能供木材立方数为(A1)7千M3, (A2)4千M3,(A3)9千M3,而四个加工厂每天所需的原料为(B1)3千M3, (B2)6千M3,(B3)5千M3,(B4)6千M3。三个储木厂往四个加工厂的运价见表4-1.问该森工局应如何组织使总运费最少,且又能满足生产需求？ 表4.1 加工厂 储木厂 B1 B2 B3 B4 产量ai

A1 3 11 3 10 7 M3 A2 1 9 2 8 4 M3 A3 7 4 10 5 9 M3 销量bj 3 M3 6 M3 5 M3 6 M3 Min 运费 解: 设Xij表示由第i个储木厂运往第j个加工厂的调运量，据题意有： Min Z=3X11+11X12+3X13+10X14+X21+9X22+2X23+8X24+7X31+4X32+10X33+5X34

st. X11+X12+X13+X14 =7 （=a1）

X21+X22+X23+X24 =4 （=a2）

X31+X32+X33+X34 =9 （=a3）

X11+X21+X31 =3 （=b1） X12+X22+X32 =6 （=b2） X1=+X23+X33=5 （=b3） X14+X24+X34=6 （=b4）

Xij≥0 i=1„3,j=1„4 本例有12个决策变量、7个约束,需有7个人工变量,按我们已学的方法，用大M法或两阶段法求解共计有19个变量。（方便吗？？） 全国,某大地区,中小的区均有此类特征的物资调运问题.设某种物资有m个产地,产量分别为ai(i=1…m),运往n个销地,销量分别为bj(j=1…n),这m个产地Ai(i=1…m),运往n个销地Bj(j=1...n)的运价分别为Cij(i=1…m, j=1…n),问如何调运使总运费最小？ 设Xij表示由第i个产地运往第j个销地的掉运量，据题意有：

Min Z=minjijijXC11

st. njijX1=ai i=1…m - - 61

miijX1=bj j=1…n Xij≥0 i=1…m ,j=1…n 变量有m*n个,有m+n个等式,需有m+n个人工变量,计有m*n+m+n个变量,若m=5,n=6则有41个变量,可见计算工作量之大,显而易见这是个LP问题,但可找出他有普通LP问题所不具备的特点,故有新的方法解此类问题。 将A矩阵展开可见（有m*n列,有m+n行）：

A=xxxxxxxxxmnmmnn212222111211100001000100000100001000100001000010001111000000000000001110000000000000111 特点1: A的组成元素仅为0,1； 特点2: A中每列有两个为1的元素,其他为0,且这两个为1的元素的位置可表达为:对应于Xij的Pij列而言，第i行和第m+j行的元素为1,其它元素为0。 4.2 运输问题的表上作业法 LP问题有表格单纯形法；运输问题也有表上作业法,步骤是: 1） 确定初始调运方案 2） 检验最优性 3） 调整 4） 重复2）、3）两步至最优解 制表过程:1）画表；2）添运价；3）作初始调运方案(初始基本可行解),这里的方法有最小元素法,西北角法,元素差额法等。 4.2.1 初始方案的给定 1）最小元素法 基本思路是“就近供应”。基变量位置填入数字（表示运量）,非基变量打X（表示运量为0）。每填一字,总可以划掉一行或一列(因为总可以满足一方),直到调运完成。 2）元素差额法(Vogel近似法 或称为 VAM 法) 最小元素法:为局部而忽略全局,元素差额法可避免这一缺点。 (1) 从每一行与每一列中都计算出两个最小元素之差 (2) 在差值最大的行或列中选出运费最小的首先满足 (3) 重新行列的计算差值

系 数 费

用 销 量 - - 62

(4) 重复(2)(3)直至完成初始调运方案 例1 解：1）用最小元素法取得初始调运方案后见下表（表中数字：右上角为Cij，居中为Xij，╳为非基变量）： 表4.2 销地 产地 B1 B2 B3 B4 产量ai

A1 3 ╳ 11 ╳ 3 4 10 3 7

A2 1 3 9 ╳ 2 1 8 ╳ 4 A3 7 ╳ 4 6 10 ╳ 5 3 9 销量bj 3 6 5 6 Min=86 2）用元素差额法取得初始调运方案后见下表（表中数字：右上角为Cij，居中为Xij，╳为非基变量，①②„„⑤为填入时的顺序）： 表4.3 销地 产地 B1 B2 B3 B4 产量ai 行 差额

A1 3 ╳ 11 ╳ 3 5 10 2 7 3-3=0 10-3=7④

A2 1 3 9 ╳ 2 ╳ 8 1 4 2-1=1 8-2=6

A3 7 ╳ 4 6 10 ╳ 5 3 9 5-4=1 7-5=2

销量bj 3 6 5 6 Min Z=85 列差额 3-1=2③ 9-4=5① 3-2=1 8-5=3② 10-8=2⑤ 初始方案中的特点: (1)有数字的格为m+n-1个,打╳的格为m*n-(m+n-1)个,即基变量个数为m+n-1个.因为在约束条件中前m行之和等于后n行之和,故A的m+n行是线性相关的, 可以证明A的秩Rh(A)=m+n-1,也就是说基变量的个数为m+n-1,为保证这点,在每填一数字时要划去一行或一- - 63

列（用╳填入没数字的行或列即可）,这m+n行的划去便要填入m+n个数据,但在填最后一数字时将同时满足一行和一列,故可保证填入的数最多有m+n-1个,在不是填最后一数字而发现同时满足一行与一列时要在这数所在的行或列上补上一个0后再划去这一行或一列以保证填入数字的个数为m+n-1(实为退化解之情形)。 (2)不存在完全以数字格为顶点的闭回路. 定义1 凡是能组成Xi1,j1 Xi2,j1 Xi2,j2 Xi3,j2 . -->. Xis,js Xi1,js (i1,i2, ... is, j1,j2, ... js互不相同)形势的变量的集合成为一个闭回路,上述变量为顶点,变量间(两点间)为边。 通俗点讲，从某点开始出发前进到某点90度转弯-->再前进-->90度转弯……-->重复前进与90度弯直到回到出发点为止,组成一个闭回路。 4.2.2 最优性判别及调整方法 初始方案最优否?, 看检验结果(如单纯形法中的δj),至少由前面两种方法得到的调运方案最小元素法较元素差额法要差(此点由目标函数值的86与85可见)。故需要进行最优性检验。通常有两种方法：闭回路法、位势法。 1)闭回路法 以最小元素法取得的初始方案为例，检验数δj,大家知道：基变量检验数δB=0,非基变量检验数δN≥0(在目标函数求Min时)为最优解。检验数的取得,以打╳格为起点,以数字格为顶点寻找"打╳格（非基变量）"的闭回路(即在整个闭回路中除打╳格这一起点外，其它的顶点全为数字格)。可以证明，每个打╳格总可以、而且仅可以找到一条这样的闭回路。 δj=奇次拐点运价总和-偶次拐点运价总和 规定:打╳格为奇次拐点， 故在表4.2中的检验数为 δ11=C11+C23-C21-C13=(3+2)-1-3=1 δ12=C12-C32+C34-C14=11-4+5-10=2 同理δ22=9-4+5-10+3-2=1 δ24=-1 δ31=10 δ33=12 将检验数δij填入表4.2中打╳格的左下角后得表4.4。∵表4.4中δij中的δ24=-1<0,故该方案不为最优方案。

2）调整（换基迭代） 可通过非基变量X24的闭回路作一调整(换基迭代),方法是在这一闭回路上选取Min{偶次拐点运量Xij}填入打╳格中同时将被选取最小运量的这格上打╳（换基）,这一闭回路上的其它拐点处理方式如下：奇次拐点运量+该量同时偶次拐点运量-该量（迭代）,闭回路以外的其它格的运量保持不变。将表4.4作调整后得到表4.5,再对表4.5进行检验，得检验数如下： δ11=0 δ12=2 δ22=2 δ23=1 δ31=9 δ33=12 δij ≧ 0 故表4.5 为一最优方案。 表4.4 - - 64

销地 产地 B1 B2 B3 B4 产量ai

A1 3 ╳ 1 11 ╳ 2 3 4 10 3 7

A2 1 3 9 ╳ 1 2 1 8 ╳ -1 4 A3 7 ╳ 10 4 6 10 ╳ 12 5 3 9 销量bj 3 6 5 6 Min=86 表4.5 销地 产地 B1 B2 B3 B4 产量ai

A1 3 ╳ 0 11 ╳ 2 3 4+1=5 10 3-1=2 7 A2 1 3 9 ╳ 2 2 ╳ 1 8 1 4 A3 7 ╳ 9 4 6 10 ╳ 12 5 3 9 销量bj 3 6 5 6 Min=85 最优解为X11=X12=X22=X23=X31=X33=0 (非基变量Xij=0) X13=5 X14=2 X21=3 X24=1 X32=6 X34=3 Z*=85 因δ11=0 故可得另一个最优方案(即无限多最优解)，按上面调整的方法沿着X11的闭回路进行调整可得表4.6,其检验数分别为(见表4.6打╳格的左下角): δ12=2 δ14=0 δ22=2 δ23=1 δ31=9 δ33=12 ∵δij≥0 故表4.6 为另一最优方案。 最优解为X12=X14=X22=X23=X31=X33=0 (非基变量Xij=0) X11=2 X13=5 X21=1 X24=3 X32=6 X34=3 Z*=85