Wang Haihua
2022/04/21
🚅 🚋😜 🚑 🚔
整数规划问题是一种数学优化或可行性方案，其中部分或全部变量被限制为整数。在许多情况下，这个术语指的是整数线性规划(ILP)，其中目标函数和约束(除整数约束外)是线性的。
特别地，0-1整数线性规划的特殊情况，其中未知量为0或1，且只需要满足约束条件。
如果决策变量不全是离散的，则该问题称为混合整数规划问题。
在整数线性规划中，标准形式不同于标准形式。一个标准形式的整数规划是这样表示的(注意，它是一个$\mathbf {x}$向量):
$$\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}$$这是两种算法的步骤：
分枝定界法
step1不考虑整数约束的情况下求解得到最优解 $x^*$（一般不是整数）；
step2以该解的上下整数界限建立新的约束，将原整数规划问题变为两个问题（分枝）；
step3分别对两个子问题求解（不考虑整数约束），若解刚好为整数解则结束；若不为整数解则继续进行分枝；
step4以最开始的目标函数值作为上界，子问题求解中得到的任一整数解为下界（定界），对子问题进行剪枝，减小问题规模；
step5重复以上步骤直到得到最优解
割平面法
step1不考虑整数约束的情况下求解得到最优解 $x^*$（一般不是整数）；
step2过该解做一个割平面（二维情况下为一条直线），缩小可行域；
step3在缩小后的可行域中求最优解（不考虑整数约束）
step4重复步骤2和步骤3，直到最优解满足整数约束
我们沿用上一篇文章中提到的巧克力生产案例：
假设一家巧克力生产公司只生产两种类型的巧克力——A和B。这两种巧克力只需要牛奶和巧克力。制造A和B的每一个单位，需要以下数量:
- 每单位A需要1单位牛奶和3单位巧克力
- 每单位B需要1单位牛奶和2单位巧克力
公司厨房里有5个单位的牛奶和12个单位的巧克力。每卖出一笔，公司就赚一笔
- 每单位A卖出6卢比
- 每单位B卖出5卢比
现在，该公司希望实现利润最大化。它应该分别生产多少单位的A和B ?
很明显在这个问题的求解中决策变量（A,B的生产数量）应为整数，是个整数规划问题。
有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度length (cm)及重量weight (kg)是不同的，表中给出了每种包装箱的厚度、重量以及数量，每辆平板车有10.2m长的地方来装包装箱，载重量为40t，由于当地货运的限制，对$C_5,C_6,C_7$类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。要求给出最好的装运方式。
import pandas as pd
import numpy as np
load_carrier()
| length(cm) | weight(kg) | number | |
|---|---|---|---|
| C1 | 48.7 | 2000.0 | 8.0 |
| C2 | 52.0 | 3000.0 | 7.0 |
| C3 | 61.3 | 1000.0 | 9.0 |
| C4 | 72.0 | 500.0 | 6.0 |
| C5 | 48.7 | 4000.0 | 6.0 |
| C6 | 52.0 | 2000.0 | 4.0 |
| C7 | 64.0 | 1000.0 | 8.0 |