运输问题初始基可行解的确定PPT学习教案

1、会计学1 运输问题初始基可行解的确定运输问题初始基可行解的确定 初始化 最优性检验 迭代 （Iteration） 最优？ yes STOP no 这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。 第1页/共40页 例1 某部门有3个同类型的工厂（产地），生产的产品由4个 销售点出售，各工厂的生产量、各销售点的销售量（假定单 位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2 中，问如何调运才能使总运费最小？ 第2页/共40页 销地 产地 产 量 412411 16 21039 10 85116 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B

2、3 A 表 4-2 11 x 12 x 13 x 14 x 21 x 22 x23 x 24 x 31 x 32 x 33 x 34 x 第3页/共40页 34333231242322 21 3 1 4 1 14131211 611589310 2114124min xxxxxxx xxxxxxcz ij ijij 4 , 3 , 2 , 1; 3 , 2, 1, 0 14 12 14 8 22 10 16 342414 332313 322212 312111 34333231 24232221 14131211 jix xxx xxx xxx xxx xxxx xxxx xxxx ij 该

3、运输问题的数学模型为： 第4页/共40页 可以证明：约束矩阵的秩 r (A) = m +n -1. 基变量的个数为 m+n-1. 第5页/共40页 第6页/共40页 第7页/共40页 下面介绍三种常用的方法。 一、给出运输问题的初始可行解（初始调运方案） l最小元素法 l西北角法 l沃格尔(Vogel)法 第8页/共40页 1。最小元素法 思想：优先满足运价（或运距）最小的供销业务。 第9页/共40页 销地 产地 产 量 412411 16 1039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 22 8 8 10 第10页/共

4、40页 销地 产地 产 量 412411 16 2109 10 85116 22 销 量 8141448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 12 8 第11页/共40页 销地 产地 产 量 41211 2109 10 85116 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 4 16 10 6 8 第12页/共40页 销地 产地 产 量 41211 8 2109 10 8116 销 量 8121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2

5、10 4 16 10 6 5 14 22 14 8 第13页/共40页 销地 产地 产 量 41211 8 2109 10 811 销 量 81248 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 4 16 10 6 5 14 22 14 86 146 第14页/共40页 销地 产地 产 量 412 8 2109 10 811 销 量 81248 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 4 16 10 6 5 14 22 14 8 6 146 11 第15页/共40页 此时得到一个初始调运方案（初始可行解）： ,10

6、 13 x , 6 14 x, 8 21 x, 2 23 x,14 32 x, 8 34 x 其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 246685143228116410 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). 第16页/共40页 西北角法 西北角法是优先满足运输表中西北角（左上角）上空格的供 销需求。 第17页/共40页 销地 产地 产 量 412411 21039 10 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 11

7、x 第18页/共40页 销地 产地 产 量 412411 21039 10 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 第19页/共40页 销地 产地 产 量 412411 21039 10 85116 22 销 量 121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 12 x 14 第20页/共40页 销地 产地 产 量 412411 21039 10 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-

8、2 8 16 8 8 6 第21页/共40页 销地 产地 产 量 412411 21039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 22 x 10 第22页/共40页 销地 产地 产 量 412411 21039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 第23页/共40页 销地 产地 产 量 412411 21039 85116 22 销 量 141448 1 A 2 A 1 B 2 B 3 B

9、 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 23 x 12 第24页/共40页 销地 产地 产 量 412411 21039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 8 第25页/共40页 销地 产地 产 量 412411 21039 85116 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 32 x 8 22 第26页/共40页 销地 产地 产 量 412411 21039 851

10、16 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 8 22 8 14 第27页/共40页 销地 产地 产 量 412411 21039 85116 销 量 141248 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 8 22 8 14 34 x 14 第28页/共40页 销地 产地 产 量 412411 21039 85116 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6

11、4 8 22 8 14 第29页/共40页 此时得到一个初始调运方案（初始可行解）： , 8 11 x , 8 12 x, 6 22 x, 4 23 x, 8 33 x,14 34 x 其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 3726141183410612848 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). 第30页/共40页 沃格尔（Vogel)法 初看起来，最小元素法十分合理。但是，有时按某一最小单位运价安排物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。 沃格尔法的思想

12、： 对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最大罚数安排运输。 第31页/共40页 销 地 产地 产 量 行罚数 123 412411 160 21039 101 8116 1 销 量 8121448 列 罚 数 12513 2 3 1 A 2 A 1 B 2 B 3 B 4 B 3 A 5 14 22 14 8 第32页/共40页 销 地 产地 产 量

13、行罚数 123 412411 1600 21039 1011 8511 2212 销 量 8141248 列 罚 数 12513 2213 3 1 A 2 A 1 B 2 B 3 B 4 B 3 A 8 14 6 14 6 第33页/共40页 销 地 产地 产 量 行罚数 123 412411 16000 1039 111 8511 2212 销 量 141248 列 罚 数 12513 2213 321 1 A 2 A 1 B 2 B 3 B 4 B 3 A 8 14 6 14 6 2 8 10 8 2 第34页/共40页 销 地 产地 产 量 行罚数 456 41211 7 1039 6

14、8511 22 销 量 1448 列 罚 数 412 5 6 1 A 2 A 1 B 2 B 3 B 4 B 3 A 8 14 6 14 6 2 8 10 8 2 4 12 16 12 4 第35页/共40页 销 地 产地 产 量 行罚数 456 41211 70 103 60 8511 22 销 量 1448 列 罚 数 412 5 2 6 1 A 2 A 1 B 2 B 3 B 4 B 3 A 8 14 6 14 6 2 8 10 8 2 4 12 16 12 4 9 4 第36页/共40页 此时得到一个初始调运方案（初始可行解）： ,12 13 x , 4 14 x, 8 21 x, 2 24 x 32 14,x, 8 34 x 其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 244685149228114412 此解满足所有约束条件，且基变量（非零变量）的个数为6