优化模型：MATLAB整数规划

一、整数规划介绍

1.1 整数规划的定义

若规划模型的所有决策变量只能取整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。

1.2 整数规划的分类

整数规划模型大致可分为两类：

（1）变量全限制为整数时，称纯（完全）整数规划。

（2）变量部分限制为整数时，称混合整数规划。

1.3 求解方法分类

• 分支定界法——可求纯或混合整数线性规划。
• 割平面法——可求纯或混合整数线性规划。
• 隐枚举法——求解0-1整数规划
  • 过滤隐枚举法
  • 分枝隐枚举法
  • 匈牙利法——解决指派问题
  • 蒙特卡洛法——求解各类规划问题

    1.4 整数规划的数学模型

    min ⁡ x f T x \underset{x}{\min}\boldsymbol{f}^T\boldsymbol{x} xmin​fTx

    s . t . { x ( i n t c o n ) A ⋅ x ⩽ b A e q ⋅ x = b e q l b ⩽ x ⩽ u b s.t.\left\{ \begin{array}{c} \boldsymbol{x}\left( intcon \right)\\ \boldsymbol{A}\cdot \boldsymbol{x}\leqslant \boldsymbol{b}\\ Aeq\cdot \boldsymbol{x}=beq\\ lb\leqslant \boldsymbol{x}\leqslant ub\\ \end{array} \right. s.t.⎩ ⎨ ⎧​x(intcon)A⋅x⩽bAeq⋅x=beqlb⩽x⩽ub​

    式中： f \boldsymbol{f} f, x \boldsymbol{x} x, b \boldsymbol{b} b,beq,lb,ub为列向量； A \boldsymbol{A} A,Aeq为矩阵。

    二、案例分析

    Matlab求解混合整数线性规划的命令为

    [x,fval]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)这里是引用

    例1：利用matlab求解该整数线性规划模型。

    max ⁡ z = 100 x 1 + 60 x 2 \max z=100x_1+60x_2 maxz=100x1​+60x2​

    s . t . { 5 x 1 + 2 x 2 ⩽ 270 4 x 1 + 3 x 1 ⩽ 250 3 x 1 + 4 x 2 ⩽ 200 x 2 = 4 x 1 x 1 , x 2 为非负整数 s.t.\left\{ \begin{array}{c} 5x_1+2x_2\leqslant 270\\ 4x_1+3x_1\leqslant 250\\ 3x_1+4x_2\leqslant 200\\ x_2=4x_1\\ x_1,x_2\text{为非负整数}\\ \end{array} \right. s.t.⎩ ⎨ ⎧​5x1​+2x2​⩽2704x1​+3x1​⩽2503x1​+4x2​⩽200x2​=4x1​x1​,x2​为非负整数​

    MATLAB代码：

    clc,clear
    f=[-100;-60];
    intcon=[1,2];
    A=[5,2;4,3;3,4];
    b=[270;250;200];
    aeq=[-4,1];
    beq=0;
    lb=[0;0];
    ub=[inf;inf];
    [x,fval]=intlinprog(f,intcon,A,b,aeq,beq,lb,ub)
    disp("x1值:" + x(1))
    disp("x2值:" + x(2))
    disp("最大值：" + (-fval))
    

    求解结果:

    例2：利用matlab求解下列混合整数规划问题。

    min ⁡ z = − 3 x 1 − 2 x 2 − x 3 \min z=-3x_1-2x_2-x_3 minz=−3x1​−2x2​−x3​

    s . t . { x 1 + x 2 + x 3 ⩽ 7 4 x 1 + 2 x 2 + x 3 = 12 x 1 , x 2 ≫ 0 x 1 = 0 或 1 s.t.\left\{ \begin{array}{c} x_1+x_2+x_3\leqslant 7\\ 4x_1+2x_2+x_3=12\\ x_1,x_2\gg 0\\ x_1=0\text{或}1\\ \end{array} \right. s.t.⎩ ⎨ ⎧​x1​+x2​+x3​⩽74x1​+2x2​+x3​=12x1​,x2​≫0x1​=0或1​

    MATLAB代码：

    clc,clear
    f=[-3;-2;-1];
    intcon=3;%只有第3个变量为整数变量
    A=ones(1,3);
    b=7;
    aeq=[4,2,1];
    beq=12;
    lb=zeros(3,1);
    ub=[inf;inf;1];
    [x,fval]=intlinprog(f,intcon,A,b,aeq,beq,lb,ub)
    

    求解结果：