class Simplex extends MinimizerLP
The Simplex class solves Linear Programming (LP) problems using a tableau based
Simplex Algorithm. 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
In case of 'a_i x >= b_i', use '-b_i' as an indicator of a '>=' constraint. The program will flip such negative b_i back to positive as well as use a surplus variable instead of the usual slack variable, i.e., a_i x <= b_i => a_i x + s_i = b_i // use slack variable s_i with coefficient 1 a_i x >= b_i => a_i x + s_i = b_i // use surplus variable s_i with coefficient -1
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
- Simplex
- MinimizerLP
- Error
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new Simplex(a: MatrixD, b: VectorD, c: VectorD)
In case there are no surplus variables (only slacks), the slack variables can form an initial basis.
In case there are no surplus variables (only slacks), the slack variables can form an initial basis.
- 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
- new Simplex(a: MatrixD, b: VectorD, c: VectorD, x_B: Array[Int], n_eq: Int = 0)
- 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 (if not available use Simple2P)
- n_eq
the number of equality constraints (must come last)
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
- Simplex → MinimizerLP
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native() @HotSpotIntrinsicCandidate()
- def dual: VectorD
Return the dual solution vector y (cost row (M) under the slack columns).
- def entering(): Int
Find the best variable x_l to enter the basis.
Find the best variable x_l to enter the basis. Determine the index of entering variable corresponding to COLUMN l (e.g., using Dantiz's Rule or Bland's Rule). Return -1 to indicate no such column. t(M).argmaxPos (JJ) // use Dantiz's rule (index of max positive, cycling possible) t(M).firstPos (JJ) // use Bland's rule (index of first positive, FPE possible)
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- final def flaw(method: String, message: String): Unit
- Definition Classes
- Error
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- def infeasible: Boolean
Determine whether the current solution (x = primal) is still primal feasible.
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- def leaving(l: Int): Int
Find the best variable x_k to leave the basis given that x_l is entering.
Find the best variable x_k to leave the basis given that x_l is entering. Determine the index of the leaving variable corresponding to ROW k using the Min-Ratio Rule. Return -1 to indicate no such row.
- l
the entering variable (column)
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- 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
- Simplex → 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
- Simplex → 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
- Simplex → AnyRef → Any
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
Deprecated Value Members
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable]) @Deprecated
- Deprecated