《运筹学》课件运筹三.ppt
1第三章第三章 运输问题运输问题 顺风而呼，声非加疾也，而闻者彰。顺风而呼，声非加疾也，而闻者彰。假舆马者，非利足也，而致千里；假舟假舆马者，非利足也，而致千里；假舟楫者，非能水也，而绝江河。君子生非楫者，非能水也，而绝江河。君子生非异也，善假于物也。异也，善假于物也。荀子荀子劝学劝学23.1 运输问题的一般数学模型运输问题的一般数学模型 有有m个产地生产某种物资，有个产地生产某种物资，有n个地区需要该类物资个地区需要该类物资 令令a1,a2,am表示各产地产量，表示各产地产量，b1,b2,bn表示各销表示各销地的销量，地的销量，ai=bj 称为产销平衡称为产销平衡 设设xij表示产地表示产地 i 运往销地运往销地 j 的物资量，的物资量，wij表示对应的单表示对应的单位运费，则我们有运输问题的数学模型如下：位运费，则我们有运输问题的数学模型如下：0 ,2,1 ,2,1)(min1111ijjmiijnjiijminjijijxnjbxmiaxxwxf销量约束产地约束运输问题有运输问题有m n个个决策变量，决策变量，m+n 个个约束条件。由于产约束条件。由于产销平衡条件，只有销平衡条件，只有m+n1个相互独立，个相互独立，因此，运输问题的因此，运输问题的基变量只有基变量只有m+n1 个个33.2 运输问题的求解方法运输问题的求解方法 约束条件非常有规律，技术系数非约束条件非常有规律，技术系数非 0 即即 1 基变量的个数远小于决策变量的个数基变量的个数远小于决策变量的个数 采用表上作业法，称为位势法和踏石法采用表上作业法，称为位势法和踏石法 运算中涉及两个表：运费表和产销平衡表运算中涉及两个表：运费表和产销平衡表(分配表分配表)销地销地产量产量运量运量12nai产地产地1x11x12x1na12x21x22x2na2 mxm1xm2xmnam销量销量 bjb1b2bn销地销地运费运费12n产地产地1w11w12w1n2w21w22w2n mwm1wm2wmn45 3.2.1 寻找初始可行解的方法寻找初始可行解的方法 1、西北角法、西北角法 从从 x11开始分配，从西北向东南方向逐个分配开始分配，从西北向东南方向逐个分配 xij 的分配公式的分配公式列待分物资量列已分配的总量行尚余物资量行已分配的总量)()(minjjbiiaxjiij例例3.2.1销地销地产量产量运费运费1234ai产地产地120113652591021031874115销量销量 bj3312126销地产量运量1234ai产地15210315销量 bj331212 例例3.2.1 西北角法西北角法销地产量运量1234ai产地13x125210315销量 bj331212销地产量运量1234ai产地13252x2210315销量 bj331212销地产量运量1234ai产地132521x2310315销量 bj331212销地产量运量1234ai产地1325219103x3315销量 bj331212销地产量运量1234ai产地13252191033x3315销量 bj331212销地产量运量1234ai产地132521910331215销量 bj3312123141205)(67ijijijxwxfnm个基变量有7 2、最低费用法、最低费用法采用最小费用优先分配的原则，看一步采用最小费用优先分配的原则，看一步编号编号运费表运费表wij分配表分配表xij2011(3)6x135I5910210187411215331212编号编号运费表运费表wij分配表分配表xij20113655II5910210187(4)1x331215331212编号编号运费表运费表wij分配表分配表xij20113655III59(10)2334101874131215331212f(x)=121，比，比西北角法低西北角法低848 3、运费差额法、运费差额法采用最大差额费用采用最大差额费用(即利用每行或列中最小费用与次最小之即利用每行或列中最小费用与次最小之间的差额中选最大间的差额中选最大)优先分配的原则，看两步优先分配的原则，看两步编号编号运费表运费表wij分配表分配表xij20113635I5910233101874131513211331212f(x)=98，比，比最低费用法最低费用法又低了又低了23编号编号运费表运费表wij分配表分配表xij20113635II59102737101874131513211331212编号编号运费表运费表wij分配表分配表xij20113635III591027371018741351513415331212编号编号运费表运费表wij分配表分配表xij201136855IV59102737101874133751513-53312129 3.2.2 利用位势法检验分配方案是否最优利用位势法检验分配方案是否最优1、标准单纯形法（目标函数求、标准单纯形法（目标函数求Max)最优检验条件为最优检验条件为cj-zj 0，通过类比法可知，运输问题的检验条件为：，通过类比法可知，运输问题的检验条件为：zij-wij 0；2、由于基变量的检验数为、由于基变量的检验数为0，所以，对于基变量，有，所以，对于基变量，有zij=wij3、一般地，令、一般地，令zij=ui+vj，且令任意一个，且令任意一个ui或或vj等于等于0（因为（因为5=5+0=4+1=3+2=2+3=1+4=0+5)，4、然后利用基变量的检验数满足、然后利用基变量的检验数满足zij=wij及关系及关系zij=ui+vj求得所求得所有的有的ui、vj和和zij5、利用检验条件、利用检验条件 zij-wij 0进行最优检验。进行最优检验。10 3.2.3 踏石法踏石法1、找入变量、找入变量 从从 zij wij 0 中找最大者，对应中找最大者，对应 xij 就是入变量就是入变量2、以、以 xij 为起点，寻找由原基变量构成的为起点，寻找由原基变量构成的闭合回路闭合回路 该回路只在每个拐角各有一个基变量，中间允许穿越某些基该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量变量；因此，闭合回路中必有偶数个变量(包括包括 xij)，且回路，且回路中每行每列只有两个变量中每行每列只有两个变量3、求入变量、求入变量 xij 的最大值及新基变量的解的最大值及新基变量的解 从从 xij出发，沿任一个方向对回路拐角上的基变量依此标出发，沿任一个方向对回路拐角上的基变量依此标“”和和“+”，表示，表示“”和和“+”xij，从而迭代后仍满足分配的从而迭代后仍满足分配的平衡平衡 标有标有“”的变量中最小者就是的变量中最小者就是出变量出变量xij*，对应对应 xij*的值就是的值就是所所求入变量求入变量 xij 的最大值的最大值 标有标有“”的变量减去的变量减去 xij*，标有标有“+”的变量加上的变量加上 xij*4、用位势法求新基变量的检验数、用位势法求新基变量的检验数 若所有若所有 zij wij 0，则达到最优，算法停止；否则返回，则达到最优，算法停止；否则返回 111 例例3.2.1 踏石法，以最低费用法所得初始解开始踏石法，以最低费用法所得初始解开始编号编号 运费表运费表zij/wij ui 分配表分配表xij -2/20 2/11 3 0/6 3 5 5 I 5 9 10 7/2 10 3 3 4 x24 10 -1/18 3/7 4 1 4 3+12 15 vj 5 1 0 3 3 3 12 12 编号编号运费表运费表 zij/wijui分配表分配表xij3/20 7/1130/6 255II595/102033 4+104/188/741 1x3278 15vj5952331212编号编号运费表运费表 zij/wijui分配表分配表xij3/20 6/1130/6 155III58/95/102137104/18741037515vj4741331212答：答：最优解如上分配表，最优解如上分配表，OBJ=98OBJ=121OBJ=101123.3 运输问题迭代中的一些具体问题运输问题迭代中的一些具体问题 3.3.1 闭合回路的画法闭合回路的画法从入变量从入变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用到其它基变量，则返回上一拐角，换一个方向走，采用深探法深探法 闭合回路不一定是矩形闭合回路不一定是矩形 3.3.2 产销不平衡产销不平衡 供过于求，即供过于求，即 ai bj，增加一个虚收点增加一个虚收点Dn+1，bn+1=ai-bj,令令 wi,n+1=0,i=1,2,m 供小于求，即供小于求，即 ai 0 中找最大者，对应中找最大者，对应 xij 就是入变量就是入变量2、以、以 xij 为起点，寻找由原基变量构成的为起点，寻找由原基变量构成的闭合回路闭合回路 该回路只在每个拐角各有一个基变量，中间允许穿越某些基该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量变量；因此，闭合回路中必有偶数个变量(包括包括 xij)，且回路，且回路中每行每列只有两个变量中每行每列只有两个变量3、求入变量、求入变量 xij 的最大值及新基变量的解的最大值及新基变量的解 从从 xij出发，沿任一个方向对回路拐角上的基变量依此标出发，沿任一个方向对回路拐角上的基变量依此标“”和和“+”，表示，表示“”和和“+”xij，从而迭代后仍满足分配的从而迭代后仍满足分配的平衡平衡 标有标有“”的变量中最小者就是的变量中最小者就是出变量出变量xij*，对应对应 xij*的值就是的值就是所所求入变量求入变量 xij 的最大值的最大值 标有标有“”的变量减去的变量减去 xij*，标有标有“+”的变量加上的变量加上 xij*4、用位势法求新基变量的检验数、用位势法求新基变量的检验数 若所有若所有 zij wij 0，则达到最优，算法停止；否则返回，则达到最优，算法停止；否则返回 116 例例3.2.1 踏石法，以最低费用法所得初始解开始踏石法，以最低费用法所得初始解开始编号编号运费表运费表zij/wijui分配表分配表xij-2/20 2/1130/6355I59107/210334 x2410-1/183/74143+12 15vj 5 10 3331212编号编号运费表运费表 zij/wijui分配表分配表xij3/20 7/1130/6 255II595/102033 4+104/188/741 1x3278 15vj5952331212编号编号运费表运费表 zij/wijui分配表分配表xij3/20 6/1130/6 155III58/95/102137104/18741037515vj4741331212答：答：最优解如上分配表，最优解如上分配表，OBJ=98OBJ=121OBJ=101173.3 运输问题迭代中的一些具体问题运输问题迭代中的一些具体问题 3.3.1 闭合回路的画法闭合回路的画法从入变量从入变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用到其它基变量，则返回上一拐角，换一个方向走，采用深探法深探法 闭合回路不一定是矩形闭合回路不一定是矩形 3.3.2 产销不平衡产销不平衡 供过于求，即供过于求，即 ai bj，增加一个虚收点增加一个虚收点Dn+1，bn+1=ai-bj,令令 wi,n+1=0,i=1,2,m 供小于求，即供小于求，即 ai bj，增加一个虚发点增加一个虚发点Wm+1，am+1=bj-ai,令令 wm+1,j=0,j=1,2,n 3.3.3 关于退化问题关于退化问题1、初始解退化。、初始解退化。即所求初始基变量的个数少于即所求初始基变量的个数少于 m+n 1。必须。必须补足基变量的个数，否则不能正常解出补足基变量的个数，否则不能正常解出 m+n个个 ui 和和 vj 所补基变量的值为所补基变量的值为 0，补充的原则：，补充的原则：(1)尽量先选运费小的实变量尽量先选运费小的实变量；(2)补充后不能有某个基变量独占一行一列补充后不能有某个基变量独占一行一列18 3.3.3 关于退化问题关于退化问题2、迭代过程中出现退化、迭代过程中出现退化 闭合回路中标有闭合回路中标有“”的基变量同时有多个达到最小的基变量同时有多个达到最小 变换后，有多个原基变量变为变换后，有多个原基变量变为 0，选运费最大者为，选运费最大者为出变量出变量，其，其余保留在新的基础解中余保留在新的基础解中 退化较严重时，可能会出现多次迭代只有值为退化较严重时，可能会出现多次迭代只有值为 0 的基变量在的基变量在转移。此时，一要耐心，二要正确选择出变量转移。此时，一要耐心，二要正确选择出变量踏石法迭代中需注意的问题：踏石法迭代中需注意的问题：1、错误地将分配表中基变量的解代入到运费表中、错误地将分配表中基变量的解代入到运费表中2、不能正确画闭合回路、不能正确画闭合回路3、初始解退化，未能补足基变量的个数。因此在位势法中、初始解退化，未能补足基变量的个数。因此在位势法中多次令某个多次令某个 ui 或或 vj 为为 0；4、在位势法中只能令一个、在位势法中只能令一个 ui 或或 vj 为为 0；若不能求出全部；若不能求出全部 ui和和 vj，说明基变量未选够数或未选对，说明基变量未选够数或未选对19202122
