class DualSimplex extends MinimizerLP
The DualSimplex 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)
- Alphabetic
- By Inheritance
- DualSimplex
- MinimizerLP
- Error
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new DualSimplex(a: MatrixD, b: VectorD, c: VectorD, x_B: Array[Int])
- a
the M-by-N constraint matrix
- b
the M-length limit/RHS vector (input b_i negative for surplus)
- c
the N-length cost vector
- x_B
the indices of the initial basis (e.g., from primal Simplex)
Value Members
- def check(x: VectoD, y: VectoD, f: Double): Boolean
Determine whether the current solution is correct.
Determine whether the current solution is correct.
- x
the primal solution vector x
- y
the dual solution vector y
- f
the minimum value of the objective function
- Definition Classes
- MinimizerLP
- val checker: CheckLP
- Definition Classes
- DualSimplex → MinimizerLP
- def dual: VectorD
Return the dual solution vector y (cost row (M) under the slack columns).
- def entering(k: Int): Int
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.
- k
the variable that is leaving the basis
- final def flaw(method: String, message: String): Unit
- Definition Classes
- Error
- def leaving(): Int
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.
- def objF(x: VectoD): Double
Return the value of the objective function f(x) = c x.
Return the value of the objective function f(x) = c x.
- x
the coordinate values of the current point
- Definition Classes
- DualSimplex → MinimizerLP
- def pivot(k: Int, l: Int): Unit
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.
- k
the leaving variable (row)
- l
the entering variable (column)
- def primal: VectorD
Return the primal solution vector x (only the basic variables are non-zero).
- def showTableau(iter: Int): Unit
Show the current tableau.
Show the current tableau.
- iter
the number of iterations do far
- def solve(): VectorD
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.
- Definition Classes
- DualSimplex → MinimizerLP
- def toString(): String
Convert the current tableau and basis to a string suitable for display.
Convert the current tableau and basis to a string suitable for display.
- Definition Classes
- DualSimplex → AnyRef → Any