Это казалось забавной проблемой, поэтому я решил сформулировать ее как IP.
Пусть J и T - набор команд и недель.
ПустьG будет набором всех игр;каждый элемент G представляет собой кортеж (i,j,t), который указывает на выездную команду (i), домашнюю команду (j) и неделю (t).
Пусть H быть набором всех домашних игр;каждый элемент H представляет собой кортеж (j,t), который указывает домашнюю команду (j) и неделю (t).
Определите следующие двоичные переменные решения:
w[j,t] = 1, если мы транслируем домашнюю игру в j в неделю t, = 0 в противном случае (определено для (j,t) in H) x[j] = 1, если команда j имеет выездтрансляция игры, = 0 в противном случае (определено для j в J) y[j] = 1, если команда j имеет трансляцию домашней игры, = 0 в противном случае (определено для jв J) z[j] = 1, если у команды j есть как выездная, так и домашняя трансляция, = 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}
Целевая функция рассчитывает общее количество команд, которые получают как домашнюю, так и выездную трансляцию.Первое ограничение говорит, что нам нужна ровно одна трансляция в неделю.Второе ограничение гласит, что x[j] не может равняться 1, если только не будет недели, когда в эфир выйдет j.Третье ограничение говорит то же самое для y[j] и домашней трансляции.Четвертое ограничение говорит, что z[j] не может быть равно 1, если оба значения x[j] и y[j] не равны 1. Последнее ограничение говорит, что все должно быть двоичным.
Я кодировал эту модель в Python / PuLPиспользуя расписание из 11 игр.(Очевидно, вы бы включили свой собственный график.)
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
Вы можете видеть, что каждая команда получает как домашнюю, так и выездную трансляцию.