0-1型整数规划
二进制变量
相互排斥的约束条件
让未选中的约束条件恒成立
$$
y_i=\begin{cases}1,第i个约束起作用\
0,第i个约束不起作用, i = 1,2,…,m,
\end{cases}
$$
加一个充分大的常数M
$$
a_{i1}x_1+…+a_{in}x_n\leq b_i+(1-y_i)M,i=1,2,…,m,\
y_1+y_2+…+y_m=1
$$
固定费用问题
用
$$
y_j\varepsilon \leq x_j \leq y_jM ,\varepsilon是充分小的正常数,M是充分大的正常数
$$
代替上面的yi,之后照旧
指派问题
$$
min \sum_{i=1}^n\sum_{j=1}^nc_{ij}x{ij},\
s.t.\begin{cases}
\sum_{j=1}^nx_{ij}=1,i=1,…,n,\
\sum_{i=1}^nx_{ij}=1,i=1,…,n,\
x_{ij}=0或1,i,j=1,…,n.
\end{cases}
$$
cij:第i个人去做第j项工作需花费cij单位时间
系数矩阵,匈牙利算法。
蒙特卡洛法(随机取样)
1 | %mente.m |
整数线性规划的计算机求解
Lingo比MatLab好
因为matlab必须把所有决策变量变为一维决策向量