matlab中linprog函数用法,[转载]matlab 线性规划函数-linprog

If the specified

input bounds for a problem are inconsistent, the output x

is x0 and the output fval is [].

Input Arguments

Function Arguments contains general descriptions of

arguments passed into linprog. Options provides the

function-specific details for the options values.

problem

f

Linear objective function vector f

Aineq

Matrix for linear inequality constraints

bineq

Vector for linear inequality constraints

Aeq

Matrix for linear equality constraints

beq

Vector for linear equality constraints

lb

Vector of lower bounds

ub

Vector of upper bounds

x0

Initial point for x, active set algorithm only

solver

'linprog'

options

Options structure created with optimset

Output Arguments

Function Arguments contains general descriptions of

arguments returned by linprog. This section provides

function-specific details for exitflag, lambda,

and output:

exitflag

Integer identifying the reason the algorithm terminated. The

following lists the values of exitflag and the

corresponding reasons the algorithm terminated.

1

Function converged to a solution x.

0

Number of iterations exceeded options.MaxIter.

-2

No feasible point was found.

-3

Problem is unbounded.

-4

NaN value was encountered during execution of the

algorithm.

-5

Both primal and dual problems are infeasible.

-7

Search direction became too small. No further progress could be

made.

lambda

Structure containing the Lagrange multipliers at the solution

x (separated by constraint type). The fields of the

structure are:

lower

Lower bounds lb

upper

Upper bounds ub

ineqlin

Linear inequalities

eqlin

Linear equalities

output

Structure containing information about the optimization. The

fields of the structure are:

iterations

Number of iterations

algorithm

Optimization algorithm used

cgiterations

0 (large-scale algorithm only, included for backward

compatibility)

message

Exit message

constrviolation

Maximum of constraint functions

firstorderopt

First-order optimality measure

Options

Optimization options used by linprog. Some options apply to all

algorithms, and others are only relevant when using the large-scale

algorithm. You can use optimset to set or change

the values of these fields in the options structure,

options. See Optimization Options Reference for

detailed information.

Medium-Scale and Large-Scale Algorithms

Both the medium-scale and large-scale algorithms use the

following options:

Diagnostics

Display diagnostic information about the function to be

minimized or solved. The choices are 'on' or the default

'off'.

Display

Level of display.

'off' displays no output.

'iter' displays output at each iteration. The

'iter' option only works with the large-scale and

medium-scale simplex algorithms.

'final' (default) displays just the final output.

LargeScale

Use large-scale algorithm when set to 'on' (default).

Use a medium-scale algorithm when set to 'off' (see

Simplex in Medium-Scale Algorithm Only). For

information on choosing the algorithm, see Choosing the

Algorithm.

MaxIter

Maximum number of iterations allowed, a positive integer. The

default is:

85 for the large-scale algorithm

10*numberOfVariables for the simplex algorithm

10*max(numberOfVariables, numberOfInequalities +

numberOfBounds) for the medium-scale active-set algorithm

TolFun

Termination tolerance on the function value, a positive scalar.

The default is:

1e-8 for the large-scale algorithm

1e-6 for the simplex algorithm

The option is not used for the medium-scale active-set

algorithm

Medium-Scale Algorithm Only

The medium-scale algorithms use the following option:

Simplex

If 'on', linprog uses the simplex algorithm. The

simplex algorithm uses a built-in starting point, ignoring the

starting point x0 if supplied. The default is

'off', meaning linprog uses an active-set algorithm. See

Medium-Scale Optimization for more information and an

example.

Examples

Find x that minimizes

f(x) =

–5x1 – 4x2

–6x3,

subject to

x1 –

x2 + x3 ≤ 20

3x1 + 2x2 +

4x3 ≤ 42

3x1 + 2x2 ≤ 30

0 ≤ x1, 0 ≤ x2, 0 ≤

x3.

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).

Algorithms

Large-Scale Optimization

The large-scale method is based on LIPSOL (Linear Interior Point

Solver, [3]), which is a variant of Mehrotra's

predictor-corrector algorithm ([2]), a primal-dual

interior-point method. A number of preprocessing steps occur before

the algorithm begins to iterate. See Large Scale Linear

Programming.

Medium-Scale Optimization

linprog uses a

projection method as used in the quadprog

algorithm. linprog is an

active set method and is thus a variation of the well-known

simplex method for linear

programming [1]. The algorithm finds an initial feasible

solution by first solving another linear programming problem.

Alternatively, you can use the simplex algorithm, described in

Medium-Scale linprog Simplex

Algorithm, by entering

options = optimset('LargeScale', 'off', 'Simplex', 'on')

and passing options as an input argument to

linprog. The simplex

algorithm returns a vertex optimal solution.

Note You cannot

supply an initial point x0 for linprog with either the large-scale method

or the medium-scale method using the simplex algorithm. In either

case, if you pass in x0 as an input argument,

linprog ignores

x0 and computes its own initial point for the

algorithm.

Diagnostics

Large-Scale Optimization

The first stage of the algorithm might involve some

preprocessing of the constraints (see Large Scale 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 all-zero row in the

constraint matrix does not have a zero in corresponding

right-hand-side 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 Large

Scale 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.

Medium-Scale Optimization

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.

Limitations

Medium-Scale Optimization

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.

Large-Scale Optimization

Large-Scale Problem Coverage and

Requirements

For Large Problems

A and Aeq should be sparse.