Vogel's approximation method: Difference between revisions

;Cf.

* [[Transportation_problem|Transportation problem]]

 

=={{header|C}}==

{{trans|Kotlin}}

#include <limits.h>

 

printf("\nTotal cost = %d\n", total_cost);

return 0;

 

{{output}}

 

If the program is changed to this (to accomodate the second Ruby example):

#include <limits.h>

printf("\nTotal cost = %d\n", total_cost);

return 0;

 

then the output, which agrees with the Phix output but not with the Ruby output itself is:

=={{header|C++}}==

{{trans|Java}}

#include <numeric>

#include <vector>

 

return 0;

{{out}}

<pre>[0, 0, 50, 0, 0]

Strongly typed version (but K is not divided in Task and Contractor types to keep code simpler).

{{trans|Python}}

import std.stdio, std.string, std.algorithm, std.range;

 

}

writeln("\nTotal Cost = ", cost);

{{out}}

<pre>

=={{header|Go}}==

{{trans|Kotlin}}

 

import (

}

fmt.Println("\nTotal cost =", totalCost)

 

{{out}}

 

If the program is changed as follows to accomodate the second Ruby example:

 

import (

}

fmt.Println("\nTotal cost =", totalCost)

 

then the output, which agrees with the C and Phix output but not with the Ruby output itself, is:

Implementation:

 

:

exceeding=. 0 <. -&(+/)

end.

_1 _1 }. R

 

Note that for our penalty we are using the difference between the two smallest relevant costs multiplied by 1 larger than the highest represented cost and we subtract from that multiple the smallest relevant cost. This gives us the tiebreaker mechanism currently specified for this task.

Task example:

 

src=: 50 60 50 50

cost=: 16 16 13 22 17,14 14 13 19 15,19 19 20 23 50,:50 12 50 15 11

30 0 20 0 10

0 20 0 30 0

 

=={{header|Java}}==

{{works with|Java|8}}

import static java.util.Arrays.stream;

import java.util.concurrent.*;

return isRow ? new int[]{pm, pc, mc, md} : new int[]{pc, pm, mc, md};

}

 

<pre>[0, 0, 50, 0, 0]

 

<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.

immutable TProblem{T<:Integer,U<:String}

sd::Array{Array{T,1},1}

isavailable(r::Resource) = 0 < r.quant

Base.isless(a::Resource, b::Resource) = a.p < b.p || (a.p == b.p && b.q < a.q)

 

'''Functions'''

 

<code>vogel</code> implements Vogel's approximation method on a <code>TProblem</code>. It is somewhat straightforward, given the types and <code>penalize!</code>.

function penalize!{T<:Integer,U<:String}(sd::Array{Array{Resource{T},1},1},

tp::TProblem{T,U})

return sol

end

 

'''Main'''

 

sup = [50, 60, 50, 50]

end

println("The total cost is: ", cost)

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

val supply = intArrayOf(50, 60, 50, 50)

}

println("\nTotal Cost = $totalCost")

 

{{out}}

=={{header|Lua}}==

{{trans|Kotlin}}

local tbl = {}

for i=1,n do

end

 

{{out}}

<pre> A B C D E

Z 0 0 0 0 50

Total Cost = 3100</pre>

 

=={{header|Phix}}==

{{trans|YaBasic}}

{{trans|Go}}

{{out}}

<pre>

</pre>

Using the sample from Ruby:

{{Out}}

Note this agrees with C and Go but not Ruby

=={{header|Python}}==

{{trans|Ruby}}

 

