## Linear Programming function

Henko
Posts: 793
Joined: Tue Apr 09, 2013 12:23 pm
My devices: iPhone,iPad
Windows
Location: Groningen, Netherlands
Flag:

### Linear Programming function

Linear programming is an "operations research" optimalization tool. Explanation of the purpose and application areas may be found on internet.
I will use this function in a small management game which i will upload in about a week.

Code: Select all

``````option base 1
nv=2 ! nr=3
dim profit(nv),restrict(nr,nv),rmax(nr),result(nv),leftovers(nr)
for i=1 to nv ! read profit(i) ! next i
for i=1 to nr
for j=1 to nv ! read restrict(i,j) ! next j
read rmax(i)
next i
opt=linP(nv,profit,nr,restrict,rmax,result,leftovers)
print result(1), result(2), opt
data 2,1          ' objective     z = 2*v1 + v2
data 15,5, 1200   ' constraint 15*v1 + 5*v2  <= 1200
data 5,10, 1100   ' constraint 5*v1  + 10*v2 <= 1100
data 15,10, 1500  ' constraint 15*v1 + 10*v2 <= 1500
end

' Lineair Programming function
' simple version: only "<=" constraints
' nv = # of variables
' v_coef() = coefficients in the objective function
' nres = # of contraints
' r_coef(,) = coefficients in the constraint relations
' r_max() = right hand side (max. values) of the constraints
' v_ result() = the resulting optimal variable values
' slack() = final value of the slack varables ("leftovers")
' the function returns the value of the objective function
'
def linP(nv,v_coef(),nres,r_coef(,),r_max(),v_result(),slack())
nr=nres+1 ! nc=nv+nres+1
dim w(nr,nc)
'******   initialize the simplex tableau
for j=1 to nv
w(1,j)=-v_coef(j)
for i=1 to nres ! w(i+1,j)=r_coef(i,j) ! next i
next j
for i=1 to nr
if i=1 then w(i,nc)=0 else w(i,nc)=r_max(i-1)
for j=1 to nres
if i=j+1 then w(i,nv+j)=1 else w(i,nv+j)=0
next j
next i
'******   process the tableau
do
'****   find pivot column, if any (if not, we're done)
m=0
for j=1 to nc-1
if w(1,j)<m then ! pc=j ! m=w(1,j) ! end if
next j
if m=0 then break
'****   find pivot row
m=1e10
for i=2 to nr
if w(i,pc)=0 then continue
aux=w(i,nc)/w(i,pc)
if aux>0 and aux<m then ! m=aux ! pr=i ! end if
next i
'****   optimalization step
fac=w(pr,pc)
for j=1 to nc ! w(pr,j)/=fac ! next j
for i=1 to nr
if not i=pr then
fac=w(i,pc)
for j=1 to nc ! w(i,j)-=fac*w(pr,j) ! next j
end if
next i
until forever
'******   extract the results from the tableau
profit=w(1,nc)
for j=1 to nv ! v_result(j)=0
for i=2 to nr ! if w(i,j)=1 then v_result(j)=w(i,nc) ! next i
next j
for j=1 to nres ! slack(j)=0
for i=2 to nr ! if w(i,nv+j)=1 then slack(j)=w(i,nc) ! next i
next j
return profit
end def
``````