reduce-historical/r34/lib/linineq.log

REDUCE 3.4, 15-Jul-91 ...

1: 
(LININEQ)


% 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;


Quitting