
 { prog.p Wed Jul 25 08:55:00 PDT 2001 }

 program glp(input,output);

  const
   epsilon = 0.0;



{ ******* math.h ******** }

  procedure plusequals(var x:integer; y:integer);
   begin
    x := x+y;
   end; {plusequals}

  procedure minusequals(var x:integer; y:integer);
   begin
    x := x-y;
   end; {minusequals}

  procedure timesequals(var x:integer; y:integer);
   begin
    x := x*y;
   end; {timesequals}

  procedure divequals(var x:integer; y:integer);
   begin
    x := x div y;
   end; {divequals}

  procedure plusequalsreal(var x:real; y:real);
   begin
    x := x+y;
   end; {plusequalsreal}

  procedure plusequalsdouble(var x:double; y:double);
   begin
    x := x+y;
   end; {plusequalsdouble}

  procedure minusequalsreal(var x:real; y:real);
   begin
    x := x-y;
   end; {minusequalsreal}

  procedure timesequalsreal(var x:real; y:real);
   begin
    x := x*y;
   end; {timesequalsreal}

  procedure divequalsreal(var x:real; y:real);
   begin
    x := x/y;
   end; {divequalsreal}

  function max2(x,y:integer):integer;
   begin
    if x >= y then max2 := x
    else max2 := y
   end; {max2}

  function max3(x,y,z:integer):integer;
   begin
    max3 := max2(x,max2(y,z))
   end; {max3}

  function ismaxof2(m,a:integer):boolean;
   begin
    ismaxof2 := m >= a
   end; {ismaxof2}

  function ismaxof3(m,a,b:integer):boolean;
   begin
    ismaxof3 := (m>=a) and (m>=b)
   end; {ismaxof3}

  function ismaxof4(m,a,b,c:integer):boolean;
   begin
    ismaxof4 := (m>=a) and (m>=b) and (m>=c)
   end; {ismaxof4}

  function ismaxof5(m,a,b,c,d:integer):boolean;
   begin
    ismaxof5 := (m>=a) and (m>=b) and (m>=c) and (m>=d)
   end; {ismaxof5}

  function ismaxof6(m,a,b,c,d,e:integer):boolean;
   begin
    ismaxof6 := (m>=a) and (m>=b) and (m>=c) and (m>=d) and (m>=e)
   end; {ismaxof6}

  procedure updateint(var x:integer; y:integer);
   begin
    if y > x then x := y
   end; {updateint}

  procedure downdateint(var x:integer; y:integer);
   begin
    if y < x then x := y
   end; {downdateint}

  procedure updatereal(var x:real; y:real);
   begin
    if y > x then x := y
   end; {updatereal}

  procedure updatedouble(var x:double; y:double);
   begin
    if y > x then x := y
   end; {updatedouble}

  procedure updatechar(var x:char; y:char);
   begin
    if y > x then x := y
   end; {updatechar}

  procedure downdatereal(var x:real; y:real);
   begin
    if y < x then x := y
   end; {downdatereal}

  function updatedreal(var x:real; y:real):boolean;
   begin
    if y > x then
     begin
      x := y;
      updatedreal := true
     end
    else
     updatedreal := false
   end; {updatedreal}

  function updateddouble(var x:double; y:double):boolean;
   begin
    if y > x then
     begin
      x := y;
      updateddouble := true
     end
    else
     updateddouble := false
   end; {updateddouble}

  function updatedrealepsilon(var x:real; y:real):boolean;
   var
    result:boolean;
   begin
    result := y > x + epsilon;
    if result then
     x := y;
    updatedrealepsilon := result
   end; {updatedrealepsilon}

  function updateddoubleepsilon(var x:double; y:double):boolean;
   var
    result:boolean;
   begin
    result := y > x + epsilon;
    if result then
     x := y;
    updateddoubleepsilon := result
   end; {updateddoubleepsilon}

  function downdatedreal(var x:real; y:real):boolean;
   begin
    if y < x then
     begin
      x := y;
      downdatedreal := true
     end
    else
     downdatedreal := false
   end; {downdatedreal}

  function min2int(x,y:integer):integer;
   begin
    if y > x then
     min2int := x
    else min2int := y
   end; {min2int}

  function min3int(x,y,z:integer):integer;
   begin
    min3int := min2int(x,min2int(y,z))
   end; {min3int}

  function min4int(x,y,z,w:integer):integer;
   begin
    min4int := min2int(x,min3int(y,z,w))
   end; {min4int}

  function min5int(x,y,z,w,u:integer):integer;
   begin
    min5int := min2int(x,min4int(y,z,w,u))
   end; {min5int}

  function min2real(x,y:real):real;
   begin
    if y > x then
     min2real := x
    else min2real := y
   end; {min2real}

  function min3real(x,y,z:real):real;
   begin
    min3real := min2real(x,min2real(y,z))
   end; {min3real}

  function min2double(x,y:double):double;
   begin
    if y > x then
     min2double := x
    else min2double := y
   end; {min2double}

  function min3double(x,y,z:double):double;
   begin
    min3double := min2double(x,min2double(y,z))
   end; {min3double}

  function max2double(x,y:double):double;
   begin
    if y < x then
     max2double := x
    else max2double := y
   end; {max2double}

  function max3double(x,y,z:double):double;
   begin
    max3double := max2double(x,max2double(y,z))
   end; {max3double}

  function max2int(x,y:integer):integer;
   begin
    if x >= y then max2int := x
    else max2int := y
   end; {max2int}

  function max3int(x,y,z:integer):integer;
   begin
    max3int := max2int(x,max2(y,z))
   end; {max3int}

  function max2real(x,y:real):real;
   begin
    if y < x then
     max2real := x
    else max2real := y
   end; {max2real}

  function max3real(x,y,z:real):real;
   begin
    max3real := max2real(x,max2real(y,z))
   end; {max3real}

  function log2(x:integer):integer;
   begin
    if x <= 1 then log2 := 0
    else log2 := 1 + log2((1+x) div 2)
   end; {log2}

  function ndigit(x,base:integer):integer;
   begin
    if x < base then ndigit := 1
    else ndigit := 1 + ndigit(x div base,base)
   end; {ndigit}

  procedure swapint(var x,y:integer);
   var
    temp:integer;
   begin
    temp := x;   
    x := y;   
    y := temp;   
   end; {swapint}

  procedure sort2(var x,y:integer);
   begin
    if x > y then swapint(x,y)
   end; {sort2}

  procedure sort3(var x,y,z:integer);
    {bubblesort}
   begin
    sort2(x,y);
    sort2(y,z);
    sort2(x,y);
   end; {sort3}

  function gcd2(x,y:integer):integer;
   begin
    {writeln('computing gcd2(',x:0,',',y:0,')');}
    if x < 0 then gcd2 := gcd2(-x,y)
    else if y < 0 then gcd2 := gcd2(x,-y)
    else if x = 0 then gcd2 := y
    else if y = 0 then gcd2 := x
    else if x <= y then gcd2 := gcd2(y mod x, x)
    else gcd2 := gcd2(y,x)
   end; {gcd2}

  function gcd3(x,y,z:integer):integer;
   begin
    gcd3 := gcd2(gcd2(x,y),z)
   end; {gcd3}

  function rnd(x:real):integer;
    {round to the nearest integer}
   begin
    if x >= 0 then
     if x < 0.5 then rnd := 0
     else rnd := trunc(x+0.5)
    else rnd := -rnd(-x)
   end; {rnd}

  function vec4intequal(a0,b0,c0,d0,a1,b1,c1,d1:integer):boolean;
   begin
    vec4intequal := (a0=a1)and(b0=b1)and(c0=c1)and(d0=d1)
   end; {vec4intequal}

  function vec4intless(a0,b0,c0,d0,a1,b1,c1,d1:integer):boolean;
   begin
    if a0<>a1 then vec4intless := a0<a1
    else if b0<>b1 then vec4intless := b0<b1
    else if c0<>c1 then vec4intless := c0<c1
    else vec4intless := d0<d1
   end; {vec4intless}



 { consttypes Thu Jul 26 03:55:11 PDT 2001 }

  const
   default = -2;
   nvarmax = 50;
   nconstraintmax = 8;
   sentinel = -1;
   maxcounter = 100;

  type
   boolvec = array[0..nvarmax] of boolean;
   doublevec = array[0..nvarmax] of double;
   equation =
    record
     leader:integer; { leader in [1..nvar], not basic[leader] }
     coefvec:doublevec; { coefvec[0] >= 0, coefvec[leader] = -1 }
    end; {constraint}
   tableau =
    record
     nvar,nconstraint:integer;
     constraint:array[-3..nconstraintmax]of equation; 
     basic:boolvec;
     pleader:array[0..nconstraintmax]of integer;
     varname:array[-3..nvarmax]of name;
     optimal:doublevec;{array[-3..nvarmax]of double;}
    end; {tableau}


 { pivot Fri Jul 27 04:09:42 PDT 2001 }

  procedure badpivot;
   begin
    writeln('badpivot');
    halt
   end; {badpivot}

  procedure unboundedhalt;
   begin
    writeln('unboundedhalt');
    halt
   end; {unboundedhalt}

  function alertnegative(x:double):double;
   begin
    if x >= 0 then alertnegative := x
    else
     begin
      if printalertnegative then writeln('alertnegative: ',x);
      alertnegative := 0.0
     end
   end; {alertnegative}

  procedure onepivot(nvar:integer; var pivrow,otherrow:equation);
   var
    pivi,i:integer;
    factor:double;
   begin
    {writeln('Entering onepivot: nvar = ',nvar:0);}
    pivi := pivrow.leader;
{writeln('pivi = ',pivi:0);}
    if otherrow.coefvec[pivi] <> 0 then
     begin
      factor := otherrow.coefvec[pivi];
{writeln('Factor = ',factor:8:5);}
      if otherrow.leader = 1 then {1 is the column for the objective}
       otherrow.coefvec[0] :=
        otherrow.coefvec[0] + factor*pivrow.coefvec[0]
      else
       otherrow.coefvec[0] :=
        alertnegative(otherrow.coefvec[0] + factor*pivrow.coefvec[0]);
      for i := 1 to nvar do {Could this be the error?}
       otherrow.coefvec[i] := otherrow.coefvec[i] + factor*pivrow.coefvec[i];
      otherrow.coefvec[pivi] := 0;
     end
   end; {onepivot}

  procedure pivotentry(var t:tableau; pivi, pivj:integer);
   var
    i,j:integer;
    factor:double;
   begin
    factor := t.constraint[pivj].coefvec[pivi];
    if factor >= 0 then badpivot
    else
     begin
      for i := 0 to t.nvar do
       t.constraint[pivj].coefvec[i] :=
        - t.constraint[pivj].coefvec[i]/factor;
      t.basic[t.constraint[pivj].leader] := true;
      t.basic[pivi] := false;
      t.constraint[pivj].leader := pivi;
      t.pleader[pivi] := pivj;
