大家好，又见面了，我是你们的朋友全栈君。

2、整数规划

2.1 定义

规划中的变量 （部分或全部） 限制为整数时， 称为整数规划。 若在线性规划模型中，变量限制为整数，则称为整数线性规划。

2.2 分类

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

2.3 整数规划特点

1、原线性规划有最优解， 当自变量限制为整数后， 其整数规划解出现下述情况：

• 原线性规划和整数规划的最优解一致
• 整数规划无可行解
• 有可行解（但不是最优解）

2、整数规划最优解不能按照实数最优解简单取整而获得

2.4 求解的方法

1. 分枝定界法—可求纯或混合整数线性规划
2. 割平面法—可求纯或混合整数线性规划
3. 隐枚举法—求解“0-1”整数规划：
   1. 过滤隐枚举法；
   2. 分枝隐枚举法。
4. 匈牙利法—解决指派问题
5. 蒙特卡洛法—求解各种类型规划

2.5 分枝定界法

对有约束条件的最优化问题 （其可行解为有限数） 的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。把全部可行解空间反复地分割为越来越小的子集，称为分枝。对每个子集内的解集计算一个目标下界（对于最小值问题） ，这称为定界。

在每次分枝后， 凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

例 1

求

解：

1、先不考虑整数限制，直接按照线性规划求解，将此线性规划问题视为 B，得

再取 x1 = x2 = 0，得到 z 为 0，那么，以上便可求出可行解 z 的上下界

2、任选 x1 和 x2 进行分枝，取 x1 <= 4，x1 >= 5

可得

对 z 再定界，有

3、对 x2 进行分枝，取 x2 <= 2，x2 >= 3，有

再定界，有

4、若再对 x2 以 1 进行分支定界，无可行解，那么，可推断，最优解为

2.6 0 – 1 整数规划

0-1 整数规划指的是变量 xj 仅能取 0 或 1，即

2.6.1 投资场所的选定——相互排斥的计划

题目描述：某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置 Aj（j = 1, 2, 3…7）可供选择，规定

Aj 点的投资为 bj 元，每年利润为 cj 元，投资总额不能超过 B 元，问如何选择可使年利润最大？

解：

引入变量 xj，令

那么问题可写为

2.6.2 互斥问题的约束条件

1、

可写为

M 为充分大的数

2、

可写为

2.6.3 固定费用的问题

例 2

某工厂为了生产某种产品，有三种方式可供选择：

• xj 表示采用第 j 种方式生产时的产量
• cj 表示第 j 种方式生产时的变动成本
• kj 表示第 j 种方式生产时的固定成本

要求最小化生产成本。

解：

第 j 种生产方式的总成本为

引入 0 – 1 变量 yj，为

于是目标函数为

对于（3）式的规定，可改写为

前者和后者分别为充分小和充分大的数

2.7 0 – 1 整数规划的解法

2.7.1 过滤隐枚举法

穷举法是最容易想到的一种方法，但是计算量太大，因此设计一种仅检查变量取值的组合的一部分，称为过滤隐枚举法。分枝定界法也为过滤隐枚举法的一种。

例 3

解题思路：

1. 先取一个可行解，例如 (x1, x2, x3) = (1, 0, 0)，可行解 z = 3
2. 因为求的是最大值，因此求解过程中凡是 z < 3 的值均不考虑
3. 改进过滤条件，抬高过滤门槛

2.8 蒙特卡洛法（随机取样法）

前面讲的是线性整数规划，接下来说明非线性整数规划的问题，当数据量很大时，采用穷举法得到最优解不符合现实，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。

例 4

解：

若采用穷举法，共 10¹⁰ 个点，可随机分析 10⁶ 便可达到最优。

mente.m 如下：目标函数 f ，约束向量函数 g

mainint.m 如下：

上面代码中 sum(g <= 0) == 4 的原因是题目中 4 个约束条件需全部满足。

2.9 指派问题的计算机求解

采用 0 – 1 整数规划求解，使用到的 MATLAB 函数为 bintprog

例 5

解：

MATLAB 程序如下：

解得

bintprog 函数说明如下：参考 https://www.jianshu.com/p/9ad0f6d0a7df

• x = bintprog(f)
• x = bintprog(f, A, b)
• x = bintprog(f, A, b, Aeq, beq)

x 是解向量，f 是矩阵系数

A是一个矩阵，b是一个向量

• A，b和变量x={x1,x2,…,xn}一起，表示了线性规划中不等式约束条件
• A，b是系数矩阵和右端向量。
• Aeq和Beq表示了线性规划中等式约束条件中的系数矩阵和右端向量。

例 6

求 max=193x1+191x2+187x3+186x4+180x5+185x6;

st.
x5+x6>=1;

x3+x5>=1;

x1+x2<=1;

x2+x6<=1;

x4+x6<=1;

x1+x2+x3+x4+x5+x6=1;

解：

f=[-193;-191;-187;-186;-180;-185;];
a=[0 0 0 0 -1 -1;0 0 -1 0 -1 0;1 1 0 0 0 0;0 1 0 0 0 1;0 0 0 1 0 1];
b=[-1,-1,1,1,1]';
aeq=[1 1 1 1 1 1];
beq=[3];
x=bintprog(f,a,b,aeq,beq)

2.10 生产与销售计划问题

2.10.1 问题描述

某公司用两种原油（ A和B ）混合加工成两种汽油（甲和乙） 。甲、乙两种汽油含 A 原油的最低比例分别为 50％和 60％，每吨售价分别为 4800 元和 5600 元。该公司现有原油 A和B 的库存量分别为 500 吨和 1000 吨， 还可以从市场上买到不超过 1500吨的原油 A。原油 A的市场价为：购买量不超过 500 吨时的单价为 10000 元/吨；购买量超过 500 吨单不超过 1000 吨时，超过 500 吨的部分 8000 元/吨；购买量超过 1000 吨时，超过 1000 吨的部分 6000 元/吨。该公司应如何安排原油的采购和加工。

2.10.2 模型

设购买的 A 为 x 吨，那么支出 c(x) 为

设 A 用于生产甲、乙的数量分别为 x11，x12，B 用于生产甲、乙的数量分别为 x21，x22，那么利润为

限制条件为

2.10.3 模型化简

解法一

将 x 分解为三个量 x1，x2，x3，分别表示采集 10 千元/吨、8 千元/吨、6 千元/吨的 A 的数量，那么

目标函数变为

注意，只有当 x1 = 500 时，才可以 8 千元/吨的价格购买 x2，也就是

同理，只有当 x2 = 500 时，才可以 10 千元/吨的价格购买 x3，也就是

即

解法二

引入 0 – 1 问题，z1 =1，z2 =1，z3 =1 表示以 6 千元/吨、8 千元/吨、10 千元/吨的价格采购 A，上述问题转化为

解法三

成本函数的曲线为

分别记 b1 = 0，b2 = 500，b3 = 1000，当 x 属于第一个小区时，

同理，当 x 属于第二个小区时，

当 x 属于第三个小区时

当 x 属于第 k 个小区时， zk = 1，否则 zk = 0，那么