作者都是各自领域经过审查的专家,并撰写他们有经验的主题. 我们所有的内容都经过同行评审,并由同一领域的Toptal专家验证.
Sean是一个充满激情的通晓多种语言的人:一个全栈向导、系统管理员和数据科学家. 他还开发了市场情报软件.
PREVIOUSLY AT
Operations research, 使用计算机做出最佳决策的科学, 已被使用和应用在许多领域的软件. 举几个例子, 物流公司用它来确定从A点到B点的最佳路线, 电力公司用它来确定电力生产计划, 制造公司用它来为他们的工厂找到最佳的人员配置模式.
今天,我们将通过一个假设的问题来探索运筹学的力量. Specifically, 我们将使用混合整数规划(MIP)来确定一个假想工厂的最佳人员配置模式.
在我们深入讨论示例问题之前, 复习一下运筹学中的一些基本概念,了解一下我们今天要用到的一些工具,是很有帮助的.
Linear programming 是否使用运筹学技术来确定数学模型中的最佳结果,其中目标和约束表示为线性方程系统. 线性规划模型的示例可能如下所示:
最大化a + b(目标)
Subject to:
a <= 2 (constraint 1)
b <= 3 (constraint 2)
在我们非常简单的例子中,我们可以看到最优结果是5,a = 2, b = 3. 虽然这是一个相当简单的例子, 您可能可以想象一个利用数千个变量和数百个约束的线性规划模型.
投资组合问题就是一个很好的例子, 你可能会得到如下所示的结果, in pseudo-code:
Maximize
Subject to:
Etc.
...
哪一个比较复杂,很难手工或试错解决. 运筹学软件将使用几种算法来快速解决这些问题. 如果您对底层算法感兴趣,我建议您学习单纯形法 here 内点法 here.
整数规划类似于线性规划,只是允许部分或全部变量为整数值. 虽然乍一看,这似乎不是一个很大的进步, 它使我们能够解决许多单独使用线性规划无法解决的问题.
其中一个问题就是背包问题, 给我们一组物品,这些物品的价值和重量都是给定的,并要求我们找到能装进背包的物品的最高价值组合. 线性规划模型将无法解决这个问题,因为没有办法表达你可以将物品放入背包或不放入背包的想法, 但是你不能把一个项目的一部分放进你的背包——每个变量都是连续的变量!
一个示例背包问题可能有以下参数:
Object | 价值(以10元为单位) | 尺寸(通用单位) |
---|---|---|
Camera | 5 | 2 |
神秘的小雕像 | 7 | 4 |
一大瓶苹果酒 | 2 | 7 |
French horn | 10 | 10 |
MIP模型是这样的:
最大化5a + 7b + 2c + 10d(目标:最大化物品价值)
Subject to:
2a + 4b + 7c + 10d <= 15 (space constraint)
在这种情况下,最优解是a=0, b=1, c=0, d=1,总项目的值为17.
我们今天要解决的问题也需要整数编程,因为工厂的员工可以安排轮班,也可以不安排轮班——为了简单起见, 在这家工厂,你不能安排一个员工上2/3的班.
为了使整数规划成为可能,使用了几种数学算法. 如果你对底层算法感兴趣, 我建议研究切割平面算法和分支定界算法 here.
今天,我们将探讨一个工厂的人员配备问题. 作为工厂的管理者, 我们希望把劳动力成本降到最低, 但我们希望确保每一个班次都有足够的覆盖范围,以满足生产需求.
假设我们有五个班次,人员需求如下:
Shift 1 | Shift 2 | Shift 3 | Shift 4 | Shift 5 |
---|---|---|---|---|
1 person | 4 people | 3 people | 5 people | 2 people |
并且,假设我们有以下工人:
Name | Availability | Cost per Shift ($) |
---|---|---|
Melisandre | 1, 2, 5 | 20 |
Bran | 2, 3, 4, 5 | 15 |
Cersei | 3, 4 | 35 |
Daenerys | 4, 5 | 35 |
Theon | 2, 4, 5 | 10 |
Jon | 1, 3, 5 | 25 |
Tyrion | 2, 4, 5 | 30 |
Jaime | 2, 3, 5 | 20 |
Arya | 1, 2, 4 | 20 |
为了使问题简单化, 让我们暂时假设可用性和成本是唯一的关注点.
对于今天的问题,我们将使用一个名为CBC的开源分支和切割软件. 我们将使用PuLP与这个软件进行交互, 这是一个流行的Python运筹学建模库. 你可以找到关于它的信息 here.
PuLP允许我们以非常Python的方式构建MIP模型,并与现有的Python代码很好地集成. 这是非常有用的,因为一些最流行的数据操作和分析工具是用Python编写的, 大多数商业运筹学系统需要在优化前后进行大量的数据处理.
展示PuLP的简洁和优雅, 这是之前的背包问题,并在PuLP中解决了:
import pulp as pl
#声明一些变量
#每个变量是一个二进制变量,要么是0,要么是1
# 1意味着物品将被放入背包
a = pl.LpVariable("a", 0,1, pl.LpInteger)
b = pl.LpVariable("b", 0,1, pl.LpInteger)
c = pl.LpVariable("c", 0,1, pl.LpInteger)
d = pl.LpVariable("d", 0,1, pl.LpInteger)
#定义问题
prob = pl.pl LpProblem(“背包”.LpMaximize)
#目标函数-最大化背包中物体的价值
b += 5 * a + 7 * b + 2 * c + 10 * d
# constraint -对象的权重不能超过15
prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15
status = prob.Solve () # Solve使用默认解算器,即CBC
print(pl.LpStatus[status]) #打印人类可读的状态
# print the values
print("a", pl.value(a))
print("b", pl.value(b))
print("c", pl.value(c))
print("d", pl.value(d))
运行这个,你应该得到输出:
Optimal
a 0.0
b 1.0
c 0.0
d 1.0
现在来看我们的调度问题!
我们的解决方案的编码相当简单. 首先,我们要定义我们的数据:
import pulp as pl
作为cl导入集合
# data
Shift_requirements = [1,4,3,5,2]
workers = {
"Melisandre": {
“可用性”:[0,1,4],
"cost": 20
},
"Bran": {
“可用性”:[1,2,3,4],
"cost": 15
},
"Cersei": {
“可用性”:[2,3],
"cost": 35
},
"Daenerys": {
“可用性”:[3,4],
"cost": 35
},
"Theon": {
“可用性”:[1,3,4],
"cost": 10
},
"Jon": {
“可用性”:[0,2,4],
"cost": 25
},
"Tyrion": {
“可用性”:[1,3,4],
"cost": 30
},
"Jaime": {
“可用性”:[1,2,4],
"cost": 20
},
"Arya": {
“可用性”:[0,1,3],
"cost": 20
}
}
接下来,我们要定义模型:
定义模型:我们想把成本降到最低
prob = pl.pl LpProblem(“调度”.LpMinimize)
#一些模型变量
cost = []
vars_by_shift = cl.defaultdict(list)
对于worker,在workers中输入信息.items():
对于info['availability']中的移位:
worker_var = pl.LpVariable(“%s_%s”% (worker, shift), 0, 1, pl.LpInteger)
vars_by_shift(转变).append(worker_var)
cost.附加(worker_var * info['cost'])
将目标设定为成本的总和
prob += sum(cost)
#设置班次要求
对于shift, enumerate(shift_requirements)中的需求:
prob += sum(vars_by_shift(转变)) >= requirement
现在我们只需让它求解并打印结果!
status = prob.solve()
print("Result:", pl.LpStatus[status])
results = []
对于移位,vars_by_shift中的vars.items():
results.append({
"shift": shift,
"workers": [var.在vars中为var命名.varValue == 1],
})
对于sorted(results, key=lambda x: x['shift'])中的结果:
print("Shift:", result[' Shift '], 'workers:', ', ').加入(结果(“工人”)))
运行代码后,您应该看到以下输出:
Result: Optimal
轮班:0工人:Arya_0
轮班:1名工人:Melisandre_1, Bran_1, Theon_1, Arya_1
轮班:2名工人:Bran_2, Jon_2, Jaime_2
轮班:3名工人:Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3
轮班:4名工人:Bran_4, Theon_4
尽管之前的模型很有趣也很有用, 它没有充分展示混合整数规划的强大功能. 我们也可以很容易地写出a for
循环查找最便宜的 x
工人为每一班,在哪里 x
一个班次需要多少工人. 演示如何使用MIP来解决难以以命令式方式解决的问题, 让我们检查一下如果添加一些额外的约束会发生什么.
假设,由于新的劳动法规,工人不能被分配超过2个班次. 来解释增加的工作量, 我们已经招募了多斯拉克人力资源团队, 谁愿意每班提供最多10名多斯拉克工人,每班工资40美元.
另外假设, 因为工厂外的一些人际冲突, 瑟曦和詹姆不能和丹妮莉丝或琼恩一起轮班. 此外,詹姆和瑟曦不能一起轮班. Finally, Arya, 谁的人际关系特别复杂, 不能和詹姆同一班吗, Cersei, or Melisandre.
这两种新的约束条件和资源的加入,绝不意味着不能通过强制手段解决问题, 但这使得解决方案更加困难, 因为人们将不得不考虑安排工人轮班的机会成本.
但是,使用混合整数编程就容易多了. 我们只需要像这样修改代码:
定义禁令列表和一些约束:
ban_list = {
(“Daenerys”、“Jaime”),
(“Daenerys”、“瑟曦”),
("Jon", "Jaime"),
("Jon", "Cersei"),
("Arya", "Jaime"),
(“Arya”、“瑟曦”),
(“Arya”、“梅莉珊卓”),
(“Jaime”,“瑟曦”)
}
DOTHRAKI_MAX = 10
DOTHRAKI_COST = 45
填充变量来实现禁令和最大位移约束:
对于worker,在workers中输入信息.items():
对于info['availability']中的移位:
worker_var = pl.LpVariable(“%s_%d”% (worker, shift), 0, 1, pl.LpInteger)
#存储一些可变数据,以便我们可以实现禁令约束
Var_data = (worker,)
vars_by_shift(转变).追加((worker_var var_data))
#按变量存储变量,这样我们就可以实现最大移位约束
vars_by_worker(工人).append(worker_var)
cost.附加(worker_var * info['cost'])
添加多斯拉克变量:
对于range(len(shift_requirements))中的移位:
dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger)
cost.追加(dothraki_var * DOTHRAKI_COST)
Dothrakis_by_shift [shift] = dothrak_var
我们还需要一个稍微修改的循环来计算移位和禁止要求:
#设置班次要求
对于shift, enumerate(shift_requirements)中的需求:
prob += sum([var[0] for var in vars_by_shift(转变)]) + dothrakis_by_shift[shift] >= requirement
设置禁令要求
对于移位,vars_by_shift中的vars.items():
for var1 in vars:
for var2 in vars:
Worker_pair = var1[1][0], var2[1][0]
如果worker_pair in ban_list:
prob += var1[0] + var2[0] <= 1
#制定劳动标准:
对于worker, vars_by_worker中的vars.items():
prob += sum(vars) <= 2
最后,打印结果:
status = prob.solve()
print("Result:", pl.LpStatus[status])
results = []
对于移位,vars_by_shift中的vars.items():
results.append({
"shift": shift,
"workers": [var[1][0] for var in vars if var[0].varValue == 1],
“多斯拉克人”:dothrakis_by_shift(转变).varValue
})
对于sorted(results, key=lambda x: x['shift'])中的结果:
print("Shift:", result[' Shift '], 'workers:', ', ').Join (result['workers']), 'dothrakis hired:', int(result['dothrakis']))
我们应该可以出发了. 运行代码,您应该看到如下输出:
Result: Optimal
轮班:0工人:Arya dothrakis雇用:0
轮班:1名工人:梅丽珊卓,席恩,提利昂,詹姆·多斯拉基斯雇佣:0人
轮班:2名工人:布兰,琼恩多斯拉基斯雇用:1
轮班:3名工人:布兰,丹妮莉丝,席恩,提利昂,艾莉亚多斯拉基斯雇用:0
轮班:4名工人:梅丽珊卓,詹姆·多斯拉基斯雇用:0
这就是结果, 一个尊重被禁止的工人名单的结果, 遵守劳动法规, 并且明智地使用多斯拉克工人.
今天,我们将探讨如何使用混合整数规划来做出更好的决策. 我们讨论了运筹学中使用的底层算法和技术,并研究了一个代表混合整数规划在现实世界中如何使用的示例问题.
我希望本文能启发您更多地了解运筹学,并使您思考如何将这项技术应用到您的项目中. 当涉及到令人兴奋的优化算法和运筹学世界时,我们只看到了冰山一角.
您可以找到与本文相关的所有代码 on GitHub. 如果你想讨论更多,请在下面分享你的评论!
线性规划是一种运筹学技术,用于确定数学模型中的最佳结果,其中目标和约束表示为线性方程系统.
整数规划类似于线性规划,只是允许部分或全部变量为整数值.
纽约,纽约,美国
2016年12月16日成为会员
Sean是一个充满激情的通晓多种语言的人:一个全栈向导、系统管理员和数据科学家. 他还开发了市场情报软件.
PREVIOUSLY AT
世界级的文章,每周发一次.
世界级的文章,每周发一次.
Join the Toptal® community.