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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4.2,用表上作业法求解运输问题,表上作业法的基本思想：,先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。,初始化,最优性检验,迭代,（,Iteration,）,最优？,yes,STOP,no,这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。,例,1,某部门有,3,个同类型的工厂（产地），生产的产品由,4,个,销售点出售，各工厂的生产量、各销售点的销售量（假定单,位为,t,）以及各工厂到销售点的单位运价（元,/t,）示于表,4-2,中，问如何调运才能使总运费最小？,销地,产地,产,量,4,12,4,11,16,2,10,3,9,10,8,5,11,6,22,销 量,8,14,12,14,48,表,4-2,该运输问题的数学模型为：,可以证明：约束矩阵的秩,r(A)=m+n-1.,基变量的个数为,m+n-1.,表上作业法,计算步骤：,1,、给出初始方案,2,、检验是否最优,3,、调整调运方案,Go to 2,表上作业法,计算步骤：,1,、给出初始方案,2,、检验是否最优,3,、调整调运方案,Go to 2,下面介绍三种常用的方法。,一、给出运输问题的初始可行解（初始调运方案）,最小元素法,西北角法,沃格尔,(Vogel),法,1,。最小元素法,思想：优先满足运价（或运距）最小的供销业务。,销地,产地,产,量,4,12,4,11,16,10,3,9,8,5,11,6,22,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,16,2,10,9,10,8,5,11,6,22,销 量,8,14,14,48,表,3-2,销地,产地,产,量,4,12,11,2,10,9,10,8,5,11,6,22,销 量,8,14,12,14,48,表,3-2,销地,产地,产,量,4,12,11,8,2,10,9,10,8,11,6,销 量,8,12,14,48,表,3-2,销地,产地,产,量,4,12,11,8,2,10,9,10,8,11,销 量,8,12,48,表,3-2,销地,产地,产,量,4,12,8,2,10,9,10,8,11,销 量,8,12,48,表,3-2,此时得到一个初始调运方案（初始可行解）：,其余变量全等于零。,总运费为（目标函数值）,此解满足所有约束条件，且基变量（非零变量）的个数为,6,（等于,m+n-1=3+4-1=6).,西北角法,西北角法是优先满足运输表中西北角（左上角）上空格的供,销需求。,销地,产地,产,量,4,12,4,11,2,10,3,9,10,8,5,11,6,22,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,10,8,5,11,6,22,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,10,8,5,11,6,22,销 量,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,10,8,5,11,6,22,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,22,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,22,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,22,销 量,14,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,22,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,销 量,14,12,14,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,销 量,14,12,48,表,3-2,销地,产地,产,量,4,12,4,11,2,10,3,9,8,5,11,6,销 量,14,12,14,48,表,3-2,此时得到一个初始调运方案（初始可行解）：,其余变量全等于零。,总运费为（目标函数值）,此解满足所有约束条件，且基变量（非零变量）的个数为,6,（等于,m+n-1=3+4-1=6).,沃格尔（,Vogel),法,初看起来，最小元素法十分合理。但是，有时按某一最小单位运价安排物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。,沃格尔法的思想：,对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最大罚数安排运输。,销 地,产地,产,量,行罚数,1,2,3,4,12,4,11,16,0,2,10,3,9,10,1,8,11,6,1,销 量,8,12,14,48,列,罚,数,1,2,5,1,3,2,3,销 地,产地,产,量,行罚数,1,2,3,4,12,4,11,16,0,0,2,10,3,9,10,1,1,8,5,11,22,1,2,销 量,8,14,12,48,列,罚,数,1,2,5,1,3,2,2,1,3,3,销 地,产地,产,量,行罚数,1,2,3,4,12,4,11,16,0,0,0,10,3,9,1,1,1,8,5,11,22,1,2,销 量,14,12,48,列,罚,数,1,2,5,1,3,2,2,1,3,3,2,1,销 地,产地,产,量,行罚数,4,5,6,4,12,11,7,10,3,9,6,8,5,11,22,销 量,14,48,列,罚,数,4,1,2,5,6,销 地,产地,产,量,行罚数,4,5,6,4,12,11,7,0,10,3,6,0,8,5,11,22,销 量,14,48,列,罚,数,4,1,2,5,2,6,此时得到一个初始调运方案（初始可行解）：,其余变量全等于零。,总运费为（目标函数值）,此解满足所有约束条件，且基变量（非零变量）的个数为,6,（等于,m+n-1=3+4-1=6).,比较上述三种方法给出的初始基可行解，以沃格尔法给出的解的目标函数值最小，最小元素法次之，西北角法解的目标函数值最大。,一般说来，沃格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似值。,销地,产地,产,量,4,1,4,6,8,1,2,5,0,8,3,7,5,1,4,销 量,6,5,6,3,20,课堂练习,