GitHub

Solving Linear Programs

Manual Solution

Once a tableau has been created for a given linear program, the objective function can be minimized by the following steps:

  • Set a starting basis using set_basis!(T, B). To have the computer suggest a starting basis, use find_a_basis(T).
  • Repeatedly pivot the tableau until all the numbers under variable names are nonpositive. Use find_pivot to have the computer suggest a basis pivot.
  • When pivoting is finished, use basic_vector(T) to get the values for the variables that minimizes the LP and use value(T) to get the minimum objective value.

Simplex Method Solution

Given a tableau, use simplex_solve! to have the computer perform all the steps to produce an optimal solution to a linear program. 

julia> T
┌──────────┬───┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│          │ z │ x_1 │ x_2 │ x_3 │ x_4 │ x_5 │ x_6 │ x_7 │ RHS │
│ Obj Func │ 1 │  -9 │  -4 │  -2 │  -2 │  -7 │  -7 │  -3 │   0 │
├──────────┼───┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│   Cons 1 │ 0 │   2 │   2 │   3 │   1 │   8 │   1 │   2 │   3 │
│   Cons 2 │ 0 │   3 │   1 │   3 │   2 │   5 │   2 │   8 │   7 │
│   Cons 3 │ 0 │   8 │   2 │   1 │   4 │   6 │   3 │   2 │   8 │
└──────────┴───┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘


julia> simplex_solve!(T)
[ Info: Finding an initial basis.
Starting basis found: [1, 5, 7]
Starting tableau

┌──────────┬───┬─────┬─────────┬────────┬─────────┬─────┬─────────┬─────┬──────────┐
│          │ z │ x_1 │     x_2 │    x_3 │     x_4 │ x_5 │     x_6 │ x_7 │      RHS │
│ Obj Func │ 1 │   0 │ -149/86 │ -53/86 │ 439/172 │   0 │ -152/43 │   0 │ 1619/172 │
├──────────┼───┼─────┼─────────┼────────┼─────────┼─────┼─────────┼─────┼──────────┤
│   Cons 1 │ 0 │   1 │    7/86 │  -9/43 │  85/172 │   0 │   29/86 │   0 │  145/172 │
│   Cons 2 │ 0 │   0 │   21/86 │  16/43 │  -3/172 │   1 │    1/86 │   0 │    5/172 │
│   Cons 3 │ 0 │   0 │   -5/86 │  19/86 │  13/172 │   0 │    5/43 │   1 │   93/172 │
└──────────┴───┴─────┴─────────┴────────┴─────────┴─────┴─────────┴─────┴──────────┘

Pivot 1 at (1, 4)

┌──────────┬───┬─────────┬─────────┬────────┬─────┬─────┬──────────┬─────┬───────┐
│          │ z │     x_1 │     x_2 │    x_3 │ x_4 │ x_5 │      x_6 │ x_7 │   RHS │
│ Obj Func │ 1 │ -439/85 │ -183/85 │ 79/170 │   0 │   0 │ -897/170 │   0 │ 86/17 │
├──────────┼───┼─────────┼─────────┼────────┼─────┼─────┼──────────┼─────┼───────┤
│   Cons 1 │ 0 │  172/85 │   14/85 │ -36/85 │   1 │   0 │    58/85 │   0 │ 29/17 │
│   Cons 2 │ 0 │    3/85 │   21/85 │  31/85 │   0 │   1 │     2/85 │   0 │  1/17 │
│   Cons 3 │ 0 │  -13/85 │   -6/85 │ 43/170 │   0 │   0 │   11/170 │   1 │  7/17 │
└──────────┴───┴─────────┴─────────┴────────┴─────┴─────┴──────────┴─────┴───────┘

Pivot 2 at (2, 3)

┌──────────┬───┬─────────┬─────────┬─────┬─────┬────────┬─────────┬─────┬────────┐
│          │ z │     x_1 │     x_2 │ x_3 │ x_4 │    x_5 │     x_6 │ x_7 │    RHS │
│ Obj Func │ 1 │ -323/62 │ -153/62 │   0 │   0 │ -79/62 │ -329/62 │   0 │ 309/62 │
├──────────┼───┼─────────┼─────────┼─────┼─────┼────────┼─────────┼─────┼────────┤
│   Cons 1 │ 0 │   64/31 │   14/31 │   0 │   1 │  36/31 │   22/31 │   0 │  55/31 │
│   Cons 2 │ 0 │    3/31 │   21/31 │   1 │   0 │  85/31 │    2/31 │   0 │   5/31 │
│   Cons 3 │ 0 │  -11/62 │  -15/62 │   0 │   0 │ -43/62 │    3/62 │   1 │  23/62 │
└──────────┴───┴─────────┴─────────┴─────┴─────┴────────┴─────────┴─────┴────────┘

Optimality reached. Pivot count = 2
Minimal value = 309/62 = 4.983870967741935
7-element Vector{Rational}:
   0
   0
  5//31
 55//31
   0
   0
 23//62

Big-M Solution

The function big_M_solve! solves linear programs using the Simplex Method on an augmented tableau. The user may specify the value of M or use the default (100).

julia> T
┌──────────┬───┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│          │ z │ x_1 │ x_2 │ x_3 │ x_4 │ x_5 │ x_6 │ x_7 │ RHS │
│ Obj Func │ 1 │  -9 │  -4 │  -2 │  -2 │  -7 │  -7 │  -3 │   0 │
├──────────┼───┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│   Cons 1 │ 0 │   2 │   2 │   3 │   1 │   8 │   1 │   2 │   3 │
│   Cons 2 │ 0 │   3 │   1 │   3 │   2 │   5 │   2 │   8 │   7 │
│   Cons 3 │ 0 │   8 │   2 │   1 │   4 │   6 │   3 │   2 │   8 │
└──────────┴───┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘


julia> big_M_solve!(T)
Solving this augmented tableau

┌──────────┬───┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬──────┬──────┬──────┬─────┐
│          │ z │ x_1 │ x_2 │ x_3 │ x_4 │ x_5 │ x_6 │ x_7 │  x_8 │  x_9 │ x_10 │ RHS │
│ Obj Func │ 1 │  -9 │  -4 │  -2 │  -2 │  -7 │  -7 │  -3 │ -100 │ -100 │ -100 │   0 │
├──────────┼───┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼──────┼──────┼──────┼─────┤
│   Cons 1 │ 0 │   2 │   2 │   3 │   1 │   8 │   1 │   2 │    1 │    0 │    0 │   3 │
│   Cons 2 │ 0 │   3 │   1 │   3 │   2 │   5 │   2 │   8 │    0 │    1 │    0 │   7 │
│   Cons 3 │ 0 │   8 │   2 │   1 │   4 │   6 │   3 │   2 │    0 │    0 │    1 │   8 │
└──────────┴───┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴──────┴──────┴──────┴─────┘

Starting tableau

┌──────────┬───┬──────┬─────┬─────┬─────┬──────┬─────┬──────┬─────┬─────┬──────┬──────┐
│          │ z │  x_1 │ x_2 │ x_3 │ x_4 │  x_5 │ x_6 │  x_7 │ x_8 │ x_9 │ x_10 │  RHS │
│ Obj Func │ 1 │ 1291 │ 496 │ 698 │ 698 │ 1893 │ 593 │ 1197 │   0 │   0 │    0 │ 1800 │
├──────────┼───┼──────┼─────┼─────┼─────┼──────┼─────┼──────┼─────┼─────┼──────┼──────┤
│   Cons 1 │ 0 │    2 │   2 │   3 │   1 │    8 │   1 │    2 │   1 │   0 │    0 │    3 │
│   Cons 2 │ 0 │    3 │   1 │   3 │   2 │    5 │   2 │    8 │   0 │   1 │    0 │    7 │
│   Cons 3 │ 0 │    8 │   2 │   1 │   4 │    6 │   3 │    2 │   0 │   0 │    1 │    8 │
└──────────┴───┴──────┴─────┴─────┴─────┴──────┴─────┴──────┴─────┴─────┴──────┴──────┘

Pivot 1 at (1, 5)

┌──────────┬───┬────────┬──────┬───────┬────────┬─────┬────────┬────────┬─────────┬─────┬──────┬────────┐
│          │ z │    x_1 │  x_2 │   x_3 │    x_4 │ x_5 │    x_6 │    x_7 │     x_8 │ x_9 │ x_10 │    RHS │
│ Obj Func │ 1 │ 3271/4 │ 91/4 │ -95/8 │ 3691/8 │   0 │ 2851/8 │ 2895/4 │ -1893/8 │   0 │    0 │ 8721/8 │
├──────────┼───┼────────┼──────┼───────┼────────┼─────┼────────┼────────┼─────────┼─────┼──────┼────────┤
│   Cons 1 │ 0 │    1/4 │  1/4 │   3/8 │    1/8 │   1 │    1/8 │    1/4 │     1/8 │   0 │    0 │    3/8 │
│   Cons 2 │ 0 │    7/4 │ -1/4 │   9/8 │   11/8 │   0 │   11/8 │   27/4 │    -5/8 │   1 │    0 │   41/8 │
│   Cons 3 │ 0 │   13/2 │  1/2 │  -5/4 │   13/4 │   0 │    9/4 │    1/2 │    -3/4 │   0 │    1 │   23/4 │
└──────────┴───┴────────┴──────┴───────┴────────┴─────┴────────┴────────┴─────────┴─────┴──────┴────────┘

Pivot 2 at (3, 1)

┌──────────┬───┬─────┬─────────┬─────────┬───────┬─────┬────────┬─────────┬──────────┬─────┬──────────┬─────────┐
│          │ z │ x_1 │     x_2 │     x_3 │   x_4 │ x_5 │    x_6 │     x_7 │      x_8 │ x_9 │     x_10 │     RHS │
│ Obj Func │ 1 │   0 │ -522/13 │ 1890/13 │ 105/2 │   0 │ 953/13 │ 8591/13 │ -3699/26 │   0 │ -3271/26 │ 9535/26 │
├──────────┼───┼─────┼─────────┼─────────┼───────┼─────┼────────┼─────────┼──────────┼─────┼──────────┼─────────┤
│   Cons 1 │ 0 │   0 │    3/13 │   11/26 │     0 │   1 │   1/26 │    3/13 │     2/13 │   0 │    -1/26 │    2/13 │
│   Cons 2 │ 0 │   0 │   -5/13 │   19/13 │   1/2 │   0 │  10/13 │   86/13 │   -11/26 │   1 │    -7/26 │   93/26 │
│   Cons 3 │ 0 │   1 │    1/13 │   -5/26 │   1/2 │   0 │   9/26 │    1/13 │    -3/26 │   0 │     2/13 │   23/26 │
└──────────┴───┴─────┴─────────┴─────────┴───────┴─────┴────────┴─────────┴──────────┴─────┴──────────┴─────────┘

Pivot 3 at (2, 7)

┌──────────┬───┬─────┬─────────┬────────┬─────────┬─────┬─────────┬─────┬────────────┬──────────┬────────────┬──────────┐
│          │ z │ x_1 │     x_2 │    x_3 │     x_4 │ x_5 │     x_6 │ x_7 │        x_8 │      x_9 │       x_10 │      RHS │
│ Obj Func │ 1 │   0 │ -149/86 │ -53/86 │ 439/172 │   0 │ -152/43 │   0 │ -17201/172 │ -8591/86 │ -17013/172 │ 1619/172 │
├──────────┼───┼─────┼─────────┼────────┼─────────┼─────┼─────────┼─────┼────────────┼──────────┼────────────┼──────────┤
│   Cons 1 │ 0 │   0 │   21/86 │  16/43 │  -3/172 │   1 │    1/86 │   0 │     29/172 │    -3/86 │     -5/172 │    5/172 │
│   Cons 2 │ 0 │   0 │   -5/86 │  19/86 │  13/172 │   0 │    5/43 │   1 │    -11/172 │    13/86 │     -7/172 │   93/172 │
│   Cons 3 │ 0 │   1 │    7/86 │  -9/43 │  85/172 │   0 │   29/86 │   0 │    -19/172 │    -1/86 │     27/172 │  145/172 │
└──────────┴───┴─────┴─────────┴────────┴─────────┴─────┴─────────┴─────┴────────────┴──────────┴────────────┴──────────┘

Pivot 4 at (3, 4)

┌──────────┬───┬─────────┬─────────┬────────┬─────┬─────┬──────────┬─────┬──────────┬──────────┬────────────┬───────┐
│          │ z │     x_1 │     x_2 │    x_3 │ x_4 │ x_5 │      x_6 │ x_7 │      x_8 │      x_9 │       x_10 │   RHS │
│ Obj Func │ 1 │ -439/85 │ -183/85 │ 79/170 │   0 │   0 │ -897/170 │   0 │ -8452/85 │ -8486/85 │ -16953/170 │ 86/17 │
├──────────┼───┼─────────┼─────────┼────────┼─────┼─────┼──────────┼─────┼──────────┼──────────┼────────────┼───────┤
│   Cons 1 │ 0 │    3/85 │   21/85 │  31/85 │   0 │   1 │     2/85 │   0 │    14/85 │    -3/85 │      -2/85 │  1/17 │
│   Cons 2 │ 0 │  -13/85 │   -6/85 │ 43/170 │   0 │   0 │   11/170 │   1 │    -4/85 │    13/85 │    -11/170 │  7/17 │
│   Cons 3 │ 0 │  172/85 │   14/85 │ -36/85 │   1 │   0 │    58/85 │   0 │   -19/85 │    -2/85 │      27/85 │ 29/17 │
└──────────┴───┴─────────┴─────────┴────────┴─────┴─────┴──────────┴─────┴──────────┴──────────┴────────────┴───────┘

Pivot 5 at (1, 3)

┌──────────┬───┬─────────┬─────────┬─────┬─────┬────────┬─────────┬─────┬──────────┬──────────┬──────────┬────────┐
│          │ z │     x_1 │     x_2 │ x_3 │ x_4 │    x_5 │     x_6 │ x_7 │      x_8 │      x_9 │     x_10 │    RHS │
│ Obj Func │ 1 │ -323/62 │ -153/62 │   0 │   0 │ -79/62 │ -329/62 │   0 │ -3089/31 │ -6187/62 │ -6181/62 │ 309/62 │
├──────────┼───┼─────────┼─────────┼─────┼─────┼────────┼─────────┼─────┼──────────┼──────────┼──────────┼────────┤
│   Cons 1 │ 0 │    3/31 │   21/31 │   1 │   0 │  85/31 │    2/31 │   0 │    14/31 │    -3/31 │    -2/31 │   5/31 │
│   Cons 2 │ 0 │  -11/62 │  -15/62 │   0 │   0 │ -43/62 │    3/62 │   1 │    -5/31 │    11/62 │    -3/62 │  23/62 │
│   Cons 3 │ 0 │   64/31 │   14/31 │   0 │   1 │  36/31 │   22/31 │   0 │    -1/31 │    -2/31 │     9/31 │  55/31 │
└──────────┴───┴─────────┴─────────┴─────┴─────┴────────┴─────────┴─────┴──────────┴──────────┴──────────┴────────┘

Optimality reached. Pivot count = 5
Minimal value = 309/62 = 4.983870967741935

Final tableau

┌──────────┬───┬─────────┬─────────┬─────┬─────┬────────┬─────────┬─────┬────────┐
│          │ z │     x_1 │     x_2 │ x_3 │ x_4 │    x_5 │     x_6 │ x_7 │    RHS │
│ Obj Func │ 1 │ -323/62 │ -153/62 │   0 │   0 │ -79/62 │ -329/62 │   0 │ 309/62 │
├──────────┼───┼─────────┼─────────┼─────┼─────┼────────┼─────────┼─────┼────────┤
│   Cons 1 │ 0 │    3/31 │   21/31 │   1 │   0 │  85/31 │    2/31 │   0 │   5/31 │
│   Cons 2 │ 0 │   64/31 │   14/31 │   0 │   1 │  36/31 │   22/31 │   0 │  55/31 │
│   Cons 3 │ 0 │  -11/62 │  -15/62 │   0 │   0 │ -43/62 │    3/62 │   1 │  23/62 │
└──────────┴───┴─────────┴─────────┴─────┴─────┴────────┴─────────┴─────┴────────┘

Minimal value = 309//62 = 4.983870967741935
7-element Vector{Rational}:
   0
   0
  5//31
 55//31
   0
   0
 23//62

Numerical Solution

The function lp_solve uses a standard linear program solver to solve the tableau. We use the HiGHS solver.

julia> T
┌──────────┬───┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│          │ z │ x_1 │ x_2 │ x_3 │ x_4 │ x_5 │ x_6 │ x_7 │ RHS │
│ Obj Func │ 1 │  -9 │  -4 │  -2 │  -2 │  -7 │  -7 │  -3 │   0 │
├──────────┼───┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│   Cons 1 │ 0 │   2 │   2 │   3 │   1 │   8 │   1 │   2 │   3 │
│   Cons 2 │ 0 │   3 │   1 │   3 │   2 │   5 │   2 │   8 │   7 │
│   Cons 3 │ 0 │   8 │   2 │   1 │   4 │   6 │   3 │   2 │   8 │
└──────────┴───┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘


julia> lp_solve(T)
Minimal objective value = 4.983870967741936

7-element Vector{Float64}:
 0.0
 0.0
 0.1612903225806452
 1.7741935483870968
 0.0
 0.0
 0.3709677419354839