MATLAB File Help: cv.solveLP Index
cv.solveLP

Solve given (non-integer) linear programming problem using the Simplex Algorithm.

[z, res] = cv.solveLP(Func, Constr)
[...] = cv.solveLP(..., 'OptionName', optionValue, ...)

Input

Output

What we mean here by "linear programming problem" (or LP problem, for short) can be formulated as:

 Maximize c*x
  subject to  A*x <= b
              x >= 0

Where c is fixed 1-by-n row-vector, A is fixed m-by-n matrix, b is fixed m-by-1 column vector and x is an arbitrary n-by-1 column vector, which satisfies the constraints.

Simplex algorithm is one of many algorithms that are designed to handle this sort of problems efficiently. Although it is not optimal in theoretical sense (there exist algorithms that can solve any problem written as above in polynomial type, while simplex method degenerates to exponential time for some special cases), it is well-studied, easy to implement and is shown to work well for real-life purposes.

The particular implementation is taken almost verbatim from:

Introduction to Algorithms, 3rd edition by T. H. Cormen, C. E. Leiserson, R. L. Rivest and Clifford Stein.

In particular, the Bland's rule http://en.wikipedia.org/wiki/Bland%27s_rule is used to prevent cycling.

See also