Python整数规划— 0−1型规划

        0 −1型整数规划是整数规划中的特殊情形，它的变量xj" role="presentation">xj$x_j$仅取值 0 或 1。这时xj" role="presentation">xj$x_j$ 称 为

0 −1变量，或称二进制变量。xj" role="presentation">xj$x_j$ 仅取值 0 或 1 这个条件可由下述约束条件：

0≤xj≤1" role="presentation">0≤xj≤1$0\le x_j\le 1$

        整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入 0 −1变 量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们 先介绍引入0 −1变量的实际问题。

---

1.数学建模过程

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

例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置（点）Ai(i=1,2,...,7)" role="presentation">Ai(i=1,2,...,7)$A_i(i=1,2,...,7)$可供选择。规定：

在东区。由 A1,A2,A3" role="presentation">A1,A2,A3$A_1,A_2,A_3$ 三个点中至多选两个；

在西区。由 A4,A5" role="presentation">A4,A5$A_4,A_5$ 两个点中至少选一个；

在南区，由 A6,A7" role="presentation">A6,A7$A_6,A_7$ 两个点中至少选一个。

如选用 Ai" role="presentation">Ai$A_i$点，设备投资估计为bi" role="presentation">bi$b_i$ 元，每年可获利润估计为 ci" role="presentation">ci$c_i$元，但投资总额不能 超过 B" role="presentation">B$B$ 元。问

应选择哪几个点可使年利润为最大？

解题时先引入0 −1变量xi(i=1,2,...,7)" role="presentation">xi(i=1,2,...,7)$x_i(i=1,2,...,7)$ 令

于是问题可列写成：

