整数与非线性规划模版

整数规划

整数规划

• 整数线性规划用intlinprog求解
• 整数非线性规划无求解算法，只能模拟，使用蒙特卡罗或其他智能算法
• 个人觉得，选取决策变量是建模时及其关键的一步！

01整数规划

依然可以考虑使用求解器求解，只要限制lb=0，ub=1即可

一些例题

学校选址要求覆盖全部小区

$\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline\text{备选校址}&\text{B1}&\text{B2}&\text{B3}&\text{B4}&\text{B5}&\text{B6}\\\hline\text{覆盖小区}&\text{A1,A5,A7}&\text{A1,A2,A5,A8}&\text{A1,A3,A5}&\text{A2,A4,A8}&\text{A3,A6}&\text{A4,A6,A8}\\\hline\end{array}$

设$x_i=\begin{cases}1,&\text{在备选校址 }B_i\text{ 建学校},\\0,&\text{在备选校址 }B_i\text{ 不建学校}&\end{cases}$

约束条件应当是每个小区至少有一个学校覆盖，得到8个不等式

$$\begin{gathered}\text{s. t.}\begin{cases}x_1+x_2+x_3\geqslant1\\x_4+x_6\geqslant1\\x_3+x_5\geqslant1\\x_2+x_4\geqslant1\\x_5+x_6\geqslant1\\x_1\geqslant1\\x_2+x_4+x_6\geqslant1\end{cases}\end{gathered}$$

求解$\min\sum_{i=1}^6x_i$即可

### 指派问题

某公司购置了设备6台，想要分配给四个企业，每个企业得到设备后年利润如下，且每个企业至少分配得到一台设备，问如何分配使得年总利润最大

x_ij表示第i个机器分给了第j个企业

$$\begin{aligned}&\max\sum_{i=1}^6\sum_{j=1}^4c_{ij}x_{ij},\mathrm{~s.t.~}\begin{cases}\sum_{i=1}^6x_{ij}\geqslant1,j=1,2,3,4,\\\sum_{j=1}^4x_{ij}=1,i=1,\cdots,6,\\x_{ij}=0\text{ 或 }1,i=1,\cdots,6;j=1,2,3,4.\end{cases}\end{aligned}$$

通用方法：蒙特卡罗(随机数硬试)

%% 用蒙特卡洛解决工厂分配设备问题
clear;clc;
n = 10000; %模拟次数
C = [4,2,3,4;
     6,4,5,5;
     7,6,7,6;
     7,8,8,6;
     7,9,8,6;
     7,10,8,6];
 res_x = 0;
 res = 0;
 for k = 1:n
     flag = 1;
     x = randi([1,4],1,6); %生成一个1*6的向量，元素为1-4的整数，表示该设备分配给了哪个企业
     for j = 1 : 4 %检查每个企业至少分配一台
         
         if(ismember(j,x) == 0)
             flag = 0;
             break;
         end
     end
     
     if(flag == 1)
         sum = 0;
         for j = 1 : 6
             sum = sum + C(j, x(j));
         end
         
         if(sum > res)
             res = sum;
             res_x = x;
         end
     end
 end

非线性规划

利用matlab求解器求解，关键是合理建模，找好非线性约束。比如著名的飞机调度问题。

在约10000米的高空的某边长为160公里的正方形区域内，经常有若干架飞机作水平飞行，区域内每架飞机的位置和速度向量均有计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞，如果会碰撞，则应计算如何调整每架（包括新进入的）飞机飞行角度的方向角，以避免碰撞。现假定条件如下：
- ①不碰撞的标准为任意两架飞机的距离大于8公里
- ②飞机飞行方向角调整的幅度不应该超过30度
- ③所有飞机飞行速度均为每小时800公里
- ④进入该区域的飞机在到达区域边缘时与区域内飞机的距离应在60公里以上
- ⑤最多需考虑6架飞机
- ⑥不必考虑飞机离开此区域后的情况

请你对这个碰撞的飞行管理问题建立数学模型，列出计算步骤，要求飞机飞行方向角调整的幅度尽量小。并对一下数据进行计算（方向角误差不超过0.01°）

这是一个求解$\min\sum_{i=1}^6(\Delta\theta_i)^2$的问题，下面写约束条件。
任意两架飞机i，j在时间t时刻的距离 d_ij⁽²⁾(t) = [x_i(t) − x_j(t)]² + [y_i(t) − y_j(t)]² 求导 $$\begin{aligned}d_{ij}^{(2)}&'(t)=2[x_i(t)-x_j(t)][x_i(t)-x_j(t)]'+2[y_i(t)-y_j(t)][y_i(t)-y_j(t)]'\\&=2[x_i(t)-x_j(t)][v\cos(\theta_i+\Delta\theta_i)-v\cos(\theta_j+\Delta\theta_j)]+2[y_i(t)-y_j(t)][v\sin(\theta_i+\Delta\theta_i)-v\sin(\theta_j+\Delta\theta_j)]\end{aligned}$$ 容易看出其二阶导大于等于0，一阶导等于0求出极值点t₀因此只需要保证在极值点时刻 $$t_0=-\frac{(x_i^0-x_j^0)\left(\cos(\theta_i+\Delta\theta_i)-\cos(\theta_j+\Delta\theta_j)\right)+(y_i^0-y_j^0)\left(\sin(\theta_i+\Delta\theta_i)-\sin(\theta_j+\Delta\theta_j)\right)}{v[\left(\cos(\theta_i+\Delta\theta_i)-\cos(\theta_j+\Delta\theta_j)\right)^2+(\sin(\theta_i+\Delta\theta_i)-\sin(\theta_j+\Delta\theta_j))^2]}$$ 满足 d_ij⁽²⁾(t₀) > 64 飞机就是安全的

另外两个约束条件分别是 $$\mid\Delta\theta_i\mid<\frac\pi6$$ 与 $$\sqrt{\left(x_i(T_i)-x_j(t)\right)^2+\left(y_i(T_i)-y_j(t)\right)^2}>60(i\neq j)$$