Если Вы когда-то учились в вузе на технической специальности или учитесь сейчас (иначе, зачем бы Вам эта статья), у Вас наверняка есть предмет, который назывался примерно так — «Методы оптимизации» / «Введение в оптимизацию» или что-то похожее. Задачки там примерно такие: «завод производит продукцию Читать полностью »
Рубрика «Линейное программирование»
Разбираем условия Каруша–Куна–Таккера. Решаем сложно простую задачу
2025-09-06 в 18:24, admin, рубрики: ККТ, Линейное программирование, методы оптимизации, нелинейное программированиеКому нужна математика?
2025-08-01 в 17:07, admin, рубрики: Алгоритмы, графы, диффи-хеллмана, книги, криптография, Линейное программирование, математика, научпоп, оптимизация, прикладная математикаЯ часто рассказываю математику тем, кто сам ею не занимается. Это непросто — и не только потому, что математика сложна сама по себе
Обычно математики интересуются тем, что связано с другими разделами самой математики, и людям «снаружи» непросто понять их мотивацию. Современная математика чаще всего развивается изнутри — из собственных понятий, задач и связей. Тем ценнее случаи, когда удаётся выстроить рассказ вокруг содержательных приложений
Больше текстов можно найти в моём телеграм канале Кроссворд Тьюринга Подписывайтесь!)
Стыковка космических аппаратов в Unity
2025-02-19 в 8:24, admin, рубрики: unity, Алгоритмы, космос, Линейное программирование, математика, оптимизация, Программирование, стыковкаКак нам удалось в 100 раз ускорить решение оптимизационной задачи NBO в Альфа-Банке
2024-09-16 в 8:53, admin, рубрики: CBC, nbo, pyomo, исследование операций, Линейное программирование, маркетинговая оптимизация, Математическая оптимизация, ускорение солверов
В данной статье мы, Advanced Analytics GlowByte, расскажем, как нам удалось ускорить решение задачи NBO на open-source солвере CBC примерно в 100 раз и добиться повышения оптимального значения целевой функции на 0,5%.
Введение
Задача коммивояжёра в общем виде. Наибыстрейшее точное решение
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 с миллиардами статей из СМИ и социальных медиа.
Индексные шарды в кластерах сильно отличаются по структуре доступа, рабочей нагрузке и размеру, что поднимает некоторые очень интересные проблемы.
В этой статье мы расскажем, как применили линейное программирование (линейную оптимизацию) для максимально равномерного распределения рабочей нагрузки поиска и индексирования по всем узлам в кластерах. Это решение уменьшает вероятность, что один узел станет узким местом в системе. В результате мы увеличили скорость поиска и сэкономили на инфраструктуре.
Читать полностью »