edu.princeton.cs.algs4

Class LinearProgramming

java.lang.Object

edu.princeton.cs.algs4.LinearProgramming

public class LinearProgramming
extends java.lang.Object

The LinearProgramming class represents a data type for solving a linear program of the form { max cx : Ax ≤ b, x ≥ 0 }, where A is a m-by-n matrix, b is an m-length vector, and c is an n-length vector. For simplicity, we assume that A is of full rank and that b ≥ 0 so that x = 0 is a basic feasible soution.

The data type supplies methods for determining the optimal primal and dual solutions.

This is a bare-bones implementation of the simplex algorithm. It uses Bland's rule to determing the entering and leaving variables. It is not suitable for use on large inputs. It is also not robust in the presence of floating-point roundoff error.

For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and 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 a m-by-n matrix, b is an m-length vector, and c is an n-length vector.

Method Summary

Modifier and Type	Method and Description
double[]	dual() Returns the optimal dual solution to this linear program
static void	main(java.lang.String[] args) Unit tests the LinearProgramming data type.
double[]	primal() Returns the optimal primal solution to this linear program.
double	value() Returns the optimal value of this linear program.

Methods inherited from class java.lang.Object

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

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 a m-by-n matrix, b is an m-length vector, and c is an n-length vector.

Parameters:

A - the m-by-b matrix

b - the m-length RHS vector

c - the n-length cost vector

Throws:

java.lang.IllegalArgumentException - unless b[i] >= 0 for each i

java.lang.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(java.lang.String[] args)

Unit tests the LinearProgramming data type.

Parameters:

args - the command-line arguments