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

《运筹学-运输问题的表上作业法(名校讲义)精选ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第十讲运输问题的表上作业法§1运输问题事例§2运输问题的一般形式§3表上作业法§1运输问题事例（1）已知，有4个产地（源点）生产的产品需销售到4个需求地（目的地或汇点），其源点产量和目的地需求量见表1-5。表1-5运输问题的需求量及产量目的地需求量源点产量1234总计22281723901234总计2418123690其源点到目的地的单位产品的运费价格见图1-7。§1运输问题事例（2）费目用的源点地12341③⑨⑤⑥2④①⑦④3⑥⑧②⑤4⑤⑤④③2418123622281723图1-7运输费用矩阵表格旁边数字为产量和需要求量

2、§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步

3、③⑨⑤⑥④18①⑦④⑥⑧②⑤⑤⑤④③2401222171023361828§3表上作业法（3）②余下元素中，最小值为c32=2。图1-9最小元素法第2步③依此类推，最后获初始基础可行解示如图1-10中。③⑨⑤⑥④18①⑦④⑥⑧12②⑤⑤⑤④③240122217102336182805§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．求出最优解这

4、有两种方法：闭回路法和位势法。①闭回路法，其思路是令表中空格（即非基础解），对应的变量由0增加d单位，然后在保持产品供求平衡（即满足约束条件）情况下，使基础解参与变动，看其费有如何变化，若费用减少，则该非基变量可进入基，否则，加以排除，其思路与单纯形法一致。现继上图继续改进基础解，直至达优。i)参见图1-11，分析非基变量x32增加d单位以后，其它基础解及费用变化。§3表上作业法（6）22③2⑨⑤⑥24④18①⑦④18⑥⑧+d12②-d⑤12⑤8⑤-d5④+d23③36222817232．求出最优解图1-11回路法原理§3表

5、上作业法（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③36222

6、817239695-3745-1对每个非基变量计算后，将其检验值填入图1-12中。图1-12回路法计算结果其中：内表示费用元素内表示检验值表内其它值为基础解。§3表上作业法（9）ii)观察表格，或检验值全部≥0，已达最优胜，结束。否则，选取最负的检验值所对的非基变量，令其进基。图1-12中，x13的检验值为最负，故令x13进基，应使x13尽量大，但又必须使其它变量非负。观察x13变化规律：x13↑→x12↓→x42↑→x43↓。应取下降变量中的最小值作为x13的值。此时min{x12，x43}=min{2，5}=2。故令

7、x13=2则x12=0，x42=10，x43=3。将图1-12修正后，再求出当前非变量的检验值，示如图1-13。非基础解的检验数合为正，故获最成解，总费用为249。§3表上作业法（10）22③⑨2⑤⑥24④18①⑦④18⑥⑧12②⑤12⑤10⑤3④23③3622281723636357452图1-13回路法所得最优表格§3表上作业法（11）②位势法（简捷法）该法对运输费用矩阵表格每次可确定一组“行值”和“列值”。确定原则为使得每个基础变量之费用cij等于相应得行、列值之和，根据该原则求出行列值之后，用这些值再去求解每个非基本

8、变量的检验数。结合本例阐述该步骤：（见图1-14）§3表上作业法（12）图1-14用位势法求解实例22③2⑨⑤⑥24④18①⑦④18⑥⑧12②⑤12⑤8⑤5④23③3622281723969-35745-1S1S2S3S4t1t2t3t4§3表上作业法（13）i)令si，tj分别为行值和列