5.整数规划

整数规划

1.定义

规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

2.分类

变量全限制为整数时，称纯（完全）整数规划。
变量部分限制为整数的，称混合整数规划。

3.特点

整数规划解和实数规划解可能一致，也可能不一致，甚至可能无解。
这里给出两个例子：
在这里插入图片描述

4.三种常用方法

隐枚举法—求解“0-1”整数规划
匈牙利法—解决指派问题（“0-1”规划特殊情形）
蒙特卡洛法—求解各种类型规划。

5.隐枚举法—求解“0-1”整数规划

定义：引入变量y取0或1，称为0 − 1变量，或称二进制变量。

好处：可以把相互排斥的条件转换成普通条件
在这里插入图片描述

在这里插入图片描述

6.指派问题

数学模型
在这里插入图片描述

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(:);
a=zeros(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);
intcon=1:25;
[x,fval] = intlinprog(c,intcon,[],[],a,b,zeros(25,1),ones(25,1));
x=reshape(x,[5,5]),fval

结果：
在这里插入图片描述

蒙特卡洛法—求解各种类型规划

在这里插入图片描述
示例1：

matlab代码：

clc, clear
x=unifrnd(0,12,[1,10000000]);
y=unifrnd(0,9,[1,10000000]);
pinshu=sum(y<x.^2 & x<=3)+sum(y<12-x & x>=3);
area_appr=12*9*pinshu/10^7

示例2:
在这里插入图片描述
matlab求解
先编写一个mente.m文件定义目标函数和约束条件，代码如下：

function [f,g]=mengte(x);
f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-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];

再在命令窗口输入生成随机数代码：

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