scalation.maxima

Simplex2P

class Simplex2P extends Error

This 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, ie., a_i x <= b_i => a_i x + s_i = b_i // use slack variable s_i with coeff 1 a_i x >= b_i => a_i x + s_i = b_i // use surplus variable s_i with coeff -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)

Linear Supertypes
Error, AnyRef, Any
Ordering
  1. Alphabetic
  2. By inheritance
Inherited
  1. Simplex2P
  2. Error
  3. AnyRef
  4. Any
  1. Hide All
  2. Show all
Learn more about member selection
Visibility
  1. Public
  2. All

Instance Constructors

  1. 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

  1. final def !=(arg0: Any): Boolean

    Definition Classes
    AnyRef → Any
  2. final def ##(): Int

    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean

    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0

    Definition Classes
    Any
  5. def clone(): AnyRef

    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  6. def dual: VectorD

    Return the dual solution vector y (cost row (M) under the slack columns).

  7. def enteringMax(): Int

  8. 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, +ve) t(M).argmaxPos (jj) // use Dantiz's rule (min index, +ve, cycling possible)

  9. final def eq(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  10. def equals(arg0: Any): Boolean

    Definition Classes
    AnyRef → Any
  11. def finalize(): Unit

    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  12. def flaw(method: String, message: String): Unit

    Show the flaw by printing the error message.

    Show the flaw by printing the error message.

    method

    the method where the error occurred

    message

    the error message

    Definition Classes
    Error
  13. final def getClass(): Class[_]

    Definition Classes
    AnyRef → Any
  14. def hashCode(): Int

    Definition Classes
    AnyRef → Any
  15. 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.

  16. final def isInstanceOf[T0]: Boolean

    Definition Classes
    Any
  17. 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)

  18. final def ne(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  19. final def notify(): Unit

    Definition Classes
    AnyRef
  20. final def notifyAll(): Unit

    Definition Classes
    AnyRef
  21. def objective: Double

    Return the value of the objective function f(x) = c x.

  22. 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)

  23. def primal: VectorD

    Return the primal solution vector x (only the basic variables are non-zero).

  24. def removeArtificials(): Unit

    Remove the artifical variables and reset the cost row (M) in the tableau.

  25. 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.

  26. def solve2P(): Boolean

    Solve the LP maximization problem using two phases if neceassry.

    Solve the LP maximization problem using two phases if neceassry. Note: phase I is always minimization. Two phases are necessary if the number of artificial variables R > 0.

  27. final def synchronized[T0](arg0: ⇒ T0): T0

    Definition Classes
    AnyRef
  28. 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
  29. final def wait(): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  30. final def wait(arg0: Long, arg1: Int): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  31. final def wait(arg0: Long): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from Error

Inherited from AnyRef

Inherited from Any

Ungrouped