案例(接力队员的选拔)

下表展示了5名接力队员A,B,C,D,E 在四种泳姿上的最快时间，现在要选拔其中四名运动员组成接力队（每名运动员选其中一种泳姿，每名运动员所选的泳姿不同）

决策变量

• $x_{ij}$: 第$j$个人是否选择第$i$项泳姿；$x_{ij}\in \{0,1\}$,$x_{ij}=1$代表选择该泳姿，$x_{ij}=0$代表不选择。

参数

• $T_{ij}$:第$j$个人游第$i$项泳姿的时间

目标函数

$$\min \quad \sum_{j=1}^{5}\sum_{i=1}^4 T_{ij}x_{ij}$$

约束条件

• 一个人至多能游一种泳姿 $$\sum_{i=1}^{4} x_{ij}\le 1,j=1,2,3,4,5 $$

• 一种泳姿只能一个人游

$$\sum_{j=1}^5 x_{ij}=1,i=1,2,3,4$$

PuLP 库求解过程

第一步：初始化模型

import pulp as lp # 引入库
import pandas as pd # 引入Pandas库
model = lp.LpProblem('swim',lp.LpMinimize) # 定义模型名字及模型是最大化还是最小化目标函数，这里是最小化

通过lp.LpProblem定义模型，其参数设置为：

• name:是模型的名子。
• sense: 用来指定求最小值/最大值问题，可选参数值：LpMinimize,LpMaximize 。

第二步：定义决策变量

# 变量和参数
data = {'泳姿1': {'A': 56, 'B': 63, 'C': 57, 'D': 55, 'E': 60},
            '泳姿2': {'A': 74, 'B': 69, 'C': 77, 'D': 76, 'E': 71},
            '泳姿3': {'A': 61, 'B': 65, 'C': 63, 'D': 62, 'E': 62},
            '泳姿4': {'A': 63, 'B': 71, 'C': 67, 'D': 62, 'E': 68}}
swim = pd.DataFrame(data) # 转换为DataFrame数据类型
persons = swim.columns # 列名为队员名字
forms = swim.index # 索引为泳姿名字

x = lp.LpVariable.dicts('x_ij',[(i,j) for i in forms for j in persons],cat='Binary') # x[i,j]表示第j人承担第i种泳姿

lp.LpVariable.dicts定义决策变量,其参数设置为：

• name: 是用户定义的变量组的名字。
• indexs: 设定索引的名字。lp.LpVariable.dicts可以批量设置变量，indexs是给变量组每个变量的索引列表。
• lowBound、upBound :设定决策变量的下界、上界；默认的下界是负无穷,上界为正无穷（就是实数范围）。
• cat :设定变量类型，可选参数值：Continuous 表示连续变量（默认值）、Integer 表示离散变量（用于整数规划问题）、Binary 表示0/1变量（用于0/1规划问题）。

第三步：定义目标函数

objective = lp.lpSum([swim.loc[i,j]*x[i,j] for i in forms for j in persons]) # 定义目标函数，lpSum是对变量求和
model += objective,'Minimize_the_total_time'  # 将目标函数添加到模型中，并定义目标函数的名字为  'Minimize_the_total_time'

添加目标函数使用 “问题名 += 目标函数式” 格式。

第四步：定义约束条件

# 约束条件1: 每个人至多游一个泳姿
for j in persons:
    model += lp.lpSum([x[i,j] for i in forms])<=1, f'constraint_{j}'
# 约束条件2: 每个泳姿只能由一个人游
for i in forms:
    model += lp.lpSum([x[i,j] for j in persons])==1, f'constraint_{i}'

添加约束条件使用 “问题名 += 约束条件表达式” 格式。约束条件可以是等式约束或不等式约束，不等式约束可以是 小于等于 或 大于等于，分别使用关键字>=、<=,等式约束使用==。

第五步：求解

model.solve()

solve() 是求解函数。PuLP默认采用 CBC 求解器来求解优化问题，也可以调用其它的优化器来求解，如：GLPK，COIN CLP/CBC，CPLEX，和GUROBI，但需要另外安装。

model.solve()结果输出为1表明求解成功。

第六步：查看求解结果

打印模型

print(model)

结果为：

