reduce-historical/r35/xlog/linineq.log

Codemist Standard Lisp 3.54 for DEC Alpha: May 23 1994
Dump file created: Mon May 23 10:39:11 1994
REDUCE 3.5, 15-Oct-93 ...
Memory allocation: 6023424 bytes

+++ About to read file tstlib.red


% Examples taken from G.B. Dantzig.

lll := {x1 >= 0,
        x1+2x2  <= 6,
        x1 + x2 >= 2,
        x1 - x2 >= 3,
             x2 >= 0,
      -2 x1 -x2 <= z };


lll := {x1>=0,

        x1 + 2*x2<=6,

        x1 + x2>=2,

        x1 - x2>=3,

        x2>=0,

         - 2*x1 - x2<=z}


sol := linineq(lll,{x1,x2,z=min});


sol := {x1=6,x2=0,z=-12}


sol := linineq(lll,{x1,x2,z=min},record=t);


                    - x2 - z
sol := {{x1=6,max(-----------,x2 + 3, - x2 + 2,0), - 2*x2 + 6},
                       2

                     z + 12
        {x2=0,0,min(--------,1)},
                       3

        {z=-12,-12,inf}}


linineq({z =  x1 + 2 x2 + 3 x3 + 4 x4,
         4 =  x1 +   x2 +   x3 +   x4,
        -2 =  x1 - 2 x2 + 3 x3 - 4 x4,
         x1>=0, x2>=0, x3>=0,x4>=0},  {z=min});


{x4=0,x3=0,x2=2,x1=2,z=6}


linineq({z =  x1 + 2 x2 + 3 x3 + 4 x4,
         4 =  x1 +   x2 +   x3 +   x4,
        -2 =  x1 - 2 x2 + 3 x3 - 4 x4,
         x1>=0, x2>=0, x3>=0,x4>=0},  {z=max});


{x4=2,x3=2,x2=0,x1=0,z=14}


linineq({ x1  +   x2 >= 1,
          x1  +   x2 <= 2,
          x1  -   x2 <= 1,
          x1  -   x2 >=-1,
                 -x2  =z } , {z=min});


     3      1      - 3
{x2=---,x1=---,z=------}
     2      2      2


linineq({ 5x1 - 4x2 + 13x3 - 2x4 +  x5 = 20,
           x1 -  x2 +  5x3 -  x4 +  x5 = 8,
           x1 + 6x2 -  7x3 +  x4 + 5x5 = z,
           x1>=0,x2>=0,x3>=0,x4>=0,x5>=0},  {z=min});


               12      4           - 60
{x5=0,x4=0,x3=----,x2=---,x1=0,z=-------}
               7       7            7



% Examples for integer and mixed integer linear programming
%   (Beightler, Phillips, Wilde,  pp. 142 ff)

linineq({z= 3x1  +   2x2,
           5x1   +   4x2  <= 23.7,
                    x1            >= 0,
                                  x2  >= 0},
                {z=max},
                int={x1,x2});


{x2=2,x1=3,z=13}


linineq({z=  x1  +    x2,
          -2x1   +   5x2  <= 8, 
                   6x1   +    x2  <= 30,
                    x1            >= 0,
                                  x2  >= 0},
                {z=max},
                int={x1,x2});


{x2=3,x1=4,z=7}


linineq({z=-7x1  + 106x2,
           -x1   +  15x2  <= 90,
                    x1   +   2x2  <= 35,
                  -3x1   +   4x2  <= 12,
                    x1            >= 0,
                                  x2  >= 0},
                {z=max},
                int={x1,x2});


{x2=7,x1=15,z=637}


linineq({z=9x1 + 6x2 + 5x3,
           2x1 + 3x2 + 7x3 <= 35/2,
                   4x1       + 9x3 <= 15,
                    x1             >= 0,
                        x2             >= 0,
                        x3             >= 0},
                {z=max},
                int={x1});


          23
{x3=0,x2=----,x1=3,z=50}
          6


% a case where the extremum requirement cannot be resolved
sol := linineq(lll,{x1,x2,z=max});


sol := {}


% print the selection from the intervals:

on prlinineq;


sol := linineq(lll,{x1,x2,z=min});

variables:(x1 x2 z)

          - 12 <= z <= inf;    minimum: z=-12

         0 <= x2 <= 0;    zero length interval: x2=0

         6 <= x1 <= 6;    zero length interval: x1=6

sol := {x1=6,x2=0,z=-12}

sol := linineq(lll,{x1,x2,z=max});

variables:(x1 x2 z)

          - 12 <= z <= inf;    max/min cannot be resolved

sol := {}


% print the full elimination process

on trlinineq;


sol := linineq(lll,{x1,x2,z=min});

variables:(x1 x2 z)
--------------------------------
next variable:x1; initial system:
{z>= - 2*x1 - x2,

 x2>=0,

 x1 - x2>=3,

 x1 + x2>=2,

 6>=x1 + 2*x2,

 x1>=0}
--------------------------------
normalized and reduced:
{x1>=0,

  - x1 - 2*x2>=-6,

 x1 + x2>=2,

 x1 - x2>=3,

 x2>=0,

 2*x1 + x2 + z>=0}
--------------------------------
class 1:
       - x2 - z
{x1>=-----------,x1>=x2 + 3,x1>= - x2 + 2,x1>=0}
          2
--------------------------------
class 2:
{ - 2*x2 + 6>=x1}
--------------------------------
class 3:
{x2>=0}
--------------------------------
class 4:
{}
--------------------------------
next variable:x2; initial system:
{x2>=0,

                - x2 - z
  - 2*x2 + 6>=-----------,
                   2

  - 2*x2 + 6>=x2 + 3,

  - 2*x2 + 6>= - x2 + 2,

  - 2*x2 + 6>=0}
--------------------------------
normalized and reduced:
{ - x2>=-1, - 3*x2 + z>=-12,x2>=0}
--------------------------------
class 1:
{x2>=0}
--------------------------------
class 2:
  z + 12
{-------->=x2,1>=x2}
    3
--------------------------------
class 3:
{}
--------------------------------
class 4:
{}
--------------------------------
next variable:z; initial system:
  z + 12
{-------->=0,1>=0}
    3
--------------------------------
normalized and reduced:
{0>=-1,z>=-12}
--------------------------------
class 1:
{z>=-12}
--------------------------------
class 2:
{}
--------------------------------
class 3:
{}
--------------------------------
class 4:
{0>=-1}

          - 12 <= z <= inf;    minimum: z=-12

         0 <= x2 <= 0;    zero length interval: x2=0

         6 <= x1 <= 6;    zero length interval: x1=6

sol := {x1=6,x2=0,z=-12}


end;
(linineq 1250 0)


End of Lisp run after 1.28+0.63 seconds