Linear Programming function

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

Linear Programming function

Post by Henko » Fri Feb 02, 2018 5:16 pm

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

Post Reply