integer_programming_v181217

整数规划

  • 整数规划是指一类要求问题的解中的全部或一部分变量为整数的数学规划。
  • 整数规划是指规划中的变量(全部或部分)限制为整数,若在线性模型中,变量限制为整数,则称为整数线性规划
  • 目前所流行的求解整数规划的方法往往只适用于整数线性规划。
  • 从约束条件的构成又可细分为:
    • 线性整数规划
    • 二次整数规划
    • 非线性整数规划
  • 在线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求某些变量的解必须是整数。例如:
    • 当变量代表的是机器的台数,工作的人数或装货的车数等
  • 为了满足整数的要求,初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解,所以应该有特殊的方法来求解整数规划。
  • 在整数规划中,
    • 如果所有变量都限制为整数,则称为 纯整数规划
    • 如果仅一部分变量限制为整数,则称为 混合整数规划
    • 整数规划的一种特殊情形是 01规划 ,它的变数仅限于0或1。
    • 不同于线性规划问题,整数和01规划问题至今尚未找到一般的多项式解法。

发展历程

  • 整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的,30多年来发展出很多方法解决各种问题。
  • 解整数规划最典型的做法是逐步生成一个相关的问题,称它是 原问题的衍生问题
  • 对每个衍生问题又伴随一个比它更易于求解的 松弛问题(衍生问题称为松弛问题的源问题)
  • 通过松弛问题的解来确定它的源问题的归宿,即源问题应被舍弃,还是再生成一个或多个它本身的衍生问题来替代它。
  • 随即 ,再选择一个尚未被舍弃的或替代的原问题的衍生问题,重复以上步骤直至 不再剩有未解决的衍生问题 为止。
  • 现今比较成功又流行的方法是 分支定界法割平面法 ,它们都是在上述框架下形成的。

应用举例

组合最优化

  • 组合最优化通常都可表述为整数规划问题。
  • 两者都是在有限个可供选择的方案中,寻找满足一定约束的最好方案。
  • 有许多典型的问题反映整数规划的广泛背景。例如:
    • 背袋(或装载)问题
    • 固定费用问题
    • 和睦探险队问题(组合学的对集问题)
    • 有效探险队问题(组合学的覆盖问题)
    • 旅行推销员问题
    • 车辆路径问题等
  • 整数规划的应用范围极其广泛。它不仅在工业和工程设计和科学研究方面有许多应用,而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。

0-1规划

  • 0-1规划在整数规划中占有重要地位
  • 一方面因为许多实际问题,例如 指派问题选地问题送货问题 都可归结为此类规划
  • 另一方面任何有界变量的整数规划都与0-1规划等价,用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题
  • 求解0-1规划的常用方法是 分枝定界法 ,对各种特殊问题还有一些特殊方法,例如 求解指派问题用匈牙利方法就比较方便

整数规划分类

  • 整数规划又分为:
    1. 纯整数规划 :所有决策变量均要求为整数的整数规划
    2. 混合整数规划 :部分决策变量均要求为整数的整数规划
    3. 纯0-1整数规划 :所有决策变量均要求为0-1的整数规划
    4. 混合0-1规划 :部分决策变量均要求为0-1的整数规划
  • 整数规划与线性规划不同之处,只在于增加了整数约束。
  • 不考虑整数约束所得到的线性规划称为整数规划的线性松弛模型。

求解方法分类

  • 分枝定界法 :可求纯或混合整数线性规划
  • 割平面法 :可求纯或混合整数线性规划
  • 隐枚举法 :求解“0-1”整数规划
    • 过滤隐枚举法
    • 分枝隐枚举法
  • 匈牙利法 :解决指派问题(“0-1”规划特殊情形)
  • 蒙特卡洛法 :求解各种类型规划

分枝定界法

  • 分枝与定界内容
    • 对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系统搜索
  • 通常,把全部可行解空间反复地分割为越来越小的子集,称为 分枝
  • 并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称为 定界
  • 在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称 剪枝
  • 这就是分枝定界法的主要思路。
  • 分枝定界法可用于解纯整数或混合的整数规划问题。
  • 在本世纪六十年代初由 LandDoig 和 Dakin 等人提出的。
  • 由于这方法灵活且便于用计算机求解,所以现在它已是解整数规划的重要方法。
  • 目前已成功地应用于求解

    • 生产进度问题
    • 旅行推销员问题
    • 工厂选址问题
    • 背包问题
    • 分配问题
  • 分枝定界法求解整数规划(最大化)问题的步骤为:

  • 第0步

    • 将要求解的整数规划问题称为问题 A ,将与它相应的线性规划问题称为问题 B 。
      • 解问题 B 可能得到以下情况之一:
        • B 没有可行解,这时 A 也没有可行解,则停止.
        • B 有最优解并符合问题 A 的整数条件, B 的最优解即为 A 的最优解,则停止。
        • B 有最优解但不符合问题 A 的整数条件,记它的目标函数值为 $\overline{z}$ 。
      • 用观察法找问题 A 的一个整数可行解,
        • 一般可取 $x_j = 0,\ j= 1 ...,n $,试探,求得其目标函数值,并记作 $\underline{z}$ 。
        • 以$z^{*}$ 表示问题 A 的最优目标函数值;
        • 这时有 $ \underline{z} \leq z^{*} \leq \overline{z} $ 进行迭代。
  • 第1步

    • 分枝
      • 在 B 的最优解中任选一个不符合整数条件的变量 $x_j$ ,其值为 $b_j$ ,以 [$b_j$] 表示小于$b_j$ 的最大整数。构造两个约束条件:
      • $x_j \leq [b_j]$
      • $x_j \geq [b_j] + 1 $
      • 将这两个约束条件,分别加入问题 B ,求两个后继规划问题$B_1$ 和 $B_2$ 。不考虑整数条件求解这两个后继问题。
    • 定界
      • 对每个后继问题求解并作为各自分枝求解的结果,将其与其它问题的解作为一个结果集,在其中 找出最优目标函数值最大者作为新的上界 $\overline{z}$ 。
      • 从已符合整数条件的各分支中,找出目标函数值为最大者作为新的下界 $\underline{z}$ ,若无则 $\underline{z}$ 不变。
  • 第2步

    • 比较与剪枝
      • 各分枝的最优目标函数中若有小于 $\underline{z}$ 者,则剪掉这枝,即以后不再考虑了。
      • 若大于 $\underline{z}$ ,且不符合整数条件,则重复第一步骤。
      • 一直到最后得到 $z^{*}$ = $\underline{z}$ 为止。得最优整数解 $x_{j}^{*} ,\ j=1,...n$。

建模

$$ Max\ z=40x_1+90x_2 \\ $$

$$ s.t.\ \ \left\{ \begin{aligned} 9x_1+7x_2 \leq 56 \\ 7x_1+20x_2 \leq \ \ 70 \\ x_1,x_2 \geq \ \ 0 \\ \end{aligned} \right. $$

先不考虑整数限制解线性规划

In [9]:
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
    print("最优值",v.name,":",v.varValue,"单位")
最大值 Z 为 355.87786300000005 个单位
最优值 x1 : 4.8091603 单位
最优值 x2 : 1.8167939 单位

第一次分枝、定界、剪枝

  • 根据上一步骤运行的结果
    • 分枝:将 $x_1$ 划分为 $0 \leq x_1 \leq 4$ 和 $ x_1 \geq 5$ 两个分枝
    • 定界:$0 \leq z^* \leq 356$
  • 根据分枝情况继续运行求解
In [10]:
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob += x1 + 0 * x2 <= 4
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
    print("最优值",v.name,":",v.varValue,"单位")
最大值 Z 为 349.0 个单位
最优值 x1 : 4.0 单位
最优值 x2 : 2.1 单位

第二次分枝、定界、剪枝

  • 继续对 $x_2$ 进行分枝
  • 继续定界并剪枝
In [11]:
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob += x1 + 0 * x2 <= 4
prob += 0 * x1 + x2 <= 2
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
    print("最优值",v.name,":",v.varValue,"单位")
最大值 Z 为 340.0 个单位
最优值 x1 : 4.0 单位
最优值 x2 : 2.0 单位

0-1 型整数规划

  • 0-1 型整数规划是整数规划中的特殊情形,它的变量 $x_j$ 仅取值 0 或 1。这时 $x_j$ 称为 0-1 变量,或称二进制变量。
  • $x_j$ 仅取值 0 或 1 这个条件可由约束条件($0 \leq x_j \leq 1$,整数) 所代替,是和一般整数规划的约束条件形式一致的。
  • 在实际问题中,如果引入 0-1 变量,就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。

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

  • 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置(点)$A_i(i=1,2,...,7)$ 可供选择。规定:
    • 在东区。由 $A_1,A_2,A_3$ 三个点中至多选两个;
    • 在西区。由 $A_4,A_5$ 两个点中至少选一个;
    • 在南区,由 $A_6,A_7$ 两个点中至少选一个。
    • 如选用 $A_i$ 点,设备投资估计为 $b_i$ 元,每年可获利润估计为 $c_i$ 元,但投资总额不能超过 B 元。
  • 问应选择哪几个点可使年利润为最大?
  • 引入0-1变量
    • $x_i\ (i=1,2,...,7)$
    • $x_i = 1$, 当 $A_i$ 点被选中
    • $x_i = 0$, 当 $A_i$ 点没被选中
  • 建模

$$ Max\ z=\sum_{i=1}^7 {c_i x_i} \\ $$

$$ s.t.\ \ \left\{ \begin{aligned} \sum_{i=1}^7 {c_i x_i} \leq B \\ x_1+x_2+x_3 \leq 2 \\ x_4+x_4 \geq 1 \\ x_6+x_7 \geq 1 \\ x_i = 0\ 或\ 1 \\ \end{aligned} \right. $$

技巧:相互排斥的约束条件

  • 有 $5x_1 + 4x_2 \leq 24$ 或 $7x_1+3x_2 \leq 45$
  • 引入 $0-1$ 变量 $y$

$$ s.t.\ \ \left\{ \begin{aligned} 5x_1+4x_2 \leq 24 + yM \\ 7x_1+3x_2 \leq 45 + (1-y)M \\ y = 0\ 或\ 1 \\ 其中M是充分大的数 \end{aligned} \right. $$

  • 有 $x_1 =0$ 或 $500 \leq x_1 \leq 800$
  • 引入 $0-1$ 变量 $y$

$$ s.t.\ \ \left\{ \begin{aligned} 500y \leq x_1 \leq 800y \\ y = 0\ 或\ 1 \\ 其中M是充分大的数 \end{aligned} \right. $$

如果有 $m$ 个互相排斥的约束条件:
$a_{i1}x_1+...+a_{in}x_n \leq b_i \ \ \ i=1,2,...,m$
为了保证这 $m$ 个约束条件只有一个起作用,我们引入 $m$ 个$0-1$ 变量$\ \ y_i\ (i=1,2,...,m)$ 和一个充分大的常数 $M$
下面这一组 $m+1$ 个约束条件
$a_{i1}x_1+...+a_{in}x_n \leq b_i + y_i M\ \ \ i=1,2,...,m \ \ \ (1)$
$y_i+...+y_m = m-1 \ \ \ \ \ \ (2)$
就合于上述的要求。
这是因为,由于(2), $m$ 个$y_i$ 中只有一个能取 0 值,设 $y_{i^*} = 0$ ,代入(1),就只有$i=i^*$ 的约束条件起作用
而别的式子都是多余的。

关于固定费用的问题(Fixed Cost Problem)

  • 在讨论线性规划时,有些问题是要求使成本为最小。那时总设固定成本为常数,并在线性规划的模型中不必明显列出。
  • 但有些固定费用(固定成本)的问题不能用一般线性规划来描述,但可改变为混合整数规划来解决。

  • 某工厂为了生产某种产品,有几种不同的生产方式可供选择,如选定的生产方式投资高(选购自动化程度高的设备),由于产量大,因而分配到每件产品的变动成本就降低;反之,如选定的生产方式投资低,将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择,令:

    • $x_j$ 表示采用第 $j$ 种方式时的产量;
    • $c_j$ 表示采用第 $j$ 种方式时每件产品的变动成本;
    • $k_j$ 表示采用第 $j$ 种方式时的固定成本。
  • 为了说明成本的特点,暂不考虑其它约束条件。采用各种生产方式的总成本分别为: $$ P_j = \ \ \left\{ \begin{aligned} k_j + c_jx_j,\ 当 x_j > 0 \\ 0\ 当x_j = 0 \\ \end{aligned} \ \ \ \ j = 1,2,3. \right. $$

  • 引入 $0-1$ 变量

$$ y_j = \ \ \left\{ \begin{aligned} 1,\ \ \ \ \ \ j\ is\ in\ use(x_j > 0). \\ 0,j\ is\ not\ in\ use(x_j = 0). \\ \end{aligned} \right. $$

  • 此时目标函数为 $$ min\ z = (k_1y_1+c_1x_1)+(k_2y_2+c_2x_2)+(k_3y_3+c_3x_3) $$
  • 即 $$ y_j\varepsilon \leq x_j \leq y_jM, \ \ j=1,2,3 $$
  • 其中 $\varepsilon$ 是一个充分小的正常数, $M$ 是个充分大的正常数。

0-1型整数规划解法之一:过滤隐枚举法

  • 解 0-1 型整数规划最容易想到的方法,和一般整数规划的情形一样,就是穷举法
  • 即检查变量取值为 $0$ 或 $1$ 的每一种组合,比较目标函数值以求得最优解,这就需要检查变量取值的 $2^n$ 个组合。
  • 对于变量个数 $n$ 较大(例如 $100 > n$ ),这几乎是不可能的。
  • 因此常设计一些方法,只检查变量取值的组合的一部分,就能求到问题的最优解。
  • 这样的方法称为 隐枚举法(Implicit Enumeration)分枝定界法 也是一种隐枚举法。
  • 对有些问题隐枚举法并不适用,所以有时穷举法还是必要的。

蒙特卡洛法(随机取样法)

  • 上面的整数规划求解方法,主要是针对线性整数规划而言
  • 而对于非线性整数规划目前尚未有一种成熟而准确的求解方法,因为非线性规划本身的通用有效解法尚未找到,更何况是非线性整数规划。
  • 尽管整数规划由于限制变量为整数而增加了难度;然而又由于整数解是有限个,于是为枚举法提供了方便。
  • 当自变量维数很大和取值范围很宽情况下,企图用显枚举法(即穷举法)计算出最优值是不现实的,但是应用概率理论可以证明,在一定的计算量的情况下,完全可以得出一个满意解。

生产与销售计划问题

问题实例

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

建立模型

  • 问题分析
    • 安排原油采购、加工的目标是 利润最大
    • 给出的是两种汽油的售价和原油 A 的采购价,利润为销售汽油的收入与购买原油 A 的支出之差。
    • 难点在于原油 A 的采购价与购买量的关系比较复杂,是分段函数关系,能否及如何用线性规划、整数规划模型加以处理是关键所在。
  • 模型建立

    • 设原油 $A$ 的购买量为 $x$ (单位:吨)。根据题目所给数据,采购的支出 $c(x)$ 可表示为如下的分段线性函数(以下价格以 千元/吨 为单位):
    • 备注:当 x = 800 时,c(x) = 10*500 + 8*(800-500) = 10*500 + 8*800-8*500) = (10-8)*500 + 8*800 = 1000 + 8*800
    • 备注:当 x = 1200 时,c(x) = 10*500 + 8*500 + 6*(1200-1000) = 10*500 + 8*500 + 6*1200 - 6*1000 = (10+8-12)*500 + 6*1200 = 3000 + 6*1200 $$ c(x) = \ \ \left\{ \begin{aligned} 10x, 0 \leq x \leq 500 \\ 1000+8x, 500 \leq x \leq 1000 \\ 3000+6x, 1000 \leq x \leq 1500 \\ \end{aligned} \right. $$
  • 设原油 $A$ 用于生产甲、乙两种汽油的数量分别为 $x_{11}$ 和 $x_{12}$,原油 $B$ 用于生产甲、乙两种汽油的数量分别为$x_{21}$ 和 $x_{22}$ ,则总的收入为 $4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})$(千元)。

  • 于是目标函数(利润)为 $$ max\ z=4.8(x_{11}+x_{21}) + 5.6(x_{12}+x_{22})-c(x) $$

  • 约束条件包括加工两种汽油用的原油 $A$ 、原油 $B$ 库存量的限制,原油 $A$ 购买量的限制,以及两种汽油含原油 $A$ 的比例限制,它们表示为

$$ s.t. = \ \ \left\{ \begin{aligned} x_{11} + x_{12} \leq 500 + x \\ x_{21} + x_{22} \leq 1000 \\ x \leq 1500 \\ \dfrac{x_{11}}{x_{11}+x_{21}} \geq 0.5 \\ \dfrac{x_{12}}{x_{12}+x_{22}} \geq 0.6 \\ x_{11},\ x_{12},\ x_{21},\ x_{22},\ x \geq 0 \\ \end{aligned} \right. $$

  • 式中的 $c(x)$ 不是线性函数,而是一个非线性规划,对于这样用分段函数定义的 $c(x)$,一般的非线性规划软件难以输入和求解。需要将该模型化简求解。 ### 简化模型
  • 将原油$A$的采购量$x$分解为$x_1$,$x_2$,$x_3$,有 $$ c(x)=10x_1+8x_2+6x_3 $$ 且 $$ x=x_1+x_2+x_3 $$
  • 此时目标函数变为 $$ max \ z=4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})-(10x_1+8x_2+6x_3) $$ #### 神来之笔
  • 只有当以10千元每吨的价格购买$x_1=500$吨时,才能以8千元每吨的价格购买$x_2(>0)$,这个条件可以表示为 $$ (x_1-500)x_2=0 $$
  • 同理,有 $$ (x_2-500)x_3=0 $$
  • 此外,还有 $$ 0 \leq x_1, x_2, x_3 \leq 500 $$
  • 至此,可得线性方程组。

Python包求解整数规划问题

通过分枝、定界、剪枝使用pulp手动添加约束条件求解

In [12]:
from pulp import *
prob = LpProblem("problem1",LpMaximize)
x1 = LpVariable("x1",0,None,LpContinuous)
x2 = LpVariable("x2",0,None,LpContinuous)
prob += 40 * x1 + 90 * x2
prob += 9 * x1 + 7 * x2 <= 56
prob += 7 * x1 + 20 * x2 <= 70
prob += x1 + 0 * x2 <= 4   # 通过分枝、定界、剪枝添加的约束条件
prob += 0 * x1 + x2 <= 2   # 通过分枝、定界、剪枝添加的约束条件
prob.writeLP("problem1.lp")
prob.solve()
print("最大值 Z 为",value(prob.objective),"个单位")
for v in prob.variables():
    print("最优值",v.name,":",v.varValue,"单位")
最大值 Z 为 340.0 个单位
最优值 x1 : 4.0 单位
最优值 x2 : 2.0 单位

编写pulp函数求解

In [13]:
# -*- coding: utf-8 -*- 
import pulp as pulp 
def solve_ilp(objective , constraints):
    prob = pulp.LpProblem('LP1' , pulp.LpMaximize) 
    prob += objective 
    for cons in constraints:
        prob += cons
    print(prob)
    status = prob.solve()
    if status != 1:
        return None
    else:
        return [v.varValue.real for v in prob.variables()]
V_NUM = 2 
#变量,直接设置下限 
variables = [pulp.LpVariable('X%d'%i , lowBound = 0 , cat = pulp.LpInteger) for i in range(0 , V_NUM)] 
#目标函数 
c = [40 , 90] 
objective = sum([c[i]*variables[i] for i in range(0 , V_NUM)]) 
#约束条件 
constraints = [] 
a1 = [9 , 7] 
constraints.append(sum([a1[i]*variables[i] for i in range(0 , V_NUM)]) <= 56) 
a2 = [7 , 20] 
constraints.append(sum([a2[i]*variables[i] for i in range(0 , V_NUM)]) <= 70) 
#print(constraints)
res = solve_ilp(objective , constraints)
print(res)
LP1:
MAXIMIZE
40*X0 + 90*X1 + 0
SUBJECT TO
_C1: 9 X0 + 7 X1 <= 56

_C2: 7 X0 + 20 X1 <= 70

VARIABLES
0 <= X0 Integer
0 <= X1 Integer

[4.0, 2.0]
  • 两种方法获得相同的结果。

文中部分信息参考百度百科、CSDN等网络资料,如有侵权请联系改正。

◎ 欢迎参与讨论,请在这里发表您的看法、交流您的观点。