scipy.optimize.

linprog

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, границы=(0, None), метод='highs', callback=None, опции=None, x0=None, integrality=None)

Линейное программирование: минимизация линейной целевой функции при линейных ограничениях равенства и неравенства.

Линейное программирование решает задачи следующего вида:

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

где \(x\) является вектором переменных решения; \(c\), \(b_{ub}\), \(b_{eq}\), \(l\), и \(u\) являются векторами; и \(A_{ub}\) и \(A_{eq}\) являются матрицами.

Альтернативно, это:

• minimize

  c @ x
  

• такой, что

  A_ub @ x <= b_ub
  A_eq @ x == b_eq
  lb <= x <= ub
  

Обратите внимание, что по умолчанию lb = 0 и ub = None. Другие границы могут быть указаны с помощью bounds.

Параметры:

cОдномерный массив

Коэффициенты линейной целевой функции для минимизации.

A_ub2-D массив, опционально

Матрица ограничений неравенства. Каждая строка A_ub определяет коэффициенты линейного ограничения-неравенства на x.

b_ub1-D массив, необязательный

Вектор ограничений-неравенств. Каждый элемент представляет верхнюю границу соответствующего значения A_ub @ x.

A_eq2-D массив, опционально

Матрица ограничений равенства. Каждая строка A_eq задает коэффициенты линейного ограничения равенства на x.

b_eq1-D массив, необязательный

Вектор ограничения равенства. Каждый элемент A_eq @ x должен равняться соответствующему элементу b_eq.

границыsequence, optional

Последовательность (min, max) пары для каждого элемента в x, определяющий минимальное и максимальное значения этой переменной решения. Если одиночный кортеж (min, max) предоставляется, тогда min и max будет служить границами для всех переменных решения. Используйте None чтобы указать, что границы нет. Например, граница по умолчанию (0, None) означает, что все переменные решения неотрицательны, и пара (None, None) означает отсутствие ограничений, т.е. все переменные могут быть любыми действительными числами.

методstr, optional

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

• ‘highs’ (по умолчанию)

• ‘highs-ds’

• 'highs-ipm'

• ‘interior-point’ (устаревший)

• ‘revised simplex’ (устаревший)

• 'simplex' (устаревший)

Устаревшие методы объявлены устаревшими и будут удалены в SciPy 1.11.0.

callbackвызываемый объект, необязательный

Если предоставлена функция обратного вызова, она будет вызываться как минимум один раз за итерацию алгоритма. Функция обратного вызова должна принимать один scipy.optimize.OptimizeResult состоящий из следующих полей:

xОдномерный массив

Текущий вектор решения.

funfloat

Текущее значение целевой функции c @ x.

successbool

True когда алгоритм успешно завершился.

slackОдномерный массив

(номинально положительные) значения невязок, b_ub - A_ub @ x.

conОдномерный массив

(Номинально нулевые) невязки ограничений-равенств, b_eq - A_eq @ x.

фазаint

Фаза выполнения алгоритма.

statusint

Целое число, представляющее статус алгоритма.

0 : Оптимизация проходит нормально.

1 : Достигнут предел итераций.

2 : Проблема, по-видимому, неразрешима.

3 : Проблема, по-видимому, неограничена.

4 : Возникли численные трудности.

nitint

Текущий номер итерации.

messagestr

Строковый дескриптор статуса алгоритма.

Функции обратного вызова в настоящее время не поддерживаются методами HiGHS.

опцииdict, optional

Словарь параметров решателя. Все методы принимают следующие параметры:

maxiterint

Максимальное количество итераций для выполнения. По умолчанию: см. документацию для конкретного метода.

dispbool

Установить в True для вывода сообщений о сходимости. По умолчанию: False.

предварительное решениеbool

Установить в False для отключения автоматического предварительного решения. По умолчанию: True.

Все методы, кроме решателей HiGHS, также принимают:

tolfloat

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

autoscalebool

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

rrbool

Установить в False для отключения автоматического удаления избыточности. По умолчанию: True.

rr_methodstring

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

SVD:

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

pivot:

Использует алгоритм, представленный в [5] для идентификации избыточных строк.

ID:

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

None:

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

По умолчанию: None. Для задач с разреженным входом этот параметр игнорируется, и используется представленный в [5] используется.

Для специфичных для метода опций см. show_options('linprog').

x01-D массив, необязательный

Начальные значения переменных решения, которые будут уточнены алгоритмом оптимизации. Этот аргумент в настоящее время используется только ‘revised simplex’ метод, и может использоваться только если x0 представляет базовое допустимое решение.

integrality1-D массив или int, опционально

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

0 : Непрерывная переменная; ограничение целочисленности отсутствует.

1 : Целочисленная переменная; переменная решения должна быть целым числом в пределах границы.

2 : Полунепрерывная переменная; переменная решения должна находиться в пределах границы или принимать значение 0.

