数学模型

Wang Haihua

🍈 🍉🍊 🍋 🍌

---

0-1规划

当整数规划问题中的整数型决策变量限制为只能取0或1时，称为0-1整数规划，简称为0-1规划。

因为0-1规划问题的解空间比一般的整数规划问题较少，求解起来较为容易，且所有的整数规划问题都可以化为0-1规划问题，所以在建立混合整数规划模型求解实际问题时，应尽量使用0-1决策变量进行建模。

例如：有十个工厂可供决策时，可以使用10个0-1变量，当取值为0时时代表不使用这个工厂，取值为1时使用该工厂。

0-1规划的常用求解方法：分支定界算法、割平面法、隐枚举法

指派问题

拟分配$n$个人去做$n$项工作，每人干且仅干一项工作，若分配第$i$人去干第$j$项工作，需花费$c_{ij}$时间，问应该如何分配工作才能使工人们总的花费时间最少？

解： 引入变量$x_{ij}$，若分配$i$做第$j$项工作，则取$x_{ij} =1$，否则$x_{ij} = 0$，上述指派问题的数学模型为：

$$ \begin{aligned} &{\min \quad \sum_{i=1}^{n} \sum_{j=1}^{n} c_{i j} x_{i j}}\\ s.t.&\left\{\begin{array}{ll} {\displaystyle\sum_{j=1}^{n} x_{i j}=1} \\ {\displaystyle\sum_{i=1}^{n} x_{i j}=1} \\ {x_{i j}=0 或 1} \end{array}\right. \end{aligned} $$

其中第二个、第三个约束条件表明的是“每个人只能负责一项工作”以及“每项工作只能交给一个人来做”。

案例(接力队员的分工）

现有4名接力队员ABCD,他们在各个泳姿的最好成绩如下表所示(数字越小越好），现要分配四个运动员的分工，问如何分工可以使整个接力队成绩最好？

	泳姿1	泳姿2	泳姿3	泳姿4
A	56	74	61	63
B	63	69	65	71
C	57	77	63	67
D	55	76	62	62

解： 建立指派问题模型 引入变量$x_{ij}$，若分配第$i$个运动员进行泳姿$j$，则取$x_{ij} =1$，否则$x_{ij} = 0$，上述指派问题的数学模型为：

$$ \begin{aligned} &{\min \quad \sum_{i=1}^{n} \sum_{j=1}^{n} c_{i j} x_{i j}}\\ s.t.&\left\{\begin{array}{ll} {\displaystyle\sum_{j=1}^{n} x_{i j}=1} \\ {\displaystyle\sum_{i=1}^{n} x_{i j}=1} \\ {x_{i j}=0 或 1} \end{array}\right. \end{aligned} $$

我们使用Python线性规划第三方库Pulp求解，得到最优安排如下

	泳姿1	泳姿2	泳姿3	泳姿4
A	0	0	1	0
B	0	1	0	0
C	1	0	0	0
D	0	0	0	1

在这种安排下总时间为249.0

参考资料

• 姜启源, 谢金星, 叶俊. 数学模型.第4版[M]. 高等教育出版社, 2011.
• https://en.wikipedia.org/wiki/Integer_programming
• https://github.com/ThomsonRen/mathmodels

---

import numpy as np
import pulp as lp
import pandas as pd
from model_insight.load_datasets import load_swim

swim = load_swim()

swim

	泳姿1	泳姿2	泳姿3	泳姿4
A	56	74	61	63
B	63	69	65	71
C	57	77	63	67
D	55	76	62	62

# initialize the model and data
model = lp.LpProblem(name="swim_team",sense=lp.LpMinimize)
people = swim.index
jobs = swim.columns

# variables
xij = lp.LpVariable.dicts(name='assignment',indexs=[(i,j) for i in people for j in jobs],cat='Binary')

# objective funtion
objective = lp.lpSum([xij[i,j]*swim.loc[i,j] for i in people for j in jobs])
model += objective,'objective_function'
# constraints
## constraints for people
for i in people:
    model += lp.lpSum([xij[i,j] for j in jobs])==1,f'constraint_people_{i}'
    
## constraints for jobs
for j in jobs:
    model += lp.lpSum([xij[i,j] for i in people])==1,f'constraint_jobs_{j}'

model.solve()

1

result = swim.copy()
for i in people:
    for j in jobs:
        result.loc[i,j]=lp.value(xij[i,j])

result

	泳姿1	泳姿2	泳姿3	泳姿4
A	0	0	1	0
B	0	1	0	0
C	1	0	0	0
D	0	0	0	1

lp.value(model.objective)

249.0