linprog(method=’highs’)

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', который автоматически выбирает между ‘highs-ds’ и 'highs-ipm'. ‘interior-point’ (по умолчанию), ‘revised simplex’, и 'simplex' (устаревший) также доступны.

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

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

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

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

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

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

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

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

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

Возвращает:

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 это включает итерации во всех фазах. Для метода внутренней точки HiGHS это не включает итерации кроссовера.

crossover_nitint

Количество прямых/двойных проталкиваний, выполненных во время процедуры кроссовера для метода внутренней точки HiGHS. Это 0 для симплекс-метода 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)

Допуск двойственной допустимости для ‘highs-ds’. Минимум этого и primal_feasibility_tolerance используется для допуска выполнимости 'highs-ipm'.

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

Допуск первичной выполнимости для ‘highs-ds’. Минимум этого и dual_feasibility_tolerance используется для допуска выполнимости 'highs-ipm'.

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

Допуск оптимальности для 'highs-ipm'. Минимально допустимое значение — 1e-12.

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

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

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

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

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

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

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

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

Критерий остановки для MIP-решателя: решатель завершит работу, когда разрыв между значением целевой функции прямой задачи и границей целевой функции двойственной задачи, масштабированный значением целевой функции прямой задачи, <= mip_rel_gap.

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.