swim:
MINIMIZE
56*x_ij_('A',_'泳姿1') + 74*x_ij_('A',_'泳姿2') + 61*x_ij_('A',_'泳姿3') + 63*x_ij_('A',_'泳姿4') + 63*x_ij_('B',_'泳姿1') + 69*x_ij_('B',_'泳姿2') + 65*x_ij_('B',_'泳姿3') + 71*x_ij_('B',_'泳姿4') + 57*x_ij_('C',_'泳姿1') + 77*x_ij_('C',_'泳姿2') + 63*x_ij_('C',_'泳姿3') + 67*x_ij_('C',_'泳姿4') + 55*x_ij_('D',_'泳姿1') + 76*x_ij_('D',_'泳姿2') + 62*x_ij_('D',_'泳姿3') + 62*x_ij_('D',_'泳姿4') + 60*x_ij_('E',_'泳姿1') + 71*x_ij_('E',_'泳姿2') + 62*x_ij_('E',_'泳姿3') + 68*x_ij_('E',_'泳姿4') + 0
SUBJECT TO
constraint_泳姿1: x_ij_('A',_'泳姿1') + x_ij_('B',_'泳姿1') + x_ij_('C',_'泳姿1')
 + x_ij_('D',_'泳姿1') + x_ij_('E',_'泳姿1') <= 1

constraint_泳姿2: x_ij_('A',_'泳姿2') + x_ij_('B',_'泳姿2') + x_ij_('C',_'泳姿2')
 + x_ij_('D',_'泳姿2') + x_ij_('E',_'泳姿2') <= 1

constraint_泳姿3: x_ij_('A',_'泳姿3') + x_ij_('B',_'泳姿3') + x_ij_('C',_'泳姿3')
 + x_ij_('D',_'泳姿3') + x_ij_('E',_'泳姿3') <= 1

constraint_泳姿4: x_ij_('A',_'泳姿4') + x_ij_('B',_'泳姿4') + x_ij_('C',_'泳姿4')
 + x_ij_('D',_'泳姿4') + x_ij_('E',_'泳姿4') <= 1

constraint_A: x_ij_('A',_'泳姿1') + x_ij_('A',_'泳姿2') + x_ij_('A',_'泳姿3')
 + x_ij_('A',_'泳姿4') = 1

constraint_B: x_ij_('B',_'泳姿1') + x_ij_('B',_'泳姿2') + x_ij_('B',_'泳姿3')
 + x_ij_('B',_'泳姿4') = 1

constraint_C: x_ij_('C',_'泳姿1') + x_ij_('C',_'泳姿2') + x_ij_('C',_'泳姿3')
 + x_ij_('C',_'泳姿4') = 1

constraint_D: x_ij_('D',_'泳姿1') + x_ij_('D',_'泳姿2') + x_ij_('D',_'泳姿3')
 + x_ij_('D',_'泳姿4') = 1

constraint_E: x_ij_('E',_'泳姿1') + x_ij_('E',_'泳姿2') + x_ij_('E',_'泳姿3')
 + x_ij_('E',_'泳姿4') = 1

VARIABLES
0 <= x_ij_('A',_'泳姿1') <= 1 Integer
0 <= x_ij_('A',_'泳姿2') <= 1 Integer
0 <= x_ij_('A',_'泳姿3') <= 1 Integer
0 <= x_ij_('A',_'泳姿4') <= 1 Integer
0 <= x_ij_('B',_'泳姿1') <= 1 Integer
0 <= x_ij_('B',_'泳姿2') <= 1 Integer
0 <= x_ij_('B',_'泳姿3') <= 1 Integer
0 <= x_ij_('B',_'泳姿4') <= 1 Integer
0 <= x_ij_('C',_'泳姿1') <= 1 Integer
0 <= x_ij_('C',_'泳姿2') <= 1 Integer
0 <= x_ij_('C',_'泳姿3') <= 1 Integer
0 <= x_ij_('C',_'泳姿4') <= 1 Integer
0 <= x_ij_('D',_'泳姿1') <= 1 Integer
0 <= x_ij_('D',_'泳姿2') <= 1 Integer
0 <= x_ij_('D',_'泳姿3') <= 1 Integer
0 <= x_ij_('D',_'泳姿4') <= 1 Integer
0 <= x_ij_('E',_'泳姿1') <= 1 Integer
0 <= x_ij_('E',_'泳姿2') <= 1 Integer
0 <= x_ij_('E',_'泳姿3') <= 1 Integer
0 <= x_ij_('E',_'泳姿4') <= 1 Integer

查看目标函数值和变量值

print('目标函数值为:'lp.value(model.objective)) # 目标函数值
print('决策变量值:')
for f in forms:
    for p in persons:
        print((f,p),lp.value(x[f,p])) # 决策变量值

通过value函数可以查看模型目标函数和变量的取值。

目标函数值为: 249.0
决策变量值:
('泳姿1', 'A') 0.0
('泳姿1', 'B') 0.0
('泳姿1', 'C') 1.0
('泳姿1', 'D') 0.0
('泳姿1', 'E') 0.0
('泳姿2', 'A') 0.0
('泳姿2', 'B') 1.0
('泳姿2', 'C') 0.0
('泳姿2', 'D') 0.0
('泳姿2', 'E') 0.0
('泳姿3', 'A') 1.0
('泳姿3', 'B') 0.0
('泳姿3', 'C') 0.0
('泳姿3', 'D') 0.0
('泳姿3', 'E') 0.0
('泳姿4', 'A') 0.0
('泳姿4', 'B') 0.0
('泳姿4', 'C') 0.0
('泳姿4', 'D') 1.0
('泳姿4', 'E') 0.0

这里的0代表不存在前面的组合，如('泳姿1', 'A') 0.0表示A不进行泳姿1;('泳姿2', 'B') 1.0表示B承担泳姿2

完整代码

import pulp as lp # 引入库
import pandas as pd # 引入Pandas库
model = lp.LpProblem('swim',lp.LpMinimize) # 定义模型名字及模型是最大化还是最小化目标函数，这里是最小化
# 变量和参数
data = {'泳姿1': {'A': 56, 'B': 63, 'C': 57, 'D': 55, 'E': 60},
            '泳姿2': {'A': 74, 'B': 69, 'C': 77, 'D': 76, 'E': 71},
            '泳姿3': {'A': 61, 'B': 65, 'C': 63, 'D': 62, 'E': 62},
            '泳姿4': {'A': 63, 'B': 71, 'C': 67, 'D': 62, 'E': 68}}
swim = pd.DataFrame(data) # 转换为DataFrame数据类型
persons = swim.columns # 列名为队员名字
forms = swim.index # 索引为泳姿名字
x = lp.LpVariable.dicts('x_ij',[(i,j) for i in forms for j in persons],cat='Binary') # x[i,j]表示第j人承担第i种泳姿
objective = lp.lpSum([swim.loc[i,j]*x[i,j] for i in forms for j in persons]) # 定义目标函数，lpSum是对变量求和
model += objective,'Minimize_the_total_time'  # 将目标函数添加到模型中，并定义目标函数的名字为  'Minimize_the_total_time'
# 约束条件1: 每个人至多游一个泳姿
for j in persons:
    model += lp.lpSum([x[i,j] for i in forms])<=1, f'constraint_{j}'
# 约束条件2: 每个泳姿只能由一个人游
for i in forms:
    model += lp.lpSum([x[i,j] for j in persons])==1, f'constraint_{i}'
model.solve()
print('目标函数值为:',lp.value(model.objective)) # 目标函数值
print('决策变量值:')
for f in forms:
    for p in persons:
        print((f,p),lp.value(x[f,p])) # 决策变量值

---

import pulp as lp # 引入库
import pandas as pd # 引入Pandas库
model = lp.LpProblem('swim',lp.LpMinimize) # 定义模型名字及模型是最大化还是最小化目标函数，这里是最小化
# 变量和参数
data = {'泳姿1': {'A': 56, 'B': 63, 'C': 57, 'D': 55, 'E': 60},
            '泳姿2': {'A': 74, 'B': 69, 'C': 77, 'D': 76, 'E': 71},
            '泳姿3': {'A': 61, 'B': 65, 'C': 63, 'D': 62, 'E': 62},
            '泳姿4': {'A': 63, 'B': 71, 'C': 67, 'D': 62, 'E': 68}}
swim = pd.DataFrame(data) # 转换为DataFrame数据类型
persons = swim.columns # 列名为队员名字
forms = swim.index # 索引为泳姿名字
x = lp.LpVariable.dicts('x_ij',[(i,j) for i in forms for j in persons],cat='Binary') # x[i,j]表示第j人承担第i种泳姿
objective = lp.lpSum([swim.loc[i,j]*x[i,j] for i in forms for j in persons]) # 定义目标函数，lpSum是对变量求和
model += objective,'Minimize_the_total_time'  # 将目标函数添加到模型中，并定义目标函数的名字为  'Minimize_the_total_time'
# 约束条件1: 每个人至多游一个泳姿
for j in persons:
    model += lp.lpSum([x[i,j] for i in forms])<=1, f'constraint_{j}'
# 约束条件2: 每个泳姿只能由一个人游
for i in forms:
    model += lp.lpSum([x[i,j] for j in persons])==1, f'constraint_{i}'
model.solve()
print('目标函数值为:',lp.value(model.objective)) # 目标函数值
print('决策变量值:')
for f in forms:
    for p in persons:
        print((f,p),lp.value(x[f,p])) # 决策变量值

目标函数值为: 320.0
决策变量值:
('A', '泳姿1') 0.0
('A', '泳姿2') 0.0
('A', '泳姿3') 1.0
('A', '泳姿4') 0.0
('B', '泳姿1') 0.0
('B', '泳姿2') 1.0
('B', '泳姿3') 0.0
('B', '泳姿4') 0.0
('C', '泳姿1') 1.0
('C', '泳姿2') 0.0
('C', '泳姿3') 0.0
('C', '泳姿4') 0.0
('D', '泳姿1') 0.0
('D', '泳姿2') 0.0
('D', '泳姿3') 0.0
('D', '泳姿4') 1.0
('E', '泳姿1') 0.0
('E', '泳姿2') 1.0
('E', '泳姿3') 0.0
('E', '泳姿4') 0.0

