运筹学-运输问题的表上作业法(名校讲义).ppt

第十讲 运输问题的表上作业法 §1 运输问题事例 §2 运输问题的一般形式 §3 表上作业法 §1 运输问题事例 （1） 已知，有4个产地（源点）生产的产品需销售到4个需求地（目 的地或汇点），其源点产量和目的地需求量见表1-5。 表1-5 运输问题的需求量及产量 目的地 需求量 源点 产量 1 2 3 4 总计 22 28 17 23 90 1 2 3 4 总计 24 18 12 36 90 其源点到目的地的单位产品的运费价格见图1-7。 §1 运输问题事例 （2） 费 目 用 的 源点 地 1 2 3 4 1 ③ ⑨ ⑤ ⑥ 2 ④ ① ⑦ ④ 3 ⑥ ⑧ ② ⑤ 4 ⑤ ⑤ ④ ③ 24 18 12 36 22 28 17 23 图1-7 运输费用矩阵 表格旁边数字为产量和需要求量 §2 运输问题的一般形式 ri——源i产量， aj——目的地j的需求量。 §3 表上作业法 （1） 与单纯形表格法一样，该法亦分两步进行： ·求出初始基础可行解 ·求出最优解 1． 用最小元素法求出满意的初始基础可解 其方法是，按照费用矩阵元素Cij增长顺序逐个选择引入基 本解的变量xij，非退化情况下，每选择1个，就必然排除1 个源点或目的地，最后一步可一次排除1个源点和1个目的 地，这样便可得到一个初始基础可行解。 §3 表上作业法 （2） 以上例考察，观察图1-7。 ①∵min{cij}=c22=1。故优先分配源2和目的地2之间的产品 图1-8 最小元素法第1步 ③ ⑨ ⑤ ⑥ ④ 18 ① ⑦ ④ ⑥ ⑧ ② ⑤ ⑤ ⑤ ④ ③ 24 0 12 22 17 10 23 36 18 28 §3 表上作业法 （3） ②余下元素中，最小值为c32=2。 ? 图1-9 最小元素法第2步 ③依此类推，最后获初始基础可行解示如图1-10中。 ③ ⑨ ⑤ ⑥ ④ 18 ① ⑦ ④ ⑥ ⑧ 12 ② ⑤ ⑤ ⑤ ④ ③ 24 0 12 22 17 10 23 36 18 28 0 5 §3 表上作业法 （4） ? 图1-10 初始基础可行解 即基础解为： x11=22，x12=18，x33=12，x42=8，x43=5，x44=23。 此时总费用为225。 22③ 2⑨ ⑤ ⑥ ④ 18① ⑦ ⑤ ⑥ ⑧ 12② ⑤ ⑤ 8⑤ 5④ 23③ §3 表上作业法 （5） ? 2．求出最优解 这有两种方法：闭回路法和位势法。 ①闭回路法，其思路是令表中空格（即非基础解），对应的变量由0增加d单位，然后在保持产品供求平衡（即满足约束条件）情况下，使基础解参与变动，看其费有如何变化，若费用减少，则该非基变量可进入基，否则，加以排除，其思路与单纯形法一致。 现继上图继续改进基础解，直至达优。 i)?????? 参见图1-11，分析非基变量x32增加d单位以后，其它基础解及费用变化。 §3 表上作业法 （6） ? 22③ 2⑨ ⑤ ⑥ 24 ④ 18① ⑦ ④ 18 ⑥ ⑧+d 12②-d ⑤ 12 ⑤ 8⑤-d 5④+d 23③ 36 22 28 17 23 ? 2．求出最优解 图1-11 回路法原理 §3 表上作业法 （7） 为使供求平衡，必须符合： x32+d→x42－d→x43+d→x33－d 变动后，费用增加值为：8d－5d+4d－2d=5d，即费用增加，x32不能进基，为比较，把增加1个单位产品所引起的费用增加值填入相应的非基变量表格内，这又称检验值。 注意，在用回路法求解每个非基变量检验值时，在根据供求平衡寻找闭合回路过程中，其回路转折点必须是基础解！ 例如，分析非基解 x31↑→x11↓→x12↑→x42↓→x43↑→x33↓→x31。 §3 表上作业法 （8） ? 22 ③ 2 ⑨ ⑤ ⑥ 24 ④ 18① ⑦ ④ 18 ⑥ ⑧ 12 ② ⑤ 12 ⑤ 8 ⑤ 5 ④ 23 ③ 36 22 28 17 23 ? 9 6 9 5 -3 7 4 5 -1 对每个非基变量计算后，将其检验值填入图1-12中。 图1-12 回路法计算结果 其中：? 内表示费用元素 ? 内表示检验值 表内其它值为基