数学建模之整数规划

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单位时间

系数矩阵，匈牙利算法。

蒙特卡洛法（随机取样）

%mente.m
function [f,g] = mente(x);
f=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);
g=[sum(x)-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];

%function.m
rand('state',sum(clock));  %初始化随机数发生器
p0=0;
tic;
for i=1:10^6 
    x=randi([0,99],1,5);  %产生一行五列的区间[0,99]的随机整数
    [f,g]=mente(x);
    if all(g<=0)
        if p0<f
            x0=x;p0=f;  %记录下当前较好的解
        end
    end
end
x0,p0
toc

整数线性规划的计算机求解

Lingo比MatLab好

因为matlab必须把所有决策变量变为一维决策向量