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

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

2、21039108511622销 量8141214481A2A1B2B3B4B3A表 4-211x12x13x14x21x22x23x24x31x32x33x34x运输问题-初始基可行解的确定34333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijijij4 , 3 , 2 , 1; 3 , 2, 1, 01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij该运输问题的数学模型为：运输问题-初始基可

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

4、 4124111610398511622销 量141214481A2A1B2B3B4B3A表 3-2228810运输问题-初始基可行解的确定 销地产地产量 412411162109108511622销 量 81414481A2A1B2B3B4B3A表 3-23210128运输问题-初始基可行解的确定 销地产地产量 412112109108511622销 量 8141214481A2A1B2B3B4B3A表 3-232104161068运输问题-初始基可行解的确定 销地产地产量 4121182109108116销 量 81214481A2A1B2B3B4B3A表 3-23210416106514

5、22148运输问题-初始基可行解的确定 销地产地产量 412118210910811销 量 812481A2A1B2B3B4B3A表 3-23210416106514221486146运输问题-初始基可行解的确定 销地产地产量 4128210910811销 量 812481A2A1B2B3B4B3A表 3-2321041610651422148614611运输问题-初始基可行解的确定此时得到一个初始调运方案（初始可行解）：,1013x, 614x, 821x, 223x,1432x, 834x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz246685143228116410

6、此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).运输问题-初始基可行解的确定 西北角法西北角法是优先满足运输表中西北角（左上角）上空格的供销需求。运输问题-初始基可行解的确定 销地产地产量41241121039108511622销 量141214481A2A1B2B3B4B3A表 3-281611x运输问题-初始基可行解的确定 销地产地产量 41241121039108511622销 量141214481A2A1B2B3B4B3A表 3-281688运输问题-初始基可行解的确定 销地产地产量 41241121039108511622销 量1214481A

7、2A1B2B3B4B3A表 3-28168812x14运输问题-初始基可行解的确定 销地产地产量 41241121039108511622销 量141214481A2A1B2B3B4B3A表 3-2816886运输问题-初始基可行解的确定 销地产地产量 412411210398511622销 量141214481A2A1B2B3B4B3A表 3-281688622x10运输问题-初始基可行解的确定 销地产地产量 412411210398511622销 量141214481A2A1B2B3B4B3A表 3-28168861064运输问题-初始基可行解的确定 销地产地产量 412411210398

8、511622销 量1414481A2A1B2B3B4B3A表 3-2816886106423x12运输问题-初始基可行解的确定 销地产地产量 412411210398511622销 量141214481A2A1B2B3B4B3A表 3-281688610648运输问题-初始基可行解的确定 销地产地产量 4124112103985116销 量141214481A2A1B2B3B4B3A表 3-2816886106432x822运输问题-初始基可行解的确定 销地产地产量 4124112103985116销 量141214481A2A1B2B3B4B3A表 3-28168861064822814运输

9、问题-初始基可行解的确定 销地产地产量 4124112103985116销 量1412481A2A1B2B3B4B3A表 3-2816886106482281434x14运输问题-初始基可行解的确定 销地产地产量 4124112103985116销 量141214481A2A1B2B3B4B3A表 3-28168861064822814运输问题-初始基可行解的确定此时得到一个初始调运方案（初始可行解）：, 811x, 812x, 622x, 423x, 833x,1434x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz3726141183410612848此解满足所有约束条

10、件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).运输问题-初始基可行解的确定 沃格尔（Vogel)法初看起来，最小元素法十分合理。但是，有时按某一最小单位运价安排物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。沃格尔法的思想： 对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最大罚数安排运输。运输问题-初始基可行

11、解的确定销 地产地产量行罚数1234124111602103910181161销 量8121448列罚数12513231A2A1B2B3B4B3A51422148运输问题-初始基可行解的确定销 地产地产量行罚数123 412411160021039101185112212销 量8141248列罚数12513221331A2A1B2B3B4B3A8146146运输问题-初始基可行解的确定销 地产地产量行罚数123 41241116000103911185112212销 量141248列罚数1251322133211A2A1B2B3B4B3A8146146281082运输问题-初始基可行解的确定销 地产地产量行罚数456 41211710396851122销 量1448列罚数412561A2A1B2B3B4B3A814614628108241216124运输问题-初始基可行解的确定销 地产地产量行罚数456 412117010360851122销 量1448列罚数4125 261A2A1B2B3B4B3A81461462810824121612494运输问题-初始基可行解的确定此时得到一个初始调运方案（初始可行解）：,1213x, 414x, 821x, 224x3214,x, 834x其余变量全等于零。总运费为（目标函数值）3141ijijijxc