Fork me on GitHub

数学建模之整数规划

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

系数矩阵,匈牙利算法。

蒙特卡洛法(随机取样)

$W2U{1H1@V{[75]`{Q@F7JH.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
%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必须把所有决策变量变为一维决策向量

0%