Исследование операций (operations research)

Исследование операций и мат.анализ

Что лучше, купить на ebay, aliexpress, или еще где, но надо платить за доставку? Но там дешево? Или купить тут? Но дороже? Но на соседней улице?

Лучше большие раки вчера по пять рублей, или сегодня маленькие по три рубля?

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

(видео)

А иногда вам предлагают оптом, но дешево. И вы прикидываете, за сколько вы сможете продать. А чтобы купить всё скопом, надо денег занять. Банк предлагает столько-то под столько-то процентов на столько-то времени. А инфляция? Какой она будет через несколько лет?

И товаров много. И продаются они по-разному.

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

Это и есть исследование операций.

Еще в книгах (AMPL, Х.Таха) об этом часто попадаются задачки вроде того, что всякому человеку нужно столько-то углеводов, жиров, белков, витаминов. И есть у вас магазин где о каждом товаре вы можете знать состав и цену. Задача накупить товаров так, чтобы сбалансировать рацион и минимизировать цену. А можно ввести дополнительный критерий -- минимизировать массу и/или объем, например, потому что вы собираетесь в поход.

Сложнее -- у вас хлебозавод, где несколько линий, одна может делать бублики и булки, вторая караваи и торты, итд. Есть сырье по известным ценам. Есть персонал. Вася может делать пряники и караваи, Петя может делать отличные хипстерские новомодные маффины и прочее, но Петя запойный, и выпадает из жизни в среднем на неделю в 2 месяца. Есть еще какие-то работники. Например, женщины, часть из которых может уйти в декрет. А ваша задача заработать побольше денег, загрузить линии побольше, да и работников тоже загрузить по максимуму, чтобы не было жалко платить им зарплату, отрывать её от сердца своего.

Так вот. Если вы почитаете классическую книгу Х.Таха -- Введение в исследование операций. Или книгу Б.Кернигана (того самого, что K&R) про AMPL. Или поковыряете Google OR-tools.

... то придете к выводу, что все эти инструменты (AMPL, Google OR-tools, IBM CPLEX) просто ищут (локальный) минимум-максимум ф-ции. Ф-ция, впрочем, может быть (очень) сложной и описываться (очень) большой системой уравнений. И инструменты эти могут быть крайне сложными. Но их суть сводима к одному предложению, только что приведенному выше.

Одна из самых важных частей мат.анализа это тоже поиск минимума-максимума ф-ций.

Очень многие практические задачи сводятся к поиску минимума-максимума, поэтому мат.анализ так старательно впрессовывают в головы студентам в технических ВУЗах.

Вроде того что надо взять ведро, пройти от точки А к точке Б, но при этом спуститься к реке и набрать воды. Где спускаться? Потом задача усложняется -- местность холмистая, взбираясь на холм вы затрачиваете столько-то усилий, спускаясь тоже затрачиваете, хотя и меньше. А река извилистая, к тому же.

Все эти задачки вроде того как муравей ползет по кувшину диковинной формы и ему нужно найти кратчайший путь. Ну и всё такое.

Ну а IT-шники, нередко сталкиваются с задачками вроде сборки серваков. И начинается -- купить старый "по объявлению" и напихать туда винтов? Но ведь напругу он же будет жрать так же как и новый? Или купить новый? А когда он окупится? А чем загрузить проц получше, чтобы не жалко было отдать за него деньги? А что мы будем хранить? А как часто обращаться к серверу? А вдруг в какой-то момент внезапно вырастет нагрузка, а мы не готовы?

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

А может лучше Hetzner? Или AWS? (Говорят что AWS такой дорогой потому что вы перекладываете свои сисадминские заботы на их сисадминов. И что тогда дороже -- самому настраивать Юниксы, тратить свое время и нервы, или пусть это делают специально обученные люди в AWS за зарплату?)

Если сервак один, то подобные задачки еще пока можно решать в уме. Если десяток разнотипных серваков под разные задачи -- это уже задачки как раз для вышеописанных инструментов.

В былые времена, когда мобильная связь еще была дорогая, приходилось мучительно выбирать тариф в зависимости от того, сколько вы юзаете sms-ок, инета, итд.

Помните, как в нулевых годах, споры, что лучше, AMD или Intel? AMD был вроде как дешевле, но к нему нужен был более дорогой кулер и БП. И что в итоге дешевле? Лушче? Как понять?

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

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

Ну и конечно же, планирование (туристических) маршрута -- долететь до города А, там пересесть на поезд, или быстро долететь сразу до точки назначения, но дороже?

С подобными задачками сталкиваются практически все люди, и часто.

MaxSAT, MaxSMT

Это пытаются делать и на основе SAT-солверов -- MaxSAT, MaxSMT. (Там применяют такие термины как поиск оптимума, оптимизация, задачи оптимизации.)

Возьмем известную проблему коммивояжера (TSP). Более приближенный к реальности пример -- надо насверлить дырок в печатной плате, это делает робот-рука с дрелью. Робот-рука обходит все дырки и сверлит. Чтобы минимизировать время и затраты электроэнергии, путь должен быть как можно короче.

