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

《运输问题-初始基可行解的确定.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、4.2用表上作业法求解运输问题表上作业法的基本思想：先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。初始化最优性检验迭代（Iteration）最优？yesSTOPno这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。例1某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2中，问如何调运才能使总运费最小？销地产地产量4124111621039108511622销量814121448表4-2该运输问题的数学模型为：可以

2、证明：约束矩阵的秩r(A)=m+n-1.基变量的个数为m+n-1.表上作业法计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2表上作业法计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2下面介绍三种常用的方法。一、给出运输问题的初始可行解（初始调运方案）最小元素法西北角法沃格尔(Vogel)法1。最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地产量4124111610398511622销量14121448表3-2①销地产地产量412411162109108511622销量8141448表3-2①②销地产地产量4121121091085

3、11622销量814121448表3-2①②③销地产地产量4121182109108116销量8121448表3-2①②③④销地产地产量412118210910811销量81248表3-2①③④⑤②销地产地产量4128210910811销量81248表3-2①③④⑤⑥⑥②此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).⒉西北角法西北角法是优先满足运输表中西北角（左上角）上空格的供销需求。销地产地产量41241121039108511622销量14121448表3-2销地

4、产地产量41241121039108511622销量14121448表3-2①销地产地产量41241121039108511622销量121448表3-2①销地产地产量41241121039108511622销量14121448表3-2①②销地产地产量412411210398511622销量14121448表3-2①②销地产地产量412411210398511622销量14121448表3-2①②③销地产地产量412411210398511622销量141448表3-2①②③销地产地产量412411210398511622销量14121448表3-2①②③④销地产地产量412411210

5、3985116销量14121448表3-2①③②④销地产地产量4124112103985116销量14121448表3-2①③②④⑤销地产地产量4124112103985116销量141248表3-2①③②④⑤销地产地产量4124112103985116销量14121448表3-2①③②④⑤⑥⑥此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).⒊沃格尔（Vogel)法初看起来，最小元素法十分合理。但是，有时按某一最小单位运价安排物品调运时，却可能导致不得不采用运费很高的其

6、他供销点，从而使整个运输费用增加。沃格尔法的思想：对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最大罚数安排运输。销地产地产量行罚数1234124111602103910181161销量8121448列罚数1251323销地产地产量行罚数123412411160021039101185112212销量8141248列罚数1251322133销地产地产量行罚

7、数12341241116000103911185112212销量141248列罚数125132213321销地产地产量行罚数45641211710396851122销量1448列罚数41256销地产地产量行罚数456412117010360851122销量1448列罚数412526此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+