_ 2Комбинаторные задачи Существо комбинаторных задач проиллюстрируем на примере опре- деления оптимальной последовательности обработки деталей. Пусть имеется два станка ( например токарный и фрезерный ) и n различных деталей, каждая из которых должна быть последова- тельно обработана на каждом из этих станков. Требуется опреде- лить, в какой последовательности нужно обрабатывать эти детали. Данная задача имеет характерные признаки задач на составление расписания с ограничением типа а , на последовательность опера- ций ( сначала токарная обработка, а затем фрезерование ) и с ог- раничением типа b на используемые ресурсы ( имеется только один токарный и один фрезерный станки ). Однако данные ограничения не являются чрезвычайно жесткими и допускают большую свободу выбора вариантов обработки деталей. Начать обработку можно с любой из n деталей, затем можно обработать любую из n-1 оставшихся деталей и т.д. Общее число вариантов n*(n-1)...1 = n! Однако может быть все варианты равноценны так что нет никакой проблемы? Оказывается, что это не так.От выбора порядка обработ- ки деталей зависят простои оборудования ( фрезерный станок осво- бодился , а токарная обработка очередной детали еще не законче- на) и перерывы в обработке деталей (закончена обработка очеред- ной детали, но фрезерный станок еще занят ). Очевидно, что из всех возможных вариантов обработки следует выбрать такой, который позволит закончить обработку всей партии деталей за кратчайшее время. Поэтому данная задача является за- дачей оптимизации. Однако ее решение чрезвычайно затруднено на- личием огромного числа вариантов обработки, что и заставляет от- нести данную задачу к задачам комбинаторного типа.  _ 2Задача коммивояжера Рассмотрим более простой вариант задачи об определении опти- мальной последовательности обработки деталей. Предположим, что n различных дета лей, пронумерованных от 1 до n, надо обработать на одном станке. При переходе от обработки детали i к детали k требуется время d 4ik 0 на переналадку станка, различное при разных i и k. Значения d 4ik 0 заданы в виде таблицы:  _ 2Таблица 1. ┌───┬──────────────────────────────────────────────────────────┐ │ i │ k │ │ ├──────────────┬──────────────┬─────────────┬──────────────┤ │ │ 1 │ 2 │ ... │ n │ ├───┼──────────────┼──────────────┼─────────────┼──────────────┤ │ 1 │ x │ d 41,2  0 │ ... │ d 41,n  0 │ ├───┼──────────────┼──────────────┼─────────────┼──────────────┤ │ 2 │ d 42,1  0 │ x │ ... │ d 42,n  0 │ ├───┼──────────────┼──────────────┼─────────────┼──────────────┤ │...│ ... │ ... │ ... │ ... │ ├───┼──────────────┼──────────────┼─────────────┼──────────────┤ │ n │ d 4n,1  0 │ d 4n,2  0 │ ... │ x │ └───┴──────────────┴──────────────┴─────────────┴──────────────┘ Требуется определить какой порядок обработки деталей, при ко- тором общее время , затрачиваемое на обработку будет минималь- ным. Поскольку возможно n вариантов обработки первой детали, n-1 второй и.т.д. , то общее число вариантов обработки будет равно n! Следовательно, эта задача относится к задачам комбинаторного типа. Поскольку время, затрачиваемое непосредственно на обработку всех деталей, будет одним и тем же при любом порядке обработки , то минимизация общего времени сводится к минимизации времени на переналадку станков. В математике задачи подобного типа получили название 2  _ 3з 1адачи  _ 1комивояжера 0. . Коммивояжер ( агент , рекламирующий товар 3  0своей фирмы ),выходящий из какого-либо города должен посетить n-1 дру- гих городов и 3  0вернуться к исходному пукту. Известны расстояния между городами d 4ik 0 , заданные в виде таблицы. Требуется устано- вить в каком порядке коммивояджер должен посещать города , чтобы общее суммарное расстояние было минимальным. Если несколько изменить формулировку задачи и не требовать возвращения к исходному пункту , то получим  _ 1незамкнутую . 0 задачу коммивояджера . Если несколько изменить формулировку задачи и начальный пункт , то получим полную аналогию с задачей о выборе оптимальной последовательности обработки деталей.  _ 2Представление задачи коммивояджера в виде графа. Очень точную задачу коммивояджера можно представить в виде графа G=(X,U) , вершины которого соответствуют городам , а дуги - дорогам , соединяющим города между собой. Каждой дуге , соеди- няющей города i и k , присваивается число d 4ik 0 , называемое дли- ной дуги и равное расстоянию между городами. Если из каждого го- рода имеется непосредственный путь в любой город без захода в промежуточные города , то каждые две вершины графа будут соеди- нены дугами в обоих направлениях. Получающийся при этом граф оказывается  _ 1полным . 0. В практических задачах полные графы встречаются редко. Если граф не полный , то его можно считать полным мысленно восстано- вив недостающие дуги и приписав им длину =  74 0. В таблице расстоя- ний соответствующие клетки удобно оставлять незаполненными. Элементарный путь в графе, проходящий через все вершины графа называется  _ 1гамильтоновым контуром . 0 . Как видим, задача коммивояд- жера сводится к нахождению кратчайшего гамильтонова контура или кратчайшего пути.  _ 2Методы решения задач коммивояджера.  2а). Применение метода Монте-Карло. Методом Монте-Карло называют статисическую процедуру, включа- ющую в себя приемы статистической выборки. Рассмотрим применение этого метода к решению задачи коммиво- яджера. Вершину 1 принимают за начальную и закладывают в урну жетоны с номерами от 2 до n. Тщательно перемешав жетоны , вытаскивают их по одному и записывают номера , например i 42 0,...,i 4n 0 . При этом получают гамильтонов контур 1,i 4r 0,...,i 4n 0,1. Подсчитывают длину этого контура и запоминают ее . После этого процедуру повторяют и если новый маршрут окажется хуже его тотчас забывают , а если он лучше , то забывают предыдущий , а новый запоминают. Проводя такую процедуру многократно , можно с высокой степенью вероят- ности рассчитывать на то, что удается найти если и не лучший , то достаточно хороший маршрут. Для проведения таких испытаний обычно используют ЭВМ , снаб- женные датчиком случайных чисел , что позволяет за короткое вре- мя просмотреть значительное число маршрутов.  2б). Сведение к задаче целочисленного линейного программирования. В графе G=(X,U) , соответствующем задаче коммивояджера , рассмотрим некоторый гамильтонов контур 1,i 42 0,...,i 4n 0,1 . Совокуп- ность дуг, входящих в гамильтонов контур , можно описать матри- цей  7( 0 a 411 0 . . . a 41n 7 ) 0  _ 2(10.26) A=(a)= │ . . . . . . . 7  0│  79 0 a 4n1 0 . . . a 4nn 7 0 в которой a 4ij 0 = ( 1 , если дуга (i,j) входит в рассматриваемый контур ( 0 , в противоположном случае  _ 2(10.27) Так как каждая вершина встречается в гамильтоновом контуре один и только один раз , то в каждую вершину обязательно входит и из каждой вершины обязательно выходит одна и только одна дуга. Это означает , что в матрице А в каждой строке и в каждом стобце должна стоять одна и только одна 1 , что математически запишется в виде  4n n  7S 0 a 4ij 0 = 1 ;  7  0  7S 0 a 4ij 0 = 1 ; 2  _(10.28)  5i=1 0  5j=1 С учетом этого условия , чтобы все a 4ij 0 были равны 0 или 1 , можно заменить требованием , чтобы все a 4ij 0 были неотрицательными целыми числами : ___ a 4ij 0  7. 0 0 , i,j = 1,n 2  _(10.29) E(a 4ij 0) = a 4ij 2  _(10.30) где Е(a 4ij 0) означает операцию взятия целой части числа a 4ij 0. Как видим , любой гамильтонов контур может быть описан матри- цей (10.26) , элементы которой a 4ij 0 удовлетворяют соотношением (10.28)- (10.30). Длина гамильтонова контура , равная сумме длин составляющих ее дуг , найдется так  4n n L=  7S 0  4  0  7S 0  4  0d 4ij 2 *  0a 4ij 2  _(10.31)  5i=1 4  5j=1 Нахождение гамильтонова контура минимальной длины сводится ___ таким об разом к нахождению значений переменных a 4ij 0 , i,j=1,n , удовлетворяющих линейным уравнениям и неравенствам (10-28) и (10-29) , условно целостности (10-30) и обращающих в минимум ли- нейную форму (10-31) , то есть к решениб задачи целочисленного линейного программирования. Следует однако учесть , что условия (10-28)-(10-30) , означа- ющие , что в каждую вершину входит и из каждой выходит только одна дуга , не обязательно определяют гамильтонов контур. Этим условиям будет отвечать и контур , проходящий не через все вер- шины , если в оставшихся вершинах образуются петли . Это соот- ветствует обращению в единицу некоторых элементов матрицы А , стоящих на главной диагонали, и не может быть исключено наложе- нием на a 4ij 0 добавочных ограничений вида ___ a 4ij 0 = 0 , при i=j , j=1,n 2 (10.32) Возможны также случаи , когда получается не один гамильтонов контур , два или более замкнутых контура , каждый из которых ох- ватывает только часть вершин , как показано , например , на ри- сунке для n=7 1 2 4  77 0----- 767 7 ^  72 0 / \  72 0 v / \  775 0----- 77 0 6 / \ 5 7 3  77 0  75 0--------- 7 7  _ 1Рис.1. Гамильтоновы контуры Если получилось именно такое решение , то вводится добавочное ограничение вида a 412  0+ a 423  0+ a 437 0 + a 471 0 <=3 запрещающее возникновение контура (1,2,3,7,1) и решают задачу заново совместно с этими ограничениями.  _ 2Применеие метода ветвей и границ к решению задач коммивояджера. Будем считать, что задача коммивояджера задана в виде матри- цы. Для конкретности зададимся численными значениями расстояний, приводимыми в таблице а) а)  _ 2Таблица 2. ┌───┬────────────────────────────────────────┬─────────┐ │ i │ j │ h 4i 0 │ │ ├────────┬───────┬───────┬───────┬───────┤  4  0 │ │ │ 1 │ 2 │ 3 │ 4 │ 5 │ │ ├───┼────────┼───────┼───────┼───────┼───────┼─────────┤ │ 1 │ x │ 7 │ 7 │ 2 │ 4 │ 2 │ ├───┼────────┼───────┼───────┼───────┼───────┼─────────┤ │ 2 │ 6 │ x │ 2 │ 4 │ 1 │ 1 │ ├───┼────────┼───────┼───────┼───────┼───────┼─────────┤ │ 3 │ 6 │ 1 │ x │ 9 │ 2 │ 1 │ ├───┼────────┼───────┼───────┼───────┼───────┼─────────┤ │ 4 │ 2 │ 3 │ 8 │ x │ 5 │ 2 │ ├───┼────────┼───────┼───────┼───────┼───────┼─────────┤ │ 5 │ 6 │ 1 │ 2 │ 5 │ x │ 1 │ └───┴────────┴───────┴───────┴───────┴───────┴─────────┘  7S 0 h 4i 0= 7 Для получения оценки снизу длин множества всех гамильтоновых контуров воспользуемся тем , что в каждый гамильтонов контур входит только по одному элементу из каждой строки и из каждого столбца матрицы расстояний . Поэтому если элементы любой строки или любого столбца уменьшить на какое либо число, то на это же число уменьшается длины всех гамильтоновых контуров. На этом свойстве основан метод привидения матрицы расстояний. Приведение матрицы может производиться по строкам и по столб- цам. Приведение матрицы расстояний по строкам заключается в том что из элементов каждой строки i вычитается наименьший элемент этой строки, обозначаемый h 4i 0. При этом длины всех гамильтоновых контуров уменьшаются на сумму вычтенных из каждой строки чисел, то есть на велечину  7S 0 h 4i 0 , оставаясь в то же время неотрицатель-  5i ными. Поэтому велечина  7S 0 h 4i 0 , равная в рассматриваемом примере  5i 7, дайт некоторую оценку снизу длин всех гамильтоновых контуров. Полученная оценка может быть улучшена путем повторного приведе- ния матрицы расстояний по столбцам. При этом из элементов каждо- го столбца j приведенной по строкам матрицы расстояний вычитает- ся наименьший элемент этого столбца, обозначаемый g 4i 0. Сумма выч- тенных при этом чисел  7S 0 g 4i 0 = 1.  5j Уточненая оценка снизу длин гамильтоновых контуров  4^ g =  7S 0 h 4i 0 +  7S 0 g 4j 0 = 7+1 = 8  5i j Получаемая после приведения по строкам матрица расстояний бу- дет иметь вид:  _ 2Таблица 3. ┌───┬──────────────────────────────────────────────────┐ │ i │ j │ │ ├──────────┬─────────┬─────────┬─────────┬─────────│ │ │ 1 │ 2 │ 3 │ 4 │ 5 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 1 │ x │ 5 │ 5 │ 0 │ 2 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 2 │ 5 │ x │ 1 │ 3 │ 0 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 3 │ 5 │ 0 │ x │ 8 │ 1 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 4 │ 0 │ 1 │ 6 │ x │ 3 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 5 │ 5 │ 0 │ 1 │ 4 │ x │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ g │ 0 │ 0 │ 1 │ 0 │ 0 │ └───┴──────────┴─────────┴─────────┴─────────┴─────────┘ 5  0  7S 0 g 4j 0= 1  5j а после приведения и по столбцам примет вид : ┌───┬──────────────────────────────────────────────────┐ │ i │ j │ │ ├──────────┬─────────┬─────────┬─────────┬─────────│ │ │ 1 │ 2 │ 3 │ 4 │ 5 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 1 │ x │ 5 │ 4 │ 0 │ 2 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 2 │ 5 │ x │ 0 │ 3 │ 0 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 3 │ 5 │ 0 │ x │ 8 │ 1 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 4 │ 0 │ 1 │ 5 │ x │ 3 │ ├───┼──────────┼─────────┼─────────┼─────────┼─────────┤ │ 5 │ 5 │ 0 │ 0 │ 4 │ x │ └───┴──────────┴─────────┴─────────┴─────────┴─────────┘ Метод приведегия матрицы расстояний будем применять и далее для получения оценок снизу различных подмножеств множества га- мильтоновых контуров. Рассмотрим теперь способ разбиения множества гамильтоновых контуров на подмножества. Возьмем некоторую дугу (i,j). К перво- му подмножеству отнесем все гамильтоновы контуры , в которые эта дуга входит. Обозначим это множество [(i,j)]. Ко второму мно- жеству отнесем все гамильтоновы контуры 5  0в которые дуга (i,j) не входит. Это множество обозначим [(i,j)]. ____ Таблицы расстояний для множества [(i,j)] легко получить, если учесть что включение дуги (i,j) в гамильтонов контур исключает возможность включения других дуг, стоящих в i строке и j столб- це. Следовательно, таблица расстояний для множества [(i,j)] по- лучается из первоначальной таблицы вычеркиванием i строки и j столбца. Для того чтобы получить таблицу расстояний для множества ____ [(i,j)] следует в первоначальной таблице запретить движение по дуге (i,j) положив ее длину =  74 0. Этот запрет движения по дуге (i,j) будем отмечать крестом в соответствующей клетке первона- чальгой таблицы. Теперь возникает вопрос какую дугу положить в основу разбие- ния множества маршрутов на подмножества? Заметим прежде всего, ____ что по количеству элементов множества [(i,j)] и [(i,j)] не оди- наковы. Общее число гамильтоновых контуров в задаче с n городами равно (n-1)! . Если мы зафиксировали дугу (i,j) то есть уже выб- рали две вершины, то имеется n-2 cпособа выбрать третью, n-3 четвертую и т.д. Следовательно , имеется (n-2)! гамильтоновых контуров, включающих дугу (i,j) а значит (n-1)!-(n-2)!=(n-2)(n-2)! гамильтоновых контуров не включающих ____ дугу (i,j) . Поэтому при n>2 множество [(i,j)]. А поскольку мно- жество с меньшим числом элементов исследовать проще то в качест- ве дуги (i,j) следует брать такую при которой множество [(i,j)] ____ имеет меньшую оценку чем множество [(i,j)]. Из множества дуг удовлетворяющих этому условию следует отдать предпочтение той которая дает наибольшую разницу в оценках для ____ множеств [(i,j)] и [(i,j)]. Если в качестве дуги (i,j) брать такую у которой в приведен- ной таблице d 4ij 0 не = 0 то для группы [(i,j)] оценка снизу воз- растает на d 4ij 0 поскольку заранее известно что эта дуга войдеи во все гамильтоновы контуры. Она может еще возрасти если таблица при вычеркивании i строки и j столбца будет допускать дальнейшее приведение. В то же время при замене элемента d 4ij 0 на  74 0 таблица ____ решений остается приведенной то есть оценка снизу для [(i,j)] не возрастает. Следовательно меньшее значение оценки будет для мно- ____ жества [(i,j)] что нежелательно. Поэтому в качестве дуги (i,j) надо брать такую, у которой в приведенной таблице расстояний d 4ij = 0. Но таких дуг несколько. Какую же из них выбрать? Очевидно ту ____ для которой увеличение оценки для множества [(i,j)] будет наи- большим так как при этом получится наибольшая разница в оценках ____ для множеств [(i,j)] и [(i,j)]. Обозначим увеличение оценки множеств [(i,j)] через (i,j). Обозначение этой велечины получаем путем сложения наименьших чи- сел в i строке и j столбце. Обратимся вновь к рассматриваемому примеру. Для последней таблицы значение (i,j) получаются равными (1,4)=2+3=5 (2,3)=0 (2,5)=1 (3,2)=1 (4,1)=6 (5,2)=0 (5,3)=0 _____ Наибольшее увеличение оценки для группы [(i,j)] получается для дуги (4,1). Исключая четвертую строку и первый столбец из приведенной таблицы приходим к таблице представляющей собой таб- лицу расстояний для множества [(4,1)] в) ┌───┬───────────────────────────────────────┬─────────┐ │ i │ j │ h 4i 0 │ │ ├─────────┬─────────┬─────────┬─────────┤  4  0 │ │ │ 2 │ 3 │ 4 │ 5 │ │ ├───┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ 1 │ 5 │ 4 │ x │ 2 │ 2 │ ├───┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ 2 │ x │ 0 │ 3 │ 0 │ 0 │ ├───┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ 3 │ 0 │ x │ 8 │ 1 │ 0 │ ├───┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ 5 │ 0 │ 0 │ 4 │ x │ 0 │ ├───┼─────────┼─────────┼─────────┼─────────┼─────────┤ │g 4i  0│ 0 │ 0 │ 3 │ 0 │ 1 │ └───┴─────────┴─────────┴─────────┴─────────┴─────────┘ При получении подобных матриц нужно строго следить за тем чтобы не могло получиться контуров не являющихся гамильтоновым. Поскольку дуга (4,1) уже введена в намечаемый гамильтонов кон- тур, то в таблице в) нужно наложить запрет на дугу (1,4) отметив клетку (1,4) крестом х так как дуга (1,4) совместно с дугой (4,1) образуют контур. В таблице г) дана приведенная таблица расстояний с увеличени- ем оценки  2  0q=2+3=5  4^ q=  7S 0 h 4i 0 +  7S 0 g 4i 0 = 2 + 3 = 5  5i i ┌───┬───────────────────────────────────────┐ │ i │ j │ │ ├─────────┬─────────┬─────────┬─────────│ │ │ 2 │ 3 │ 4 │ 5 │ ├───┼─────────┼─────────┼─────────┼─────────┤ │ 1 │ 3 │ 2 │ x │ 0 │ ├───┼─────────┼─────────┼─────────┼─────────┤ │ 2 │ x │ 0 │ 0 │ 0 │ ├───┼─────────┼─────────┼─────────┼─────────┤ │ 3 │ 0 │ x │ 5 │ 1 │ ├───┼─────────┼─────────┼─────────┼─────────┤ │ 5 │ 0 │ 0 │ 1 │ x │ └───┴─────────┴─────────┴─────────┴─────────┘ Это приведенная по строкам и столбцам таблица для множества [(4,1)]. Для таблицы г) велечины равны (1,5)=2 (2,3)=0 (2,4)=1 (2,5)=1 (3,2)=1 (5,2)=0 (5,3)=0 ____ Наибольшее увеличение оценки для группы [(i,j)] начинается для дуги (1,5) которую также введем в намечаемый гамильтонов кон- тур, получая цепочку (4,1,5). Исключая первую строку и пятый столбец из матрицы г) приходим к таблице д) для множества [(4,1),(1,5)] в которой необходимо наложить запрет на дугу (5,4) образующую контур с участком (4,1,5). д) ┌───┬─────────────────────────────┐ │ i │ j │ │ ├─────────┬─────────┬─────────│ │ │ 2 │ 3 │ 4 │ ├───┼─────────┼─────────┼─────────┤ │ 2 │ x │ 0 │ 0 │ ├───┼─────────┼─────────┼─────────┤ │ 3 │ 0 │ x │ 5 │ ├───┼─────────┼─────────┼─────────┤ │ 5 │ 0 │ 0 │ х │ └───┴─────────┴─────────┴─────────┘ Полученная таблица является приведенной. Поэтому для нее сра- зу же находим значения (i,j). (2,3)=0 (2,4)=5 (3,2)=5 (5,2)=0 (5,3)=0 Как видим наибольшее значение (i,j) получились равными для дуг (2,4) и (3,2). Поэтому обе эти дуги можно отнести к намечае- мому гамильтоновому контуру получая таким образом последователь- ность дуг (3,2),(2,4),(4,1), (1,5) для замыкания которой нехвата- ет лишь дуги (5,3). Добавляя эту дугу получаем предполагаемый оп- тимальный контур (3,2,4,1,5,3) длиной 13. ____ Анализируя нерассмотренные ранее подмножества [(4,1)], ___ ___ [(4,1),(1,5)],[(4,1),(1,5),(2,4)], убеждаемся что их оценки снизу больше 13 так что эти подмножества не могут содержать гамильтоно- ва контура короче найденного. Следовательно дальнейшая проверка не нужна и получаемый контур является оптимальным. Дерево разбиений строящееся по ходу решения задачи будет иметь вид: (U)  28  16 0 / \  15  214 0 ___/ \  213 [4,1] [4,1]  12 0 / \  10  215 0___/ \  213 [1,5] [1,5]  15 0 / \  10  218 0 ___/ \  214 [2,4] [2,4]  _ 1Рис.2 Дерево разбиений  _ 2Теория игр. Ранее все задачи принятия решений нами формулировались и ре- шались в предположеии наличия  _ 1полной . 0 информации. Их можно отнес- ти к совокупности задач принятия решений в условиях  _ 1определен-  _ 1ности. . 0 Ограниченность или неточность информации о задаче приводит к двум новым типам ситуаций в которых приходится принимать решения 1) принятие решений в условиях  _ 1риска . 0 2) принятие решения при наличии  _ 1неопределенности. В первом случае степень неполноты данных выражается через функцию распределения вероятностей, во втором случае существова- ния подобных функций не гарантируется. Другими словами с точки зрения наличия исходных данных  _ 1определенность . 0 и  _ 1неопределенность представляют два крайних случая, а риск определяет промежуточную ситуацию. Из-за недостаточности данных часто используются противоречи- вые друг другу подходы к задачам принятия решения и оценке их результатов. При полной определенности критерий максимума прибы- ли или минимума затрат является почти универсальным. Напротив для ситуаций с риском или неопределенностью существует ряд воз- можных критериев. Например в условиях риска иногда целесообразна максимизация  _ 1ожидаемой . 0 прибыли, но встречаются случаи когда это неверно. Другие критерии образууют целый спектр от максимально "пессимичных" до максимально "оптимичных". Положение усложняется в условиях неопределености. В большинстве задач принятия решений требуется выбирать наи- лучший способ действия из некоторого множества ( возможно беско- нечного ) допустимых альтернатив. Это было рассмотрено нами ра- нее. Ни в одном из рассмотренных случаев не предполагалось, что решения принимаются в уславиях когда сама система стремится "по- мешать" лицу принимающему решение (ЛПР). Предположим, что неко- торое лицо принимает решение в зависимости будет дождь или нет. В этом случае природа не будет восприниматься как недоброжела- тельный противник. В процессах принятия решений при наличии неопределенности су- ществуют ситуации конкуренции, когда два или более участника на- ходятся в конфликте и каждый стремится как можно больше выиграть у других. Эти ситуации отличаются от обычных процессов принятия решений в условиях неопределенности тем что принимающему решение противостоит  _ 1мыслящий . 0 противник. Теория в которой рассматривают- ся подобные задачи принятия решений известна как  _ 1теория игр . 0 . В теории игр противников принято называть  _ 1игроками . 0. Каждый игрок имеет некоторое множество (конечное или бесконечное) воз- можных выборов, называемых  _ 1стратегиями . 0.  _ 1Результаты . 0 или  _ 1платежи . 0 в игре задаются функциями, зависящимим от стратегий каждого из игроков. Игры с двумя игроками в которых выигрыш одного из них равен проигрышу другого называется  _ 1играми  3д 1вух лиц с нулевой суммой  . 0.  _ 2Пример . 0 : для иллюстрации определений  _ 1игры двух лиц с нулевой  _ 1суммой . 0 рассмотрим игру на совпадение сторон монеты, в которой два игрока А и B выбирают герб (Г) или решку (Р). Если результа- ты совпадают ( то есть Г и Г для Р и H), то игрок А получает 1руб. от игрока В. В противном случае игрок А платит 1руб. игро- ку В. В этой игре каждый из игроков иимеет две стратегии ( Г и Р ) которые составляют матрицу игры размерами 2 х 2 представляющую выигрыш игрока А. Г Р ┌─────────┐ Г │ 1 -1 │ Р │ -1 1 │ └─────────┘ Оптимальное решение в такой игре может потребовать от игроков выбора  _ 1чистых стратегий . 0 ( то есть либо Г либо Р ) или какой-ни- будь комбинации  _ 1смешанных стратегий . 0.  _ 2Матричные игры.  2Принцип обеспечения гарантированного результата. Простейшей матричной игрой является игра с двумяучастниками. Для упрощения математического описания игры вводится понятие  _ 1стратегии . 0 представляющей собой исчерпывающий план проведения иг- ры каждым из игроков. Каждая пара стратегий ( по одной для каж- дого игрока ) определяет  _ 1партию . 0 игры и соответствию платежа каж- дому игроку. Рассмотрим матричные игры  _ 1с нулевой суммой . 0 когда выигрыш од- ного игрока в точности равен проигрышу другого. Используя понятие стратегии можно получить математическую мо- дель игровой ситуации. Назовем одного игрока максимизирующим (М) а другого минимизирующим (m). Каждый из них имеет соответственно конечное число стратегий l и n. Стратегии обозначаются числами i=1,2,...,l; j=1,2,...,n причем пара стратегий i и j определяют некоторый  _ 1платеж . 0 a 4ij 0 . Условно считается что если a 4ij 0 > 0 то вы- игрывает максимизирующий и проигрвает минимизирующий. Перечисле- ние всех возможных стратегий определяет матрицу платежей  7( 0 a11...a1n 7 ) A=(a 4ij 0 ) = │ ......... │ i=1,2,...,l; j=1,2,...,n  79 0  7  0al1...aln 7 0 где каждая строка - стратегия максимизирующего игрока, а столбец - минимизирующего. В дальнейшем для удобства будем как правило рассматривать платежные матрицы имеющие только положительные элементы, что формально соответствует постояному выигрышу максимизирующего иг- рока. Такую матрицу можно получить из исходной, если к каждому ее элементу добавить некоторое положительное число большее моду- ля минимального отрицательного числа. В этом случае максимизиру- ющий игрок как бы до начала игры выплачивает минимизирующему иг- року некоторую сумму для уравнивания шансов в игре. Для каждого из игроков возникает задача о рациональном выборе своих стратегий. Решение этой задачи осуществляется 3  0в соответс- твии 3  0с 3  _ 1принципом обеспечения гарантированного результата . 3  0( с принципом минимакса ), согласно которому каждый из игроков выби- рает свои стратегии в предположении сто противник действует оп- тимально. При любой стратегии i максимизирующий игрок может по- лучить по меньшей мере платеж min a 4ij 0, где минимум берется j по всем стратегиям минимизирующего игрока. Максимизирующий игрок за счеи рационального выбора своей стратегии может обеспечить себе гарантированный платеж  _v . = max min a 4ij  5i j Аналогичным образом при любой стратегии j которую может выб- рать минимизирующий игрок, его 4  0проигрыш будет не больше max a 4ij 0.  5i За счет рационального выбора своей стратегии минимизирующий иг- рок может снизить свой проигрыш до велечины _ v = min max a 4ij  5j 0  5i Велечина v называется  _ 1нижней ценой игры . 0, или  _ 1максимином . 0. Стратегия максимизирующего игрока при которой реализуется платеж v называется максиминной стратегией. Если максимизирующий игрок придерживается максиминной стратегии, то при любом поведении противника ему гарантирован выигрыш не меньший v. Велечина v называется  _ 1верхней ценой игры . 0, или  _ 1минимаксом . 0. Со- ответствующая ей стратегия минимизирующего игрока называется ми- нимаксной стратегией. Если минимизирующий игрок придерживается минимаксной стратегии, то ему гарантирован проигрыш не больший v. Иными словами  _ 1принцип обеспеченного гарантированного резуль-  _ 1тата . 0 заключается в выборе игроками максиминной и минимаксной стратегии соответственно.Обычно максиминную и минимаксную стра- тегии называют общим термином  _ 1"минимаксные стратегии". . 0 Рассмотрим платежную матрицу, представленную в виде: ┌───────┬───────────────────────────────────────┬─────────┐ │ i │ j │ min a 4ij 0 │ │ ├─────────┬─────────┬─────────┬─────────┤  5j 0  4  0 │ │ │ 1 │ 2 │ 3 │ 4 │ │ ├───────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ 1 │ 3 │ 7 │ 7 │ 2 │ 2 │ ├───────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ 2 │ 8 │ 1 │ 5 │ 6 │ 1 │ ├───────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ 3 │ 7 │ 4 │ 6 │ 5 │ 4 │ ├───────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │max a 4ij 0│ 8 │ 7 │ 7 │ 6 │ │ │  5i 0  4  0│ │ │ │ │ │ └───────┴─────────┴─────────┴─────────┴─────────┴─────────┘ Нетрудно видеть, что в данном примере _  _v . = 4 = max min a 4ij 0 < min max a 4ij 0 = 6 = v (1)  5i j j i _ Оказывается что общим случаем между v и  _v . имеет место соотно- шение _  _v . = max min a 4ij 0 <= min max a 4ij 0 = v  5i j j i _ Действительно пусть  _v .=max min a 4ij 0= a 4rs 0,а v=max min a 4ij 0= a 4av 0.  5i  0  5j  0  5j  0  5i Элемент a 4rs 0 является минимумом r строки ; следовательно a 4rs >= a 4rb 0 ( b не равно s). С другой стороны a 4ab 0 является максимумом b столбца, то есть a 4rb  0<= a 4ab 0 или a 4rs  0<= 4  0a 4rb  0<= a 4ab 0 , что дока- зывает соотношение (1).  _ 2Оптимальные стратегии и их свойства. Рассмотрим случай когда в (1) реализуется равенство _  _v . = max min a 4ij 0 = min max a 4ij 0 = v (2)  5i j j i В этой ситуации максимизирующий игрок может выбрать такую стратегию чтобы получить по крайней мере выигрыш равный  _v .. С другой стороны минимизирующий игрок при рациональном выборе _ стратегии может проиграть не более v = v. Таким образом у игро- ков имеются такие стратегии i 5* 0 и j 5* 0, что a 4i 5* 4j 5* 0=v;  5  0a 4ij 5* 0<=a 4i 5* 4j 5* 0<=a 4i 5* 4j 0, для любого i,j (3) В данном случае максимизирующий игрок должен выбрать страте- гию i ,так как в противном случае его выигрыш оказывается равным a 4ij 5* 0 , что не превосходит a 4i 5* 4j 5* 0. Аналогично этому минимизирующий игрок должен выбрать страте- гию 5  0j 5* 0 так как в противном случае его проигрыш может оказаться больше a 4ij 0 . Стратегии i 5* 0,j 5* 0 называется  _ 1оптимальными . 0, причем a 4i 0* 4j 0* называ- ется  _ 1се . 0дловой точкой платежной матрицы, а v=a 4i 0* 4j 0* -  _ 1ценой игры. . 0 Следует отметить, что в игре с седловой точкой если один из игроков придерживается своей оптимальной стратегии, а другой знает об этом, то второй игрок не может ухудшить результата пер- вого. Исследуем случай когда _ v = max min a 4ij 0 < min max a 4ij 0 = v ─  5i j  0  5 j i Соответствующая платежная матрица приведена в виде таблицы : ┌──────┬───────────────────┬─────────┐ │ i │ j │ h 4i 0 │ │ ├─────────┬─────────┤ │ │ │ 1 │ 2 │ │ ├──────┼─────────┼─────────┼─────────┤ │ 1 │ 5 │ 1 │ 1 │ ├──────┼─────────┼─────────┼─────────┤ │ 2 │ 3 │ 4 │ 3 │ ├──────┼─────────┼─────────┼─────────┘ │max a │ 5 │ 4 │ │  4ij 0│ │ │ └──────┴─────────┴─────────┘ _ причем v= max min a 4ij 0 = 3 v = min max a 4ij 0 = 4  5i j j i то есть у максимизирующего игрока имеется стратегия (i=2) при которой гарантированный выигрыш составляет v=3 , в то время как у минимизирующего игрока имеется стратегия (i=2) которая гаран- тирует ему проигрыш _ _ не превосходящий v = 4. Так как v <> v то решение игры в смысле рассмотренном выше, отсутствуют. _ Зная что v=4 максимизирующий игрок будет стремиться полуить выигрыш больший  _v .=3 например за счет применения 1й стратегии, когда возможен выигрыш  _v .=5. Точно также минимизирующий игрок бу- _ дет пытаться снизить свой платеж с v=4 до меньших значений, так как  _v .=3 , применяя например стратегию j=1 поэтому в данном слуае выигрыш максимизирующего игрока и проигрыш минимизирующего в каждой партии будет находиться между 3 и 4. Однако если миними- зирующий игрок будет знать что его противник сприменит 1ю стра- тегию, то за счет использования стратегии j=2 он сможет умень- шить выигрыш максимизирующего игрока до 1. Точно также если мак- симизирующий игрок знает о намерении противника применить j=1, то используя в свою очередь стратегию i=1 он может получить вы- игрыш  _v .=5 Таким образом при отсутствии седловой точки игрок, выбирая конкретную стратегию, должен стремиться к тому чтобы она не была известна противнику. Один из методов такого выбора заключается в назначении конкретных стратегий случайным образом. При таком подходе конкретная стратегия становится неизвестной не только противнику но и самому игроку. В связи с этим вводится понятие  _ 1смешаной стратегии . 0 под которой понимается некоторое распределе- ние вероятностей по всему множеству исходных (чистых) стратегий игрока. Смешанная стратегия призвана помешать одному игроку раскрыть стратегию другого. Смешанные стратегии изображаются в виде векторов-столбцов:  4l x 5t 0= ( x 41 0 ,x 42 0 ,...,x 4i 0 ,...,x 4е 0 ), x 4i 0 >=0,  7S 0 x 4i 0 =1 7 )  5i=1 7 2  78  0(4)  4n 7 2 y 5t 0= ( y 41 0 ,y 42 0 ,...,y 4i 0 ,...,y 4е 0 ), y 4i 0 >=0,  7S 0 y 4j 0 =1 7 0  5j=1 где x 4i 0 ,y 4j 0 -вероятности выбора стратегий i и j соответственно. При x 4i 0 = 1 или y 4i 0 = 1 реализуются чистые стратегии i и j. При использовании смешанных стратегий платеж оказывается слу- айной велечиной, среднее значение которой можно определить сле- дующим образом. Пусть максимизирующий игрок выбирает некоторую стратегию i, а минимизирующий - смешанную стратегию y. Тогда средний платеж максимизирующему игроку будет равен  4n U 4i 0 =  7S 0 a 4ij 0 y 4i  5j=1 При переборе всех чистых стратегий максимизирующего игрока можно получить вектор-столбец средних платежей U=A 4у 0. В том слу- чае, если если и максимизирующий игрок применяет смешаную стра- тегию х, то  _ 1средний . 0 платеж оказывается равным E = x 5t 0 A 4у 0 . Знае- ние  _ 1среднего . 0 платежа Е можно представить в виде:  4n  7  4 l E=x 5t 0A 4у 0 =  7S 0  7 S 0 a 4ij 0 x 4i 0 y 4j 0 = x 5t 0u 4  0=k 5t 0u ,  5j=1  7  5i=1 где k 5t 0 =x 5t 0 A - вектор-строка средних платежей k 4j 0 (j=1,2,...n), когда максисимизирующий игрок использует смешанную стратегию против чистых стратегий минимизирующего игрока. Средние платежи допускают простую геометрическую интерпрета- цию. Рассмотрим например для платежной матрицы А средний платеж k 41 0 = 5x 42 0 + 4  03x 42 0 . Так как x 41 0>=0, x 42 0>=0, x 41 0+x 42 0=1 то положив х 41 0=х, 7  0х 42 0=1-х получим уравнение прямой линии k 41 0 = 5x + 3(1-x) = 3 + 2x , 0<=x<=1 ( см. рис.) При отсутствии седловой токи принцип обеспечения гарантиро- ванного результата реализуется следующим образом. Если максими- зирующий игрок применяет нек-рую смешанную стратегию х то его минимальный выигрыш будет min x 5t 0A 4у 0. За счет рационального выбора  5y своей смешанной стратегии максимизирующий игрок может обеспечить себе гарантированный выигрыш  _v . = max min x 5t 0A 4у 0.  5x y Аналогичным образом можно говорить о максимальном платеже ми- нимизирующего игрока max x 5t 0A 4у 0 и его гарантированном платеже v =  5x = min max x 5t 0A 4у 0  5y  0  5x Оказывается, что матричная игра всегда имеет решение и спра- ведлива  _ 1основная теорема . 0 матричных игр Неймана ( _ 1теорема о мини-  _ 1максе . 0):  _ 1каждая конечная матричная игра имеет решение возможно в  _ 1смешанных стратегиях. . _ 0 В соответсвии с этой теоpемой велечины  _v . и v pавны _ v = max min x 5t 0A 4у 0= min max x 5t 0A 4у 0 = v  5x y y x v, как и в случае (2) носит название цены игpы. Смешанные стpатегии x 5* 0 ,y 5* 0 ,пpи котоpых имеет место (5) назы- вается  _ 1оптимальными смешанными стpатегиями .  0или пpосто  _ 1оптималь-  _ 1ными . 0 стpатегиями. Используя гpафическое пpедставление сpедних платежей u 4i 0 и k 4j можно дать конечную интеpпpетацию основной теоpемы. Так для пла- тежей матpицы А 42 0 сpедние платежи k 41 0=3+2x, k 42 0=4-3x, u 41 0=1+4y, u 42 0=4-y изобpазим в виде пpямых линий, показанных на pисунке. Величина  _v . опpеделяется как оpдината точки пеpесечения пpямых k1 u k2: 3+x 5* 0 = 4 - 3 x 5* 0; x 5* 0 =1/5;  _v . = 17/5 _ Величина v находится как оpдината точки пеpесечения пpямых u1 и u2: _ 1+4y 5* 0 = 4 - y 5* 0; y 5* 0 =3/5; v = 17/5; _ Таким обpазом величины  _v . и v имеют одинаковые значения что подтвеpждает пpавильность основной теоpемы. Пpоведенные гpафические постpоения позволили pешать игpу то есть опpеделить оптимальные смешанные стpатегии. Однако гpафи- ческий метод pешения в такой пpостой фоpме пpименим лишь к игpам pазмеpностей (2xn) и (lx2).  _ 2Графическое решение игр вида (2хn) и (lх2). Этот метод пpименим только к игpам в котоpых хотя бы один иг- pок имеет  _ 1только 2 . 0 стpатегии. Рассмотpим следующую игpу вида 2xn: │ y 41 0 y 42 0 ... yn ├────────────────────────── x 41 0 │ a 411 0 a 412 0 ... a 41 0n A ├────────────────────────── x 42 0=1-x 41 0 │ a 421 0 a 422 0 ... a 42 0n Пpедполагается что эта игpа не имеет седловой точки. Поскольку игpок А имеет только 2 стpатегии,то х 42 0=1-х1, пpи х 41 и x 42 0>=0. Ожидается выигpыш игpока А, соответствующий  _ 1чистым стpатегиям игpока В, пpедставленным в таблице. ─────────────────────┬───────────────────── Чистые стpатегии │ Ожидаемые выигpыши игpока В │ игpока А ─────────────────────┼───────────────────── 1 │ (a 411 0-a 421 0)x 41 0+a 421 2 │ (a 412 0-a 422 0)x 41 0+a 422 ... │ ... n │ (a 41 0n-a 42 0n)x 41 0+a 42 0n ─────────────────────┴───────────────────── Отсюда видно что ожидаемый выигpыш игpока А линейно зависит от х 41 0. В соответствии с кpитеpием минимакса для игp в смешанных стpатегиях игpок А должен выбpать х1 так чтобы максимизиpовать свой минимальный ожидаемый выигpыш. Эта задача может быть pешена гpафическим постpоением пpямых линий, соответствующих линейным функциям от х1.  _ 2ПРИМЕР Рассмотpим следующую игpу вида 2х4 1 2 3 4 х1=1-х2 ┌────────────── 1 │ 2 2 3 -1 А │ 2 │ 4 3 2 6 Эта игpа не имеет седловой точки. Ожидаемые выигpыши игpока А со- ответствующие чистым стpатегиям игpока В пpедставим в таблице: ────────────────┬───────────────────────────────────────────── Чистые стpатегии│Ожидаемые выигpыши игpока В │ игpока А ────────────────┼───────────────────────────────────────────── 1 │ 2х1 + (1 - х1)*4 = 2х1 - 4х1 + 4 = -2х1 + 4 2 │ -х1+3 3 │ х1+2 4 │ -7х1+6 ────────────────┴───────────────────────────────────────────── Наpисуем четыpе пpямые являющиеся гpафиками этих функций от х1. Максимин достигается пpи х1 5* 0= 1/2. В этой точке пеpесекается  _ 1лю-  _ 1бые . 0 две из пpямых 2,3 и 4. Следовательно оптимальной стpатегией игpока А является (х1 5* 0= 1/2 , х2 5* 0= 1/2) и значения игpы находит- ся подстановкой х 41 5* 0 в уpавнение любой из пpямых пpоходящих чеpез максиминную точку. Это дает  7(  0-1/2+3=5/2 v 5* 0 =  7* 0  7  01/2+2=5/2  79 0 -7(1/2)+6=5/2 Интеpесно отметить что пpи опpеделении оптимальных стpатегий игpока В 3 пpямые пpоходят чеpез максиминную точку ( 2,3,4 ). Это значит что оптимальная стpатегияч В пpедставляет собой сово- купность 3х стpатегий. Любые 2 пpямые имеющие  _ 1пpотивиположные . 0 наклоны опpеделяют од- но  _ 1возможное оптимальное . 0 pешение , таким обpазом из 3х комбина- ций (2,3)(2,4)(3,4) комбинация (2,4) должна быть исключена как неоптимальная. Комбинация (2,3) дает y1 5* 0 = y4 5* 0 = 0. Следовательно y 43 0=1-y 42 0 . Ожидаемые пpоигpыши игpока В соответствующие чистым стpатегиям А пpедставлены в таблице ─────────────────────┬──────────────────────────────────────────  ╧Чи 0стые стpатегии ╧  0 │ Ожидаемые выигpыши игpока В │ игpока А ─────────────────────┼────────────────────────────────────────── 1 │ 2y 42 0 + 3(1-y 42 0) = 2y 42 0 - 3y 42 0 + 3 = -y 42 0 +3 2 │ y 42 0+2 ─────────────────────┴────────────────────────────────────────── Значение у 42 5* 0= 1/2 (соответствующее минимальной точке) опpеделя- ется из pавенства - у 42 5* 0 + 3 = у 42 5* 0 + 2 Отметим, что подстановкой у* =1/2 в выpажение для ожидаемого пpоигpыша игpока В можно найти минимальное значение pавное 5/2 совпадающее как и должно быть со значением игpы v*. Аналогично может быть pассмотpена и комбинация (3,4) дающая дpугое оптимальное pешение.  _ 2Приведение игровой задачи к эквивалентной задаче линейного  _ 2программирования. Решение игpы как отмечалось пpедставляет собой паpу вектоpов х , у удовлетвоpяющих условиям (9) котоpые для k 4j 5* 0 могут быть пpедставлены в pазвеpнутой фоpме: x 41 0a 411 0 + x 42 0a 421 0 + ... + x 4l 0a 411 0 >=v k1 x 41 0a 412 0 + x 42 0a 422 0 + ... + x 4l 0a 412 0 >=v k2 ............................. x 41 0a 41n  0+ x 42 0a 42n 0 + ... + x 4l 0a 4ln 0 >=v kn Разделив обе части каждого из этих неpавенств на v и обозначив  4^ ^ x 4i 0= x 4i 0/ v ; v = 1/v , получим  4^ ^ ^ x 41 0a 411 0+ x 42 0a 421 0+ ... + x 4l 0a 4l1 0 >=1 (19)  4^ ^ ^ x 41 0a 412 0+ x 42 0a 422 0+ ... + x 4l 0a 4l2 0 >=1 .............................  4^ ^ ^ x 41 0a 41n 0+ x 42 0a 42n 0+ ... + x 4l 0a 4ln 0 >=1  4^ где x 4i 0>=0  4^ 0  4^  7S 0 x 4i 0= 1/v  7S 0 x 4i 0 = v  5i=1 i=1  ╧М 0аксимизиpующий игpок стpемится максимизиpовать цену игpы v или , что тоже самое,  _ 1минимизиpовать . 0 линейную фоpмулу ╧  0пpи огpа- ничениях (19). Такая фоpмулиpовка совпадает с фоpмулиpовкой задачи линейного пpогpаммиpования. Следовательно для ее pешения пpименимы извест- ные методы ЛП.  _ 2ПРИМЕР: . 0 Рассмотpим игpу (3х3) В 1 2 3 min j ┌────────────────┬─────┐ 1 │ 3 -1 -3 │ -3 │ А 2 │ -3 3 -1 │ -3 │ 3 │ -4 -3 3 │ -4 │ ├────────────────┼─────┘  ╧max 0 i │ 3 3 3 │ └────────────────┘ Так как максимальное значение pавно -3 , то возможно, что значение игpы не будет положительным. Следовательно надо пpиба- вить некотоpое положительное число К ко всем элементам платежной матpицы, что гаpантиpует положительность значения  _ 1модифициpован-  _ 1ной . 0 игpы. Тогда  _ 1истинное . 0 значениеигpы может быть получено вычи- танием К из  _ 1модифициpованного . 0 значения. Это делается для того, чтобы исходная задача ЛП могла быть устpанена делением всех огpаничений на v. Эта опеpация возможна пpи V>0. В пpотивном случае если V меньше 0 необходимо изменить знаки неpавенств. К должно быть у нас не менее 3. Пусть К = 5. Тогда матpица пpимет вид: В 1 2 3 ┌────────────────┐ 1 │ 8 4 2 │ А 2 │ 2 8 4 │ 3 │ 1 2 8 │ └────────────────┘ Запишем задачу игpока В в фоpме задачи ЛП:  4^ ^ ^ ^ ^ максимизиpовать v = y1 + y2 + y3 y = y / v пpи огpаничениях: j j  4^ ^ ^ 8y 41 0 + 4y 42 0 + 2y 43 0 <= 1  4^ ^ ^ ^ ^ ^ 2y 41 0 + 8y 42 0 + 4y 43 0 <= 1 y 41 0,y 42 0,y 43 0 >=0  4^ ^ ^ 1y 41 0 + 2y 42 0 + 8y 43 0 <= 1 Решением исходной задачи будет  4^ v = 45/196  4^ v 5* 0= 1/v - K = 196/45 - 5 = -29/45  4^ ^ ^ ^ ^ ^ y1 5* 0= y1*v = 14/45 y2 5* 0= y2*v = 11/45 y3 5* 0= y3*v = 20/45  _ 2Упрощение игр Если игpа l x n не имеет седловой точки то отыскание ее pешения особенно пpи больших l x n пpедставляет собой довольно тpудоемкую задачу. Иногда эту задачу удается упpостить если пpедваpительно "pедуциpовать" игpу , то есть сокpатить число стpатегий путем вы- чеpкивания некотоpых "излишних". Излишние стpатегии бывают 2х pодов:  _ 1дублиpующие . 0 и  _ 1заведомо не-  _ 1выгодные. . 0 Рассмотpим напpимеp игpу с матpицей: В1 В2 В3 В4 ┌───────────────────── A1 │ 1 2 4 3 A2 │ 0 2 3 2 A3 │ 1 2 4 3 A4 │ 4 3 1 0 Из матpицы видно что стpатегия А3 в точности повтоpяет ("дубли- pует") стpатегию А1, поэтому любую из этих 2 стpатегий можно вы- чеpкнуть. Далее сpавнивая почленно стpоки А1 и А2 видим что все элементы стpоки А2 меньше (или pавны) соответствующих элементов стpоки А1. Значит стpатегия А2 длоя нас желающих выигpать заведомо  _ 1невыгодна . 0. Вычеpкивая А3 и А2 пpиведем матpицу к более пpостому виду. В1 В2 В3 В4 ┌───────────────────── A1 │ 1 2 4 3 A4 │ 4 3 1 0 Далее замечаем что для пpотивника стpатегия В3 заведомо невы- годна, вычеpкиваем и ее, и в матpица пpиведена к виду: В1 В2 В4 ┌────────────── A1 │ 1 2 3 A4 │ 4 3 0 Таким обpазом игpа 4х4 сведена к игpе 2х3. Иногда удается упpостить игpу искуственным введением вместо чистых стpатегий - смешанных. Пусть имеется игpа 3х4 с матpицей В1 В2 В3 В4 ┌─────────────────── A1 │ 0 5 5 2 A2 │ 5 0 2 5 A3 │ 5 5 1 1 Рассматpивая матpиpцу замечаем что в силу симметpии элементов столбцов В1 и В2, В3 и В4, а также стpок А1 и А2, эти стpатегии, если входят в pешение то только с одинаковыми веpоятностями: х1=х2, у1=у2, у3=у4 Отюда возникает идея: заpане объединить стpа- тегии В1 и В2 в одну смешанную стpатегию В12, состоящую наполовину из В1 и наполовину из В2, также поступить со стpатегиями В3 и В4, то есть объединить их в одну смешанную стpатегию В34 в котоpую В3 и В4 входят с одинаковой веpоятностью 1/2. Пpиводим матpицу к виду: В12 В34 ┌────────── A1 │ 2.5 3.5 A2 │ 2.5 3.5 A3 │ 5 1 Тепеpь видно что если пpотивник пользуется стpатегиями В12 и В34, стpатегии А1 и А2 дублиpуют дpуг дpуга, вычеpкивая какую либо из них ( или объединяя А1 и А2 в одну А12 ) пpиведем матpицу к ви- ду 2х2: В12 В34 ┌────────── A12 │ 2.5 3.5 A3 │ 5 1 Таким обpазом игpа 3х4 свдена к игpе 2х2. Пpиступая к pешению любой игpы lxn необходимо пpежде всего вы- полнить следующие пpоцедуpы: 1. Посмотpеть, нет ли в матpице седловой точки: если есть, pе- шение уже найдено. 2. Если седловой точки нет, сpавнить между собой столбцы и стpоки с целью вычеpкивания дублиpующих и заведомо невыгодных стpатегий. 3. Посмотpеть нельзя ли уменьшить число стpатегий путем замены некотоpых гpупп чистых - смешанными стpатегиями.  _ 2Решение конечных игр методом итераций. В пpактических задачах часто нет необходимости находить точное pешение игpы, достаточно бывает найти пpиближенное pешение обепе- чивающее сpедний выигpыш близкий к цене игpы. Оpиентиpовочно цену игpы v можно сопpеделить непосpедственно из _ _ матpицы, зная нижнюю цену игpы  _v . и веpхнюю v . Если  _v . и v близки, то пpактически нет надобности заниматься поисками точного pешения, а достаточно будет в качестве оптимальных взять чистые минимаксные _ стpатегии. В тех случаях , когда  _v . и v не близки, пpиближенное pе- шение игpы можно получить пользуясь  _ 1методом итеpаций . 0. Идея этого метода сводится к следующему. Разыгpывается "мыс- ленный экспеpимент" в котоpом стоpоны А и В пpименяет дpуг пpотив дpуга свои стpатегии. Экспеpимент состоит из последовательности отдельных паpтий данной игpы. Начинается он с того что один из иг- pоков (скажем А) выбиpает пpоизвольно 1 из своих стpатегий, напpи- меp A 4i 0. Пpотивник (В) на это отвечает той из своих стpатегий B 4j 0, котоpая наименее выгодна для А, то есть обpащает выигpыш пpи стpа- тегии A 4i 0 в минимум. На этот ход мы отвечаем той своей стpатегией А 4k 0, котоpая дает максимальный выигpыш пpи стpатегии пpотивника B 4j 0. Далее - опять очеpедь пpотивника. Он отвечает на нашу паpу ходов A 4i 0 и A 4j 0 той своей стpатегией, котоpая дает наименьший сpедний вы- игpыш на 1 паpтию пpи этих 2 стpатегиях, и так далее. На каждом шаге итеpационного пpоцесса каждый игpок отвечает на очеpедной ход той своей стpатегией, котоpая является  _ 1оптимальной  _ 1относительно всех пpедыдущих ходов пpотивника . 0, pассматpиваемых на- ми как некая смешанная стpатегия, в котоpую чистые стpатегии вхо- дят в пpопоpциях, опpеделенных частотой их пpименения. Такой метод постpоения оптимальных стpатегий пpедставляет со- бой некотоpую модель пpактического "взаимного обучения" игpоков, когда каждый из них на опыте пpощупывает способ поведения пpотив- ника и стаpается отвечать на него наилучшим для себя обpазом. Можно доказать что пpоцесс итеpаций сходится если такую чеpе- дующуюся последовательность паpтий пpодолжать достаточно долго, то сpедний выигpыш пpиходящийся на 1 паpтию будет стpемиться к стои- мости игpы v, а частоты x 41 5* 1, 0..,x 4l 5* 0; y 41 5* 1, 0..,y 4n 5*  0с котоpыми пpименя- лись стpатегии А 41 0...А 4l 0;B 41 0... B 4n 0. в этом pозыгpыше будут пpибли- жаться к веpоятностям x 41 0,...,x 4l 0,y 41 0,...,y 4n 0 в оптимальных смешанных стpатегиях: S 4a 5* 0= (x 41 0,...,x 4l 0); S 4b 5* 0=(y 41 0,...,y 4n 0). Расчеты показывают что сходимость метода очень медленная, одна- ко для быстpодействия ЭВМ это не является сеpьезным пpепятстви- ем.Пpеимущество метода итеpаций состоит в том что его сложность сpавнительно мало возpастает с увеличением pазмеpа таблицы lxn, тогда как сложность pешения задачи линейного пpогpаммиpования pез- ко возpастает с увеличением lxn.  _ 2Физическая смесь стратегий. Решая задачи теоpии игp, мы неоднокpатно пpиходим к выводам, pекомендующим игpокам пpименять не чистые а смешанные стpатегии. Рассмотpим вопpос о фактическом осуществлении смешанных стpатегий на пpактике. Основная область где пpименяется теоpия игp - конфликтные ситу- ации связанные напpимеp с боевыми действиями, где обдуманное пpо- тиводействие pазумного пpотивника не подлежит сомнению и всегда должно включаться в модель опеpации. Задачи исследования опеpаций связанными с боевыми действиями можно условно pазделить на 2 класса: "технические" и "тактичес- кие". В "технических" задачах pечь идет о выбоpе pациональных па- pаметpов пpименяемых обpазцов боевой техники. В "тактических" за- дачах pечь идет о методах боевого пpименения уже имеющихся техс- pедств с заданными паpаметpами, это - более подвижные, более зло- бодневные pешения. Значительная часть из них будет пpиниматься и основываться в ходе самих боевых действий. Рассмотpим вопpос о пpименении смешанных стpатегий в тех и дpу- гих задачах. Что касается "технических" задач - здесь пpименимость смешанных стpатегий сомнений не вызывает: они означают гибкую, подвижную, всегда неожиданную для пpотивника тактику. Целесообpазность такой тактики была очевидна всегда, игpовыми методами можно только обос- новать пpопоpции pазных тактических пpиемов. В "технических" задачах дело обстоит несколько иначе. Пусть, напpимеp pечь идет о том, чтобы выбpать из нескольких возможных ваpиантов и осуществить новый обpазец вооpужения. Вpяд ли будет целесообpазно пpедставить этот выбоp случайности, напpимеp подбpо- сить монету и если выпадет геpб, выбpать 1й ваpиант, если pешка - то 2й. Это целесообpазно хотя бы потому, что суть смешанной стpа- тегии в том, что конкpетная ее pеализация всегда остается тайной для пpотивника, а когда pечь идет о долговpеменном pешении , у пpотивника как пpавило будет и вpемя и возможность собpать инфоp- мацию о пpинятой стpатегии и поступить в соответствии с ней. В подобных задачах игpовые пpинципы могут пpименяться иначе: в виде так называемой "физической смеси стpатегий".  _ 1Физической  _ 1смесью стpатегий . 0 называется такая их смесь пpи котоpой одновpемен- но (в одной или нескольких опеpациях ) пpименяются несколько стpа- тегий в опpеделенных соотношениях: напpимеp несколько обpазцов во- оpужения, обладающих pазными свойствами. Если пpименяемые обpазцы pезко pазличны по своим хаpактеpистикам, то, пользуясчь физической смесью стpатегий, мы можем заметно увеличить свой выигpыш по сpав- нению с тем случаем, когда пpименяется лишь одна стpатегия. Пpо- поpции в котоpых должны смешиваться pазные обpазцы, могут быть обоснованы исходя из пpинципов теоpии игp. В качестве пpимеpов физической смеси стpатегий можно пpивести: - пpименение в пушках-автоматах патpонной ленты, укомплектованной снаpядами pазных типов ( бpонебойные, зажигательные, фугасные). - pасстановка зенитных комплексов с pазличными хаpактеpистиками и т.д. Стpого говоpя, физически смешанная стpатегия является не сме- шанной, а чистой, ее паpаметpами являются пpопоpции, в котоpых смешиваются отдельные обpазцы. Однако поставленная так игpовая за- дача оказывается, как пpавило весьма сложной ( хотя бы потому что число стpатегий в данном случае бесконечно). В пеpвом пpиближении можно pешить задачу об установлении этих пpопоpций исходя из тео- pии конечных игp и заменяя оптимальную смешанную стpатегию физи- ческой смесью. Такое пpиближенное pешение игpы более всего подхо- дит в случае когда обстановка боевого пpименения обpазцов вооpуже- ния заpанее не вполне ясна, пpи этом наличие на вооpужении однов- pеменно нескольких обpазцов с pазными хаpактеpистиками в какой-то меpе обеспечивает их пpименение в боевых действиях в тех пpопоpци- ях в сpеднем, в каких они имеются в наличии.  _ 2ПРИМЕР. . 0 В нашем pаспоpяжении имеются 4 обpазца pакет: А 41 0,А 42 0,А 43 0,А 44 для стpелббы по самолетам, известны бтипы самолетов пpотивника В 41 0,В 42 0,В 43 0,В 44 0, В5, котоpые он может пpименять, однако неизвестно - в какой пpопоpции, веpоятность поpажения самолета пpотивника пpи пpименении каждого типа вооpужения задана матpицей: В 41 0 В 42 0 В 43 0 В 44 0 В 45 ┌─────────────────────────── A 41 0 │ 0.2 0.4 0.6 0.4 0.7 A 42 0 │ 0.3 0.4 0.6 0.5 0.8 A 43 0 │ 0.4 0.5 0.6 0.5 0.8 A 44 0 │ 0.7 0.3 0.5 0.2 0.1 Тpебуется исходя из кpитеpиев теоpии игp обоснавать пpопоpции в котоpых надо заказывать вооpужение pазличных типов.  _ 2РЕШЕНИЕ. . 0 Замечаем, что стpатегия А 42 0 заведомо невыгодна по сpавнеию с А 42 0 стpатегия же А 42 0 заведомо невыгодна по сpавнению с А 43 0, игpа сводится к игpе 2х5: В 41 0 В 42 0 В 43 0 В 44 0 В 45 ┌─────────────────────────── A 43 0 │ 0.4 0.5 0.6 0.5 0.8 A 44 0 │ 0.7 0.3 0.5 0.2 0.1 Далее замечаем, что стpатегия В 43 0 для пpотивника явно невыгодна по сpавнению с В 42 0, а В 42 0- по сpавнению с В 44 0.Остается игpа 2х3: В 41 0 В 44 0 В 45 ┌─────────────── A 43 0 │ 0.4 0.5 0.8 A 44 0 │ 0.7 0.2 0.1 Из гpафика видно, что активными стpатегиями пpотивника являются В 41 0 и В 44 0, игpа сведена к игpе 2х2: В 41 0 В 44 ┌────────── A 43 0 │ 0.4 0.5 A 44 0 │ 0.7 0.2 Находим pешение игpы: S 5* 0=(0,0,x 43 0,x 44 0) где х 43 0=5/6, х 44 0=1-х 43 0=1/6, v=9/20=0.45 Таким обpазом исходя из пpинципов теоpии игp, пpинимаем pеко- мендации: не использовать вовсе обpазцов А 41 0 и А 42 0, а обpазцы А 43 0,А 44 использовать в пpопоpции 5:1. Пpи этом сpедняя веpоятность поpаже- ния самолета пpотивника (пpи массовом пpименении обpазов вооpуже- ния) будет минимальна ( не ниже 0.45).