class RevisedSimplex extends MinimizerLP
The RevisedSimplex class solves Linear Programming (LP) problems using the
Revised Simplex Algorithm. Given a constraint matrix 'a', constant 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
The Revised Simplex Algorithm operates on 'b_inv', which is the inverse of the basis-matrix ('ba' = 'B'). It has benefits over the Simplex Algorithm (less memory and reduced chance of round off errors).
- Alphabetic
- By Inheritance
- RevisedSimplex
- MinimizerLP
- Error
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
-
new
RevisedSimplex(a: MatrixD, b: VectorD, c: VectorD, x_B: Array[Int] = null)
- a
the constraint matrix
- b
the constant/limit vector
- c
the cost/revenue vector
- x_B
the initial basis (set of indices where x_i is in the basis)
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
- RevisedSimplex → MinimizerLP
-
def
clone(): AnyRef
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
def
dual: VectoD
Return the dual solution vector (y).
-
def
entering(): Int
Find the best variable x_l to enter the basis.
Find the best variable x_l to enter the basis. Use Dantiz's Rule: index of max positive (cycling possible) z value. Return -1 to indicate no such column.
-
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(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 variable chosen to enter the basis
-
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 optimal objective function value (f(x) = c x).
Return the optimal objective function value (f(x) = c x).
- x
the primal solution vector
- Definition Classes
- RevisedSimplex → MinimizerLP
-
def
pivot(k: Int, l: Int): Unit
Pivot by replacing x_k with x_l in the basis.
Pivot by replacing x_k with x_l in the basis. Update b_inv, b_ and c_.
- k
the leaving variable
- l
the entering variable
-
def
primal: VectorD
Return the primal (basis only) solution vector (x).
-
def
primalFull(x: VectorD): VectorD
Return the full primal solution vector (xx).
-
def
rebuild(): Unit
Rebuild the b_inv matrix from the original a matrix, by setting basis columns and inverting that matrix in-place.
-
def
setBasis(j: Int = N-M, l: Int = M): Array[Int]
There are M+N variables, N decision and M slack variables, of which, for each iteration, M are chosen for a Basic Feasible Solution (BFS).
There are M+N variables, N decision and M slack variables, of which, for each iteration, M are chosen for a Basic Feasible Solution (BFS). The the variables not in the basis are set to zero. Setting j to N will start with the slack variables in the basis (only works if b >= 0).
- j
the offset to start the basis
- l
the size of the basis
-
def
showTableau(iter: Int): Unit
Show the current revised tableau.
Show the current revised tableau.
- iter
the number of iterations do far
-
def
solve(): VectorD
Solve a Linear Programming (LP) problem using the Revised Simplex Algorithm.
Solve a Linear Programming (LP) problem using the Revised Simplex Algorithm. Iteratively pivot until there an optimal solution is found or it is determined that the solution is unbounded. Return the optimal vector x.
- Definition Classes
- RevisedSimplex → MinimizerLP
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
-
def
toString(): String
Convert the current revised tableau (basis, b_inv, b_, and c_) to a string.
Convert the current revised tableau (basis, b_inv, b_, and c_) to a string.
- Definition Classes
- RevisedSimplex → AnyRef → Any
-
def
unbounded(u: VectoD): Boolean
Check if u <= 0., the solution is unbounded.
Check if u <= 0., the solution is unbounded.
- u
the vector for leaving
-
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( ... )
- var x_B: Array[Int]