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