Смешанное целочисленное программирование (MIP) – это мощный метод оптимизации, используемый для решения сложных задач принятия решений, связанных с комбинацией непрерывных и дискретных переменных.
Он находит применение в различных областях, таких как планирование производства, управление цепочками поставок, распределение ресурсов и планирование.
В этой статье мы рассмотрим, как формулировать и решать задачи смешанного целочисленного программирования с использованием Python. Мы будем использовать библиотеку PuLP, популярный инструмент моделирования линейного программирования с открытым исходным кодом, чтобы продемонстрировать реализацию.
Алгоритм линейного программирования:
Линейное программирование — это метод исследования операций, используемый для определения оптимального решения в математической модели, где цель и ограничения выражаются в виде системы линейных уравнений.
- Симплексный алгоритм. Симплексный алгоритм является одним из наиболее известных и широко используемых алгоритмов LP. Он систематически перемещается от одной вершины допустимой области к другой вдоль ребер, оптимизируя целевую функцию на каждом шаге, пока не будет достигнуто оптимальное решение. Он эффективен для решения задач LP с умеренным числом переменных и ограничений.
- Методы внутренних точек. Методы внутренних точек, также известные как барьерные методы, представляют собой алгоритмы итерационной оптимизации, которые исследуют внутреннюю часть допустимой области, а не вершины. Они используют барьерные функции, чтобы гарантировать, что итерации остаются в допустимой области. Методы внутренних точек известны своей эффективностью при решении крупномасштабных задач ЛП.
- Алгоритм двойного симплекса: Алгоритм двойного симплекса представляет собой вариант алгоритма симплекса, который работает с двойной проблемой LP. Он начинается с начального допустимого решения и итеративно улучшает его, пока не будет получено оптимальное решение. Этот алгоритм особенно полезен, когда количество ограничений велико по сравнению с количеством переменных.
- Методы секущих плоскостей. Методы секущих плоскостей направлены на решение проблем LP путем итеративного добавления дополнительных ограничений, известных как секущие плоскости, для сужения допустимой области. Эти секущие плоскости получаются из двойственной задачи задачи ЛП или путем создания действительных неравенств. Методы секущих плоскостей могут быть эффективны для решения задач ЛП с большим количеством переменных и ограничений.
- Алгоритм эллипсоида: Алгоритм эллипсоида — это теоретический алгоритм LP, который использует метод эллипсоида для итеративного сокращения эллипсоида вокруг оптимального решения, пока не будет достигнута желаемая точность. Хотя алгоритм Ellipsoid обладает хорошими теоретическими свойствами, на практике он не так эффективен по сравнению с другими алгоритмами LP.
- Методы секущей плоскости внутренней точки: этот класс алгоритмов сочетает в себе преимущества методов внутренней точки и методов секущей плоскости. Они используют методы внутренних точек для получения приближенного решения, а затем используют секущие плоскости для итеративного улучшения решения.
Эти алгоритмы LP различаются по своему подходу, сложности и эффективности для разных экземпляров проблемы. Выбор алгоритма зависит от конкретных характеристик задачи LP, таких как количество переменных и ограничений, разреженность задачи и желаемая точность.
Пример модели линейного программирования можно сформулировать следующим образом:
Let's consider a different example of a linear programming model: Maximize 5x + 3y (objective function) Subject to the following constraints: 2x + y <= 10 x + 3y <= 12 x, y >= 0
В этом примере мы стремимся максимизировать целевую функцию 5x + 3y, придерживаясь заданных ограничений. Первое ограничение представляет собой ограничение на комбинированные значения x и y, умноженные на 2, которые не должны превышать 10. Второе ограничение накладывает ограничение на сумму x и 3, умноженных на y, которая не должна превышать 12. Наконец, не- Ограничения отрицательности указывают, что и x, и y должны быть больше или равны нулю.
Инвестиционный портфель — отличный пример, который может быть сложно решить вручную методом проб и ошибок.
Алгоритм целочисленного программирования:
Алгоритмы целочисленного программирования – это алгоритмы оптимизации, предназначенные для решения задач целочисленного программирования (IP), в которых переменные решения должны принимать целые значения. Эти алгоритмы специально разработаны для обработки дополнительной сложности, создаваемой целочисленными переменными, по сравнению с задачами линейного программирования (ЛП), где переменные могут принимать любые действительные значения.
Существует несколько ключевых алгоритмов целочисленного программирования, которые были разработаны на протяжении многих лет. Вот некоторые из часто используемых:
- Ветвь и граница: Ветвь и граница — это широко используемый алгоритм для решения задач целочисленного программирования. Он систематически исследует пространство решений, разбивая его на более мелкие подзадачи, ограничивая оптимальное решение внутри каждой подзадачи и разветвляясь на многообещающие области пространства решений, пока не будет найдено оптимальное целочисленное решение.
- Плоскость сечения: Метод плоскости сечения улучшает LP-релаксацию задач IP за счет итеративного добавления действительных неравенств, известных как плоскости сечения, для ужесточения решения LP-релаксации до тех пор, пока оно не станет целочисленным решением. Этот алгоритм помогает эффективно сократить пространство поиска.
- Ветвь и разрез: Ветвь и разрез — это расширение алгоритма «Ветвь и граница», которое включает в себя метод секущей плоскости. Он сочетает в себе преимущества обоих алгоритмов за счет использования секущих плоскостей для усиления LP-релаксаций в каждом узле дерева ветвей и границ, что приводит к более быстрой сходимости к оптимальному целочисленному решению.
- Branch and Price: Branch and Price — это алгоритм, подходящий для решения задач ИС с большим количеством переменных. Он сочетает в себе методы генерации столбцов и ветвления для создания и оценки перспективных столбцов (переменных) итеративно, постепенно создавая оптимальное решение. Это особенно эффективно для задач с большим количеством ограничений.
- Динамическое программирование. Динамическое программирование можно применять для решения определенных типов задач целочисленного программирования, таких как задачи о рюкзаке, путем их разбиения на более мелкие подзадачи и их рекурсивного решения. Он использует перекрывающуюся структуру подзадач, чтобы избежать избыточных вычислений.
- Эвристические алгоритмы. В дополнение к точным алгоритмам используются различные эвристические алгоритмы, такие как генетические алгоритмы, имитация отжига и табу-поиск, чтобы найти почти оптимальные решения для крупномасштабных задач целочисленного программирования за разумное время вычислений. Эти алгоритмы обеспечивают приближенные решения с хорошим качеством, но не гарантируют оптимальности.
Некоторые алгоритмы больше подходят для определенных типов задач или размеров задач. Реализации этих алгоритмов доступны в различных библиотеках оптимизации и программных пакетах, таких как PuLP, Gurobi, CPLEX и SCIP, которые предоставляют эффективные и надежные решатели для целочисленного программирования.
Применительно к задачам о рюкзаке, которые включают в себя выбор подмножества предметов с определенными значениями и весами, чтобы максимизировать общую стоимость в пределах ограничения веса, алгоритмы IP могут предоставить оптимальные решения. Давайте рассмотрим задачу о рюкзаке, используя Python и библиотеку PuLP, которая объединяет решатели IP.
Рассмотрим следующий пример задачи о рюкзаке:
Проблема: у вас есть рюкзак с максимальной грузоподъемностью 15. Доступно пять предметов, каждый со следующим весом и стоимостью:
Пункт 1: вес = 4, ценность = 8
Пункт 2: вес = 5, стоимость = 12
Пункт 3: вес = 3, ценность = 6
Пункт 4: вес = 7, стоимость = 14
Пункт 5: вес = 6, стоимость = 10
Цель состоит в том, чтобы максимизировать общую стоимость выбранных предметов, гарантируя, что общий вес не превышает вместимость рюкзака.
Теперь давайте решим эту задачу о рюкзаке, используя язык программирования Python и библиотеку PuLP:
from pulp import *
# Create the problem instance
problem = LpProblem("Knapsack Problem", LpMaximize)
# Decision variables
items = range(5) # Number of items
selected = LpVariable.dicts("Selected", items, cat="Binary")
# Objective function: Maximize the total value
problem += lpSum(selected[i] * [8, 12, 6, 14, 10][i] for i in items)
# Constraint: Total weight should not exceed the knapsack capacity
problem += lpSum(selected[i] * [4, 5, 3, 7, 6][i] for i in items) <= 15
# Solve the problem
problem.solve()
# Print the optimal solution
print("Optimal Solution:")
for i in items:
if selected[i].value() == 1:
print(f"Item {i + 1} is selected")
# Print the maximum value
print("Maximum Value:", value(problem.objective))
В этом примере мы определяем переменные решения, используя LpVariable.dicts из PuLP, указывая, что они должны принимать двоичные значения (0 или 1), чтобы указать, выбран элемент или нет. Целевая функция состоит в том, чтобы максимизировать общую стоимость выбранных элементов. Добавим ограничение, чтобы общий вес выбранных предметов не превышал вместимость рюкзака.
После решения проблемы с помощью problem.solve() мы можем извлечь оптимальное решение, проверив значения переменных решения. Наконец, мы печатаем выбранные элементы и максимальное полученное значение.
Используя алгоритмы PuLP и IP, мы можем эффективно решить проблему рюкзака и получить оптимальное решение.
Дополнительные ограничения:
Ограничения включают ограничение на назначение рабочих не более чем в две смены, наличие дотракийских рабочих и указанные межличностные конфликты.
from pulp import *
# Define shift names and their requirements
shifts = ["Shift 1", "Shift 2", "Shift 3", "Shift 4", "Shift 5"]
shift_requirements = [8, 6, 9, 7, 5] # Number of workers required for each shift
# Define the cost per worker for each shift
shift_costs = [100, 120, 110, 115, 105] # Cost per worker for each shift
# Define the limit on assigning workers to shifts
max_shifts_per_worker = 2
# Define the Dothraki worker availability and cost
dothraki_worker_limit = 10
dothraki_worker_cost = 40
# Define the interpersonal conflicts
interpersonal_conflicts = [(1, 3), (1, 4), (2, 3), (2, 4), (1, 2), (5, 3), (5, 4)]
# Create the problem instance
problem = LpProblem("Staffing Problem", LpMinimize)
# Decision variables
workers = LpVariable.dicts("Workers", (shifts, range(dothraki_worker_limit + 1)), lowBound=0, cat="Integer")
dothraki_workers = LpVariable.dicts("Dothraki_Workers", shifts, lowBound=0, cat="Integer")
# Objective function: Minimize the total labor costs
problem += lpSum(workers[shift][worker] * shift_costs[i] for i, shift in enumerate(shifts) for worker in range(dothraki_worker_limit + 1)) + \
lpSum(dothraki_workers[shift] * dothraki_worker_cost for shift in shifts)
# Constraints: Ensure sufficient coverage for each shift
for i, shift in enumerate(shifts):
problem += lpSum(workers[shift][worker] for worker in range(dothraki_worker_limit + 1)) + dothraki_workers[shift] >= shift_requirements[i]
# Constraints: Limit on assigning workers to shifts
for worker in range(dothraki_worker_limit + 1):
problem += lpSum(workers[shift][worker] for shift in shifts) <= max_shifts_per_worker
# Constraints: Interpersonal conflicts
for conflict in interpersonal_conflicts:
for shift in shifts:
problem += workers[shift][conflict[0]] + workers[shift][conflict[1]] <= 1
# Solve the problem
problem.solve()
# Print the optimal solution
print("Optimal Solution:")
for shift in shifts:
for worker in range(dothraki_worker_limit + 1):
if workers[shift][worker].value() > 0:
print(f"{shift}: Worker {worker} - {int(workers[shift][worker].value())} workers")
if dothraki_workers[shift].value() > 0:
print(f"{shift}: Dothraki Workers - {int(dothraki_workers[shift].value())} workers")
# Print the minimum cost
print("Minimum Cost:", value(problem.objective))
В этом коде введите новые переменные решения workers для представления рабочих, назначенных на смены, и dothraki_workers для представления количества дотракийских рабочих, назначенных на каждую смену. Переменная решения workers теперь имеет два измерения.
Вывод:
Сегодня мы рассмотрели применение смешанно-целочисленного программирования для улучшения процессов принятия решений. Мы углубились в основные алгоритмы и методы, используемые в исследовании операций, и рассмотрели практический пример, демонстрирующий реальную полезность смешанно-целочисленного программирования.
Я надеюсь, что эта статья пробудила ваш интерес к исследованию операций и побудила вас к дальнейшему изучению огромного потенциала алгоритмов оптимизации. Область исследования операций таит в себе множество захватывающих возможностей, которые можно использовать в различных проектах.
Если вы хотите углубиться в эту тему или получить доступ к коду, связанному с этой статьей, не стесняйтесь посетить наш репозиторий GitHub. Я призываю вас поделиться своими мыслями и комментариями ниже; Я готов участвовать в дальнейших дискуссиях.
Спасибо, что присоединились ко мне в этом путешествии в область смешанно-целочисленного программирования. Пусть это послужит отправной точкой для открытия новых возможностей и расширения ваших возможностей решения проблем!
Ссылки:
