Использование MILP и Python для оптимальной бизнес-аналитики

Принятие решений — одно из самых напряженных занятий человека. Время от времени люди используют все формы фреймворков, такие как SWOT-анализ, Анализ MoSCoW, плюсы и минусы Минусы, которые я называю хеджированием, которые следует учитывать при принятии решений Бенджамином Франклином, матрица Эйзенхауэра, икигай, японский метод для выяснения того, движется ли ваша жизнь в правильном направлении, что примерно переводится как «причина для жизни», ЛОПАТА фреймворк, модифицированный подсчет Борда, фреймворк принятия решений RICE, модель Хоя-Тартера, фреймворк Cynefin, модель принятия решений Хартнетта, ориентированную на консенсус, модель принятия решений Врума-Йеттона, циклы НОРД, фреймворк STAR для решения конфликтов — и это лишь некоторые из них.

Эти вышеупомянутые фреймворки не исключают методов оптимизации; которые относительно включают поиск кратчайшего пути между двумя точками. Несколько дисциплин, включая инженерию, финансы, экономику, исследование операций и машинное обучение, могут выиграть от использования методов оптимизации. MILP (смешанное целочисленное линейное программирование) — это один из решателей, в котором реализованы методы оптимизации. Следовательно, мы сосредоточимся на его использовании для решения проблемы в этой статье, в основном потому, что MILP — это метод математической оптимизации, который сочетает в себе «линейное программирование» и «целочисленное программирование» для решения задач как с непрерывными, так и с дискретными переменными.

В этой статье мы рассмотрим проблему планирования медсестер (NSP), а ниже приведены проблемы, которые нам необходимо решить:

:::подсказка Инфузионный центр в больнице UMC предоставляет услуги по введению (лекарств) для различных видов лечения, включая химиотерапию рака, иммунотерапию, лечение ревматоидного артрита, ферротерапию и переливание крови.

Чтобы обеспечить надежный поток пациентов в течение дня, т. е. короткое время ожидания для пациентов и небольшую сверхурочную работу для медсестер, центру требуется «по крайней мере» (это можно рассматривать как «больше или равно») следующего количества медсестер, чтобы работать в центре в течение всей недели: Понедельник = 17 Вторник = 13 Среда = 15 Четверг = 19 Пятница = 14 Суббота = 16 Воскресенье = 11. Если медсестра работает полный рабочий день, она должна работать пять дней подряд затем два выходных дня. Медсестра, работающая неполный рабочий день, должна работать три дня подряд, а затем четыре выходных дня.

Стоимость найма медсестер на полный и неполный рабочий день зависит от дня недели: для будних дней полный рабочий день = 250 евро/день и неполный рабочий день = 150 евро/день. По субботам полный рабочий день = 315 евро в день и неполный рабочий день = 185 евро в день. По воскресеньям полный рабочий день = 375 евро в день и неполный рабочий день = 225 евро в день.

Разница в оплате труда заключается в том, что медсестры, работающие полный рабочий день, специализируются на обширном обучении и имеют постоянные контракты (больше затрат), тогда как медсестры, работающие неполный рабочий день, являются медсестрами общего профиля (например, не специализирующимися на химиотерапии) с временными контрактами. Однако, согласно трудовому законодательству, неполный рабочий день может быть занят не более 25 % рабочего времени.

Сформулируйте и решите математическую программу (MILP), чтобы ответить на следующие вопросы:

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

2. Какова минимальная общая стоимость в неделю?

:::

Наша цель в этой задаче — найти оптимальные значения переменных, которые удовлетворяют набору линейных ограничений и целевой функции, которую необходимо максимизировать или минимизировать. Кроме того, я хочу подчеркнуть в пунктах вопроса, что медсестры, работающие полный рабочий день, «специализируются с обширной подготовкой». что они имеют дело с больничными пациентами, и приоритет для этого не будет плохой идеей, даже если мы увеличим медсестер, занятых неполный рабочий день. Самое главное, вы не хотите серьезных побочных эффектов в вашей больнице.

Мы решим этот вопрос/проблему с модулем Gurobi Optimizer Python. Но прежде чем ее решать, давайте поговорим о Гуроби.

Что такое Гуроби?

Gurobi — это стандартное решение для оптимизации компьютерного программирования. Он предлагает надежную и адаптируемую основу для решения широкого круга задач математической оптимизации, в том числе связанных с линейным программированием (LP), смешанно-целочисленным программированием (MIP), квадратичным программированием (QP), коническим программированием второго порядка (SOCP). и многое другое. С приложениями, варьирующимися от управления цепочками поставок и логистики до оптимизации портфеля и машинного обучения, Gurobi широко используется в бизнесе, академических кругах и исследованиях. Python, C++, Java, MATLAB и R — это лишь некоторые из языков программирования, для которых Gurobi предоставляет интерфейсы.

Мы собираемся использовать следующие функции в модуле Gurobi Python Optimization:

:::информация GRBModel.AddVars(количество, тип)

Это позволяет добавить в модель новую переменную решения.

Аргумент позволяет указать «количество объектов переменных для добавления» и «тип переменной для новых переменных, в котором мы будем использовать INTEGER в нашем собственном случае, поскольку мы имеем дело с количеством дней, запланированных для медсестер».

:::

:::информация GRBModel.setObjective(expr, sense=None)

Эта функция позволяет установить цель модели равной линейному или квадратичному выражению.

Аргумент позволяет указать выражение, а также необязательный смысл оптимизации (например, GRB.MINIMIZE для минимизации, GRB.MAXIMIZE для максимизации).

Если аргумент смысла оптимизации не указан, для определения смысла используется значение атрибута ModelSense.

:::

:::информация GRBModel.AddConstr(lhsExpr, sense, rhsExpr, name)

Это позволяет добавить в модель одно линейное ограничение.

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

:::

:::информация Model.optimize(callback=None)

Это принимает атрибут класса обратного вызова.

Обратный вызов — это пользовательская функция, которая периодически вызывается оптимизатором Gurobi, чтобы пользователь мог запросить или изменить состояние оптимизации. Точнее, если вы передаете функцию, которая принимает два аргумента (модель и где) в качестве аргумента в Model.optimize() или Model.computeIIS(), ваша функция будет вызываться во время оптимизации.

Мы должны использовать метод optimize(), чтобы найти наилучший результат, который удовлетворяет требованиям и минимизирует или максимизирует целевую функцию после установления переменных, ограничений и целевой функции.

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

Метод optimize() создает подходящее сообщение с описанием характера проблемы, если задача оптимизации является «неразрешимой» или «невыполнимой».

:::

Установив в мельчайших подробностях нашу сильную сторону, давайте приступим к решению вопроса и выполним следующие шаги:

1. Установите программное обеспечение Gurobi Optimizer и получите лицензию, если вы еще этого не сделали.

<код>питон python -m pip установить gurobipy==10.0.1

2. Импортируйте модуль Gurobi Python и инициализируйте среду Gurobi.

<код>питон из импорта gurobipy *

3. Укажите дни недели, указанные в вопросе.

<код>питон days = ['Пн', 'Вт', 'Ср', 'Чт', 'Пт', 'Сб', 'Вс']

4. Определите спрос на медсестер в каждый день недели как заданный.

<код>питон спрос = {'Пн': 17, 'Вт': 13, 'Ср': 15, «Чт»: 19, «Пт»: 14, «Сб»: 16, «Вс»: 11

5. Определите стоимость найма медсестер на полный рабочий день в каждый день недели, как указано.

<код>питон cost_fulltime = {'Пн': 250, 'Вт': 250, 'Ср': 250, «Чт»: 250, «Пт»: 250, «Сб»: 315, «Вс»: 375

6. Определите стоимость найма медсестер на неполный рабочий день в каждый день недели

<код>питон cost_parttime = {'Пн': 150, 'Вт': 150, 'Ср': 150, «Чт»: 150, «Пт»: 150, «Сб»: 185, «Вс»: 225

7. Определите максимальную долю времени, которую можно посвятить частичной занятости. Вопрос говорит о 25%, что равно 0,25

<код>питон max_parttime = 0,25

8. Определить количество дней подряд, отработанных медсестрами, работающими полный и неполный рабочий день

<код>питон fulltime_days_on = 5 parttime_days_on = 3

9. Создайте модель Гуроби

<код>питон модель = Модель()

1. Определите переменные решения

   <код>питон fulltime = model.addVars(дни, vtype=GRB.INTEGER, name="fulltime") parttime = model.addVars(days, vtype=GRB.INTEGER, name="parttime")

   11. Определите целевую функцию для минимизации общих затрат на медсестер

   <код>питон model.setObjective (сумма ( cost_fulltime[d] * fulltime[d] + cost_parttime[d] * parttime[d] для d в днях))

   Для функций setObjective() мы не указали минимизацию или максимизацию. Не предоставив его, Gurobi по умолчанию использует ModelSense, что, как предполагается, мы минимизируем. Наше выражение действительно представляет целевую функцию минимизации.

   Минимизация и максимизация — два основных типа целей оптимизации.

   Поиск минимального значения функции или цели или точки, в которой она имеет наименьшее возможное значение, называется минимизацией.

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

   Например, в линейном программировании мы часто стремимся максимизировать или уменьшить целевую функцию, принимая во внимание определенные ограничения. Количество, которое мы хотим максимизировать или минимизировать, представлено целевой функцией, а ограничения — ограничениями или границами, наложенными на задачу.

   12. Добавьте ограничения, чтобы обеспечить удовлетворение спроса на медсестер каждый день недели

   <код>питон для d в днях: model.addConstr(полный рабочий день[d] + неполный рабочий день[d] >= спрос[d])

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

   <код>питон model.addConstr(sum(parttime[d] для d в днях) <= max_parttime * sum(fulltime[d] + parttime[d] для d в днях))

1. Добавьте ограничения, чтобы медсестры, работающие полный рабочий день, работали пять дней подряд, а затем два выходных дня.

   <код>питон для i в диапазоне (длина (дней) - fulltime_days_on + 1): model.addConstr (сумма (полный рабочий день [дней [j]] для j в диапазоне (i, i + fulltime_days_on)) >= 5)

   15. Добавьте ограничения, чтобы медсестры, работающие неполный рабочий день, работали три дня подряд, а затем четыре выходных дня.

   <код>питон для i в диапазоне (длина (дни) - parttime_days_on + 1): model.addConstr (сумма (неполный рабочий день [дней [j]] для j в диапазоне (i, i + parttime_days_on)) >= 3)

   16. Теперь решим модель

   <код>питон model.optimize()

   17. Так как мы оптимизировали нашу модель. Давайте распечатаем результат оптимизации, чтобы ответить на наши подвопросы.

   ```питон print("Оптимальное решение:") для d в днях: print("{}: Full-time={}, Part-time={}".format(d, int(fulltime[d].x), int(parttime[d].x)))

   print("Общая стоимость: €{}".format(int(model.objVal))) ```

   Вывод

   В моей локальной системе я получил следующее решение:

   ``ямл Ограниченная лицензия — только для непроизводственного использования — истекает 28 октября 2024 г. Оптимизатор Gurobi версии 10.0.1, сборка v10.0.1rc0 (mac64[x86])

   Модель ЦП: ЦП Intel(R) Core(TM) i7-4558U с тактовой частотой 2,80 ГГц Количество потоков: 2 физических ядра, 4 логических процессора, использование до 4 потоков

   Оптимизация модели с 16 строками, 14 столбцами и 58 ненулевыми значениями. Отпечаток модели: 0xbd18a424 Типы переменных: 0 непрерывных, 14 целых (0 двоичных) Статистика коэффициентов: Диапазон матрицы [2e-01, 1e+00] Целевой диапазон [2e+02, 4e+02] Диапазон границ [0e+00, 0e+00] Диапазон RHS [3e+00, 2e+01] Найдено эвристическое решение: цель 27615.000000 Предварительное время: 0,00 с Presolved: 16 строк, 14 столбцов, 58 ненулевых значений. Типы переменных: 0 непрерывных, 14 целых (0 двоичных) Найдено эвристическое решение: цель 26835.000000

   Корневая релаксация: цель 2.512250e+04, 14 итераций, 0,00 секунд (0,00 рабочих единиц)

   Узлы | Текущий узел | Границы цели | Работа
   
   Расширить Необъявить | IntInf глубины объекта | Действующий BestBd Gap | Это/время узла
    0 0 25122.5000 0 2 26835.0000 25122.5000 6,38% - 0s
   
   H 0 0 25155.000000 25122.5000 0,13% - 0 с
   Изучен 1 узел (14 симплексных итераций) за 0,01 секунды (0,00 рабочих единиц).
   Количество потоков: 4 (из 4 доступных процессоров)
   Количество решений 3: 25155 26835 27615 
   Оптимальное решение найдено (допуск 1.00e-04)
   Лучшая цель 2,515500000000e+04, лучшая граница 2,515500000000e+04, зазор 0,0000%
   Оптимальное решение:
   Пн: полный рабочий день = 17, неполный рабочий день = 0
   Вт: полный рабочий день = 13, неполный рабочий день = 0
   Ср.: полный рабочий день=12, неполный рабочий день=3
   Чт: полный рабочий день=19, неполный рабочий день=0
   Пт: полный рабочий день=14, неполный рабочий день=0
   Сб: полный рабочий день=4, неполный рабочий день=12
   Вс: полный рабочий день = 0, неполный рабочий день = 11
   Общая стоимость:
   €25155
   ```
   
   Чтобы получить общее общее количество медсестер, занятых полный и неполный рабочий день, указанное в вопросе 1**, мы просто суммируем количество медсестер, которые должны работать каждый день неделя. Например, оптимальное решение показывает, что в понедельник должны быть запланированы на работу 17 медсестер, занятых полный рабочий день, и 0 медсестер, занятых неполный рабочий день, поэтому общее количество медсестер в этот день составляет 17 + 0 = 17.
   
   Если просуммировать количество медсестер, которые должны работать в каждый день недели, мы получим следующее:
   
   <код>ямл
   Штатные медсестры: 17 + 13 + 12 + 19 + 14 + 4 + 0 = 79
   Медсестры, занятые неполный рабочий день: 0 + 0 + 3 + 0 + 0 + 12 + 11 = 26
   
   Что касается вопроса 2; общая стоимость €25 155 — это минимальная стоимость, полученная в результате решения задачи оптимизации. Это представляет собой общие затраты, которые понесет инфузионный центр при соблюдении всех требований постановки задачи и использовании оптимального количества медсестер, работающих полный и неполный рабочий день.
   
   В заключение мы видим, что наше решение осуществимо. Тем не менее, над этим все же можно поработать таким образом, чтобы оптимизация уменьшила количество штатных медсестер, поскольку они получают высокую заработную плату. Но мы должны спросить себя, можем ли мы отказаться от преимуществ последовательности обучения, которые есть у штатных медсестер. Если это так, то мы можем найти решение, которое будет более выгодным для медсестер, работающих неполный рабочий день, и нескольких медсестер, работающих полный рабочий день, со значительной суммой затрат ниже нашего результата в 25 155 евро, даже при сохранении 0,25% рабочей нагрузки и 3-дневный рабочий график с 4-мя выходными.
   

Как вы представляете свой отчет в качестве бизнес-аналитика?

Вот как я это сделаю ниже

:::подсказка Отчет о решении для MILP:

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

Идеальный ответ был найден путем оптимизации модели MILP. Идеальная цель:

25 155 евро, а идеальная граница – 25 155 евро с нулевым разрывом. Это показывает, что мы вполне уверены, что нашли наилучший вариант.

Исходя из идеального решения, мы можем сделать вывод, что уровни персонала для каждого дня недели следующие:

* В понедельник работает 17 смен с полной занятостью медсестер; уход на неполный рабочий день в этот день невозможен. * Во вторник есть 13 смен медсестер с полной занятостью, но не смен медсестер с частичной занятостью. * Медсестры, работающие неполный рабочий день, работают по средам в 3 смены по сравнению с 12 сменами медсестер, работающих полный рабочий день. * В четверг есть 19 смен медсестер с полной занятостью, но не смен медсестер с частичной занятостью. * В пятницу медсестры на неполный рабочий день не работают; вместо этого штатные медсестры работают в 14 смен. * Медсестры на полный рабочий день работают в 4 смены по субботам, а медсестры на неполный рабочий день работают в 12 смен. * По воскресеньям нет дежурных медсестер, но медсестры, работающие неполный рабочий день, работают в 11 смен.

Эта стратегия сводит к минимуму общие расходы на уход, удовлетворяя при этом минимальные потребности в персонале на каждый день недели. Этот идеальный вариант обойдется вам в 25 155 евро на уход за больными.

В целом, это решение предлагает практичный и экономичный подход к увеличению численности персонала в больницах.

:::

Ведущий образ создан со стабильной диффузией.