数学建模：整数编程示例模型（Python 求解器）
目录
- 例 1 : 选课策略模型
- 1. 为了选修课程门数最少, 应学习哪些课程?
- 建立 0-1 规划模型
- Python 求解
- 2. 选修课程最少时, 为了学分尽量多, 应学习哪些课程?
- 例 2 : 装箱问题
- 模型 1 : 体积上多装
- 建立整数规划模型
- Python 求解
- 模型 2 : 重量上多装
用 Python 求解整数规划模型只需用 cvxpy 模块在建立变量时指定 integer=True 即可, 即
x=cp.Variable(shape=(),integer=True)
其他操作与线性规划相同.
例 1 : 选课策略模型
| 课号 | 课名 | 学分 | 所属类别 | 先修课要求 |
|---|---|---|---|---|
| 1 | 微积分 | 5 | 数学 | |
| 2 | 线性代数 | 4 | 数学 | |
| 3 | 最优化方法 | 4 | 数学；运筹学 | 微积分；线性代数 |
| 4 | 数据结构 | 3 | 数学；计算机 | 计算机编程 |
| 5 | 应用统计 | 4 | 数学；运筹学 | 微积分；线性代数 |
| 6 | 计算机模拟 | 3 | 计算机；运筹学 | 计算机编程 |
| 7 | 计算机编程 | 2 | 计算机 | |
| 8 | 预测理论 | 2 | 运筹学 | 应用统计 |
| 9 | 数学实验 | 3 | 运筹学；计算机 | 微积分；线性代数 |
要求至少选两门数学课, 三门运筹学课和两门计算机课
1. 为了选修课程门数最少, 应学习哪些课程?
建立 0-1 规划模型
这是一个指派模型
决策变量: 引入 0-1 变量
x
i
=
{
1
,
选修课号
i
的课程
0
,
不选课号
i
的课程
x_i= \begin{cases} 1, \ \text{选修课号} \ i \ \text{的课程} \\ 0, \ \text{不选课号} \ i \ \text{的课程} \end{cases}
xi={1, 选修课号 i 的课程0, 不选课号 i 的课程
目标函数: 选修课程总数最少
min
Z
=
∑
i
=
1
9
x
i
\min \quad Z=\sum_{i=1}^{9} x_{i}
minZ=i=1∑9xi
约束条件
-
最少 2 门数学课，3 门运筹学课，2 门计算机课:
{ x 1 + x 2 + x 3 + x 4 + x 5 ≥ 2 x 3 + x 5 + x 6 + x 8 + x 9 ≥ 3 x 4 + x 6 + x 7 + x 9 ≥ 2 \begin{cases} x_{1}+x_{2}+x_{3}+x_{4}+x_{5} \geq 2 \\ x_{3}+x_{5}+x_{6}+x_{8}+x_{9} \geq 3 \\ x_{4}+x_{6}+x_{7}+x_{9} \geq 2 \end{cases} ⎩⎪⎨⎪⎧x1+x2+x3+x4+x5≥2x3+x5+x6+x8+x9≥3x4+x6+x7+x9≥2 -
先修课程要求:
{ 2 x 3 − x 1 − x 2 ≤ 0 x 4 − x 7 ≤ 0 2 x 5 − x 1 − x 2 ≤ 0 x 6 − x 7 ≤ 0 x 8 − x 5 ≤ 0 2 x 9 − x 1 − x 2 ≤ 0 \begin{cases} 2 x_{3}-x_{1}-x_{2} \leq 0\\ x_{4}-x_{7} \leq 0\\ 2 x_{5}-x_{1}-x_{2} \leq 0 \\ x_{6}-x_{7} \leq 0 \\ x_{8}-x_{5} \leq 0 \\ 2 x_{9}-x_{1}-x_{2} \leq 0 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧2x3−x1−x2≤0x4−x7≤02x5−x1−x2≤0x6−x7≤0x8−x5≤02x9−x1−x2≤0
Python 求解
import numpy as np
import cvxpy as cp
x=cp.Variable(9, integer=True) #决策变量, 整数型
c=np.array([5,4,4,3,4,3,2,2,3]) #学分
obj=cp.Minimize(cp.sum(x)) #目标函数, 总课程最少
con=[x>=0,x<=1,
cp.sum(x[0:5])>=2,
x[2]+x[4]+x[5]+x[7]+x[8]>=3,
x[3]+x[5]+x[6]+x[8]>=2,
2*x[2]-x[0]-x[1]<=0,
x[3]-x[6]<=0,
2*x[4]-x[0]-x[1]<=0,
x[5]-x[6]<=0,
x[7]-x[4]<=0,
2*x[2]-x[0]-x[1]<=0] #约束条件
prob=cp.Problem(obj,con) #建立模型
prob.solve()
print("最优值:", prob.value)#最优课程总数
print("最优解:", x.value)
print("总学分:", np.sum(x.value*c))
最优值: 6.0
最优解: [1. 1. 0. 0. 1. 1. 1. 1. 0.]
总学分: 20.0
这里最优解不是唯一的, 我们可以进一步提出下面的问题
2. 选修课程最少时, 为了学分尽量多, 应学习哪些课程?
我们已经求出最少课程门数为 6 门, 所以只需在第 1 问模型的基础上把目标函数变为
max
Z
=
∑
i
=
1
9
c
i
x
i
\max \quad Z=\sum_{i=1}^{9} c_i x_{i}
maxZ=i=1∑9cixi
其中
c
1
c_1
c1 为课号为
i
i
i 的课程的学分. 再加上约束条件
∑
i
=
1
9
x
i
=
6
\sum_{i=1}^{9} x_{i}=6
i=1∑9xi=6
即可.
import numpy as np
import cvxpy as cp
x=cp.Variable(9, integer=True)