数学建模：整数规划示例模型 (Python 求解)

用 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运筹学；计算机微积分；线性代数

要求至少选两门数学课, 三门运筹学课和两门计算机课

这是一个指派模型

决策变量: 引入 0-1 变量
x i = { 1 , 选修课号 i 的课程 0 , 不选课号 i 的课程 x_i= \begin{cases} 1, \ \text{选修课号} \ i \ \text{的课程} \ 0, \ \text{不选课号} \ i \ \text{的课程} \end{cases}x i ​={1 ,选修课号i 的课程0 ,不选课号i 的课程​

目标函数: 选修课程总数最少
min ⁡ Z = ∑ i = 1 9 x i \min \quad Z=\sum_{i=1}^{9} x_{i}min Z =i =1 ∑9 ​x i ​

约束条件

• 最少 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}⎩⎪⎨⎪⎧​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 ​
• 先修课程要求:
  { 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}⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​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 ​

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,x1,
     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

这里最优解不是唯一的, 我们可以进一步提出下面的问题

我们已经求出最少课程门数为 6 门, 所以只需在第 1 问模型的基础上把目标函数变为
max ⁡ Z = ∑ i = 1 9 c i x i \max \quad Z=\sum_{i=1}^{9} c_i x_{i}max Z =i =1 ∑9 ​c i ​x i ​

其中 c 1 c_1 c 1 ​ 为课号为 i i i 的课程的学分. 再加上约束条件
∑ i = 1 9 x i = 6 \sum_{i=1}^{9} x_{i}=6 i =1 ∑9 ​x i ​=6

即可.

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.Maximize(c@x)
con=[x>=0,x1,
     cp.sum(x)==6,
     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))

最优值: 22.0
最优解: [1. 1. 1. 0. 1. 1. 1. 0. 0.]
总学分: 22.0

例 2 : 装箱问题

有 7 种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度 l l l (cm) 及重量 w w w (kg) 是不同的，表中给出了每种包装箱的厚度、重量以及数量，每辆平板车有 10.2 m 长的地方来装包装箱，载重量为 40 t，由于当地货运的限制，对 C 5 , C 6 , C 7 {C_5},{C_6},{C_7}C 5 ​,C 6 ​,C 7 ​ 类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过 302.7 cm。要求给出最好的装运方式。

/cm48.752.061.372.048.752.064.0

/kg200030001000500400020001000件数8796648

题中所有包装箱共重 89 t，而两辆平板车一共只能载重 80 t，因此不可能全装下。究竟在两辆车上各装哪些种类箱子且各为多少才合适，必须有评价的标准。这标准就是遵守题中说明的重量、厚度、件数等方面的约束条件，尽可能地多装，而尽可能多装有两种理解：一是尽可能在体积上多装，由于规定是按面包片重叠那样的装法，故等价于尽可能使两辆车上的装箱总厚度尽可能大；二是尽可能在重量上多装，即使得两辆车上的装箱总重量尽可能大。

设决策变量 x i j ( i = 1 , 2 ; j = 1 , 2 , ⋯ , 7 ) {x_{ij}}(i = 1,2;j = 1,2, \cdots ,7)x i j ​(i =1 ,2 ;j =1 ,2 ,⋯,7 ) 表示第 i i i 辆车上装第 j j j 种包装箱的件数，l j , w j , a j ( j = 1 , 2 , ⋯ , 7 ) {l_j},{w_j},{a_j}(j = 1,2, \cdots ,7)l j ​,w j ​,a j ​(j =1 ,2 ,⋯,7 ) 分别表示第 j j j 种包装箱的厚度、重量和件数

max ⁡ z 1 = ∑ j = 1 7 l j ( x 1 j + x 2 j ) \max \quad z_{1}=\sum_{j=1}^{7} l_{j}\left(x_{1 j}+x_{2 j}\right)max z 1 ​=j =1 ∑7 ​l j ​(x 1 j ​+x 2 j ​)