print(model)

swim:
MINIMIZE
56*x_ij_('A',_'泳姿1') + 74*x_ij_('A',_'泳姿2') + 61*x_ij_('A',_'泳姿3') + 63*x_ij_('A',_'泳姿4') + 63*x_ij_('B',_'泳姿1') + 69*x_ij_('B',_'泳姿2') + 65*x_ij_('B',_'泳姿3') + 71*x_ij_('B',_'泳姿4') + 57*x_ij_('C',_'泳姿1') + 77*x_ij_('C',_'泳姿2') + 63*x_ij_('C',_'泳姿3') + 67*x_ij_('C',_'泳姿4') + 55*x_ij_('D',_'泳姿1') + 76*x_ij_('D',_'泳姿2') + 62*x_ij_('D',_'泳姿3') + 62*x_ij_('D',_'泳姿4') + 60*x_ij_('E',_'泳姿1') + 71*x_ij_('E',_'泳姿2') + 62*x_ij_('E',_'泳姿3') + 68*x_ij_('E',_'泳姿4') + 0
SUBJECT TO
constraint_泳姿1: x_ij_('A',_'泳姿1') + x_ij_('B',_'泳姿1') + x_ij_('C',_'泳姿1')
 + x_ij_('D',_'泳姿1') + x_ij_('E',_'泳姿1') <= 1

constraint_泳姿2: x_ij_('A',_'泳姿2') + x_ij_('B',_'泳姿2') + x_ij_('C',_'泳姿2')
 + x_ij_('D',_'泳姿2') + x_ij_('E',_'泳姿2') <= 1

constraint_泳姿3: x_ij_('A',_'泳姿3') + x_ij_('B',_'泳姿3') + x_ij_('C',_'泳姿3')
 + x_ij_('D',_'泳姿3') + x_ij_('E',_'泳姿3') <= 1

constraint_泳姿4: x_ij_('A',_'泳姿4') + x_ij_('B',_'泳姿4') + x_ij_('C',_'泳姿4')
 + x_ij_('D',_'泳姿4') + x_ij_('E',_'泳姿4') <= 1

constraint_A: x_ij_('A',_'泳姿1') + x_ij_('A',_'泳姿2') + x_ij_('A',_'泳姿3')
 + x_ij_('A',_'泳姿4') = 1

constraint_B: x_ij_('B',_'泳姿1') + x_ij_('B',_'泳姿2') + x_ij_('B',_'泳姿3')
 + x_ij_('B',_'泳姿4') = 1

constraint_C: x_ij_('C',_'泳姿1') + x_ij_('C',_'泳姿2') + x_ij_('C',_'泳姿3')
 + x_ij_('C',_'泳姿4') = 1

constraint_D: x_ij_('D',_'泳姿1') + x_ij_('D',_'泳姿2') + x_ij_('D',_'泳姿3')
 + x_ij_('D',_'泳姿4') = 1

constraint_E: x_ij_('E',_'泳姿1') + x_ij_('E',_'泳姿2') + x_ij_('E',_'泳姿3')
 + x_ij_('E',_'泳姿4') = 1

VARIABLES
0 <= x_ij_('A',_'泳姿1') <= 1 Integer
0 <= x_ij_('A',_'泳姿2') <= 1 Integer
0 <= x_ij_('A',_'泳姿3') <= 1 Integer
0 <= x_ij_('A',_'泳姿4') <= 1 Integer
0 <= x_ij_('B',_'泳姿1') <= 1 Integer
0 <= x_ij_('B',_'泳姿2') <= 1 Integer
0 <= x_ij_('B',_'泳姿3') <= 1 Integer
0 <= x_ij_('B',_'泳姿4') <= 1 Integer
0 <= x_ij_('C',_'泳姿1') <= 1 Integer
0 <= x_ij_('C',_'泳姿2') <= 1 Integer
0 <= x_ij_('C',_'泳姿3') <= 1 Integer
0 <= x_ij_('C',_'泳姿4') <= 1 Integer
0 <= x_ij_('D',_'泳姿1') <= 1 Integer
0 <= x_ij_('D',_'泳姿2') <= 1 Integer
0 <= x_ij_('D',_'泳姿3') <= 1 Integer
0 <= x_ij_('D',_'泳姿4') <= 1 Integer
0 <= x_ij_('E',_'泳姿1') <= 1 Integer
0 <= x_ij_('E',_'泳姿2') <= 1 Integer
0 <= x_ij_('E',_'泳姿3') <= 1 Integer
0 <= x_ij_('E',_'泳姿4') <= 1 Integer

---