Vogel's approximation method: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 73:
;Cf.
* [[Transportation_problem|Transportation problem]]
=={{header|11l}}==
{{trans|Python}}
<lang 11l>V costs = [‘W’ = [‘A’ = 16, ‘B’ = 16, ‘C’ = 13, ‘D’ = 22, ‘E’ = 17],
‘X’ = [‘A’ = 14, ‘B’ = 14, ‘C’ = 13, ‘D’ = 19, ‘E’ = 15],
‘Y’ = [‘A’ = 19, ‘B’ = 19, ‘C’ = 20, ‘D’ = 23, ‘E’ = 50],
‘Z’ = [‘A’ = 50, ‘B’ = 12, ‘C’ = 50, ‘D’ = 15, ‘E’ = 11]]
V demand = [‘A’ = 30, ‘B’ = 20, ‘C’ = 70, ‘D’ = 30, ‘E’ = 60]
V cols = sorted(demand.keys())
V supply = [‘W’ = 50, ‘X’ = 60, ‘Y’ = 50, ‘Z’ = 50]
V res = Dict(costs.keys().map(k -> (k, DefaultDict[Char, Int]())))
[Char = [Char]] g
L(x) supply.keys()
g[x] = sorted(costs[x].keys(), key' g -> :costs[@x][g])
L(x) demand.keys()
g[x] = sorted(costs.keys(), key' g -> :costs[g][@x])
L !g.empty
[Char = Int] d
L(x) demand.keys()
d[x] = I g[x].len > 1 {(costs[g[x][1]][x] - costs[g[x][0]][x])} E costs[g[x][0]][x]
[Char = Int] s
L(x) supply.keys()
s[x] = I g[x].len > 1 {(costs[x][g[x][1]] - costs[x][g[x][0]])} E costs[x][g[x][0]]
V f = max(d.keys(), key' n -> @d[n])
V t = max(s.keys(), key' n -> @s[n])
(t, f) = I d[f] > s[t] {(f, g[f][0])} E (g[t][0], t)
V v = min(supply[f], demand[t])
res[f][t] += v
demand[t] -= v
I demand[t] == 0
L(k, n) supply
I n != 0
g[k].remove(t)
g.pop(t)
demand.pop(t)
supply[f] -= v
I supply[f] == 0
L(k, n) demand
I n != 0
g[k].remove(f)
g.pop(f)
supply.pop(f)
L(n) cols
print("\t "n, end' ‘ ’)
print()
V cost = 0
L(g) sorted(costs.keys())
print(g" \t", end' ‘ ’)
L(n) cols
V y = res[g][n]
I y != 0
print(y, end' ‘ ’)
cost += y * costs[g][n]
print("\t", end' ‘ ’)
print()
print("\n\nTotal Cost = "cost)</lang>
{{out}}
<pre>
A B C D E
W 50
X 20 40
Y 30 20
Z 30 20
Total Cost = 3130
</pre>
=={{header|C}}==
| |||