Anonymous user
Vogel's approximation method: Difference between revisions
→{{header|Tcl}}: Added zkl
(→{{header|Tcl}}: Added zkl) |
|||
Line 689:
Y 20 30
Z 50
Total Cost = 3100
</pre>
=={{header|zkl}}==
{{trans|Python}}{{trans|Ruby}}
<lang zkl>costs :=D("W",D("A",16, "B",16, "C",13, "D",22, "E",17),
"X",D("A",14, "B",14, "C",13, "D",19, "E",15),
"Y",D("A",19, "B",19, "C",20, "D",23, "E",50),
"Z",D("A",50, "B",12, "C",50, "D",15, "E",11)).makeReadOnly();
demand:=D("A",30, "B",20, "C",70, "D",30, "E",60); // gonna be modified
supply:=D("W",50, "X",60, "Y",50, "Z",50); // gonna be modified</lang>
<lang zkl>cols :=demand.keys.sort();
res :=vogel(costs,supply,demand);
cost :=0;
println("\t",cols.concat("\t"));
foreach g in (costs.keys.sort()){
print(g,"\t");
foreach n in (cols){
y:=res[g].find(n);
if(y){ y=y[0]; print(y); cost += y*costs[g][n]; }
print("\t");
}
println();
}
println("\nTotal Cost = ",cost);</lang>
<lang zkl>fcn vogel(costs,supply,demand){
// a Dictionary can be created via a list of (k,v) pairs
res := D(costs.pump(List,fcn([(k,_)]){ return(k,D()) }));
g := D(); // cross index costs and make writable
supply.pump(Void,'wrap([(k,_)]){ g[k] =
costs[k].keys.sort('wrap(a,b){ costs[k][a]<costs[k][b] }).copy() });
demand.pump(Void,'wrap([(k,_)]){ g[k] =
costs.keys.sort('wrap(a,b){ costs[a][k]<costs[b][k] }).copy() });
while(g){
d:=D(demand.pump(List,'wrap([(k,_)]){ return(k,
g[k][0,2].apply('wrap(gk){ costs[gk][k] }).reverse().reduce('-)) }));
s:=D(supply.pump(List,'wrap([(k,_)]){ return(k,
g[k][0,2].apply('wrap(gk){ costs[k][gk] }).reverse().reduce('-)) }));
f:=(0).max(d.values); f=d.filter('wrap([(_,v)]){ v==f })[-1][0];
t:=(0).max(s.values); t=s.filter('wrap([(_,v)]){ v==t })[-1][0];
t,f=(if(d[f]>s[t]) T(f,g[f][0]) else T(g[t][0],t));
v:=supply[f].min(demand[t]);
res[f].appendV(t,v); // create t:(v) or append v to t:(...)
if(0 == (demand[t] -= v)){
supply.pump(Void,'wrap([(k,n)]){ if(n!=0) g[k].remove(t) });
g.del(t); demand.del(t);
}
if(0 == (supply[f] -= v)){
demand.pump(Void,'wrap([(k,n)]){ if(n!=0) g[k].remove(f) });
g.del(f); supply.del(f);
}
}//while
res
}</lang>
{{out}}
<pre>
A B C D E
W 50
X 10 20 20 10
Y 20 30
Z 50
Total Cost = 3100
| |||