Алгоритмы вроде генетических (GA), симуляции отжига (SA), hill climbing, найдут просто хорошее решение (локальный оптимум), но не обязательно лучшее (глобальный оптимум). Лучшее редко кому нужно на практике, достаточно просто хорошего. MaxSAT, MaxSMT может найти (гарантированно) лучший оптимум, но затратив куда больше времени. Потом пошли модификации -- MaxSAT-incomplete-anytime -- этот находит лучшее решение, что смог, пока его не прервали извне (послав ему Unix-сигнал). Так можно выделить ему N времени на работу.

Плановая экономика и войны

(Большую) страну вроде СССР можно представить в виде (очень) большого завода. И начать обсчитывать всё, вплоть до того, сколько нужно гаек, лопат, всякой фигни мелкой. Это называлось "плановая экономика". Вспоминаем термины: "центральное планирование", "госплан".

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

Были бонусы -- отсутствие инфляции. Олдовые люди поэтому помнят советские цены на всё подряд. (Даже я помню некоторые.) Цены расчитываются и потом фиксируются. Конечно, еще и для того чтобы облегчить прочие расчеты и предсказуемость всей системы.

Экономика может быстро перестроиться на военку -- в СССР ожидалось что рано или поздно третья мировая война начнется.

Экономика не должна ВЫДАТЬ столько-то оружия, она должна ВЫДАВАТЬ его длительное время. В итоге воюют не люди, не государства, не империи, а экономики. Отсюда пропаганда/философия/государственная идеология в духе "если наша экономика победит, значит она лучше/прогрессивнее [чем другая]".

В книгах по теор.веру попадается такая задачка -- садятся 2 человека и подкидуют монету. Выпадает орел, первый второму отдает рубль. Выпадает решка, второй первому отдает рубль. Всё честно, прозрачно, никого шулерства и кидняка. Вопрос -- кто выиграет? Этот вопрос даже не на математические знания а на сообразительность. Его можно задавать в играх вроде "что-где-когда".

А выиграет тот, у кого больше денег. Тот, у кого их меньше, в какой-то момент не сможет отыграться и выпадет из игры.

Кому интересна теория, гуглите про random walk.

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

И как тут не вспомнить "Эффект Матфея"?! 1, 2.

Так объясняют войны. Кто вложит больше ресурсов, тот и выиграет войну. Всё остальное уже второстепенно.

Точнее, не ВЛОЖИТ, а сможет ВКЛАДЫВАТЬ какое-то (может быть даже очень продолжительное) время.

У Р.Докинза есть книга с названием "Эгоисти́чный ген". Подразумевается, что этот кусок инфы (ген) -- это он всем управляет. Это он всё себе подчинил, как самый главный "эгоист". Он всё решает и управляет живыми существами. А ему нужно размножаться, копировать себя в пространстве, и больше ничего. (Тут так и напрашивается аналогия с компьютерными вирусами, "зловредами".) А оболочка живых существ/растений/бактерий в физическом мире -- это уже второстепенное. (В случае со "зловредами", это компы, серваки, инет.)

Так наверное борятся и экономики друг с другом. Это экономике надо расширяться, выживать, итд. Это они всё подчиняют себе.

Были и проблемы -- очень низкий выбор продукции вообще и ширпортреба в частности. Поэтому в любом городе быв.СССР, приходите на барахолку, а там (ностальгичные) предметы советского быта одни и те же. От Одессы до Владивостока. А всё почему? Наверное, маломощные компы -- вспомним какими они были вплоть до 1980-х. Это было слабое место в советской системе. Поэтому запад пытался бороться при помощи консюмеризма (сколько-то там сортов колбасы, например, а затем "колбасная эмиграция"). Запад в этом зашел настолько далеко (в т.ч. по инерции), что уже сами западные люди сомневаются, нужно ли всё это? И зачем? И не перебор ли это? А затем что это всё не для своих. А для чужих. Чтобы подразнить страны победнее. Т.е., как бы реклама.

А.Вассерман иногда говорит о том, что мощность компов будет достаточна для того чтобы что-то там (по его мнению) случилось. Я уже забыл что, наверное опять плановая экономика. И он упоминает метод Гаусса. Мне кажется, он ошибается, потому что метод Гаусса для вещественных чисел. А в плановой экономике мы все-таки оперируем целыми объектами (товарами), поэтому эта задача скорее из разряда Integer Linear Programming (ILP, целочисленное программирование). Что, опять же, близко к исследованию операций (OR). В СССР этим пытались заниматься, потому что это (сильно?) могло помочь экономике.

В свое время, в начале 1980-х, отметился даже Станислав Ашманов, отец того самого Игоря Ашманова: 1, 2.

(the post first published at 20240606, updated 20240608.)


List of my other blog posts.

Subscribe to my news feed,

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.