运筹学计算最佳运输方案和最低运费率

这是一个产销平衡的运输问题，但在百度的知识里不太容易画出表格，所以我就简单说说做法。

先画初始表。

？(5) ?(1) ?(8) 12

？(2) ?(4) ?(1) 14

？(3) ?(6) ?(7) 4

9 10 11

使用最小元素法查找运费最小的单元格，如第一行和第二列。

填写产量和销售额中较小的数字，分别从产量和销售额中减去这个数字，并划掉这一栏。

？(5) 10(1) ?(8) 2

？(2) ?(4) ?(1) 14

？(3) ?(6) ?(7) 4

9 0(已删除)11

在没有被划掉的方框里，再找一个运费最低的，比如第二行第三列。

填写产量和销售额中较小的数字，分别从产量和销售额中减去这个数字，并划掉这一栏。

？(5) 10(1) ?(8) 2

？(2) ?(4) 11(1) 3

？(3) ?(6) ?(7) 4

9 0(删除)0(删除)

在没有被划掉的方框里，再找一个运费最低的，比如第二行第一列。

填写产量和销售额中较小的数字，分别从产量和销售额中减去这个数字，划掉这条线。

？(5) 10(1) ?(8) 2

3(2) ?(4) 11(1) 0划掉。

？(3) ?(6) ?(7) 4

6 0(删除)0(删除)

在没有被划掉的方框里，再找一个运费最低的，比如第三行第一列。

填写产量和销售额中较小的数字，分别从产量和销售额中减去这个数字，划掉这条线。

？(5) 10(1) ?(8) 2

3(2) ?(4) 11(1) 0划掉。

4(3) ?(6) ?(7)删除0

2 0(删除)0(删除)

在没有划掉的方框里，再找一个运费最低的，比如第一行第一列。

填写产量和销售额中较小的数字，分别从产量和销售额中减去这个数字，然后划掉这一行和这一列。

2(5) 10(1) ?(8)划掉0

3(2) ?(4) 11(1) 0划掉。

4(3) ?(6) ?(7)删除0

0(删除)0(删除)0(删除)

从而得到一个初始可行解。

然后用位势法判断最优解。

2(5) 10(1) ?(8) 0

3(2) ?(4) 11(1) -3

4(3) ?(6) ?(7) -2

5 1 4

适马(1，3) = 4

六适马(2，2) = 6

六适马(3，2) = 7

六适马(3，3) = 5

所有的测试数都是非负的，所以它是最优解。

最优运输方案是产地1-销售地1: 2。

产地2-“销售区域1: 10”

产地1-“销售2: 3”

产地3-销售地点2: 11

产地1-“销售3: 4”

最低运费为:5 * 2+1 * 10+2 * 3+1 * 11+3 * 4 = 49。