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
- All
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
-
final
def
!=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
##(): Int
- Definition Classes
- AnyRef → Any
-
final
def
==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
val
EPSILON: Double
- Attributes
- protected
- Definition Classes
- MinimizerLP
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
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
clone(): AnyRef
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
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
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
equals(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
finalize(): Unit
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
-
final
def
flaw(method: String, message: String): Unit
- Definition Classes
- Error
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
-
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
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.
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
-
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
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
-
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
-
final
def
wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )