Main menu

Цена анархии (Price of Anarchy): количественная оценка эгоизма в транспортных сетях

Когда каждый водитель в мегаполисе выбирает свой маршрут на работу, он руководствуется исключительно эгоистичной целью — минимизировать собственное время в пути (состояние пользовательского равновесия Вардропа). Однако это индивидуальное поведение неизбежно приводит к перегрузке критических транспортных узлов, ухудшая общую ситуацию для всех. Если бы машинами управлял центральный суперкомпьютер (социальный оптимум), общее время всех людей в пробках было бы значительно меньше. В 1999 году математики Христос Пападимитриу и Элиас Куцупиас ввели в теорию игр и исследование операций концепцию «Цены анархии» (Price of Anarchy, PoA) — точную алгебраическую метрику, измеряющую финансовую и временную плату общества за отсутствие централизованного контроля.

Подробнее

Субмодульная оптимизация: закон убывающей отдачи в дискретной математике

В экономике хорошо известен закон убывающей предельной полезности: каждый следующий съеденный кусок торта приносит меньше удовольствия, чем предыдущий. В дискретной математике и исследовании операций аналогом этого закона является свойство субмодулярности. Оно описывает функции множеств, для которых добавление нового элемента к небольшому множеству дает больший прирост ценности, чем добавление того же элемента к более крупному множеству. Задачи субмодульной оптимизации возникают повсеместно: от оптимального размещения датчиков качества воды в городской водопроводе до выбора лидеров мнений для вирусного маркетинга в социальных сетях.

Подробнее

Формула Литтла: универсальный закон теории массового обслуживания и бережливого производства

Среди сотен сложных дифференциальных уравнений и марковских матриц, составляющих теорию массового обслуживания, существует один закон, поражающий своей математической простотой и абсолютной универсальностью. В 1961 году профессор MIT Джон Литтл строго доказал формулу, связывающую три главных параметра любой системы очередей: среднее количество заявок в системе (L), среднюю интенсивность входящего потока (лямбда) и среднее время нахождения заявки в системе (W). Уравнение L = лямбда * W стало фундаментом не только для телекоммуникационной инженерии, но и для философии бережливого производства (Lean Manufacturing) по всему миру.

Подробнее

Соц. сети