Начало работы с OR-инструментами для Python

Следующие разделы помогут вам начать работу с OR-Tools для Python:

Что такое проблема оптимизации?

Цель оптимизации — найти лучшее решение проблемы из большого множества возможных решений. (Иногда вам будет достаточно найти любое осуществимое решение; OR-Tools тоже может это сделать.)

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

Как и все задачи оптимизации, эта задача имеет следующие элементы:

  • Цель — количество, которое вы хотите оптимизировать. В приведенном выше примере целью является минимизация затрат. Чтобы поставить задачу оптимизации, вам необходимо определить функцию, которая вычисляет значение цели для любого возможного решения. Это называется целевой функцией . В предыдущем примере целевая функция рассчитает общую стоимость любого назначения пакетов и маршрутов.

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

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

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

Первым шагом в решении задачи оптимизации является определение цели и ограничений.

Решение задачи оптимизации на Python

Далее мы приведем пример задачи оптимизации и покажем, как ее настроить и решить на Python.

Пример линейной оптимизации

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

Максимизируйте 3x + y при следующих ограничениях:

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

Целевая функция в этом примере — 3x + y . И целевая функция, и ограничения задаются линейными выражениями, что делает эту задачу линейной.

Основные шаги решения проблемы

Для каждого языка основные этапы постановки и решения задачи одинаковы:

  1. Импортируйте необходимые библиотеки,
  2. Объявите решатель,
  3. Создайте переменные,
  4. Определите ограничения,
  5. Определить целевую функцию,
  6. Вызовите решатель и
  7. Отобразите результаты.

Программа на Python

В этом разделе рассматривается программа Python, которая устанавливает и решает проблему.

Вот шаги:

  • Импортируйте необходимые библиотеки.
    from ortools.linear_solver import pywraplp
  • Объявите решатель.
    # Create the linear solver with the GLOP backend.
solver = pywraplp.Solver.CreateSolver("GLOP")
if not solver:
    return
    pywraplp — это оболочка Python для базового решателя C++. Аргумент "GLOP" указывает GLOP , линейный решатель OR-Tools.
  • Создайте переменные.
    # Create the variables x and y.
x = solver.NumVar(0, 1, "x")
y = solver.NumVar(0, 2, "y")

print("Number of variables =", solver.NumVariables())
  • Определите ограничения. Первые два ограничения, 0 ≤ x ≤ 1 и 0 ≤ y ≤ 2 , уже установлены определениями переменных. Следующий код определяет ограничение x + y ≤ 2 :
    # Create a linear constraint, 0 <= x + y <= 2.
ct = solver.Constraint(0, 2, "ct")
ct.SetCoefficient(x, 1)
ct.SetCoefficient(y, 1)

print("Number of constraints =", solver.NumConstraints())
    Метод SetCoefficient устанавливает коэффициенты x и y в выражении для ограничения.
  • Определите целевую функцию.
    # Create the objective function, 3 * x + y.
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 1)
objective.SetMaximization()
    Метод SetMaximization объявляет это проблемой максимизации.
  • Вызовите решатель и отобразите результаты.
    print(f"Solving with {solver.SolverVersion()}")
solver.Solve()
print("Solution:")
print("Objective value =", objective.Value())
print("x =", x.solution_value())
print("y =", y.solution_value())

Полная программа

Полная программа представлена ​​ниже.

from ortools.linear_solver import pywraplp


def main():
    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        return

    # Create the variables x and y.
    x = solver.NumVar(0, 1, "x")
    y = solver.NumVar(0, 2, "y")

    print("Number of variables =", solver.NumVariables())

    # Create a linear constraint, 0 <= x + y <= 2.
    ct = solver.Constraint(0, 2, "ct")
    ct.SetCoefficient(x, 1)
    ct.SetCoefficient(y, 1)

    print("Number of constraints =", solver.NumConstraints())

    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x, 3)
    objective.SetCoefficient(y, 1)
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    solver.Solve()

    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x.solution_value())
    print("y =", y.solution_value())


if __name__ == "__main__":
    main()

Запуск программы

Вы можете запустить приведенную выше программу следующим образом:

  1. Скопируйте и вставьте приведенный выше код в новый файл и сохраните его как program.py .
  2. Откройте командное окно и перейдите в каталог, в котором вы сохранили program.py . В командной строке введите:
    python relative/path/to/program.py
    где relative/path/to/ это путь к каталогу, в котором вы сохранили программу.

Программа возвращает значения x и y , которые максимизируют целевую функцию:

Solution:
x =  1.0
y =  1.0

Больше примеров Python

Дополнительные примеры Python, иллюстрирующие, как решать различные типы задач оптимизации, см. в разделе «Примеры» .

Определение типа проблемы, которую вы хотите решить

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

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

Ниже вы найдете краткий обзор типов проблем, которые решает OR-Tools, а также ссылки на разделы этого руководства, в которых объясняется, как решить каждый тип проблем.

Линейная оптимизация

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

Основным решателем в OR-Tools для задач такого типа является решатель линейной оптимизации, который на самом деле является оболочкой для нескольких различных библиотек для линейной и смешанно-целочисленной оптимизации , включая сторонние библиотеки.

Узнайте больше о линейной оптимизации

Смешанно-целочисленная оптимизация

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

Узнайте больше о смешанно-целочисленной оптимизации.

Оптимизация ограничений

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

Узнайте больше об оптимизации ограничений

Назначение

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

Узнать больше о задании

Упаковка

Бин-упаковка — это задача упаковки набора предметов разного размера в контейнеры разной вместимости. Цель — упаковать как можно больше объектов с учетом вместимости контейнеров. Особым случаем является задача о рюкзаке , в которой контейнер всего один.

Узнайте больше об упаковке в мусорные контейнеры

Планирование

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

Узнайте больше о планировании

Маршрутизация

Задачи маршрутизации включают в себя поиск оптимальных маршрутов для парка транспортных средств, пересекающих сеть, определенную ориентированным графом. Проблема назначения посылок грузовикам доставки, описанная в разделе «Что такое задача оптимизации?» , является одним из примеров проблемы маршрутизации. Другая проблема – это задача коммивояжера .

Узнать больше о маршрутизации

Сетевые потоки

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

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

Узнайте больше о сетевых потоках