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

╰+哭是因爲堅強的太久メ 2023-09-28 21:24 3阅读 0赞

> 0 −1型整数规划是整数规划中的特殊情形，它的变量![x\_\{j\}][x_j]仅取值 0 或 1。这时![x\_\{j\}][x_j] 称 为
> 
> 0 −1变量，或称二进制变量。![x\_\{j\}][x_j] 仅取值 0 或 1 这个条件可由下述约束条件：
> 
> ![0\\leq x\_\{j\}\\leq 1][0_leq x_j_leq 1]
> 
> 整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入 0 −1变 量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们 先介绍引入0 −1变量的实际问题。

--------------------

###  ###

## 1.数学建模过程 ##

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

例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置（点）![A\_\{i\}(i=1,2,...,7)][A_i_i_1_2_..._7]可供选择。规定：

在东区。由 ![A\_\{1\},A\_\{2\},A\_\{3\}][A_1_A_2_A_3] 三个点中至多选两个；

在西区。由 ![A\_\{4\},A\_\{5\}][A_4_A_5] 两个点中至少选一个；

在南区，由 ![A\_\{6\},A\_\{7\}][A_6_A_7] 两个点中至少选一个。

如选用 ![A\_\{i\}][A_i]点，设备投资估计为![b\_\{i\}][b_i] 元，每年可获利润估计为 ![c\_\{i\}][c_i]元，但投资总额不能 超过 ![B][] 元。问

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

解题时先引入0 −1变量![x\_\{i\}(i=1,2,...,7)][x_i_i_1_2_..._7] 令

![54c2fbf28f3b4db5855d7e2ebb988cf9.png][]

于是问题可列写成：

