Сходимость метода для матричных игр

из "Введение в теорию, методы и экономические предложения задач о дополнительности "

Доказательство очевидно. Подчеркнем, что индекс г0 не меняется вдоль всего пути Лемке. Смена его означала бы, что одна из неизвестных исходной базисной пары покинула базис, что является признаком получения искомого решения и завершения работы алгоритма в целом. [c.18]
Лемма 4.1 позволяет сформулировать первый результат о существовании решения линейной задачи о дополнительности. [c.18]
Теорема 4.1. Если М 0, то система (3.1) при любом q имеет хотя бы одно допустимое базисное решение, удовлетворяющее условиям дополнительности. [c.18]
Строим путь Лемке, применяя описанные выше правила. По следствию 3.1 из теоремы 3.1 процесс прервется или по достижении решения исходной задачи, или по выходу на неограниченное ребро (луч) множества Р. Покажем, что последнее невозможно. В самом деле, если бы это было так, мы столкнулись бы с выполнением условий (4.1)— (4.3), где г0 = 1. Поскольку М О и z О, то w 0. Отсюда, в силу (4.3), Zi = Zi = О при всех г 1. Следовательно, zi — единственная изменяющаяся вместе с А неизвестная (наряду с компонентами w, . . . , wn). Но это значит, что конечный луч совпадает с начальным, что по следствию 3.1 невозможно. [c.18]
Обоснование следующего факта требует модификации схемы выбора начальной точки. [c.18]
Теорема 4.2. Биматричная игра Г (А, В) разрешима, и ее решение можно получить методом Лемке. [c.18]
Эта таблица последняя, так как соответствующее ей базисное решение (w (0,0,0 , , 1) допустимо и удовлетворяет условиям дополнительности. [c.20]

Вернуться к основной статье