Симплексный алгоритм и крайние точки
По этому вопросу я сокращаюсь так: LP = линейная программа, BFS = базовое возможное решение, SEF = стандартная форма равенства.
Поскольку симплекс-алгоритм выполняет итерацию от крайней точки до крайней точки (что соответствует тому факту, что симплекс выполняет итерацию от BFS к BFS, когда LP находится в SEF), как геометрически работает симплекс-алгоритм, когда допустимая область представляет собой многогранник, который не может быть реализован в SEF (например, полупространство)? Предположим, у нас есть ЛП, для которой допустимая область не имеет крайних точек. Затем мы можем написать «эквивалентный» LP, который находится в SEF, и вместо этого запустить на нем симплексный алгоритм. Но у этого нового многогранника есть крайние точки, тогда как у исходного, по предположению, их нет. Первоначально я думал, что крайние точки одной ЛП биективно соответствуют крайним точкам другой, но, очевидно, это не так.
Итак, когда именно крайние точки SEF-версии LP биективно соответствуют крайним точкам оригинала? И, кроме того, если такое взаимное соответствие не выполняется, как мы должны геометрически интерпретировать то, что делает симплекс-алгоритм, в терминах исходного LP?
Ответы
алгоритм симплекс выполняет итерацию от крайней точки до крайней точки
Технически нет. Симплексный алгоритм повторяется от основания к основанию . Просто так случается, что возможные базовые решения соответствуют крайним точкам. (например, двойственный симплекс выполняет итерацию по двойственно допустимым базовым решениям, которые не являются крайними точками области прямой допустимости).
Рассмотрим LP в стандартной форме, который пишет \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}Возможная область этой LP всегда многогранна. Если у него нет крайних точек, то оно либо пусто (и основных допустимых решений нет), либо аффинное подпространство$\mathbb{R}^{n}$. Теперь последний случай невозможен , потому что никакое аффинное подпространство не может быть подмножеством$\mathbb{R}_{+}^{n}$.
Теперь, возвращаясь к (как я думаю) вашему первоначальному вопросу: учитывая исходный многогранник и SEF-представление для него, имеет ли это представление крайние точки и соответствуют ли они крайним точкам исходного многогранника? Ответ: да, у SEF будут крайние точки, и нет, они не всегда могут соответствовать крайним точкам вашего исходного многогранника.
Вот простой пример: возьмите $\mathcal{P} = \{x \in \mathbb{R}\}$, представляющий собой одномерный многогранник. Его формулировка имеет одну свободную переменную и никаких ограничений.
Чтобы построить представление SEF, замените $x$ от $x^{+} - x^{-}$ с участием $x^{\pm} \geq 0$. Сейчас же,$(0, 0)$ крайняя точка этой СЭФ, соответствующая $x=0$, что не является крайней точкой $\mathcal{P}$.
Не уверен, что я полностью понимаю ваш вопрос, но я предполагаю, что ваше замешательство связано с предположением, что базовое решение - это «крайняя точка». Базовое (не обязательно прямое или двойственно допустимое) решение - это просто пересечение ограничений количества строк (некоторые из которых могут быть границами). Вполне возможно, что проблема не имеет прямого или двойственно допустимого решения, в результате чего она либо недопустима, либо неограничена. Учебные симплексные алгоритмы иногда упускают из виду тот факт, что для создания BFS для фактического запуска алгоритма требуется некая форма подхода фазы 1. Возможно, что на первичной фазе 1 проблема окажется неприемлемой, а также возможно, что на двойной фазе 1 проблема окажется неограниченной.
Обновление: ответ mtanneau, вероятно, говорит все, что можно сказать, для одного ограничения со свободными переменными применимо то же самое. Я просто хочу добавить, что симплексные реализации работают со свободными переменными напрямую и не преобразуют их в две переменные, ограниченные нулем. Но то же самое верно, алгоритм выполняет итерацию по базовым решениям, и принято соглашение, что неосновные свободные переменные принимают значение 0. Также отметим, что для ограниченных многогранников базовые решения соответствуют крайним точкам.