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