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

• • 例 1 : 选课策略模型
  • • 1. 为了选修课程门数最少, 应学习哪些课程?
    • • 建立 0-1 规划模型
      • Python 求解
    • 2. 选修课程最少时, 为了学分尽量多, 应学习哪些课程?
  • 例 2 : 装箱问题
  • • 模型 1 : 体积上多装
    • • 建立整数规划模型
      • Python 求解
    • 模型 2 : 重量上多装

用 Python 求解整数规划模型只需用 cvxpy 模块在建立变量时指定 integer=True 即可, 即

x=cp.Variable(shape=(),integer=True)

其他操作与线性规划相同.

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

这是一个指派模型

决策变量: 引入 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∑9​xi​

约束条件

• 最少 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​

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

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

我们已经求出最少课程门数为 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∑9​ci​xi​

其中 c 1 c_1 c1​ 为课号为 i i i 的课程的学分. 再加上约束条件
∑ i = 1 9 x i = 6 sum_{i=1}^{9} x_{i}=6 i=1∑9​xi​=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,x<=1, 
     cp.sum(x)==6, #选修课程数为最少的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

有 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} C5​,C6​,C7​ 类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过 302.7 cm。要求给出最好的装运方式。

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

设决策变量 x i j ( i = 1 , 2 ; j = 1 , 2 , ⋯   , 7 ) {x_{ij}}(i = 1,2;j = 1,2, cdots ,7) xij​(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) lj​,wj​,aj​(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) maxz1​=j=1∑7​lj​(x1j​+x2j​)

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=12​xij​≤aj​,j=1,2,⋯,7,∑j=17​lj​xij​≤1020,i=1,2,∑j=17​wj​xij​≤40000,i=1,2,∑j=57​lj​(x1j​+x2j​)≤302.7,xij​≥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@L<=1020, x@w<=40000, 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} = sumlimits_{j = 1}^7 {{w_j}({x_{1j}} + {x_{2j}})} maxz2​=j=1∑7​wj​(x1j​+x2j​)

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@L<=1020, x@w<=40000, 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.]]