class Simplex2P extends Error
The Simplex2P 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 maximize
the objective function 'f(x)', while satisfying all of the constraints, i.e.,
maximize 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 and artificial 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 For each ">=" constraint, an artificial variable is introduced and put into the initial basis. These artificial variables must be removed from the basis during Phase I of the Two-Phase Simplex Algorithm. After this, or if there are no artificial variables, Phase II is used to find an optimal value for 'x' and the optimum value for 'f'.
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, M+N..nn-2] = r (artificial variable matrix) -- [0..M-1, nn-1] = b (limit/RHS vector) -- [M, 0..nn-2] = c (cost vector)
- Alphabetic
- By Inheritance
- Simplex2P
- Error
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
-
new
Simplex2P(a: MatrixD, b: VectorD, c: VectorD)
- 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
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
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
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 enteringMax(): Int
-
def
enteringMin(): 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).firstPos (jj) // use Bland's rule (lowest index, positive) t(M).argmaxPos (jj) // use Dantiz's rule (min index, positive, cycling possible)
-
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
-
def
initBasis(): Unit
Initialize the basis to the slack and artificial variables.
Initialize the basis to the slack and artificial variables. Perform row operations to make cost row (t(M)) zero in artificial var columns. If b(i) is negative have a surplus and artificial variable, otherwise, just a slack variable.
-
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
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
-
def
objective: Double
Return the value of the objective function f(x) = c x.
-
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
removeArtificials(): Unit
Remove the artificial variables and reset the cost row (M) in the tableau.
-
def
solve(): Unit
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.
-
def
solve2P(): Boolean
Solve the LP maximization problem using two phases if necessary.
Solve the LP maximization problem using two phases if necessary. Note: phase I is always minimization. Two phases are necessary if the number of artificial variables R > 0.
-
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
- Simplex2P → 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( ... )