非线性整数规划问题

非线性整数规划问题是指目标函数和约束条件都可能是非线性的，且变量为整数的优化问题。

在 MATLAB 中，没有专门的函数来求解非线性整数规划问题，但是可以通过蒙特卡洛方法来求得近似解。

蒙特卡洛方法

蒙特卡洛方法是一种用随机数来解决问题的方法，它的基本思想是：通过随机的方法来模拟问题的解，从而得到问题的近似解。

例
求解下列非线性整数规划问题：

$$\begin{equation} \max \quad Z=x_{1}^2 + x_{2}^2 + 3x_{3}^2 + 4x_{4}^2 + 2x_{5}^2 - 8x_{1} - 2x_{2} - 3x_{3} - x_{4} - 2x_{5} \end{equation}$$

$$\begin{equation} \text { s.t. } \left\{ \begin{array}{c} x_{1} + x_{2} + x_{3} + x_{4} + x_{5} \leq 400 \\ x_{1} + 2x_{2} + 2x_{3} + x_{4} + 6x_{5} \leq 800 \\ 2x_{1} + x_{2} + 6x_{3} \leq 200 \\ x_{3} + x_{4} + 5x_{5} \leq 200 \\ 0 \leq x_{i} \leq 99, \quad i=1,2,3,4,5 \\ x_{i} \in \mathbb{Z}, \quad i=1,2,3,4,5 \end{array} \right. \end{equation}$$

解

首先，我们需要定义目标函数和约束条件函数：

1
2
3
4

% 目标函数
function [z] = objfun(x)
  z = x(1)^2 + x(2)^2 + 3*x(3)^2 + 4*x(4)^2 + 2*x(5)^2 - 8*x(1) - 2*x(2) - 3*x(3) - x(4) - 2*x(5);
end

1
2
3
4
5
6
7
8
9
10
11
12

% 约束条件函数
function [flag] = confun(x)
  c = [x(1) + x(2) + x(3) + x(4) + x(5) - 400;
       x(1) + 2*x(2) + 2*x(3) + x(4) + 6*x(5) - 800;
       2*x(1) + x(2) + 6*x(3) - 200;
       x(3) + x(4) + 5*x(5) - 200];
  if all(c <= 0)
      flag = 1;
  else
      flag = 0;
  end
end

然后就可以开始蒙特卡洛模拟了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

% 蒙特卡洛模拟
n = 1000; % 模拟次数
lb = zeros(1, 5); % 变量下界
ub = 99*ones(1, 5); % 变量上界
sol = []; % 保存满足约束条件的解
fval = -inf; % 保存最大值
for i = 1:n
    x = floor(lb + (ub - lb + 1).*rand(1, 5)); % 生成随机解
    if confun(x) == 1 % 判断是否满足约束条件
        z = objfun(x); % 计算目标函数值
        if z > fval % 更新最大值
            fval = z;
            sol = x;
        end
    end
end

模拟次数越多，得到的解就越接近最优解，但是计算时间也会越长。

当模拟次数为 1,000 时，得到的近似解为：

1
2
3
4
5
6
7

>> sol
sol =
    5    45    17    91     9

>> fval
fval =
    35913

当模拟次数为 100,000 时，得到的近似解为：

1
2
3
4
5
6
7

>> sol
sol =
    23    91     5    99    11

>> fval
fval =
    47829

当模拟次数为 10,000,000 时，得到的近似解为：

1
2
3
4
5
6
7

>> sol
sol =
    47    98     1    99    16

>> fval
fval =
    50826

可以看到，当模拟次数越多时，得到的近似解越接近最优解。

本题若使用显式枚举法，需要枚举$100^5 = 10^{10}$ 种解，而蒙特卡洛模拟只需要模拟$10^7$ 次，便可以得到一个精度较高的近似解。

在精度要求不那么严格的情况下，蒙特卡洛模拟是一种非常有效的方法。