GitHub

Exported SimplexTableaux Functions and their Docstrings

SimplexTableaux.Tableau — Type

Tableau(A::Matrix, b::Vector, c::Vector)

Create a Tableau data structure for the canonical form linear program minimize $c'x$ subject to $Ax ≥ b, x ≥ 0$.

If the LP is in standard form, minimize $c'x$ s.t. $Ax = b, x ≥ 0$, use Tableau(A, b, c, false).

source
SimplexTableaux.big_M_tableau — Function
big_M_tableau(T::Tableau, M::Int=100)

Form a new tableau from T by adding m artificial variables and add the terms +M*x_i (for each artificial variable x_i) to the objective function. Then set the basis to the columns for the artifical variables.

source
SimplexTableaux.check_basis — Method
check_basis(T::Tableau, vars::Vector{Int})::Bool

See if the list of column indices vars forms a basis (feasible or not) for T.

source
SimplexTableaux.dual — Method
dual(T::Tableau)

Create a tableau that is dual to T.

Caveats:

  • T should have been created from canonical data (not standard). [Standard LPs TBW.]
  • The returned tableau is set up as a minimization problem so the value of the solved LP is negative the desired value. However, the basic feasible vector is correct.
source
SimplexTableaux.get_Abc — Method
get_Abc(T::Tableau)

Returns a 3-tuple containing copies of the matrix A and the vectors b and c used to create T.

source
SimplexTableaux.header — Method
header(T::Tableau)

Return the header (negative reduced costs) of T.

Example

For this Tableau

┌──────────┬───┬─────┬─────┬─────┬─────┬─────┬─────┐
│          │ z │ x_1 │ x_2 │ x_3 │ x_4 │ x_5 │ RHS │
│ Obj Func │ 1 │  -2 │  -4 │  -2 │  -1 │   1 │   0 │
├──────────┼───┼─────┼─────┼─────┼─────┼─────┼─────┤
│   Cons 1 │ 0 │   2 │   1 │   0 │   9 │  -1 │   9 │
│   Cons 2 │ 0 │   1 │   1 │  -1 │   5 │   1 │   7 │
└──────────┴───┴─────┴─────┴─────┴─────┴─────┴─────┘

header(T) returns the vector [-2, -4, -2, -1, 1].

source
SimplexTableaux.is_canonical — Method
is_canonical(T::Tableau)::Bool

Return true if T was created from a canonical LP and return false if it was created from a standard LP.

source
SimplexTableaux.is_infeasible — Method
is_infeasible(T::Tableau)::Bool

Return true if the tableau represents an infeasible linear program (i.e., the feasible region is empty).

source
SimplexTableaux.lp_solve — Function
lp_solve(T::Tableau, verbose::Bool=true)

Use a standard linear programming solver [HiGHS by defaut] to find the optimal solution to the LP in T. Returns the values of the variables.

With verbose set to true [default], the value of the objective function is printed. Set verbose to false to supress this.

source
SimplexTableaux.phase_one_tableau — Method
phase_one_tableau(T::Tableau)

Create a tableau with additional slack variables from which it is easy to extract a basis for T or determine that T is infeasible.

source
SimplexTableaux.pivot! — Method
pivot!(T::Tableau, i::Int, j::Int)

Modify T by doing a pivot operation at contraint i and variable x_j.

source
SimplexTableaux.rhs — Method
rhs(T::Tableau)

Return the right-hand column of the T.

Example

For this Tableau

┌──────────┬───┬─────┬─────┬─────┬─────┬─────┬─────┐
│          │ z │ x_1 │ x_2 │ x_3 │ x_4 │ x_5 │ RHS │
│ Obj Func │ 1 │  -2 │  -4 │  -2 │  -1 │   1 │   0 │
├──────────┼───┼─────┼─────┼─────┼─────┼─────┼─────┤
│   Cons 1 │ 0 │   2 │   1 │   0 │   9 │  -1 │   9 │
│   Cons 2 │ 0 │   1 │   1 │  -1 │   5 │   1 │   7 │
└──────────┴───┴─────┴─────┴─────┴─────┴─────┴─────┘

rhs(T) returns the vector [9,7].

source
SimplexTableaux.set_basis! — Method
set_basis!(T::Tableau)

Invoke find_a_basis(T) and use the result to establish a basis for T. Silently fail if no basis is found.

source
SimplexTableaux.status — Method
status(T::Tableau)::Symbol

Return an indicator for the status of the tableau T being one of:

  • :no_basis – no basis has been established for this tableau
  • :feasible – the tableau is in a feasible state, but not optimal (rhs is nonnegative).
  • :infeasible – the tableau is in an infeasible state (rhs contains negative values).
  • :optimal – the tableau has reached a global minimization point.
  • :unbounded – no pivots are possible; objective function can be arbitrarily negative.
source
SimplexTableaux.value — Method
value(T::Tableau, x::Vector)

Return the value of the LP in T at the point x.

This can also be invoked as T(x).

source