s . t . { ∑ i = 1 2 x i j ≤ a j , j = 1 , 2 , ⋯ , 7 , ∑ j = 1 7 l j x i j ≤ 1020 , i = 1 , 2 , ∑ j = 1 7 w j x i j ≤ 40000 , i = 1 , 2 , ∑ j = 5 7 l j ( x 1 j + x 2 j ) ≤ 302.7 , x i j ≥ 0 且为整数, i = 1 , 2 ; j = 1 , 2 , ⋯ , 7. { s.t. }\left{\begin{array}{l} \sum_{i=1}^{2} x_{i j} \leq a_{j}, \quad j=1,2, \cdots, 7, \ \sum_{j=1}^{7} l_{j} x_{i j} \leq 1020, \quad i=1,2, \ \sum_{j=1}^{7} w_{j} x_{i j} \leq 40000, \quad i=1,2, \ \sum_{j=5}^{7} l_{j}\left(x_{1 j}+x_{2 j}\right) \leq 302.7, \ x_{i j} \geq 0 \text { 且为整数, } \quad i=1,2 ; j=1,2, \cdots, 7 . \end{array}\right.s .t .⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​∑i =1 2 ​x i j ​≤a j ​,j =1 ,2 ,⋯,7 ,∑j =1 7 ​l j ​x i j ​≤1 0 2 0 ,i =1 ,2 ,∑j =1 7 ​w j ​x i j ​≤4 0 0 0 0 ,i =1 ,2 ,∑j =5 7 ​l j ​(x 1 j ​+x 2 j ​)≤3 0 2 .7 ,x i j ​≥0 且为整数,i =1 ,2 ;j =1 ,2 ,⋯,7 .​

import cvxpy as cp
import numpy as np

L=np.array([48.7,52.0,61.3,72.0,48.7,52.0,64.0])
w=np.array([2000,3000,1000,500,4000,2000,1000])
a=np.array([8,7,9,6,6,4,8])

x=cp.Variable((2,7), integer=True)
obj=cp.Maximize(cp.sum(x@L))
con=[cp.sum(x,axis=0,keepdims=True)a.reshape(1,7),
     x@L1020, x@w40000, cp.sum(x[:,4:]@L[4:])302.7, x>=0]
prob = cp.Problem(obj, con)
prob.solve(solver='GLPK_MI')
print("最优值为:",prob.value)
print("最优解为：\n",x.value)

最优值为: 2039.4
最优解为：
 [[4. 1. 5. 3. 3. 2. 0.]
 [4. 6. 4. 3. 0. 1. 0.]]

目标函数变为
max ⁡ z 2 = ∑ j = 1 7 w j ( x 1 j + x 2 j ) \max \quad \;{z_2} = \sum\limits_{j = 1}^7 {{w_j}({x_{1j}} + {x_{2j}})}max z 2 ​=j =1 ∑7 ​w j ​(x 1 j ​+x 2 j ​)

import cvxpy as cp
import numpy as np

L=np.array([48.7,52.0,61.3,72.0,48.7,52.0,64.0])
w=np.array([2000,3000,1000,500,4000,2000,1000])
a=np.array([8,7,9,6,6,4,8])

x=cp.Variable((2,7), integer=True)
obj=cp.Maximize(cp.sum(x@w))
con=[cp.sum(x,axis=0,keepdims=True)a.reshape(1,7),
     x@L1020, x@w40000, cp.sum(x[:,4:]@L[4:])302.7, x>=0]
prob = cp.Problem(obj, con)
prob.solve(solver='GLPK_MI')
print("最优值为:",prob.value)
print("最优解为：\n",x.value)

最优值为: 73000.0
最优解为：
 [[6. 0. 0. 6. 6. 0. 0.]
 [2. 7. 9. 0. 0. 0. 0.]]

Original: https://blog.csdn.net/qq_55851911/article/details/124514976
Author: Charle4Leclerc
Title: 数学建模：整数规划示例模型 (Python 求解)