Оптимизация с учетом предпочтений

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

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

Задачи оптимизации

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

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

Мы же, для примера, возьмем классическую задачу группового путешествия!)