org.apache.commons.math3.optim.linear
class SimplexTableau extends Object implements Serializable
Example:
W | Z | x1 | x2 | x- | s1 | s2 | a1 | RHS --------------------------------------------------- -1 0 0 0 0 0 0 1 0 <= phase 1 objective 0 1 -15 -10 0 0 0 0 0 <= phase 2 objective 0 0 1 0 0 1 0 0 2 <= constraint 1 0 0 0 1 0 0 1 0 3 <= constraint 2 0 0 1 1 0 0 0 1 4 <= constraint 3W: Phase 1 objective function Z: Phase 2 objective function x1 & x2: Decision variables x-: Extra decision variable to allow for negative values s1 & s2: Slack/Surplus variables a1: Artificial variable RHS: Right hand side
Modifier and Type | Field and Description |
---|---|
private List<String> |
columnLabels
The variables each column represents
|
private List<LinearConstraint> |
constraints
Linear constraints.
|
private static double |
CUTOFF_THRESHOLD
The cut-off threshold to zero-out entries.
|
private static int |
DEFAULT_ULPS
Default amount of error to accept in floating point comparisons (as ulps).
|
private double |
epsilon
Amount of error to accept when checking for optimality.
|
private LinearObjectiveFunction |
f
Linear objective function.
|
private int |
maxUlps
Amount of error to accept in floating point comparisons.
|
private static String |
NEGATIVE_VAR_COLUMN_LABEL
Column label for negative vars.
|
private int |
numArtificialVariables
Number of artificial variables.
|
private int |
numDecisionVariables
Number of decision variables.
|
private int |
numSlackVariables
Number of slack variables.
|
private boolean |
restrictToNonNegative
Whether to restrict the variables to non-negative values.
|
private static long |
serialVersionUID
Serializable version identifier.
|
private RealMatrix |
tableau
Simple tableau.
|
Constructor and Description |
---|
SimplexTableau(LinearObjectiveFunction f,
Collection<LinearConstraint> constraints,
GoalType goalType,
boolean restrictToNonNegative,
double epsilon)
Builds a tableau for a linear problem.
|
SimplexTableau(LinearObjectiveFunction f,
Collection<LinearConstraint> constraints,
GoalType goalType,
boolean restrictToNonNegative,
double epsilon,
int maxUlps)
Build a tableau for a linear problem.
|
Modifier and Type | Method and Description |
---|---|
private void |
copyArray(double[] src,
double[] dest) |
protected RealMatrix |
createTableau(boolean maximize)
Create the tableau by itself.
|
protected void |
divideRow(int dividendRow,
double divisor)
Subtracts a multiple of one row from another.
|
protected void |
dropPhase1Objective()
Removes the phase 1 objective function, positive cost non-artificial variables,
and the non-basic artificial variables from this tableau.
|
boolean |
equals(Object other) |
protected int |
getArtificialVariableOffset()
Get the offset of the first artificial variable.
|
protected Integer |
getBasicRow(int col)
Checks whether the given column is basic.
|
private int |
getConstraintTypeCounts(Relationship relationship)
Get a count of constraints corresponding to a specified relationship.
|
protected double[][] |
getData()
Get the tableau data.
|
protected double |
getEntry(int row,
int column)
Get an entry of the tableau.
|
protected int |
getHeight()
Get the height of the tableau.
|
protected static double |
getInvertedCoefficientSum(RealVector coefficients)
Get the -1 times the sum of all coefficients in the given array.
|
protected int |
getNumArtificialVariables()
Get the number of artificial variables.
|
protected int |
getNumDecisionVariables()
Get the number of decision variables.
|
protected int |
getNumObjectiveFunctions()
Get the number of objective functions in this tableau.
|
protected int |
getNumSlackVariables()
Get the number of slack variables.
|
protected int |
getOriginalNumDecisionVariables()
Get the original number of decision variables.
|
protected int |
getRhsOffset()
Get the offset of the right hand side.
|
protected int |
getSlackVariableOffset()
Get the offset of the first slack variable.
|
protected PointValuePair |
getSolution()
Get the current solution.
|
protected int |
getWidth()
Get the width of the tableau.
|
int |
hashCode() |
protected void |
initializeColumnLabels()
Initialize the labels for the columns.
|
(package private) boolean |
isOptimal()
Returns whether the problem is at an optimal state.
|
private LinearConstraint |
normalize(LinearConstraint constraint)
Get a new equation equivalent to this one with a positive right hand side.
|
List<LinearConstraint> |
normalizeConstraints(Collection<LinearConstraint> originalConstraints)
Get new versions of the constraints which have positive right hand sides.
|
private void |
readObject(ObjectInputStream ois)
Deserialize the instance.
|
protected void |
setEntry(int row,
int column,
double value)
Set an entry of the tableau.
|
protected void |
subtractRow(int minuendRow,
int subtrahendRow,
double multiple)
Subtracts a multiple of one row from another.
|
private void |
writeObject(ObjectOutputStream oos)
Serialize the instance.
|
private static final String NEGATIVE_VAR_COLUMN_LABEL
private static final int DEFAULT_ULPS
private static final double CUTOFF_THRESHOLD
private static final long serialVersionUID
private final LinearObjectiveFunction f
private final List<LinearConstraint> constraints
private final boolean restrictToNonNegative
private transient RealMatrix tableau
private final int numDecisionVariables
private final int numSlackVariables
private int numArtificialVariables
private final double epsilon
private final int maxUlps
SimplexTableau(LinearObjectiveFunction f, Collection<LinearConstraint> constraints, GoalType goalType, boolean restrictToNonNegative, double epsilon)
f
- Linear objective function.constraints
- Linear constraints.goalType
- Optimization goal: either GoalType.MAXIMIZE
or GoalType.MINIMIZE
.restrictToNonNegative
- Whether to restrict the variables to non-negative values.epsilon
- Amount of error to accept when checking for optimality.SimplexTableau(LinearObjectiveFunction f, Collection<LinearConstraint> constraints, GoalType goalType, boolean restrictToNonNegative, double epsilon, int maxUlps)
f
- linear objective functionconstraints
- linear constraintsgoalType
- type of optimization goal: either GoalType.MAXIMIZE
or GoalType.MINIMIZE
restrictToNonNegative
- whether to restrict the variables to non-negative valuesepsilon
- amount of error to accept when checking for optimalitymaxUlps
- amount of error to accept in floating point comparisonsprotected void initializeColumnLabels()
protected RealMatrix createTableau(boolean maximize)
maximize
- if true, goal is to maximize the objective functionpublic List<LinearConstraint> normalizeConstraints(Collection<LinearConstraint> originalConstraints)
originalConstraints
- original (not normalized) constraintsprivate LinearConstraint normalize(LinearConstraint constraint)
constraint
- reference constraintprotected final int getNumObjectiveFunctions()
private int getConstraintTypeCounts(Relationship relationship)
relationship
- relationship to countprotected static double getInvertedCoefficientSum(RealVector coefficients)
coefficients
- coefficients to sumprotected Integer getBasicRow(int col)
col
- index of the column to checkprotected void dropPhase1Objective()
private void copyArray(double[] src, double[] dest)
src
- the source arraydest
- the destination arrayboolean isOptimal()
protected PointValuePair getSolution()
protected void divideRow(int dividendRow, double divisor)
After application of this operation, the following will hold:
minuendRow = minuendRow - multiple * subtrahendRow
dividendRow
- index of the rowdivisor
- value of the divisorprotected void subtractRow(int minuendRow, int subtrahendRow, double multiple)
After application of this operation, the following will hold:
minuendRow = minuendRow - multiple * subtrahendRow
minuendRow
- row indexsubtrahendRow
- row indexmultiple
- multiplication factorprotected final int getWidth()
protected final int getHeight()
protected final double getEntry(int row, int column)
row
- row indexcolumn
- column indexprotected final void setEntry(int row, int column, double value)
row
- row indexcolumn
- column indexvalue
- for the entryprotected final int getSlackVariableOffset()
protected final int getArtificialVariableOffset()
protected final int getRhsOffset()
protected final int getNumDecisionVariables()
If variables are not restricted to positive values, this will include 1 extra decision variable to represent the absolute value of the most negative variable.
getOriginalNumDecisionVariables()
protected final int getOriginalNumDecisionVariables()
getNumDecisionVariables()
protected final int getNumSlackVariables()
protected final int getNumArtificialVariables()
protected final double[][] getData()
private void writeObject(ObjectOutputStream oos) throws IOException
oos
- stream where object should be writtenIOException
- if object cannot be written to streamprivate void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException
ois
- stream from which the object should be readClassNotFoundException
- if a class in the stream cannot be foundIOException
- if object cannot be read from the streamCopyright (c) 2003-2013 Apache Software Foundation