Solve linear programming problems
Finds the minimum of a problem specified by
$$\underset{x}{\mathrm{min}}{f}^{T}x\text{suchthat}\{\begin{array}{c}A\cdot x\le b,\\ Aeq\cdot x=beq,\\ lb\le x\le ub.\end{array}$$
f, x, b, beq, lb, and ub are vectors, and A and Aeq are matrices.
x = linprog(f,A,b)
x = linprog(f,A,b,Aeq,beq)
x = linprog(f,A,b,Aeq,beq,lb,ub)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
x = linprog(problem)
[x,fval] = linprog(...)
[x,fval,exitflag] = linprog(...)
[x,fval,exitflag,output] = linprog(...)
[x,fval,exitflag,output,lambda] = linprog(...)
linprog
solves linear programming problems.
x = linprog(f,A,b)
solves
min f'*x
such that A*x ≤ b
.
x = linprog(f,A,b,Aeq,beq)
solves
the problem above while additionally satisfying the equality constraints Aeq*x = beq
. Set A = []
and b = []
if
no inequalities exist.
x = linprog(f,A,b,Aeq,beq,lb,ub)
defines
a set of lower and upper bounds on the design variables, x
,
so that the solution is always in the range lb ≤ x ≤ ub
.
Set Aeq = []
and beq = []
if no equalities exist.
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
sets
the starting point to x0
. linprog
uses x0
only
with the activeset
algorithm. linprog
ignores x0
with
the interiorpoint
and simplex
algorithms.
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
minimizes
with the optimization options specified in options
.
Use optimoptions
to set these
options.
x = linprog(problem)
finds the minimum
for problem
, where problem
is
a structure described in Input Arguments.
Create the problem
structure by exporting
a problem from Optimization app, as described in Exporting Your Work.
[x,fval] = linprog(...)
returns
the value of the objective function fun
at the
solution x
: fval = f'*x
.
[x,fval,exitflag] = linprog(...)
returns
a value exitflag
that describes the exit condition.
[x,fval,exitflag,output] = linprog(...)
returns
a structure output
that contains information about
the optimization.
[x,fval,exitflag,output,lambda] = linprog(...)
returns
a structure lambda
whose fields contain the Lagrange
multipliers at the solution x
.
Note:
If the specified input bounds for a problem are inconsistent,
the output 
Function Arguments contains
general descriptions of arguments passed into linprog
. Options provides the functionspecific
details for the options
values.
problem 
 Linear objective function vector f 
 Matrix for linear inequality constraints  
 Vector for linear inequality constraints  
 Matrix for linear equality constraints  
 Vector for linear equality constraints  
lb  Vector of lower bounds  
ub  Vector of upper bounds  
 Initial point for x , active set algorithm
only  
 'linprog'  
 Options created with optimoptions 
Function Arguments contains
general descriptions of arguments returned by linprog
.
This section provides functionspecific details for exitflag
, lambda
,
and output
:
 Integer identifying the
reason the algorithm terminated. The following lists the values of  
 Function converged to a solution  
 Number of iterations exceeded  
 No feasible point was found.  
 Problem is unbounded.  

 
 Both primal and dual problems are infeasible.  
 Search direction became too small. No further progress could be made.  
 Structure containing the
Lagrange multipliers at the solution  
lower  Lower bounds  
upper  Upper bounds  
ineqlin  Linear inequalities  
eqlin  Linear equalities  
 Structure containing information about the optimization. The fields of the structure are:  
iterations  Number of iterations  
algorithm  Optimization algorithm used  
cgiterations  0 (interiorpoint algorithm only, included for backward compatibility)  
message  Exit message  
constrviolation  Maximum of constraint functions  
firstorderopt  Firstorder optimality measure 
Optimization options used by linprog
. Some
options apply to all algorithms, and others are only relevant when
using the interiorpoint algorithm. Use optimoptions
to
set or change options
. See Optimization Options Reference for detailed information.
All linprog
algorithms use the following
options:
Algorithm  Choose the optimization algorithm:
For information on choosing the algorithm, see Linear Programming Algorithms. 
 Display diagnostic information
about the function to be minimized or solved. The choices are 
 Level of display.

Use  Use the 
 Maximum number of iterations allowed, a positive integer. The default is:

 Termination tolerance on the function value, a positive scalar. The default is:

simplex
Algorithm OnlyThe 'simplex'
algorithm uses the following
option:
Use  If 
dualsimplex
Algorithm OnlyThe 'dualsimplex'
algorithm uses the following
options:
MaxTime  Maximum amount of time in seconds that the algorithm
runs. The default is 
Preprocess  Level of LP preprocessing prior to dual simplex algorithm
iterations. Choices are 
TolCon  Feasibility tolerance for constraints, a scalar from 
Find x
that minimizes
f(x) = –5x_{1} – 4x_{2} –6x_{3},
subject to
x_{1} – x_{2} + x_{3} ≤
20
3x_{1} +
2x_{2} + 4x_{3} ≤
42
3x_{1} +
2x_{2} ≤ 30
0
≤ x_{1}, 0 ≤ x_{2},
0 ≤ x_{3}.
First, enter the coefficients
f = [5; 4; 6]; A = [1 1 1 3 2 4 3 2 0]; b = [20; 42; 30]; lb = zeros(3,1);
Next, call a linear programming routine.
[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb);
Examine the solution and Lagrange multipliers:
x,lambda.ineqlin,lambda.lower x = 0.0000 15.0000 3.0000 ans = 0.0000 1.5000 0.5000 ans = 1.0000 0.0000 0.0000
Nonzero elements of the vectors in the fields of lambda
indicate
active constraints at the solution. In this case, the second and third
inequality constraints (in lambda.ineqlin
) and
the first lower bound constraint (in lambda.lower
)
are active constraints (i.e., the solution is on their constraint
boundaries).
The first stage of the algorithm might involve some preprocessing
of the constraints (see InteriorPoint Linear Programming). Several possible conditions
might occur that cause linprog
to exit with an
infeasibility message. In each case, the exitflag
argument
returned by linprog
is set to a negative value
to indicate failure.
If a row of all zeros is detected in Aeq
but
the corresponding element of beq
is not zero, the
exit message is
Exiting due to infeasibility: An allzero row in the constraint matrix does not have a zero in corresponding righthandside entry.
If one of the elements of x
is found not
to be bounded below, the exit message is
Exiting due to infeasibility: Objective f'*x is unbounded below.
If one of the rows of Aeq
has only one nonzero
element, the associated value in x
is called a singleton variable.
In this case, the value of that component of x
can
be computed from Aeq
and beq
.
If the value computed violates another constraint, the exit message
is
Exiting due to infeasibility: Singleton variables in equality constraints are not feasible.
If the singleton variable can be solved for but the solution violates the upper or lower bounds, the exit message is
Exiting due to infeasibility: Singleton variables in the equality constraints are not within bounds.
Note The preprocessing steps are cumulative. For example, even if your constraint matrix does not have a row of all zeros to begin with, other preprocessing steps may cause such a row to occur. 
Once the preprocessing has finished, the iterative part of the algorithm begins until the stopping criteria are met. (See InteriorPoint Linear Programming for more information about residuals, the primal problem, the dual problem, and the related stopping criteria.) If the residuals are growing instead of getting smaller, or the residuals are neither growing nor shrinking, one of the two following termination messages is displayed, respectively,
One or more of the residuals, duality gap, or total relative error has grown 100000 times greater than its minimum value so far:
or
One or more of the residuals, duality gap, or total relative error has stalled:
After one of these messages is displayed, it is followed by one of the following six messages indicating that the dual, the primal, or both appear to be infeasible. The messages differ according to how the infeasibility or unboundedness was measured.
The dual appears to be infeasible (and the primal unbounded).(The primal residual < TolFun.) The primal appears to be infeasible (and the dual unbounded). (The dual residual < TolFun.) The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(TolFun).(The primal residual < 10*TolFun.) The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(TolFun).(The dual residual < 10*TolFun.) The dual appears to be infeasible and the primal unbounded since the primal objective < 1e+10 and the dual objective < 1e+6. The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > 1e+6. Both the primal and the dual appear to be infeasible.
Note that, for example, the primal (objective) can be unbounded and the primal residual, which is a measure of primal constraint satisfaction, can be small.
linprog
gives a warning
when the problem is infeasible.
Warning: The constraints are overly stringent; there is no feasible solution.
In this case, linprog
produces a result that
minimizes the worst case constraint violation.
When the equality constraints are inconsistent, linprog
gives
Warning: The equality constraints are overly stringent; there is no feasible solution.
Unbounded solutions result in the warning
Warning: The solution is unbounded and at infinity; the constraints are not restrictive enough.
In this case, linprog
returns a value of x
that
satisfies the constraints.
At this time, the only levels of display, using the Display
option
in options
, are 'off'
and 'final'
;
iterative output using 'iter'
is not available.
Coverage and Requirements
For Large Problems 

A and Aeq should be sparse. 
[1] Dantzig, G.B., A. Orden, and P. Wolfe, "Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints," Pacific Journal Math., Vol. 5, pp. 183–195, 1955.
[2] Mehrotra, S., "On the Implementation of a PrimalDual Interior Point Method," SIAM Journal on Optimization, Vol. 2, pp. 575–601, 1992.
[3] Zhang, Y., "Solving LargeScale Linear Programs by InteriorPoint Methods Under the MATLAB Environment," Technical Report TR9601, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.