数学建模算法与应用 整数规划（cvxpy包）
习题习题2.1 试将下述非线性的0-1规划问题转换成线性的0-1规划问题maxz=x1+x1x2−x3max z = x_1+x_1x_2-x_3maxz=x1+x1x2−x3s.t.={−2x1+3x2+x3≤3xj=0或1, j=1,2,3s.t.=\begin{cases}-2x_1 + 3x_2+x_3 \leq 3\\x_j = 0 \text{或}1,
习题
习题2.1
试将下述非线性的0-1规划问题转换成线性的0-1规划问题
m
a
x
z
=
x
1
+
x
1
x
2
−
x
3
s
.
t
.
=
{
−
2
x
1
+
3
x
2
+
x
3
≤
3
x
j
=
0
或
1
,
j
=
1
,
2
,
3
max z = x_1+x_1x_2-x_3\\ s.t.= \begin{cases} -2x_1 + 3x_2+x_3 \leq 3\\ x_j = 0 \text{或}1,\ \ j = 1,2,3 \end{cases}
maxz=x1+x1x2−x3s.t.={−2x1+3x2+x3≤3xj=0或1, j=1,2,3
算法设计
做变量替换
y
=
x
1
x
2
y = x_1x_2
y=x1x2，则有如下关系：
x
1
+
x
2
−
1
≤
y
≤
x
1
x
1
+
x
2
−
1
≤
y
≤
x
2
x_1+x_2-1 \leq y \leq x_1 \\ x_1 + x_2 -1 \leq y \leq x_2
x1+x2−1≤y≤x1x1+x2−1≤y≤x2
从而得到如下的线性0-1规划
m
a
x
z
=
x
1
+
y
−
x
3
s
.
t
.
=
{
−
2
x
1
+
3
x
2
+
x
3
≤
3
x
1
+
x
2
−
1
≤
y
≤
x
1
x
1
+
x
2
−
1
≤
y
≤
x
2
x
j
=
0
或
1
,
j
=
1
,
2
,
3
y
=
0
或
1
max z = x_1 + y - x_3\\ s.t.= \begin{cases} -2x_1 + 3x_2 + x_3 \leq 3\\ x_1 + x_2 -1 \leq y \leq x_1\\ x_1 + x_2 -1 \leq y \leq x_2\\ x_j = 0 或 1, \ \ j = 1,2,3\\ y = 0或1 \end{cases}
maxz=x1+y−x3s.t.=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧−2x1+3x2+x3≤3x1+x2−1≤y≤x1x1+x2−1≤y≤x2xj=0或1, j=1,2,3y=0或1
习题2.2
某市为方便小学生上学，拟在新建的8个居民小区 A 1 , A 2 , . . . , A 8 A_1,A_2,...,A_8 A1,A2,...,A8增设若干所小学，经过论证知备选校址有 B 1 , B 2 , . . . , B 6 B_1,B_2,...,B_6 B1,B2,...,B6，它们能够覆盖的居民小区如下表所示。
| B 1 B_1 B1 | B 2 B_2 B2 | B 3 B_3 B3 | B 4 B_4 B4 | B 5 B_5 B5 | B 6 B_6 B6 |
|---|---|---|---|---|---|
| A 1 , A 5 , A 7 A_1,A_5,A_7 A1,A5,A7 | A 1 , A 2 , A 5 , A 8 A_1,A_2,A_5,A_8 A1,A2,A5,A8 | A 1 , A 3 , A 5 A_1,A_3,A_5 A1,A3,A5 | A 2 , A 4 , A 8 A_2,A_4,A_8 A2,A4,A8 | A 3 , A 6 A_3,A_6 A3,A6 | A 4 , A 6 , A 8 A_4,A_6,A_8 A4,A6,A8 |
试建立一个数学模型，确定出最小个数的建校地址，使其能够覆盖所有的居民小区
算法设计
令
x
i
=
{
1
,
在
备
选
校
址
B
i
建
学
校
0
,
在
备
选
校
址
B
i
不
建
学
校
x_{i} = \begin{cases} 1,\ \ \ 在备选校址B_{i}建学校\\ 0,\ \ \ 在备选校址B_{i}不建学校\\ \end{cases}
xi={1, 在备选校址Bi建学校0, 在备选校址Bi不建学校
小区
A
1
A_{1}
A1可以被备选校址B_1、B_2、B_3处所建的学校覆盖，则有约束条件
x
1
+
x
2
+
x
3
≥
1
x_1 + x_2 + x_3 \geq 1
x1+x2+x3≥1
依次类推，建立如下0-1整数规划模型：
m
i
n
∑
i
=
1
6
x
i
s
.
t
.
=
{
x
1
+
x
2
+
x
3
≥
1
x
2
+
x
4
≥
1
x
3
+
x
5
≥
1
x
4
+
x
6
≥
1
x
5
+
x
6
≥
1
x
1
≥
1
x
2
+
x
4
+
x
6
≥
1
x
i
=
0
或
1
,
i
=
1
,
2
,
.
.
.
,
8
min \sum^{6}_{i = 1}x_i\\ s.t. = \begin{cases} x_1 + x_2 + x_3 \geq 1 \\ x_2 + x_4 \geq 1 \\ x_3 + x_5 \geq 1 \\ x_4 + x_6 \geq 1 \\ x_5 + x_6 \geq 1 \\ x_1 \geq 1\\ x_2 + x_4 + x_6 \geq 1 \\ x_{i} = 0 或 1,\ \ \ i = 1,2,...,8 \end{cases}
mini=1∑6xis.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧x1+x2+x3≥1x2+x4≥1x3+x5≥1x4+x6≥1x5+x6≥1x1≥1x2+x4+x6≥1xi=0或1, i=1,2,...,8
# 决策变量
n = 8
# nonneg参数，变量是否为非负
x = cp.Variable(n,nonneg = True)
# 约束1
A1 = np.array([[1,1,1,0,0,0,0,0],
[0,1,0,1,0,0,0,0],
[0,0,1,0,1,0,0,0],
[0,0,0,1,0,1,0,0],
[0,0,0,0,1,1,0,0],
[1,0,0,0,0,0,0,0],
[0,1,0,1,0,1,0,0]])
b1 = np.array([1,1,1,1,1,1,1])
# 约束2
A2 = np.ones((8, 8))
for i in range(A2.shape[0]):
for j in range(A2.shape[1]):
if i == j:
pass
else:
A2[i, j] = A2[i, j]*0
b2 = np.array([0,0,0,0,0,0,0,0])
# 约束3
A3 = np.ones((8, 8))
for i in range(A3.shape[0]):
for j in range(A3.shape[1]):
if i == j:
pass
else:
A3[i, j] = A3[i, j]*0
b3 = np.array([1,1,1,1,1,1,1,1])
# 目标函数
c = np.array([1,1,1,1,1,1,1,1])
# 定义问题，添加约束条件
prob = cp.Problem(cp.Minimize(c.T @ x),
[A1 @ x >= b1,
A2 @ x >= b2,
A3 @ x <= b3])
# 求解
ans = prob.solve(solver=cp.GLOP)
# 输出结果
print("目标函数最小值:", ans)
# 对x向量各元素取整数后再输出
print(x.value)
输出
目标函数最小值: 3.0
[ 1. -0. 0. 1. 1. -0. -0. -0.]
习题2.3
某公司新购置了某种设备6台，欲分配给下属的4个企业，每个企业至少获订一台设备，已知各企业获得这种设备后年创利润如下表所示，单位为千万元。问应如何分配这些设备能使年创利润最大，最大利润是多少？
| 设备 | 甲 | 乙 | 丙 | 丁 |
|---|---|---|---|---|
| 1 | 4 | 2 | 3 | 4 |
| 2 | 6 | 4 | 5 | 5 |
| 3 | 7 | 6 | 7 | 6 |
| 4 | 7 | 8 | 8 | 6 |
| 5 | 7 | 9 | 8 | 6 |
| 6 | 7 | 10 | 8 | 6 |
算法设计
用
j
=
1
,
2
,
3
,
4
j = 1,2,3,4
j=1,2,3,4分别表示甲、乙、丙、丁4个企业，
c
i
j
c_{ij}
cij表示第
i
(
i
=
1
,
2
,
.
.
.
,
6
)
i(i= 1,2,...,6)
i(i=1,2,...,6)台设备分配给第j个企业创造的利润，引进0-1变量：
x
i
j
=
{
1
,
第
i
台
设
备
分
配
给
第
j
个
企
业
0
,
第
i
台
设
备
不
分
配
给
第
j
个
企
业
x_{ij} = \begin{cases} 1,\ \ \ 第i台设备分配给第j个企业 \\ 0,\ \ \ 第i台设备不分配给第j个企业\\ \end{cases}
xij={1, 第i台设备分配给第j个企业0, 第i台设备不分配给第j个企业
数学模型为：
m
a
x
∑
i
=
1
6
∑
j
=
1
4
c
i
j
x
i
j
s
.
t
.
=
{
∑
i
=
1
6
≥
1
,
j
=
1
,
2
,
3
,
4
∑
j
=
1
4
≥
1
,
i
=
1
,
2
,
.
.
.
,
6
x
i
j
=
0
或
1
,
i
=
1
,
2
,
.
.
.
6
;
j
=
1
,
2
,
3
,
4
max \sum_{i = 1}^{6} \sum_{j = 1}^{4}c_{ij}x_{ij}\\ s.t. = \begin{cases} \sum\limits^{6}_{i = 1} \geq 1,\ \ j = 1,2,3,4\\ \sum\limits^{4}_{j = 1}\geq1,\ \ i = 1,2,...,6\\ x_{ij} = 0 或 1,\ \ i = 1,2,...6;j = 1,2,3,4 \end{cases}
maxi=1∑6j=1∑4cijxijs.t.=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧i=1∑6≥1, j=1,2,3,4j=1∑4≥1, i=1,2,...,6xij=0或1, i=1,2,...6;j=1,2,3,4
- 这里用到了矩阵的点乘，需要用函数
multiply，不能直接用python内置的矩阵乘法c * x会报维度错误。函数说明参考
# 决策变量
n = (6,4)
# nonneg参数，变量是否为非负
x = cp.Variable(n,nonneg = True)
# 约束1
b1 = np.ones((6,4))
c = np.array([[4,2,3,4],
[6,4,5,5],
[7,6,7,6],
[7,8,8,6],
[7,9,8,6],
[7,10,8,6]])
# 定义问题，添加约束条件
prob = cp.Problem(cp.Maximize(cp.sum(cp.sum(cp.multiply(c,x),axis = 1),axis = 0)),
[cp.sum(x,axis = 0) >= 1,
cp.sum(x,axis = 1) == 1,
x <= b1])
# 求解
ans = prob.solve(solver=cp.GLOP)
# 输出结果
print("目标函数最大值:", ans)
# 对x向量各元素取整数后再输出
print(x.value)
输出：
目标函数最大值: 44.0
[[ 0. -0. -0. 1.]
[ 1. -0. -0. -0.]
[ 0. -0. 1. -0.]
[-0. -0. 1. -0.]
[-0. 1. -0. -0.]
[-0. 1. -0. -0.]]
习题2.4
有一场由4个项目（高低杠、平衡木、跳马、自由体操）组成的女子体操团体赛，赛程规定：每个队最多允许10名运动员参赛，每一个项目可以有6名选手参加。每个选手参赛的成绩评分从高到低依次为10、9.9、9.8、…、0.1、0。每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者。此外，还规定每个运动员只能参加全能比赛（4项全参加）与单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加3个单项。每个队应有4人参加全能比赛，其余运动员参加单项比赛。
现某代表队的教练已经对其所带领的10名运动员参加各个项目的成绩进行了大量测试，教练发现每个运动员在每个单项上的成绩稳定在4个得分上，她们得到这些成绩的相应概率也由统计得出，试解答以下问题：
（1）每个选手的各单项得分按最悲观估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高；每个选手的各单项得分按均值估算，在此前提下，请为该队排出一个出场阵容，使该队团队总分尽可能高。
（2）若对以往的资料及近期各种信息进行分析得到：本次夺冠的团体总分估计不少于236.2分，该队为了夺冠应排出怎样的阵容？以该阵容出战，其夺冠的前景如何？得分前景又如何？它有90%的把握战胜怎样水平的对手？
算法设计1
- 记
i
=
1
,
2
,
3
,
4
i = 1,2,3,4
i=1,2,3,4分别表示高低杠、平衡木、跳马、自由体操4项运动。引进决策变量：
x i j = { 1 , 第 j 个 人 参 加 第 i 个 项 目 0 , 第 j 个 人 不 参 加 第 i 个 项 目 x_{ij} = \begin{cases} 1,\ \ \ 第j个人参加第i个项目 \\ 0,\ \ \ 第j个人不参加第i个项目\\ \end{cases} xij={1, 第j个人参加第i个项目0, 第j个人不参加第i个项目
建立如下的非线性整数规划模型：
m i n ∑ i = 1 4 ∑ j = 1 6 c i j x i j s . t . = { ∑ j = 1 10 x i j = 6 , i = 1 , 2 , 3 , 4 ∑ j = 1 10 ∏ i = 1 4 x i j = 4 min \sum^{4}_{i = 1}\sum^{6}_{j = 1}c_{ij}x_{ij}\\ s.t. = \begin{cases} \sum\limits^{10}_{j = 1}x_{ij} = 6,\ \ i = 1,2,3,4\\ \sum\limits^{10}_{j = 1}\prod\limits^{4}_{i = 1}x_ij = 4\\ \end{cases} mini=1∑4j=1∑6cijxijs.t.=⎩⎪⎪⎨⎪⎪⎧j=1∑10xij=6, i=1,2,3,4j=1∑10i=1∏4xij=4
引入0-1变量：
y j = { 1 , 第 j 个 人 参 加 全 能 比 赛 0 , 第 j 个 人 不 参 加 全 能 比 赛 y_{j} = \begin{cases} 1,\ \ \ 第j个人参加全能比赛 \\ 0,\ \ \ 第j个人不参加全能比赛\\ \end{cases} yj={1, 第j个人参加全能比赛0, 第j个人不参加全能比赛
将非线性整数规划模型转换为0-1整数线性规划模型：
m i n ∑ i = 1 4 ∑ j = 1 6 c i j x i j s . t . = { ∑ j = 1 10 x i j = 6 , i = 1 , 2 , 3 , 4 4 y j ≤ ∑ i = 1 4 x i j ≤ 3 + y j , j = 1 , 2 , . . . , 10 ∑ j = 1 10 y j = 4 min \sum^{4}_{i = 1}\sum^{6}_{j = 1}c_{ij}x_{ij}\\ s.t. = \begin{cases} \sum\limits^{10}_{j = 1}x_{ij} = 6,\ \ i = 1,2,3,4\\ 4y_{j} \leq \sum\limits^{4}_{i = 1}x_{ij} \leq 3 + y_{j},\ \ j = 1,2,...,10\\ \sum\limits^{10}_{j = 1}y_{j} = 4 \end{cases} mini=1∑4j=1∑6cijxijs.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧j=1∑10xij=6, i=1,2,3,44yj≤i=1∑4xij≤3+yj, j=1,2,...,10j=1∑10yj=4 - 变量约束条件改为布尔变量
boolean = True，或整数变量integer = True，但是需要注意的是如果使用整数变量，最后需要添加条件x >= 0,x <= 1 - 更换求解器，以前的
GLOP求解器无法解决有布尔变量的线性规划，所以将求解器换成GLPK_MI - 如果提示求解器未安装，请使用
pip install cvxopt，然后再使用cp.installed_solvers()，查看已安装的求解器 - 以前使用
GLOP时语法是prob.solve(solver=cp.GLOP)，现在使用GLPK_MI，语法变为prob.solve(solver='GLPK_MI') - 数据下载
data = np.loadtxt("../input/math-modeling/data2_4.txt")
fen = data[:,0:20:2]
gai = data[:,1:20:2]
low = np.zeros([4,10])
zhun = np.zeros([4,10])
for i in range(0,4):
for j in range(0,10):
low[i,j] = fen[4*i,j]
zhun[i,j] = fen[4*i:4*(i+1),j] @ gai[4*i:4*(i+1),j]
# 决策变量
n = (4,10)
z = 10
# nonneg参数，变量是否为非负
x = cp.Variable(n,boolean = True)
y = cp.Variable(z,boolean = True)
# 定义问题，添加约束条件
prob = cp.Problem(cp.Maximize(cp.sum(cp.sum(cp.multiply(low,x)))),
[cp.sum(x,axis = 1) == 6,
cp.sum(y,axis = 0) == 4,
4 * y <= cp.sum(x,axis = 0),
cp.sum(x,axis = 0) <= 3+y])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最大值:", ans)
# 对x向量各元素取整数后再输出
print(x.value)
输出：
目标函数最大值: 212.3
[[0. 1. 0. 0. 1. 1. 1. 0. 1. 1.]
[0. 1. 0. 1. 1. 1. 0. 1. 1. 0.]
[1. 1. 0. 1. 1. 1. 0. 0. 1. 0.]
[0. 1. 1. 0. 1. 1. 0. 0. 1. 1.]]
# 定义问题，添加约束条件
prob = cp.Problem(cp.Maximize(cp.sum(cp.sum(cp.multiply(zhun,x)))),
[cp.sum(x,axis = 1) == 6,
cp.sum(y,axis = 0) == 4,
4 * y <= cp.sum(x,axis = 0),
cp.sum(x,axis = 0) <= 3+y,
x>=0,x<=1,y>=0,y<=1])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最大值:", ans)
# 对x向量各元素取整数后再输出
print(x.value)
输出：
目标函数最大值: 225.1
[[0. 1. 1. 0. 0. 1. 1. 0. 1. 1.]
[0. 1. 1. 0. 1. 0. 0. 1. 1. 1.]
[1. 1. 1. 1. 0. 0. 0. 0. 1. 1.]
[0. 1. 1. 0. 1. 0. 0. 1. 1. 1.]]
算法设计2
将团体总分236.2作为一个约束条件，得分的概率作为目标函数，建立0-1整数规划模型。用
k
=
1
,
2
,
3
,
4
k = 1,2,3,4
k=1,2,3,4记运动员参加项目得到了第
K
K
K种得分，
a
i
j
k
a_{ijk}
aijk和
b
i
j
k
b_{ijk}
bijk分别表示第
j
j
j个运动员参加第
i
i
i个项目得到的第
k
k
k种得分值及概率。记
p
i
j
p_{ij}
pij为运动员
j
j
j参加第
i
i
i个项目的某种得分的概率。
引入0-1变量：
z
i
j
k
=
{
1
,
运
动
员
j
参
加
项
目
i
得
到
a
i
j
k
分
0
,
运
动
员
j
参
加
i
项
目
没
得
到
a
i
j
k
分
z_{ijk} = \begin{cases} 1,\ \ \ 运动员j参加项目i得到a_{ijk}分 \\ 0,\ \ \ 运动员j参加i项目没得到a_{ijk}分\\ \end{cases}
zijk={1, 运动员j参加项目i得到aijk分0, 运动员j参加i项目没得到aijk分
建立如下的整数规划模型：
m
a
x
∏
i
=
1
4
∏
j
=
1
10
p
i
j
x
i
j
s
.
t
.
=
{
∑
j
=
1
10
x
i
j
=
6
,
i
=
1
,
2
,
3
,
4
4
y
j
≤
∑
i
=
1
4
x
i
j
≤
3
+
y
j
∑
j
=
1
10
y
j
=
4
p
i
j
=
∑
k
=
1
4
b
i
j
k
z
i
j
k
,
i
=
1
,
2
,
3
,
4
;
j
=
1
,
2
,
⋯
,
10
c
i
j
=
∑
k
=
1
4
a
i
j
k
z
i
j
k
,
i
=
1
,
2
,
3
,
4
;
j
=
1
,
2
,
⋯
,
10
∑
i
=
1
4
∑
j
=
1
10
c
i
j
x
i
j
≥
236.2
∑
j
=
1
4
z
i
j
k
≤
1
,
i
=
1
,
2
,
3
,
4
;
j
=
1
,
2
,
⋯
,
10
x
i
j
=
∑
k
=
1
4
z
i
j
k
,
i
=
1
,
2
,
3
,
4
;
j
=
1
,
2
,
⋯
,
10
max\ \ \prod^{4}_{i = 1}\prod^{10}_{j = 1}p_{ij}^{x_{ij}}\\ s.t. = \begin{cases} \sum\limits^{10}_{j = 1}x_{ij} = 6,\ \ i = 1,2,3,4\\ 4y_{j} \leq \sum\limits^{4}_{i = 1}x_{ij}\leq 3+y_{j}\\ \sum\limits^{10}_{j = 1}y_j = 4\\ p_{ij} = \sum\limits^{4}_{k = 1}b_{ijk}z_{ijk},\ i = 1,2,3,4;\ j = 1,2,\cdots,10\\ c_{ij} = \sum\limits^{4}_{k = 1}a_{ijk}z_{ijk},\ i = 1,2,3,4;\ j = 1,2,\cdots,10\\ \sum\limits_{i = 1}^{4}\sum\limits_{j = 1}^{10}c_{ij}x_{ij} \geq 236.2\\ \sum\limits_{j = 1}^{4}z_{ijk} \leq 1,\ i = 1,2,3,4;\ j = 1,2,\cdots,10\\ x_{ij} = \sum\limits^{4}_{k = 1}z_{ijk},\ \ i = 1,2,3,4;j = 1,2,\cdots,10 \end{cases}
max i=1∏4j=1∏10pijxijs.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧j=1∑10xij=6, i=1,2,3,44yj≤i=1∑4xij≤3+yjj=1∑10yj=4pij=k=1∑4bijkzijk, i=1,2,3,4; j=1,2,⋯,10cij=k=1∑4aijkzijk, i=1,2,3,4; j=1,2,⋯,10i=1∑4j=1∑10cijxij≥236.2j=1∑4zijk≤1, i=1,2,3,4; j=1,2,⋯,10xij=k=1∑4zijk, i=1,2,3,4;j=1,2,⋯,10
习题2.5
某单位需要加工制作 100 100 100套钢架，每套用长为 2.9 m 2.9m 2.9m、 2.1 m 2.1m 2.1m和 1 m 1m 1m的圆钢各一根。已知原料长 6.9 m 6.9m 6.9m。（1）如何下料，使用原材料最省？（2）若下料方式不超过三种，则应如何下料，使用的原材料最省？
算法设计1
- 使用枚举法列出所有可行的套裁方案。
| 目标 | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 2.9 | 1 | 2 | 0 | 0 | 0 | 0 | 1 |
| 2.1 | 0 | 0 | 3 | 2 | 1 | 0 | 1 |
| 1 | 4 | 1 | 0 | 2 | 4 | 6 | 1 |
| 合计 | 6.9 | 6.8 | 6.3 | 6.2 | 6.1 | 6 | 6 |
| 料头 | 0 | 0.1 | 0.6 | 0.7 | 0.8 | 0.9 | 0.9 |
- 为了保证完成100套钢架，所使用原材料最省，可以混合使用各种下料方案。设按方案A、B、C、D、E、F、G下料的原材料根数分别为
x
i
(
i
=
1
,
2
,
.
.
.
,
7
)
x_{i}(i = 1,2,...,7)
xi(i=1,2,...,7)，根据上表的数据建立如下线性规划模型：
m i n ∑ i = 1 7 x i s . t . = { x 1 + 2 x 2 + x 7 ≥ 100 3 x 3 + 2 x 4 + x 5 + x 7 ≥ 100 4 x 1 + x 2 + 2 x 4 + 4 x 5 + 6 x 6 + x 7 ≥ 100 , x i ≥ 0 且 为 整 数 , i = 1 , 2 , . . . , 7 min\ \ \sum^{7}_{i = 1}x_i\\ s.t. = \begin{cases} x_1 + 2x_2+x_7 \geq 100\\ 3x_3 + 2x_4 + x_5 + x_7 \geq 100\\ 4x_1 + x_2 + 2x_4 + 4x_5 + 6x_6 +x_7 \geq100,\\ x_i \geq 0且为整数,\ \ \ i = 1,2,...,7 \end{cases} min i=1∑7xis.t.=⎩⎪⎪⎪⎨⎪⎪⎪⎧x1+2x2+x7≥1003x3+2x4+x5+x7≥1004x1+x2+2x4+4x5+6x6+x7≥100,xi≥0且为整数, i=1,2,...,7 - 这题需要对自变量约束，其为整型
s = np.zeros((4,7))
temp = 0
for i in range(3):
for j in range(4):
for k in range(7):
if (2.9 * i + 2.1 * j + k > 5.9) and (2.9 * i + 2.1 * j + k <= 6.9):
s[:,temp] = np.array([i,j,k,6.9-(2.9 * i + 2.1 * j +k)]).T
temp = temp + 1
ss = s[3,:][np.argsort(s[3,:])]
idx = np.argsort(s[3,:])
s = s[:,idx]
a = s[0:3,:]
# 决策变量
n = 7
# integer,变量为整型
x = cp.Variable(n,integer = True)
# 定义问题，添加约束条件
prob = cp.Problem(cp.Minimize(cp.sum(x)),
[a @ x >= 100,x >= 0])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最小值:", ans)
print(x.value)
输出：
目标函数最小值: 91.0
[14. 43. 33. 1. 0. 0. 0.]
算法设计2
- 用
i
=
1
,
2
,
.
.
.
,
7
i = 1,2,...,7
i=1,2,...,7分别表示套裁方案A、B、C、D、E、F、G，引进0-1变量：
y i = { 1 , 采 用 第 i 种 套 裁 方 法 0 , 不 采 用 第 i 种 套 裁 方 法 y_{i} = \begin{cases} 1,\ \ \ 采用第i种套裁方法\\ 0,\ \ \ 不采用第i种套裁方法 \end{cases} yi={1, 采用第i种套裁方法0, 不采用第i种套裁方法 - 设
x
i
(
i
=
1
,
2
,
.
.
.
,
7
)
x_i(i = 1,2,...,7)
xi(i=1,2,...,7)表示采用第
i
i
i种套裁方案下料的原材料根数。建立如下整数规划模型：
m i n ∑ i = 1 7 x i s . t . = { x 1 + 2 x 2 + x 7 ≥ 100 3 x 3 + 2 x 4 + x 5 + x 7 ≥ 100 4 x 1 + x 2 + 2 x 4 + 4 x 5 + 6 x 6 + x 7 ≥ 100 , x i ≥ 0 且 为 整 数 , i = 1 , 2 , . . . , 7 x i ≤ M y , i = 1 , 2 , . . . , 7 ∑ i = 1 7 y i = 3 y i = 0 或 1 , i = 1 , 2 , . . . , 7 min\ \ \sum^{7}_{i = 1}x_i\\ s.t. = \begin{cases} x_1 + 2x_2+x_7 \geq 100\\ 3x_3 + 2x_4 + x_5 + x_7 \geq 100\\ 4x_1 + x_2 + 2x_4 + 4x_5 + 6x_6 +x_7 \geq100,\\ x_i \geq 0且为整数,\ \ \ i = 1,2,...,7\\ x_i \leq My,\ \ \ i = 1,2,...,7\\ \sum\limits^{7}_{i = 1}y_i = 3\\ y_i = 0或1,\ \ \ i = 1,2,...,7\\ \end{cases} min i=1∑7xis.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧x1+2x2+x7≥1003x3+2x4+x5+x7≥1004x1+x2+2x4+4x5+6x6+x7≥100,xi≥0且为整数, i=1,2,...,7xi≤My, i=1,2,...,7i=1∑7yi=3yi=0或1, i=1,2,...,7
# 决策变量
n = 7
k = 7
# integer,变量为整型
x = cp.Variable(n,integer = True)
# boolean，变量为布尔类型
y = cp.Variable(n,boolean = True)
# 定义问题，添加约束条件
prob = cp.Problem(cp.Minimize(cp.sum(x)),
[a @ x >= 100,
x >= 0,
x <= 10000 * y,
cp.sum(y) == 3])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最小值:", ans)
print(x.value)
输出：
目标函数最小值: 92.0
[15. 43. 34. 0. 0. 0. 0.]
习题2.6
求解整数线性规划问题
m
i
n
z
=
20
x
1
+
90
x
2
+
80
x
3
+
70
x
4
+
30
x
5
s
.
t
.
=
{
x
1
+
x
2
+
x
5
≥
30
x
3
+
x
4
≥
30
3
x
1
+
2
x
3
≤
120
3
x
2
+
2
x
4
+
x
5
≤
48
x
j
≥
0
且
为
整
数
,
j
=
1
,
2
,
.
.
.
.
,
5
min\ \ z = 20x_1 + 90x_2 + 80x_3+70x_4+30x_5\\ s.t. = \begin{cases} x_1 + x_2 + x_5 \geq 30\\ x_3 + x_4 \geq 30\\ 3x_1 + 2x_3 \leq 120\\ 3x_2 + 2x_4+ x_5 \leq 48\\ x_j \geq 0 且为整数,\ \ \ j = 1,2,....,5 \end{cases}
min z=20x1+90x2+80x3+70x4+30x5s.t.=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x1+x2+x5≥30x3+x4≥303x1+2x3≤1203x2+2x4+x5≤48xj≥0且为整数, j=1,2,....,5
算法设计
# 决策变量
n = 5
# integer,变量为整型
x = cp.Variable(n,integer = True)
# 约束1
A1 = np.array([[1,1,0,0,1],
[0,0,1,1,0]])
b1 = np.array([30,30])
# 约束2
A2 = np.array([[3,0,2,0,0],
[0,3,0,2,1]])
b2 = np.array([120,48])
# 定义问题，添加约束条件
c = np.array([20,90,80,70,30])
prob = cp.Problem(cp.Minimize(c.T @ x),
[A1 @ x >= b1,
A2 @ x <= b2,
x >= 0])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最小值:", ans)
print(x.value)
输出：
目标函数最小值: 2760.0
[30. 0. 6. 24. 0.]
习题2.7
美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件家电时分别占用的设备A和设备B的台时，调试工序时间，每天可用于这两种家电的能力，各销售一件家电的获利情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。
| 项目 | Ⅰ | Ⅱ | 每天可用能力 |
|---|---|---|---|
| 设备A/h | 0 | 5 | 15 |
| 设备B/h | 6 | 2 | 24 |
| 调试工序/h | 1 | 1 | 5 |
| 利润/元 | 2 | 1 |
算法设计
- 设
x
1
,
x
2
x_{1},x_{2}
x1,x2分别表示美佳公司每天制造家电Ⅰ、Ⅱ的产量，建立整数规划：
m a x z = 2 x 1 + x 2 s . t . = { 5 x 2 ≤ 15 6 x 1 + 2 x 2 ≤ 24 x 1 + x 2 ≤ 5 x 1 , x 2 ≥ 0 且 为 整 数 max\ \ z = 2x_1 + x_2\\ s.t. = \begin{cases} 5x_2 \leq 15 \\ 6x_1 + 2x_2 \leq 24\\ x_1 + x_2 \leq 5\\ x_1,x_2 \geq 0\ 且为整数 \end{cases} max z=2x1+x2s.t.=⎩⎪⎪⎪⎨⎪⎪⎪⎧5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0 且为整数
# 决策变量
n = 2
# integer,变量为整型
x = cp.Variable(n,integer = True)
# 约束1
A1 = np.array([[0,5],
[6,2],
[1,1]])
b1 = np.array([15,24,5])
# 约束2
A2 = np.array([[1,0],
[0,1]])
b2 = np.array([0,0])
# 定义问题，添加约束条件
c = np.array([2,1])
prob = cp.Problem(cp.Maximize(c.T @ x),
[A1 @ x <= b1,
A2 @ x >= b2])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最大值:", ans)
print(x.value)
输出：
目标函数最大值: 8.0
[4. 0.]
习题2.8
求解标准的指派问题，其中指派矩阵
C
=
[
6
7
5
8
9
10
6
3
7
9
3
8
8
11
12
6
7
9
9
7
5
4
7
6
5
8
9
6
10
7
9
8
7
6
5
9
]
C = \begin{bmatrix} 6 & 7 & 5 & 8 & 9 & 10\\ 6 & 3 & 7 & 9 & 3 & 8\\ 8 & 11 & 12 & 6 & 7 & 9\\ 9 & 7 & 5 & 4 & 7 & 6\\ 5 & 8 & 9 & 6 & 10 & 7\\ 9 & 8 & 7 & 6 & 5 & 9\\ \end{bmatrix}
C=⎣⎢⎢⎢⎢⎢⎢⎡6689597311788571259789646693771051089679⎦⎥⎥⎥⎥⎥⎥⎤
算法设计
- 记
C
=
(
c
i
j
)
6
×
6
C = (c_{ij})_{6 \times 6}
C=(cij)6×6，引进0-1变量：
x i j = { 1 , 第 i 个 人 干 第 j 项 工 作 0 , 第 i 个 人 不 干 第 j 项 工 作 x_{ij} = \begin{cases} 1,\ \ \ 第i个人干第j项工作\\ 0,\ \ \ 第i个人不干第j项工作 \end{cases} xij={1, 第i个人干第j项工作0, 第i个人不干第j项工作 - 指派问题的0-1数学模型为：
m i n z = ∑ i = 1 6 ∑ j = 1 6 c i j x i j s . t . = { ∑ i = 1 6 x i j = 1 , i = 1 , 2 , . . . , 6 ∑ i = 1 6 x i j = 1 , j = 1 , 2 , . . . , 6 x i j = 0 或 1. i , j = 1 , 2 , . . . , 6 min\ \ z = \sum^{6}_{i = 1}\sum^{6}_{j = 1}c_{ij}x_{ij}\\ s.t. = \begin{cases} \sum\limits^{6}_{i = 1}x_{ij} = 1,\ \ i = 1,2,...,6\\ \sum\limits^{6}_{i = 1}x_{ij} = 1,\ \ j = 1,2,...,6\\ x_{ij} = 0或1.i,\ \ j = 1,2,...,6 \end{cases} min z=i=1∑6j=1∑6cijxijs.t.=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧i=1∑6xij=1, i=1,2,...,6i=1∑6xij=1, j=1,2,...,6xij=0或1.i, j=1,2,...,6
# 决策变量
n = (6,6)
# integer,变量为整型
x = cp.Variable(n,boolean = True)
c = np.array([[6,7,5,8,9,10],
[6,3,7,9,3,8],
[8,11,12,6,7,9],
[9,7,5,4,7,6],
[5,8,9,6,10,7],
[9,8,7,6,5,9]])
prob = cp.Problem(cp.Minimize(cp.sum(cp.sum(cp.multiply(c,x)))),
[cp.sum(x,axis = 0) == 1,
cp.sum(x,axis = 1) == 1])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最大值:", ans)
print(x.value)
输出：
目标函数最大值: 30.0
[[0. 0. 1. 0. 0. 0.]
[0. 1. 0. 0. 0. 0.]
[0. 0. 0. 1. 0. 0.]
[0. 0. 0. 0. 0. 1.]
[1. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 1. 0.]]
习题2.9
已知某物质有8个配送中心可以供货，有15个部队用户需要该物资，配送中心和部队用户之间单位物质的运费、15个部队用户的物质需求量和8个配送中心的物质储备量数据。
（1）根据题目给定的数据，求最小运费调用计划。
（2）若每个配送中心，可以对某个用户配送物资，也可以不对某个用户配送物资；若配送物资，配送量要大于等于1000且小于等于2000，求此时的费用最小调用计划。
算法设计1
- 根据题意，建立如下的夏新规划模型：
m i n z = ∑ i = 1 15 ∑ j = 1 8 c i j x i j s . t . = { ∑ i = 1 15 x i j ≤ b j , i = 1 , 2 , . . . , 8 ∑ i = 1 8 x i j = a i , j = 1 , 2 , . . . , 15 x i j ≥ 0 , i = 1 , 2 , . . . , 15 j = 1 , 2 , . . . , 6 min\ \ z = \sum^{15}_{i = 1}\sum^{8}_{j = 1}c_{ij}x_{ij}\\ s.t. = \begin{cases} \sum\limits^{15}_{i = 1}x_{ij} \leq b_j,\ \ i = 1,2,...,8\\ \sum\limits^{8}_{i = 1}x_{ij} = a_i,\ \ j = 1,2,...,15\\ x_{ij} \geq 0,\ \ i = 1,2,...,15\ \ j = 1,2,...,6 \end{cases} min z=i=1∑15j=1∑8cijxijs.t.=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧i=1∑15xij≤bj, i=1,2,...,8i=1∑8xij=ai, j=1,2,...,15xij≥0, i=1,2,...,15 j=1,2,...,6
d = np.loadtxt("../input/math-modeling/data2_9_1.txt")
a = d[0:-1,-1]
b = d[-1,0:-1]
c = d[0:-1,0:-1]
# 决策变量
n = (15,8)
# integer,变量为整型
x = cp.Variable(n,integer = True)
prob = cp.Problem(cp.Minimize(cp.sum(cp.sum(cp.multiply(c,x)))),
[cp.sum(x,axis = 0) <= b,
cp.sum(x,axis = 1) == a,
x >= 0])
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最小值:", ans)
print(x.value)
输出：
目标函数最小值: 9244730.0
[[ 0. 0. 0. 0. 0. 3000. 0. 0.]
[ 0. 0. 0. 0. 3100. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 2900.]
[ 0. 0. 3100. 0. 0. 0. 0. 0.]
[3100. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 3400. 0. 0. 0. 0.]
[ 0. 3500. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 3200. 0. 0. 0. 0.]
[ 0. 3000. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 3100.]
[ 0. 0. 0. 0. 0. 0. 3300. 0.]
[ 0. 0. 0. 0. 0. 0. 3200. 0.]
[ 0. 0. 0. 0. 0. 0. 3300. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 2900.]
[ 0. 0. 0. 0. 0. 0. 0. 3100.]]
算法设计2
- 引入0-1变量：
y i j = { 1 , 第 j 个 配 送 中 心 供 应 第 i 个 用 户 0 , 第 j 个 配 送 中 心 不 供 应 第 i 个 用 户 y_{ij} = \begin{cases} 1,\ \ \ 第j个配送中心供应第i个用户\\ 0,\ \ \ 第j个配送中心不供应第i个用户 \end{cases} yij={1, 第j个配送中心供应第i个用户0, 第j个配送中心不供应第i个用户 - 建立如下的混合整数线性规划模型：
m i n z = ∑ i = 1 15 ∑ j = 1 8 c i j x i j s . t . = { ∑ i = 1 15 x i j ≤ b j , i = 1 , 2 , . . . , 8 ∑ i = 1 8 x i j = a i , j = 1 , 2 , . . . , 15 1000 y i j ≤ x i j ≤ 2000 y i j , i = 1 , 2 , . . . , 15 j = 1 , 2 , . . . , 6 y i j = 0 或 1 , i = 1 , 2 , . . . , 15 j = 1 , 2 , . . . , 6 min\ \ z = \sum^{15}_{i = 1}\sum^{8}_{j = 1}c_{ij}x_{ij}\\ s.t. = \begin{cases} \sum\limits^{15}_{i = 1}x_{ij} \leq b_j,\ \ i = 1,2,...,8\\ \sum\limits^{8}_{i = 1}x_{ij} = a_i,\ \ j = 1,2,...,15\\ 1000y_{ij} \leq x_{ij} \leq 2000y_{ij},\ \ i = 1,2,...,15\ \ j = 1,2,...,6\\ y_{ij} = 0或1,\ \ i = 1,2,...,15\ \ j = 1,2,...,6\\ \end{cases} min z=i=1∑15j=1∑8cijxijs.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧i=1∑15xij≤bj, i=1,2,...,8i=1∑8xij=ai, j=1,2,...,151000yij≤xij≤2000yij, i=1,2,...,15 j=1,2,...,6yij=0或1, i=1,2,...,15 j=1,2,...,6
输出：
目标函数最小值: 12682750.0
[[ 0. 0. 0. 0. 1000. 2000. 0. 0.]
[ 0. 0. 0. 0. 2000. 1100. 0. 0.]
[ 0. 0. 1000. 0. 0. 0. 0. 1900.]
[ 0. 0. 2000. 0. 1100. 0. 0. 0.]
[2000. 0. 0. 1100. 0. 0. 0. 0.]
[1400. 0. 0. 2000. 0. 0. 0. 0.]
[1500. 2000. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 2000. 1200. 0. 0. 0.]
[1000. 2000. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 1100. 0. 0. 0. 0. 2000.]
[ 0. 0. 0. 0. 0. 0. 2000. 1300.]
[ 0. 0. 0. 1200. 0. 0. 2000. 0.]
[ 0. 0. 0. 1300. 0. 0. 2000. 0.]
[ 0. 0. 1000. 0. 0. 0. 0. 1900.]
[ 0. 0. 0. 1100. 0. 0. 0. 2000.]]
习题2.10
有4名同学到一家公司参加3个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在3个阶段的面试时间也不同，如下表所示。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早餐8:00，请问他们最早何时能离开公司？
| 同学 | 秘书初试 | 主管复试 | 经理面试 |
|---|---|---|---|
| 同学甲 | 14 | 16 | 21 |
| 同学乙 | 19 | 17 | 10 |
| 同学丙 | 10 | 15 | 12 |
| 同学丁 | 9 | 12 | 13 |
算法设计
- 记
t
i
j
t_{ij}
tij为第
i
i
i名同学参加第
j
j
j阶段面试需要的时间，令
x
i
j
x_{ij}
xij表示第
i
i
i名同学参加第
j
j
j阶段面试的开始时间，
T
T
T为完成全部面试所花费的时间。引进0-1变量：
y i k = { 1 , 第 i 名 同 学 在 第 k 名 同 学 前 面 面 试 0 , 第 k 名 同 学 在 第 i 名 同 学 前 面 面 试 y_{ik} = \begin{cases} 1,\ \ \ 第i名同学在第k名同学前面面试\\ 0,\ \ \ 第k名同学在第i名同学前面面试 \end{cases} yik={1, 第i名同学在第k名同学前面面试0, 第k名同学在第i名同学前面面试 - 由此建立如下的混合整数规划模型：
m i n T s . t . = { T ≥ x i 3 + t i 3 , i = 1 , 2 , 3 , 4 x i j + t i j ≤ x i , j + 1 , i = 1 , 2 , 3 , 4 ; j = 1 , 2 x i j + t i j ≤ x k j + 10000 ( 1 − y i k ) , 1 ≤ i < k ≤ 4 ; j = 1 , 2 , 3 x k j + t k j ≤ x i j + 10000 y i k , 1 ≤ i < k ≤ 4 ; j = 1 , 2 , 3 y i k = 0 或 1 , 1 ≤ i < k ≤ 4 min\ \ T\\ s.t. = \begin{cases} T \geq x_{i3} + t_{i3},\ \ i = 1,2,3,4\\ x_{ij} + t_{ij} \leq x_{i,j+1},\ \ i = 1,2,3,4;\ \ j=1,2\\ x_{ij} + t_{ij} \leq x_{kj} + 10000(1-y_{ik}),\ \ 1 \leq i < k \leq 4;\ \ j = 1,2,3\\ x_{kj} + t_{kj} \leq x_{ij} + 10000y_{ik},\ \ 1 \leq i < k \leq 4;\ \ j = 1,2,3\\ y_{ik} = 0或1,\ \ 1 \leq i < k \leq 4 \end{cases} min Ts.t.=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧T≥xi3+ti3, i=1,2,3,4xij+tij≤xi,j+1, i=1,2,3,4; j=1,2xij+tij≤xkj+10000(1−yik), 1≤i<k≤4; j=1,2,3xkj+tkj≤xij+10000yik, 1≤i<k≤4; j=1,2,3yik=0或1, 1≤i<k≤4 - 对于大量有循环约束，可以在Python中定义一个列表，然后使用for循环来追加或扩展约束
t = np.array([[14,16,21],
[19,17,10],
[10,15,12],
[9,12,13]])
x = cp.Variable((4,3),nonneg = True)
y = cp.Variable((4,4),boolean = True)
T = cp.Variable(1)
constraints = [x[:,2] + t[:,2] <= T]
for i in range(4):
for j in range(2):
constraints += [x[i,j] + t[i,j] <= x[i,j+1]]
for i in range(3):
for j in range(3):
for k in range(i+1,4):
constraints += [x[i,j] + t[i,j] <= x[k,j] + 10000 * (1-y[i,k]),
x[k,j] + t[k,j] <= x[i,j] + 10000 * y[i,k]]
prob = cp.Problem(cp.Minimize(T),constraints)
# 求解
ans = prob.solve(solver='GLPK_MI')
# 输出结果
print("目标函数最小值:", ans)
print(x.value)
输出：
目标函数最小值: 82.0
[[ 9. 23. 39.]
[33. 54. 72.]
[23. 39. 60.]
[-0. 9. 21.]]
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
17
0- 0
已为社区贡献3条内容
所有评论(0)