|\^/|     Maple V Release 4 (Worcester Polytechnic Institute)
._|\|   |/|_. Copyright (c) 1981-1996 by Waterloo Maple Inc. All rights
 \  MAPLE  /  reserved. Maple and Maple V are registered trademarks of
 <____ ____>  Waterloo Maple Inc.
      |       Type ? for help.
#  March 21, 2004
> read pivot.txt:
Warning, new definition for pivot
> 
# We solve the LP   Max   8/3 x1  +  1/3  x2
#              subject to 2/3 x1  +  1/3  x2 <= 28
#                             x1             <= 30
#                             x1,         x2 >= 0
# Introduce slack variables x3 and x4 and here are the initial
# data structures A, b, c, z needed for WJM's pivot routine:
> 
> A := matrix(2,4,[ 2/3,1/3,1,0,   1,0,0,1]);
                               [2/3    1/3    1    0]
                          A := [                    ]
                               [ 1      0     0    1]

>  
> 
> b := matrix(2,1,[28,30]);
                                        [28]
                                   b := [  ]
                                        [30]

> 
> c := matrix(1,4,[8/3,1/3,0,0]);
                          c := [8/3    1/3    0    0]

> 
> z := 0;
                                     z := 0

> 
> 
# See initial tableau by trivial pivot:
> pivot(1,3);
    x1      x2      x3      x4   |    b  
_________________________________|_________
     .66     .33    1.00    0.00 |  28.00 
    1.00    0.00    0.00    1.00 |  30.00 
_________________________________|_________
    2.66     .33    0.00    0.00 |   0.00 


> 
# Choose x1 as entering variable. Find ratios:
> ratios(1);
row  1:  Upper bound =  42.0000 
row  2:  Upper bound =  30.0000 
> 
# Tighter restriction comes from row 2.
# So x4 exits the basis. Pivot on row 2, column 1.
> pivot(2,1);
    x1      x2      x3      x4   |    b  
_________________________________|_________
    0.00     .33    1.00    -.66 |   8.00 
    1.00    0.00    0.00    1.00 |  30.00 
_________________________________|_________
    0.00     .33    0.00   -2.66 | -80.00 


> 
# Reduced cost c2 is still positive, so not done.
# x2 is the entering variable. Find ratios (even though its obviously row 1):
> ratios(2);
row  1:  Upper bound =  24.0000 
row  2:  No upper bound 
> 
# So x3 exits the basis and we pivot on row 1, column 2.
> pivot(1,2);
    x1      x2      x3      x4   |    b  
_________________________________|_________
    0.00    1.00    3.00   -2.00 |  24.00 
    1.00    0.00    0.00    1.00 |  30.00 
_________________________________|_________
    0.00    0.00   -1.00   -2.00 | -88.00 


> 
# Now we have reached optimality. All reduced costs non-positive.
# Optimal basis:  {x1,x2}
# Optimal Solution: x* = [ 30, 24, 0, 0 ]
# Optimal objective value: z* = 88
> quit
bytes used=873584, alloc=786288, time=0.03