[mathematical modeling / mathematical programming model]

Statement ： This article is written with reference to the online course of mathematical modeling Qingfeng .

Mathematical programming

• What is mathematical programming ？
  Research on mathematical programming ： Under given conditions （ constraint condition ）, How to follow a certain beam index （ Objective function ） To find a plan 、 The best plan for management .
  namely ： The problem of finding the extreme value of the objective function under certain constraints .

• The general form of mathematical programming
  General form ：min or max f(x) s.t Inequality constraints
  Objective function ：
  $$minz=6x_1+3x_2+4x_3$$
  constraint condition ：
  $$\{\begin{array}{c}{x}_1+2x_2-3x_3⩽80\\ x_1+x_2+x_3=120\\ x_1⩾30\\ 0⩽x_2⩽50\\ x_3⩾20\end{array}$$

• Classification of mathematical programming
  Mathematical programming problems mainly include linear programming , Nonlinear programming and integer programming, etc .

Linear programming

When the objective function and constraints are linear expressions , Then the mathematical programming problem at this time is the linear programming problem .1947 year , American mathematician Danzig proposed an algorithm to solve mathematical programming problems – Simplex .
Objective function ：
$$minz=6x_1+3x_2+4x_3$$
constraint condition ：
$$\{\begin{array}{c}{x}_1+2x_2-3x_3⩽80\\ x_1+x_2+x_3=120\\ x_1⩾30\\ 0⩽x_2⩽50\\ x_3⩾20\end{array}$$

Use matlab Solving linear programming problems

• matlab Standard form of linear programming in
  $$min{C}^{T}X\left(C=\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\\ c_n\end{array}\right),X=\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_n\end{array}\right),nIs\; the\; number\; of\; decision\; variables\right)$$
  $$S.t.\{\begin{array}{c}Ax\le b(Inequality\; constraints)\\ Aeqx=beq(Equality\; constraints)\\ lb\le x\le ub(Upper\; and\; lower\; bound\; constraints)\end{array}$$

matlab When solving linear programming problems , The input of solving the problem shall be specified in the format . such as :

1. The objective function to be solved must be the minimum , Therefore, if we get an objective function to solve the maximum value , You need to multiply the objective function -1, At this time, the minimum value solved is multiplied -1 Is the maximum value .
   $$maxz*-min-z$$
2. All inequalities must be of type less than or equal , At this point, if you have an inequality of type greater than or equal , You can multiply both ends of the inequality at the same time -1 To make the symbol take the opposite . For example, the following two formulas are equivalent ：
   $$\begin{gathered} 4x_1+6x_2-7x_3\ge 17 \\ -4x_1-6x_2+7x_3\le -17 \end{gathered}$$
   If only greater than or less than , Only add or subtract a very small value , Get a solution that meets the accuracy requirements
   $$4x_1-7x_2+x_3<4\Rightarrow 4x_1-7x_2+x_3\le 4-0.001$$
   example 1, For example, such a topic contains all special conditions ：
   $$\begin{gathered} maxz=2x_1+3x_2-5x_3 \\ S.t\{\begin{array}{c}{x}_1+x_2+x_3=7\\ 2x_1-5x_2+x_3\ge 10\\ x_1+3x_2+x_3\le 12\\ x_1,x_2,x_3\ge 0\end{array} \end{gathered}$$
   Its standard form is ：
   $$maxz*-min-z$$$$c=\left[\begin{array}{c}-2\\ -3\\ 5\end{array}\right],x=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right],A=\left[\begin{array}{c}-25-1\\ 121\end{array}\right],b=\left[\begin{array}{c}-10\\ 12\end{array}\right],Aeq=\left[\begin{array}{c}111\end{array}\right],beq=\left[\begin{array}{c}7\end{array}\right],lb=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$$

• Use matlab Command to solve linear programming problems

  [x, fval] = linprog(c, A, b, Aeq, beq, lb, ub, X0)
  

1. Return value x： Represents a group that obtains the optimal value x Value ;
2. Return value fval： The optimal value of the objective function ;
3. Parameter Division X0 Ditto outside ,X0 Represents the initial value of iterative solution , Generally, there is no need to give additional ;
4. For nonexistent constraints , Use [] placeholder ;
5. For variables without upper and lower bounds, you can use +inf and -inf It means no upper bound and no lower bound respectively .

for example ：
$$\begin{gathered} maxz=2x_1+3x_2-5x_3 \\ S.t\{\begin{array}{c}{x}_1+x_2+x_3=7\\ 2x_1-5x_2+x_3\ge 10\\ x_1+3x_2+x_3\le 12\\ x_1,x_2,x_3\ge 0\end{array} \end{gathered}$$

matlab The order is ：

%  Objective function coefficient 
c = [-2; -3; 5];
%  Inequality constraint number 
A = [-2 5 -1;
     1 3 1];
b = [-10; 12];

%  Equality constraints 
Aeq = [1 1 1];
beq = 7;

%  Upper and lower bound constraints 
lb = [0; 0; 0];

[x, fval] = linprog(c, A, b, Aeq, beq, lb);
fval = -fval;

The result is ：

Optimal solution found.

x =
    6.4286
    0.5714
         0

fval =
   14.5714

Nonlinear regularization

When the objective function or constraint condition is a nonlinear expression , Then the mathematical programming problem at this time is a nonlinear programming problem . The solution of nonlinear programming problems is usually much more difficult , At present, there is no general algorithm . Most algorithms use the initial value of selected decision variables , Search for the optimal solution .

Objective function ：
$$minz=x_1+3x_2+4x_3$$
constraint condition ：
$$\{\begin{array}{c}{x}_1+x_2-x_3⩽80\\ x_1+7x_2+x_3=120\\ 0⩽x_2^2⩽50\\ x_1,x_3⩾20\end{array}$$

Use matlab Solving nonlinear programming problems

• matlab Standard form of nonlinear programming in
  $$minf(x)$$$$S.t.\{\begin{array}{c}Ax\le b,Aeqx=beq(Linear\; constraints)\\ C\left(x\right)\le 0,Ceq(x)=0(Nonlinear\; constraints)\\ lb\le x\le ub(Upper\; and\; lower\; bound\; constraints)\end{array}$$

1. among C(x) and Ceq(x) They are nonlinear inequality constraints and nonlinear equality constraints .
2. C(x) and Ceq(x) The right side of must be zero . When it is not zero, you need to move .
3. The objective function to be solved must be the minimum , Therefore, if we get an objective function to solve the maximum value , You need to multiply the objective function -1, At this time, the minimum value solved is multiplied -1 Is the maximum value .
   $$maxz*-min-z$$
4. All inequalities must be of type less than or equal , At this point, if you have an inequality of type greater than or equal , You can multiply both ends of the inequality at the same time -1 To make the symbol take the opposite . For example, the following two formulas are equivalent ：
   $$\begin{gathered} 4x_1+6x_2-7x_3\ge 17 \\ -4x_1-6x_2+7x_3\le -17 \end{gathered}$$
   If only greater than or less than , Only add or subtract a very small value , Get a solution that meets the accuracy requirements .
   $$4x_1-7x_2+x_3<4\Rightarrow 4x_1-7x_2+x_3\le 4-0.001$$
   example 2, for example ：
   $$\begin{gathered} minf(x)=x_1^2+x_2^2+x_3^2+7 \\ S.t.\{\begin{array}{c}{x}_1^2-x_2+x_3^2\ge 0\\ x_1+x_2^2+x_3^2\le 20\\ -x_1-x_2^2+2=0\\ x_2+2x_3^2=3\\ x_1+x_2+x_3\le 5\\ x_1,x_2,x_3\ge 0\end{array} \end{gathered}$$
   Its standard form is ：
   $$S.t.\left(\begin{array}{c}A=\left[\begin{array}{c}111\end{array}\right],b=5,Aeq=[],beq=[],\\ C(x)=\left[\begin{array}{c}-x_1^2+x_2-x_3^2\\ x_1+x_2^2+x_3^2-20\end{array}\right],Ceq=\left[\begin{array}{c}-x_1-x_2^2+2\\ x_2+2x_3^2-3\end{array}\right],\\ lb=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\end{array}\right)$$

• Use matlab Command solving nonlinear programming
  matlab Function for solving nonlinear programming

  [x, val] = fmincon(@fun, X0, A, b, Aeq, beq, lb, ub, @nonfun, option)
  

1. @fun Represents the objective function , You need to write a separate m File storage objective function .

   function f = func(x)
   	f = x(1) ^ 2 + x(2) + ... - x(n) ^ 4
   end
   

   among ,f For the return value ,x The variable is a vector .

2. X0 For the initial value . Different from linear programming , The selection of initial value in nonlinear programming is very important , Because the result of linear programming is only a local optimal solution . To make the result as possible optimal The following methods can be used ：(1) Given different initial values , Find the optimal solution in it ;(2) First use Monte Carlo to get a solution , And use this solution as the initial value to solve .

3. A, b, Aeq, beq, lb, ub ditto .

4. @nonlfun Represents a nonlinear constraint function .

   function [c, ceq] = nonlfunc(x)
   	c = [ Nonlinear inequality constraints 1, Nonlinear inequality constraints 2... Nonlinear inequality constraints n]
   	c = [ Nonlinear equality constraints 1, Nonlinear equality constraints 2... Nonlinear equality constraints n]
   end
   

5. Use when some constraints do not exist [] Just occupy the space .

6. option Choice of solution algorithm .matlab A total of 4 Different options in , Each has its own practical conditions, advantages and disadvantages , It is advisable to use different algorithms to solve and select the optimal value in turn . The four algorithms are ：interior-point Interior point method ( If you do not actively modify the options, it is the default )、sqp Sequential quadratic programming 、active-set Effective set method and trust-region-reflective Trust region reflection algorithm .
   Change the method of solving algorithm ：

   option = optimoption('fmincon', 'Algorithm', ' Choose algorithm ')
   %  The available algorithms are  interior-point、sqp、active-set、trust-region-reflective
   

For example 2,matlab The solution code is ：
func.m( Objective function )

%  Objective function  

function f = func(x)
    f = x(1)^2 + x(2)^2 + x(3)^2 + 7;
end

nonlfunc.m( Nonlinear constraints )

%  Nonlinear constraints 

function [c,ceq] = nonlfunc(x)
    c = [-x(1)^2 + x(2) - x(3)^2;
         x(1) + x(2)^2 + x(3)^2 - 20];
    ceq = [-x(1) - x(2)^2 + 2;
           x(2) + 2*x(3)^2 - 3];
end

Solve the code ：

%  Linear inequality constraints 
A = [1 1 1];
b = 5;

%  Upper and lower bound constraints 
lb = [0 0 0]';

%  Initial value selection   Note that the more reasonable the initial value is ( Compliance constraint ), The better the value obtained, the faster the solution speed 
x0 = [1 1 1];

[x, fval] = fmincon(@func, x0, A, b, [], [], lb, [], @nonlfunc);

Solution result ：

x =
    0.5522    1.2033    0.9478
    
fval =
    9.6511

It can be seen that the selection of the initial value for this problem is still good , But the luck of choosing the initial value is not always very good . A certain strategy needs to be taken . for example , Monte Carlo simulation ：

%  Number of random groups 
n = 10000000;

%  Further compress the range of random numbers according to the last two constraints 
x1 = unifrnd(0, 5, n, 1); %  Generate n Group [0, 5] Random number between 
x2 = unifrnd(0, 5, n, 1);
x3 = unifrnd(0, 5, n, 1);

fmin = +inf;

for i = 1 : n
    xx = [x1(i) x2(i) x3(i)];
    if (xx(1)^2 - xx(2) + xx(3)^2 >=0 && xx(1) + xx(2)^2 + xx(3)^2 <=20)
        result = xx(1)^2 + xx(2)^2 + xx(3)^2 + 7;
        if result < fmin
            fmin = result;
            x0 = xx;
        end
    end
end

disp(x0); %  A set of initial values obtained by simulation are 0.0601    0.0043    0.0380
[x, fval] = fmincon(@func, x0, A, b, [], [], lb, [], @nonlfunc);

Integer regularization

Integer programming is a kind of mathematical programming problem with integer variables . It is divided into Integer linear programming and Integer nonlinear programming . at present , The popular integer programming algorithms can only solve integer linear programming .

Use matlab Solving integer programming problems – linear

[x, fval] = intlinprog(c, intcon, A, b, Aeq, beq, lb, ub)

1. intlinprog Initial value cannot be specified ;
2. Joined the intcon Parameters can specify which parameters must be integers . For example, there are three decision variables [x1, x2, x3], When intcon = [1, 3] Represents a decision variable 1 And decision variables 3 It has to be an integer .

for example ：
$$\begin{gathered} maxz=2x_1+3x_2-5x_3 \\ S.t\{\begin{array}{c}{x}_1+x_2+x_3=7\\ 2x_1-5x_2+x_3\ge 10\\ x_1+3x_2+x_3\le 12\\ x_1,x_2,x_{3\in Z}\\ x_1,x_2,x_3\ge 0\end{array} \end{gathered}$$
matlab Program ：

%  Objective function coefficient 
c = [-2; -3; 5];
%  Inequality constraint number 
A = [-2 5 -1;
     1 3 1];
b = [-10; 12];

%  Equality constraints 
Aeq = [1 1 1];
beq = 7;

%  Upper and lower bound constraints 
lb = [0; 0; 0];

[x, fval] = intlinprog(c, [1, 2, 3], A, b, Aeq, beq, lb);
fval = -fval;

Solution result ：

x =
    7.0000
         0
         0
         
fval =
   14.0000

0-1 Regularization

0-1 Programming is a special case of integer programming ,0-1 The value of planning variables can only be 0 or 1.

Use matlab solve 01 Programming problem – linear

[x, fval] = intlinprog(c, intcon, A, b, Aeq, beq, lb, ub)

It is the same as solving linear integer programming , Just change the upper and lower bounds to ：
$$lb=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right],ub=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]$$

Use integer linearity 01 Planning to solve 01 knapsack problem （ The capacity of the backpack is 30）：

goods	1	2	3	4	5	6	7	8	9	10
weight	6	3	4	5	1	2	3	5	4	2
value	540	200	180	350	60	150	280	450	320	120

matlab Solver ：

%  Objective function coefficient 
c = [-540; -200; -180; -350; -60; -150; -280; -450; -320; -120];
%  Inequality constraint number 
A = [6 3 4 5 1 2 3 5 4 2];
b = 30;

intcon = 1:10;

%  Upper and lower bound constraints 
lb = zeros(10, 1);
ub = ones(10, 1);

[x, fval] = intlinprog(c, intcon, A, b, [], [], lb, ub);
fval = -fval;

Solution result ：

x =
     1
     1
     0
     1
     0
     1
     1
     1
     1
     1
     
fval =
        2410