Я читаю симплексный алгоритм в учебнике под названием Алгоритмы Дасгупта-Пападимитриу-Вайрани
На каждой итерации симплекс имеет две задачи: 1. Проверить, является ли текущая вершина оптимальной (и если да, то Остановись). 2. Определите, куда двигаться дальше.
Как мы увидим, обе задачи легко выполнить, если вершина окажется в начале координат. И если вершина находится в другом месте, мы преобразуем систему координат, чтобы переместить ее в начало координат!
Сначала давайте посмотрим, почему начало координат так удобно. Предположим, что у нас есть некоторый шаблон c LP
max c transpose * x Ax <= bx> = 0
, где x - вектор переменных, x = (x1;:: :; xn). Предположим, происхождение возможно. Тогда это, безусловно, вершина, поскольку это единственная точка, в которой n неравенств {x1> = 0, ..., xn> = 0} тесны.
Теперь давайте решим две наши задачи. Задача 1:
Начало координат является оптимальным тогда и только тогда, когда все ci <= 0 </p>
Если все ci <= 0, то, учитывая ограничения x> = 0, мы не можем надеяться на лучшая объективная ценность. И наоборот, если некоторое ci> 0, то начало координат не является оптимальным, поскольку мы можем увеличить целевую функцию, подняв xi.
Таким образом, для задачи 2 мы можем двигаться, увеличив некоторую xi, для которой ci> 0 Насколько мы можем увеличить это? Пока мы не столкнемся с каким-то другим ограничением. То есть, мы снимаем жесткое ограничение xi> = 0 и увеличиваем xi до тех пор, пока какое-то другое неравенство, ранее потерянное, не стало жестким.
В этот момент у нас снова ровно n жестких неравенств, поэтому мы находимся в новой вершине.
Например, предположим, что мы имеем дело со следующей линейной программой.
> max 2x1 + 5x2 2x1 - x2 <= 4 ----> Eq 1
x1 + 2x2 <= 9 ----> Eq 2
> -x1 + x2 <= 3 -----> Eq 3
x1 >= 0 -----------> Eq 4
x2 >= 0 -----------> Eq 5
Симплекс можно запустить в начале координат, что определяется ограничениями 4 и 5. Чтобы двигаться, мы освобождаем жесткое ограничение x2> = 0. По мере постепенного увеличения x2 первое ограничение, с которым оно сталкивается, равно -x1 + x2 <= 3, и поэтому оно должно остановиться на x2 = 3, после чего этот новый Неравенство тесно. Таким образом, новая вершина задается уравнениями 3 и 4. </p>
Итак, мы знаем, что делать, если мы находимся в начале координат. Но что, если наша текущая вершина u находится в другом месте? Хитрость заключается в том, чтобы преобразовать u в начало координат, сдвигая систему координат из обычного (x1, ..., xn) в локальный вид из u. Эти локальные координаты состоят из (соответственно масштабированных) расстояний y1, ..., yn до n гиперплоскостей (неравенств), которые определяют и заключают в себе u:
u
/ \
/ \
/ /\
/ /y1\
/----x \
y2
В частности, если одно из этих охватывающих неравенств равно ai * x <= bi, то расстояние от точки x до этой конкретной «стены» равно yi = bi - ai * x </p>
n уравнений этого типа, по одному на стенку, определяют значения yi как линейные функции XI, и это отношение может быть обращено к express XI как линейная функция от YI. Таким образом, мы можем переписать весь LP с точки зрения y. Это принципиально не меняет его (например, оптимальное значение остается неизменным), но выражает его в другой системе координат. Пересмотренный локальный LP имеет следующие три свойства:
Пересмотренный локальный LP имеет следующие три свойства: 1. Он включает в себя неравенства y> = 0, которые являются просто преобразованными версиями неравенств, определяющих u. 2. Вы - источник в y-пространстве. 3. Функция стоимости становится max cu + ~ cT * y, где cu - значение целевой функции для u, а ~ c - преобразованный вектор стоимости.
У меня возникли трудности с Понимание хитрости в вышеприведенном утверждении, упомянутом ниже:
Хитрость заключается в том, чтобы преобразовать u в начало координат, сдвигая систему координат из обычного (x1, ..., xn) в локальное представление из u , Эти локальные координаты состоят из (соответственно масштабированных) расстояний y1, ..., yn до n гиперплоскостей (неравенств), которые определяют и заключают u:
Что автор имеет в виду, переводя систему координат в локальное представление из "u" в приведенном выше утверждении?
Что означают локальные координаты из расстояний до n гиперплоскостей?
Пожалуйста, объясните
Заранее спасибо за ваше время и помощь