Зачем решать экстремальные задачи

Введение

Постановка задачи

Формирование целевой функции и начальных условий для минимизации стоимости диеты

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

Пролог

Транспортная задача линейного программирования относится к перечню классических задач, решаемых в практике деятельности людей. Эта задача методами классической математики не решается. В задаче необходимо отыскивать экстремум целевой функции. В задаче целевая функция – линейная. Ограничения на переменные (их может быть очень много) описываются также линейными зависимостями. Казалось бы чего проще. Но как раз ограничения и порождают трудности, связанные не просто с поиском max и min при отсутствии ограничений, а с необходимостью учета таких ограничений. Искать требуется не просто экстремум, а условный экстремум. Методы решения задачи позволяют учитывать особенности структуры задачи и даже отказаться от симплексного метода решения в чистом виде.

Сейчас в различных источниках имеется огромное количество статей, материалов конференций, телеграм-каналов и открытых репозиториев в GitHub на любую тему из сферы Data Science. В статье хочется обратить ваше внимание на отдельный класс задач, которому, по нашему мнению, уделяют меньше внимания и который не так часто встречается в рамках Data Science кейсов, соревнований или хакатонов.

Речь пойдет о «Других» рекомендациях -- ML-системах, которые уже нельзя отнести к рекомендательным в популярном/классическим смысле. Давайте разберемся, что для нас классика, а что — нет.

Недавно столкнулся с интересной задачей в интернете. Компания BIA Technologies организовала конкурс для математиков, в рамках которого предлагалось решить реальную прикладную задачу, а именно — построить оптимальное расписание производственных заданий для предприятия на горизонт планирования в 30 дней. Я решил поучаствовать в конкурсе, так как данный вызов показался мне интересным, плюс у меня уже был за плечами опыт реализации подобных задач на практике. В этой статье я хотел поделиться с вами результатами и продемонстрировать лучшие, на мой взгляд, подходы к решению таких задач.

Дочитав эту статью до конца, вы сможете решать точно задачу коммивояжёра на сотню элементов за считанные секунды!

Заинтригованы? Тогда, добро пожаловать под кат.

На Хабре уже были публикации о симплекс-методе раз и два. И они очень даже хороши. Но это не те публикации, которые расчитаны на школьников или учителей школ. Я же хотел обратить внимание на одну довольно старую статью, вышедшую в журнале "Юный техник" в августе 1985 года. Естественно, она была нацелена на школьников. И мне давно хотелось разобрать её детально...

Приветствую! Я, Ложкинс Алексей, консультант и разработчик оптимизационных решений и математических моделей для бизнеса. Это первая в цикле работ обучающая статья, часть личного образовательного проекта "Make optimization simple". Цель проекта – продемонстрировать доступность технологий и показать на примерах, что моделировать можно без глубокого математического фундамента.

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

Теперь к истокам задачи: часто, чтобы математическая модель была применима в реальном секторе, необходимо использовать очень много ограничений и большое количество переменных. Задачи, возникающие в бизнесе в реальных условиях, требуют использования моделей с большим количеством ограничений и большим количеством переменных.  Временами задача в лоб может и не решиться, поэтому были придуманы различные трюки. Один из них - метод « генерации столбцов» (Column generation).