Рубрика «Линейное программирование»

Задача коммивояжера (TSP) точное решение — метод целочисленного линейного программирования (Integer programming) - 1

Все пути одинаковы: они ведут в никуда. Но у одних есть сердце, а у других — нет. Один путь дает тебе силы, другой — уничтожает тебя.

- Карлос Кастанеда

Читать полностью »

Как оптимизировали экономику СССР и что из этого вышло - 1

Я работаю специалистом по обработке и анализу данных (data scientist), поэтому большая часть моей работы включает в себя подбор оптимизируемых метрик и размышления о том, как выполнять процессы с максимальной эффективностью. Недавно я обнаружил совершенно удивительную книгу об экономических проблемах в СССР и о коллективе экономистов и компьютерных учёных, стремившихся решить их на основе данных. Книга называется Red Plenty. На самом деле она написана в жанре романа, что странно, однако представляет собой точную экономическую историю СССР. Автор активно заимствует информацию из книги 1973 года под названием Planning Problems in the USSR, которую я тоже приобрёл. При чтении этих книг я не мог не обратить внимания на параллели с планированием в любой современной организации. Факт, который покажется сегодня знакомым каждому data scientist: во второй книге есть цитата исследователя, жалующегося на то, что 90% своего времени он потратил на очистку данных, и только 10% — на само моделирование!

Кроме проведения интересных параллелей с современными data science и методами исследований технологических операций, эти книги помогли мне многое понять об интересных аспектах, о которых ранее я почти ничего не знал, например, о линейном программировании, ценовом равновесии и истории Советского Союза. В этом посте я расскажу о том, что узнал.
Читать полностью »

Пролог

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

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

Оптимальное расположение шардов в петабайтном кластере Elasticsearch: линейное программирование - 1В самом сердце информационно-поисковых систем Meltwater и Fairhair.ai работает набор кластеров Elasticsearch с миллиардами статей из СМИ и социальных медиа.

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

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

Введение

По линейному программированию средствами Python мною в статье [1] было рассмотрено решение задачи оптимизации с функцией цели альтернативной к основной. Как было показано в статье приём с введением новых функций цели при рассмотрении одной общей задачи оптимизации значительно расширяет аналитические возможности метода. Поэтому логично выбрать и рассмотреть такой пример, в котором при решении общей задачи оптимизации можно сформулировать несколько альтернативных функций цели.

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

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

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

Для поддержания нормальной жизнедеятельности человеку необходимо потреблять в день не менее 118 г белков, 56 г жиров, 500 г углеводов и 28 г минеральных солей. Эти питательные вещества содержатся в разных количествах и разных пищевых продуктах.

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

Расширение аналитических возможностей метода линейного программирования средствами Python - 1
Читать полностью »

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

Зачем может понадобиться линейное программирование на практике? Как правило, с его помощью решают задачу минимизации функции f(x) (или обратную задачу максимизации для — f(x) ).

Здесь я не буду приводить теоретические выкладки (можно посмотреть тут), а рассмотрю конкретный пример.

Итак, задача.

У нас есть 8 фабрик, которые каждую неделю производят некоторое количество продукции. Нам нужно распределить продукцию по 13 магазинам так, чтобы максимизировать суммарную прибыль, при этом разрешается закрывать нерентабельные магазины.
Читать полностью »

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

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

К сожалению, не всегда можно положиться на интуицию. Допустим Вы сотрудник коммерческой фирмы и отвечаете за рекламу. Затраты на рекламу в месяц не должны превышать 10 000 денежных единиц (д.е). Минута радиорекламы стоит 5 д.е., а телерекламы 90 д.е. Фирма намерена использовать радиорекламу в два раза чаще чем телерекламу. Практика показывает, что 1 минута телерекламы обеспечивает объём продаж в 30 раз больший чем 1 минута радиорекламы.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js