Vogel's approximation method: Difference between revisions
Content added Content deleted
m (Explain tiebreaker on penalty) |
(→{{header|Julia}}: A new entry for Julia) |
||
Line 319: | Line 319: | ||
[0, 0, 0, 0, 50] |
[0, 0, 0, 0, 50] |
||
Total cost: 3100</pre> |
Total cost: 3100</pre> |
||
=={{header|Julia}}== |
|||
This solution is designed to scale well to large numbers of suppliers and customers. The opportunity cost matrix is sorted only once, and penalties are recalculated only when the relevant resources are exhausted. The solution is stored in a [http://docs.julialang.org/en/release-0.3/manual/arrays/#sparse-matrices sparse matrix], because the number of components to a solution is less than s+c (suppliers + customers) but the size of the matrix is s*c. |
|||
This solution does not impose the requirement that the problem be balanced. <code>vogel</code> will iterate until either supply or demand is exhausted and provide a low-cost result even when the problem is unbalanced, whether this result is a good solution is left for the user to decide. The function <code>isbalanced</code> can be used to test whether a give problem is balanced. |
|||
'''Types''' |
|||
The immutable type <code>TProblem</code> stores the problem's parameters. It includes permutation matrices that allow the rows and columns of the total opportunity cost matrix to be sorted as needed. |
|||
<code>Resource</code> stores the currently available quantity of a given supply or demand as well as its penalty, cost, and some meta-data. <code>isavailable</code> indicates whether any of the given resource remains. <code>isless</code> is designed to make the currently most usable resource appear as a maximum compared to other resources. |
|||
<lang Julia> |
|||
immutable TProblem{T<:Integer,U<:String} |
|||
sd::Array{Array{T,1},1} |
|||
toc::Array{T,2} |
|||
labels::Array{Array{U,1},1} |
|||
tsort::Array{Array{T,2}, 1} |
|||
end |
|||
function TProblem{T<:Integer,U<:String}(s::Array{T,1}, |
|||
d::Array{T,1}, |
|||
toc::Array{T,2}, |
|||
slab::Array{U,1}, |
|||
dlab::Array{U,1}) |
|||
scnt = length(s) |
|||
dcnt = length(d) |
|||
size(toc) = (scnt,dcnt) || error("Supply, Demand, TOC Size Mismatch") |
|||
length(slab) == scnt || error("Supply Label Size Labels") |
|||
length(dlab) == dcnt || error("Demand Label Size Labels") |
|||
0 <= minimum(s) || error("Negative Supply Value") |
|||
0 <= minimum(d) || error("Negative Demand Value") |
|||
sd = Array{T,1}[] |
|||
push!(sd, s) |
|||
push!(sd, d) |
|||
labels = Array{U,1}[] |
|||
push!(labels, slab) |
|||
push!(labels, dlab) |
|||
tsort = Array{T,2}[] |
|||
push!(tsort, mapslices(sortperm, toc, 2)) |
|||
push!(tsort, mapslices(sortperm, toc, 1)) |
|||
TProblem(sd, toc, labels, tsort) |
|||
end |
|||
isbalanced(tp::TProblem) = sum(tp.sd[1]) == sum(tp.sd[2]) |
|||
type Resource{T<:Integer} |
|||
dim::T |
|||
i::T |
|||
quant::T |
|||
l::T |
|||
m::T |
|||
p::T |
|||
q::T |
|||
end |
|||
function Resource{T<:Integer}(dim::T, i::T, quant::T) |
|||
zed = zero(T) |
|||
Resource(dim, i, quant, zed, zed, zed, zed) |
|||
end |
|||
isavailable(r::Resource) = 0 < r.quant |
|||
Base.isless(a::Resource, b::Resource) = a.p < b.p || (a.p == b.p && b.q < a.q) |
|||
</lang> |
|||
'''Functions''' |
|||
<code>penalize!</code> updates the penalty, cost and some meta-data of lists of supplies and demands. It short-circuits to avoid recalculating these values when the relevant resources remain available. Sorting is provided by the permutation matrices in <code>TProblem</code>. |
|||
<code>vogel</code> implements Vogel's approximation method on a <code>TProblem</code>. It is somewhat straightforward, given the types and <code>penalize!</code>. |
|||
<lang Julia> |
|||
function penalize!{T<:Integer,U<:String}(sd::Array{Array{Resource{T},1},1}, |
|||
tp::TProblem{T,U}) |
|||
avail = BitArray{1}[] |
|||
for dim in 2:-1:1 |
|||
push!(avail, bitpack(map(isavailable, sd[dim]))) |
|||
end |
|||
for dim in 1:2, r in sd[dim] |
|||
if r.quant == 0 |
|||
r.l = r.m = r.p = r.q = 0 |
|||
continue |
|||
end |
|||
r.l == 0 || !avail[dim][r.l] || !avail[dim][r.m] || continue |
|||
rsort = filter(x->avail[dim][x], vec(slicedim(tp.tsort[dim],dim,r.i))) |
|||
rcost = vec(slicedim(tp.toc, dim, r.i))[rsort] |
|||
if length(rsort) == 1 |
|||
r.l = r.m = rsort[1] |
|||
r.p = r.q = rcost[1] |
|||
else |
|||
r.l, r.m = rsort[1:2] |
|||
r.p = rcost[2] - rcost[1] |
|||
r.q = rcost[1] |
|||
end |
|||
end |
|||
nothing |
|||
end |
|||
function vogel{T<:Integer,U<:String}(tp::TProblem{T,U}) |
|||
sdcnt = collect(size(tp.toc)) |
|||
sol = spzeros(T, sdcnt[1], sdcnt[2]) |
|||
sd = Array{Resource{T},1}[] |
|||
for dim in 1:2 |
|||
push!(sd, [Resource(dim, i, tp.sd[dim][i]) for i in 1:sdcnt[dim]]) |
|||
end |
|||
while any(map(isavailable, sd[1])) && any(map(isavailable, sd[2])) |
|||
penalize!(sd, tp) |
|||
a = maximum([sd[1], sd[2]]) |
|||
b = sd[rem1(a.dim+1,2)][a.l] |
|||
if a.dim == 2 # swap to make a supply and b demand |
|||
a, b = b, a |
|||
end |
|||
expend = min(a.quant, b.quant) |
|||
sol[a.i, b.i] = expend |
|||
a.quant -= expend |
|||
b.quant -= expend |
|||
end |
|||
return sol |
|||
end |
|||
</lang> |
|||
'''Main''' |
|||
<lang Julia> |
|||
sup = [50, 60, 50, 50] |
|||
slab = ["W", "X", "Y", "Z"] |
|||
dem = [30, 20, 70, 30, 60] |
|||
dlab = ["A", "B", "C", "D", "E"] |
|||
c = [16 16 13 22 17; |
|||
14 14 13 19 15; |
|||
19 19 20 23 50; |
|||
50 12 50 15 11] |
|||
tp = TProblem(sup, dem, c, slab, dlab) |
|||
sol = vogel(tp) |
|||
cost = sum(tp.toc .* sol) |
|||
println("The solution is:") |
|||
print(" ") |
|||
for s in tp.labels[2] |
|||
print(@sprintf "%4s" s) |
|||
end |
|||
println() |
|||
for i in 1:size(tp.toc)[1] |
|||
print(@sprintf " %4s" tp.labels[1][i]) |
|||
for j in 1:size(tp.toc)[2] |
|||
print(@sprintf "%4d" sol[i,j]) |
|||
end |
|||
println() |
|||
end |
|||
println("The total cost is: ", cost) |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
The solution is: |
|||
A B C D E |
|||
W 0 0 50 0 0 |
|||
X 10 20 20 0 10 |
|||
Y 20 0 0 30 0 |
|||
Z 0 0 0 0 50 |
|||
The total cost is: 3100 |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |