整数规划
《数学建模算法与应用》第二章<整数规划>学习笔记
概论
- 整数规划的定义
数学规划中的变量(部分或全部)限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 - 整数规划的分类
如不加特殊说明，则一般指整数线性规划。整数线性规划模型大致可分为两类:
(1)变量全限制为整数时，称纯(完全)整数规划。
(2)变量部分限制为整数时，称混合整数规划。 - 整数规划的特点
(1)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况。- 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
- 整数规划无可行解。
- 有可行解（当然存在最优解），但最优解值变差。
(2)整数规划最优解不能按照实数最优解简单取整而获得。
- 求解方法分类
(1)分支定界法——可求纯或混合整数线性规划。
(2)割平面法——可求纯或混合整数线性规划。
(3)求解“0-1”整数规划。- 过滤隐枚举法。
- 分支隐枚举法。
(4)匈牙利法——解决指派问题(“0-1”规划特殊情形)。
(5)蒙特卡洛法——求解各种类型规划。
0-1型整数规划
0-1型整数规划是整数规划中的特殊情形，它的变量仅取值0或1.这是被称为0-1变量，或称二进制变量。仅取值0或1这个条件可由下述约束条件$$0≤x_j≤1且x_j≤为整数$$所代替，是和一般整数规划的约束条件形式一致的。
互相排斥的约束条件
关于固定费用的问题
指派问题的数学模型
蒙特卡洛法(随机取样法)
蒙特卡洛方法也称为计算机随机模拟方法，它源于世界著名的赌城─—摩纳哥的Monte Carlo(蒙特卡洛)。它是基于对大量事件的统计结果来实现一些确定性问题的计算。使用蒙特卡洛方法必须使用计算机生成相关分布的随机数， Matlab给出了生成各种随机数的命令。
整数线性规划的计算机求解
对于整数线性规划问题，也可以使用Matlab的intlinprog函数求解，但使用Matlab软件求解数学规划问题有一个缺陷，即必须把所有的决策变量化成一维决策向量，实际上对于多维变量的数学规划问题，用Matlab软件求解，需要做一个变量替换，把多维决策变量化成一维决策向量，变量替换后，约束条件很难写出。
MATLAB求解混合整数线性规划的命令为
1 | [x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) |
现代优化算法
- 遗传算法
- 模拟退火算法
- 粒子群算法(蚁群、鱼群、鸟群)