Transportation problem: Difference between revisions
m
Add REXX using Vogel's Approximation
(→{{header|Julia}}: swap optimizers: GLPK for Ipopt (produces integer solutions)) |
Walterpachl (talk | contribs) m (Add REXX using Vogel's Approximation) |
||
Line 3,904:
S1 20 - 5
S2 - 30 5 </pre>
=={{header|REXX}}==
<lang rexx>/* REXX ***************************************************************
* Solve the Transportation Problem using Vogel's Approximation
**********************************************************************/
Parse Arg fid
If fid='' Then
fid='input1.txt'
Call init
r=1
c=1
m.=0
Do Forever
dmax.=0
dmax=0
Do r=1 To rr
dr.r=''
Do c=1 To cc
If cost.r.c<>'*' Then
dr.r=dr.r cost.r.c
End
dr.r=words(dr.r) dr.r
dr.r=diff(dr.r)
If dr.r>dmax Then Do; dmax=dr.r; dmax.0='R'; dmax.1=r; dmax.2=dr.r; End
End
Do c=1 To cc
dc.c=''
Do r=1 To rr
If cost.r.c<>'*' Then
dc.c=dc.c cost.r.c
End
dc.c=words(dc.c) dc.c
dc.c=diff(dc.c)
If dc.c>dmax Then Do; dmax=dc.c; dmax.0='C'; dmax.1=c; dmax.2=dc.c; End
End
Do r=1 To rr
End
Do c=1 To cc
End
cmin=999
Select
When dmax.0='R' Then Do
r=dmax.1
Do c=1 To cc
If cost.r.c<>'*' &,
cost.r.c<cmin Then Do
cmin=cost.r.c
cx=c
End
End
Call allocate r cx
End
When dmax.0='C' Then Do
c=dmax.1
Do r=1 To rr
If cost.r.c<>'*' &,
cost.r.c<cmin Then Do
cmin=cost.r.c
rx=r
End
End
Call allocate rx c
End
Otherwise
Leave
End
End
Do r=1 To rr
Do c=1 To cc
If cost.r.c<>'*' Then Do
Call allocate r c
cost.r.c='*'
End
End
End
cost=0
Say ''
Say 'Allocations'
ol=' '
Do c=1 To cc
ol=ol format(dd.c,3)
End
Say ol
Do r=1 To rr
ol=format(ss.r,4)
Do c=1 To cc
If m.r.c>0 Then Do
ol=ol format(m.r.c,3)
cost+=m.r.c*costx.r.c
End
Else
ol=ol ' - '
End
Say ol
End
Say 'Total cost' cost
Exit
allocate: Procedure Expose m. source. demand. cost. rr cc
Parse Arg r c
sh=min(source.r,demand.c)
source.r-=sh
demand.c-=sh
m.r.c=sh
If source.r=0 Then Do
Do c=1 To cc
cost.r.c='*'
End
End
If demand.c=0 Then Do
Do r=1 To rr
cost.r.c='*'
End
End
Return
diff: Procedure
Parse Value arg(1) With n list
If n<2 Then Return 0
list=wordsort(list)
Return word(list,2)-word(list,1)
init:
parse Value linein(fid) With numSources numDestinations 1 rr cc
l=linein(fid)
source_sum=0
Do i=1 To numSources
Parse Var l source.i l
ss.i=source.i
source_sum+=source.i
End
l=linein(fid)
demand_sum=0
Do i=1 To numDestinations
Parse Var l demand.i l
dd.i=demand.i
demand_sum+=demand.i
End
Do i=1 To numSources
l=linein(fid)
Do j=1 To numDestinations
Parse Var l cost.i.j l
End
End
Do i=1 To numSources
ol=format(source.i,3)
Do j=1 To numDestinations
ol=ol format(cost.i.j,4)
End
End
Select
When source_sum=demand_sum Then Nop /* balanced */
When source_sum>demand_sum Then Do /* unbalanced - add dummy demand */
cc+=1
demand.cc=source_sum-demand_sum
dd.cc=demand.cc
Do r=1 To rr
cost.r.cc=0
End
End
Otherwise /* demand_sum>source_sum */ Do /* unbalanced - add dummy source */
rr+=1
source.rr=demand_sum-source_sum
ss.rr=source.rr
Do c=1 To cc
cost.rr.c=0
End
End
End
Do r=1 To rr
Do c=1 To cc
costx.r.c=cost.r.c
End
End
Say 'Sources / Demands / Cost'
ol=' '
Do c=1 To cc
ol=ol format(demand.c,3)
End
Say ol
Do r=1 To rr
ol=format(source.r,4)
Do c=1 To cc
ol=ol format(cost.r.c,3)
End
Say ol
End
Return>(lang>
{{out}}
<pre>Sources / Demands / Cost
20 30 10
25 3 5 7
35 3 2 5
Allocations
20 30 10
25 20 - 5
35 - 30 5
Total cost 180</pre>
=={{header|SAS}}==
| |||