运输问题-初始基可行解的确定VIP专享VIP免费

4.2用表上作业法求解运输问题表上作业法的基本思想：先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。初始化最优性检验迭代（Iteration）最优？yesSTOPno这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。例1某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2中，问如何调运才能使总运费最小？销地产地产量4124111621039108511622销量8141214481A2A1B2B3B4B3A表4-211x12x13x14x21x22x23x24x31x32x33x34x34333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijijij4,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⑥⑥②此时得到一个初始调运方案（初始可行解）：,1013x,614x,821x,223x,1432x,834x其余变量全等于零。总运费为（目标函数值）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⑥⑥此时得到一个初始调运方案（初始可行解）：,811x,812x,622x,423x,833x,1434x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz3726141183410612848此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).⒊沃格尔（Vogel)法初看起来，最小元素法十分合理。但是，有时按某一最小单位运价安排...