《运筹学第3章：运输问题-数学模型及其解法》由会员分享，可在线阅读，更多相关《运筹学第3章：运输问题-数学模型及其解法（13页珍藏版）》请在金锄头文库上搜索。
1、幻灯片 1管理与人文学院 忻展 红1999，4第三章第三章 运输问题运输问题 数学模型及其解法数学模型及其解法顺风而呼，声非加疾也，而闻者彰。假舆马者，非利足也，而致千里；假舟楫者，顺风而呼，声非加疾也，而闻者彰。假舆马者，非利足也，而致千里；假舟楫者， 非能水也，而绝江河。君子生非异也，善假于物也。非能水也，而绝江河。君子生非异也，善假于物也。 荀子荀子劝学劝学 幻灯片 23.1 运输问题的一般数学模型运输问题的一般数学模型 有有m个产地生产某种物资，有个产地生产某种物资，有n个地区需要该类物资个地区需要该类物资 令令a1, a2, , am表示各产地产量，表示各产地产量， b1, b2,
2、, bn表示各销地的销量，表示各销地的销量，ai=bj 称为称为 产销平衡产销平衡 设设xij表示产地表示产地 i 运往销地运往销地 j 的物资量，的物资量，wij表示对应的单位运费，则我们有运输问表示对应的单位运费，则我们有运输问 题的数学模型如下：题的数学模型如下：运输问题有 mn 个决策变量，m+n 个约束条件。由于产销平衡条件，只有 m+n1 个相 互独立，因此，运输问题的基变量只有 m+n1 个 幻灯片 33.2 运输问题的求解方法 约束条件非常有规律，技术系数非 0 即 1 基变量的个数远小于决策变量的个数 采用表上作业法，称为位势法和踏石法 运算中涉及两个表：运费表和产销平衡表(
3、分配表)0, 2 , 1, 2 , 1)(min1111ijjmiijnjiijminjijijxnjbxmiaxxwxf不不不不不不不不LL销销地地 运运费费12L Ln产产地地 1w11w12L Lw1n 2w21w22L Lw2nMMMMMMOOMM mwm1wm2L Lwmn幻灯片 43.2.1 寻找初始可行解的方法 1、西北角法 从 x11 开始分配，从西北向东南方向逐个分配 xij 的分配公式销销地地产产量量 运运量量12L Lnai产产地地 1x11x12L Lx1na1 2x21x22L Lx2na2MMMMMMO OMMMM mxm1xm2L Lxmnam销销量量 bjb1b
4、2L Lbn例 3.2.1销销地地产产量量 运运费费1234ai产产地地 12011365 25910210 31874115 销销量量 bj331212幻灯片 5例 3.2.1 西北角法销地产量 运量1234ai产地 15 210 315 销量 bj331212 不不不不不不不不不不不不不不不不不不不不不不不不不不) () (minjjbiiax ji ij销地产量 运量1234ai产地 1325 2x2210 315 销量 bj331212销地产量 运量1234ai产地 1325 21x2310 315 销量 bj331212销地产量 运量1234ai产地 1325 21910 3x331
5、5 销量 bj331212销地产量 运量1234ai产地 1325 21910 33x3315 销量 bj331212销地产量 运量1234ai产地 1325 21910 331215 销量 bj331212 3141205)(67 ijijijxwxfnm不不不不不幻灯片 62、最低费用法 采用最小费用优先分配的原则，看一步销地产量 运量1234ai产地 13x125 210 315 销量 bj331212编编号号运运费费表表 wij分分配配表表 xij 20113655 II5910210 187(4)1x331215 331212编编号号运运费费表表 wij分分配配表表 xij 2011
6、3655 III59(10)233410 1874131215 331212f(x)=121，比 西北角法低 84 幻灯片 73、运费差额法 采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分 配的原则，看两步编编号号运运费费表表 wij分分配配表表 xij 2011(3)6x135 I5910210 187411215 331212编编号号运运费费表表 wij分分配配表表 xij 20113635 II5910273710 18741315 13211331212编编号号运运费费表表 wij分分配配表表 xij 20113635 III5910273710 1874
7、13515 13415331212f(x)=98，比 最低费用法 又低了 23编编号号运运费费表表 wij分分配配表表 xij 201136855 IV5910273710 18741337515 13-5331212幻灯片 83.2.2 利用位势法检验分配方案是否最优 不采用单纯型法，如何获得 xij 的检验数 找到原问题的基础可行解，保持互补松弛条件，求出对应对偶问题的解，若该对偶问 题的解非可行，则原问题的解不是最优解；否则，达到最优解编编号号运运费费表表 wij分分配配表表 xij 20113635 I591023310 18741315 13211331212 njmivuwvuvb
8、uavugjiijjinjjjmiii, 2, 1 , 2 , 1,),(max 11LL不不幻灯片 90, 2 , 1 , 2 , 1 )(min1111ijjmiijnjiijminjijijxnjbxmiaxxwxfLL不不v,v,v,u,uwv u wvu wvu wv uwvuwvuvbvbvbuauamax 321212332222221121331122111113322112211幻灯片 10位势法的原理 为满足互补松弛条件，原问题中 xij 被选为基变量，即 xij0，则要求对偶问题中 ui+vj=wij，即该行的松弛变量为 0 共有 m+n1 个基变量 xij ，因此可得
9、m+n1 个等式 ui+vj=wijm+n1 个等式只能解出 m+n1 个 ui 和 vj ，而一共有 m+n 个 ui 和 vj ，但可令 任一个 ui 或 vj =0，从而解出其它 m+n1 个的值；这就是位势法 令 zij= ui + vj ，其相当原问题 xij 的机会费用 若对所有非基变量有 zij wij 0，即 ui + vj wij，表明当前 ui 和 vj 是对偶问题 的可行解，由互补松弛定理可知当前 m+n1 个基变量 xij 是最优解，否则 从 zij wij 0 中找最大者，对应 xij 就是入变量幻灯片 113.2.3 踏石法 1、找入变量 从 zij wij 0 中
10、找最大者，对应 xij 就是入变量2、以 xij 为起点，寻找由原基变量构成的闭合回路 该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回 路中必有偶数个变量(包括 xij )，且回路中每行每列只有两个变量 3、求入变量 xij 的最大值及新基变量的解 从 xij 出发，沿任一个方向对回路拐角上的基变量依此标“”和“+” ，表示 “”和“+” xij ，从而迭代后仍满足分配的平衡 标有“”的变量中最小者就是出变量 xij* ，对应 xij*的值就是所求入变量 xij 的最大值 标有“”的变量减去 xij*，标有“+”的变量加上 xij* 4、用位势法求新基变量的检验数 若所
11、有 zij wij 0，则达到最优，算法停止；否则返回 1 幻灯片 12例 3.2.1 踏石法，以最低费用法所得初始解开始3323132222121121112223222111131211232322222121131312121111vbxx vb xxvbxxuaxxxuaxxxxwxwxwxwxwxwmin OBJ=121编编号号运运费费表表 zij / wijui分分配配表表 xij3 / 20 7 / 1130 / 6 255 II595 / 102033 4+104 / 188 / 741 1x3278 15 vj5952331212OBJ=101编编号号运运费费表表 zij /
12、 wijui分分配配表表 xij3 / 20 6 / 1130 / 6 155 III58 / 95 / 102137104 / 18741037515 vj4741331212答：最优解如上分配表，OBJ=98 幻灯片 133.3 运输问题迭代中的一些具体问题 3.3.1 闭合回路的画法 从入变量 xij 出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变 量，则返回上一拐角，换一个方向走，采用深探法 闭合回路不一定是矩形 3.3.2 产销不平衡 供过于求，即 ai bj ，增加一个虚收点 Dn+1，bn+1= ai - bj , 令 wi,n+1=0, i=1,2,m 供小于求，即
13、 ai bj ，增加一个虚发点 Wm+1，am+1= bj - ai , 令 wm+1,j=0, j=1,2,n 3.3.3 关于退化问题 1、初始解退化。即所求初始基变量的个数少于 m+n1。必须补足基变量的个数， 否则不能正常解出 m+n 个 ui 和 vj 所补基变量的值为 0 ，补充的原则：(1)尽量先选运费小的实变量；(2)补充后不能有 某个基变量独占一行一列 幻灯片 143.3.3 关于退化问题 2、迭代过程中出现退化 闭合回路中标有“”的基变量同时有多个达到最小 变换后，有多个原基变量变为 0，选运费最大者为出变量，其余保留在新的基础 解中 退化较严重时，可能会出现多次迭代只有值为 0 的基变量在转移。此时，一要耐心， 二要正确选择出变量 踏石法迭代中需注意的问题： 1、错误地将分配表中基变量的解代入到运费表中 2、不能正确画闭合回路 3、初始解退化，未能补足基变量的个数。因此在位势法中多次令某个 ui 或 vj 为 0； 4、在位势法中只能令一个 ui 或 vj 为 0；若不能求出全部 ui 和 vj ，说明基变量未 选够数或未选对编编号号运运费费表表 zij / wijui分分配配表表 xij-2 / 20 2 / 1130 / 6355 I59107 / 210334 x2410-1 / 18 3 / 74143+12 15 vj 5 10 3331212
