跳转至

整数规划⚓︎

约 3119 个字 预计阅读时间 10 分钟

4.1 问题和模型⚓︎

  • 决策变量必须取整数的规划问题被称为整数规划(IP)。整数规划分为线性和非线性。
  • 在整数规划中，如果所有决策变量都是非负整数，为纯整数规划，如果所有变量、系数、常数均为整数，为全整数规划，如果只有一部分决策变量是非负整数，其余变量可为非负数实数，为混合整数规划，当所有决策变量只能在0和1两个整数中取值，称为0-1整数规划。
  • 整数规划和线性规划的关系：

    通过仅仅对线性规划的最优解舍入得到的解不一定是最优解。

4.2 分支定界（Branch and Bound）法⚓︎

  • 给整数规划的松弛问题分别添加两个不同的约束条件，将其分解成两个线性规划问题（子问题），子问题的可行域包含了原整数规划的全部可行解，舍弃了一部分非整数可行解（包含松弛问题的非整数最优解）。此时整数点就在可行域的边界上，从而有机会成为子问题的最优解。一般情况下分支还可以和定界相结合，只考虑最优值比界限“好”的分支，剔除最优解比界限“差”的分支。界限也是可以变化的，常用“好”的界限替代“坏”的界限

  • 【表示】

  • 步骤

  • 先不考虑整数约束，求解IP的松弛问题LP，可以得到以下情况：

    1. 如果LP没有可行解，那么IP也没有可行解；停止；
    2. 如果LP有可行解，并符合IP的整数条件，那么LP最优解就是IP的最优解；
    3. 如果LP有最优解，但是不符合IP的整数条件，转入下一步，先设LP的最优解\(x^{(0)} = (b^{'}_1, b^{'}_2, ...,b^{'}_m, 0, 0,..0)^{T}\)，目标函数值是\(z^{(0)}\) ，其中\(b^{'}_i (i = 1,2,..,m)\)不全为整数；
  • 定界。记IP的最优值是\(z^*\)，把\(z^{(0)}\)作为\(z^*\)的上界，\(\overline{z} = z^{0}\)。记\(\overline{z} = z^{(0)}\)。利用观察法找到一个整数可行解\(x^{'}\)，并且用其相应的目标函数值\(z^{'}\)作为\(z^{*}\)的下界，记为\(\underline{z} = z^{'}\)，也可以令\(\underline{z} = \infty\)，则有\(\underline{z} \leq z^{*} \leq \overline{z}\)
  • 分支。在(LP)的最优解x^{(0)}中，任选一个不符合整数条件的变量，例如\(x_r = b^{'}_r\)（不为整数），以\([b^{'}_r]\) 表示不超过\(b^{'}_r\)的最大整数，构造两个约束条件：\(x_r \leq [b^{'}_r]\) 和\(x_r \geq [b^{'}_r]+1\)，将这两个约束条件分别加入问题IP，形成两个子问题（IP_1）和（IP_2)，再求解这两个子问题的松弛问题(LP_1) 和 (LP_2)的最优解；
  • 修改上下界，按照以下规则：1⃣️ 在各个分支问题中，找出目标函数值最大者作为新的上界；2⃣️ 从已符合整数条件的分支中找出目标函数最大者作为新的下界；
  • 比较和去支。在各个分支的目标函数值中，如果有小于\(z\)者，则去掉此支，表明此问题已经探清，否则继续分支。同样如果在分支过程中，相应的线性规划问题不可行，就不必再继续分支了。如此反复直到得到\(z = z^* = \overline{z}\)为止。也就得到最终最优解\(x^{*}\)。

4.3 割平面（Cutting Planes）法⚓︎

  • 基本思想：首先求解相应的线性规划，然后不断增加适当的线性约束，将原可行域割去不含整数可行解的一部分，最终得到一个具有整数坐标的极点的可行域，而该极点正好是原整数规划问题的最优解。

  • 关键在于怎么找到割平面方程，并且使得包含割平面约束在内的新约束问题的一个极点解成为最优整数解。

  • 纯整数割平面法的介绍：

  • 1⃣️ 用单纯形法求解(IP)对应的松弛问题(LP)

    • 1⃣️.1⃣️ 如果LP没有可行解，那么IP也没有可行解；终止；
    • 1⃣️.2⃣️ 如果LP有最优解，同时符合IP的整数条件，那么LP的最优解就是IP的最优解，停止计算；
    • 1⃣️.3⃣️ 如果LP有最优解，但是不符合IP的整数条件，那么转入下一步；
  • 2⃣️ 从LP的最优解中，任选一个不为整数的分量x_r，将最优单纯形表中的该行系数\(a^{'}_{ij}\)分解成整数部分和小数部分之和，并且以该行为源行，按下式子构造割平面方程：【补充】
  • 3⃣️ 将所得的割平面方程作为一个新的约束条件放回最优单纯形表中，同时增加一个单位列向量，用对偶单纯形法求出新的最优解，并返回1。

4.4 0-1整数规划⚓︎

  • 是整数规划的特殊情形，也是应用非常广泛的一类整数规划，其中的整数变量只能取0或者1。
  • 求解算法：完全枚举法和隐枚举法。
    • 完全枚举需要列举所有可能的情况\((2^n)\)种，不现实；
    • 隐枚举法：往往只有一部分解是可行的，因此只需要检查全部组合中的一部分就可以求出最优解，当发现某个变量组合不满足其中一个约束条件时，就不必检查其他条件是否可行。对可行解，其目标函数值也有优劣之分，如果发现一个可行解，可以依据目标函数值再构造一个过滤条件，如果一些变量组合的目标函数值更差，就不必验证可行性，如果可行解的目标函数更优，就更新过滤条件。

Abstract

待补充

4.5 指派问题⚓︎

在实际当中会遇到这样的问题：有n项不同的工作要完成，恰好有n人（或者n台设备）可以分别完成其中一个工作，但是每个人完成各个项目的效率不一样，应该指派哪一个人去完成哪一个任务？这样的问题就是指派问题。

4.5.1 指派问题模型⚓︎

  • 设\(c_{ij} > 0\)，表示第i个人完成第j项任务的效率（时间成本等），定义决策变量如下：
\[x_{ij} = \hspace{4pt} \left\{ \begin{aligned} 1, 如果指派第i人做第j项工作\\ 0, 若不指派第i人做第j个工作  \\  i, j = 1,2,...,n  \end{aligned}  \right. \]
\[min \hspace{4pt} z = \sum \limits^{n}_{i = 1} \sum \limits^{n}_{j = 1} c_{ij}x_{ij} \\
s.t \hspace{4pt} \left\{ \begin{aligned} \sum \limits^{n}_{i=1} x_{ij} = 1 , i = 1,2,..,n \\ \sum \limits^{n}_{j=1} x_{ij} = 1, j = 1,2,..,n   \\  x_{ij} = 0 \hspace{4pt} or \hspace{4pt} 1  \end{aligned}  \right.\]

数据主要集中在效益矩阵\(C\)中。

  • 性质：如果矩阵\(C\)的一行或者一列的各元素加上同一个实数得到矩阵\(B = (b_{ij})_{m \times n}\)，那么以\(B\)为系数矩阵的指派问题与原问题有相同的解。

4.5.2 匈牙利法⚓︎

  1. 变换系数矩阵\(c_{ij}\)为\(b_{ij}\)，使得在\(b_{ij}\)的各行各列中都出现0元素，也就是：
    1. 从\(c_{ij}\)的每行元素都减去该行的最小元素；
    2. 从所得的新系数矩阵的每列元素中减去该列的最小元素
  2. 进行试指派，以寻求最优解。
  3. 做最少的直线覆盖所有的0元素；
  4. 变换矩阵\(b_{ij}\)以增加0元素；

    找到覆盖所有0元素的最少直线，然后剩余矩阵就是一个没有0元素的矩阵 【详细补充】

4.5.3 非标准形式的指派问题⚓︎

一般处理方法是先将其转化成标准形式的指派问题，然后用匈牙利法求解。

  1. 最大化指派问题——设最大化指派问题的系数矩阵\(C = (c_{ij})\)，其中最大元素为\(m\)。令矩阵\(B = (b_{ij}) = (m - c_{ij})\)，则以\(B\)为系数矩阵的最小化指派问题和以\(C\)为系数矩阵的最大化指派问题有相同的最优解（也就是同时取反，那么最大就是最小值）
  2. 人数和事数不相等的指派问题：若人少事多，那么增加一些虚拟的“人”，其费用系数取0，若人多事少，那么添加一些虚拟的“事”，费用系数取0；
  3. 一个人可以做几件事的指派问题，若一个人可以做几件事，就将该人化作几个“人”来接受指派，这几个人做同一件事的系数都一样；
  4. 某事一定不能由某人做的指派问题——若某事一定不能由某人做，那么可以将对应的系数矩阵取足够大的整数M；

4.6 整数规划案例⚓︎

4.6.1 配送系统设计⚓︎

例题一： 排班问题⚓︎

  • 某公司上班时间段和所需人数如下，设每个人员上班时间为6小时，请问需要配备多少人员才能满足正常运转？
时间段 人数 时间段 人数
5-7 a 17-19 g
7-9 b 19 -21 h
9-11 c ... ...
11-13 d
13-15 e
15-17 f
Tips

设第一个时间内上班人员\(x_1\), 第二个上班人员为\(x_2\),..., 依次写约束；

例题二：含有相互排斥的约束条件的问题:⚓︎

  • 工序B每周工时约束\(0.3x_1 + 0.5x_2 \leq 150\); 现有另一种加工方式，相应工时约束变为\(0.2x_1 + 0.4x_2 \leq 130\)。但是只能从两种方式中选一种，如何建模？
Tips

令\(y_1\) （0-1变量）表示选择第一种；\(y_2\)（0-1变量）表示选择第二种， 有 \(0.3x_1 + 0.5x_2 \leq 150 + M ( 1- y_1)\)，和 \(0.2x_1 + 0.4x_2 \leq 130 + M(1-y_2)\)

  • 推广：从 \(p\) 个方式中，选择出\(q\)个不同的，就是引入\(p\)个约束条件，如何建模？

例题三：带固定费用的生产问题⚓︎

  • 给定多种产品及其资源约束，产品单价、成本、固定费用，如何安排？
Tips

引入0-1变量，乘在固定费用后面，写入目标函数中； 约束条件要加上 \(x_j \leq M_j y_j\)

例题四：机床加工问题⚓︎

  • 4台机床加工3产品，各个产品的机床加工顺序以及加工工时如图所示，如何在最短时间内加工完毕全部产品？
产品 情况
1 机床1 (a_11) ⇒ 机床3 (a_{13}) ⇒ 机床4 (a_{14})
2 机床1 (a_{21}) ⇒ 机床2 ( a_{22} ⇒ 机床4 (a_{24}) )
3 机床2 ⇒ 机床3

3个约束： 1. 同一个产品，必须在前一台机床上加工完毕再转到下一个机床 2. 对于同一个机床，如果正在某项产品加工，那么不能开始另一个机床加工； 3. 产品2的加工总时长不得超过d

Tips
  • x_{ij}：产品i在机床j上的开始加工时间 【constraint 1】；
  • y_j : 机床j先加工某产品（0-1变量） 【constraint 2】
  • 拓展：如果某台机床有多个产品，如何建模？ y_{jik} ?

例题五：从标准形到非标准形指派问题⚓︎

N人做N事，无其他约束⚓︎

  • 匈牙利法，经典指派问题

有事情某人不能做⚓︎

  • 系数矩阵加入大M。如果添虚拟人，同样要把M加上；

某事情必须做⚓︎

  • 如果添加虚拟人，任何虚拟人做这个事情的成本都为M；

人比事情少，一人只做一件事⚓︎

  • 添加虚拟人，不过全部置0；

人比事情少，特定人可做1～K件事⚓︎

  • 添加虚拟人，系数按照特定的那个（些）人来，如果矩阵非方阵，必须要补齐
    • 如果只有一人可以做两件事，其他都是一件事，可以：补一个虚拟人，他做每件事的成本是所有人中最低的那个人的成本；【一个技巧】
  • 如果有特定人可做K件事，则这些人都添加K-1个虚拟人，每个虚拟人的成本和对应的人相同，如果需要补齐矩阵，则补齐事情的成本系数均为0；

事情比人少，一人只做一件事⚓︎

  • 添加虚拟事，成本系数全部置0；