Mathematica 9 is now available
SEARCH MATHEMATICA 8 DOCUMENTATION
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Mathematica > Mathematics and Algorithms > Matrices and Linear Algebra > Matrix-Based Minimization >
Built-in Mathematica SymbolTutorials »|See Also »|More About »

LinearProgramming

LinearProgramming[c, m, b]
finds a vector x which 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 which 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 siEqual1, or mi.xEqualbi if siEqual0, or mi.x≤bi if siEqual-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.
  • All entries in the vectors c and b and the matrix m must be real numbers.
  • None is equivalent to specifying no bounds.
  • LinearProgramming gives exact rational number or integer results if its input consists of exact rational numbers.
  • 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 10^(-6) for approximate numbers.
EXAMPLESCLOSE ALL
Basic Examples   (1)
Minimize x+y, subject to constraint x+2 y>=3, and implicit non-negative constraints:
Solve the problem with equality constraint x+2 y=3, and implicit non-negative constraints:
Solve the problem with equality constraint x+2 y<=3, and implicit non-negative constraints:
Minimize x+y, subject to constraint x+2 y>=3, and implicit non-negative constraints:
In[1]:=
Click for copyable input
Out[1]=
Solve the problem with equality constraint x+2 y=3, and implicit non-negative constraints:
In[2]:=
Click for copyable input
Out[2]=
Solve the problem with equality constraint x+2 y<=3, and implicit non-negative constraints:
In[3]:=
Click for copyable input
Out[3]=
Scope   (6)
Minimize x+y, subject to constraint x+2 y>=3, and lower bounds x>=-1, y>=-1:
Minimize x+y, subject to constraint x+2 y>=3, and bounds 2>=x>=-1, 1>=y>=-1:
Minimize 2 x-3 y, subject to constraint -x-2 y<=3, and upper bounds x<=1, y<=1:
Minimize x+y, subject to constraint 5 x+2 y>=3 and implicit non-negative constraints:
Minimize 2 x+3 y subject to bounds x>=-1 and y>=-2 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)
"InteriorPoint" is faster than "Simplex" or "RevisedSimplex", though it only works for machine-precision problems:
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 (1,0) and (0,1):
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 n in LinearProgramming syntax:
Because scaling is applied internally, the simplex algorithm converges very quickly:
New in 2 | Last modified in 6
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team