CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第三章运输问题 数学模型及其解法 顺风而呼,声非加疾也,而闻者彰。 假舆马者,非利足也,而致干里;假舟 楫者,非能水也,而绝江河。君子生非 异也,善假于物也。 荀子《劝学》
第三章 运输问题 — 数学模型及其解法 顺风而呼，声非加疾也，而闻者彰。 假舆马者，非利足也，而致千里；假舟 楫者，非能水也，而绝江河。君子生非 异也，善假于物也。 荀子《劝学》 ©管理与人文学院 忻展红 1999，4
3运输问题的一般数学模型 有m个产地生产某种物资,有n个地区需要该类物资 令a1,a2,…,an表示各产地产量,b1,b2…,b表示各销 地的销量,Σ∑b称为产销平衡 设x;表示产地i运往销地j的物资量,w/表示对应的单 位运费,则我们有运输问题的数学模型如下: minf(x)=∑∑w 运输问题有mn个 决策变量,m+n个 约束条件。由于产 a1i=1.2,…,m产地约束销平衡条件,只有 m+n-1个相互独立 12…,n销量约束因此,运输问题的 基变量只有m+n1 ≥0 个
2 3.1 运输问题的一般数学模型 • 有m个产地生产某种物资，有n个地区需要该类物资 • 令a1 , a2 , …, am表示各产地产量， b1 , b2 , …, bn表示各销 地的销量，ai=bj 称为产销平衡 • 设xij表示产地 i 运往销地 j 的物资量，wij表示对应的单 位运费，则我们有运输问题的数学模型如下： = = = = = = = = = 0 1,2, , 1,2, , min ( ) 1 1 1 1 i j j m i i j n j i j i m i n j i j i j x x b j n x a i m f x w x 销量约束 产地约束 运输问题有mn个 决策变量，m+n 个 约束条件。由于产 销平衡条件，只有 m+n–1个相互独立， 因此，运输问题的 基变量只有m+n–1 个
32运输问题的求解方法 约束条件非常有规律,技术系数非0即1 基变量的个数远小于决策变量的个数 采用表上作业法,称为位势法和踏石法 运算中涉及两个表:运费表和产销平衡表(分配表) 镅销地 销地 产量 费 2 n运量 n 产地 产地 W1 w12 n in W2122 w2n wml m2 , m1-m2 销量bb1b2
3 3.2 运输问题的求解方法 • 约束条件非常有规律，技术系数非 0 即 1 • 基变量的个数远小于决策变量的个数 • 采用表上作业法，称为位势法和踏石法 • 运算中涉及两个表：运费表和产销平衡表(分配表) 销 地 运 费 1 2 n 产 地 1 w11 w1 2 w1n 2 w2 1 w2 2 w2n m wm1 wm2 wm n
321寻找初始可行解的方法 1、西北角法 从x1开始分配,从西北向东南方向逐个分配 x的分配公式 (a1-行已分配的总量)=i行尚余物资量 x,=m(b-列已分配的总量)=/列待分物资量 例321 销地 产量 费地 12011365 5910210 31874115 销量b33122
4 3.2.1 寻找初始可行解的方法 1、西北角法 – 从 x11开始分配，从西北向东南方向逐个分配 – xij 的分配公式 − = − = = 列已分配的总量 列待分物资量 行已分配的总量 行尚余物资量 ( ) ( ) min b j j a i i x j i i j 例3.2.1 销 地 产 量 运 费 1 2 3 4 ai 产 地 1 2 0 11 3 6 5 2 5 9 1 0 2 1 0 3 1 8 7 4 1 1 5 销 量 bj 3 3 1 2 1 2
例321西北角法 销地 里 量地 234 32 93 10 1215 销量b331212 m+n=7有6个基变量(x)=∑∑nx=205
5 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 5 2 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 例3.2.1 西北角法 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 x1 2 5 2 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 x2 2 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 x2 3 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 9 1 0 3 x3 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 9 1 0 3 3 x3 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 9 1 0 3 3 1 2 1 5 销 量 bj 3 3 1 2 1 2 = = + = = = 3 1 4 1 7 6 ( ) 205 i j i j i j m n 有 个基变量 f x w x
2、最低费用法 采用最小费用优先分配的原则,看一步 编号 运费表{wn} 分配表{x} 2011(3)6 59102 10 18741 1215 331212 「编号运费表{wn} 分配表{x} 201136 5 5 59102 10 187(4) 31215 331212 编号 运费表{wn 分配表{x} 201136 5 5|c)=121,比 Ⅲ159(10)2334 10 西北角法低 18741 31215 84 331212
6 2、最低费用法 • 采用最小费用优先分配的原则，看一步 编 号 运费表{wi j} 分配表{xi j} 2 0 11 (3) 6 x1 3 5 I 5 9 1 0 2 1 0 1 8 7 4 1 1 2 1 5 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 5 5 I I 5 9 1 0 2 1 0 1 8 7 (4) 1 x33 1 2 1 5 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 5 5 III 5 9 (10) 2 3 3 4 1 0 1 8 7 4 1 3 1 2 1 5 3 3 1 2 1 2 f(x)=121，比 西北角法低 84
3、运费差额法 釆用最大差额费用即利用每行或列中最小费用与次最小之L 间的差额中选最大优先分配的原则,看两步 编号 运费表{wn} 分配表{xn} 201136 59102 187 333 505 132 331212 编号 运费表{wn} 分配表{x 2011363 5910273 710 187413 132 331212 编号 运费表{wn} 分配表{x} 201136 59102 373 3 18741 134 331212 fx)=98,比 编号 运费表{w;} 分配表{x} 最低费用法 201136 5又低了23 I 10 3 710 1874 873 37515 13 5 331212
7 3、运费差额法 • 采用最大差额费用(即利用每行或列中最小费用与次最小之 间的差额中选最大)优先分配的原则，看两步 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 3 5 I 5 9 1 0 2 3 3 1 0 1 8 7 4 1 3 1 5 1 3 2 1 1 3 3 1 2 1 2 f(x)=98，比 最低费用法 又低了23 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 3 5 I I 5 9 1 0 2 7 3 7 1 0 1 8 7 4 1 3 1 5 1 3 2 1 1 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 3 5 III 5 9 1 0 2 7 3 7 1 0 1 8 7 4 1 3 5 1 5 1 3 4 1 5 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 8 5 5 I V 5 9 1 0 2 7 3 7 1 0 1 8 7 4 1 3 3 7 5 1 5 1 3 - - 5 3 3 1 2 1 2
3.22利用位势法检验分配方案是否最优 不采用单纯型法,如何获得x:的检验数 找到原问题的基础可行解,保持互补松弛条件,求出 对应对偶问题的解,若该对偶问题的解非可行,则原 问题的解不是最优解;否则,达到最优解 mf(x)=∑∑1 xy max g(nv)=>a4+>b ∑xn=41i=1,2,…,m L.+v:≤ l,v±不限 ∑xn=b;j=1 1,2,…,m2j=1,2,…,n ≥0
8 3.2.2 利用位势法检验分配方案是否最优 • 不采用单纯型法，如何获得xij的检验数 • 找到原问题的基础可行解，保持互补松弛条件，求出 对应对偶问题的解，若该对偶问题的解非可行，则原 问题的解不是最优解；否则，达到最优解 = = = = = = = = = 0 1,2, , 1,2, , min ( ) 1 1 1 1 i j j m i i j n j i j i m i n j i j i j x x b j n x a i m f x w x = = + = + = = i m j n u v u v w g u v a u b v i j i j i j n j j j m i i i 1,2, , , 1, 2, , , max ( , ) 1 1 不限
min Wuru+w12*12+w13-13+w2r-21+W2222+w23-23- x11+2+x13 21+x22+x23=a +x21 13 +X22=b max ayu,+a2u2+bv+b2v2+b3v3 1 12 +1x≤ 13 1 l1,u2,v,v2,3不旅
9 + = + = + = + + = + + = + + + + + 1 3 2 3 3 3 1 2 2 2 2 2 1 1 2 1 1 1 2 1 2 2 2 3 2 2 1 1 1 2 1 3 1 1 1 1 1 1 1 2 1 2 1 3 1 3 2 1 2 1 2 2 2 2 2 3 2 3 x x b v x x b v x x b v x x x a u x x x a u min w x w x w x w x w x w x + + + + + + + + + + u ,u ,v ,v ,v 不 限 u v w u v w u v w u v w u v w u v w max a u a u b v b v b v 1 2 1 2 3 2 3 2 3 2 2 2 2 2 1 2 1 1 3 1 3 1 2 1 2 1 1 1 1 1 1 2 2 1 1 2 2 3 3
位势法的原理 为满足互补松弛条件,原问题中x;被选为基变量,即x1≥0 则要求对偶问题中+y=%,即该行的松弛变量为0 共有m+n-1个基变量x;,因此可得m+n-1个等式ur+v=w m+n-1个等式只能解出m+n-1个u;和v,而一共有m计n个 u;和v;,但可令任一个或v=0,从而解出其它m+n-1个 的值;这就是位势法 令矿l1+,其相当原问题x的机会费用 若对所有非基变量有-wn≤0,即+v≤w7,表明当前m 和v是对偶问题的可行解,由互补松弛定理可知当前 m+n-1个基变量x;是最优解,否则 从动->0中找最大者,对应x;就是入变量
10 位势法的原理 • 为满足互补松弛条件，原问题中xij被选为基变量，即xij0， 则要求对偶问题中ui+vj=wij，即该行的松弛变量为0 • 共有m+n−1个基变量xij ，因此可得m+n−1个等式 ui+vj=wij • m+n−1个等式只能解出 m+n−1个 ui 和 vj ，而一共有m+n个 ui 和 vj ，但可令任一个ui 或 vj =0，从而解出其它 m+n−1个 的值；这就是位势法 • 令 zij= ui + vj ，其相当原问题xij的机会费用 • 若对所有非基变量有 zij − wij 0，即 ui + vj wij，表明当前ui 和 vj 是对偶问题的可行解，由互补松弛定理可知当前 m+n−1个基变量xij 是最优解，否则 • 从 zij − wij > 0 中找最大者，对应 xij 就是入变量