《管理运筹学》演示(运输问题).ppt
010-62374836(宅)华北电力大学华北电力大学线性规划图解法单纯形表结构线性规划单纯形法(1)最小元素法伏格尔法闭回路法位势法闭回路调整法目标规划图解法(1)目标规划图解法(2)整数规划(分枝定界法)和和线性规划单纯形法(2)图解法与单纯形法的联系指派问题(匈牙利法)(1)使用计算机软件包求解指派问题(匈牙利法)(2)0-1规划(隐枚举法)整数规划(割平面法)典型应用案例线性规划单纯形法(3)目标规划单纯形法线性规划求解几种结果几种常用规划数学软件比较动态规划(1)动 态 规 划(2)最小树问题(破圈法/避圈法)最短路问题(迪克斯拉法)(1)最大流问题(福克逊法)最小费用最大流问题(2)对偶单纯形法改进单纯形法动态规划(逆推法)(顺推法)(3)销地产地B1B2B3B4A1A2A3销量产量产地A1A2A3销地B1B2B3B47493656317119432101085最小元素法1 12 2334 45 51010产销平衡表产销平衡表单位运价表单位运价表运输问题运输问题(表上作业法表上作业法)销地销地B1B2B3B4产地产地A1A2A3销量3656产量749产销平衡表产销平衡表伏格尔法伏格尔法销地销地B1B2B3B4A1A2A3产地产地单位运价表单位运价表317119432101085行差额行差额列差额列差额011601213 32133121231276252102081885552 27 7 1010运输问题运输问题(表上作业法表上作业法)产地产地A1A2A3销地销地B1B2B3B4销量销量3 36 65 56 6产量产量7 74 49 9闭回路法闭回路法333146311197432101058检验数表检验数表 (+1)(-1)(+1)(-1)?1A1A3产地A2销地B1B2B3B4产销平衡表产销平衡表+单位运价表单位运价表运输问题运输问题(表上作业法表上作业法)产地产地A1A2A3销地销地B1B2B3B4销量销量3 36 65 56 6产量产量7 74 49 9闭回路法闭回路法333146311197432101058检验数表检验数表 (+1)(-1)(+1)(-1)21A1A3产地A2销地B1B2B3B4产销平衡表产销平衡表+单位运价表单位运价表运输问题运输问题(表上作业法表上作业法)产地产地A1A2A3销地销地B1B2B3B4销量销量3 36 65 56 6产量产量7 74 49 9闭回路法闭回路法333146311197432101058检验数表检验数表 21(+1)(-1)(+1)(-1)(+1)(-1)1A1A3产地A2销地B1B2B3B4产销平衡表产销平衡表+单位运价表单位运价表运输问题运输问题(表上作业法表上作业法)产地产地A1A2A3销地销地B1B2B3B4销量销量3 36 65 56 6产量产量7 74 49 9闭回路法闭回路法333146311197432101058检验数表检验数表 211(+1)(-1)(+1)(-1)(+1)(-1)A1A3产地A2销地B1B2B3B4产销平衡表产销平衡表+单位运价表单位运价表运输问题运输问题(表上作业法表上作业法)产地产地A1A2A3销地销地B1B2B3B4销量销量3 36 65 56 6产量产量7 74 49 9闭回路法闭回路法333146311197432101058检验数表检验数表 211A1A3产地A2销地B1B2B3B4(+1)(-1)(+1)(-1)产销平衡表产销平衡表+单位运价表单位运价表运输问题运输问题(表上作业法表上作业法)产地产地A1A2A3销地销地B1B2B3B4销量销量3 36 65 56 6产量产量7 74 49 9闭回路法闭回路法333146311197432101058检验数表检验数表 211A1A3产地A2销地B1B2B3B4(-1)(+1)(-1)(+1)产销平衡表产销平衡表+单位运价表单位运价表销地产地B1B2B3B4A1A2A3销量产量7493656最小元素法314633产销平衡表产销平衡表3 16 45321013销量产量365674最小元素法位势表位势法3521920-418列位势行位势销地B1B2B3B4检验数表产地A1A2A3列位势1829行位势10-437119108注:浮碉数字代表运价1102112-1销地B1B2B3B4产地A1A2A3销量3656产量749闭回路调整法闭回路调整法364133(+1)(-1)(+1)(-1)(-1)(-1)(-1)(-1)1 1调 整 表表调整后的运输方案销地B1B2B3B4产地A1A2A3销量3656产量749365132从运价表中找出一最小值(称最小元素)，当有两个以上最小元素时，可任选其中的一个，该元素的位置即为要调运的位置；在产销平衡表对应最小运价的位置进行分配，尽可能调运；在单位运价表中划去以被满足的行或列处的运价，表示该行或列的调运已完成；重复上述步骤。再在上面运价表中找出没有被划去的最小元素，再在产销平衡表对应的最小运价位置进行调运分配，并划去相应的行或 列。步骤如下：步骤如下：q 从单位运价表中每行和每列上分别找出两个最小元素，计算这两个最小元素的差额，最大差额所在的行或列中最小运价所在位置，即优先进行调运的位置；q 在产销平衡表上相应的调运位置上尽最大可能调运；q 在运价表上划去相应的行或列的运价；q 重复上面步骤，再在运价表中计算各行和各列没有划去的最小运价和次小运价的差额，确定最大差额所在的行或列中最小运价的位置，并进行调运，同时在运价表上划去相应的行或列的运价。步骤如下：步骤如下：v先做一个位势表，位势表结构与平衡表类似，将产销平衡表 数字格中运量换以运价，并在表的右端增加1列行位势 和在表的下端增加1行列位势 ；v任意给定某一行位势或列位势的值，再按照公式 确定其它的 或 值。这里，为运价；v计算空格检验数。任一空格的检验数按下式计算：式中 为该空格对应的运价，和 分别为该行和该列的位势。步骤如下:从检验数表中找出最小的负检验数。当有两个或两个以上的负检验数时，选取其中最小的检验数；在产销平衡表中以最小的负检验数所对应的空格为起点，作一闭回路，闭回路上其它顶点必须是数字格，再从起点开始沿闭回路按顺时针或逆时针增加1个单位运量(标注+1),其它顶点相应的增加(标注+1),或减少(标注-1)1个单位运量,以保持供需平衡；确定调运方案的调整量。所有标注(-1)数字格所对应运量的最小值，为调运方案的调整量。给所有标注(+1)数字格运量增加一个调整量，所有标注(-1)数字格运量减少一个调整量，闭回路之外的其它运量保持不变,这样得到一个新的调运方案。步骤如下：步骤如下：Keep Connecting In The FutureKeep Connecting In The FutureE-mail:E-mail:
