linprog(method='highs-ds')

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-ds'. ‘highs’, 'highs-ipm', ‘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

Общее количество выполненных итераций. Это включает итерации во всех фазах.

crossover_nitint

Это всегда 0 для симплексного метода HiGHS. Для метода внутренней точки 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

Максимальное количество итераций для выполнения в любой фазе. По умолчанию — максимально возможное значение для int на платформе.

dispbool (по умолчанию: False)

Установить в True если индикаторы статуса оптимизации должны выводиться в консоль во время оптимизации.

предварительное решениеbool (по умолчанию: True)

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

time_limitfloat

Максимальное время в секундах, выделенное на решение задачи; по умолчанию - наибольшее возможное значение для double на платформе.

dual_feasibility_tolerancedouble (по умолчанию: 1e-07)

Допуск двойственной допустимости для ‘highs-ds’.

primal_feasibility_tolerancedouble (по умолчанию: 1e-07)

Допуск первичной выполнимости для ‘highs-ds’.

simplex_dual_edge_weight_strategystr (по умолчанию: None)

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

'dantzig' использует исходную стратегию Данцига выбора наиболее отрицательной приведённой стоимости.

'devex' использует стратегию, описанную в [15].

steepest использует точную стратегию наискорейшего спуска, как описано в [16].

'steepest-devex' начинается с точной стратегии наискорейшего спуска, пока вычисления не станут слишком затратными или неточными, а затем переключается на метод devex.

В настоящее время, None всегда выбирает 'steepest-devex', но это может измениться по мере появления новых опций.

unknown_optionsdict

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

Примечания

Метод ‘highs-ds’ является оболочкой для высокопроизводительной реализации двойственного пересмотренного симплекс-метода на C++ (HSOL) [13], [14]. Метод 'highs-ipm' является обёрткой для реализации на C++ interior-pточка mетод [13]; он включает процедуру кроссовера, поэтому точен как симплекс-решатель. Метод ‘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

[15]

Харрис, Паула М.Дж. «Методы выбора опорного элемента в коде Devex LP.» Математическое программирование 5.1 (1973): 1-28.

[16]

Голдфарб, Дональд и Джон Кер Рид. "A practicable steepest-edge simplex algorithm." Mathematical Programming 12.1 (1977): 361-371.