if printout then
      writeln('Pivot entry: variable ',pivi:0,' constraint ',pivj:0);
      for j := 0 to t.nconstraint do if j <> pivj then
{begin}
{writeln('Onepivot pivj = ',pivj:0,' j = ',j:0);}
       onepivot(t.nvar,t.constraint[pivj],t.constraint[j]);
{end;}
{begin temporary
    writeln('The sum of the Lambdas is ',optimalsum(t,11,t.nvar):12:9);
    for i := 1 to t.nvar do write(ord(t.basic[i]):1); writeln;
    for i := 0 to t.nvar do
     begin
      writefixlenname(t.varname[i],shortnamelen);
      write(': ');
      for j := 0 to t.nconstraint do
       write(t.constraint[j].coefvec[i]:6:2);
      writeln
     end;
end temporary}
    {displaytableau(t);}
     end
   end; {pivotentry}

  procedure pivotcolumn(var t:tableau; pivi:integer);
    {input condition: t.}
   var
    i,pivj,j:integer;
    ratio,minratio,pivotvalue:double;
    unbounded:boolean;
   begin
if printout then
    writeln('Attempting to pivot on variable ',pivi:0);
    unbounded := true;
    for j := 1 to t.nconstraint do
     with t.constraint[j] do
      if coefvec[pivi] < -epsilon then
       if unbounded then
        begin
         unbounded := false;
         pivj := j;
         pivotvalue := coefvec[pivi];
         minratio := - coefvec[0]/coefvec[pivi]
        end
       else
        begin
         ratio := - coefvec[0]/coefvec[pivi];
         if (ratio < minratio) then
          begin
           minratio := ratio;
           pivj := j
          end
        end; {if not unbounded, the correct value of pivj is found}
    if unbounded then
     begin
      writeln('Unbounded: here is the tableau');
      for i := 1 to t.nvar do write(ord(t.basic[i]):1); writeln;
      for i := 0 to t.nvar do
       begin
        writefixlenname(t.varname[i],shortnamelen);
        write(': ');
        for j := 0 to t.nconstraint do
         write(t.constraint[j].coefvec[i]:6:2);
        writeln
       end;
      writeln('Attempting to pivot on variable ',pivi:0);
      unboundedhalt
     end
    else
     pivotentry(t,pivi,pivj)
   end; {pivotcolumn}


  { names Fri Aug 31 02:27:29 PDT 2001 }

  const
   maxnamelen = 30;
   shortnamelen = 10;
   blank = ' ';
   tab = '	';

  type
   maxstring = array[1..maxnamelen]of char;
   shortstring = array[1..shortnamelen]of char;
   name =
    record
     symbol:maxstring;
     length:integer;
    end; {name}

  procedure maxname(var x:name; s:maxstring);
   var
    i,j:integer;
    unfinished:boolean;
   begin
    j := 0;
    for i := 1 to maxnamelen do
     if not (s[i] in [blank,tab]) then j := i;
    x.length := j;
    for i := 1 to maxnamelen do
     if i <= j then
      x.symbol[i] := s[i]
     else
      x.symbol[i] := blank
   end; {maxname}

  procedure shortname(var x:name; s:shortstring);
   var
    i,j:integer;
    unfinished:boolean;
   begin
    j := 0;
    for i := 1 to shortnamelen do
     if not (s[i] in [blank,tab]) then j := i;
    x.length := j;
    for i := 1 to maxnamelen do
     if i <= j then
      x.symbol[i] := s[i]
     else
      x.symbol[i] := blank
   end; {shortname}

  procedure badtag;
   begin
    writeln('badtag');
    halt
   end; {badtag}

  procedure appendtag(var x:name; n,w:integer);
   { appends a w-digit numeral for n after x }
   const
    decimalbase = 10;
    base = 10;
   function digit(d:integer):char;
    begin
     if d < decimalbase then digit := char(ord('0')+d)
     else digit := char(ord('A')+d-decimalbase)
    end; {digit}
   begin
{writeln('Appendtag: x.length = ',x.length:0,' n = ',n:0,' w = ',w:0);}
    if (n < 0) or (w < 0) then badtag;
    if (w = 0) and (n > 0) then badtag;
    if w+x.length > maxnamelen then badtag;
    if w > 0 then
     begin
      appendtag(x,n div base,w-1);
      plusequals(x.length,1);
      x.symbol[x.length] := digit(n mod base);
     end
   end; {appendtag}

  procedure shortnametag(var x:name; s:shortstring; n,w:integer);
   begin
    shortname(x,s);
    appendtag(x,n,w)
   end; {shortnametag}

  procedure writename(var x:name);
   var
    i:integer;
   begin
    for i := 1 to x.length do
     write(x.symbol[i])
   end; {writename}

  procedure writefixlenname(var x:name; fixlen:integer);
   var
    i:integer;
   begin
    for i := 1 to fixlen do
     if i <= x.length then
      write(x.symbol[i])
     else write(blank)
   end; {writename}

  procedure writequotedname(var x:name);
   begin
    write('"');
    writename(x);
    write('"')
   end; {writequotedname}

  procedure writelnquotedname(var x:name);
   begin
    write('"');
    writename(x);
    writeln('"');
   end; {writelnquotedname}

  procedure writelnname(var x:name);
   begin
    writename(x);
    writeln
   end; {writelnname}

  procedure readname(var x:name);
    {reads alphanumeric, dash, and underscore as part of name}
    {ignores leading blanks and tabs}
    {destroys first other input symbol after the name}
    {automatic stop at eoln}
    {truncates to maxnamelen characters}
    {length may be zero}
   var
    i:integer;
    c:char;
    reading:boolean;
   begin
    reading := true;
    i := 0;
    while not eoln and reading do
     begin
      read(c);
      if c in ['A'..'Z','a'..'z','0'..'9','-','_'] then
       if i < maxnamelen then 
        begin
         i := i+1;
         x.symbol[i] := c
        end
       else
      else if (i = 0) and (c in [blank,tab]) then
      else reading := false
     end;
    x.length := i
   end; {readname}

  function nameshortequals(var x:name; s:shortstring):boolean;
   var
    i:integer;
    result:boolean;
   begin
    result := true;
    for i := 1 to shortnamelen do
     if x.symbol[i] <> s[i] then result := false;
    nameshortequals := result;
   end; {nameshortequals}


  { outputs Tue Aug  7 02:40:10 PDT 2001 }
  { displaynzoptimal augmented Sat Sep  8 06:09:59 PDT 2001 }

  procedure olddisplayoptimal(var t:tableau);
   var
    j:integer;
   begin
    writeln('optimal value of objective = ',
             t.constraint[0].coefvec[0]:12:9);
    for j := 1 to t.nconstraint do
     writeln('variable ',t.constraint[j].leader:0,' is ',
             t.constraint[j].coefvec[0]:12:9);
    writeln('All other variables are basic')
   end; {olddisplayoptimal}

  procedure displayoptimal(var t:tableau);
   var
    i,j:integer;
   begin
    writeln('Solution');
    for i := 1 to t.nvar do
     begin
      j := t.pleader[i];
      write(i:2,' ');
      writefixlenname(t.varname[i],shortnamelen);
      write(' = ');
      writeln(t.optimal[i]:12:9);
     end
   end; {displayoptimal}

  procedure displaynzoptimal(var t:tableau);
   var
    i:integer;
   begin
    writeln('Solution: only nonzero values');
    {for i := 1 to t.nvar do if (i = 1) or (t.optimal[i] > 0) then}
    for i := 1 to t.nvar do if not t.basic[i] then
     begin
      write(i:2,' ');
      writefixlenname(t.varname[i],shortnamelen);
      write(' = ');
      writeln(t.optimal[i]:12:9);
     end;
    write('Positive:');
    for i := 2 to t.nvar do if t.optimal[i] > 0 then
     begin
      write(' ');
      writename(t.varname[i]);
     end;
    writeln;
   end; {displaynzoptimal}

  procedure dependencies(var t:tableau);
   const
    overheadindices = 10;
   var
    i:integer;
   begin
    writename(t.varname[1]);
    write(' from ');
    for i := overheadindices+1 to t.nvar do
     if t.optimal[i] > 0 then
     begin
      writename(t.varname[i]);
      write('  ');
     end;
    writeln;
   end; {dependencies}

  procedure displaytableau(var t:tableau);
   var
    i,j:integer;
   begin
writeln('nvar = ',t.nvar:0);
    for i := 1 to t.nvar do write(ord(t.basic[i]):1); writeln;
    shortname(t.varname[0],'wascorrupt');
    for i := 0 to t.nvar do
     begin
write(i:2,': ');
      writefixlenname(t.varname[i],shortnamelen);
      write(': ');
      for j := 0 to t.nconstraint do
       write(' ',t.constraint[j].coefvec[i]:5:2);
      writeln
     end
   end; {displaytableau}



  { inputs Mon Aug  6 04:06:48 PDT 2001 }

  procedure badinput;
   begin
    writeln('badinput');
    halt
   end; {badinput}

  procedure checkleaders(var t:tableau);
   var
    i,j:integer;
   begin
{
    for i := 1 to t.nvar do write(ord(t.basic[i]):1); writeln;
    for i := 0 to t.nvar do
     begin
      writefixlenname(t.varname[i],shortnamelen);
      write(': ');
      for j := 0 to t.nconstraint do
       write(t.constraint[j].coefvec[i]:6:2);
      writeln
     end;
}
    for i := 1 to t.nvar do t.pleader[i] := sentinel;
    for j := 0 to t.nconstraint do
     for i := 1 to t.nvar do if not t.basic[i] then
      if t.constraint[j].coefvec[i] = -1 then
       begin
        t.pleader[i] := j;
        t.constraint[j].leader := i;
       end;
{
    for j := 0 to t.nconstraint do write(t.constraint[j].leader:4); writeln;
    write('  ');
    for i := 1 to t.nvar do write(t.pleader[i]:2); writeln;
}
    for i := 1 to t.nvar do if not t.basic[i] then
     if t.constraint[t.pleader[i]].leader <> i then
begin
writeln('i = ',i:0);
writeln('j = ',j:0);
writeln('t.pleader[i] = ',t.pleader[i]:0);
writeln('t.constraint[t.pleader[i]].leader = ',
t.constraint[t.pleader[i]].leader:0);
      badinput;
end;
    for j := 0 to t.nconstraint do
     if t.pleader[t.constraint[j].leader] <> j then badinput;
    for j := 0 to t.nconstraint do
     if t.constraint[j].coefvec[t.constraint[j].leader] <> -1 then badinput;
    for i := 1 to t.nvar do if not t.basic[i] then
     for j := 0 to t.nconstraint do
      if (i <> t.constraint[j].leader) and
         (t.constraint[j].coefvec[i] <> 0) then badinput;
{writeln('End checkleaders');}
   end; {checkleaders}

  procedure readtableau( var t:tableau);
   var
    i,j:integer;
    b:char;
   begin
    for i := 1 to nvarmax do t.basic[i] := false;
    for j := 0 to t.nconstraint do
     for i := 1 to nvarmax do t.constraint[j].coefvec[i] := default;
    readln(t.nvar,t.nconstraint);
{   writeln('nvar = ',t.nvar:0,' nconstraint = ',t.nconstraint:0);}
    if (t.nvar>nvarmax)or(t.nconstraint>nconstraintmax) then badinput;
    for i := 1 to t.nvar do
     begin read(b); t.basic[i] := b = '1' end;
    readln;
    for i := 0 to t.nvar do
     begin
      readname(t.varname[i]);
      for j := 0 to t.nconstraint do
       read(t.constraint[j].coefvec[i]);
      readln
     end;
    checkleaders(t);
{writeln('nvar = ',t.nvar:0,' nconstraint = ',t.nconstraint:0);flush(output);}
{writeln('End readtableau');}
   end; {readtableau}
    


  { minmax Sat Aug 11 04:11:51 PDT 2001 }

  function canpivot(var t:tableau; var pivi:integer):boolean;
   var
    i:integer;
    maxpos:double;
   begin
    pivi := 0;
    maxpos := 0;
    for i := 2 to t.nvar do
     if t.basic[i] then
      if t.constraint[0].coefvec[i] > maxpos then
       begin
        pivi := i;
        maxpos := t.constraint[0].coefvec[i]
       end;
    canpivot := (pivi >= 2) and (pivi <= t.nvar)
   end; {canpivot}

  procedure maximize(var t:tableau);
   var
    i,pivi,counter:integer;
   begin
    counter := 0;
if printout then
      displaytableau(t);
    while canpivot(t,pivi) do
     begin
      counter := counter+1;
if printout then
      writeln('Pivot ',counter:0);
      pivotcolumn(t,pivi);
      checkleaders(t);
if printout then
      displaytableau(t);
     end;
    for i := 1 to t.nvar do
     t.optimal[i] := 0;
    for i :=  0 to t.nconstraint do
     t.optimal[t.constraint[i].leader] := t.constraint[i].coefvec[0]
   end; {maximize}

  function maximum(var t:tableau):double;
   begin
    maximize(t);
    maximum := t.optimal[1]
   end; {maximum}



 { testers Thu Jul 26 06:03:42 PDT 2001 }

  procedure tester1;
   var
    t:tableau;
   begin
    readtableau(t);
    maximize(t);
    checkleaders(t);
    displayoptimal(t);
   end; {tester1}
  
  procedure tester2;
   var
    x:name;
   begin
    shortname(x,'hello     ');
    writequotedname(x);writeln;
    maxname(x,'abcdefghijklmnopqrstuvwxyz    ');
    writequotedname(x);writeln;
   end;

  begin
   tester1;
  end.

