【公式求解】线性规划之整数规划(1)

对于限制全部或部分决策变量取离散非负整数值的线性规划,称之为整数线性规划,简称为整数规划。常见的整数规划求解算法有分支定界法、隐枚举法等。

例:求解下列整数线性规划问题
$ min \quad z = 40x_{1}+90x_{2} $
$ s.t. \begin{cases}
9x_{1}+7x_{2} \leq 56 \\
7x_{1}+20x_{2} \geq 70 \\
x_{1},x_{2} \geq 0且为整数
\end{cases}
$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np
import cvxpy as cp

c = np.array([40,90]) # 目标变量

a = np.array([[9,7],[-2,-20]]) # 定义约束矩阵
b = np.array([56,-70]) # 定义约束条件的右边向量
x = cp.Variable(2, integer=True) # 定义两个整数决策变量(特殊点)

obj = cp.Minimize(c@x) # 构造目标函数

con = [a@x<=b, x>=0] # 构造约束条件

prob = cp.Problem(obj, con) # 构建问题模型

prob.solve(solver='GLPK_MI', verbose=True) # 求解问题

print('最优解为:', x.value)
print('最优值为:', prob.value)
0%