Войти
Физика для игрСтатьи

Линейная задача о дополнительности

Автор:

Как известно, к решению линейной задачи о дополнительности сводятся многочисленные задачи моделирования механических систем со связями и контактами. При этом для решения задачи в настоящее время обычно применяется итерационный алгоритм Лемке или Данцига. Например, для методов динамики твердого тела, которое описано в документе:
http://www.cs.ubc.ca/grads/resources/thesis/Nov02/Michael_Cline.pdf необходимо решить LCP методом Лемке.

Линейной задачей о дополнительности называют задачу решения смешанной системы уравнений и нестрогих неравенств:
w = Mz + q (1)
w ≥ 0
q ≥ 0
w*q = 0,
в которой искомыми являются векторы w и z .

Алгоритм Лемке. Применение искусственной переменной.

Это итеративный метод, который работает, представляя искусственные переменные z0 так, что бы уравнение (1) превратилось в: w = Mz + e*z0 + q, где e = (1, 1, . . . , 1) (2) При снижении значения z0 значения неизвестных wi также будут уменьшаться.

Первая итерация алгоритма: Если вектор q не отрицателен, то решение тривиально: w = q; z = 0; и алгоритм прекращает свою работу. Иначе определяем z0 как абсолютный минимальный элемент (и его индекс t) вектора q. Это гарантирует, что w = Mz + e*z0 + q ≥ 0. Для нахождения начального базисного вектора заменяем w[t] на z0;

Итерации алгоритма: Решаем фундаментальную систему решений относительно базисного вектора. Определяем дополнительную переменную к покинувшей базис переменной (на первой итерации – w[t]) и определяем исходящую переменную, как неизвестную, которая первой убывая, достигает нулевого уровня. Если такой переменной не будет обнаружено, то алгоритм прекращает свою работу без решения. Иначе если эта переменная z0. Рассмотрим пример для пояснения: Пусть дано: q(-3,6,1) и
M
0 –1 2
2 0 –2
-1 1 0 

Найти такие z и w, которые удовлетворяют условиям LCP.

На первой итерации найдем минимальный элемент вектора q, он равен –3. z0 присваиваем 3, и приравниваем w1 = z0;
Решаем фундаментальную систему относительно z0,w2,w3:

w1 = z0 - z2 + 2z3 - 3
w2 = z0 + 2z1 - 2z3 + 6
w3 = z0 - z1 + z2 - 1

w1 = z0 - z2 + 2z3 - 3
w2 - w1 =  2z1 + z2 - 4z3 + 9
w3 - w1 = -z1 + 2z2 - 2z3 + 2

z0 = w1 + z2 - 2z3 + 3
w2 = w1 + 2z1 + z2 - 4z3 + 9
w3  = w1 -  z1 + 2z2 - 2z3 + 2

Теперь начинаем основные итерации алгоритма:
Следующий в базис будет вводиться переменная z1, которая является дополнительной к покинувшей базис переменной w1. Теперь посмотрим, как будут вести себя переменные при увеличении нашей входящей переменной z1. z0 меняться не будет, w2 будет увеличиваться, а w3 уменьшиться. Теперь, посмотрим до какого значения мы можем увеличивать значение z1, так, что бы не нарушались основные условия. Таким значением будет 2. И переменная, которая блокирует дальнейший рост, будет w3. Вот она и будет исходящей, поэтому w3 = z1;

z0 = w1 + z2 - 2z3 + 3
w2 = w1 + 2z1 + z2 - 4z3 + 9
w3 = w1 -  z1 + 2z2 - 2z3 + 2 | *2 + 2 уравнение

z0 = w1 + z2 – 0 + 2z3 + 3
w2 = w1 - 2w3 + 5z2 - 8z3 + 13
z1 = w1 - w3  + 2w2 - 2z3 + 2

Теперь вводим в базис z3, которая является дополнительной к w3. Блокирующая ее рост z1 покидает базис, z1 = z3, поскольку z0, w2, z1 будут уменьшаться. Теперь, посмотрим до какого значения мы можем увеличивать значение z3, так, что бы не нарушались основные условия задачи. Таким значением будет 1. И переменная, которая блокирует дальнейший рост, будет z1.
И решаем ФСР относительно z0,w2,z3:

z0 =                        w3  - z2 + z1 + 1
w2 = -w1  -          2w3 - 3z2 + 4z1 + 5
z3 = 0.5*w1 – 0.5*w3 + z2 – 0.5*z1 + 1

Теперь вводим в базис w1. Теперь посмотрим, как будут вести себя переменные при увеличении нашей входящей переменной w1. z0 меняться не будет, w2 будет уменьшиться, z3 будет увеличиваться . Теперь, посмотрим до какого значения мы можем увеличивать значение w1, так, что бы не нарушались основные условия. Таким значением будет 5. И переменная, которая блокирует дальнейший рост, будет w2. Вот она и будет исходящей, поэтому w1 = w2;
И решаем ФСР относительно z0,w1,z3:

z0 =                        w3  - z2 + z1 + 1
w1 = -w1  -          2w3 - 3z2 + 4z1 + 5
z3 = -0.5*w1 + 0.5*w3 –0.5*z2 + 1.5*z1 + 3.5

На последнем шаге z2 заменит z0, Решаем ФСР относительно z2, w1, z3:

Z2 =  w3  - z0 + z1 + 1
w1 = -w3 - 3z0 + z1 + 2
z3 =  -0.5*z0 +  z1 + 3

и поскольку нам удалось выкинуть переменную z0 из разряда базисных переменных, то алгоритм завершает свою работу с решением: w(2,0,0) и z(0,1,3)
Как вы догадались определение исходящей переменной, и решение ФСР влечет за собой неплохие ресурсные затраты. Поэтому в таком виде алгоритм Лемке лучше не использовать, тем не менее, он очень хорошо объясняет логику решения LCP.

21 марта 2006