---

前言

整数规划基于线性规划，在线性规划的前提下，多了部分或全部决策变量是整数的约束条件。不特殊说明的话，整数规划就是指整数线性规划

分类

（1）变量全部为整数时，称作纯整数规划
（2）变量部分为整数时，称作混合整数规划

根据求解方法分类

（1）分枝定界算法——解决纯或混合整数规划
（2）割平面算法——解决纯或混合整数规划
（3）匈牙利算法——解决指派问题（“0-1”规划）

---

1、分枝定界算法和割平面算法

虽然这两个在解决问题所用的思路不同，但最终的公式是一样的。具体的算法内容就不详写了，这里仅写出如何利用matlab编写相应的代码。
在线性规划的约束条件下，加入新的约束条件，第几位决策变量是整数
$$\begin{gathered} \underset{x}{\min }{\mathbf{c}}^T\mathbf{x} \\ s.t.\{\begin{array}{l}\mathbf{x}(intcon)为整数，\\ \mathbf{A}\cdot \mathbf{x}\le \mathbf{b}\\ Aeq\cdot \mathbf{x}=beq\\ lb\le \mathbf{x}\le ub\end{array} \end{gathered}$$
引入了一个新的向量$\mathbf{i}\mathbf{n}\mathbf{t}\mathbf{c}\mathbf{o}\mathbf{n}$例如当$intcon=[1,3]$时，即表示第一位和第三位决策变量是整数
引入新的matlab求解整数规划的命令

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

这里举一个例子
例1 求解如下的混合整数规划问题
$$\begin{gathered} minz=-3x_1-2x_2-x_3 \\ s.t.\{\begin{array}{l}{x}_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12\\ x_1,x_2\ge 0\\ x_3=0or1\end{array} \end{gathered}$$
解 求解matlab程序为

clc;
clear;
c=[-3,-2,-1];
intcon=3;
A=ones(1,3);b=7;
Aeq=[4,2,1];beq=12;
lb=zeros(3,1);ub=[inf;inf;1];
[x,fval]=intlinprog(c,intcon,A,b,Aeq,beq,lb,ub)

2、匈牙利算法

介绍匈牙利算法之前，首先要介绍一下0-1规划问题，此时变量$x_j$仅取值0或1，而$x_j$称作0-1变量，此时约束条件为
$$0\le x_j\le 1,且x_j为整数$$

约束条件相互排斥

有时候，约束条件之间不是同时存在的，仅出现其中一个约束条件。例如有两种运输方式选择，用车运输或者用船运输。用车运输时约束条件为$5x_1+4x_2\le 24$，用船运输时约束条件为$7x_1+3x_2\le 45$。两种约束条件显然不能同时存在，这时引入一个0-1变量即可解决问题
$$y=\{\begin{array}{l}1，船运\\ 0，车运\end{array}$$
则约束条件可以改写为
$$\{\begin{array}{l}5x_1+4x_2\le 24+yM,\\ 7x_1+3x_2\le 45+(1-y)M,\\ y=0or1\end{array}$$
只要使得M足够大就可以。则当约束条件互斥时，只需要引入一个变量就可以充分表达约束条件。

指派问题

指派问题指的是指派一些人去某地，此时每个人都去且仅能去一个地方。当给了每人工作的时长，目标函数可能就是花费的总时间最少；当给了每个人工作的收益，目标函数可能就是总收益的最大值。
依旧是省略具体的算法，只展示了公式和代码部分
例2 分配n个人去做n项工作，每人做且仅做一项工作，若分配第i人去做第j项工作，需花费$c_{ij}$单位时间，问怎么分配工作才能使工人花费的总时间最少？
解： 引入0-1变量
$$x_{ij}=\{\begin{array}{l}1，第i人做第j项工作\\ 0，第i人不做第j项工作\end{array}i，j=1,2,...,n$$
则上述指派问题的数学模型为
$$\begin{gathered} min\sum _{i=1}^n\sum _{j=1}^n{c}_{ij}{x}_{ij} \\ s.t.\{\begin{array}{l}\sum _{j=1}^n{x}_{ij}=1,i=1,...,n,(1)\\ \sum _{i=1}^n{x}_{ij}=1,j=1,2,...,n(2)\\ x_{ij}=0or1,i,j=1,...n(3)\end{array} \end{gathered}$$
上述式子中，（1）式表示每个工作只能由一个人完成，（2）式表示每个人只能干一项工作。
特别需要说明的是，如果不限制每人工作的项目数，那么（2）式就可以去掉
这里给出一个具体的指派矩阵，便于后续matlab的代码编写
$$\left[\begin{array}{ccccc}3& 8& 2& 10& 3\\ 8& 7& 2& 9& 7\\ 6& 4& 2& 7& 5\\ 8& 4& 2& 3& 5\\ 9& 10& 6& 9& 10\end{array}\right]$$
则matlab的代码如下

c=[3,8,2,10,3;
   8,7,2,9,7;
   6,4,2,7,5;
   8,4,2,3,5;
   9,10,6,9,10];
   c=c(:);Aeq=zeros(10,25)%这里的10是共有10个式子，25是共有25个决策变量
for i=1:5
   	Aeq(i,(i-1)*5+1:5*i)=1;%对应着（2）
   	Aeq(5+i,i:5:25)=1;%对应着（1）
end
beq=ones(10,1);
intcon=1:25;
lb=zeros(25,1);
ub=ones(25,1);
x=intlinprog(c,intcon,[],[],Aeq,beq,lb,ub);
x=reshape(x,[5,5])

代码运行结果如下图所示