4.2用表上作业法求解运输问题表上作业法的基本思想:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进,直至求出最优方案,如下图所示。初始化最优性检验迭代(Iteration)最优?yesSTOPno这和单纯形法的求解思想完全一致,但是具体的作法则更加简捷。例1某部门有3个同类型的工厂(产地),生产的产品由4个销售点出售,各工厂的生产量、各销售点的销售量(假定单位为t)以及各工厂到销售点的单位运价(元/t)示于表4-2中,问如何调运才能使总运费最小?销地产地产量4124111621039108511622销量8141214481A2A1B2B3B4B3A表4-211x12x13x14x21x22x23x24x31x32x33x34x34333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijijij4,3,2,1;3,2,1,01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij该运输问题的数学模型为:可以证明:约束矩阵的秩r(A)=m+n-1.基变量的个数为m+n-1.表上作业法计算步骤:1、给出初始方案2、检验是否最优3、调整调运方案,Goto2表上作业法计算步骤:1、给出初始方案2、检验是否最优3、调整调运方案,Goto2下面介绍三种常用的方法。一、给出运输问题的初始可行解(初始调运方案)最小元素法西北角法沃格尔(Vogel)法1。最小元素法思想:优先满足运价(或运距)最小的供销业务。销地产地产量4124111610398511622销量141214481A2A1B2B3B4B3A表3-2①228810销地产地产量412411162109108511622销量81414481A2A1B2B3B4B3A表3-2①3②210128销地产地产量412112109108511622销量8141214481A2A1B2B3B4B3A表3-2①3②210416106③8销地产地产量4121182109108116销量81214481A2A1B2B3B4B3A表3-2①3②210416106③5142214④8销地产地产量412118210910811销量812481A2A1B2B3B4B3A表3-2①3210416106③5142214④86146⑤②销地产地产量4128210910811销量812481A2A1B2B3B4B3A表3-2①3210416106③5142214④86146⑤11⑥⑥②此时得到一个初始调运方案(初始可行解):,1013x,614x,821x,223x,1432x,834x其余变量全等于零。总运费为(目标函数值)3141ijijijxcz246685143228116410此解满足所有约束条件,且基变量(非零变量)的个数为6(等于m+n-1=3+4-1=6).⒉西北角法西北角法是优先满足运输表中西北角(左上角)上空格的供销需求。销地产地产量41241121039108511622销量141214481A2A1B2B3B4B3A表3-281611x销地产地产量41241121039108511622销量141214481A2A1B2B3B4B3A表3-2816①88销地产地产量41241121039108511622销量1214481A2A1B2B3B4B3A表3-2816①8812x14销地产地产量41241121039108511622销量141214481A2A1B2B3B4B3A表3-2816①88②6销地产地产量412411210398511622销量141214481A2A1B2B3B4B3A表3-2816①88②622x10销地产地产量412411210398511622销量141214481A2A1B2B3B4B3A表3-2816①88②6106③4销地产地产量412411210398511622销量1414481A2A1B2B3B4B3A表3-2816①88②6106③423x12销地产地产量412411210398511622销量141214481A2A1B2B3B4B3A表3-2816①88②6106③4④8销地产地产量4124112103985116销量141214481A2A1B2B3B4B3A表3-2816①886106③4②④32x822销地产地产量4124112103985116销量141214481A2A1B2B3B4B3A表3-2816①886106③4②④8228⑤14销地产地产量4124112103985116销量1412481A2A1B2B3B4B3A表3-2816①886106③4②④8228⑤1434x14销地产地产量4124112103985116销量141214481A2A1B2B3B4B3A表3-2816①886106③4②④8228⑤14⑥⑥此时得到一个初始调运方案(初始可行解):,811x,812x,622x,423x,833x,1434x其余变量全等于零。总运费为(目标函数值)3141ijijijxcz3726141183410612848此解满足所有约束条件,且基变量(非零变量)的个数为6(等于m+n-1=3+4-1=6).⒊沃格尔(Vogel)法初看起来,最小元素法十分合理。但是,有时按某一最小单位运价安排...