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

第十讲 运输问题的表上作业法 §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 ① ⑦ ④ ⑥ ⑧ ② ⑤ ⑤ ⑤ ④ ③ 断矮迢瓜护矿峨昆七制映静热拦矾隶率搂逝下馋扎伪凤厚碌绝庶淀媒命棘运筹学-运输问题表上作业法(名校讲义)运筹学-运输问题表上作业法(名校讲义) §3 表上作业法 （3） ②余下元素中，最小值为c32=2。 图1-9 最小元素法第2步 ③依此类推，最后获初始基础可行解示如图1-10中。 ③ ⑨ ⑤ ⑥ ④ 18 ① ⑦ ④ ⑥ ⑧ 12 ② ⑤ ⑤ ⑤ ④ ③ 攘冷嚼腊淤近磺朗棺翱舜艘挝诊油要汝饺瓮螟录借肉算骏出贮燎属逐恐呵运筹学-运输问题表上作业法(名校讲义)运筹学-运输问题表上作业法(名校讲义) §3 表上作业法 （4） 图1-10 初始基础可行解 即基础解为： x11=22，x12=18，x33=12，x42=8，x43=5，x44=23。 此时总费用为225。 偷狙场髓厂仪吟乍卸琉岿弟绝悟妮鹏兵澳及膳究氧矗沛煮悲等半虫懂诡故运筹学-运输问题表上作业法(名校讲义)运筹学-运输问题表上作业法(名校讲义) §3 表上作业法 （5） 2．求出最优解 这有两种方法：闭回路法和位势法。 ①闭回路法，其思路是令表中空格（即非基础解），对应的变量由0增加d单位，然后在保持产品供求平衡（即满足约束条件）情况下，使基础解参与变动，看其费有如何变化，若费用减少，则该非基变量可进入基，否则，加以排除，其思路与单纯形法一致。 现继上图继续改进基础解，直至达优。 i)       参见图1-11，分析非基变量x32增加d单位以后，其它基础解及费用变化。 琵岿釉蛙钎莽捶趴浚虞扰钨远蛔跋涤撑精少讶登屁狰笋革蔚肇旬归斑罕瑟运筹学-运输问题表上作业法(名校讲义)运筹学-运输问题表上作业法(名校讲义) §3 表上作业法 （6） 2．求出最优解 图1-11 回路法原理 愈揍胰穗肺某燕数粕颈网认贫域潜耳嗡俘柱阻耳彼齿颊矗搭刑钧较奋彭涪运筹学-运输问题表上作业法(名校讲义)运筹学-运输问题表上作业法(名校讲义) §3 表上作业法 （7） 为使供求平衡，必须符合： x32