·一般模型

也即决策变量部分或全部为整数的规划问题就是整数规划

·整数线性规划问题分类

纯整数线性规划、混合整数线性规划、

0-1整数线性规划：决策变量只取0或1

·特点

可行域为离散点集；

最优值≤线性规划的目标函数值

不适用单纯形法求解

·使某个条件不起作用

条件为≥，则在右侧减M；条件为≤，则在右侧加M；

运用0-1变量示例如下

·作为决策变量

·步骤

单纯形法求松弛线性规划问题的最优表，如下图：

写出约束条件如下图：

将系数、常数项转化为整数或非负真分数(如-1/4x3项、7/4项)，如下图：

将整数部分、分数部分分列两边，如下图：

对①式，x1-x3为整数，且因为x1,x3≥0，所以3/4-3/4x3-1/4x4≤0

此例恰巧②式得出结果同上，

则割平面方程：3x3+x4-x5=3

将割平面方程作为约束条件加入松弛线性规划问题中再次求解该线性规划问题即可

分枝定界问题一般只有两个决策变量

·步骤：

图解法求松弛线性规划的最优解；

分枝：

 任选一个非整数解的变量xi，分两枝：xi≤【xi】(即对xi取整)和xi≥【xi】+1，分别将之加入约束条件中求解；

定界：

 两枝解若均为整数解，则选目标值更优的作为答案；

 两枝解一枝整数解，一枝非整数解，且整数解目标值更优的，选择整数解作为答案；

  两枝解一枝整数解X1，一枝非整数解，且非整数解目标值更优的，对非整数解中的非整数变量继续分枝，直至分枝中得出优于X1的整数解X2或分枝均不优于X1时停止，答案有X2选X2，无则选X1；

 两枝解均为非整数解的，选择更优的继续分枝，过程中一直保持比较；

·示例

分枝如下：

注意：得出4不要忘记和10/3作比较，假如得出的整数解不是4而是3，则还要对10/3这一枝继续分枝；

分支定界法配合清晰图解法使用。

·0-1隐枚举法

0-1隐枚举法是分支定界法的一种，但是决策变量只取0或1，可以穷举所有可行解及对应目标函数值以判断最优

·指派问题：n个人完成n项工作，怎样指派时间最少/成本最小，极小化问题

·匈牙利法：

效率矩阵①：每行减去该行最小元得②

②：每列减去该列最小元得③

③：圈出所有不同行且不同列的0元素，且用与圈出0个数相等的直线覆盖所有0元素，该数目=矩阵阶数时得出最优方案，＜阶数时得④

④：选取未被覆盖部分的最小元，未被覆盖的行减去该最小元，被覆盖的列加上该最小元得⑤

⑤：重复上述步骤直至圈0数目与阶数相等

最优方案⑥：将圈出0的位置在效率矩阵中对应圈出即可

·示例