《运输问题-初始基可行解的确定》由会员分享，可在线阅读，更多相关《运输问题-初始基可行解的确定（40页珍藏版）》请在金锄头文库上搜索。
1、 4.2 用表上作业法求解运输问题表上作业法的基本思想：先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。初始化最优性检验迭代 （Iteration）最优？yes STOPno这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。例1 某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2中，问如何调运才能使总运费最小？销地产地产 量 412411 1621039 1085116 22销 量814121448表 4-2该运输问题
2、的数学模型为：可以证明：约束矩阵的秩 r (A) = m +n -1.基变量的个数为 m+n-1.表上作业法v计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2表上作业法v计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2下面介绍三种常用的方法。一、给出运输问题的初始可行解（初始调运方案）l最小元素法l西北角法l沃格尔(Vogel)法1。最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地产 量412411 16103985116 22销 量14121448表 3-2销地产地产 量412411 162109 1085
3、116 22销 量8141448表 3-2销地产地产 量412112109 1085116 22销 量814121448表 3-2销地产地产 量4121182109 108116销 量8121448表 3-2销地产地产 量4121182109 10811销 量81248表 3-2销地产地产 量41282109 10811销 量81248表 3-2此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6). 西北角法西北角法是优先满足运输表中西北角（左上角）上空格的供销需求。销地产地产 量
4、 41241121039 1085116 22销 量14121448表 3-2销地产地产 量41241121039 1085116 22销 量14121448表 3-2销地产地产 量41241121039 1085116 22销 量121448表 3-2销地产地产 量41241121039 1085116 22销 量14121448表 3-2销地产地产 量4124112103985116 22销 量14121448表 3-2销地产地产 量4124112103985116 22销 量14121448表 3-2销地产地产 量4124112103985116 22销 量141448表 3-2销地产地
5、产 量4124112103985116 22销 量14121448表 3-2销地产地产 量4124112103985116销 量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、合理。但是，有时按某一最小单位运价安排物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。沃格尔法的思想：对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最大罚数安排运输。销 地 产地产 量行罚数 123412411 160 21039 101 8116 1 销 量8121448 列 罚 数12513 2 3销 地 产地产 量行罚数 12
7、3412411 1600 21039 1011 8511 2212 销 量8141248 列 罚 数12513 2213 3销 地 产地产 量行罚数 123412411 16000 1039 111 8511 2212 销 量141248 列 罚 数12513 2213 321销 地 产地产 量行罚数 45641211 7 1039 6 8511 22 销 量1448 列 罚 数412 5 6销 地 产地产 量行罚数 45641211 70 103 60 8511 22 销 量1448 列 罚 数412 5 2 6此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).比较上述三种方法给出的初始基可行解，以沃格尔法给出的解的目标函数值最小，最小元素法次之，西北角法解的目标函数值最大。一般说来，沃格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似值。销地产地产 量4146 81250 83751 4销 量656320课堂练习
