В данной статье мы, Advanced Analytics GlowByte, расскажем, как нам удалось ускорить решение задачи NBO на open-source солвере CBC примерно в 100 раз и добиться повышения оптимального значения целевой функции на 0,5%.
Рубрика «Линейное программирование»
Как нам удалось в 100 раз ускорить решение оптимизационной задачи NBO в Альфа-Банке
2024-09-16 в 8:53, admin, рубрики: CBC, nbo, pyomo, исследование операций, Линейное программирование, маркетинговая оптимизация, Математическая оптимизация, ускорение солверовЗадача коммивояжёра в общем виде. Наибыстрейшее точное решение
2024-09-04 в 16:19, admin, рубрики: задача коммивояжёра, Линейное программирование
К величию есть только один путь, и этот путь проходит через страдания.
- Альберт Эйнштейн
Эта работа является заключением пятилетнего марафона по поиску самого быстрого способа нахождения минимального точного решения для задачи коммивояжёра в общем виде.
Сбалансированный рацион питания
2024-08-08 в 9:16, admin, рубрики: витамины, здоровое питание, Линейное программирование, правильное питание, рацион питанияВ сети существует много материалов из серии «ешьте то… не ешьте это… и будете здоровее». Проблема в том, что эти материалы часто противоречат друг другу, обрывочны и бессистемны. Поэтому мне стало интересно разобраться с тем, какие же всё-таки продукты включать в рацион, чтобы одновременно:
-
получать все требуемые элементы в минимально необходимых нормах,
-
не превышать безопасные нормы элементов,
-
оптимизировать меню относительно некоторого показателя, например цены, или относительной «вкусности», или др.
Такая постановка задачи соответствует Читать полностью »
Задача коммивояжера (TSP) точное решение — метод целочисленного линейного программирования (Integer programming)
2023-01-21 в 7:23, admin, рубрики: python, TSP, алгоритм, Алгоритмы, высокая производительность, задача коммивояжёра, Линейное программирование, Совершенный код, точное решение, целочисленное программирование
Все пути одинаковы: они ведут в никуда. Но у одних есть сердце, а у других — нет. Один путь дает тебе силы, другой — уничтожает тебя.
- Карлос Кастанеда
Как оптимизировали экономику СССР и что из этого вышло
2020-11-18 в 8:30, admin, рубрики: Блог компании VDSina.ru, Канторович, линейная алгебра, Линейное программирование, математика, Научно-популярное, Парето, СССР, технологические процессы, Читальный зал, экономика
Я работаю специалистом по обработке и анализу данных (data scientist), поэтому большая часть моей работы включает в себя подбор оптимизируемых метрик и размышления о том, как выполнять процессы с максимальной эффективностью. Недавно я обнаружил совершенно удивительную книгу об экономических проблемах в СССР и о коллективе экономистов и компьютерных учёных, стремившихся решить их на основе данных. Книга называется Red Plenty. На самом деле она написана в жанре романа, что странно, однако представляет собой точную экономическую историю СССР. Автор активно заимствует информацию из книги 1973 года под названием Planning Problems in the USSR, которую я тоже приобрёл. При чтении этих книг я не мог не обратить внимания на параллели с планированием в любой современной организации. Факт, который покажется сегодня знакомым каждому data scientist: во второй книге есть цитата исследователя, жалующегося на то, что 90% своего времени он потратил на очистку данных, и только 10% — на само моделирование!
Кроме проведения интересных параллелей с современными data science и методами исследований технологических операций, эти книги помогли мне многое понять об интересных аспектах, о которых ранее я почти ничего не знал, например, о линейном программировании, ценовом равновесии и истории Советского Союза. В этом посте я расскажу о том, что узнал.
Читать полностью »
Подробный разбор симплекс-метода
2019-11-02 в 14:18, admin, рубрики: Линейное программирование, математика, оптимизация, Симплекс-методПролог
Недавно появилась необходимость создать с нуля программу, реализующую алгоритм симплекс-метода. Но в ходе решения я столкнулся с проблемой: в интернете не так уж много ресурсов, на которых можно посмотреть подробный теоретический разбор алгоритма (его обоснование: почему мы делаем те или иные шаги) и советы по практической реализации — непосредственно, алгоритм. Тогда я дал себе обещание — как только завершу задачу, напишу свой пост на эту тему. Об этом, собственно, и поговорим.
Замечание. Пост будет написан достаточно формальным языком, но будет снабжен комментариями, которые должны внести некоторую ясность. Такой формат позволит сохранить научный подход и при этом, возможно, поможет некоторым в изучении данного вопроса.
Читать полностью »
Оптимальное расположение шардов в петабайтном кластере Elasticsearch: линейное программирование
2018-11-13 в 13:23, admin, рубрики: elasticsearch, jvm, Shardonnay, Алгоритмы, высокая производительность, индексирование по времени, линейная оптимизация, Линейное программирование, линейный солвер, математика, Проектирование и рефакторинг, Серверная оптимизация, стек ELK
В самом сердце информационно-поисковых систем Meltwater и Fairhair.ai работает набор кластеров Elasticsearch с миллиардами статей из СМИ и социальных медиа.
Индексные шарды в кластерах сильно отличаются по структуре доступа, рабочей нагрузке и размеру, что поднимает некоторые очень интересные проблемы.
В этой статье мы расскажем, как применили линейное программирование (линейную оптимизацию) для максимально равномерного распределения рабочей нагрузки поиска и индексирования по всем узлам в кластерах. Это решение уменьшает вероятность, что один узел станет узким местом в системе. В результате мы увеличили скорость поиска и сэкономили на инфраструктуре.
Читать полностью »
Расширение аналитических возможностей метода линейного программирования средствами Python
2017-10-11 в 5:32, admin, рубрики: python, библиотека cvxopt, диета, Линейное программирование, математика, разработка под windowsВведение
По линейному программированию средствами Python мною в статье [1] было рассмотрено решение задачи оптимизации с функцией цели альтернативной к основной. Как было показано в статье приём с введением новых функций цели при рассмотрении одной общей задачи оптимизации значительно расширяет аналитические возможности метода. Поэтому логично выбрать и рассмотреть такой пример, в котором при решении общей задачи оптимизации можно сформулировать несколько альтернативных функций цели.
Постановка задачи
На примере задачи об оптимальной диете рассмотреть формирование различных альтернативных функций цели с необходимыми начальными условиями. Кроме этого разработать простой и единообразный интерфейс решения подобных задач с выводом результатов понятных конечному пользователю.
Формирование целевой функции и начальных условий для минимизации стоимости диеты
Для поддержания нормальной жизнедеятельности человеку необходимо потреблять в день не менее 118 г белков, 56 г жиров, 500 г углеводов и 28 г минеральных солей. Эти питательные вещества содержатся в разных количествах и разных пищевых продуктах.
В таблице приведено количество питательных веществ в различных продуктах в г/кг и условная цена этих продуктов за 1 кг. Необходимо составить дневной рацион, содержащий минимальную суточную норму питательных веществ при минимальной их стоимости.
Линейное программирование в python силами библиотеки scipy
2017-07-11 в 12:41, admin, рубрики: python, scipy, Линейное программирование, метки: линейное программированиеВ своей первой публикации мне хочется рассказать о том, как можно быстро и просто решить задачу линейного программирования с помощью замечательной библиотеки scipy. Для подобных задач в python есть так же pulp, но для новичков в scipy более понятный синтаксис.
Зачем может понадобиться линейное программирование на практике? Как правило, с его помощью решают задачу минимизации функции f(x) (или обратную задачу максимизации для — f(x) ).
Здесь я не буду приводить теоретические выкладки (можно посмотреть тут), а рассмотрю конкретный пример.
Итак, задача.
У нас есть 8 фабрик, которые каждую неделю производят некоторое количество продукции. Нам нужно распределить продукцию по 13 магазинам так, чтобы максимизировать суммарную прибыль, при этом разрешается закрывать нерентабельные магазины.
Читать полностью »
Решение задач линейного программирования с использованием Python
2017-06-10 в 11:08, admin, рубрики: optimize, python, scipy, Линейное программирование, метки: Линейное программированиеЗачем решать экстремальные задачи
На практике очень часто возникают задачи, для решения которых используются методы оптимизации. В обычной жизни при множественном выборе, например, подарков к новому годы мы интуитивно решаем задачу минимальных затрат при заданном качестве покупок.
К сожалению, не всегда можно положиться на интуицию. Допустим Вы сотрудник коммерческой фирмы и отвечаете за рекламу. Затраты на рекламу в месяц не должны превышать 10 000 денежных единиц (д.е). Минута радиорекламы стоит 5 д.е., а телерекламы 90 д.е. Фирма намерена использовать радиорекламу в два раза чаще чем телерекламу. Практика показывает, что 1 минута телерекламы обеспечивает объём продаж в 30 раз больший чем 1 минута радиорекламы.