在 Python 中使用线性规划进行调节优化

在 Python 中使用线性规划进行调节优化

调优是许多行业的挑战。从在生产线上分配工作到安排医院手术病例的时间表,如何有效管理有限资源的问题频出。

虽然“粗略”规划也可以帮我们推进,但有时更高级的规范分析工具(例如线性规划)可以帮助决策者快速确定最佳选择。

该技术是不是新的- mathematical programming已经存在了几十年,但近年来它已变得更加方便。线性求解器算法性能的改进使得可以在合理的时间范围内解决更复杂的问题;Pyomo 等开源库使使用熟悉的编码语言构建模型成为可能,而数字化提高了高质量数据的可用性。

然而,尽管取得了这些进步,数据分析师经常忽视传统的优化方法。

在这篇文章中,希望展示线性编程的价值,并展示如何开始使用 Python 构建模型。为此,我们将以医院调优为例构建一个基本模型来优化医院的手术室调优。

调优对于手术室部门的顺利运行至关重要。有效的日程安排使各方收益:医务人员、医疗保健提供者,尤其是患者。手术计划安排仍然是医院面临的主要挑战。最近由 NHS Improvement 进行的一项研究报告称,通过改进手术清单和假期预订的管理,每年可以完成额外的 290,000 次手术 。

经常会有一些突发流行病或是事故造成大量的资源需求,因此对手术室时间表的有效管理比平时更加​​相关。这是一项复杂的挑战,解决方案不仅仅在于分析。

这里只以外科医生择期手术计划的简化示例。我们的目标是突出分析手术室规划的潜力——该模型并非旨在成为现实中的决策支持工具。

假设医院手术部门正在为一名眼科医生计划择期手术。医院有两个名单:

  • 指派给医生在截止日期前执行的操作清单
  • 分配给医生的手术室时间段清单

手术室可以是半天(8.30am-1pm)或全天(8.30am-6pm),医生通常每周分配一次手术议程,任务是将医生即将到来的手术进行手术室的分配,以便最大限度地利用每个手术室利用率定义为手术病例占手术室时间段的百分比。

手术必须在其目标截止日期之前完成,并且至少有 15% 的手术室时间段应用于其他活动(例如消毒、工作人员休息等)。

公式化——从业务问题到数学模型

我们将问题表述为灵活的作业车间调优问题,其中手术病例类似于工作,手术室类似于机器。我们首先定义决策变量、线性约束和线性目标函数。

1. 导入数据

在我们开始之前,让我们看看数据。我们有两个数据源:case .csv和sessions.csv。

cases.csv包含所有即将进行的择期手术的列表:

sessions.csv包含所有即将到来的手术室的列表

Github 存储库上提供了完整的 CSV 文件。

我们首先使用 Sets(类似于数组)和 Params(键值对)将相关数据导入 Pyomo ConcreteModel 对象。

我们使用许多辅助函数来初始化 Pyomo Sets 和 Params。为简洁起见,此处省略了这些内容,但可以在 Github 存储库中找到。

我们还定义了一个名为 TASKS 的 Set,其中包含 (CaseID, SessionID) 的所有可能组合的列表。这代表了所有可用的潜在案例分配决策:

 [(1, 1001), (1, 1002), (1, 1003), (1, 1004), (2, 1001), (2, 1002), (2, 1003), (2, 1004), (3, 1001), (3, 1002), (3, 1003), (3, 1004), (4, 1001), (4, 1002), (4, 1003), (4, 1004), (5, 1001), (5, 1002), (5, 1003), (5, 1004), (6, 1001), (6, 1002), (6, 1003), (6, 1004), (7, 1001), (7, 1002), (7, 1003), (7, 1004), (8, 1001), (8, 1002), (8, 1003), (8, 1004), (9, 1001), (9, 1002), (9, 1003), (9, 1004), (10, 1001), (10, 1002), (10, 1003), (10, 1004), (11, 1001), (11, 1002), (11, 1003), (11, 1004), (12, 1001), (12, 1002), (12, 1003), (12, 1004), (13, 1001), (13, 1002), (13, 1003), (13, 1004), (14, 1001), (14, 1002), (14, 1003), (14, 1004), (15, 1001), (15, 1002), (15, 1003), (15, 1004), (16, 1001), (16, 1002), (16, 1003), (16, 1004), (17, 1001), (17, 1002), (17, 1003), (17, 1004), (18, 1001), (18, 1002), (18, 1003), (18, 1004), (19, 1001), (19, 1002), (19, 1003), (19, 1004), (20, 1001), (20, 1002), (20, 1003), (20, 1004), (21, 1001), (21, 1002), (21, 1003), (21, 1004), (22, 1001), (22, 1002), (22, 1003), (22, 1004), (23, 1001), (23, 1002), (23, 1003), (23, 1004), (24, 1001), (24, 1002), (24, 1003), (24, 1004), (25, 1001), (25, 1002), (25, 1003), (25, 1004), (26, 1001), (26, 1002), (26, 1003), (26, 1004), (27, 1001), (27, 1002), (27, 1003), (27, 1004), (28, 1001), (28, 1002), (28, 1003), (28, 1004), (29, 1001), (29, 1002), (29, 1003), (29, 1004), (30, 1001), (30, 1002), (30, 1003), (30, 1004)]

We generate all possible combinations of cases and sessions and store them in the TASKS Set.

2. 决策变量

主要决定给手术分配手术室。这需要对上述任务集中的每个手术和手术室组合做二进制的yes/no决定。

