методичка Теория игр 2014. Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014
 Скачать 1.28 Mb.
|
j j n j p j j n j , (20) где ) , ( ) 1 , ( 2 1 p p p p x – произвольная смешанная стратегия игрока A . В формуле (20) фактически записан выигрыш ) , ( j x H A игрока A , когда игрок применяет одну из своих n чистых стратегий ) ( j : ) 1 ( ) , ( 2 1 p a p a j x H j j A , n j , 1 (21) Наша задача определить максимум в формуле (20). Проще всего это сделать, построив график функции ) 1 ( 2 1 p a p a v j j на плоскости pOv . Указанное уравнение описывает на данной плоскости прямую линию, те. каждой чистой стратегии ) ( j игрока B соответствует своя прямая. Поэтому сначала нужно нанести на плоскость pOv все прямые вида ) 1 ( 2 1 p a p a v j j , n j , 1 . Затем для каждого значения p ( 1 0 p ) путем визуального сравнения соответствующих ему значений v на каждой из построенных прямых определяется и отмечается минимальное из них. В результате описанной процедуры получается ломаная, которая и является графиком функции ) 1 ( min 2 выделена жирной линией на рис. Эта ломаная как бы огибает снизу все семейство построенных n прямых, и поэтому ее называют нижней огибающей этого семейства. Верхняя точка построенной нижней огибающей определяет цену игры v и оптимальную стратегию игрока A : ) 1 , ( p p x (на рис. эта точка есть пересечение прямых, отвечающих l B и k B стратегиям игрока B ). Описанная процедура решения может рассматриваться как некоторый аналог максиминного подхода для игрока A при отсутствии седловой точки. v p * 0 v p (k) (l) (1) (2) 1 Рис Утверждение Лучшая стратегия игрока A против чистых стратегий игрока B лучшая вообще, т.к. ) , ( ) , ( y x H v j x H A A , Пример 4. Решить матричную игру с платежной матрицей 2 5 7 11 Сначала исследуем матрицу P на наличие седловой точки. 2 } 2 , 2 max{ v , 5 } 11 , 5 , 7 min{ v , те. седловой точки нет. Значит решение игры нужно искать в смешанных стратегиях. Вычисляем средние выигрыши игрока A по формуле (21), когда игрок B применяет одну из своих трех чистых стратегий 1 B : (я прямая p p p v 5 7 ) 1 ( 7 2 , 2 B : (я прямая p p p v 2 5 ) 1 ( 5 3 , 3 B : (я прямая p p p v 9 2 ) 1 ( 2 Приведенные выше три уравнения фактически можно получить при помощи умножения строки ) 1 , ( p p слева на столбцы матрицы P . Далее, строим все три полученные выше прямые на координатной плоскости pOv (см. рис, и находим их нижнюю огибающую. На выделенной огибающей находим аналитически координаты наивысшей точки. Из рис, видно, что эта точка является пересечением ой и ей прямых, поэтому оптимальное значение p ищем из системы уравнений p v p v 9 2 , 2 5 p p 9 2 2 5 В результате получаем решение 11 3 p , цена игры 11 Таким образом, оптимальная смешанная стратегия x игрока будет следующая 11 8 ; 11 3 x v * p * 0 v p (3) (1) (2) 1 2 5 7 Рис Опишем далее процедуру отыскания оптимальной смешанной стратегии игрока B . В зависимости от формы нижней огибающей здесь может представиться несколько случаев. 1. Нижняя огибающая имеет ровно одну наивысшую точку ) , ( v p а) Если 0 p , то это означает, что игрок A придерживается своей чистой стратегии А (см. риса. Тогда игроку B выгодно применять чистую стратегию, соответствующую номеру прямой (на риса это прямая ) ( j ), проходящей через точку ) , 0 ( v и имеющей наибольший отрицательный наклон. v * 0 v p ( j) 1 v * 0 v p ( j) 1 Риса Рис.7б б) Если 1 p , те. игрок A выбрал чистую стратегию А , то оптимальной для игрока B является чистая стратегия, соответствующая номеру прямой, проходящей через точку ) , 1 ( v и имеющей наименьший положительный наклон (см. рис.7б). в) Если 1 0 p , тов наивысшей точке нижней огибающей пересекаются как минимум две прямые, одна из которых (k-ая) имеет положительный наклона другая (l-ая) – отрицательный (см. рис.7в), и оптимальная смешанная стратегия игрока B получается, если положить q q k , q q l 1 , 0 j q для всех l k j , . Здесь ) ..., , , ( 2 1 n q q q y – это смешанная стратегия игрока B , а величина q есть решение уравнения ) 1 ( ) 1 ( 2 2 1 1 q a q a q a q a l k l k (22) 2. Нижняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии ) ( j игрока B , которая и является оптимальной для него (см. рис.7г). v * p * 0 v p (l) 1 (k) v * 0 v p ( j) 1 Рис.7в Рис.7г Вернемся к решению примера 4. Здесь игрок B обладает тремя стратегиями, поэтому его смешанная стратегия будет ) , , ( 3 2 1 q q q y . Так как прямые линии (2) и (3) на рис определяют наивысшую точку нижней огибающей, то, используя пункт в, следует принять 0 1 q , q q 2 , q q 1 3 ( 1 3 2 1 q q q ). Далее, из формулы (22) следует, что ) 1 ( 2 5 ) 1 ( 11 3 q q q q 11 Отсюда получаем следующее оптимальное решение 11 2 , 11 Проверка 11 49 11 / 2 11 / 9 0 2 5 7 11 3 2 11 8 11 3 ) ( ) , ( T A A y P x y x H v 1.5.2. РЕШЕНИЕ МАТРИЧНОЙ (ИГРЫ Пусть теперь игрок B имеет две стратегии 1 B и 2 B , и его смешанная стратегия определяется вектором ) , ( 2 1 q q y , 1 2 1 q q ; а игрок имеет m стратегий 1 A , …, m A . Тогда платежная матрица P имеет вид 2 1 22 21 12 Анализ такой игры во многом напоминает рассуждения, описанные для игры (2 n). Пусть ) , ( 2 1 q q y – произвольная смешанная стратегия игрока Тогда выигрыш игрока B в ситуации ) , ( y i , те. когда игрок придерживается своей чистой стратегии i A ( m i , 1 ), равен ) 1 ( ) ( ) , ( 2 1 q a q a y P i y i H i i T A , m i , 1 (23) Графиком функций ) , ( y i H A , определяемых формулой (23), являются m прямых линий на плоскости qOv . Рассмотрим верхнюю огибающую этих прямых, те. функцию ) 1 ( max ) ( 2 1 1 q a q a q H i i m i A . Эта функция будет выпуклой (как верхняя огибающая семейства выпуклых функций. Точка минимума q функции ) (q H A дает оптимальную смешанную стратегию ) 1 , ( q q y , а цена игры v будет определяться как ) 1 ( max min ) ( 2 1 1 1 0 q a q a q H v i i m i q A v * q * 0 v q 1 (3) (1) (2) 2 –1 v * q * 0 v q 1 1 4 3 (4) Риса Рис.8б Таким образом, на координатной плоскости qOv точка q будет абсциссой нижней точки полученной верхней огибающей (ломаной линии) (см. риса, которое и определяет оптимальную стратегию игрока B , а ординатой этой точки будет цена игры v . Отыскание оптимальной смешанной стратегии игрока A проводится по той же схеме, которая позволяет найти оптимальную стратегию игрока B в игре (2 n). Рассмотрим пример. Пример 5. Пусть платежная матрица P имеет следующий вид 1 2 0 3 2 1 1 Сначала проанализируем игруна наличие седловой точки 1 } 1 , 0 , 1 , 1 max{ v , 2 } 2 , 4 min{ v , v v седловой точки нет. Итак, решение будем искать в смешанных стратегиях. Вычисляем средние выигрыши игрока B по формуле (23), когда игрок A применяет одну из своих четырех чистых стратегий 1 A : (я прямая 1 5 ) 1 ( 1 4 q q q v , 2 A : (я прямая q q q v 3 2 ) 1 ( 2 , 3 A : (я прямая q q q v 3 ) 1 ( 0 3 , 4 A : (я прямая q q q v 1 ) 1 ( 1 Приведенные выше четыре уравнения могут быть также получены при помощи умножения строк матрицы P справа на столбцы Далее, наносим найденные прямые на координатную плоскость qOv см. рис.8б). Из рис.8б видно, что нижняя точка верхней огибающей выделена жирной линией) является точкой пересечения прямых (2) и (4). Решая систему , 1 , 3 2 q v q v получим решение 4 1 q , 4 5 v . Таким образом, оптимальной стратегией игрока B будет 4 3 , 4 Ищем далее оптимальную стратегию игрока A . Так как нижняя точка верхней огибающей лежала на пересечении (ой и (ой прямых, то смешанная стратегия игрока A будет иметь следующий вид ) , , , ( 4 3 2 1 p p p p x , 0 1 p , p p 2 , 0 3 p , p p 1 4 . Вычисляем средние выигрыши игрока A , когда игрок B придерживается одной из своих двух чистых стратегий 0 1 1 2 0 3 2 1 1 4 ) 1 0 0 ( ) 1 ( )) 1 ( , ( p p P x x H v T A , 3 2 ) 1 ( 2 p p p 1 ) 1 ( 2 1 0 1 2 0 3 2 1 1 4 ) 1 Отсюда имеем p p 1 3 2 , те. 4 1 p , 4 5 v . Таким образом, оптимальной смешанной стратегией игрока A будет 4 3 ; 0 ; 4 Приведем еще некоторые свойства (теоремы, полезные при отыскании решения игры. Теорема 1.5.1. Пусть ) ..., , , ( 2 1 m p p p x и ) ..., , , ( 2 1 n q q q y – оптимальные стратегии игроков A и B . Тогда для любого i ( m i , 1 ), при котором v y i H A ) , ( , имеет место равенство 0 i p , а для любого j ( n j , 1 ) такого, что ) , ( j x H v A , имеет место равенство Обратно, если 0 i p , то v y i H A ) , ( , а если 0 j q , то и v j x H A ) , ( (сравните со свойством 2 для оптимальных смешанных стратегий двух игроков. Чистая стратегия ( i ) ( m i , 1 ) игрока A (или ( j ) ( n j , 1 ) игрока B ) называется существенной или активной стратегией, если существует оптимальная стратегия ) ..., , , ( 2 1 m p p p x (или ) ..., , , ( 2 1 n q q q y ) этого игрока, для которой 0 i p ( 0 j q ). Из этого определения и предыдущей теоремы следует, что для любой существенной стратегии ( i ) игрока A и любой оптимальной стратегии y игрока B выполняется равенство в игре (см. равенства (11) и (а v y a y P i y i H T i T A ) ( ) ( ) ( ) , ( , б) где i a – i -ая строка матрицы Аналогичное равенство имеет место для любой существенной стратегии ( j ) ( n j , 1 ) игрока B и оптимальной стратегии x игрока A : v a x j P x j x H j T A ) ( ) , ( , в) где j a – j -ый столбец матрицы P 1.6. ДОМИНИРОВАНИЕ СТРАТЕГИЙ [3, гл, § 3-6], [4, гл, § 8], [6, гл, § 4]. Сложность решения матричной игры возрастает с увеличение размеров матрицы платежей P . Поэтому следует проанализировать матрицу P с целью сокращения ее размерности. При анализе платежной матрицы сразу же можно выделить стратегии, являющиеся дублирующими или заведомо невыгодными для сторон. Определение 1. Говорят, что смешанная стратегия x игрока доминирует его стратегию x в (игре, если для всех чистых стратегий игрока B выполняются неравенства j j a x a x , n j , 1 (24) Определение 2. Говорят, что чистая стратегия i A (или i ) игрока доминирует его чистую стратегию l A (или l ), если lj ij a a , Если указанное неравенство выше выполняется строго, тов этом случае стратегия i A доминирует строго стратегию l A . Тогда стратегию l A игроку A использовать ненужно и необходимо удалить соответствующую l -ую строку из платежной матрицы Определение 3. Аналогично, смешанная стратегия y игрока доминирует его смешанную стратегию y , если для всех чистых стратегий игрока A имеем y a y a i i , m i , 1 (25) Определение 4. Говорят, что чистая стратегия j B (или j ) игрока доминирует его чистую стратегию k B (или k ), если ik ij a a , Если указанное неравенство выполняется строго, тов этом случае стратегия j B доминирует строго стратегию k B . Тогда стратегию k B игроку B нет необходимости использовать и необходимо удалить соответствующий k -ый столбец из платежной матрицы Формулы (24) и (25) означают, что строка (столбец) матрицы должны быть не больше (не меньше) некоторой выпуклой линейной комбинации остальных строк (столбцов. Определение 5. Говорят, что в (игре i -ая стратегия дублирует j -ую стратегию, если jl il a a , для n l , 1 , или lj li a a , для Все дублирующие стратегии, кроме одной из них, нужно удалять из игры, и считать, что вероятности их выбора равны нулю. Определение 6. Стратегии x и x игрока A называются эквивалентными в игре, если для всех n j , 1 : j j a x a x , те. При этом выполняется равенство Аналогично для игрока Определение 7. Стратегии y и y игрока B называются эквивалентными в игре, если для всех m j , 1 : y a y a i i , те. При этом выполняется равенство Определение 8. Стратегия x ( y ) игрока A ( B ) доминируема, если существует стратегия x ( y ) этого игрока, которая доминирует x ( y ). Игроки A и B не должны использовать свои доминируемые стратегии в игре. Укажем здесь несколько теорем. Теорема 1. Если в игре стратегия x одного из игроков доминирует оптимальную стратегию x , то стратегия x также оптимальна. Теорема 2. Если в игре стратегия x одного из игроков оптимальна, то x – доминируема строго (те. для нее формулы (не выполняются. Теорема 3. Пусть в (игре i -ая строка ( j -ый столбец) матрицы P доминируема (доминируем) и пусть P – матрица, получаемая из матрицы P вычеркиванием ой строки (го столбца. Тогда справедливы следующие утверждения 1. A A v v (цены обоих игр совпадают. 2. Всякая оптимальная стратегия y игрока B (оптимальная стратегия x игрока A ) в игре с матрицей P является оптимальной ив игре с матрицей P 3. Если x ( y ) – оптимальная смешанная стратегия игрока A ( B ) в игре с матрицей P , то оптимальная смешанная стратегия x ( y ) игрока A ( B ) в игре с матрицей P получается из стратегии x ( y ) добавлением на i -ое ( j -ое) место в x ( y ) нуля. Приведем примеры, поясняющие указанные здесь определения и теоремы. Пример 6. Пусть платежная матрица P имеет следующий вид 3 3 4 2 6 4 3 7 3 6 5 1 6 4 3 7 4 4 2 Сначала проанализируем игруна наличие седловой точки 3 } 2 , 3 , 1 , 3 , 2 max{ v , 5 } 6 , 6 , 5 , 7 min{ v , v v седловой точки нет. Значит ищем решение в смешанных стратегиях. Стратегии 2 A и 4 A являются дублирующими, так какая и 4-ая строки матрицы P совпадают. Следовательно нужно удалить одну из этих строк, например 4-ую. В результате из P получим матрицу P : 3 3 4 2 3 6 5 1 6 4 3 7 4 4 2 5 5 3 2 Далее, видим, что стратегия 2 A доминирует стратегию 1 A , т.к. для всех элементов второй и первой строки выполнено j j a a 1 2 , Поэтому первую строку матрицы P нужно вычеркнуть, что приводит кВ матрице P третья строка доминируется выпуклой линейной комбинацией первой и второй строк вида 2 1 3 3 2 3 1 a a a , поэтому третью строку нужно отбросить. Линейная комбинация строк i a матрицы P вида k k a a 1 является выпуклой, если коэффициенты i этой линейной комбинации удовлетворяют свойствами. Аналогично для столбцов этой матрицы. Итак, от матрицы P приходим к матрице P : 3 6 5 1 6 4 3 7 3 2 4 3 2 1 A A P B B B B Видно, что третий столбец матрицы P строго доминируется вторым столбцом, поэтому третий столбец нужно отбросить и перейти кВ матрице IV P третий столбец доминируем как выпуклая линейная комбинация первого и второго столбцов вида 2 1 3 2 1 2 1 IV IV IV a a a , поэтому третий столбец нужно отбросить. В результате приходим к матричной игре V с матрицей V P , 5 1 3 7 3 2 2 у которой нет доминириуемых строки столбцов. Решая эту игру аналитически, получим ) 1 ( 5 3 ) 1 ( 7 p p p p v 2 1 p , те. оптимальной стратегией игрока A в игре V будет 2 1 , 2 Аналогично для игрока B имеем ) 1 ( 5 ) 1 ( 3 7 q q q q v 4 1 q , те. его оптимальной стратегией будет 4 3 , 4 1 ) ( V y . Цена игры здесь Проведем графическое решение игры IV с матрицей IV P и покажем его совпадение с предыдущим решением. По формуле (21) имеем 1 B : (я прямая p p p v 6 1 ) 1 ( 7 , 2 B : (я прямая p p p v 2 5 ) 1 ( 5 3 , 4 B : (я прямая p p p v 3 3 ) 1 ( 3 Полученные три прямые отображены на координатной плоскости pOv на рис. Далее, выделяем нижнюю огибающую данного семейства прямых и находим аналитически координаты наивысшей точки. Из рис, видно, что эта точка является пересечением ой и ой прямых, поэтому оптимальное значение p ищем из системы уравнений p v p v 2 5 , 6 1 p p 2 5 6 1 2 Отсюда получим 2 1 , 2 1 ) ( IV x , что совпадает с ) ( V x . Используя здесь только первую и вторую стратегии игрока B , получим такое же решение как и для матрицы V P : 0 , 4 3 , 4 1 ) ( IV y v * p * 0 v p (3) (1) (2) 1 1 5 7 3 Рис Таким образом, оптимальными стратегиями исходной игры будут следующие (на места удаленных (доминируемых) стратегий добавлены нули 0 , 0 , 2 1 , 2 1 , 0 x , 0 , 0 , 4 3 , 4 1 y и цена игры 4 v 1.7 ВПОЛНЕ СМЕШАННЫЕ ИГРЫ [2, гл, § 1], [3, гл, § 7], [4, гл, § 9]. Пусть все стратегии обоих игроков или хотя бы у одного из них будут активными (существенными) и при этом ни одна из существенных стратегий не является строго доминируемой. Такую ситуацию равновесия в игре принято называть вполне смешанной (те. хотя бы у одного из игроков все вероятности ) ( j i q p ненулевые по j i, ). Теорема Если матричная (игра является вполне смешанной и цена игры 0 v , то игра имеет единственное решение и квадратную матрицу ( n m ). При этом, оптимальные стратегии y x , и цена игры определяются последующим формулам T u uP uP x 1 1 ; T T T u uP u P y 1 1 ; T u uP v 1 1 , (26) где Комментарий к теореме если матрица P содержит отрицательные элементы, то ее цена игры может оказаться равной нулю. Тогда, чтобы использовать формулы (26), нужно изменить матрицу P , прибавив к ее элементам любое положительное число , такое, чтобы все элементы стали положительными. Этим мы гарантируем выполнение условия 0 v . В соответствии с леммой о масштабе, оптимальные стратегии для игры с новой матрицей P P будут такими же, как ив игре с матрицей Пример 7. Рассмотрим игру с матрицей вида 0 2 3 3 0 1 2 Убедимся, что здесь отсутствует седловая точка 0 } 0 , 1 , 1 max{ v , 2 } 3 , 2 , 3 min{ v , v v . Значит будем искать решение в смешанных стратегиях. Так как не все элементы матрицы P положительны, перейдем к новой матрице 1 P P , тогда 1 3 4 4 1 0 3 2 0 P и В этой матрице отсутствуют доминируемые строки и столбцы, иона является квадратной, поэтому для поиска оптимальных стратегий применим формулы (26). Для этого найдем обратную матрицу 1 ) ( P , применяя метод Гаусса (при помощи элементарных преобразований строк исходную матрицу приводим к единичной, а единичная матрица тем же преобразованиями приводится к обратной 1 0 0 0 1 0 0 0 1 1 3 4 4 1 0 3 2 0 0 0 1 0 1 0 1 0 0 3 2 0 4 1 0 1 3 4 0 2 1 0 1 0 1 0 0 5 0 0 4 1 0 1 3 4 0 5 2 5 1 0 1 0 1 0 0 1 0 0 4 1 0 1 3 4 0 2 1 0 3 4 5 2 1 5 1 1 0 0 0 1 0 0 3 4 0 2 1 0 3 4 5 7 11 5 1 1 0 0 0 1 0 0 0 4 0 2 1 0 3 4 4 / 5 4 / 7 4 / 11 5 1 1 0 0 0 1 0 0 0 1 0 2 1 0 3 4 4 / 5 4 / 7 4 / 11 5 1 ) ( 1 P Далее 4 1 , 20 3 , 20 1 0 2 1 0 3 4 4 / 5 4 / 7 4 / 11 1 , 1 , 1 5 1 ) ( 1 P u ; 20 9 1 1 1 4 1 , 20 3 , 20 1 ) ( 1 T u P u 9 20 v 9 11 1 v v ; 9 5 , 3 1 , 9 1 ) ( 1 v P u x ; 5 / 1 5 / 1 20 / 1 1 1 1 0 2 1 0 3 4 4 / 5 4 / 7 4 / 11 5 1 ) ( 1 T u P 9 4 , 9 4 , 9 1 ) ( 1 T T v u P y 1.8. РЕШЕНИЕ МАТРИЧНЫХ ИГР МЕТОДАМИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ [1, гл, § 5], [2, гл, § 1], [3, гл, § 8], [4, гл, § 6], [6, гл, § 5]. Рассмотрим матричную (игру с матрицей n m ij a P ) ( . Будем полагать, что цена игры 0 v . Это предположение всегда выполняется, если элементы ij a матрицы P неотрицательны, те. 0 ij a . Если в исходной матрице P есть отрицательные числа, всегда можно прибавить такое максимальное положительное число, при котором 0 ij a , j i, . При этом цена игры также увеличиться на это число (лемма о масштабе. Итак, пусть 0 v , что возможно если все элементы Посмотрим сначала на игру глазами игрока Из свойств оптимальных смешанных стратегий игроков следует, что при оптимальном поведении игрока A (те. когда он выбирает свою оптимальную стратегию ) ,..., ( 1 m p p x ) и любом поведении противника игрока B ) сумма его выигрыша не меньше, чем цена игры v , поэтому в случае выбора игроком B его чистых стратегий j B , n j , 1 можно записать следующие уравнения v j x H A ) , ( , те. v j P x T ) ( , n j , 1 (27) Иными словами выполняются соотношения , 1 v p a m i i ij n j , 1 ; ; 1 1 m i i p 0 i p , а) Из (а) следует, что , 1 1 m i i ij x a n j , 1 ; ; 1 1 v x m i i 0 i x , m i , 1 , (28) где v p x i i . Так как игрок A стремится максимизировать свой выигрыш, то задача поиска оптимального решения для игрока A в матричной игре сводится к решению следующей задачи найти величины 0 i x , удовлетворяющие системе ограничений , 1 1 m i i ij x a n j , 1 ; (29) такие, что их сумма минимальна min 1 ) ( 1 v x x F m i i (30) Рассмотрим теперь игру глазами игрока B . Если игрок B использует свою оптимальную стратегию ) ,..., ( 1 n q q y , а игрок A – одну из своих чистых стратегий i A , m i , 1 , то средний выигрыш ) , ( y i H A в игре будет не больше, чем цена игры, те. выполняются соотношения , 1 v q a n j j ij m i , 1 ; ; 1 1 n j j q 0 j q , n j , 1 , (31) которые с учетом замены v q y j j переходят в , 1 1 n j j ij y a m i , 1 ; ; 1 1 v y n j j 0 j y , n j , 1 (32) Так как игрок B стремится минимизировать свой проигрыш v , то задача поиска оптимального решения для игрока B сводится к решению следующей задачи найти величины 0 j y , n j , 1 , удовлетворяющие системе ограничений , 1 1 n j j ij y a m i , 1 ; (33) такие, что их сумма максимальна max 1 ) ( 1 v y y G n j i (34) Задача (29)-(30) называется прямой задачей линейного программирования, а задача (33)-(34) – двойственной задачей линейного программирования в матричной (игре. Решение этих задач может быть получено аналитически при помощи так называемого симплекс- метода. Итак, матричная (игра свелась к решению двух двойственных задач линейного программирования (29)-(30), (33)-(34), в которых v y G x F y x 1 ) ( max ) ( min , где v – это цена исходной матричной игры. Сформулируем кратко алгоритм симплекс-метода с использованием симплекс-таблиц. Симплекс-метод основан на утверждении о том, что линейная функция или ) ( y G ) задачи линейного программирования достигает своего оптимума (максимума или минимума) водной из угловых точек многогранника решений, который определяется неравенствами (29) или (33). Идея симплекс-метода состоит в направленном переборе угловых точек с последующим уменьшением значений целевой функции ) (x F для задачи на минимум (или увеличением значений целевой функции ) ( для задачи на максимум. Рассмотрим реализацию симплекс-метода для следующей общей задачи линейного программирования найти максимум (минимум) линейной функции n j j j x c x F 1 ) ( относительно n неизвестных 1 x , …, n x , удовлетворяющих системе ограничений, состоящей из m уравнений- неравенств вида , ) ( 1 i n j j ij b x a m i , 1 ; 0 j x , n j , 1 (35) В векторно-матричной форме это выглядит такс) при ограничениях b x A ) ( , 0 x , (37) где n m ij a A , T m b b b ) , ,.. ( 1 , T n x x x ) , ,.. ( 1 . Знаки в системе ограничений (35) (или (37)) встречаются в задачах на максимума знаки – в задачах на минимум. Возможны также и случаи, когда в системе ограничений типа (37) встречаются как знаки неравенств итак и знаки равенства " " Симплекс-метод применяется к канонической задаче линейного программирования, те. когда все ограничения на неизвестные являются ограничениями-равенствами. Чтобы перейти от ограничений вида (35), (37) к ограничениям-равенствам, нужно в каждое уравнение системы ограничений добавить по одной положительной переменной i n x , m i , 1 либо с коэффициентом 1 (в случае неравенства ), либо с коэффициентом 1 (в случае неравенства ). В результате этого задача линейного программирования примет следующий канонический вид найти max(min) ) ( 1 n j j j x c x F (38) при ограничениях-равенствах , ) ( 1 i i n n j j ij b x x a m i , 1 ; 0 j x , m n j , 1 (39) Таким образом, система ограничений вида (39) состоит из m уравнений с m n неизвестными. Для реализации симплекс-метода необходимо установить три основных элемента способ определения начального допустимого базисного решения правило перехода к лучшему (по сравнению с предыдущим) решению критерий проверки оптимальности найденного решения. Не теряя общности, будем считать, что система ограничений типа равенств для канонической задачи (38) имеет следующий вид b x A , 0 x , (40) где n m ij a A , T m b b b ) , ,.. ( 1 , T n x x x ) , ,.. ( 1 , Будем полагать, что ранг матрицы системы ограничений (40) совпадает с рангом расширенной матрицы этой системы, те. ) | ( ) ( b A r A r r . Если m r , то уравнения с номерами 1 r , …, являются линейными комбинациями предыдущих уравнений и их можно отбросить. В случае, если 2 r или 2 n , решение задачи (38) можно найти геометрически. Подробнее об этом можно почитать в [1]-[2]. Пусть m r . При этом считаем, что n r . Выберем какие-либо базисных переменных j x , m j , 1 в системе (40) и будем считать их главными (это можно определить через базисный ненулевой минор матрицы A ). Если рассматривать систему ограничений вида (39), тов этой системе в качестве базисных переменных можно взять новые дополнительные переменные i n x , m i , 1 , т.к. базисный минор при этих переменных совпадает с определителем единичной матрицы. Дальнейшие рассуждения будут касаться системы ограничений вида (40). Оставшиеся переменные в этой системе, а именно 1 m x , …, n x будут тогда свободными. Выразим базисные (основные) переменные j x , m j , 1 через свободные переменные, те. запишем их в виде n n i m m i i i x x x ) 0 ( , 1 ) 0 ( 1 , ) 0 ( , m i , 1 , (41) где свободные переменные 1 m x , …, n x могут принимать любые значения. Положив их равными нулю, получим частное решение системы (40): ) 0 ( i i x , m i , 1 ; 0 Отсюда получаем нулевое (начальное) базисное решение ) 0 ,... 0 , ,..., , ( ) 0 ( ) 0 ( 2 ) 0 ( 1 ) 0 ( m n m x (42) Решение (42) будет допустимым базисным решением, если все коэффициенты 0 ) 0 ( i , m i , 1 , иначе это решение будет недопустимыми тогда нужно заново выбирать другие базисные переменные. Пусть решение (42) допустимо. Функцию ) (x F в (38) нужно преобразовать так, чтобы базисные переменные были выражены через свободные. В результате этого функция ) (x F примет следующий вид n m j j j x x F 1 ) 0 ( ) 0 ( 0 ) ( , (43) где знак " " будет для задачи на минимума знак ”–” для задачи на максимум. При этом б б 1 ) 0 ( ) 0 ( 0 X C с m i i i (44) для задачи на минимум б, n m j , 1 ; (45) а для задачи на максимум j j j m i i ij j с X C c c б 1 ) 0 ( ) 0 ( , n m j , 1 (46) Здесь вектор б состоит из коэффициентов i c при базисных переменных i x в функции ) (x F , те. ) ,..., ( 1 б m с с C ; вектор-столбец б, те. состоит из значений допустимых базисных переменных i x (на начальном шаге вектор j X – это столбец, состоящий из коэффициентов ) 0 ( ij , m i , 1 при переменных j x в системе ограничений (41). Все коэффициенты системы (41), а также i c , ) 0 ( 0 и удобно свести в так называемую симплекс-таблицу, которая отражает ход решения, достигнутое решение и признак оптимальности на каждом шаге алгоритма симплекс-метода. Итак, начальная симплекс-таблица может принять следующий общий вид Симплекс-таблица 1 (й шаг б б б … k x … m x 1 m x … l x … n x 1 x с ) 0 ( 1 1 … 0 … 0 ) 0 ( 1 , 1 m … ) 0 ( , 1 l … ) 0 ( , 1 n ) 0 ( 1 … … … … … … … … … … … … … … k x с ) 0 ( k 0 … 1 … 0 ) 0 ( 1 , m k … ) 0 ( ,l k … ) 0 ( ,n k ) 0 ( k … … … … … … … … … … … … … … m x с ) 0 ( m 0 … 0 … 1 ) 0 ( 1 , m m … ) 0 ( ,l m … ) 0 ( ,n m ) 0 ( m ) 0 ( j ) 0 ( 0 0 … 0 … 0 ) 0 ( 1 m В первом столбце "б" симплекс-таблицы перечислены базисные переменные, во втором столбце "б" указаны коэффициенты i c при базисных переменных в функции ) (x F , в третьем столбце "б" приведены значения базисных переменных, что соответствует достигнутому решению ) 0 ( x (на начальном нулевом шаге) для исходной задачи. На пересечении строки столбцов, в которых выписаны базисные переменные i x ( m i , 1 ), можно заметить единичную матрицу. Это правило сохраняется для всех симплекс-таблиц. Далее идут столбцы " j X " ( n m j , 1 ): в них выписаны коэффициенты ) 0 ( ij , m i , 1 при остальных переменных (свободных или небазисных) в системе (41). Последний столбец ) ,..., ( ) 0 ( ) 0 ( 1 m определяет базисную переменную, которую нужно вывести из базиса. Прокомментируем последнюю строку таблицы. Здесь значение ) ( ) 0 ( ) 0 ( 0 x F , а значения ) 0 ( j , n m j , 1 определяют оптимальность достигнутого решения. Отметим, что у базисных переменных 0 ) 0 ( j , Укажем признак оптимальности достигнутого решения если на некотором шаге s все 0 ) ( s j , n j , 1 , то полученное допустимое базисное решение будет оптимальными максимум (минимум) функции ) (x F равен числу ) ( 0 s , те. Пусть на шаге s некоторые из коэффициентов ) (s j будут отрицательны. В этом случае достигнутое решение ) (s x не является оптимальным, поэтому следует перейти к новому допустимому базисному решению ) 1 ( s x , при котором значение функции ) (x F увеличится (для задачи на максимум) или уменьшится (для задачи на минимум. Укажем здесь алгоритм перехода к новой симплекс-таблице. Итак, из множества отрицательных коэффициентов ) (s j выбираем максимальный по модулю (если таких будет несколько, то берем первый из них. Пусть это будет ) ( s l . Индекс l тогда определяет некую свободную переменную l x , которую нужно сделать базисной. Соответствующий столбец l X в симплекс-таблице принято называть разрешающим столбцом. Далее, для каждой строки симплекс-таблицы определим ограничения на новую базисную переменную l x , чтобы выяснить за счет какой старой базисной переменной в базис вводится новая переменная l x . Ограничения ) ( s i , m i , 1 (по каждой базисной переменной) вычисляем последующему правилу 1) если ) ( s i и ) ( , s l i имеют разные знаки, то ) ( s i (вместо знака ” ” в самом правом столбце симплекс-таблицы можно ставить знак ” – ”); 2) если 0 ) ( s i и 0 ) ( , s l i , то ) ( s i ; 3) если 0 ) ( , s l i , то ) ( s i ; 4) если 0 ) ( s i и 0 ) ( , s l i , то 0 ) ( s i ; 5) если ) ( s i и ) ( , s l i имеют одинаковые знаки, то ) ( , ) ( ) ( s l i s i s i (47) Далее, определяется ) ( ) ( min s i i s k . Индекс k здесь указывает базисную переменную k x , которая выводится из базиса, и ее место займет новая переменная l x . Соответствующая этой переменной k -ая строка симплекс-таблицы называется разрешающей строкой. Элемент ) ( , s l k , стоящий на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом симплекс-таблицы. При переходе к новой симплекс-таблице поступаем следующим образом 1) все элементы разрешающей строки (кроме коэффициента с ) делим на разрешающий элемент ) ( , s l k ; 2) в столбцах j X , соответствующих базисным переменным, ставим 0 и 1, причем значение 1 – напротив своей базисной переменной, а значение 0 – напротив остальных базисных переменных 3) остальные элементы новой симплекс-таблицы вычисляются последующему правилу (правило Гаусса ) ( , ) ( , ) ( , ) ( , ) 1 ( , s l k s j k s l i s j i s j i , ) ( , ) ( ) ( , ) ( ) 1 ( s l k s k s l i s i s i (48) Получив на шаге s +1 новую симплекс-таблицу, вычисляем коэффициенты ее последней строки по формулам (44)-(46) (верхний индекс «0» в коэффициентах заменить на s +1). Далее, повторяем рассуждения относительно оптимальности достигнутого решения. Рассмотрим пример решения матричной игры при помощи указанного выше алгоритма симплекс-метода. Походу решения укажем способ отыскания решения для двойственной задачи линейного программирования. Пример 8. Определить при помощи линейного программирования решение игровой задачи с платежной матрицей 1 0 3 0 2 1 1 Определим верхнюю и нижнюю цены игры 1 } 1 , 1 , 1 max{ v , 1 } 1 , 2 , 3 min{ v , Значит, решение ищем в смешанных стратегиях игроков ) , , ( 3 2 1 p p p x A , ) , , ( 3 2 1 q q q y B , где 1 3 2 1 p p p , 1 3 2 Так как не все элементы матрицы P положительны, перейдем к новой матрице 1 P P , тогда 0 1 4 1 3 0 2 0 1 1 P P , и 1 A A v v – цена игры с новой матрицей Обозначив A i i v p x , 3 , 2 , 1 i и A j j v q y , 3 , 2 , 1 j , составим две взаимно-двойственные задачи линейного программирования (см. (29)-(30) и (33)-(34)): задача 1. Найти минимум линейной функции x A v x x x x F min 1 ) ( 3 2 1 при ограничениях 3 , 1 , 0 , 1 2 , 1 3 , 1 4 2 1 3 2 3 1 i x x x x x x x i (49) После приведения системы ограничений к каноническому виду, получим 6 , 1 , 0 , 1 2 , 1 3 , 1 4 6 2 1 5 3 2 4 а) Если переменные 4 x , 5 x , 6 x принять в качестве базисных, а переменные 1 x , 2 x , 3 x – свободными, то при 0 3 2 1 x x x получим первое базисное решение ) 1 , 1 , 1 , 0 , 0 , 0 ( ) 0 ( x , которое не является допустимым. Укажем здесь один из универсальных подходов исправления такой ситуации. Этот подход получил название метод искусственного базиса (или М-метод). Суть М-метода состоит в следующем (подробнее см. в [1], раздел 5.7). В каждое уравнение системы ограничений, дающее отрицательное значение компоненты в базисном решении, вводим новую искусственную переменную k x ( m l l k , , 1 ), которая имеет тот же знак, что и свободный коэффициент в правой части уравнения (см. (39)). Далее, все искусственные переменные делаем базисными. При этом линейная функция ) (x F (см. (36) и (38)) преобразится в функцию ) , ( x x T , которая для задачи на максимум имеет вид ) ( ) ( ) , ( 1 l x x M x F x x T ( M – произвольное большое положительное число, заведомо большее всех коэффициентов i c в ) (x F ), а для задачи на минимум Пусть входе решения ЗЛП для функции ) , ( x x T с искусственным базисом симплекс-методом было получено оптимальное решение ив этом решении все искусственные переменные оказались равными нулю, тогда исходная ЗЛП для функции имеет оптимальное решение (потому что 0 ) ( min 1 l x x M ). В противном случае исходная ЗЛП не имеет оптимального решения. Итак, используя М-метод, переходим от системы ограничений (а) к системе (б ; 9 , 1 , 0 , 1 2 , 1 3 , 1 4 9 6 2 1 8 5 3 2 7 4 3 б) где переменные 7 x , 8 x , 9 x – это искусственные переменные. Делаем эти переменные базисными, а остальные 6 , 1 , i x i – свободными. Тогда при 6 , 1 , 0 i x i получим начальное (нулевое) допустимое базисное решение ) 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 ( ) 0 ( x . В окончательном оптимальном решении * x нас будут интересовать только первые три компоненты вектора * x . Функция ) (x F здесь также преобразится и примет следующий вид ) ( ) ( 9 8 7 3 2 в) Изв) следует, что коэффициенты i c при искусственных переменных равны числу M ( 0 M очень большое число. На основании (49б-в) построим первую симплекс-таблицу. |