Package edu.princeton.cs.algs4
Class LinearProgramming
 Object

 edu.princeton.cs.algs4.LinearProgramming

public class LinearProgramming extends Object
TheLinearProgramming
class represents a data type for solving a linear program of the form { max cx : Ax ≤ b, x ≥ 0 }, where A is an mbyn matrix, b is an mlength vector, and c is an nlength vector. For simplicity, we assume that A is of full rank and that b ≥ 0 so that x = 0 is a basic feasible solution.The data type supplies methods for determining the optimal primal and dual solutions.
This is a barebones implementation of the simplex algorithm. It uses Bland's rule to determine the entering and leaving variables. It is not suitable for use on large inputs.
This computes correct results if all arithmetic performed is without floatingpoint rounding error or arithmetic overflow. In practice, there will be floatingpoint rounding error and this implementation is not robust in the presence of such errors.
For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description LinearProgramming(double[][] A, double[] b, double[] c)
Determines an optimal solution to the linear program { max cx : Ax ≤ b, x ≥ 0 }, where A is an mbyn matrix, b is an mlength vector, and c is an nlength vector.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double[]
dual()
Returns the optimal dual solution to this linear programstatic void
main(String[] args)
Unit tests theLinearProgramming
data type.double[]
primal()
Returns the optimal primal solution to this linear program.double
value()
Returns the optimal value of this linear program.



Constructor Detail

LinearProgramming
public LinearProgramming(double[][] A, double[] b, double[] c)
Determines an optimal solution to the linear program { max cx : Ax ≤ b, x ≥ 0 }, where A is an mbyn matrix, b is an mlength vector, and c is an nlength vector. Parameters:
A
 the mbyb matrixb
 the mlength RHS vectorc
 the nlength cost vector Throws:
IllegalArgumentException
 unlessb[i] >= 0
for eachi
ArithmeticException
 if the linear program is unbounded


Method Detail

value
public double value()
Returns the optimal value of this linear program. Returns:
 the optimal value of this linear program

primal
public double[] primal()
Returns the optimal primal solution to this linear program. Returns:
 the optimal primal solution to this linear program

dual
public double[] dual()
Returns the optimal dual solution to this linear program Returns:
 the optimal dual solution to this linear program

main
public static void main(String[] args)
Unit tests theLinearProgramming
data type. Parameters:
args
 the commandline arguments

