播出时间选择
Broadcast Schedule Selection
我有 11 支球队的 11 周比赛时间表（每周 5 场比赛）。我需要尝试从该列表中 select 11 场比赛（每周 1 场）为 11 支球队中的每支球队提供一场主场和一场客场比赛的转播。理想情况下，这将是我可以在未来几年重复使用的代码，并且我可以在必要时扩展到更多团队和数周。
我知道为给定的、已创建的时间表找到可行解决方案的可能性极低，而且在许多情况下不存在解决方案。因此，当不存在上述类型的解决方案时，我希望获得接近的时间表。也就是说，所有球队都获得两次广播，但有些球队可能获得两场主场或两场客场比赛，而不是每场比赛一场。
我研究了几种不同的方法。我有许多 5x2（客队，主队）阵列（每周比赛），我尝试 运行 a sort/selection 有条件（比如 a_1 =\= a_j j>1 and a_i in {1..11}) on，但我不知道如何让双重限制 selection 起作用，我也不知道当它没有更多可行的 select 离子时，如何让它回到以前的 select 离子。我尝试过暴力破解，但 4000 万种可能的组合超出了我的处理能力。
我正在使用 MATLab 执行所有工作。我通常可以将 C 或 C++ 翻译成 MATLab 可用代码。
这似乎是一个有趣的问题，所以我想办法将其表述为 IP。
设 J 和 T 为团队和周的集合。
设G为所有游戏的集合； G 的每个元素都是一个元组 (i,j,t)，表示客队 (i)、主队 (j) 和星期 (t) .
设H为所有主场比赛的集合； H 的每个元素都是一个元组 (j,t)，表示主队 (j) 和星期 (t)。
定义以下二元决策变量：
w[j,t] = 1 如果我们在 t 周在 j 播放主场比赛，否则 = 0（为 (j,t) in H 定义）x[j] = 1 如果团队 j 有一个 away-game 广播，= 0 否则（为 J 中的 j 定义）y[j] = 1 如果团队 j 有 home-game 广播，= 0 否则（为 J 中的 j 定义）z[j] = 1 如果团队 j 有 away-game 和 home-game 广播，= 0 否则（为 j 在 J)
则模型为：
maximize sum {j in J} z[j]
subject to sum {j in J} w[j,t] = 1 for all t
x[j] <= sum {(i,t) in H: (j,i,t) in G} w[i,t] for all j
y[j] <= sum {t in T} w[j,t] for all j
z[j] <= (1/2) * (x[j] + y[j]) for all j
w[j,t], x[j], y[j], z[j] in {0,1}
objective 函数计算同时获得主场和客场广播的球队总数。第一个约束说我们每周只需要一次广播。第二个约束说 x[j] 不能等于 1，除非有某个星期 j 的客场比赛被广播。第三个约束对 y[j] 和家庭广播也是如此。第四个约束说 z[j] 不能等于 1，除非 x[j] 和 y[j] 都等于 1。最后一个约束说一切都必须是二进制的。
我使用 11 场比赛的时间表在 Python/PuLP 中对这个模型进行了编码。 （显然，您会加入自己的日程安排。）
from pulp import *
import numpy as np
# Number of teams, weeks, and games per week.
num_teams = 11
num_weeks = 11
num_games_per_week = 5
# Lists of teams and weeks.
teams = range(1, num_teams+1)
weeks = range(1, num_weeks+1)
# List of game tuples: (i, j, t) means team i plays at team j in week t.
games = [(1, 10, 1), (2, 9, 1), (3, 8, 1), (4, 7, 1), (5, 6, 1),
(6, 4, 2), (7, 3, 2), (8, 2, 2), (9, 1, 2), (10, 11, 2),
(2, 11, 3), (3, 10, 3), (4, 9, 3), (5, 8, 3), (6, 7, 3),
(7, 5, 4), (8, 4, 4), (9, 3, 4), (10, 2, 4), (11, 1, 4),
(3, 1, 5), (4, 11, 5), (5, 10, 5), (6, 9, 5), (7, 8, 5),
(8, 6, 6), (9, 5, 6), (10, 4, 6), (11, 3, 6), (1, 2, 6),
(4, 2, 7), (5, 1, 7), (6, 11, 7), (7, 10, 7), (8, 9, 7),
(9, 7, 8), (10, 6, 8), (11, 5, 8), (1, 4, 8), (2, 3, 8),
(5, 3, 9), (6, 2, 9), (7, 1, 9), (8, 11, 9), (9, 10, 9),
(10, 8, 10), (11, 7, 10), (1, 6, 10), (2, 5, 10), (3, 4, 10),
(11, 9, 11), (1, 8, 11), (2, 7, 11), (3, 6, 11), (4, 5, 11)]
# List of home games: (j, t) means there is a home game at j in week t.
home_games = [(j, t) for (i, j, t) in games]
# Initialize problem.
prob = LpProblem('Broadcast', LpMaximize)
# Generate decision variables.
w = LpVariable.dicts('w', home_games, 0, 1, LpInteger)
x = LpVariable.dicts('x', teams, 0, 1, LpInteger)
y = LpVariable.dicts('y', teams, 0, 1, LpInteger)
z = LpVariable.dicts('z', teams, 0, 1, LpInteger)
# Objective function.
prob += lpSum([z[j] for j in teams])
# Constraint: 1 broadcast per week.
for t in weeks:
prob += lpSum([w[j, t] for j in teams if (j, t) in home_games]) == 1
# Constraint: x[j] can only = 1 if we broadcast a game in which j is away team.
for j in teams:
prob += x[j] <= lpSum([w[i, t] for (i, t) in home_games if (j, i, t) in games])
# Constraint: y[j] can only = 1 if we broadcast a game in which j is home team.
for j in teams:
prob += y[j] <= lpSum(([w[j, t] for t in weeks if (j, t) in home_games]))
# Constraint: z[j] can only = 1 if x[j] and y[j] both = 1.
for j in teams:
prob += z[j] <= 0.5 * (x[j] + y[j])
# Solve problem.
prob.solve()
# Print status.
print("Status:", LpStatus[prob.status])
# Print optimal values of decision variables.
for v in prob.variables():
if v.varValue is not None and v.varValue > 0:
print(v.name, "=", v.varValue)
# Prettier print.
print("\nNumber of teams with both home and away broadcasts: {:.0f}".format(np.sum([z[j].value() for j in teams])))
for (i, j, t) in games:
if w[j, t].value() == 1:
print("Week {:2d}: broadcast team {:2d} at team {:2d}".format(t, i, j))
结果是：
Number of teams with both home and away broadcasts: 11
Week 1: broadcast team 1 at team 10
Week 2: broadcast team 10 at team 11
Week 3: broadcast team 5 at team 8
Week 4: broadcast team 8 at team 4
Week 5: broadcast team 6 at team 9
Week 6: broadcast team 11 at team 3
Week 7: broadcast team 4 at team 2
Week 8: broadcast team 9 at team 7
Week 9: broadcast team 7 at team 1
Week 10: broadcast team 2 at team 5
Week 11: broadcast team 3 at team 6
你可以看到每支球队都有主场和客场广播。
我有 11 支球队的 11 周比赛时间表（每周 5 场比赛）。我需要尝试从该列表中 select 11 场比赛（每周 1 场）为 11 支球队中的每支球队提供一场主场和一场客场比赛的转播。理想情况下，这将是我可以在未来几年重复使用的代码，并且我可以在必要时扩展到更多团队和数周。
我知道为给定的、已创建的时间表找到可行解决方案的可能性极低，而且在许多情况下不存在解决方案。因此，当不存在上述类型的解决方案时，我希望获得接近的时间表。也就是说，所有球队都获得两次广播，但有些球队可能获得两场主场或两场客场比赛，而不是每场比赛一场。
我研究了几种不同的方法。我有许多 5x2（客队，主队）阵列（每周比赛），我尝试 运行 a sort/selection 有条件（比如 a_1 =\= a_j j>1 and a_i in {1..11}) on，但我不知道如何让双重限制 selection 起作用，我也不知道当它没有更多可行的 select 离子时，如何让它回到以前的 select 离子。我尝试过暴力破解，但 4000 万种可能的组合超出了我的处理能力。
我正在使用 MATLab 执行所有工作。我通常可以将 C 或 C++ 翻译成 MATLab 可用代码。
这似乎是一个有趣的问题，所以我想办法将其表述为 IP。
设 J 和 T 为团队和周的集合。
设G为所有游戏的集合； G 的每个元素都是一个元组 (i,j,t)，表示客队 (i)、主队 (j) 和星期 (t) .
设H为所有主场比赛的集合； H 的每个元素都是一个元组 (j,t)，表示主队 (j) 和星期 (t)。
定义以下二元决策变量：
w[j,t] = 1如果我们在t周在j播放主场比赛，否则= 0（为(j,t) in H定义）x[j] = 1如果团队j有一个 away-game 广播，= 0否则（为J中的j定义）y[j] = 1如果团队j有 home-game 广播，= 0否则（为J中的j定义）z[j] = 1如果团队j有 away-game 和 home-game 广播，= 0否则（为j在J)
则模型为：
maximize sum {j in J} z[j]
subject to sum {j in J} w[j,t] = 1 for all t
x[j] <= sum {(i,t) in H: (j,i,t) in G} w[i,t] for all j
y[j] <= sum {t in T} w[j,t] for all j
z[j] <= (1/2) * (x[j] + y[j]) for all j
w[j,t], x[j], y[j], z[j] in {0,1}
objective 函数计算同时获得主场和客场广播的球队总数。第一个约束说我们每周只需要一次广播。第二个约束说 x[j] 不能等于 1，除非有某个星期 j 的客场比赛被广播。第三个约束对 y[j] 和家庭广播也是如此。第四个约束说 z[j] 不能等于 1，除非 x[j] 和 y[j] 都等于 1。最后一个约束说一切都必须是二进制的。
我使用 11 场比赛的时间表在 Python/PuLP 中对这个模型进行了编码。 （显然，您会加入自己的日程安排。）
from pulp import *
import numpy as np
# Number of teams, weeks, and games per week.
num_teams = 11
num_weeks = 11
num_games_per_week = 5
# Lists of teams and weeks.
teams = range(1, num_teams+1)
weeks = range(1, num_weeks+1)
# List of game tuples: (i, j, t) means team i plays at team j in week t.
games = [(1, 10, 1), (2, 9, 1), (3, 8, 1), (4, 7, 1), (5, 6, 1),
(6, 4, 2), (7, 3, 2), (8, 2, 2), (9, 1, 2), (10, 11, 2),
(2, 11, 3), (3, 10, 3), (4, 9, 3), (5, 8, 3), (6, 7, 3),
(7, 5, 4), (8, 4, 4), (9, 3, 4), (10, 2, 4), (11, 1, 4),
(3, 1, 5), (4, 11, 5), (5, 10, 5), (6, 9, 5), (7, 8, 5),
(8, 6, 6), (9, 5, 6), (10, 4, 6), (11, 3, 6), (1, 2, 6),
(4, 2, 7), (5, 1, 7), (6, 11, 7), (7, 10, 7), (8, 9, 7),
(9, 7, 8), (10, 6, 8), (11, 5, 8), (1, 4, 8), (2, 3, 8),
(5, 3, 9), (6, 2, 9), (7, 1, 9), (8, 11, 9), (9, 10, 9),
(10, 8, 10), (11, 7, 10), (1, 6, 10), (2, 5, 10), (3, 4, 10),
(11, 9, 11), (1, 8, 11), (2, 7, 11), (3, 6, 11), (4, 5, 11)]
# List of home games: (j, t) means there is a home game at j in week t.
home_games = [(j, t) for (i, j, t) in games]
# Initialize problem.
prob = LpProblem('Broadcast', LpMaximize)
# Generate decision variables.
w = LpVariable.dicts('w', home_games, 0, 1, LpInteger)
x = LpVariable.dicts('x', teams, 0, 1, LpInteger)
y = LpVariable.dicts('y', teams, 0, 1, LpInteger)
z = LpVariable.dicts('z', teams, 0, 1, LpInteger)
# Objective function.
prob += lpSum([z[j] for j in teams])
# Constraint: 1 broadcast per week.
for t in weeks:
prob += lpSum([w[j, t] for j in teams if (j, t) in home_games]) == 1
# Constraint: x[j] can only = 1 if we broadcast a game in which j is away team.
for j in teams:
prob += x[j] <= lpSum([w[i, t] for (i, t) in home_games if (j, i, t) in games])
# Constraint: y[j] can only = 1 if we broadcast a game in which j is home team.
for j in teams:
prob += y[j] <= lpSum(([w[j, t] for t in weeks if (j, t) in home_games]))
# Constraint: z[j] can only = 1 if x[j] and y[j] both = 1.
for j in teams:
prob += z[j] <= 0.5 * (x[j] + y[j])
# Solve problem.
prob.solve()
# Print status.
print("Status:", LpStatus[prob.status])
# Print optimal values of decision variables.
for v in prob.variables():
if v.varValue is not None and v.varValue > 0:
print(v.name, "=", v.varValue)
# Prettier print.
print("\nNumber of teams with both home and away broadcasts: {:.0f}".format(np.sum([z[j].value() for j in teams])))
for (i, j, t) in games:
if w[j, t].value() == 1:
print("Week {:2d}: broadcast team {:2d} at team {:2d}".format(t, i, j))
结果是：
Number of teams with both home and away broadcasts: 11
Week 1: broadcast team 1 at team 10
Week 2: broadcast team 10 at team 11
Week 3: broadcast team 5 at team 8
Week 4: broadcast team 8 at team 4
Week 5: broadcast team 6 at team 9
Week 6: broadcast team 11 at team 3
Week 7: broadcast team 4 at team 2
Week 8: broadcast team 9 at team 7
Week 9: broadcast team 7 at team 1
Week 10: broadcast team 2 at team 5
Week 11: broadcast team 3 at team 6
你可以看到每支球队都有主场和客场广播。