Simplex-method with Minimal-Ratio-Test (MRT)

by W.Lindner

LindnerW@t-online.de

We solve the example of J. Chinneck (chapter4.pdf) using EULER.
URL: http://www.sce.carleton.ca/faculty/chinneck/po.html

The LP is:

  Maximize    Z = 15x1 + 10x2
  subject to
             x1>=0
             x2>=0
             x1<=2
             x2<=3
          x1+x2<=4

In Matrixnotation:

  x    y   s1 s2 s3   b
  1    0   1  0  0    2
  0    1   0  1  0    3
  1    1   0  0  1    4
  -15 -10

The situation is:
>loadimg("Lp-Bild1"); 

Linear Programming

>load "MRT.e";
>A=[1,0,1,0,0,2;0,1,0,1,0,3;1,1,0,0,1,4;-15,-10,0,0,0,0]
Column 1 to 3:
                  1                   0                   1 
                  0                   1                   0 
                  1                   1                   0 
                -15                 -10                   0 
Column 4 to 6:
                  0                   0                   2 
                  1                   0                   3 
                  0                   1                   4 
                  0                   0                   0 
The (last) row of the objective function has his smallest value
-15 in column 1. So we choose column A[,1] as our pivotCOLUMN.
To choose the corresponding ROW we make the MinimalRatioTest (MRT):
>MRT1(A,1)   // MRT by inspecting with the eyes
Quotients :
      2.00
no limit
      4.00
>MRT (A,1)   // we control our pivot positions
Quotients :
                  2 
                  4 
Take : i=1 j=1
The MinimalRatioTest MRT b/pivotcolumn[1] has his smallest value
in row 1. So we pivotizise at position (1,1).
Calculate A[k]:=A[k]-A[k,1]/A[1,1]*A[1] for k=2,3,4 (without 1):
>A1=pivotize(A,1,1)
Column 1 to 3:
                  1                   0                   1 
                  0                   1                   0 
                  0                   1                  -1 
                  0                 -10                  15 
Column 4 to 6:
                  0                   0                   2 
                  1                   0                   3 
                  0                   1                   2 
                  0                   0                  30 
We see: (x1,x2,s1,s2,s3)=(2,0,0,3,2) with z=30. 
The objective functin row has his smallest value -10 in column
2. So we choose  column A[,2] as new pivotCOLUMN.
>MRT1(A1,2)  // choose pivot row for yourself
Quotients :
no limit
      3.00
      2.00
>MRT (A1,2)  // test your choise
Quotients :
                  3 
                  2 
Take : i=3 j=2
The MinimalRatioTest MRT b/pivotColumn[2] has his smallest value
in row 3. So we pivotizise at position (3,2). We calculate
A[k]:=A[k]-A[k,2]/A[3,2]*A[2] for k=1,2,4 (without 3):
>A2=pivotize(A1,3,2)
Column 1 to 3:
                  1                   0                   1 
                  0                   0                   1 
                  0                   1                  -1 
                  0                   0                   5 
Column 4 to 6:
                  0                   0                   2 
                  1                  -1                   1 
                  0                   1                   2 
                  0                  10                  50 
We see: (x1,x2,s1,s2,s3)=(2,2,0,1,0) with z=50.
The row of the  objective function has no negative entry: STOP!
We get the solution: x1=2, x2=2 and z=50.
The situation now is:
>loadimg("Lp-Bild2.png");

Linear Programming

Now we have a procedural understanding of the simplex method.
We get a conceptual understanding by studying the text of John
Chinneck.
We control our result with the numeric tool EULER :
>shortformat; 
>A=[1,0,1,0,0;0,1,0,1,0;1,1,0,0,1]
            1             0             1             0             0 
            0             1             0             1             0 
            1             1             0             0             1 
>b=[2;3;4]
            2 
            3 
            4 
>c=[15,10,0,0,0]
[ 15  10  0  0  0 ]
>{x,r,i}=simplex(A,b,c, max=1); r, 
0
>x     // solution
            2 
            2 
            0 
            0 
            0 
>c.x   // check
[ 50 ]
We control our result with the symbolic CAS Maxima:
>:: load("simplex");
>:: A := matrix([1,0,1,0,0],[0,1,0,1,0],[1,1,0,0,1])
                          [ 1  0  1  0  0 ]
                          [               ]
                          [ 0  1  0  1  0 ]
                          [               ]
                          [ 1  1  0  0  1 ]

>:: b:=[2,3,4]
                              [2, 3, 4]

>:: c:=[-15,-10,0,0,0]
                        [- 15, - 10, 0, 0, 0]

>:: linear_program(A, b, c)
                       [[2, 2, 0, 1, 0], - 50]

.. or:
>:: maximize_lp(15*x1 + 10*x2, [ x1>=0, x2>=0, x1<=2, x2<=3, x1+x2<=4])
                        [50, [x2 = 2, x1 = 2]]

-------------------------------------------- Exercise:
Solve the following LP via the example above.
. What is the term of the objective function?
. Formulate the LP as A*X=B with constrains.
--------------------------------------------
>fracformat(10);
>LP:=[-1,  1,  1, 1, 0, 0; ...
>      1, -2,  1, 0, 1, 0; ...
>      1,  1,  0, 0, 0, 1; ...
>      0,  0, -1, 0, 0, 0]
       -1         1         1         1         0         0 
        1        -2         1         0         1         0 
        1         1         0         0         0         1 
        0         0        -1         0         0         0