linprog(method=‘highs-ipm’)#

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)

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

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

\[\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}\) являются матрицами.

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

минимизировать:

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, определяя минимальное и максимальное значения этой переменной решения. Используйте None чтобы указать, что ограничения отсутствуют. По умолчанию ограничения (0, None) (все переменные решения неотрицательны). Если одиночный кортеж (min, max) предоставляется, тогда min и max будет служить границами для всех переменных решения.
методstr: Это документация, специфичная для метода 'highs-ipm'. 'highs-ipm', ‘highs-ds’, ‘interior-point’ (по умолчанию), ‘revised simplex’, и 'simplex' (устаревший) также доступны.

Возвращает:

resOptimizeResult

A scipy.optimize.OptimizeResult состоящий из полей:

x1D массив

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

funfloat

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

slack1D массив

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

con1D массив

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

successbool

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

statusint

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

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

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

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

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

4 : Решатель HiGHS столкнулся с проблемой.

messagestr

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

nitint

Общее количество выполненных итераций. Для метода внутренней точки HiGHS это не включает итерации кроссовера.

crossover_nitint

Количество прямых/двойственных проталкиваний, выполненных во время процедуры кроссовера для метода внутренней точки HiGHS.

ineqlinOptimizeResult

Информация о решении и чувствительности, соответствующая ограничениям-неравенствам, b_ub. Словарь, состоящий из полей:

остатокnp.ndnarray: (Номинально положительные) значения переменных ослабления, b_ub - A_ub @ x. Эта величина также часто называется «запасом».
маргинальные распределенияnp.ndarray: Чувствительность (частная производная) целевой функции по правой части ограничений-неравенств, b_ub.

eqlinOptimizeResult

Решение и информация о чувствительности, соответствующие ограничениям равенства, b_eq. Словарь, состоящий из полей:

остатокnp.ndarray: (Номинально нулевые) невязки ограничений-равенств, b_eq - A_eq @ x.
маргинальные распределенияnp.ndarray: Чувствительность (частная производная) целевой функции по правой части ограничений-равенств, b_eq.

нижняя, верхняяOptimizeResult

Информация о решении и чувствительности, соответствующая нижним и верхним границам на переменные решения, границы.

остатокnp.ndarray: (Номинально положительные) значения величины x - lb (нижняя) или ub - x (верхний).
маргинальные распределенияnp.ndarray: Чувствительность (частная производная) целевой функции по нижней и верхней границы.

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

Для документации по остальным параметрам см. scipy.optimize.linprog

Опции:

——-
maxiterint: Максимальное количество итераций для выполнения в любой фазе. Для 'highs-ipm', это не включает количество кроссоверных итераций. По умолчанию — наибольшее возможное значение для int на платформе.
dispbool (по умолчанию: False): Установить в True если индикаторы статуса оптимизации должны выводиться в консоль во время оптимизации.
предварительное решениеbool (по умолчанию: True): Предварительное решение пытается выявить тривиальные несовместимости, определить тривиальную неограниченность и упростить задачу перед отправкой её основному решателю. Обычно рекомендуется сохранять настройки по умолчанию True; установить в False если предварительное решение должно быть отключено.
time_limitfloat: Максимальное время в секундах, выделенное на решение задачи; по умолчанию - наибольшее возможное значение для double на платформе.
dual_feasibility_tolerancedouble (по умолчанию: 1e-07): Минимум этого и primal_feasibility_tolerance используется для допуска выполнимости 'highs-ipm'.
primal_feasibility_tolerancedouble (по умолчанию: 1e-07): Минимум этого и dual_feasibility_tolerance используется для допуска выполнимости 'highs-ipm'.
ipm_optimality_tolerancedouble (по умолчанию: 1e-08): Допуск оптимальности для 'highs-ipm'. Минимально допустимое значение — 1e-12.
unknown_optionsdict: Дополнительные аргументы, не используемые этим конкретным решателем. Если unknown_options если не пуст, выдается предупреждение со списком всех неиспользуемых опций.

Примечания

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

Поля результата ineqlin, eqlin, lower, и upper все содержат маргинальные распределения, или частные производные целевой функции по правой части каждого ограничения. Эти частные производные также называются «множителями Лагранжа», «двойственными значениями» и «теневой ценой». Соглашение о знаке маргинальные распределения противоположна множителям Лагранжа, создаваемым многими нелинейными решателями.

Ссылки

[13] (1,2)

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