org.apache.commons.math.optimization.linear

Class SimplexSolver

java.lang.Object

org.apache.commons.math.optimization.linear.AbstractLinearOptimizer

org.apache.commons.math.optimization.linear.SimplexSolver

All Implemented Interfaces:

LinearOptimizer

public class SimplexSolver
extends AbstractLinearOptimizer

Solves a linear problem using the Two-Phase Simplex Method.

Since:

2.0

Version:

$Revision: 812831 $ $Date: 2009-09-09 10:48:03 +0200 (mer. 09 sept. 2009) $

Field Summary

Fields

Modifier and Type	Field and Description
private static double	DEFAULT_EPSILON Default amount of error to accept in floating point comparisons.
protected double	epsilon Amount of error to accept in floating point comparisons.

Fields inherited from class org.apache.commons.math.optimization.linear.AbstractLinearOptimizer

DEFAULT_MAX_ITERATIONS, function, goal, linearConstraints, nonNegative

Constructor Summary

Constructors

Constructor and Description
SimplexSolver() Build a simplex solver with default settings.
SimplexSolver(double epsilon) Build a simplex solver with a specified accepted amount of error

Method Summary

Methods

Modifier and Type	Method and Description
protected void	doIteration(SimplexTableau tableau) Runs one iteration of the Simplex method on the given model.
RealPointValuePair	doOptimize() Perform the bulk of optimization algorithm.
private java.lang.Integer	getPivotColumn(SimplexTableau tableau) Returns the column with the most negative coefficient in the objective function row.
private java.lang.Integer	getPivotRow(SimplexTableau tableau, int col) Returns the row with the minimum ratio as given by the minimum ratio test (MRT).
protected void	solvePhase1(SimplexTableau tableau) Solves Phase 1 of the Simplex method.

Methods inherited from class org.apache.commons.math.optimization.linear.AbstractLinearOptimizer

getIterations, getMaxIterations, incrementIterationsCounter, optimize, setMaxIterations

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_EPSILON

private static final double DEFAULT_EPSILON

Default amount of error to accept in floating point comparisons.

See Also:

Constant Field Values

epsilon

protected final double epsilon

Amount of error to accept in floating point comparisons.

Constructor Detail

SimplexSolver

public SimplexSolver()

Build a simplex solver with default settings.

SimplexSolver

public SimplexSolver(double epsilon)

Build a simplex solver with a specified accepted amount of error

Parameters:

epsilon - the amount of error to accept in floating point comparisons

Method Detail

getPivotColumn

private java.lang.Integer getPivotColumn(SimplexTableau tableau)

Returns the column with the most negative coefficient in the objective function row.

Parameters:

tableau - simple tableau for the problem

Returns:

column with the most negative coefficient

getPivotRow

private java.lang.Integer getPivotRow(SimplexTableau tableau,
                            int col)

Returns the row with the minimum ratio as given by the minimum ratio test (MRT).

Parameters:

tableau - simple tableau for the problem

col - the column to test the ratio of. See getPivotColumn(SimplexTableau)

Returns:

row with the minimum ratio

doIteration

protected void doIteration(SimplexTableau tableau)
                    throws OptimizationException

Runs one iteration of the Simplex method on the given model.

Parameters:

tableau - simple tableau for the problem

Throws:

OptimizationException - if the maximal iteration count has been exceeded or if the model is found not to have a bounded solution

solvePhase1

protected void solvePhase1(SimplexTableau tableau)
                    throws OptimizationException

Solves Phase 1 of the Simplex method.

Parameters:

tableau - simple tableau for the problem

Throws:

OptimizationException - if the maximal number of iterations is exceeded, or if the problem is found not to have a bounded solution, or if there is no feasible solution

doOptimize

public RealPointValuePair doOptimize()
                              throws OptimizationException

Perform the bulk of optimization algorithm.

Specified by:

doOptimize in class AbstractLinearOptimizer

Returns:

the point/value pair giving the optimal value for objective function

Throws:

OptimizationException - if no solution fulfilling the constraints can be found in the allowed number of iterations