《运筹学课件ch3运输问题》课件.ppt

* 运筹学课件 2.检验（闭回路法:计算空格的检验数） ①找出任意空格的闭回路—除此空格外，其余顶点均为有数格。如从a11出发可找 （ A1 B1 ）→ （ A1 B3 ） → （ A2 B3 ） → （ A2 B1 ）； ②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的代数和。 如σ11＝c11-c13+c13-c21=3-3+2-1=1③计算出此空格的检验数σij, 若σij ≥０，则该方案为最优方案，否则转３； 每一个空格的检验数=奇顶点运费之和 – 偶顶点运费之和。 * 运筹学课件 B1 B2 B3 B4 A1 1 2 4 3 A2 3 1 1 -1 A3 10 6 12 3 注：检验数的经济意义，以σ11为例，空格表示原方案中X11=0,即A1 → B1 的运输量为0。若试着运1单位，则这样所引起的总费用的变化恰是σ11，可见检验数σij的意义是： Ai → Bj增运１单位所引起的总费用的增量。 σij＞０，说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在 Ai → Bj上增运。 (+1)*3+ (-1)*3+(+1)*2+(-1)*1=1 空格检验数 3 11 3 10 1 9 2 8 7 4 10 5 * 运筹学课件 B1 B2 B3 B4 A1 1 2 4 3 A2 3 1 1 -1 A3 10 6 12 3 σ24=(+1)*8+(-1)*2+(+1)*3+(-1)*10=-1 表示原方案中X24=0,即A1 → B1 的运输量为0。若试着运1单位，引起的总费用减少. + + - - 3 11 3 10 1 9 2 8 7 4 10 5 * 运筹学课件 从σij 为最小负值的空格出发.对其闭回路上的奇数顶点运量增加θ,偶数顶点的运量减少θ(这才能保证新的平衡)，其中θ为该空格闭回路中偶数顶点的最小值。∵ σ240，∴从（A2 B4） 出发其闭回路上θ=1，调整后得到一个新方案（如下表），运量为θ=1的（A2 B3）变空格，得到新方案后再转 2。 经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。 注：若闭回路的偶数顶点中同时有两个格以上运量为θ，则调整后其中一个变空格，其余填0。（保证基变量个数不变） 3 6 1 3 2 5 3.调整: 1 2 9 2 1 12 * 运筹学课件 4）表上作业法须注意的问题： i) 在最终调运表中，若有某个空格（非基变量）的检验数为0时，则表明该运输问题有多重调运方案； ii) 在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列（绝对不能同时把行、列划去，否则就不满足圈格=m+n－1个的要求，即基变量的个数永远要保持为m+n－1个）； iii) 在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n－1个的需要。 iv) 用最小元素法所得到的初始方案可以不唯一。 * 运筹学课件 （Ⅲ）产销不平衡的运输问题 1.产大于销的情况： 添加松弛变量xin+1 xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地—Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即剩余量就地库存 * 运筹学课件 产大于销的产销量表 A1 Am a1 am B1 …… Bn b1 …… bn Bn+1 A1 Am B1 …… Bn C11 0 0 C1n Cm1 Cmn 产大于销的单位运价表 Bn+1 * 运筹学课件 2.销大于产的情况： 添加松弛变量xm+1j 同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在， cm+1j为0。 * 运筹学课件 销大于产的产销量表 A1 Am a1 am B1 …… Bn b1 …… bn Am+1 A1 Am B1 …… Bn C11 0 0 C1n Cm1 Cmn 销大于产的单位运价表 Am+1 …… * 运筹学课件 B1 B2 B3 B4 ai A1 5 9 2 3 60 A2 -- 4 7 8 40 A3 3 6 4 2 30 A4 4 8 10 11 50 bj 20 60 35 45 180 160 因为有： 【例】求下列表中极小化运输问题的最优解。 所以是一个产大于销的运输问题。 * 运筹学课件 表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一