Determine whether the current solution is correct.
Determine whether the current solution is correct.
the primal solution vector x
the dual solution vector y
the minimum value of the objective function
Return the dual solution vector y (cost row (M) under the slack columns).
Find the best variable x_l to enter the basis given that x_k is leaving the basis.
Find the best variable x_l to enter the basis given that x_k is leaving the basis. Determine the index of the entering variable corresponding to COLUMN l by selecting the minimum ratio. Return -1 to indicate no such column.
the variable that is leaving the basis
Show the flaw by printing the error message.
Show the flaw by printing the error message.
the method where the error occurred
the error message
Find the best variable x_k to leave the basis.
Find the best variable x_k to leave the basis. Determine the index of the leaving variable corresponding to ROW k by selecting the most negative RHS value. Return -1 to indicate no such row.
Return the value of the objective function f(x) = c x.
Return the value of the objective function f(x) = c x.
the coordinate values of the current point
Pivot on entry (k, l) using Gauss-Jordan elimination to replace variable x_k with x_l in the basis.
Pivot on entry (k, l) using Gauss-Jordan elimination to replace variable x_k with x_l in the basis.
the leaving variable (row)
the entering variable (column)
Return the primal solution vector x (only the basic variables are non-zero).
Show the current tableau.
Show the current tableau.
the number of iterations do far
Run the simplex algorithm starting from an initial BFS and iteratively find a non-basic variable to replace a variable in the current basis so long as the objective function improves.
Run the simplex algorithm starting from an initial BFS and iteratively find a non-basic variable to replace a variable in the current basis so long as the objective function improves. Return the optimal vector x.
Convert the current tableau and basis to a string suitable for display.
Convert the current tableau and basis to a string suitable for display.
This class solves Linear Programming (LP) problems using a tableau based Dual Simplex Algorithm. It is particularly useful when re-optimizing after a constraint has been added. The algorithm starts with an infeasible super-optimal solution and moves toward (primal) feasibility and optimality.
Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', find values for the solution/decision vector 'x' that minimize the objective function f(x), while satisfying all of the constraints, i.e.,
minimize f(x) = c x subject to a x <= b, x >= 0
Creates an MM-by-NN simplex tableau with -- [0..M-1, 0..N-1] = a (constraint matrix) -- [0..M-1, N..M+N-1] = s (slack/surplus variable matrix) -- [0..M-1, NN-1] = b (limit/RHS vector) -- [M, 0..NN-2] = c (cost vector)