我们还想计算每个手术的开始时间和每个手术室的利用率。总而言之,我们有 3 个决策变量:

我们在 Pyomo 模型中定义这些决策变量如下:

3. 目标函数

线性规划的一个优点是可以灵活地定义代表我们业务需求的目标函数。我们可以自由定义任何(线性)函数,在我们的例子中,我们的目标是最大限度地利用所有手术室:

4. 约束

接下来,我们添加我们的约束。约束捕获所有规则(在这个例子中不太现实!)确保模型返回的解决方案构成一个可行的手术室时间表。这里我们有6条规则:

  1. 手术室的开始时间必须晚于分配给它的手术开始时间
  2. 手术必须在其分配的手术室结束之前结束
  3. 一台手术最多只能分配一个手术室
  4. 不能在截止日期之后将手术分配手术室
  5. 一个手术室 不能有两台手术不能重叠:一个手术的开始时间必须在另一个手术的结束时间之后
  6. 手术室的利用率等于手术病例占用的手术室持续时间的分数

我们还限制了决策变量的界限。利用率必须介于 0 和 85% 之间(因为必须保持 15% 的手术室空闲用于其他活动)并且手术的开始时间必须介于 0 和一天中的分钟数 (1440) 之间。

4.1 向模型添加约束

通过为每个约束编写单独的 Python 函数并使用 Pyomo 的Constraint方法,将上述约束添加到模型中:

Model constraint — the non-linear disjunction is added using Pyomo’s GDP extension.

为了将这些约束定义为线性方程,我们使用了两个值得注意的有用技术:Big M 公式和逻辑析取。

Big M Formulation

是打开和关闭约束的技巧。例如,上面的约束 1 规定手术必须在手术室开始时间之后开始。这仅对分配了手术的手术室有效。它不应该适用于所有其他手术室。我们确保在不等式中发生这种情况:

其中M是一个足够大的常数,session_assigned是一个二进制变量。盯着这个足够长的时间后,它开始变得有意义。如果session_assigned等于 1,则必须保持该规则。但是,如果session_assigned为 0,则(假设 M 足够大)RHS 上的第二项变得比第一项大得多,因此整个 RHS 始终为负。由于我们的变量边界强制case_start_time ≥ 0,因此实际上没有额外的限制。

析取

约束编号 5 是逻辑分离:一组通过 OR 关系链接的约束。析取声明对于同一手术中中的任何一台手术,手术 1 发生在手术 2 之前,或者手术 2 发生在手术 1 之前。

这种关系是非线性的,因此我们必须将其转换为线性约束才能使用标准线性求解器。为此,我们使用了 Pyomo 的广义析取编程 (GDP) 建模扩展(参见上面代码片段中的第 27 行)。它允许我们将析取定义为一个简单的 Python 函数,而将“析取”模型转换回标准混合交互编程 (MIP) 模型所需要做的就是包含以下行:

pe.TransformationFactory("gdp.bigm").apply_to(model)

可以通过添加大 M 约束并向模型引入新的二元变量来避免 GDP 扩展,但我们将保持分离,因为它有效且可读。

最后,我们完成了!完整的线性规划模型是:

A flexible job-shop scheduling model for elective surgery planning.

求解模型——生成手术室时间表

使用 Pyomo 之类的接口的一个优点是可以轻松尝试不同的线性求解器,而无需用另一种编码语言重写模型。

在这里,我们使用 Coin-or Branch and Cut (CBC)——一种开源混合整数程序求解器。

下面的代码片段使用 Pyomo 的 SolverFactory 类求解模型。该类可以采用许多调整参数来控制所选求解器的操作,但为简单起见,我们保留默认设置,但时间限制为 60 秒。

下面是一个甘特图,用于可视化模型返回的解决方案。输入手术和手术室数据可在此处获得:

模型结果:手术病例(编号 1-30)被分配到四个手术室。每个手术室至少有 15% 的时间可以免费用于其他活动。

上面的图表显示了一个可行的手术和手术室时间表,可以最大限度地利用受我们限制的所有手术室。提供给模型的输入数据的需求(手术时间)多于容量(手术室时间),并且模型持续时间为 70 分钟的玻璃体切除术是最大化所有手术室总利用率的最佳选择。

线性规划是帮助组织快速做出明智决策的强大工具。这对数据分析师来说是一项有用的技能,并且使用 Pyomo 等开源库可以轻松地在 Python 中构建模型。

在这篇文章中,我们创建了一个简单的优化模型来有效地安排手术案例。尽管不是现实世界的解决方案,但它展示了线性规划等优化方法如何支持规划人员充分利用其可用资源。

此模型可能的后续步骤是:

  • 调整求解器参数以提高性能并减少求解时间
  • 重新构建模型以简化问题并减少求解时间
  • 调整目标函数以更好地表示性能目标
  • 加入额外的约束以更好地代表现实中的手术室安排
  • 使用更复杂的方法来预测手术时间

在最后一个要点上,线性规划等规范性分析技术越来越多地与机器学习等预测方法相结合。对于这里介绍的调优应用程序,机器学习可用于预测任务的持续时间,甚至可以预测将要发生的任务。一旦预测了需求,优化方法就可以帮助进行规划。

作者:Lewis Woolfson

免责声明:凡未注明来源或者来源为网络的信息均转自其它平台,是出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。网站只负责对文章进行整理、排版、编辑,不承担任何法律责任。若有侵权或异议请联系我们删除,谢谢。

发表评论

您的电子邮箱地址不会被公开。