3-2表上作业法.ppt

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