![\\begin\{aligned\} &\\operatorname\{Max\} \\quad z=\\sum\_\{i=1\}^\{7\} c\_\{i\} x\_\{i\} \\\\ &\\left\\\{\\begin\{array\}\{l\} \\sum\_\{i=1\}^\{7\} b\_\{i\} x\_\{i\} \\leq B \\\\ x\_\{1\}+x\_\{2\}+x\_\{3\} \\leq 2 \\\\ x\_\{4\}+x\_\{5\} \\geq 1 \\\\ x\_\{6\}+x\_\{7\} \\geq 1, \\quad x\_\{i\}=0 \\text \{ or \} 1 \\end\{array\}\\right. \\end\{aligned\}][begin_aligned_ _operatorname_Max_ _quad z_sum_i_1_7_ c_i_ x_i_ _ _left_begin_array_l_ _sum_i_1_7_ b_i_ x_i_ _leq B _ x_1_x_2_x_3_ _leq 2 _ x_4_x_5_ _geq 1 _ x_6_x_7_ _geq 1_ _quad x_i_0 _text _ or _ 1 _end_array_right. _end_aligned]

### 2.相互排斥的约束条件 ###

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

![5 x\_\{1\}+4 x\_\{2\} \\leq 24 \\text \{ or \} 7 x\_\{1\}+3 x\_\{2\} \\leq 45][5 x_1_4 x_2_ _leq 24 _text _ or _ 7 x_1_3 x_2_ _leq 45]

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

![\\left\\\{\\begin\{array\}\{l\} 5 x\_\{1\}+4 x\_\{2\} \\leq 24+y M \\\\ 7 x\_\{1\}+3 x\_\{2\} \\leq 45+(1-y) M \\\\ y=0 \\text \{ or \} 1 \\end\{array\}\\right.][left_begin_array_l_ 5 x_1_4 x_2_ _leq 24_y M _ 7 x_1_3 x_2_ _leq 45_1-y_ M _ y_0 _text _ or _ 1 _end_array_right.]

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

![x\_\{1\}=0 \\text \{ or \} 500 \\leq x\_\{1\} \\leq 800][x_1_0 _text _ or _ 500 _leq x_1_ _leq 800]

可改写为

![\\left\\\{\\begin\{array\}\{l\} 500 y \\leq x\_\{1\} \\leq 800 y \\\\ y=0 \\text \{ or \} 1 \\end\{array\}\\right.][left_begin_array_l_ 500 y _leq x_1_ _leq 800 y _ y_0 _text _ or _ 1 _end_array_right.]

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

![a\_\{i 1\} x\_\{1\}+\\cdots+a\_\{i n\} x\_\{n\} \\leq b\_\{i\} \\quad i=1,2, \\cdots, m][a_i 1_ x_1_cdots_a_i n_ x_n_ _leq b_i_ _quad i_1_2_ _cdots_ m]

为了保证这 ![m][] 个约束条件只有一个起作用，我们引入 ![m][] 个0 −1变量![y\_\{i\}(i=1,2,...,m)][y_i_i_1_2_..._m] 和一个充分大的常数 ![M][] ，而下面这一组![m+1][m_1]个约束条件

![\\begin\{aligned\} &a\_\{i 1\} x\_\{1\}+\\cdots+a\_\{i n\} x\_\{n\} \\leq b\_\{i\}+y\_\{i\} M \\quad i=1,2, \\cdots, m \\\\ &y\_\{1\}+\\cdots+y\_\{m\}=m-1 \\end\{aligned\}][begin_aligned_ _a_i 1_ x_1_cdots_a_i n_ x_n_ _leq b_i_y_i_ M _quad i_1_2_ _cdots_ m _ _y_1_cdots_y_m_m-1 _end_aligned]

就合于上述的要求。这是因为，由于（2），m 个 ![y\_\{i\}][y_i] 中只有一个能取 0 值，设 ![y\_\{i\}^\{\*\}=0][y_i_0] ， 代入（1），就只有![i=i^\{\*\}][i_i]的约束条件起作用，而别的式子都是多余的。

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

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

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

*  ![x\_\{j\}][x_j] 表示采用第 j 种方式时的产量；
 *  ![c\_\{j\}][c_j] 表示采用第 j 种方式时每件产品的变动成本；
 *  ![k\_\{j\}][k_j] 表示采用第 j 种方式时的固定成本。

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

![P\_\{j\}=\\left\\\{\\begin\{array\}\{ll\} k\_\{j\}+c\_\{j\} x\_\{j\}, & \\text \{ \} x\_\{j\}>0 \\\\ 0, & \\text \{ \} x\_\{j\}=0 \\end\{array\} \\quad j=1,2,3 .\\right.][P_j_left_begin_array_ll_ k_j_c_j_ x_j_ _ _text _ _ x_j_0 _ 0_ _ _text _ _ x_j_0 _end_array_ _quad j_1_2_3 ._right.]

在构成目标函数时，为了统一在一个问题中讨论，现引入0 −1变量![y\_\{j\}][y_j] ，令

![3adaeec26b9843868639b8278f4c9102.png][]

于是目标函数

![\\min z=\\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)][min z_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 个线性约束条件：

![y\_\{j\} \\varepsilon \\leq x\_\{j\} \\leq y\_\{j\} M, \\quad j=1,2,3][y_j_ _varepsilon _leq x_j_ _leq y_j_ M_ _quad j_1_2_3]

其中![\\varepsilon][varepsilon]是一个充分小的正常数，![M][] 是个充分大的正常数。当 ![x\_\{j\}][x_j]> 0时 ![y\_\{j\}][y_j]必须为 1；当 ![x\_\{j\}][x_j] = 0时只有 ![y\_\{j\}][y_j]为 0 时才有意义。

**举个栗子：**

![\\begin\{aligned\} &\\operatorname\{Max\} \\quad z=3 x\_\{1\}-2 x\_\{2\}+5 x\_\{3\} \\\\ &\\left\\\{\\begin\{array\}\{l\} x\_\{1\}+2 x\_\{2\}-x\_\{3\} \\leq 2 \\\\ x\_\{1\}+4 x\_\{2\}+x\_\{3\} \\leq 4 \\\\ x\_\{1\}+x\_\{2\} \\leq 3 \\\\ 4 x\_\{2\}+x\_\{3\} \\leq 6 \\\\ x\_\{1\}, x\_\{2\}, x\_\{3\}=0 \\text \{ or \} 1 \\end\{array\}\\right. \\end\{aligned\}][begin_aligned_ _operatorname_Max_ _quad z_3 x_1_-2 x_2_5 x_3_ _ _left_begin_array_l_ x_1_2 x_2_-x_3_ _leq 2 _ x_1_4 x_2_x_3_ _leq 4 _ x_1_x_2_ _leq 3 _ 4 x_2_x_3_ _leq 6 _ x_1_ x_2_ x_3_0 _text _ or _ 1 _end_array_right. _end_aligned]

###  ###

### 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

[x_j]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7Bj%7D
[0_leq x_j_leq 1]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%200%5Cleq%20x_%7Bj%7D%5Cleq%201
[A_i_i_1_2_..._7]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20A_%7Bi%7D%28i%3D1%2C2%2C...%2C7%29
[A_1_A_2_A_3]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20A_%7B1%7D%2CA_%7B2%7D%2CA_%7B3%7D
[A_4_A_5]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20A_%7B4%7D%2CA_%7B5%7D
[A_6_A_7]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20A_%7B6%7D%2CA_%7B7%7D
[A_i]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20A_%7Bi%7D
[b_i]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20b_%7Bi%7D
[c_i]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20c_%7Bi%7D
[B]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B
[x_i_i_1_2_..._7]: https://latex.csdn.net/eq?%5Cdpi%7B100%7D%20x_%7Bi%7D%28i%3D1%2C2%2C...%2C7%29
[54c2fbf28f3b4db5855d7e2ebb988cf9.png]: https://img-blog.csdnimg.cn/54c2fbf28f3b4db5855d7e2ebb988cf9.png
[begin_aligned_ _operatorname_Max_ _quad z_sum_i_1_7_ c_i_ x_i_ _ _left_begin_array_l_ _sum_i_1_7_ b_i_ x_i_ _leq B _ x_1_x_2_x_3_ _leq 2 _ x_4_x_5_ _geq 1 _ x_6_x_7_ _geq 1_ _quad x_i_0 _text _ or _ 1 _end_array_right. _end_aligned]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cbegin%7Baligned%7D%20%26%5Coperatorname%7BMax%7D%20%5Cquad%20z%3D%5Csum_%7Bi%3D1%7D%5E%7B7%7D%20c_%7Bi%7D%20x_%7Bi%7D%20%5C%5C%20%26%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D%20%5Csum_%7Bi%3D1%7D%5E%7B7%7D%20b_%7Bi%7D%20x_%7Bi%7D%20%5Cleq%20B%20%5C%5C%20x_%7B1%7D&plus;x_%7B2%7D&plus;x_%7B3%7D%20%5Cleq%202%20%5C%5C%20x_%7B4%7D&plus;x_%7B5%7D%20%5Cgeq%201%20%5C%5C%20x_%7B6%7D&plus;x_%7B7%7D%20%5Cgeq%201%2C%20%5Cquad%20x_%7Bi%7D%3D0%20%5Ctext%20%7B%20or%20%7D%201%20%5Cend%7Barray%7D%5Cright.%20%5Cend%7Baligned%7D
[5 x_1_4 x_2_ _leq 24 _text _ or _ 7 x_1_3 x_2_ _leq 45]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%205%20x_%7B1%7D&plus;4%20x_%7B2%7D%20%5Cleq%2024%20%5Ctext%20%7B%20or%20%7D%207%20x_%7B1%7D&plus;3%20x_%7B2%7D%20%5Cleq%2045
[left_begin_array_l_ 5 x_1_4 x_2_ _leq 24_y M _ 7 x_1_3 x_2_ _leq 45_1-y_ M _ y_0 _text _ or _ 1 _end_array_right.]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D%205%20x_%7B1%7D&plus;4%20x_%7B2%7D%20%5Cleq%2024&plus;y%20M%20%5C%5C%207%20x_%7B1%7D&plus;3%20x_%7B2%7D%20%5Cleq%2045&plus;%281-y%29%20M%20%5C%5C%20y%3D0%20%5Ctext%20%7B%20or%20%7D%201%20%5Cend%7Barray%7D%5Cright.
[x_1_0 _text _ or _ 500 _leq x_1_ _leq 800]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B1%7D%3D0%20%5Ctext%20%7B%20or%20%7D%20500%20%5Cleq%20x_%7B1%7D%20%5Cleq%20800
[left_begin_array_l_ 500 y _leq x_1_ _leq 800 y _ y_0 _text _ or _ 1 _end_array_right.]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D%20500%20y%20%5Cleq%20x_%7B1%7D%20%5Cleq%20800%20y%20%5C%5C%20y%3D0%20%5Ctext%20%7B%20or%20%7D%201%20%5Cend%7Barray%7D%5Cright.
[a_i 1_ x_1_cdots_a_i n_ x_n_ _leq b_i_ _quad i_1_2_ _cdots_ m]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20a_%7Bi%201%7D%20x_%7B1%7D&plus;%5Ccdots&plus;a_%7Bi%20n%7D%20x_%7Bn%7D%20%5Cleq%20b_%7Bi%7D%20%5Cquad%20i%3D1%2C2%2C%20%5Ccdots%2C%20m
[m]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20m
[y_i_i_1_2_..._m]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20y_%7Bi%7D%28i%3D1%2C2%2C...%2Cm%29
[M]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20M
[m_1]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20m&plus;1
[begin_aligned_ _a_i 1_ x_1_cdots_a_i n_ x_n_ _leq b_i_y_i_ M _quad i_1_2_ _cdots_ m _ _y_1_cdots_y_m_m-1 _end_aligned]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cbegin%7Baligned%7D%20%26a_%7Bi%201%7D%20x_%7B1%7D&plus;%5Ccdots&plus;a_%7Bi%20n%7D%20x_%7Bn%7D%20%5Cleq%20b_%7Bi%7D&plus;y_%7Bi%7D%20M%20%5Cquad%20i%3D1%2C2%2C%20%5Ccdots%2C%20m%20%5C%5C%20%26y_%7B1%7D&plus;%5Ccdots&plus;y_%7Bm%7D%3Dm-1%20%5Cend%7Baligned%7D
[y_i]: https://latex.csdn.net/eq?%5Cdpi%7B100%7D%20y_%7Bi%7D
[y_i_0]: https://latex.csdn.net/eq?%5Cdpi%7B100%7D%20y_%7Bi%7D%5E%7B*%7D%3D0
[i_i]: https://latex.csdn.net/eq?%5Cdpi%7B100%7D%20i%3Di%5E%7B*%7D
[c_j]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20c_%7Bj%7D
[k_j]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20k_%7Bj%7D
[P_j_left_begin_array_ll_ k_j_c_j_ x_j_ _ _text _ _ x_j_0 _ 0_ _ _text _ _ x_j_0 _end_array_ _quad j_1_2_3 ._right.]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20P_%7Bj%7D%3D%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bll%7D%20k_%7Bj%7D&plus;c_%7Bj%7D%20x_%7Bj%7D%2C%20%26%20%5Ctext%20%7B%20%7D%20x_%7Bj%7D%3E0%20%5C%5C%200%2C%20%26%20%5Ctext%20%7B%20%7D%20x_%7Bj%7D%3D0%20%5Cend%7Barray%7D%20%5Cquad%20j%3D1%2C2%2C3%20.%5Cright.
[y_j]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20y_%7Bj%7D
[3adaeec26b9843868639b8278f4c9102.png]: https://img-blog.csdnimg.cn/3adaeec26b9843868639b8278f4c9102.png
[min z_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]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cmin%20z%3D%5Cleft%28k_%7B1%7D%20y_%7B1%7D&plus;c_%7B1%7D%20x_%7B1%7D%5Cright%29&plus;%5Cleft%28k_%7B2%7D%20y_%7B2%7D&plus;c_%7B2%7D%20x_%7B2%7D%5Cright%29&plus;%5Cleft%28k_%7B3%7D%20y_%7B3%7D&plus;c_%7B3%7D%20x_%7B3%7D%5Cright%29
[y_j_ _varepsilon _leq x_j_ _leq y_j_ M_ _quad j_1_2_3]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20y_%7Bj%7D%20%5Cvarepsilon%20%5Cleq%20x_%7Bj%7D%20%5Cleq%20y_%7Bj%7D%20M%2C%20%5Cquad%20j%3D1%2C2%2C3
[varepsilon]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cvarepsilon
[begin_aligned_ _operatorname_Max_ _quad z_3 x_1_-2 x_2_5 x_3_ _ _left_begin_array_l_ x_1_2 x_2_-x_3_ _leq 2 _ x_1_4 x_2_x_3_ _leq 4 _ x_1_x_2_ _leq 3 _ 4 x_2_x_3_ _leq 6 _ x_1_ x_2_ x_3_0 _text _ or _ 1 _end_array_right. _end_aligned]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cbegin%7Baligned%7D%20%26%5Coperatorname%7BMax%7D%20%5Cquad%20z%3D3%20x_%7B1%7D-2%20x_%7B2%7D&plus;5%20x_%7B3%7D%20%5C%5C%20%26%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D%20x_%7B1%7D&plus;2%20x_%7B2%7D-x_%7B3%7D%20%5Cleq%202%20%5C%5C%20x_%7B1%7D&plus;4%20x_%7B2%7D&plus;x_%7B3%7D%20%5Cleq%204%20%5C%5C%20x_%7B1%7D&plus;x_%7B2%7D%20%5Cleq%203%20%5C%5C%204%20x_%7B2%7D&plus;x_%7B3%7D%20%5Cleq%206%20%5C%5C%20x_%7B1%7D%2C%20x_%7B2%7D%2C%20x_%7B3%7D%3D0%20%5Ctext%20%7B%20or%20%7D%201%20%5Cend%7Barray%7D%5Cright.%20%5Cend%7Baligned%7D