[数学建模笔记] 2.整数编程

例1：

例2：

 2.割平面法

基本思想：

1.如果松弛问题（P0）无解，则（P）无解；

2.如果（P0）的最优解为整数向量，则也是（P）的最优解；

3.如果（P0）的解含有非整数分量，则对（P0）增加割平面条件：即对（P0）增加一个线性约束，将（P0）的可行域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题（P）的可行解，得到问题（P1），重复上述的过程。

例1：

 基本步骤：

 程序流程：

3.0-1规划

例1：0-1变量的使用

投资问题：有600万元投资五个项目，收益如表，求利润最大的方案？

 

 例2：互斥约束问题

例3：固定费用问题

 4.指派问题

数学模型：

 非标准形式的指派问题：

1.最大化指派问题：

中最大元素为m，令

2.人数和工作数不等

人少工作多：添加虚拟的“人”，代价都为0

人多工作少：添加虚拟的工作，代价都为0

3.一个人可做多件工作

该人可化为几个相同的“人”

4.某工作一定不能由某人做

该人该工作的相应代价取足够大M

匈牙利算法：

参考：指派问题：匈牙利算法_Wonz-****博客_匈牙利算法 指派问题

例1：

 例2：

 

 例3：

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(:); %把矩阵c转换成向量
a=zeros(10,25); %10个方程（行+列），25个未知数
for i=1:5
    a(i,(i-1)*5+1:5*i)=1;
    a(5+i,i:5:25)=1;
end %此循环把指派问题转化为线性规划问题
b=ones(10,1);
[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1));
X=reshape(x,5,5) %重构成矩阵
opt=y