[其它语言学习]ch3运输问题.ppt

运输问题的一般提法是： 2.产销不平衡问题 此时分为两种情形来考虑： 供不应求：即产量小于销量时有 供过于求：即产量大于销量时有 二.运输问题的模型 将约束方程式展开可得 上述模型是一个线性规划问题。但是其结构很特殊，特点如下： 1.变量多（mn个），但结构简单。 技术系数矩阵 三.运输问题的解法 运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是： 1.运输问题所涉及的变量多，造成单纯 形表太大； 2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。 以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。 位势法求检验 小结： 运输问题的常用解法： 最小元素法（确定初始方案）→闭回路法（检验当前方案）→闭回路法（方案调整） 解：1.确定初始方案: (最小元素法基本思想：就近供应，即从单位运价表上最小的运价开始确定产销关系，以此类推，直到给出初始方案为止)①从运价表上找出最小运价C21=1， A2 先保证供应B1 ，X21=3，划去运价表上B1 列；②再从运价表上其余元素中找到最小的运价C23=2，加工厂A2 应供给B3， X23=1，划去A2行；③再从运价表上其余元素中找到最小的运价C13=3，所以A1先保证供应B3 ， B3 尚缺4单位，因此X13=4，划去B3 列。 （Ⅲ）产销不平衡的运输问题 1.产大于销的情况： 2.销大于产的情况： 2.检验（闭回路法:计算空格的检验数） ①找出任意空格的闭回路—除此空格外，其余顶点均为有数格。如从a11出发可找 （ A1 B1 ）→ （ A1 B3 ） → （ A2 B3 ） → （ A2 B1 ）； ②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的代数和。 如σ11＝c11-c13+c13-c21=3-3+2-1=1③计算出此空格的检验数σij, 若σij ≥０，则该方案为最优方案，否则转３； 每一个空格的检验数=奇顶点运费之和 – 偶顶点运费之和。 3 12 6 10 A3 -1 1 1 3 A2 3 4 2 1 A1 B4 B3 B2 B1 注：检验数的经济意义，以σ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 3 12 6 10 A3 -1 1 1 3 A2 3 4 2 1 A1 B4 B3 B2 B1 σ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) 用最小元素法所得到的初始方案可以不唯一。 添加松弛变量