第二节 运输问题的表上作业法.pptVIP

运输问题——表上作业法 第二节 运输问题的 表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。 表上作业法是单纯形法在求解运输问题的一种简便方法。 单纯形法与表上作业法的关系： （1）找出初始基可行解 （2）求各非基变量的检验数 （3）判断是否最优解 运输问题——表上作业法 计算表中空格检验数 表上给出m+n-1个数字格 判断方法相同 换基： （4）确定换入变量和换出变量找出新的基可行解。 （5）重复（2）、（3）直至求出最优解。 运输问题——表上作业法 表上调整（闭回路调整） （运输问题必有最优解） 停止 最优解 ？ 是 否 举例说明表上作业法： 例1、某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表： 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 第一步：确定初始基可行解 ——最小元素法、伏格尔法 方法1：最小元素法 最小元素法思路： 从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。? 运输问题——表上作业法 最小元素法举例： 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 2 0 10 10 0 6 14 8 6 8 0 0 0 0 6 0 最小元素法举例： 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 最小元素法缺点：会出现顾此失彼 （运费差额问题） 考虑运价差 罚数（即差额）=次小运价-最小运价 罚数（或差额）的解释： 差额大，则不按最小运费调运，运费增加大。 差额小，则不按最小运费调运，运费增加不大。 运输问题——表上作业法 对差额最大处，采用最小运费调运。 方法2：沃格尔法 沃格尔法思路： 结合例1说明这种方法。 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 行罚数 ① 0 4-4=0 第一次： 结合例1说明这种方法。 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 行罚数 ① 0 1 3-2=1 第一次： 结合例1说明这种方法。 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 行罚数 ① 0 1 1 第一次： 结合例1说明这种方法。 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 行罚数 ① 0 1 1 列 罚 数 4-2=2 2 1 5 3 ① 第一次： 结合例1说明这种方法。 运输问题——表上作业法 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 行罚数 ① 0 1 1 列 罚 数 2 1 5 3 ① 14 8 0 优先安排销地 ，否则运价会更高 下次不考虑该列 第一次： 结合例1说明这种方法。 运输问题——表上作业法 第二次： 行罚数 ② 0 1 1 列 罚 数 2 1 3 ② 优先安排销地 ，否则运价会更高 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 14 8 0 0 6 下次不考虑该行 结合例1说明这种方法。 运输问题——表上作业法 行罚数 ③ 0 1 列 罚 数 2 1 2 ③ 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 14 8 0 0 6 下次不考虑该列 8 0 2 第三次： 结合例1说明这种方法。 运输问题——表上作业法 行罚数 ④ 7 6 列 罚 数 1 2 ④ 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 14 8 0 0 6 8 0 2 4 12 0 下次不考虑该列 第四次: 结合例1说明这种方法。 运输问题——表上作业法 行罚数 ⑤ 0 0 列 罚 数 2 ⑤ 4 2 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产