运筹学, 使用计算机做出最佳决策的科学, 已被使用和应用在许多领域的软件. 举几个例子, 物流公司用它来确定从A点到B点的最佳路线, 电力公司用它来确定电力生产计划, 制造公司用它来为他们的工厂找到最佳的人员配置模式.

今天，我们将通过一个假设的问题来探索运筹学的力量. 具体地说, 我们将使用混合整数规划(MIP)来确定一个假想工厂的最佳人员配置模式.

运筹学算法

在我们深入讨论示例问题之前, 复习一下运筹学中的一些基本概念，了解一下我们今天要用到的一些工具，是很有帮助的.

线性规划算法

线性规划 是否使用运筹学技术来确定数学模型中的最佳结果，其中目标和约束表示为线性方程系统. 线性规划模型的示例可能如下所示:

最大化a + b(目标)
主题:
a <= 2 (constraint 1)
b <= 3 (constraint 2)

在我们非常简单的例子中，我们可以看到最优结果是5,a = 2, b = 3. 虽然这是一个相当简单的例子, 您可能可以想象一个利用数千个变量和数百个约束的线性规划模型.

投资组合问题就是一个很好的例子, 你可能会得到如下所示的结果, 在伪代码:

Maximize 

主题:


等.
...

哪一个比较复杂，很难手工或试错解决. 运筹学软件将使用几种算法来快速解决这些问题. 如果您对底层算法感兴趣，我建议您学习单纯形法 在这里 内点法 在这里.

整数规划算法

整数规划类似于线性规划，只是允许部分或全部变量为整数值. 虽然乍一看，这似乎不是一个很大的进步, 它使我们能够解决许多单独使用线性规划无法解决的问题.

其中一个问题就是背包问题, 给我们一组物品，这些物品的价值和重量都是给定的，并要求我们找到能装进背包的物品的最高价值组合. 线性规划模型将无法解决这个问题，因为没有办法表达你可以将物品放入背包或不放入背包的想法, 但是你不能把一个项目的一部分放进你的背包——每个变量都是连续的变量!

一个示例背包问题可能有以下参数:

MIP模型是这样的:

最大化5a + 7b + 2c + 10d(目标:最大化物品价值)
主题:
    2a + 4b + 7c + 10d <= 15 (space constraint)

在这种情况下，最优解是a=0, b=1, c=0, d=1，总项目的值为17.

我们今天要解决的问题也需要整数编程，因为工厂的员工可以安排轮班，也可以不安排轮班——为了简单起见, 在这家工厂，你不能安排一个员工上2/3的班.

为了使整数规划成为可能，使用了几种数学算法. 如果你对底层算法感兴趣, 我建议研究切割平面算法和分支定界算法 在这里.

示例问题:调度

问题描述

今天，我们将探讨一个工厂的人员配备问题. 作为工厂的管理者, 我们希望把劳动力成本降到最低, 但我们希望确保每一个班次都有足够的覆盖范围，以满足生产需求.

假设我们有五个班次，人员需求如下:

并且，假设我们有以下工人:

为了使问题简单化, 让我们暂时假设可用性和成本是唯一的关注点.

我们的工具

对于今天的问题，我们将使用一个名为CBC的开源分支和切割软件. 我们将使用PuLP与这个软件进行交互, 这是一个流行的Python运筹学建模库. 你可以找到关于它的信息 在这里.

PuLP允许我们以非常Python的方式构建MIP模型，并与现有的Python代码很好地集成. 这是非常有用的，因为一些最流行的数据操作和分析工具是用Python编写的, 大多数商业运筹学系统需要在优化前后进行大量的数据处理.

展示PuLP的简洁和优雅, 这是之前的背包问题，并在PuLP中解决了:

进口纸浆

#声明一些变量
#每个变量是一个二进制变量，要么是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

状态=问题.Solve () # Solve使用默认解算器，即CBC
print (pl.LpStatus[状态]) #打印人类可读的状态

#打印值
打印(“a”,pl.值(a))
打印(“b”,pl.值(b))
打印(“c”,pl.值(c))
打印(“d”,pl.值(d))

运行这个，你应该得到输出:

最优
a 0.0
b 1.0
c 0.0
d 1.0

现在来看我们的调度问题!

编写我们的解决方案

我们的解决方案的编码相当简单. 首先，我们要定义我们的数据:

进口纸浆
作为cl导入集合

#数据
Shift_requirements = [1,4,3,5,2]
工人= {
    "梅莉珊卓":{
        “可用性”:[0,1,4]，
        “成本”:20
    },
    “糠”:{
        “可用性”:[1,2,3,4]，
        “成本”:15
    },
    ”瑟曦":{
        “可用性”:[2,3]，
        “成本”:35
    },
    " Daenerys ": {
        “可用性”:[3,4]，
        “成本”:35
    },
    "全心全意地":{
        “可用性”:[1,3,4]，
        “成本”:10
    },
    “乔”:{
        “可用性”:[0,2,4]，
        “成本”:25
    },
    “泰瑞欧”:{
        “可用性”:[1,3,4]，
        “成本”:30
    },
    “杰米”:{
        “可用性”:[1,2,4]，
        “成本”:20
    },
    " Arya ": {
        “可用性”:[0,1,3]，
        “成本”:20
    }
}

接下来，我们要定义模型:

定义模型:我们想把成本降到最低
ProB = pl.pl LpProblem(“调度”.LpMinimize)

#一些模型变量
成本= []
Vars_by_shift = cl.defaultdict(列表)

对于worker，在workers中输入信息.项目():
    对于info['availability']中的移位:
        Worker_var = pl.LpVariable(“%s_%s”% (worker, shift)， 0, 1, pl.LpInteger)
        vars_by_shift(转变).追加(worker_var)
        成本.附加(worker_var * info['成本'])

将目标设定为成本的总和
probb += sum(成本)

#设置班次要求
对于shift, enumerate(shift_requirements)中的需求:
    prob += sum(vars_by_shift(转变)) >= requirement

现在我们只需让它求解并打印结果!

状态=问题.解决()
打印(“结果:pl.LpStatus[状态])
结果= []
对于移位，vars_by_shift中的vars.项目():
    结果.追加({
        “转变”:转变,
        “工人”:[var.在vars中为var命名.varValue == 1]，
    })

对于sorted(结果, key=lambda x: x['shift'])中的结果:
    print("Shift:"， result[' Shift ']， 'workers:'， '， ').加入(结果(“工人”)))

运行代码后，您应该看到以下输出:

结果:最优
轮班:0工人:Arya_0
轮班:1名工人:梅莉珊卓_1, 麸皮_1, 全心全意地_1, Arya_1
轮班:2名工人:麸皮_2, 乔恩_2, Jaime_2
轮班:3名工人:麸皮_3, Daenerys_3, 全心全意地_3, 泰瑞欧_3, Arya_3
轮班:4名工人:麸皮_4, 全心全意地_4

增加难度:额外的限制

尽管之前的模型很有趣也很有用, 它没有充分展示混合整数规划的强大功能. 我们也可以很容易地写出a 为 循环查找最便宜的 x 工人为每一班，在哪里 x 一个班次需要多少工人. 演示如何使用MIP来解决难以以命令式方式解决的问题, 让我们检查一下如果添加一些额外的约束会发生什么.

额外的约束

假设，由于新的劳动法规，工人不能被分配超过2个班次. 来解释增加的工作量, 我们已经招募了多斯拉克人力资源团队, 谁愿意每班提供最多10名多斯拉克工人，每班工资40美元.

另外假设, 因为工厂外的一些人际冲突, 瑟曦和詹姆不能和丹妮莉丝或琼恩一起轮班. 此外，詹姆和瑟曦不能一起轮班. 最后, Arya, 谁的人际关系特别复杂, 不能和詹姆同一班吗, 瑟曦, 或梅莉珊卓.

这两种新的约束条件和资源的加入，绝不意味着不能通过强制手段解决问题, 但这使得解决方案更加困难, 因为人们将不得不考虑安排工人轮班的机会成本.

解决方案

但是，使用混合整数编程就容易多了. 我们只需要像这样修改代码:

定义禁令列表和一些约束:

Ban_list = {
    (“Daenerys”、“Jaime”),
    (“Daenerys”、“瑟曦”),
    (“乔”、“Jaime”),
    (“乔”,”瑟曦”),
    (“Arya”、“Jaime”),
    (“Arya”、“瑟曦”),
    (“Arya”、“梅莉珊卓”),
    (“Jaime”,“瑟曦”)
}

Dothraki_max = 10
多斯拉克成本= 45

填充变量来实现禁令和最大位移约束:

对于worker，在workers中输入信息.项目():
    对于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(工人).追加(worker_var)
        成本.附加(worker_var * info['成本'])

添加多斯拉克变量:

对于range(len(shift_requirements))中的移位:
    Dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger)
    成本.追加(dothraki_var * DOTHRAKI_COST)
    Dothrakis_by_shift [shift] = dothrak_var

我们还需要一个稍微修改的循环来计算移位和禁止要求:

#设置班次要求
对于shift, enumerate(shift_requirements)中的需求:
    prob += sum([var[0] 为 var in vars_by_shift(转变)]) + dothrakis_by_shift[shift] >= requirement

设置禁令要求
对于移位，vars_by_shift中的vars.项目():
    对于vars中的var1:
        对于vars中的var2:
            Worker_pair = var1[1][0]， var2[1][0]
            如果worker_pair in ban_list:
                prob += var1[0] + var2[0] <= 1

#制定劳动标准:
对于worker, vars_by_worker中的vars.项目():
    prob += sum(vars) <= 2

最后，打印结果:

状态=问题.解决()
打印(“结果:pl.LpStatus[状态])
结果= []
对于移位，vars_by_shift中的vars.项目():
    结果.追加({
        “转变”:转变,
        “工人”:[var[1][0] 为 var in vars if var[0].varValue == 1]，
        “多斯拉克人”:dothrakis_by_shift(转变).varValue
    })

对于sorted(结果, key=lambda x: x['shift'])中的结果:
    print("Shift:"， result[' Shift ']， 'workers:'， '， ').Join (result['workers'])， 'dothrakis hired:'， int(result['dothrakis']))

我们应该可以出发了. 运行代码，您应该看到如下输出:

结果:最优
轮班:0工人:Arya dothrakis雇用:0
轮班:1名工人:梅丽珊卓，席恩，提利昂，詹姆·多斯拉基斯雇佣:0人
轮班:2名工人:布兰，琼恩多斯拉基斯雇用:1
轮班:3名工人:布兰，丹妮莉丝，席恩，提利昂，艾莉亚多斯拉基斯雇用:0
轮班:4名工人:梅丽珊卓，詹姆·多斯拉基斯雇用:0

这就是结果, 一个尊重被禁止的工人名单的结果, 遵守劳动法规, 并且明智地使用多斯拉克工人.

结论

今天，我们将探讨如何使用混合整数规划来做出更好的决策. 我们讨论了运筹学中使用的底层算法和技术，并研究了一个代表混合整数规划在现实世界中如何使用的示例问题.

我希望本文能启发您更多地了解运筹学，并使您思考如何将这项技术应用到您的项目中. 当涉及到令人兴奋的优化算法和运筹学世界时，我们只看到了冰山一角.

您可以找到与本文相关的所有代码 GitHub上. 如果你想讨论更多，请在下面分享你的评论!