第六讲 运输问题的表上作业法.pptVIP

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