Solving linear programming problems based on MATLAB

Catalog

introduce ： How to understand linear and nonlinear

1、 Linear programming

2、 Nonlinear programming

        1、 With constraints

        2、 No constraints

3、 Second planning problem

4、 The author concludes

---

introduce ：

Linear and nonlinear , It is often used to distinguish functions y = f （x） For arguments x Dependency of . Linear function is primary function , Its image is a straight line . Other functions are nonlinear functions , The image is not a straight line

In Mathematics , Linear relation refers to independent variable x And dependent variables yo Can be expressed as y=ax+b ,（a,b Constant ）, That is to say x And y There is a linear relationship between .

It can't be expressed as y=ax+b ,（a,b Constant ）, That is, nonlinear relationship , The nonlinear relationship can be quadratic , Cubic equifunction relation , It may not matter

1、 Linear programming (linprog)

Linear programming features ： Member variables are all primary items , And there are constraints , Find the maximum or minimum value

The standard form of linear programming requires that the objective function be minimized , The constraints take the equation , The variable is nonnegative , If it does not meet the conditions, it must be transformed into a standard form （ At most, a minus sign is added ）,

f yes x1,x2,x3 Find the coefficient in front of the maximum and minimum member variables , If the maximum value is required, it must first be converted to the standard form , Add a minus sign before the final output , Present as column vectors .

a Is the coefficient in front of the constraint member variable , The standard form is less than or equal to , If it is greater than or equal to, you need to convert plus minus sign , The coefficients of the same formula are presented as line vectors （,）, Different formulas are column vectors （;）

b Is the value of the constraint , Present as column vectors

aeq,beq They are the coefficients and values of equal cases , If the constraint is useless "[ ]" Instead of , Don't omit

The final output [x,y]=linprog(f,a,b,aeq,beq,lb,ub)   lb,ub Respectively, the upper and lower limits are generally determined by zeros(i,j) refer to i( Number of variables ) That's ok j Column zero matrix substitution, if there are specific conditions, specific analysis

f=[2;3;-5];
a=[-2 5 -1;1 3 1];
b=[-10;12];
aeq=[1 1 1];
beq=7;
[x,y]=linprog(-f,a,b,aeq,beq,zeros(3,1));
fprintf('x1=%.4f,x2=%.4f,x3=%.4f\nz:%.4f\n',x,-y);

---

---

---

2、 Nonlinear programming

        1、 No constraints  

 ①fminunc function

  Seeking unconstrained Multivariable The minimum value of a function

                     x = fminunc(fun,x0)

 x = fminunc(fun,x0) from x0 PM , Try to find fun A local minimum of the function described in x. spot x0 It can be scalar 、 Vector or matrix .

fmincon The function is default from what you give x0 Start searching for the center , Until the minimum value of the function is found , And return the distance x0 The minimum value of the nearest function corresponds to x value

In this way, we must determine the corresponding of the minimum value of the function in advance when calculating x Approximate range of values
Make sure we set the initial value x0 In what you ask x near , To reduce the amount of calculation

MATLAB Implementation steps

  1、 Defined function , And the file should be consistent with the function name

  2、 Define scripts , First write x0[i,j], Then call the function , Finally, look at the results of the workspace

---

contrast :

    fminbnd The univariate function finds the minimum value in the range

 

 

---

2、 With constraints （ The premise is nonlinear ）

     ①fmincon function

Basic grammar ：[x,fval]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)

 

  

---

---

3、 Second planning problem  

features ： Quadratic programming is a kind of nonlinear programming , If the objective function of a nonlinear programming is an independent variable x The quadratic function of , The constraints are all linear , It is called secondary Planning

        Standard form ——

 

 

 

First , vector x It's easy to write , because f(x) There are two variables x1 and x2, therefore

                                ​​​​​​​        ​​​​​​​        

  secondly , vector f Only with two variables x1 and x2 Is related to , therefore fTx=-2x1-6x2, therefore

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

  In this case ,, This is because x1 The square of the item （ namely x1x1） The coefficient is 1/2, So the first 1 Xing di 1 The elements of the column are 1=2*(1/2),x2 The square of the item （ namely x2x2） The coefficient is 1, So the first 2 Xing di 2 The elements of the column are 2=2*1,x1x2 term （ namely x2x1） The coefficient of is -1, So the first 1 Xing di 2 Column and the first 2 Xing di 1 The elements of the column are -1.

summary ： Let's set the matrix H The first i Xing di j The element size of the column is H(i,j), Second term xixj The coefficient of is a(i,j);

Attention is x1x1,x2x2 The coefficient is multiplied by 2

The author concludes ：

linear ：

linprog  It solves the maximum and minimum value problem of multivariate linear functions with constraints

nonlinear ：

In addition, the common point is that we need to define the objective function and it is a primary function

fminunc It solves the maximum and minimum value problem under the unconstrained condition of nonlinear multivariate

contrast ：fminbnd The solution is the maximum and minimum value of the nonlinear element variable in the given range

fmincon It solves the maximum and minimum value problem under nonlinear multivariate constraints

Second planning ：

quadprog The solution is nonlinear and the objective function is quadratic , The constraint condition is also the maximum and minimum value problem under linear conditions