A Simplex Iteration

John E. Mitchell

Consider the linear programming problem

min         8x1  +   4x2  +   5x3  +    6x4
subject to    x1  +   2x2  -    x3  -     x4  =   1
           - x1  -   5x2  +   2x3  +    3x4  =   1
                               xi  ≥   0 ∀i

We have

    [                    ]       [    ]
        1    2  - 1  - 1           1                 [            ]
A =                       ,  b =       ,   and cT =   8  4   5  6  .
      - 1  - 5    2    3           1

Columns 1 and 3 of A are linearly independent, so we initialize with B equal to these two columns:

    [          ]
B =     1  - 1   ,
      - 1    2

and then

     [         ]          [   ]         [   ]         [     ]         [    ]
         2  - 1             8             4              x1             x2
N =    - 5   3   ,  cB =    5  ,  cN  =   6   ,  xB =    x3  ,  xN  =   x4   .

The corresponding basic solution is obtained by calculating B-1b:

     [    ]           [       ][   ]   [    ]
xB =   x1   =  B- 1b =   2  1    1   =   3   .
       x3                1  1    1       2

Thus, we have a basic feasible solution x1 = [3, 0, 2, 0]T . The objective function value is

cT x1 = cTB -1b = 34.
         B

We next express the LP in the form

min         cTBB -1b  +  (cTN -  cTBB -1N )xN
subject to    x      +            B -1N x    =  B -1b
               B                         N
                                    xB, xN   ≥  0

This requires the following calculations:

         [      ] [         ]   [        ]
B -1N =    2  1      2  - 1   =   - 1  1   .
           1  1     - 5   3       - 3  2

and

                              [        ]
 T    T   -1                    - 1  1
cN - cBB    N =  [4, 6] - [8, 5]  - 3  2   = [4, 6] - [- 23, 18 ] = [27, - 12].

(This vector is the vector of reduced costs.) Thus we can express our original linear programming problem equivalently as

min         34            +   27x   -   12x
                                 2          4
subject to      x1        -     x2  +     x4  =   3
                      x3  -    3x2  +    2x4  =   2
                                xi  ≥   0 ∀i.

(Notice the order of the variables.) Since the cost of x4 is negative in this formulation and x4 is currently zero, we can try to improve the solution by increasing x4. The first constraint tells us that we have (with x2 = 0)

x1 =  3 - x4,

so we can’t make x4 any bigger than 3 without violating the nonnegativity restriction on x1. Similarly, the second constraint tells us that we have

x3 = 2 - 2x4,

so we can’t make x4 any bigger than 1 without violating the nonnegativity restriction on x3. (This examination to find the largest possible increase in the variable entering the basis is known as the minimum ratio test.) Thus, we set x4 to 1 and remove x3 from the basis, giving a new basis of x1 and x4. (This is a pivot from one basic feasible solution to another.)

We can now repeat the whole process over again from the new basic feasible solution. The matrix B now consists of columns 1 and 4 of A:

    [          ]
        1  - 1
B =   - 1    3   ,

We have

     [         ]          [   ]         [   ]         [     ]         [    ]
         2  - 1             8             4              x1             x2
N =    - 5   2   ,  cB =    6  ,  cN  =   5   ,  xB =    x   ,  xN  =   x    .
                                                          4               3

The corresponding basic solution is obtained by calculating B-1b:

     [    ]             [       ][   ]   [    ]
       x1       - 1    1-  3  1    1       2
xB =   x4   =  B   b = 2   1  1    1   =   1   .

Thus, we have the basic feasible solution x2 = [2, 0, 0, 1]T . The objective function value is

 T  2    T  -1
c x  =  cBB   b = 22,

which is indeed an improvement on the previous objective function value of 34. We next express the LP in the form

             T  -1        T     T  -1
min         cBB   b  +  (cN -  cBB   N )xN
subject to    xB     +            B -1N xN   =  B -1b
                                    xB, xN   ≥  0

This requires the following calculations:

           [      ] [          ]     [         ]
  -1      1- 3  1       2  - 1     1-    1  - 1
B   N  =  2  1  1     - 5    2  =  2   - 3   1

and

                               [          ]
 T    T  -1              1         1  - 1
cN - cBB   N  = [4, 5] - -[8, 6]  - 3    1   = [4, 5] - [- 5, - 1] = [9, 6].
                         2

Thus, we have another equivalent formulation of our original linear programming problem:

min        22             +    9x   +     6x
                                 2          3
subject to     x1         +  0.5x2  -   0.5x3  =  2
                     x4   -  1.5x2  +   0.5x3  =  1
                                xi  ≥   0 ∀i.

Since the reduced costs are all nonnegative, this solution is actually optimal.

Note: Let z be the objective function, so -z + 8x1 + 4x2 + 5x3 + 6x4 = 0. Then the pivot we performed can be calculated exactly like a pivot in Gaussian elimination, by pivoting on x4 in the second constraint of the formulation:

min         - z            +  27x2   -   12x4  =   - 34
subject to       x1        -     x2  +     x4  =      3
                       x3  -    3x2  +    2x4  =      2
                                 xi  ≥  0  ∀i.

becomes

min        - z            +     9x2  +     6x3  =   - 22
subject to      x1        +   0.5x2  -   0.5x3  =     2
                      x4  -   1.5x2  +   0.5x3  =     1

                                 xi  ≥   0 ∀i,

after reordering the columns.

Note: In a practical implementation, only quantities that are actually needed are calculated, and the quantities are calculated more efficiently. For example, the inverse matrix B-1 is never calculated explicitly.