Maxz=∑i=17cixi{∑i=17bixi≤Bx1+x2+x3≤2x4+x5≥1x6+x7≥1,xi=0 or 1" role="presentation">Maxz=∑i=17cixi⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪∑7i=1bixi≤Bx1+x2+x3≤2x4+x5≥1x6+x7≥1,xi=0 or 1$\begin{array}{rl}& \mathrm{Max}z=\sum _{i=1}^7{c}_i{x}_i\\ & \{\begin{array}{l}\sum _{i=1}^7{b}_i{x}_i\le B\\ x_1+x_2+x_3\le 2\\ x_4+x_5\ge 1\\ x_6+x_7\ge 1,x_i=0\text{ or }1\end{array}\end{array}$

2.相互排斥的约束条件

有两个相互排斥的约束条件

5x1+4x2≤24 or 7x1+3x2≤45" role="presentation" style="position: relative;">5x1+4x2≤24 or 7x1+3x2≤45$5x_1+4x_2\le 24\text{ or }7x_1+3x_2\le 45$

引入0 −1变量 y ，则上述约束条件可改写为：

{5x1+4x2≤24+yM7x1+3x2≤45+(1−y)My=0 or 1" role="presentation" style="position: relative;">⎧⎩⎨⎪⎪5x1+4x2≤24+yM7x1+3x2≤45+(1−y)My=0 or 1$\{\begin{array}{l}5x_1+4x_2\le 24+yM\\ 7x_1+3x_2\le 45+(1-y)M\\ y=0\text{ or }1\end{array}$

其中 M 是充分大的数。 约束条件

x1=0 or 500≤x1≤800" role="presentation" style="position: relative;">x1=0 or 500≤x1≤800$x_1=0\text{ or }500\le x_1\le 800$

可改写为

{500y≤x1≤800yy=0 or 1" role="presentation" style="position: relative;">{500y≤x1≤800yy=0 or 1$\{\begin{array}{l}500y\le x_1\le 800y\\ y=0\text{ or }1\end{array}$

如果有 m 个互相排斥的约束条件：

ai1x1+⋯+ainxn≤bii=1,2,⋯,m" role="presentation" style="position: relative;">ai1x1+⋯+ainxn≤bii=1,2,⋯,m$a_{i1}{x}_1+\cdots +a_{in}{x}_n\le b_{i}i=1,2,\cdots ,m$

为了保证这 m" role="presentation" style="position: relative;">m$m$ 个约束条件只有一个起作用，我们引入 m" role="presentation" style="position: relative;">m$m$ 个0 −1变量yi(i=1,2,...,m)" role="presentation" style="position: relative;">yi(i=1,2,...,m)$y_i(i=1,2,...,m)$ 和一个充分大的常数 M" role="presentation" style="position: relative;">M$M$ ，而下面这一组m+1" role="presentation" style="position: relative;">m+1$m+1$个约束条件

ai1x1+⋯+ainxn≤bi+yiMi=1,2,⋯,my1+⋯+ym=m−1" role="presentation" style="position: relative;">ai1x1+⋯+ainxn≤bi+yiMi=1,2,⋯,my1+⋯+ym=m−1$\begin{array}{rl}& a_{i1}{x}_1+\cdots +a_{in}{x}_n\le b_i+y_{i}Mi=1,2,\cdots ,m\\ & y_1+\cdots +y_m=m-1\end{array}$

 就合于上述的要求。这是因为，由于（2），m 个 yi" role="presentation" style="position: relative;">yi$y_i$ 中只有一个能取 0 值，设 yi∗=0" role="presentation" style="position: relative;">y∗i=0$y_i^{\ast }=0$ ， 代入（1），就只有i=i∗" role="presentation" style="position: relative;">i=i∗$i=i^{\ast }$的约束条件起作用，而别的式子都是多余的。

3.关于固定费用的问题（Fixed Cost Problem）

        固定费用（固定成本）的问题不能用一般线 性规划来描述，但可改变为混合整数规划来解决，见下例。

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

• xj" role="presentation" style="position: relative;">xj$x_j$ 表示采用第 j 种方式时的产量；
• cj" role="presentation" style="position: relative;">cj$c_j$ 表示采用第 j 种方式时每件产品的变动成本；
• kj" role="presentation" style="position: relative;">kj$k_j$ 表示采用第 j 种方式时的固定成本。

为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为：

Pj={kj+cjxj, xj>00, xj=0j=1,2,3." role="presentation" style="position: relative;">Pj={kj+cjxj,0, xj>0 xj=0j=1,2,3.$P_j=\{\begin{array}{ll}{k}_j+c_j{x}_j,& x_j>0\\ 0,& x_j=0\end{array}j=1,2,3.$

在构成目标函数时，为了统一在一个问题中讨论，现引入0 −1变量yj" role="presentation" style="position: relative;">yj$y_j$ ，令

 于是目标函数

 minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)" role="presentation" style="position: relative;">minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)$minz=\left(k_1{y}_1+c_1{x}_1\right)+\left(k_2{y}_2+c_2{x}_2\right)+\left(k_3{y}_3+c_3{x}_3\right)$

（3）式这个规定可表为下述 3 个线性约束条件：

yjε≤xj≤yjM,j=1,2,3" role="presentation" style="position: relative;">yjε≤xj≤yjM,j=1,2,3$y_j\epsilon \le x_j\le y_{j}M,j=1,2,3$

 其中ε" role="presentation" style="position: relative;">ε$\epsilon$是一个充分小的正常数，M" role="presentation" style="position: relative;">M$M$ 是个充分大的正常数。当 xj" role="presentation" style="position: relative;">xj$x_j$> 0时 yj" role="presentation" style="position: relative;">yj$y_j$必须为 1；当 xj" role="presentation" style="position: relative;">xj$x_j$ = 0时只有 yj" role="presentation" style="position: relative;">yj$y_j$为 0 时才有意义。

举个栗子：

 Maxz=3x1−2x2+5x3{x1+2x2−x3≤2x1+4x2+x3≤4x1+x2≤34x2+x3≤6x1,x2,x3=0 or 1" role="presentation" style="position: relative;">Maxz=3x1−2x2+5x3⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪x1+2x2−x3≤2x1+4x2+x3≤4x1+x2≤34x2+x3≤6x1,x2,x3=0 or 1$\begin{array}{rl}& \mathrm{Max}z=3x_1-2x_2+5x_3\\ & \{\begin{array}{l}{x}_1+2x_2-x_3\le 2\\ x_1+4x_2+x_3\le 4\\ x_1+x_2\le 3\\ 4x_2+x_3\le 6\\ x_1,x_2,x_3=0\text{ or }1\end{array}\end{array}$

4.编程实现

使用Python实现

import pulp
InvestLP = pulp.LpProblem("0 −1型整数规划问题", sense=pulp.LpMaximize)  # 定义问题，求最大值
x1= pulp.LpVariable('x1', cat='Binary')  # 定义 x1
x2= pulp.LpVariable('x2', cat='Binary')  # 定义 x2
x3= pulp.LpVariable('x3', cat='Binary')  # 定义 x3
InvestLP += (3*x1 - 2*x2 + 5*x3 )  # 设置目标函数 f(x)
InvestLP += (x1 + 2*x2 - x3  <= 2)  # 不等式约束
InvestLP += (x1 + 4*x2 + x3 <= 4)
InvestLP += (x1 +x2 <= 3)
InvestLP += (4*x2 +x3 <= 6)
InvestLP.solve()
print(InvestLP.name)  # 输出求解状态
print("求解状态:", pulp.LpStatus[InvestLP.status])  # 输出求解状态
for v in InvestLP.variables():
    print(v.name, "=", v.varValue)  # 输出每个变量的最优值
print("目标函数值 =", pulp.value(InvestLP.objective))  # 输出最优解的目标函数值

输出结果：

0 −1型整数规划问题
求解状态: Optimal
x1 = 1.0
x2 = 0.0
x3 = 1.0
目标函数值 = 8.0