Последовательность формализации экстремальных задач

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

Этапы математической формулировки задачи оптимизации следующие.

• 1. Словесная постановка задачи.
• 2.

  Введение

  обозначений для переменных. При этом полезно указывать их размерность для проверки правильности полученных соотношений.

• 3. Запись в принятых обозначениях критерия оптимальности как функции искомых переменных.
• 4.

  Введение

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

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

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

Пусть имеется п объектов (игроков, команд, …), каждый из которых характеризуется ценой (силой) С, (i = 1, 2, …, п) заранее неизвестной. Нужно упорядочить эти объекты по величине цены, используя только парные сравнения (поединки двух игроков). Сравнение характеризуется погрешностью А. Это случайная величина с заданной плотностью распределения. Результат упорядочивания будет неточным. Его точность, которую надо количественно оценить, зависит от числа сравнений и от их организации (системы розыгрыша).

Как организовать розыгрыш, чтобы достигнуть заданной средней по множеству розыгрышей точности упорядочивания при минимальном числе парных сравнений?

В разных видах спорта, а часто в одном и том же виде, используют разные системы розыгрыша (круговую, кубковую, швейцарскую, смесь круговой и кубковой и пр.) Какая из них лучше? Как выбор системы зависит от А? Как учесть априорные знания о Q (рейтинги), если они имеются и известна их точность?

Задача требует исследования вероятности того, что при парном сравнении победил действительно сильнейший игрок. Эта вероятность зависит от того, с каким счетом он победил и от того, каков средний счет игры в данном виде спорта.