Смешанно-целочисленное программирование: руководство по принятию вычислительных решений

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

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

Алгоритмы исследования операций

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

Алгоритмы линейного программирования

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

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

В нашем очень простом примере мы видим, что оптимальный результат равен 5, где a = 2 и b = 3. Хотя это довольно тривиальный пример, вы, вероятно, можете представить себе модель линейного программирования, в которой используются тысячи переменных и сотни ограничений. .

Хорошим примером может быть проблема инвестиционного портфеля, где вы можете получить что-то вроде следующего в псевдокоде:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

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

Алгоритмы целочисленного программирования

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

Одной из таких проблем является задача о рюкзаке, когда нам дается набор предметов с заданными значениями и весами, и нас просят найти комбинацию предметов с наивысшей ценностью, которую мы можем поместить в наш рюкзак. Модель линейного программирования не сможет решить эту проблему, потому что невозможно выразить мысль о том, что вы можете либо положить предмет в свой рюкзак, либо нет, но вы не можете положить часть предмета в свой рюкзак — каждая переменная является непрерывной. Переменная!

Пример задачи о рюкзаке может иметь следующие параметры:

И модель MIP будет выглядеть так:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

Оптимальным решением в этом случае является a=0, b=1, c=0, d=1, при этом значение общего элемента равно 17.

Задача, которую мы сегодня решим, также потребует целочисленного программирования, поскольку работник на заводе может быть либо назначен на смену, либо нет — для простоты вы не можете назначить работника на 2/3 смены на этом заводе.

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

Пример проблемы: планирование

описание проблемы

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

Предположим, у нас есть пять смен со следующими потребностями в персонале:

И, предположим, у нас есть следующие работники:

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

Наши инструменты

Для сегодняшней задачи мы будем использовать часть программного обеспечения с открытым исходным кодом под названием CBC. Мы будем взаимодействовать с этим программным обеспечением, используя PuLP, популярную библиотеку моделирования исследований операций для Python. Вы можете найти информацию об этом здесь.

PuLP позволяет нам создавать модели MIP в стиле Python и хорошо интегрируется с существующим кодом Python. Это очень полезно, так как некоторые из самых популярных инструментов обработки и анализа данных написаны на Python, а большинство коммерческих систем исследования операций требуют обширной обработки данных до и после оптимизации.

Чтобы продемонстрировать простоту и элегантность PuLP, вот задача о рюкзаке, которая была решена ранее в PuLP:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Запустите это, и вы должны получить вывод:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Теперь о нашей проблеме планирования!

Кодирование нашего решения

Кодирование нашего решения довольно простое. Во-первых, мы хотим определить наши данные:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

Далее мы хотим определить модель:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

А теперь мы просто просим его решить и распечатать результаты!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

После запуска кода вы должны увидеть следующие результаты:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Немного усложните задачу: дополнительные ограничения

Несмотря на то, что предыдущая модель была интересной и полезной, она не в полной мере демонстрирует возможности смешанно-целочисленного программирования. Мы также могли бы легко написать цикл for для поиска x самых дешевых рабочих для каждой смены, где x — количество рабочих, необходимых для смены. Чтобы продемонстрировать, как можно использовать MIP для решения проблемы, которую было бы сложно решить императивным способом, давайте посмотрим, что произойдет, если мы добавим несколько дополнительных ограничений.

Дополнительные ограничения

Предположим, что в связи с новым трудовым законодательством ни один рабочий не может быть назначен более чем в 2 смены. Чтобы учесть увеличение объема работы, мы наняли Дотракийскую кадровую группу, которая предоставит до 10 дотракийских рабочих в каждую смену по ставке 40 долларов за смену.

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

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

Решение

Однако со смешанным целочисленным программированием все намного проще. Нам просто нужно изменить наш код следующим образом:

Определите список банов и некоторые ограничения:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Заполните переменные для реализации ограничений запрета и максимальной смены:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Добавьте переменные дотракийцев:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Нам также понадобится слегка модифицированный цикл для вычисления требований сдвига и запрета:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

И, наконец, для печати результатов:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

И мы должны быть готовы идти. Запустите код, и вы должны увидеть вывод, как показано ниже:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

И вот он, результат, который соблюдает список запрещённых рабочих, соблюдает трудовые нормы и разумно использует дотракийских рабочих.

Заключение

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

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

Вы можете найти весь код, относящийся к этой статье, на GitHub. Если вы хотите обсудить больше, поделитесь своими комментариями ниже!