840
Пишу о матмоделях и прикладных задачах. Сотрудничество: @tarasov_math Сайт http://tarasov.expert
Закрыли окончательно заказ по автоматизации мясоперабатывающего завода для IBS. Там все за NDA, про конечного клиента написать не могу.
Ниже напишу суть того, что сделали.
Модель описывает птицеперерабатывающее предприятие: площадки, цеха и производственные центры. Живок перерабатывается, затем продукция проходит разделку и сборку, превращаясь в полуфабрикаты и готовые SKU. Оптимизатор выбирает рецептуры, сырьё, линии, центры, объёмы производства, склады и объемы отгрузок по планам продаж. Выбор среди двух критериев расчёта: минимизация дефицита или максимизация маржи. Поддерживаются 18 месячных периодов, 35 суточных или 28 волн по 12 часов. Целевая размерность - 500 SKU готовой продукции, 100 производственных центров, до 20 этапов на производство каждого SKU и 6000 грузополучателей.
Математическая часть - смешанно-целочисленная линейная модель (MILP), но почти все переменные непрерывные. Основная сложность - целочисленные переменные, которые нужны главным образом для этапов с фиксированной длительностью: они учитывают партии, одновременную обработку нескольких партий на одном центре и переход выпуска между периодами. Также в задаче присутствует множество альтернативных цепочек производства. Складские остатки ведутся по возрасту, чтобы учитывать сроки годности. Снятые ограничения заменяются штрафными превышениями, показывающими нехватку ресурса. Оптимизатор интегрирован с базой и системой заказчика.
Если есть похожие задачи - обращайтесь. :) кококо
Лучший способ учиться "не думать" - данетки.
На тимбилдинге загадал классическую данетку про артиста и шкаф. И ребята очень долго тупили и не могли понять, как могло измениться положение шкафа. Выяснили, что шкаф не был повернут, не сдвигался по полу, не поднимался вверх. И все равно они могли сдвинуться дальше. Потому что представляли в голове картину, а правильный ответ в эту картину не укладывался :)
Математик из Нижнего Тагила опроверг гипотезу, над которой учёные бились почти 30 лет, — благодаря мемной переписке с ChatGPT. Мозги гения + иишка помогут разгрузить дороги от пробок.
Выпускник вышки Дмитрий Рыбин, который недавно защитил кандидатскую по ИИ в Китае и сейчас живёт в Шэньчжэне, попросил жипитишку "совершить научный прорыв" и найти контрпример к гипотезе Диница—Гарга—Гоеманса. Сначала модель отказалась, но после нескольких настойчивых просьб всё-таки взялась за задачу и за пару часов выдала решение.
Вердикт ИИ: идеальное математическое распределение потоков — например, в дорожных, логистических или компьютерных сетях — всегда можно реализовать на практике без дополнительных потерь. Почти 30 лет ни доказать, ни опровергнуть это никому не удавалось.
Талант сначала решил, что нейросеть галлюцинирует. Но контрпример оказался настолько коротким, что он проверил его вручную прямо во время просмотра фильма с друзьями. Ошибки не нашлось — гипотеза действительно оказалась неверной.
Сам математик называет всю историю чистым мемом. Со слов Рыбина, его главный вклад — несколько раз подряд просить иишку не сдаваться и продолжить исследование. Теперь спецы смогут точнее учитывать ограничения при проектировании транспортных, логистических и компьютерных сетей. Это может помочь решить проблему пробок на дорогах — маршруты будут улучшать с учётом всех вводных.
❗ Не грузятся фото и видео? Читайте нас в MAX
Время работы программы.
Одним из самых главных параметров задачи заказчика является время работы алгоритма.
Это требование растет из реальных бизнес целей заказчика. Оно может быть от миллисекунд до недель.
Я считаю, что умение контролировать скорость алгоритма это один из важных критериев профессионализма оптимизатора. Тут срабатывают две вещи - уметь слышать заказчика. Если он хочет чтобы алгоритм работал за секунду то не впихивать ему алгоритм который работает за 10, даже если он классный. И второе уметь заранее оценивать перспективное время работы и не влетать в ситуацию когда алгоритм не справляется.
Понятно что с одной стороны сделать более быстрый алгоритм сложнее чем более медленный. С другой стороны жесткие временные рамки появились не просто так, а значит в реальности эта задача как то уже решается и надо просто улучшить. И еще чем жестче временные рамки там меньше вариантов как получить вообще результат. В некотором смысле такие жесткие по времени алгоритмы искать и писать проще.
У меня было пару кейсов где приходилось решать миллисекундные задачи. Одна это был некий планировщик очередей, где удалось ускорить простейший алгоритм, который вроде как нельзя было улучшить. И еще один кейс - микроманеврирование космического аппарата для ЕКА. Делал когда то. Оба кейса прикольные, постараюсь вспомнить их и описать.
Если у вас есть интересные кейсы на жесткие по времени задачи - пишите в комментариях. :)
А на обратном пути в бизнес зале случайно встретили заказчика
Читать полностью…
Сделали второе видео. https://youtu.be/Hw4Lj4yYXH4
Читать полностью…
Никто не может посоветовать ИИ-иллюстратора? Чтобы он имел опыт использования всех ии рисовалок, мог сам если что что-то нарисовать и мог пробиться сквозь ии до получения нужного результата? Я сам не справляюсь.
Читать полностью…
#текучка
Гребаное судоку.
Готовлю сейчас подкаст про судоку.
Вспомнил прикол, один клиент приходил к нам с выражением "I tied solving this fucking sudoku".
Кажется это еще один критерий, что у вас есть задача для оптимизации бизнеса.
А у вас есть "судоку", от которого вы задолбались ? :)
Хорошая оптимизационная программа должна уметь работать в разных условиях.
Я несколько раз ходил в роли субподрядчика на тендеры по планированию работы бензовозов. Ни разу не выиграли (я помню эпичную историю, когда в конце презентации мой заказчик, который продавал проект спросил уже своего заказчика: "вам понравилась наша презентация?" 🤣).
Вот интересно, как сейчас эти аналоги работают. Тоже надо же оптимизировать, но уже в условиях нехватки бензина и когда заправки так или иначе будут становиться сухими.
Одно из важных преимуществ ЛП перед эвристикой, то она легко перенастраивается под изменение условий. А эвристики обычно пишутся под одну конкретную нехватку, которую и минимизируют.
Еще задача о развозе бензина интересна тем, что это двухуровневая задача. С одной стороны надо сделать план на сегодня. С другой стороны удобный для сегодняшнего дня план, может создать проблемы в последующие дни. То есть на самом деле мы решаем задачу на месяц, которая состоит из взаимодействующих 30 ежедневных задач. Это существенно меняет всю картину. Надо будет про это отдельный пост написать.
#мысль
Наблюдал тут что некоторые разработчики делают две версии алгоритма, в зависимости от его сложности.
Никогда не выбирайте между хорошим, но медленным алгоритмом и плохим, но быстрым. Надо просто подумать и написать быстрый, но хороший алгоритм :) В крайнем случае сделать универсальный алгоритм и бегунок, который плавно перемещает скорость и качество алгоритма.
Вообще любой if это костыль. Вместо здорового коня или трепетной лани мы получаем сиамских близнецов, которые ни то ни сё, и с которыми потом больше возни. При отладке в два раза больше случаев, которые приходится рассматривать.
Если есть желание сделать первый иф, то обычно возникают и вторые и третьи. Режимы работы программы, зима/лето, виды клиентов и т.п. И число различных вариантов поведения работы программы растет экспоненциально. Во всем этом быстро закапываешься без всякого смысла.
Совсем без ифов не обойтись, и потому любой, который можно выкинуть, надо выкидывать к чертовой матери.
Еженедельник видео продолжается! Выложена наконец запись моего выступления про 13 сфер.
Читать полностью…
Решил завести видео блог. Вот первая запись про линейное программирование на ютюбе. Попозже сделаю другие каналы. Жду отзывы и замечания. Надеюсь первый блин не слишком комом.
Читать полностью…
#текучка #ии
Я в прошлом посте забыл написать свежий прикол. Мне новый клиент вместо ТЗ дал md-файлы для введения в контекст 🤖
Голограмма.
#физика
Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою. Козьма Прутков.
Когда-то давно объяснил ребенку, как устроена дифракционная решетка. Недавно он спросил, как работает настоящая голограмма. Смог объяснить на пальцах.
Возьмем на этот раз в качестве аналогии не звуковые, а реальные волны. Если бросить камень в воду, то от него пойдут круги. Если бросить, скажем, два камня, то конструкция волн будет более сложной. Можно бросить одновременно кучу камней так, чтобы каждый камень, если смотреть сверху, был бы пикселем (или металлическую пластинку с вырезанным изображением). И тогда получится какая-то конструкция волн. Отметим пики волн — это получается новая (интерференционная) картинка. Получается, что мы научились делать из одной картинки другую. Назовем эту операцию «плюх».
Что будет, если применить «плюх» к уже полученной картинке? Давайте посмотрим на простой пример отдельного камня. После «плюха» получается система колец разной высоты. Кольцо бросить в воду — от него тоже пойдут волны в разные стороны, и одна из них соберется в центре, и будет одна большая струя вверх, ровно нам том месте где падал исходно камень. Что-то похожее можно посмотреть здесь. Если запустить несколько колец, то получится даже аккуратнее, то есть другие волны будут взаимно гаситься.
Получается, что два «плюха» возвращают исходное изображение. Можно сделать следующую конструкцию. Вырезаем картинку из металла и бросаем в воду. Фотографируем получившуюся волну и делаем по ней новую картинку из металла. Назовем ее «плюхограммой». После этого, если ее снова бросить в воду, то волны создадут исходное изображение.
Теперь перейдем к голограмме. Тут вместо «плюха» мы облучаем лазером, а вместо записывания пиков волн — фотография. Когда мы второй раз освещаем лазером получившуюся фотографию, волны (уже световые) полностью повторяют исходный объект. То есть мы видим его так, как будто он есть, причем с разных ракурсов.
P.S. Голограмма отдельной точки или пары точек как набор колец имеет интересное применение — дифракционная контактная линза. Это просто кружок пластика, на котором нарисованы концентрические окружности. В результате свет идет как будто через эти пары точек. Получается линза с двумя фокусами.
Парадоксы статистики.
Наткнулся недавно на забавный факт. В больнице опрашивали водителей пострадавших в ДТП про их уровень вождения. Они оценили себя в среднем заметно выше среднего.
Звучит очень смешно, но я уверен, их самооценка вполне объективна.
Рассмотрим две когорты - владельцы личного авто и профессионалы.
Первые проезжают 10-20 тысяч километров в год, а вторые 100-200 тысяч. Соответственно профи и ездят сильно лучше и в аварии попадают сильно чаще.
Выложил новое видео. Свою любимую задачку про 4 братьев.
https://www.youtube.com/watch?v=2ivsFwuGsfY
Прямо сейчас получается похожая история с "разумными эвристиками" с одним из клиентов. Есть один очень даже разумный и очевидный критерий определенного вида глупостей, которых не должно по идее быть в оптимальном решении. Мой алгоритм их делает в два раза больше. Точнее картинка выглядит так. Базовый алгоритм не делает глупости в 99% случаев, а мой в 98%. При этом общее качество решения у меня получается заметно выше.
Если же этот критерий зажимать в 0% то общее качество решения должно заметно упасть.
Разумные эвристики хороши как критерий проверки алгоритма на глупость, и как работающий алгоритм, если по каким то причинам нельзя написать лучше алгоритм.
#метод_деления_пополам
Хороший повод напомнить, почему думать вредно.
Принцип звучит очень странно, казалось бы, математик-программист этим и зарабатывает.
Проблема в том, что человеки любят думать, так же как кошки залазить в коробки. Или другими словами - если вы молоток, то все кажется гвоздями. Потому мы норовим думать там, где это просто вредно. А думать надо только там, где без этого реально не обойтись.
Это общие рассуждения, распишу 4 конкретных темы, где вредно думать и почему:
1. Поиск ошибки/отладка. То, чем мы занимаемся большую часть времени. Можно попытаться подумать - то есть выстроить у себя в голове картину мира и найти ошибку. Все так конечно делают и метод работает. Но он медленный и подходит в простых ситуациях. Проблема в том, что он привычный и дефолтный из-за того, что в школе и университете мы учились на простых задачках и там метод хорошо работал. А сложная система обладает эмерджетностью, то есть новыми и неочевидными свойствами. Даже в относительно простой системе канализации можно так неправильно установить кран, что потом унитаз взорвется. Я считаю, что существенно более эффективный способ это локализация ошибки (он же метод разрыва и метод деления пополам). В локализации тоже надо думать, но о другом. Как сделать правильный эксперимент, как проще сузить пространство поиска.
2. Делай, что любишь, и люби, что делаешь. Если ты делаешь алгоритм для заказчика, то очень вредно привязываться к конкретному решению, так как оно может оказаться не оптимальным. Когда мы только начинаем над чем-то думать, мы уже начинаем изобретать велосипеды. И это от вот этой любви.
3. Бери больше кидай дальше, пока летит отдыхай. Всем математикам-оптимизаторам платят за результат. Чем меньше думаешь над конкретной задачей, тем быстрее и эффективней её сделаешь. И тем больше задач решишь. Думать все равно придется.:)
4. Когда кругозор сжимается в точку, она называется точка зрения. Идет прогресс, появляются новые методы и жизнь упрощается. Это и раньше было, а сейчас ИИ дает очень яркий пример. Чтобы идти в ногу со временем, надо, как говорят стартаперы, подрывать себя. То есть скептически к себе временами относиться. проверять себя.
Я воспользовался вашим советом что думать вредно и просто спросил ЛЛМ 4 раза сделать научный прорыв в одной задачке и она сделала
Читать полностью…
Ищу владельцев коммерческой техники. Кажется пора делать ИИ-агентов, которые будут заниматься сдачей этой техники в аренду. Раньше этот процесс автоматизировать было нереально. А сейчас с ИИ кажется пора.
Если вы этим занимаетесь или у вас есть знакомые - отзовитесь!
Скатались со своей командой в Калиниград, хороший тимбилдинг получился.
Читать полностью…
Комбинаторный взрыв.
Комбинаторный взрыв — важное понятие в оптимизации.
Есть классическая математическая легенда, иллюстрирующая этот взрыв. Когда изобретатель шахмат попросил 1 рисовое зернышко за первую клетку и в два раза больше зернышек за каждую последующую.
Общее количество риса получается не космическое, но заоблачное. :) Примерно с гору Эльбрус.
Скоро выложу новый видео-ролик, сделал для него иллюстрацию, не могу не поделиться с вами.
#мысль #внедрение.
Визуализация под заказчика.
В дополнение про нейросетки в головах диспетчеров (и вообще тех кто до алгоритма занимался планированием).
Очень важно не лениться и делать визуализацию точно такую же, к какой привыкли диспетчера. В идеале пользоваться уже готовой их системой, и только сгружать свои результаты.
Потому что люди уже привыкли к такому формату данных. И у них реально нейросетка в голове обучена под эти картинки. Если такой формат чем-то плох, то лучше потом уже переделать. Но начать нужно именно с этой визуализации. Там людям будет проще понять ваши результаты.
Ну и вообще кладите в проект больше визуализации! В эпоху ИИ это совсем просто стало делать.
Вспоминается прикол из прошлого лета. Я делаю расписание самолетов на своем прототипе и регулярно показываю его заказчику и диспетчера моментально находят те или иные огрехи. А в один такой прогон показываю очередное расписание. И на созвоне была тишина минуту или две. Оказывается мой алгоритм смог расставить самолеты, так как не догадались сами диспетчеры. И получилось лучше. Для меня все эти расписания выглядели абсолютно одинаково. :)
Это был прорыв и дальше работать стало сильно легче.
А у вас были какие-то нетривиальные визуализации или истории связанными с ними?
Многоуровневые задачи
Я несколько раз сталкивался с задачами одновременной оптимизации на разных уровнях:
1. Бензовозы. Минимизация пробега при минимальном уровне «сухих» заправок.
2. Контейнерные перевозки. Минимизация порожнего прогона вагонов и контейнеров без их скопления в одном углу страны.
3. VRP для доставки еды — когда курьер может сделать несколько доставок за день.
4. Назначение пилотов и самолётов на рейсы.
Во всех этих задачах тактическая цель до определённой степени конфликтует со стратегической.
Бензин удобно развозить секторами по кругу, чтобы заправки осушались тоже по кругу, и сухие заправки каждый раз были более или менее рядом. Однако такой «лепесток» в моменте даёт не самый короткий маршрут.
В контейнерных перевозках обычно есть дисбаланс между востоком и западом (раньше товары ехали в основном на запад, сейчас — на восток). В моменте всегда удобно не возвращать порожние вагоны и контейнеры назад, но на долгосроке это создаёт большие проблемы.
В VRP для локальной задачи удобно возить заказы по отдельности — так достигается лучший уровень сервиса. Но в рамках целого дня заказы надо группировать, чтобы курьеры не заканчивались.
При планировании пилотов на короткий промежуток можно не учитывать налёт и брать самых удобных. Но это ведёт к неравномерному налёту, и к концу месяца часть пилотов выбирает лимит и становится недоступна.
Способов решения этой проблемы я вижу два.
1. Критерий «оперативного долга», который локальная задача может копить или тратить, и добавить его в целевую функцию. Тогда верхнеуровневая задача по сути становится жадным алгоритмом с этим критерием. Метод удобен, но только когда критерий очевиден и легко настраивается. В некоторых случаях другого варианта просто нет — например, когда мы не знаем будущего.
2. Решить стратегическую задачу укрупнённо, а после фиксации принципиальных решений решать тактические подзадачи.
Самое главное — осознать, сколько уровней у вашей задачи. Если их больше одного, то сначала надо решать верхний уровень, а уже потом — нижний. Слышал естественное правило: 80 % экономии даёт верхний уровень и 20 % — нижний.
#мысль
Неосознанная компетентность.
Есть такое интересное явление, которое я обнаружил, когда делал планирование пилотов на самолеты, и с тех пор на которое регулярно натыкаюсь в совершенно разных отраслях.
Диспетчера (и другие ручные планировщики) хорошо делают свою работу, но не могут объяснить словами, что они делают. А если они и объясняют, то только конкретное решение. И то что они говорят словами, это тоже нельзя брать на веру.
То есть они говорят про симптомы.
Надо понимать при этом, что они делают они свою работу очень даже хорошо, лучше чем кажется на первый взгляд. И если они хотят странного, то скорее с ними все в порядке, и это ты недоглядел чего-то в своем алгоритме.
Причина этого простая. Человек это обученная годами нейросетка. А задачи объяснять не было.
Похожая история была в Школе Яндекса. При массе отличных программистов в Яндексе было не так просто найти в школу преподавателей. Потому что уметь осознавать, что ты делаешь и как ты принимаешь решения, и потом объяснить это другому - это дополнительный навык. Собственно он называется умение преподавать.
А.С. Тарасов (TarasovMath), Задача Таммеса для 13 точек (сильная проблема тринадцати сфер)
Кстати запись прошедшего семинара от 13 мая:
YouTube->
Дзен->
RuTube->
Файл->
Презентация->
Объявляется неделя видосов! Вышло интервью с Леной Денисовой, про образование, как учить детей с учетом ИИ, как воспитать гениев и много другое, рутюб.
Читать полностью…
#mip #cpsat
Не складывается у меня любовь с CPSAT. Не видел еще примеров задач, чтобы CPSAT был прямо лучше MIP.
Было несколько попыток знакомых апологетов CPSAT переписать MIP задачу под CP и все были не удачными. Я вот сейчас попробую предпринять попытку переписать одну задачу с CP на MIP. При этом она должна стать сильно быстрее и лучше.
Далеко не факт конечно. Синдром, что прочитать чужую программу сложнее, чем написать свою тоже имеется :)
Главная моя претензия к CP-SAT даже не в плане алгоритмов, а в том что она провоцирует программистов писать в привычном им императивном стиле. А это приводит к бегу по кругу в стиле анекдотов Даниила Хармса.
Сейчас полезно учить декларативные и функциональные языки программирования. Просто чтобы уметь разные парадигмы. Так будет проще освоить новые парадигмы которые придут с ИИ.
#мысль
Чем ты лучше ИИ?
Я регулярно нанимаю фрилансеров на разовые задачи. И кучу прошлых задач явно можно было сделать с помощью ИИ не хуже если не лучше.
И теперь когда я начинаю работать с фрилансером я в голове уже прокручиваю вопрос.
Наверно пора задавать уже его вслух. И всем уметь отвечать на него. Я вот умею. А вы?
Гуляли с детьми по оленьему сафари парку. Повторили упрощенную задачку про подвесной мост. Фонарик не нужен, два брата шатают мост так, что другим уже не пройти :)
Читать полностью…
Поосваивал Claue Code на курсах, не понравилось пробиваться сквозь кучу препонов, поставил вместо него Open Code.
В качестве пробы пера сделал сайт https://deepwhale.ru/ для нашего проекта. Вполне себе. При этом все на бесплатной версии DeepSeek, соответственно ни копейки не потратил только время :). В общем рекомендую OpenCode. Пока для себя не понял где мне его не хватает