3 : Полуцелая переменная; переменная решения должна быть целым числом в пределах границы или принимать значение 0.

По умолчанию все переменные непрерывны.

Для смешанных ограничений целочисленности предоставьте массив формы c.shape. Для вывода ограничения на каждую переменную решения из более коротких входных данных, аргумент будет транслирован в c.shape используя numpy.broadcast_to.

Этот аргумент в настоящее время используется только ‘highs’ метод и игнорируется в противном случае.

Возвращает:

resOptimizeResult

A scipy.optimize.OptimizeResult состоящий из полей ниже. Обратите внимание, что типы возвращаемых значений полей могут зависеть от того, была ли оптимизация успешной, поэтому рекомендуется проверить OptimizeResult.status перед использованием других полей:

xОдномерный массив

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

funfloat

Оптимальное значение целевой функции c @ x.

slackОдномерный массив

(Номинально положительные) значения переменных ослабления, b_ub - A_ub @ x.

conОдномерный массив

(Номинально нулевые) невязки ограничений-равенств, b_eq - A_eq @ x.

successbool

True когда алгоритму удается найти оптимальное решение.

statusint

Целое число, представляющее статус завершения алгоритма.

0 : Оптимизация успешно завершена.

1 : Достигнут предел итераций.

2 : Проблема, по-видимому, неразрешима.

3 : Проблема, по-видимому, неограничена.

4 : Возникли численные трудности.

nitint

Общее количество итераций, выполненных на всех этапах.

messagestr

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

Смотрите также

show_options

Дополнительные опции, принимаемые решателями.

Примечания

В этом разделе описаны доступные решатели, которые можно выбрать с помощью параметра 'method'.

‘highs-ds’, и 'highs-ipm' являются интерфейсами к симплексным и интерьер-точечным методам решателей HiGHS [13], соответственно. ‘highs’ (по умолчанию) выбирает между двумя автоматически. Это самые быстрые линейные программные решатели в SciPy, особенно для больших, разреженных задач; какой из этих двух быстрее, зависит от задачи. Другие решатели — это устаревшие методы и будут удалены, когда callback поддерживается методами HiGHS.

Метод ‘highs-ds’, является оберткой для высокопроизводительной реализации двойного пересмотренного симплекс-метода на C++ (HSOL) [13], [14]. Метод 'highs-ipm' является оболочкой для C++ реализации interior-pточка mетод [13]; он включает процедуру кроссовера, поэтому точен как симплекс-решатель. Метод ‘highs’ выбирает между двумя автоматически. Для нового кода, включающего linprog, мы рекомендуем явно выбирать одно из этих трех значений метода.

Добавлено в версии 1.6.0.

Метод ‘interior-point’ использует алгоритм следования по примарно-дуальному пути, как описано в [4]. Этот алгоритм поддерживает разреженные матрицы ограничений и обычно быстрее симплекс-методов, особенно для больших разреженных задач. Однако обратите внимание, что возвращаемое решение может быть немного менее точным, чем решения симплекс-методов, и, как правило, не будет соответствовать вершине политопа, определенного ограничениями.

Добавлено в версии 1.0.0.

Метод ‘revised simplex’ использует пересмотренный симплекс-метод, как описано в [9], за исключением того, что факторизация [11] базисной матрицы, а не её обратной, эффективно поддерживается и используется для решения линейных систем на каждой итерации алгоритма.

Добавлено в версии 1.3.0.

Метод 'simplex' использует традиционную полную табличную реализацию симплекс-алгоритма Данцига [1], [2] (не симплекс Нелдера-Мида). Этот алгоритм включен для обратной совместимости и образовательных целей.

Добавлено в версии 0.15.0.

Перед применением ‘interior-point’, ‘revised simplex’, или 'simplex', процедура предварительного решения на основе [8] пытается выявить тривиальные несовместимости, тривиальную неограниченность и потенциальные упрощения задачи. В частности, проверяет:

• строки нулей в A_eq или A_ub, представляющие тривиальные ограничения;

• столбцы нулей в A_eq и A_ub, представляющие неограниченные переменные;

• столбцы-одиночки в A_eq, представляющие фиксированные переменные; и

• столбцы-одиночки в A_ub, представляющие простые ограничения.

Если предварительный анализ показывает, что задача неограничена (например, неограниченная переменная без ограничений имеет отрицательную стоимость) или неразрешима (например, строка нулей в A_eq соответствует ненулевому значению в b_eq), решатель завершает работу с соответствующим кодом состояния. Обратите внимание, что предварительное решение завершается как только обнаруживается любой признак неограниченности; следовательно, задача может быть сообщена как неограниченная, хотя на самом деле задача невыполнима (но невыполнимость еще не обнаружена). Поэтому, если важно знать, является ли задача фактически невыполнимой, решите задачу снова с опцией presolve=False.

