Слабая переменная

В задаче оптимизации слабая переменная — это переменная, которая добавляется к ограничению неравенства, чтобы преобразовать его в ограничение равенства. Также добавляется ограничение неотрицательности слабой переменной. ^[1]^: 131

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

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

Slack-переменные также используются в методе Big M.

Пример [ править ]

Введя слабую переменную $\mathbf {s} \geq \mathbf {0}$ , неравенство $\mathbf {A} \mathbf {x} \leq \mathbf {b}$ можно преобразовать к уравнению $\mathbf {A} \mathbf {x} +\mathbf {s} =\mathbf {b}$ .

Встраивание в ортант [ править ]

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

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

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

Ссылки [ править ]

^ Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 октября 2011 г.
^ Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 . ^: 42

Внешние ссылки [ править ]

Учебное пособие по слабым переменным — решение проблем с медленными переменными онлайн

[1] Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 октября 2011 г.

[2] Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 . ^: 42

[1]

[2]