Лекция #19. Решение LCP методом Лемке [Лектор - fd]

Автор: Арсений Капулкин

[20:12] <fd> Значит, хочу предупредить, что я пробовал объянснят ьЛемке уже дважды
[20:12] <fd> оба раза безуспешно
[20:12] <fd> пробую третий
[20:12] <fd> если стало не понятно - не ждите, что будет лучше, спрашивайте
[20:13] <fd> Во-первых, нафик Лемке нужен
[20:14] <fd> он нафик не нужен :) Но по просьбе Иннокентия.. В общем, Лемке - это крайне тормознйо способ решить ЛЦП. Однако, в доках, бывает, используется. И вообще помогает вкурить в суть ЛЦП.. Так что рассказываю
[20:15] <fd> Когда речь идёт о СОРе, например, в доках, и по-жизни, смешивают обычно постановку задачи и её решение
[20:15] <fd> то есть, в нашем случае, формулировку физической задачи в форме ЛЦП, и решение ЛЦП
[20:17] <fd> Оптимизации в СОРе тоже происходят из сути физической задачи.. В Лемке таких зависимых оптимизаций нет, поэтому рассказ будет о ЛЦП и Лемке в отрыве от физики
[20:17] <fd> хотя физика - основное примение в нашем деле
[20:18] <fd> СОР, меня спрашивают тут, - основной практический алгоритм решения ЛЦП, итеративный, SOR-LCP, он же Projected Gauss-Seidel. Его, видимо, можн опорекомендовать на практике, но сейчас не про него
[20:19] <fd> ЛЦП - задача о линйеной дополняющей. В Лемке рассматривается в классическом виде:
[20:20] <fd> (1)w - A*x = q, где A - квадратная матрица размерности n на n, q - вектор размерности n, w,x - неизвестыне
[20:20] <fd> (2) w >=0 ; x >= 0 для каждого i
[20:20] <fd> (3) w*x = 0 для каждого i
[20:22] <fd> Последнее условие означает w dot x = 0
[20:23] <fd> По-русски если, неизвестные неотрицательны, но при этом из каждой дополняющей пары неизвестных одна - нулевая
[20:25] <fd> Если есть такой вектор x, что -A*x = q и x неотрицателен, то ЛЦП выражадется в систему линейных уравнений
[20:25] <fd> Если q неотрицателен, то при x = 0 w = q будет допустимым решением ЛЦП
[20:26] <fd> Последний случай тривиален - если q неотрицательно, дальше не решаем
[20:28] <fd> Значит Лемке - итеративен, в том смысле, что он делает неизвестное заранее число итераций
[20:29] <fd> Однако каждая следующая итерация НЕ приблежает нас к решению, поэтому нельзя сделать конченое число итераций, или что-т оподобное, предвосхищая вопросы скажу
[20:30] <fd> Смысл итераций Лемке заключается в переборе почти допустимых базисов.. Что такое - скажу позже..
[20:30] <fd> Под базисом в Лемке понимается обычно набор ненулевых переменных
[20:31] <fd> как я говорил, каждая пара дополнительных переменных x - w содержит одну нулевую, и одну неотрицательную переменную
[20:32] <fd> неотрицательные - базисные, нулевые - небазисные. Поскольку это разграничение танцует от нулевых перменных, будут ли среди неотрицательных базисных нулевые - не важно
[20:34] <fd> Ох, спрашивают меня тут про геометрическое представление ЛЦП :((
[20:34] <fd> Ну, есть конусы ЛЦП, но они совершенно не наглядны, на мой вкус..
[20:34] <fd> Попробую объяснить шкурой, но без графики
[20:36] <fd> ЛЦП можн опредставить как систему линйеных уравнений относительно x, но все х положительны, а если х "хочет" стать отрицательным, то он "упирается" в 0, а i-е уравнение вычёркивается (на деле, компенсируется ростом w)
[20:37] <fd> Ещё более шкурно - это в Бараффовской задаче про силы реакций опоры
[20:38] <fd> он выразил ускорения в точках контакта через силы реакции опоры и иные силы
[20:39] <fd> ускорение от иных сил шло вектором, а действие сил реакции опоры превращалось в эти самые ускорения матричным умноженеим
[20:39] <fd> То есть a = Af + q
[20:41] <fd> f >= само собой, чтобы реакция опоры не стягивала тела, a >=0 чтобы не было ускорения друг в друга в точке опопры (собственно, сут ьопопры), а a dot f = 0 потому как если ускоерние положительное, то сила реакции в этйо точке действовать не должна
[20:41] <fd> Это н егеометрия, но это один из физических смыслов лцп
[20:41] <fd> на мой взгляд, очень наглядно
[20:42] <fd> Итак, возвращаюсь к базисам
[20:44] <fd> чисто теоритичсеки, если бы мы силою Б-жей знали, какие x объявить базисными, чтобы выполнились условия ЛЦП, этого было бы достаточно для решения
[20:44] <fd> Поясню
[20:45] <fd> Если какие-то х базисные, то дополнительные к ним w - небазисные, и соответственно оставшиеся x небазиснве, оставшиеся w - базисные
[20:46] <fd> Так как небазисные нулевые, остаётся половина неизвестных, что соответсвует размерност иматрицы
[20:46] <fd> и остаток решается как система уравнений
[20:48] <fd> Это так мжно показать - введём прямоугольную матрицу М = (I;-A) и вектор v = (w,x). Тогда M * v = q, и если в  v половина переменных 0, то получается симпатичная СЛАУ
[20:49] <fd> Поэтому весь ЛЕМКЕ - это поиск допустимого базиса
[20:49] <fd> такого базиса, в котором выполянются услвоия неотрицательности (2) и дополнительности (3)
[20:50] <fd> Теперь атас. Собственно, Лемке. Дальше меня обычно н епонимают.
[20:50] <fd> Лемке работает через искуссвтенную переменную
[20:51] <fd> Вводится лишняя перменная в систему
[20:52] <fd> Берётся столбец e положительных значений, обычно - единиц, и система заменяется на w - Ax = e*z + q
[20:53] <fd> Если искусственная перменная z = 0, то система приходит к нормальной системе ЛЦП
[20:54] <fd> Соотвтественно, если z - небазисная, и условия ЛЦП выполянются, то такой базис является допустимым
[20:54] <fd> Если z - базисная, но условия ЛЦП выполнются, то такой базис - "почти допустимый"
[20:55] <fd> Лемке от итерации к итерации перемещается между почти допусмыми базисами, пока не встертит собственно допустимый
[20:56] <fd> Как оно перемещается?
[20:56] <fd> Оно пермещается заменой одной переменной в базисе
[20:57] <fd> От каждой итерации к каждой одна переменная объявляется 0, уходит из базиса, а другая, бывшая 0, объявляется неотрицательной и входит в бвзис
[20:57] <fd> В ротации участвуют, естественно, как х, так и w, и z
[20:58] <fd> На всякий случай - z - СКАЛЯР, w и x - вектора
[20:59] <fd> Из условия дополнительности (3) следует, что из каждого почти дрпустимог обазиса подобнйо перстановкой можно прийти только в 2 другиъх почти допустимых базиса
[21:02] <fd> Объясняется это просто - когда мы вводим какую-либо переменную в бвзис, мы не можем заранее предугадать, какая переменная станет 0 и выйдет из базиса, при сохранении условий неотрицательности. Но необходимо, чтобы из каждой пары дополнительных перменных одна была нулевой. Значит, можно вводить только такую перменну, которая и сама не в бвзисе, и её дополнительная перменная не в бвзисе
[21:03] <fd> Есть только одна пара дполнительных пересенных, которые в данном почти допустимом базисе обе вне базиса
[21:03] <fd> Эт овозникает как раз из-за искусственной переменной
[21:04] <fd> Если она в базисе, их n штук в базисе, то одна пара дополнительных целиком вне базиса
[21:06] <fd> Ну вот.. Поэтому есть траектория Лемке, от одного базиса к другому.. Потому как с одного сопряжённого она входит, а в другой выходит
[21:07] <fd> Есть случаи вырожденности, но о них позже
[21:07] <fd> А так Лемке бужет идти по траектории либо пока не встертится допустимый базис, либо пока мы не вылетим по бесконченому лучу
[21:08] <fd> Бесконечный луч - это когда невозможно выбрать уходящую переменную.
[21:10] <fd> Уходящая перменная рассчитывается просто - максимизируется значение входящей до тех пор, пока рост не упрётся в одно из условий неотрицательности. Блокирующая переменная, услвоие неотрицательности которой блокирует рост входящей, и назначается уходящей
[21:10] <fd> Если рост входящей перменной ничем не блокируется, то это и есть бесконечный луч
[21:11] <fd> Он свидетельствует либо о том, что у ЛЦП нет решения, лиюо что метод Лемке не может его найти
[21:11] <fd> Значит, с чего начать
[21:11] <fd> Начинают просто
[21:12] <fd> Ищется самая отрицательная q
[21:12] <fd> q
[21:12] <fd> z = -q, x = 0,
[21:14] <fd> получается w  = q + ez, причём q + ez будет, естественно, неотрицателен, а его i элемент будет 0
[21:14] <fd> то есть w <=> 0
[21:14] <fd> то есть, она тоже небазисная в начальном базисе
[21:14] <fd> и все х небазисные
[21:17] <fd> так находится первоначальный базис, который, к тому же, имеет интеерснеое свойство - из него нельзя уйти увеличением w, ибо попадём на бесконченый луч. Рост w не блокируется ничем.
[21:18] <fd> пожтому из таког оначального базиса один выход - через рост x, ибо x и w - это та самая единственная пара, которая целиком вне базиса
[21:18] <fd> Это даёт однозначность начала процесса
[21:18] <fd> так, чую, пора давать код..
[21:21] <fd> http://www.everfall.com/paste/id.php?7safd21rczoe
[21:22] <fd> строки 4 - 26 выбор начального базиса
[21:22] <fd> 19- 24 - обработка тривиального случая, когда q положительный
[21:25] <fd> Значит переход от базиса к базису
[21:25] <fd> выглядит просто
[21:25] <fd> мы знаем переменную, которую мы вывели в бвзис на предыдущей итерации
[21:26] <fd> Мы знаем, какую вывели
[21:27] <fd> Мы берёмновой входящей перменной дополнительную к ней
[21:28] <fd> Смысл этого я объяснял выше - выведенная переменная стала 0, дополнительная к ней 0 была, значит, эт оединственная небазисная пара, и вводя ту, которую мы вывел ина прошлйо итерации, мы вернулись бы назад, поэтому вводим дополнительную к ней
[21:29] <fd> В мозгах наших максимизируем её, пока рост не хзаблокируется условием неотрицательности другой перменной
[21:29] <fd> когда заблокировался - блокирующую выводим из базиса
[21:29] <fd> вот.

29 марта 2006