LinearProgramming
LinearProgramming[c,m,b]
finds a vector x that minimizes the quantity c.x subject to the constraints m.x≥b and x≥0.
LinearProgramming[c,m,{{b1,s1},{b2,s2},…}]
finds a vector x that minimizes c.x subject to x≥0 and linear constraints specified by the matrix m and the pairs {bi,si}. For each row mi of m, the corresponding constraint is mi.x≥bi if si==1, or mi.x==bi if si==0, or mi.x≤bi if si==-1.
LinearProgramming[c,m,b,l]
minimizes c.x subject to the constraints specified by m and b and x≥l.
LinearProgramming[c,m,b,{l1,l2,…}]
minimizes c.x subject to the constraints specified by m and b and xi≥li.
LinearProgramming[c,m,b,{{l1,u1},{l2,u2},…}]
minimizes c.x subject to the constraints specified by m and b and li≤xi≤ui.
LinearProgramming[c,m,b,lu,dom]
takes the elements of x to be in the domain dom, either Reals or Integers.
LinearProgramming[c,m,b,lu,{dom1,dom2,…}]
takes xi to be in the domain domi.
Details and Options
- All entries in the vectors c and b and the matrix m must be real numbers.
- The bounds li and ui must be real numbers or Infinity or -Infinity.
- None is equivalent to specifying no bounds.
- LinearProgramming gives exact rational number or integer results if its input consists of exact rational numbers.
- LinearProgramming returns unevaluated if no solution can be found.
- LinearProgramming finds approximate numerical results if its input contains approximate numbers. The option Tolerance specifies the tolerance to be used for internal comparisons. The default is Tolerance->Automatic, which does exact comparisons for exact numbers, and uses tolerance
for approximate numbers. - SparseArray objects can be used in LinearProgramming.
- With Method->"InteriorPoint", LinearProgramming uses interior point methods.
Examples
open allclose allBasic Examples (1)
Scope (6)
Minimize 
, subject to constraint 
and lower bounds 
, 
:
Minimize 
, subject to constraint 
and bounds 
, 
:
Minimize 
, subject to constraint 
and upper bounds 
, 
:
Minimize 
, subject to constraint 
and implicit non-negative constraints:
Minimize 
subject to bounds 
and 
only:
Solve the same kind of problem, but with both variables integers:
Solve the same problem, but with the first variable an integer:
Solve larger LPs, in this case 200,000 variables and 10,000 constraints:
Generalizations & Extensions (1)
Objective, constraints, and bounds can all be specified as SparseArray:
Options (2)
Method (1)
Tolerance (1)
If an approximated solution is sufficient, a loose Tolerance option makes the solution process faster:
Properties & Relations (2)
A linear programming problem can also be solved using Minimize:
NMinimize or FindMinimum can be used to solve inexact linear programming problems:
Possible Issues (4)
The integer programming algorithm is limited to the machine-number problems:
The "InteriorPoint" method only works for machine numbers:
The "InteriorPoint" method may return a solution in the middle of the optimal solution set:
The "Simplex" method always returns a solution at a corner of the optimal solution set:
In this case the optimal solution set is the set of all points on the line segment between 
and 
:
The "InteriorPoint" method may not always be able to tell if a problem is infeasible or unbounded:
Neat Examples (1)
This expresses the Klee–Minty problem of dimension 
in LinearProgramming syntax:
Because scaling is applied internally, the simplex algorithm converges very quickly:
Implementation notes: Numerical and Related Functions