Математическое моделирование, оптимизация, исследование операций, программирование в ограничениях … Продолжим двигаться в этом направлении.
Статья выполнена в рамках проекта “Make optimization simple”, который погружает в область бизнес задач с точки зрения математического моделирования и оптимизации. Посредством готовых библиотек демонстрируются примеры решения такого рода задач.
В этой статье разберем одну из таких постановок. На примере задачи планирования сменного графика сотрудников сети стоматологических клиник пройдем этапы: от формулирования бизнес ограничений до получения готового решения. Для моделирования и поиска решения будем использовать инструменты Python и библиотеку OR-Tools.
Описание задачи
Одной из распространенных задач планирования расписаний является распределение сотрудников по сменам. В качестве примера рассмотрим задачу планирования графика работы сотрудников в сети стоматологических клиник.
В задаче сделаем акцент на ведущих стоматологах сети как наиболее ценных и редких кадрах. Такого рода специалисты работают в нескольких клиниках сети одновременно. Распределение ведущих специалистов позволяет клиникам предлагать широкий спектр специалистов, реализующих услуги «повышенного» качества. При этом в штате можно иметь небольшое количество высококвалифицированных специалистов.
Тихонов Н. А. — Основы математического моделирования — Типы математических моделей (Лекция 1)
Перейдем непосредственно к моделируемой проблеме. Рассмотрим задачу распределения ограниченного количества ведущих стоматологов в сети клиник. С целью предоставления клиентам выбора из нескольких ведущих экспертов-стоматологов к каждой из клиник необходимо привязать несколько ведущих сотрудников. Один эксперт может работать в нескольких клиниках в разные смены.
В каждой клинике предусмотрен кабинет, в котором работают эксперты. Кроме того, законодательством регламентированы ограничения по режиму труда и отдыху рабочих — два выходных дня в неделю.
Резюме: задача состоит в том, чтобы для каждого ведущего стоматолога назначить сменный график и место работы.
Постановка задачи
Сеть из 3 стоматологических клиник имеет в своем ассортименте 5 экспертов. Все клиники сети работают без выходных по одной смене каждый день (8 часов). График работы сотрудников должен иметь недельный цикл (горизонт планирования 7 дней). Необходимо распределить сотрудников по клиникам и сменам при следующих ограничениях:
- Каждый эксперт может работать только в одной клинике в смену;
- В каждой клинике в любой из дней недели должен работать ровно один эксперт (одно помещение под эксперта);
- Эксперты работают 5 смен в неделю (режим труда и отдыха);
- В каждой клинике в течение недели должны работать не менее 2 разных экспертов (имитация выбора для клиента).
Построение модели и ее python реализация
Рассматриваемая нами задача состоит из набора ограничений, как и задача планирования расписаний в целом, ее можно представить в виде задачи удовлетворения ограничений (ЗУО). Элементы «языка ЗУО»:
Математическая модель задачи. Как составить. Математическая постановка. Исследование операций.
- набор решающих переменных;
- допустимые значения этих переменных;
- список ограничений, накладываемых на переменные;
- целевая функция.
Представление задачи в формате ЗУО не дает ее решение, а только предлагает вариант формализации в некоторой математической форме. Одним из вариантов для ее решения является парадигма программирование в ограничениях (Constraint Programming, CP). Она представляет собой набор методов и алгоритмов для решения ЗУО.
Конечно, уже разработаны и упакованы библиотеки для решения задач удовлетворения ограничений, в которых реализованы алгоритмы программирования в ограничениях, такие пакеты называются solver или cp-solver.
Из числа open source решений наиболее эффективным является cp-sat solver ORtools. Библиотека также предоставляет функционал для описания ЗУО. На примере данного solver`а будем моделировать и решать задачу планирования расписания смен ведущих стоматологов сети клиник.
Установить библиотеку ORtools в среду python можно с помощью pip:
pip install ortools
Индексы и входные данные
В задаче фигурируют три объекта: клиника, эксперт и смена. Введем для них следующие обозначения:
— индекс и список клиник, клиника содержится во множестве ;
— индекс и список экспертов, эксперт содержится во множестве ;
— индекс и дни недели, день недели содержится во множестве .
Запишем эти множества в виде списков Python:
# Инициализируем множества/списки K = [«Klinika1», «Klinika2», «Klinika3»] # Список клиник в сети E = [«Expert1», «Expert2», «Expert3», «Expert4», «Expert5»] # Список экспертов T = [«Smena» + str(t) for t in range(1, 8)] # Список смен trudovoy_kodex = 5 # Константа, ограничение кол-ва рабочих смен у эксперта min_experts_per_clinic = 2 # Минимальное кол-во экспертов, привязанных к клинике
Импорт библиотеки и инициализация модели
ORtools содержит в себе различные обертки для различных классов задач, в том числе для ЗУО. Поэтому импорт нужной нам части находится на четвертом уровне: from ortools.sat.python import cp_model . Переменные, ограничения и целевая функция инициализируются в экземпляре класса CpModel() . Объект модели может содержать только описание одной задачи, но никто не мешает инициализировать несколько экземпляров модели.
# Импорт «редактора» для записи ЗУО from ortools.sat.python import cp_model import pandas as pd # Инициализация модели model = cp_model.CpModel()
Инициализация переменных
Прежде чем перейти к формулированию ограничений, определим набор решающих переменных. В задаче фигурируют три типа объектов/параметров: эксперт, клиника и смена. Все возможные комбинации этих объектов клиника-эксперт-смена представляют собой потенциальные варианты работы экспертов.
Каждую такую комбинацию свяжем с переменной , которая принимает значение 1, если эксперт работает в смену в клинике , 0 — в противном случае. Таким образом, у нас есть 3*5*7 = 105 переменных, соответствующих всем комбинациям.
Например: если переменная для комбинации Klinika1-Expert1-Smena1 равна 1, следовательно, Эксперт 1 должен работать в Клинике 1 в Смену 1. Если значение переменной равно 0, то Эксперт 1 не работает в Клинике 1 в Смену 1.
Кроме допустимых комбинаций введем вспомогательные переменные-индикаторы клиника-эксперт. Значение переменной равное 1, будет означать, что эксперт работает, по крайней мере, одну смену в клинике , 0 — эксперт не работает в клинике .
Например: если переменная для комбинации Klinika1-Expert1 равна 1, следовательно, Эксперт 1 должен работать в Клинике 1 хотя бы одну смену. Если значение переменной равно 0, то Эксперт 1 не работает в Клинике 1 вообще.
Добавление переменных в CpModel возможно через метод NewBoolVar , если переменная бинарная (может принимать значения 0 или 1) или с помощью метода NewIntVar для целочисленных переменных. Переменные, соответствующие допустимым комбинациям, будем складировать в словарь X , переменные-индикаторы — в Y .
Важно! Использование cp-sat solver’а возможно только для решения задач с целочисленными переменными.
# Инициализация переменных комбинации X = <> # Словарь для хранения ссылок на переменные for k in K: for e in E: for t in T: var_name = f»x___» # Название переменной X[k, e, t] = model.NewBoolVar(name=var_name) # Инициализация переменных-индикаторов Y = <> # Словарь для хранения ссылок на переменные-индикаторы for k in K: for e in E: var_name = f»y__» # Название переменной-индикатора Y[k, e] = model.NewBoolVar(name=var_name)
Ограничение: один эксперт в каждой клинике каждый день
Всего в нашем распоряжении пять экспертов и три клиники. Ровно один из этих пяти экспертов должен работать в Клинике 1 в Смену 1. Это условие можно записать следующим образом:
Аналогичные ограничения создаем для всех остальных пар клиника-смена. В связи с большим количеством ограничений (3*7=21 шт.), текстовую запись всех ограничений опустим.
Более лаконично ограничения можно записать в математической форме с использованием знака суммы и символа для каждого элемента множества («Для любого. »).
Добавление ограничений в CpModel возможно через метод Add , но наше ограничение подпадает под определенный шаблон ограничений AddExactlyOne (ровно одна переменная равняется 1). Использование таких шаблонов позволяет алгоритмам автоматически подстраиваться под ограничения и работать эффективнее. Добавим ограничения в модель.
# Ограничение: один эксперт в каждой клинике каждый день for k in K: # для каждой клиники for t in T: # для каждого дня недели # Список экспертов для работы в клинике «k» в смену «t» lst_vars = [X[k, e, t] for e in E] # Добавление ограничений в модель: ровно один эксперт в клинике в смену model.AddExactlyOne(lst_vars) # model.Add(sum(lst_vars) == 1) # Альтернативный способ добавления ограничения
Ограничение: эксперт работает не более чем в одной клинике в смену
Исходя из физических ограничений, сотрудник не может находиться одновременно в двух разных местах. Данное ограничение очевидно, но в модель его необходимо передать совместно с другими ограничениями.
В сети три клиники, в одной из которых может работать Эксперт 1 в Смену 1. Кроме того, Эксперт 1 может вообще не работать в Смену 1 — выходной. Это условие с помощью введенных переменных можно записать как
Аналогичные ограничения создаем для всех остальных пар эксперт-смена. В связи с большим количеством ограничений (5*7=35 шт.) текстовую запись всех ограничений снова опустим. Лаконичная запись в виде формулы:
Данное ограничение является шаблонным, задается посредством метода AddAtMostOne (не более чем одна переменная равна 1).
# Ограничение: Каждый эксперт может работать только в одной клинике в смену. for e in E: # для каждого эксперта for t in T: # для каждой смены # Список клиник для работы эксперта «e» в смену «t» lst_vars = [X[k, e, t] for k in K] # Добавление ограничений в модель: у эксперта не более одной клиники в смену model.AddAtMostOne(lst_vars) # model.Add(sum(lst_vars)
Ограничение: связь переменных-комбинаций и переменных-индикаторов
Презентация на тему Математическое моделирование на компьютере
Компьютерное моделирование – информационное моделирование с помощью компьютера. Математическая модель – описание объекта моделирования на языке математики Компьютерная математическая модель – программа, реализующая расчеты состояния моделируемой системы по ее математической
- Главная
- Разное
- Математическое моделирование на компьютере
Слайды и текст этой презентации
Слайд 1 Математическое моделирование на компьютере
Слайд 2 Компьютерное моделирование – информационное моделирование
с помощью компьютера.
Математическая модель – описание
объекта моделирования на языке математики
Компьютерная математическая модель
– программа, реализующая расчеты состояния моделируемой системы по ее математической модели
Слайд 3 Виды математических моделей:
По отраслям наук (математические модели
в физике, биологии, социологии)
По применяемому мат. аппарату (основаны на
применении уравнений различных классов, статистических методов, алгебраических структур и преобразований)
По
основной функции
1) дескриптивные модели
2) оптимизационные модели
3) многокритериальные модели
Слайд 4
Слайд 5 Этапы разработки мат. модели
I этап: определение целей моделирования
Цели:
понимание, управление, прогнозирование
II этап: составление списка параметров модели, подразделение
их на входные и выходные, расстановка по уровню значимости.
разделение входных параметров по степени важности влияния их изменений на выходные параметры, выбор первоочередных выходных параметров
Слайд 6 Этапы разработки мат. модели
III этап: математическая формализация
между входными и выходными параметрами
IV этап: реализация математической модели
Нахождение
способа вычисления неизвестных.
Аналитические методы позволяют выразить неизвестные величины через входные
параметры в явном функциональном виде.
Численные методы применяются, когда не удается получить аналитическое решение
Слайд 7 Компьютерная реализация моделирования
сопровождается разработкой алгоритма и составлением
программы для компьютера.
Пакет прикладных программ(ППП) –
специальным образом организованные
программные комплексы, рассчитанные на применение в определенной предметной области и
дополненные соответствующей технической документацией.
Слайд 8 Для графической обработки результатов моделирования используются специальные графические
средства – пакеты научной и инженерной графики, реализующие в
том числе и анимацию, и трехмерное(3D) представление.
Программирование на универсальных языках
является самым универсальным и «гибким» способом реализации мат. моделирования.
Программирование заключается в построении алгоритма, составлении программы и отладки программы.
Затем следует вычислительный эксперимент.
Анализ адекватности модели – сложная проблема, требующая участия прежде всего постановщика задачи и специалистов.
Источник: mypreza.com