Vogel's approximation method: Difference between revisions

Line 482:

until g.empty?

d = demand~~.each~~.collect{|x,y| [x, z = COSTS[g[x][0]][x], g[x][1] ? COSTS[g[x][1]][x] - z : z]}

d = demand.collect{|x,y| [x, z = COSTS[g[x][0]][x], g[x][1] ? COSTS[g[x][1]][x] - z : z]}

dmax = d.max_by{|n| n[2]}

d = d.select{|x| x[2] == dmax[2]}.min_by{|n| n[1]}

s = supply~~.each~~.collect{|x,y| [x, z = COSTS[x][g[x][0]], g[x][1] ? COSTS[x][g[x][1]] - z : z]}

s = supply.collect{|x,y| [x, z = COSTS[x][g[x][0]], g[x][1] ? COSTS[x][g[x][1]] - z : z]}

dmax = s.max_by{|n| n[2]}

s = s.select{|x| x[2] == dmax[2]}.min_by{|n| n[1]}

t,f = d[2]==s[2] ? [s[1], d[1]] : [d[2],s[2]]

d,s = t > f ? [d[0],g[d[0]][0]] : [g[s[0]][0],s[0]]

v = [supply[s], demand[d]].min

res[s][d] += v

demand[d] -= v

if demand[d] == 0 then

supply.reject{|k, n| n == 0}.each_key{|x| g[x].delete(d)}

g.delete(d)

demand.delete(d)

end

supply[s] -= v

if supply[s] == 0 then

demand.reject{|k, n| n == 0}.each_key{|x| g[x].delete(s)}

g.delete(s)

supply.delete(s)

end

COLS.each{|n| print "\t", n}

puts

⚫

print "\n"

cost = 0

COSTS.each_key{|g| ~~print g, "\t"~~

COSTS.each_key do |g|

⚫

print g, "\t"

COLS.each{|n| y = res[g][n]

COLS.each do |n|

⚫

print y if y != 0

~~cost +~~= ~~y * COSTS~~[g][n]

y = res[g][n]

⚫

print y if y != 0

print "\t"

}

cost += y * COSTS[g][n]

print "\n"

print "\t"

end

}

puts

end

print "\n\nTotal Cost = ", cost</lang>

Line 532:

Line 534:

===Reference Example===

Replacing the data in the Task Example with:

⚫

<lang ruby>COSTS = {S1: {D1: 46, D2: 74, D3: 9, D4: 28, D5: 99},

⚫

COSTS = {S1: {D1: 46, D2: 74, D3: 9, D4: 28, D5: 99},

S2: {D1: 12, D2: 75, D3: 6, D4: 36, D5: 48},

S3: {D1: 35, D2: 199, D3: 4, D4: 5, D5: 71},

Line 539:

Line 540:

S5: {D1: 85, D2: 60, D3: 14, D4: 25, D5: 79}}

demand = {D1: 278, D2: 60, D3: 461, D4: 116, D5: 1060}

supply = {S1: 461, S2: 277, S3: 356, S4: 488, S5: 393}

supply = {S1: 461, S2: 277, S3: 356, S4: 488, S5: 393}</lang>

</lang>

Produces:

<pre>