costs = {'W': {'A': 16, 'B': 16, 'C': 13, 'D': 22, 'E': 17},

print "\t",

print

{{out}}

<pre> A B C D E

somehow at the same total cost!

 

(define-values (1st 2nd 3rd) (values first second third))

 

(DEMAND (hash 'A 30 'B 20 'C 70 'D 30 'E 60))

(SUPPLY (hash 'W 50 'X 60 'Y 50 'Z 50)))

 

{{out}}

{{trans|Sidef}}

 

:W{:16A, :16B, :13C, :22D, :17E},

:X{:14A, :14B, :13C, :19D, :15E},

print "\n";

}

{{out}}

<pre> A B C D E

{{trans|java}}

===Vogel's Approximation===

* Solve the Transportation Problem using Vogel's Approximation

Default Input

* Note: correctness of input is not checked

* 20210102 restored Vogel's Approximation and added Optimization

**********************************************************************/

Parse Arg fid

If fid='' Then

End

 

Call steppingstone

Exit

End

Parse Var in.1 numSources numDestinations . 1 rr cc .

source_sum=0

Do i=1 To numSources

Return strip(swl)

 

Parse Arg header

If header='' Then

 

steppingstone: Procedure Expose matrix. cost. rr cc matrix. demand_in.,

maxReduction=0

move=''

Parse Var matrix.r.c r c cost qrc

If qrc=0 Then Do

path=getclosedpath(r,c)

If pelems(path)<4 Then Do

End

If reduction < maxreduction Then Do

move=path

leaving=leavingCandidate

maxReduction = reduction

End

if move<>'' Then Do

quant=word(leaving,4)

If quant=0 Then Do

Parse Var m r c cpu qrc

Parse Var matrix.r.c vr vc vcost vquant

If plus Then

nquant=vquant+quant

Else

nquant=vquant-quant

matrix.r.c = vr vc vcost nquant

plus=\plus

End

move=''

Call steppingStone

End

Call show_alloc 'Optimal Solution' fid

Return

 

Parse Arg rd,cd

path=rd cd cost.rd.cd word(matrix.rd.cd,4)

Return stones(path)

 

Parse Arg list

Do Forever

list_1=remove_1(list)

If list_1=list Then Leave

list=list_1

End

Return list_1

 

Parse Arg list

cntr.=0

parse Var list e.i '|' list

Parse Var e.i r c .

End

n=i-1

Return list

 

Parse Arg lst

tstc=lst

Parse Var tstc o.i '|' tstc

end

stones=lst

o.0=i-1

prev=o.1

st.i=prev

k=i//2

Parse Var nbrs n.1 '|' n.2

If k=0 Then

stones=stones'|'st.i

End

Return stones

 

parse Arg s, lst

Do i=1 To 4

Return n

 

If (rr+cc-1)<>ms Then Do

Do r=1 To rr

Return

 

ms=0

list=''

End

Return strip(list,,'|')

 

Novalue:

Nop

End

{{out}}

<pre>F:\>regina tpv vv.txt

 

===Low Cost Algorithm===

* Solve the Transportation Problem using the Least Cost Method

Default Input

* 20201228 corresponds to NWC above

* Note: correctness of input is not checked

**********************************************************************/

Signal On Halt

Parse Arg fid

If fid='' Then

Call init

Do r=1 To rr

Do c=1 To cc

End

End

mincost=1e10

Do r=1 To rr

End

Call show_alloc 'Low Cost Algorithm'

Call steppingstone

Exit

Return

 

Parse Arg header

If header='' Then

 

steppingstone: Procedure Expose matrix. cost. rr cc matrix. demand_in.,

maxReduction=0

move=''

Parse Var matrix.r.c r c cost qrc

If qrc=0 Then Do

path=getclosedpath(r,c)

Iterate

reduction = 0

lowestQuantity = 1e10

End

If reduction < maxreduction Then Do

move=path

leaving=leavingCandidate

maxReduction = reduction

End

if move<>'' Then Do

quant=word(leaving,4)

If quant=0 Then Do

Parse Var m r c cpu qrc

Parse Var matrix.r.c vr vc vcost vquant

If plus Then

nquant=vquant+quant

Else

nquant=vquant-quant

matrix.r.c = vr vc vcost nquant

plus=\plus

End

move=''

Call steppingStone

End

Call show_alloc 'Optimal Solution' fid

Return

 

Parse Arg rd,cd

path=rd cd cost.rd.cd word(matrix.rd.cd,4)

Return stones(path)

 

Parse Arg list

Do Forever

list_1=remove_1(list)

If list_1=list Then Leave

list=list_1

End

Return list_1

 

Parse Arg list

cntr.=0

parse Var list e.i '|' list

Parse Var e.i r c .

End

n=i-1

Return list

 

Parse Arg lst

stones=lst

tstc=lst

Do i=1 By 1 While tstc<>''

Parse Var tstc o.i '|' tstc

End

o.0=i-1

prev=o.1

Return stones

 

parse Arg s, lst

Parse Var lst o.i '|' lst

End

nbrs.=''

sr=word(s,1)

End

Return n

 

fixDegenerateCase: Procedure Expose matrix. rr cc ms ms demand_in. source_in. move cnt.

If (rr+cc-1)<>ms Then Do

Do r=1 To rr

Return

 

ms=0

list=''

End

Return strip(list,,'|')

 

Novalue:

Nop

End

{{out}}

<pre>F:\>rexx tpl vv.txt

Breaks ties using lowest cost cell.

===Task Example===

#

# Nigel_Galloway

puts

end

{{out}}

<pre>

===Reference Example===

Replacing the data in the Task Example with:

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

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

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

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

Produces:

<pre>

=={{header|Sidef}}==

{{trans|Ruby}}

W => :(A => 16, B => 16, C => 13, D => 22, E => 17),

X => :(A => 14, B => 14, C => 13, D => 19, E => 15),

}

 

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

# A sort that works by sorting by an auxiliary key computed by a lambda term

}

return $res

Demonstration:

W {A 16 B 16 C 13 D 22 E 17}

X {A 14 B 14 C 13 D 19 E 15}

}] \t]

}

{{out}}

<pre>

{{libheader|Wren-math}}

{{libheader|Wren-fmt}}

 

var supply = [50, 60, 50, 50]

 

var diff = Fn.new { |j, len, isRow|

var min2 = min1

var minP = -1

 

var maxPenalty = Fn.new { |len1, len2, isRow|

var pc = -1

var pm = -1

var r = cell[0]

var c = cell[1]

demand[c] = demand[c] - q

if (demand[c] == 0) colDone[c] = true

i = i + 1

}

 

{{out}}

=={{header|Yabasic}}==

{{trans|C}}

N_ROWS = 4 : N_COLS = 5

print

next i

 

=={{header|zkl}}==

{{trans|Python}}{{trans|Ruby}}

"W",Dictionary("A",16, "B",16, "C",13, "D",22, "E",17),

"X",Dictionary("A",14, "B",14, "C",13, "D",19, "E",15),

"Z",Dictionary("A",50, "B",12, "C",50, "D",15, "E",11)).makeReadOnly();

demand:=Dictionary("A",30, "B",20, "C",70, "D",30, "E",60); // gonna be modified

res :=vogel(costs,supply,demand);

cost:=0;

println();

}

// a Dictionary can be created via a list of (k,v) pairs

res:= Dictionary(costs.pump(List,fcn([(k,_)]){ return(k,D()) }));

}//while

res

{{out}}

<pre>