Если ни недопустимость, ни неограниченность не обнаружены за один проход предварительной обработки, границы сужаются, где это возможно, и фиксированные переменные удаляются из задачи. Затем линейно зависимые строки A_eq матрицы удаляются (если они не представляют невыполнимость), чтобы избежать численных трудностей в основной процедуре решения. Обратите внимание, что строки, которые почти линейно зависимы (в пределах заданного допуска), также могут быть удалены, что в редких случаях может изменить оптимальное решение. Если это вызывает беспокойство, устраните избыточность в формулировке вашей задачи и запустите с опцией rr=False или presolve=False.

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

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

Ссылки

[1]

Dantzig, George B., Linear programming and extensions. Rand Corporation Research Study Princeton Univ. Press, Princeton, NJ, 1963

[2]

Хиллер, С.Х. и Либерман, Г.Дж. (1995), «Введение в математическое программирование», McGraw-Hill, глава 4.

[3]

Блэнд, Роберт Г. Новые конечные правила выбора опорного элемента для симплекс-метода. Математика операционных исследований (2), 1977: стр. 103-107.

[4]

Андерсен, Эрлинг Д., и Кнуд Д. Андерсен. «Внутренний точечный оптимизатор MOSEK для линейного программирования: реализация однородного алгоритма». Высокопроизводительная оптимизация. Springer US, 2000. 197-232.

[5] (1,2,3)

Andersen, Erling D. “Finding all linearly dependent rows in large-scale linear programming.” Optimization Methods and Software 6.3 (1995): 219-227.

[6]

Фройнд, Роберт М. "Прямо-двойственные внутренние методы для линейного программирования на основе метода Ньютона." Неопубликованные конспекты курса, март 2004. Доступно 25.02.2017 на https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf

[7]

Фоурер, Роберт. «Решение линейных программ методами внутренней точки». Неопубликованные конспекты лекций, 26 августа 2005 г. Доступно 25.02.2017 по адресу http://www.4er.org/CourseNotes/Book%20B/B-III.pdf

[8] (1,2)

Андерсен, Эрлинг Д., и Кнуд Д. Андерсен. «Предварительное решение в линейном программировании». Математическое программирование 71.2 (1995): 221-245.

[9]

Bertsimas, Dimitris, и J. Tsitsiklis. «Введение в линейное программирование.» Athena Scientific 1 (1997): 997.

[10]

Andersen, Erling D., et al. Implementation of interior point methods for large scale linear programming. HEC/Universite de Geneve, 1996.

[11]

Бартельс, Ричард Х. «Стабилизация симплекс-метода.» Журнал Numerische Mathematik 16.5 (1971): 414-434.

[12]

Tomlin, J. A. “On scaling linear programming problems.” Mathematical Programming Study 4 (1975): 146-166.

[13] (1,2,3)

Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. “HiGHS - высокопроизводительное программное обеспечение для линейной оптимизации.” alphap

[14]

Хуанфу, К. и Холл, Дж. А. Дж. «Параллелизация двойственного пересмотренного симплексного метода». Математическое программирование и вычисления, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

Примеры

Попробуйте в вашем браузере!

Рассмотрим следующую задачу:

\[\begin{split}\min_{x_0, x_1} \ -x_0 + 4x_1 & \\ \mbox{such that} \ -3x_0 + x_1 & \leq 6,\\ -x_0 - 2x_1 & \geq -4,\\ x_1 & \geq -3.\end{split}\]

Задача не представлена в форме, принимаемой linprog. Это легко исправить, преобразовав ограничение «больше чем» в ограничение «меньше чем» путём умножения обеих сторон на коэффициент \(-1\). Также обратите внимание, что последнее ограничение фактически является простой границей \(-3 \leq x_1 \leq \infty\). Наконец, поскольку нет ограничений на \(x_0\), мы должны явно указать границы \(-\infty \leq x_0 \leq \infty\), так как по умолчанию переменные являются неотрицательными. После сбора коэффициентов в массивы и кортежи, входные данные для этой задачи:

>>> from scipy.optimize import linprog
>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bounds = (None, None)
>>> x1_bounds = (-3, None)
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])
>>> res.fun
-22.0
>>> res.x
array([10., -3.])
>>> res.message
'Optimization terminated successfully. (HiGHS Status 7: Optimal)'

Маргиналы (также известные как двойственные значения / теневые цены / множители Лагранжа) и остатки (зазоры) также доступны.

>>> res.ineqlin
  residual: [ 3.900e+01  0.000e+00]
 marginals: [-0.000e+00 -1.000e+00]

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

>>> eps = 0.05
>>> b[1] += eps
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.05

Кроме того, поскольку остаток по первому ограничению-неравенству равен 39, мы можем уменьшить правую часть первого ограничения на 39, не затрагивая оптимальное решение.

>>> b = [6, 4]  # reset to original values
>>> b[0] -= 39
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.0

НазадОткрыть во вкладке