数学建模-规划问题

目录

    • 1.线性规划
    • 2.二次规划
    • 3.非线性规划
    • 4.0-1整数规划

1.线性规划

如果目标函数及约束条件均为线性函数,则称为线性规划问题!

Matlab规定线性规划的标准形式为:
m i n c T x ( 1 ) min\quad c^Tx \quad(1) mincTx(1)

s . t . A x ≤ b ( 2 ) s.t.\quad Ax\le b \quad(2) s.t.Axb(2)

其中,式(1)称为目标函数,式(2)称为约束条件 x x x 称为决策变量,满足约束条件的解称为可行解,使目标函数达到最小值的可行解称为最优解

例子:
m a x z = 2 x 1 + 3 x 2 ( 3 ) max \quad z=2x_1+3x_2 \quad(3) maxz=2x1+3x2(3)

s . t . { x 1 + x 2 ≤ 5 3 x 1 + 2 x 2 ≥ 6 x 1 + x 2 = 5 0 ≤ x 1 , x 2 ≤ 10 ( 4 ) s.t. \begin{cases} x_1+x_2\le 5\\ 3x_1+2x_2\ge6\\ x_1+x_2=5\\ 0\le x_1,x_2\le10\\ \end{cases} \quad(4) s.t.x1+x253x1+2x26x1+x2=50x1,x210(4)

c=[2;3];
a=[1,1
   -3,-2];
b=[5;-6];
aeq=[1,1];
beq=5;
lb=[0;0];
rb=[10;10];
[x,y,exitflag]=linprog(-c,a,b,aeq,beq,lb,rb);

数学建模-规划问题_第1张图片

2.二次规划

如果目标函数为自变量的二次函数,约束条件全是线性函数,则称为二次规划!

Matlab规定二次规划的标准形式为:
m i n 1 2 x T H x + f T x ( 5 ) min\quad \frac{1}{2}x^THx+f^Tx \quad(5) min21xTHx+fTx(5)

s . t . A x ≤ b ( 6 ) s.t.\quad Ax\le b \quad(6) s.t.Axb(6)

其中, H H H为实对称矩阵

例子:
m i n f ( x ) = 2 x 1 2 − 4 x 1 x 2 + 4 x 2 2 − 6 x 1 − 3 x 2 ( 7 ) min\quad f(x)=2x_1^2-4x_1x_2+4x_2^2-6x_1-3x_2 \quad(7) minf(x)=2x124x1x2+4x226x13x2(7)

s . t . { x 1 + x 2 ≤ 15 3 x 1 + 2 x 2 ≥ 6 x 1 + x 2 = 8 0 ≤ x 1 , x 2 ≤ 10 ( 8 ) s.t. \begin{cases} x_1+x_2\le 15\\ 3x_1+2x_2\ge6\\ x_1+x_2=8\\ 0\le x_1,x_2\le10\\ \end{cases} \quad(8) s.t.x1+x2153x1+2x26x1+x2=80x1,x210(8)

h=[4,-4
   -4,8];
f=[-6;-3];
a=[1,1
   -3,-2];
b=[15;-6];
aeq=[1,1];
beq=8;
lb=[0;0];
rb=[10;10];
[x,y,exitflag]=quadprog(h,f,a,b,aeq,beq,lb,rb);

3.非线性规划

如果目标函数及约束条件存在非线性函数,则称为非线性规划问题!

Matlab规定非线性规划的标准形式为:
m i n f ( x ) ( 9 ) min \quad f(x) \quad(9) minf(x)(9)

s . t . { A x ≤ b A e q ⋅ x = b e q c ( x ) ≤ 0 c e q ( x ) = 0 ( 10 ) s.t. \begin{cases} Ax\le b\\ Aeq\cdot x=beq\\ c(x)\le0\\ ceq(x)=0 \end{cases} \quad(10) s.t.AxbAeqx=beqc(x)0ceq(x)=0(10)

其中, c ( x ) 、 c e q ( x ) c(x)、ceq(x) c(x)ceq(x)是非线性向量函数。

例子:
m a x z = x 1 2 + 3 x 2 + x 3 ( 11 ) max \quad z=x_1^2+3x_2+x_3 \quad(11) maxz=x12+3x2+x3(11)
s . t . { x 1 + 4 x 2 + 2 x 3 ≥ 8 3 x 1 ⋅ 2 x 2 ≥ 6 x 1 + x 2 = 8 x 1 2 + x 3 = 10 0 ≤ x 1 , x 2 , x 3 ≤ 10 ( 12 ) s.t. \begin{cases} x_1+4x_2+2x_3\ge 8\\ 3x_1\cdot2x_2\ge6\\ x_1+x_2=8\\ x_1^2+x_3=10\\ 0\le x_1,x_2,x_3\le10\\ \end{cases} \quad(12) s.t.x1+4x2+2x383x12x26x1+x2=8x12+x3=100x1,x2,x310(12)

A=[1,4,2];
b=8;
aeq=[1,1,0];
beq=8;
lb=[0;0;0];
rb=[10;10;10];
[x,y,exitflag]=fmincon(@fun1,[2;6;6],-A,-b,aeq,beq,lb,rb,@fun2);

function f=fun1(x)
    f=x(1)^2+3*x(2)+x(3);
end

function [g,h]=fun2(x)
    g=-3*x(1)*2*x(2)+6;
    h=x(1)^2+x(3)-10;
end

4.0-1整数规划

规划中的变量限制为整数时,称为整数规划!

Matlab规定整数规划的标准形式为:
m i n f T x ( 13 ) min \quad f^Tx \quad(13) minfTx(13)

s . t . { A x ≤ b A e q ⋅ x = b e q x i = 0 或 1 ( 14 ) s.t. \begin{cases} Ax\le b \\ Aeq\cdot x=beq\\ x_i=0或1 \end{cases} \quad(14) s.t.AxbAeqx=beqxi=01(14)

例子:
m i n z = x 1 + 3 x 2 + x 3 ( 15 ) min \quad z=x_1+3x_2+x_3 \quad(15) minz=x1+3x2+x3(15)
s . t . { x 1 + 4 x 2 + 4 x 3 ≥ 4 x 1 + x 2 = 1 x i = 0 , 1 ( i = 1 , 2 , 3 ) ( 16 ) s.t. \begin{cases} x_1+4x_2+4x_3\ge 4\\ x_1+x_2=1\\ x_i=0,1(i=1,2,3) \end{cases} \quad(16) s.t.x1+4x2+4x34x1+x2=1xi=0,1(i=1,2,3)(16)

f=[1;3;1];
A=[1 4 4];
b=4;
aeq=[1,1,0];
beq=1;
lb=[0;0;0];
rb=[1;1;1];
[x,y,exitflag]=intlinprog(f,[1,2,3],A,b,aeq,beq,lb,rb);% [1,2,3]代表x1-x3都是整数

你可能感兴趣的