运输问题-初始欣赏基可行解的确定.ppt

表上作业法 计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 表上作业法 计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 * * 4.2 用表上作业法求解运输问题 表上作业法的基本思想： 先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。 初始化 最优性检验 迭代 （Iteration） 最优？ yes STOP no 这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。 例1 某部门有3个同类型的工厂（产地），生产的产品由4个 销售点出售，各工厂的生产量、各销售点的销售量（假定单 位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2 中，问如何调运才能使总运费最小？ 6 11 5 9 3 10 8 2 11 48 22 10 16 产 量 14 12 14 8 销 量 4 12 4 销地 产地 表 4-2 该运输问题的数学模型为： 可以证明：约束矩阵的秩 r (A) = m +n -1. 基变量的个数为 m+n-1. 下面介绍三种常用的方法。 一、给出运输问题的初始可行解（初始调运方案） 最小元素法 西北角法 沃格尔(Vogel)法 1。最小元素法 思想：优先满足运价（或运距）最小的供销业务。 6 11 5 9 3 10 8 11 48 22 16 产 量 14 12 14 销 量 4 12 4 销地 产地 表 3-2 ① 6 11 5 9 10 8 2 11 48 22 10 16 产 量 14 14 8 销 量 4 12 4 销地 产地 表 3-2 ① ② 6 11 5 9 10 8 2 11 48 22 10 产 量 14 12 14 8 销 量 12 4 销地 产地 表 3-2 ① ② ③ 6 11 9 10 8 2 11 48 10 产 量 14 12 8 销 量 12 4 8 销地 产地 表 3-2 ① ② ③ ④ 11 9 10 8 2 11 48 10 产 量 12 8 销 量 12 4 8 销地 产地 表 3-2 ① ③ ④ ⑤ ② 11 9 10 8 2 48 10 产 量 12 8 销 量 12 4 8 销地 产地 表 3-2 ① ③ ④ ⑤ ⑥ ⑥ ② 此时得到一个初始调运方案（初始可行解）： 其余变量全等于零。 总运费为（目标函数值） 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). ⒉ 西北角法 西北角法是优先满足运输表中西北角（左上角）上空格的供 销需求。 6 11 5 9 3 10 8 2 11 48 22 10 产 量 14 12 14 销 量 4 12 4 销地 产地 表 3-2 6 11 5 9 3 10 8 2 11 48 22 10 产 量 14 12 14 销 量 4 12 4 销地 产地 表 3-2 ① 6 11 5 9 3 10 8 2 11 48 22 10 产 量 14 12 销 量 4 12 4 销地 产地 表 3-2 ① 6 11 5 9 3 10 8 2 11 48 22 10 产 量 14 12 14 销 量 4 12 4 销地 产地 表 3-2 ① ② 6 11 5 9 3 10 8 2 11 48 22 产 量 14 12 14 销 量 4 12 4 销地 产地 表 3-2 ① ② 6 11 5 9 3 10 8 2 11 48 22 产 量 14 12 14 销 量 4 12 4 销地 产地 表 3-2 ① ② ③ 6 11 5 9 3 10 8 2 11 48 22 产 量 14 14 销 量 4 12 4 销地 产地 表 3-2 ① ② ③ 6 11 5 9 3 10 8 2 11 48 22 产 量 14 12 14 销 量 4 12 4 销地 产地 表 3-2 ① ② ③ ④ 6 11 5 9 3 10 8 2 11 48 产 量 14 12 14 销 量 4 12