6.2. Футбольные клубы и спортсмены

(Приводим выдержку из заметки "Итальянский легион", опубликованной в "Советском спорте" 23 сентября 1984 г.

"Италия, пожалуй, самый крупный в мире "импортер" футбольных "звезд". Местные клубы скупили много выдающихся игроков Европы и Южной Америки. Хорошо еще, иронично замечают футбольные обозреватели многих стран, что в Италии каждому клубу разрешают заявлять только двух зарубежных игроков. Из 16 команд высшей лиги только "Кремонезе" не имеет в своем составе ни одного иностранного футболиста.")

Спортивная фирма "Рекорд" владеет несколькими футбольными клубами. Пусть, для определенности, их три - B₁, B₂, B₃.

Как это практикуется во многих зарубежных странах, коллектив игроков частично пополняется за счет покупки спортсменов, подготовленных в юниорских центрах и клубах других организаций и в иных странах. Простоты ради предположим, что таких центров два - A₁ и A₂ и что в текущем году центры предлагают для переходов в клубы фирмы соответственно a₁ и a₂ игроков примерно одного класса. В то же время футбольные клубы нуждаются в пополнении своих составов соответственно b₁, b₂ и b₃ игроками. Без ограничения общности можно допустить, что

т. е., что общее число подготовленных в. центрах игроков совпадает с общими потребностями клубов. При нарушении этого условия, как станет ясно из последующего, можно ввести в рассмотрение "фиктивный" клуб (при выпуске, превышающем потребности) или "фиктивный" центр (при потребностях, превышающих выпуск).

Допустим, что за игрока, передаваемого центром A_i клубу B_j, вносится сумма, равная c_ij и считающаяся предопределенной. Перед фирмой возникает задача составления такого плана приглашения игроков из центров в клубы, который при наименьших затратах предусматривает приглашение всех подготовленных футболистов и полное удовлетворение потребностей клубов в пополнении.

Придадим задаче математическую форму. Обозначим через x_ij пока неизвестное число футболистов, переходящих из центра A_i в клуб B_j. Тогда общее число футболистов, переходящих из центров A₁ и A₂ в клуб B_j, составит x_1j + x_2j. Эта сумма должна совпадать с потребностью b_j клуба B_j (j = 1, 2, 3). Тем самым приходим к трем уравнениям:

При этом общее число футболистов, передаваемых центрами клубам, составит

При выбранном плане X = {x_ij; i = 1, 2; j = 1, 2, 3} распределения футболистов по клубам общие затраты фирмы составят

Приходим, таким образом, к следующей математической задаче (задаче линейного программирования): среди всех неотрицательных решений x_ij системы ограничений (7) - (8) найти такое, при котором форма S(X) достигает наименьшего значения.

Легко видеть, что сформулированная нами прежде задача о назначениях имеет тот же вид, что и рассматриваемая задача, в которой все a_i равны 1 и все b_j равны 1.

Познакомимся с методами решения такого типа задач сначала на числовом примере. Положим a₁ = 2; a₂ = 3, b₁ = 1, b₂ = 3, b₃ = 1 соответственно. Пусть заданы стоимости c₁₁ = 4, c₁₂ = 9, c₁₃ = 3, c2₁ = 4, c₂₂ = 8, c₂₃ = 1. Условие (6) при этом выполнено, а ограничения (7) - (8) и минимизируемая форма (9) принимают вид

Заметим вновь, что при выполнении условия (6) система ограничений (10) - (11) всегда совместна. Действительно, если отвлечься от минимизации формы S(X), то совершенно очевидно, что существует бесчисленное множество способов организовать требуемые пополнения клубов. Систему (10) - (11) пяти алгебраических уравнений с шестью неизвестными (ее ранг r = 4) можно разрешить относительно четырех неизвестных (они называются базисными) и выразить их через два оставшихся (свободных) неизвестных. Выбрав в качестве базисных x₁₃, x₂₁, x₂₂, x₂₃, а в качестве свободных x₁₁, x₁₂, найдем

При этом для формы S(X) получим выражение

Наконец, запишем условия неотрицательности всех переменных

Прежде чем перейти к геометрическому толкованию задачи и ее решению, введем некоторые основные понятия линейного программирования.

Остановимся сначала на неравенстве (I). Введем на плоскости прямоугольную декартову систему координат. Оси системы обозначим x₁₂ и x₁₁. Заменим в (I) знак неравенства на знак точного равенства:

Известно из курса математики средней школы, что всякое линейное уравнение, и, в частности (Г), определяет в данной системе координат прямую. Рассмотрим далее линейную функцию (линейную форму), равную левой части уравнения (Г):

Выберем на плоскости произвольную точку A₀ с координатами (x₁₁⁰, x₁₂⁰) и подставим их в выражение (16) для формы F. При этом форма F примет определенное числовое значение

Это число называют значением F в точке A₀.

Зададимся теперь произвольным числом С и рассмотрим совокупность точек плоскости (геометрическое место точек плоскости), в которых форма F равна числу C:

Последнее уравнение определяет некоторую прямую на плоскости. Эту прямую называют линией равных значений формы F. В частности, прямая (Г) является линией нулевых значений F. Две прямые - линии равных значений

отвечающие различным значениям C₁ и C₂, не пересекаются: они имеют равные угловые коэффициенты (но различные свободные члены) и оказываются параллельными.

Следовательно, вся плоскость как бы "расслаивается" на бесчисленное множество параллельных прямых - прямых равных значений формы F. Переход от точек одной прямой к точкам другой сопровождается изменением значения формы F.

Все сказанное выше о рассмотренной нами форме (16) сохраняет свою силу в отношении всякой другой линейной формы Ф = a₁x₁₁ + a₂x₁₂ + a₀ с произвольными действительными коэффициентами a₀, a₁, a₂. В частности, все справедливо для линейных форм - левых частей неравенств (II) - (VI). Вот почему, начиная с этого места, будем рассматривать произвольную форму Ф, в которой для сокращения записи обозначим x₁₁ и x₁₂ просто через x₁ и x₂ соответственно: