Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

то в силу условий невырожденности выполнены также (m + n −1) из соотношений

где X = kfr , (k ≥ k1 ) , выполняются, то можно утверждать, что пары (X ,Y 1 ) составляют открытое ребро многогранника Ζ , лежащее

в H1 . Точка (X 1 ,Y 1 ) является концом этого ребра.

Докажем единственность этого ребра. Рассмотрим любое другое неограниченное ребро многогранника Ζ , например (X ,Y 0 ) , где X = kfl , (l ≠ r) , а Y 0 – крайняя точка множества Υ .

121

Такое ребро не принадлежит H1 в силу того, что либо условие

не выполняется. Теорема доказана.

Два открытых ребра многогранника Ζ называются смежными, если они имеют общий конец. Последовательность смежных открытых ребер из H s вместе с их концевыми точками называется

s -путем.

При решении задачи, рассмотренной в примере 2.2 (см. рис. 2.4 и 2.5), можно двигаться по следующему s -пути с началом в точке

(X 2 ,Y 1 ) :

– двигаемся вдоль неограниченного ребра (X ,Y 1 ) до точки

(X 1,Y 1 ) ;

–из точки (X 1,Y 1 ) продолжаем движение вдоль ребра (X 1 ,Y ) , то есть по прямой 1 в множестве Υ , попадаем в крайнюю точку

(X 1,Y 0 ) ;

–(X 1,Y ) является концом ребра (X ,Y 0 ) , где точки X Χ

принадлежат прямой 4, по этому ребру можно попасть в (X 0 ,Y 0 )

– конечную точку рассматриваемого s -пути.

Теорема 2.7. Пусть Z – крайняя точка Ζ и Z H s . Найдутся одно или два открытых ребра, лежащих в H s и имеющих Z своей

крайней точкой; Z является ситуацией равновесия в том и только в том случае, когда такое ребро единственное.

Доказательство. Положим, что Z – крайняя точка Ζ и Z H s . Возможны два случая.

1. Пусть (es ,Y ) ((bs , X ) −1) = 0 . Поскольку справедливы (m + n) соотношений

( fi , X ) ((ai ,Y ) −1) = 0 , i =1,..., m ,

122

точка Z = (X , Y ) – ситуация равновесия. Как было показано, при этом или (es ,Y ) = 0 , или (bs , X ) −1 = 0 , но не оба сомножителя равны нулю сразу.

имеющих Z своим концом, причем, как было показано, вдоль каждого из них нарушается в точности одно соотношение. Поэтому в H s будет лежать только то единственное ребро, вдоль которого

нарушается условие (bs , X ) −1 = 0 .

найдется такой индекс q , для которого выполнены сразу или оба соотношения

которого нарушается условие (aq ,Y ) −1 = 0 . При этом Z не явля-

123

ется ситуацией равновесия. На любом другом ребре Ζ , имеющем Z концевой точкой, не выполнено какое - либо из соотношений, определяющих H s .

Теорема доказана.

Доказанные выше теоремы гарантируют существование крайней точки Z , лежащей в H s . Начав с такой точки Z1 , можно двигаться

по ребру, лежащему в H s : или это ребро закончится в другой крайней точке Z2 , или это единственное неограниченное ребро, лежащее в H s . В первом случае или Z2 – ситуация равновесия, и процесс не может быть продолжен, или существует другое ребро с концом в Z2 , лежащее в H s , по которому можно продолжать двигаться. Процесс прекращается в следующих случаях, когда:

–попадаем на неограниченное ребро;

–достигаем ситуации равновесия, отличной от точки Z1 ;

–приходим в точку, в которой уже были.

Вернуться можно только в начальную точку пути, так как в противном случае имелась бы точка, к которой примыкают три ребра. Таким образом, начав с Z1 , возвращаемся в Z1 , или нет. В первом

случае путь называется замкнутым (рис. 2.6, а). Если путь не замкнут, то он заканчивается либо в ситуации равновесия (рис. 2.6, б), либо на неограниченном ребре (рис. 2.6, в).

Рис. 2.6. Возможные s-пути

124

Теорема 2.8. Пусть P – s -путь, содержащий неограниченное ребро F . Тогда на P лежит в точности одна ситуация равновесия. Ее можно вычислить, последовательно проходя путь P , начиная с ребра F . Общее число ситуаций равновесия конечно и нечетно.

Доказательство. Единственный s -путь P , начинающийся с F , должен закончиться в некоторой крайней точке, являющейся ситуацией равновесия (см. рис. 2.6, в). Отличный от P незамкнутый путь должен иметь две конечные точки (см. рис. 2.6, б), каждая из которых является ситуацией равновесия. Отсюда следует утверждение теоремы.

2.1.4.4. Алгоритм Лемке – Хоусона решения биматричных игр

p0 (X ) ={ f1 ,..., fm } . Составляем симплекс-таблицы.

Таблица A

125