运筹我刚考完
1 最小元素法:
在运费表中找到最小运费 并满足 当产大于销时 划去销地的列 满足的量为该列销量
当产小于销时 划去产地的行 满足的量为该行产量
将所有满足的量填入产销平衡表中对应的格子
则最终的产销平衡表为:
8 2 - - 10
- - 2 18 20
- 20 10 - 30
于是 最小运费为:8*1+2*2+6*2+5*18+20*10+10*11=454(楼上的同学算错了哦)
2 用位势法检验基可行解
首先求出各行与各列的检验数
设A1行的检验数为0 由 行检验数+列检验数=运费
则检验数依次为:
行:0 3 8
列:1 2 3 2
不存在负检验数
因此已经得到最优解
不需进行迭代
所以 最小运费为454 元
貌似最小元素法有误差的吧,看书去,运筹学课本上有的
除去产量列数据和销量行数据,其余数据是对应的由Ai运送到Bj的单位运费。找初始解有一般有三种办法左上角法(或西北角法)、最小元素法和Vogl近似法(VAM)。 最小元素法就是先找到运费最小的,然后看所在列与行,将较小的值赋给它,例如本题最初选A1B1元素,运费为1,其最多能运8单位的产品到B1(B1只需要8单位),这样,把该列划去,并把第一行末的产量改为2,依次这样迭代,就能最后找到M+N+1(行数+列数-1)个初始解
运费:1×8+2×2+6×2+5×18+10×20+11×10=424
继续迭代就得看检验数了,还是去好好看书吧!