Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

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

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

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


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

Как это практикуется во многих зарубежных странах, коллектив игроков частично пополняется за счет покупки спортсменов, подготовленных в юниорских центрах и клубах других организаций и в иных странах. Простоты ради предположим, что таких центров два - A1 и A2 и что в текущем году центры предлагают для переходов в клубы фирмы соответственно a1 и a2 игроков примерно одного класса. В то же время футбольные клубы нуждаются в пополнении своих составов соответственно b1, b2 и b3 игроками. Без ограничения общности можно допустить, что

a1 + a2 = b1 + b2 + b3, (6)

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

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

Придадим задаче математическую форму. Обозначим через xij пока неизвестное число футболистов, переходящих из центра Ai в клуб Bj. Тогда общее число футболистов, переходящих из центров A1 и A2 в клуб Bj, составит x1j + x2j. Эта сумма должна совпадать с потребностью bj клуба Bj (j = 1, 2, 3). Тем самым приходим к трем уравнениям:

x11 + x21 = b1; x12 + x22 = b2, x13 + x23 = b3. (7)

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

x11 + x12 + x13 = a1; x21 + x22 + x23 = a2. (8)

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

S(X) = c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23. (9)

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

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

Познакомимся с методами решения такого типа задач сначала на числовом примере. Положим a1 = 2; a2 = 3, b1 = 1, b2 = 3, b3 = 1 соответственно. Пусть заданы стоимости c11 = 4, c12 = 9, c13 = 3, c21 = 4, c22 = 8, c23 = 1. Условие (6) при этом выполнено, а ограничения (7) - (8) и минимизируемая форма (9) принимают вид

x11 + x12 = 1, x12 + x22 = 3, x13 + x23 = 1, (10)
x11 + x12 + x13 = 2, x21 + x22 + x23 = 3, (11)
xij≥0 (i = 1, 2; j = 1, 2, 3), (12)
S(X) = 4x11 + 9x12 + 3x13 + 4x21 + 8x22 + x23. (13)

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

x13 = 2 - x11 - x12, x23 = - 1 + x11 + x12, (14)
x21 = 1 - x11, x22 = 3 - x12.

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

S(X) = 33 - 2x11 - x12. (15)

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

2 - x11 - x12≥0, (I)
1 - x11≥0, (II)
3 - x12≥0, (III)
-1 + x11 + x12≥0, (IV)
x11≥0, (V)
x12≥0. (VI)

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

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

2 - x11 - x12 = 0. (I')

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

F = 2 - x11 - x12. (16)

Выберем на плоскости произвольную точку A0 с координатами (x110, x120) и подставим их в выражение (16) для формы F. При этом форма F примет определенное числовое значение

F(A0) = F0 = 2 - x110 - x120.

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

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

2 - x11 - x12 = C.

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

x11 + x12 + C1 - 2 = 0, x11 + x12 + C2 - 2 = 0,

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

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

Все сказанное выше о рассмотренной нами форме (16) сохраняет свою силу в отношении всякой другой линейной формы Ф = a1x11 + a2x12 + a0 с произвольными действительными коэффициентами a0, a1, a2. В частности, все справедливо для линейных форм - левых частей неравенств (II) - (VI). Вот почему, начиная с этого места, будем рассматривать произвольную форму Ф, в которой для сокращения записи обозначим x11 и x12 просто через x1 и x2 соответственно:

Ф = a0 + a1x1 + a2x2. (17)
предыдущая главасодержаниеследующая глава



ИНТЕРЕСНО:

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru