LP建模问题：汉堡店雇佣员工

This article is categorized as "Garbage" . It should NEVER be appeared in your search engine's results.

2024-12-25

本笔记写于2024-12-25，目的仅仅是为了回忆去年做过的一道题，而不是探索这类问题（实际上的这类问题要复杂很多，我只是遇到了一个简化版本）。原题找不到了，用claude帮我回忆了一下，觉得大概是这个样子，数字都没有经过验证的，所以下面的题就不要想着用求解器去求解了。

注意：实际上下面的问题应该是integer programming范畴的问题，而且要求应该更复杂，但这里仅仅讨论建模思路

Claude给我的题：

Consider a Burger King store that needs to schedule workers for a week. The store is open 7 days a week, and they need at least 10 workers each day to operate effectively. This constant staffing requirement makes the problem cleaner while preserving its mathematical essence.

The store employs two types of workers:

Full-time workers:

• Must work exactly 5 consecutive days per week
• Cost $150 per day
• Can start their work sequence on any day of the week

Part-time workers:

• Must work exactly 3 consecutive days per week
• Cost $175 per day
• Can start their work sequence on any day of the week

Object: minimize total costs to hire workers

这道题的关键在于建立变量的思路，或者说如何正确理解 consecutive . 正确思路应该是：

变量[mathjax]f_i[/mathjax]: Number of full-time workers starting from [mathjax]i-th[/mathjax] day of a week. [mathjax]i=1, 2, 3, 4, 5, 6, 7[/mathjax]

变量[mathjax]p_i[/mathjax]: Number of part-time workers starting from [mathjax]i-th[/mathjax] day of a week. [mathjax]i=1, 2, 3, 4, 5, 6, 7[/mathjax]

所以如果要想知道周一（1）有多少员工，应该是[mathjax]f_4+f_5+f_6+f_7+f_1+p_6+p_7+p_1[/mathjax].

周二到周日同理

答案：

实际上这道题还应该加上额外限制：

1. 每一天的最低员工要求都是不一样的，比如周一到周五要求应该低一些，周末要求应该高一些
2. 员工数必须是整数（超出本篇范畴）

2025-07-24

在整理老笔记的时候突然发现了一道看似差不多实际上还是有些区别的汉堡店员工题（应该是早就写了笔记，但后来很快就忘了）

出自2023-10-16的笔记，还是先把链接和题目放上来：

🔗 [Formulations of linear and non-linear programs] https://ocw.mit.edu/courses/15-053-optimization-methods-in-management-science-spring-2013/d244065e2dce13f23254035a14586d6c_MIT15_053S13_lec2.pdf

答案：

这道题用相似的变量定义就可以，区别在于这道题的目标函数是“total number of workers”而不是员工工资开销

实际上总员工数量就是[mathjax]x_1+x_2+x_3+x_4+x_5+x_6+x_7[/mathjax]，关键在于理解[mathjax]x_i[/mathjax]代表的含义是“仅从周x开始工作的员工”。虽然周一和周二的实际上班员工会共享一部分，但[mathjax]x_1[/mathjax]和[mathjax]x_2[/mathjax]之间没有共享任何员工！周一开始工作的员工那就是独立的一批，和“周二开始工作的员工”就没有任何重叠的部分。

顺便，上面这道题有整数解。附上LP（使用pulp）和IP（使用gurobi）的代码：

LP：

from pulp import *

prob = LpProblem("burger", LpMinimize)

x1 = LpVariable("x1")
x2 = LpVariable("x2")
x3 = LpVariable("x3")
x4 = LpVariable("x4")
x5 = LpVariable("x5")
x6 = LpVariable("x6")
x7 = LpVariable("x7")

prob += x1 + x2 + x3 + x4 + x5 + x6 + x7

prob += x4 + x5 + x6 + x7 + x1 >= 17
prob += x5 + x6 + x7 + x1 + x2 >= 13
prob += x6 + x7 + x1 + x2 + x3 >= 15
prob += x7 + x1 + x2 + x3 + x4 >= 19
prob += x1 + x2 + x3 + x4 + x5 >= 14
prob += x2 + x3 + x4 + x5 + x6 >= 16
prob += x3 + x4 + x5 + x6 + x7 >= 11

prob += x1 >= 0
prob += x2 >= 0
prob += x3 >= 0
prob += x4 >= 0
prob += x5 >= 0
prob += x6 >= 0
prob += x7 >= 0

prob.solve()

print("Status:", LpStatus[prob.status])
if prob.status == 1:
    for v in prob.variables():
        print(v.name, "=", v.varValue)
    print('minimize result: ' + str(value(prob.objective)))

得到：

Status: Optimal
x1 = 1.3333333
x2 = 5.3333333
x3 = 0.0
x4 = 7.3333333
x5 = 0.0
x6 = 3.3333333
x7 = 5.0
minimize result: 22.3333332

IP的代码是gpt给我转换的，懒得写了：

from gurobipy import Model, GRB

model = Model("burger")

x = {}
for i in range(1, 8):
    x[i] = model.addVar(lb=0, name=f"x{i}", vtype=GRB.INTEGER)

model.setObjective(x[1] + x[2] + x[3] + x[4] + x[5] + x[6] + x[7], GRB.MINIMIZE)

model.addConstr(x[4] + x[5] + x[6] + x[7] + x[1] >= 17)
model.addConstr(x[5] + x[6] + x[7] + x[1] + x[2] >= 13)
model.addConstr(x[6] + x[7] + x[1] + x[2] + x[3] >= 15)
model.addConstr(x[7] + x[1] + x[2] + x[3] + x[4] >= 19)
model.addConstr(x[1] + x[2] + x[3] + x[4] + x[5] >= 14)
model.addConstr(x[2] + x[3] + x[4] + x[5] + x[6] >= 16)
model.addConstr(x[3] + x[4] + x[5] + x[6] + x[7] >= 11)

model.optimize()

if model.status == GRB.OPTIMAL:
    print("Status: Optimal")
    for i in range(1, 8):
        print(f"x{i} = {x[i].X}")
    print("Minimize result:", model.ObjVal)
else:
    print(f"Status: {model.status}")

得到：

Status: Optimal
x1 = 7.0
x2 = 5.0
x3 = 1.0
x4 = 7.0
x5 = -0.0
x6 = 3.0
x7 = -0.0
Minimize result: 23.0