Переменная Slack

редактировать

В задаче оптимизации , резервная переменная - это переменная, которая добавлена к ограничению неравенства, чтобы преобразовать его в равенство. Введение переменной slack заменяет ограничение неравенства на ограничение равенства и ограничение неотрицательности для переменной slack.

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

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

Содержание

1 Пример
2 Встраивание в orthant
3 ссылки
4 Внешние ссылки

Пример

путем введения переменной slack $y ≥ 0 {\ displaystyle \ mathbf {y} \ geq \ mathbf {0} }$ ${\ displaystyle \ mathbf {y} \ geq \ mathbf {0}}$ , неравенство $A x ≤ b {\ displaystyle \ mathbf {A} \ mathbf {x} \ leq \ mathbf {b}}$ ${\ mathbf {A}} {\ mathbf {x}} \ leq {\ mathbf {b}}$ можно преобразовать в уравнение $A x + y = b {\ displaystyle \ mathbf {A} \ mathbf {x} + \ mathbf {y} = \ mathbf {b}}$ ${\ displaystyle \ mathbf {A} \ mathbf {x} + \ mathbf {y} = \ mathbf {b}}$ .

Встраивание в ортант

переменные Slack дают вложение многогранника $P ↪ (R ≥ 0) f {\ displaystyle P \ hookrightarrow (\ mathbf {R} _ {\ geq 0}) ^ {f}}$ $P \ hookrightarrow ( \ mathbf {R} _ {\ geq 0}) ^ f$ в стандартный f- orthant, где f - количество ограничений (грани многогранника). Эта карта взаимно однозначна (переменные резерва определяются однозначно), но не на (не все комбинации могут быть реализованы), и выражается в терминах ограничений (линейные функционалы, ковекторы).

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

Двойным образом обобщенные барицентрические координаты выражают многогранник с n вершинами (двойственными фасетам), независимо от размерности, как изображение стандартного $(n - 1) {\ displaystyle (n-1)}$ $(n-1)$ -симплекс, имеющий n вершин - карта находится на: $Δ n - 1 ↠ P, {\ displaystyle \ Delta ^ {n-1} \ twoheadrightarrow P,}$ $\ Delta ^ {{n-1}} \ twoheadrightarrow P,$ и выражает точки через вершины (точки, векторы). Отображение взаимно однозначно тогда и только тогда, когда многогранник является симплексом, и в этом случае отображение является изоморфизмом; это соответствует точке, не имеющей уникальных обобщенных барицентрических координат.

Ссылки

Внешние ссылки

Учебное пособие по Slack Variable - Решайте проблемы с Slack-переменными онлайн