транспортная задача линейного программирования

Классическая постановка транспортной задачи. Пусть имеется m поставщиков А ₁, А ₂, ..., А_i, ..., А_m однородного груза в количествах соответственно а ₁, а ₂, ..., а_i,..., а_m единиц и n потребителей В ₁, В ₂ ,..., В_j, .... В_n этого груза, потребность которых составляет соответственно b ₁, b ₂, ..., b_j, ..., b_n единиц.

Известны стоимость перевозок единиц груза от i -го поставщика к j -му потребителю – с_ij (i = ; j = ).

Требуется составить такой план перевозок груза, который обеспечит минимальные транспортные расходы.

Обозначим через х_ij (i = ; j = ) – количество единиц груза, перевозимого от i -го поставщика к j -му потребителю.

Таблица 27

	b 1		b 2		...	bi		...	bn
а 1		c 11		c 12	...		c 1 j	...		c 1 n
	x 11		x 12			x 1 j			x1n
a 2		c 21		c 22	...		c 2 i	...		c 2 n
	x 21		x22			x2i			x2n
...	...		...		...	...		...	...
ai		ci 1		ci 2	...		cij	...		cin
	xi 1		xi 2			xij			xin
...	...		...		...	...		...	...
am		cm 1		cm 2	...		cmi	...		cmn
	xm 1		xm 2			xmi			xmn

Чтобы решить транспортную задачу, описываемую открытой моделью (когда наличие груза у поставщиков не совпадает с потребностью груза у потребителей), ее необходимо сбалансировать или, другими словами, открытую модель привести к закрытой. Достигается это введением фиктивных поставщиков или потребителей (добавляется новая строка или столбец в матрицу перевозок). Стоимость перевозки единицы груза до фиктивного потребителя или от фиктивного поставщика принимается равной нулю, так как груз не перевозится. Переход от открытой модели к закрытой фактически означает приведение модели транспортной задачи к канонической форме без учета требования максимизации целевой функции.

Оптимальный план закрытой Т-задачи отыскивается в 2 этапа:

1)построение исходного базисного плана Т-задачи (построенный план должен быть сбалансированным и невырожденным);

2)оптимизация исходного базисного плана.

7.2. Методы построения исходного плана

Метод северо-западного угла. Определение значений x_ij начинается с левой верхней клетки таблицы (это соответствует северо-западному углу на географической карте). Находим значение х ₁₁из соотношения:

.

Возможны три варианта:

1. Если а ₁ < b ₁, то x_ij = a_i, строка i = 1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b ₁ (столбец j = 1) уменьшается на величину а ₁.

2. Если а ₁ > b ₁, то х ₁₁ = b ₁, столбец j = 1 исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика а ₁ (строка i = 1) уменьшается на величину b ₁.

3. Если а ₁ = b ₁, то х ₁₁ = а ₁ = b ₁, строка i = 1 или столбец j = 1 исключаются из дальнейшего рассмотрения. Такой вариант вычеркивания не приводит к вырождению исходного плана. Если вычеркнуть и строку i = 1, и столбец j = 1, получается вырожденный исходный план.

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

После завершения описанного процесса необходимо провести проверку полученного плана на вырожденность. Если количество заполненных клеток равно m + n – 1, то план является невырожденным, в противном случае – вырожденным.

7.3. Оптимизация исходного базисного плана перевозок

Алгоритм метода потенциалов

Шаг 1. Вычисление потенциалов, согласованных с опорным планом поставок. Потенциалы u_i поставщиков и v_j потребителей находятся из уравнений вида:

.

Такие уравнения составляются для всех занятых поставками клеток таблицы. Далее задают любое значение потенциалу u₁ и из системы уравнений однозначно определяют все остальные потенциалы. Значения потенциалов записывают справа и снизу таблицы против соответствующих строк и столбцов. Или добавляют к таблице столбец справа для потенциалов поставщиков и строку снизу для потенциалов потребителей:

При практическом определении потенциалов необязательно выписывать на каждой итерации соответствующую систему уравнений. Можно находить потенциалы непосредственно по таблице, не выписывая в явном виде систему.

Шаг 2. Проверка плана на оптимальность.

Для всех свободных (незаполненных) клеток рассчитаем величину

.

Если для каждой незаполненной клетки выполняется условие то план оптимальный. В противном случае полученный план не является оптимальным, и необходимо переходить к новому базисному плану.

Шаг 3. Улучшение плана поставок.

3.1. Среди положительных величин выбирается максимальная. Выбранную клетку (i, j) помечают знаком “·” в центре клетки. Эта клетка в следующей таблице будет занята поставкой. Одновременно с занятием новой клетки происходит освобождение одной из занятых прежним планом клеток.

3.2. Для правильного перемещения перевозок, чтобы не нарушить ограничений, строится цикл, т. е. замкнутый путь, соединяющий выбранную незаполненную клетку с ней же самой и проходящий через заполненные клетки. Цикл строится следующим образом. Вычеркиваются все строки и столбцы, содержащие ровно одну заполненную клетку (выбранная клетка при этом считается заполненной). Все остальные заполненные клетки составляют цикл и лежат в его углах.

Цикломназывается набор клеток таблицы, которые могут быть соединены замкнутой ломаной линией, удовлетворяющей следующим двум условиям:

1) любое звено ломаной находится либо в строке, либо в столбце таблицы;

2) никакие два ее звена не могут находиться в одной строке или в одном столбце.

Примечание. После перевода незаполненной клетки в число заполненных количество заполненных клеток становится равным m + n. Для такого количества клеток всегда можно построить цикл, и он будет единственным. Направление построения цикла (по часовой стрелке или против) несущественно.

3.3. В угловой каждой клетке цикла, начиная с незаполненной, проставляются поочередно знаки «+» и «–». В клетках со знаком «–» выбирается минимальная величина, которую обозначим через .

Переходим к новому плану поставок путем корректировки старого плана по следующим формулам:

Корректировку плана лучше начинать с перераспределения поставок в клетках цикла, добавляя к поставкам в плюсовых клетках цикла величину Q и вычитая ее из поставок в минусовых клетках.

При этом рекомендуется обходить клетки цикла последовательно в одном направлении, начиная с новой занимаемой клетки, помеченной знаком «·».

Следует отметить, что если минимальная поставка находится одновременно в нескольких минусовых клетках цикла, то при переходе к новому опорному плану освобождается только одна из них, а остальные остаются занятыми нулевыми поставками.

На этом полностью заканчивается одна итерация метода оптимизации. Далее процесс продолжается аналогичным способом.

Шаг 1. Находим потенциалы, согласованные с новым планом.

Шаг 2. Проверяем новый план на оптимальность.

Если все получен оптимальный план.

Если имеются идем на шаг 3 и т. д.

7.4. Пример решения транспортной задачи

Пример 1. Решить транспортную задачу методом потенциалов, построив начальный опорный план по правилу северо-западного угла:

А = (30; 50; 40; 33)

В = (58; 22; 18; 22)

Решение. В данной задаче четыре поставщика с запасами грузов а_i, i = 1, 4 и четыре потребителя с потребностями b_j, j = 1, 4. Прежде чем приступить к решению транспортной задачи, необходимо ее закрыть, если она открытая.

Суммарный объем груза у поставщиков равен: , а суммарная потребность составляет величину . Так как то задача открытая и, чтобы ее закрыть, вводим 5-го (фиктивного) потребителя с потребностью в грузе, равной разности . Будем иметь .

Если то в Т-задачу вводится фиктивный поставщик с запасом груза

Коэффициенты транспортных расходов на доставку груза от поставщиков к фиктивному потребителю полагаются равными нулю: , .

Представим закрытую Т-задачу в табличной форме (табл. 31):

Таблица 31

	bj
аi
	х 11		х 12		х 13		х 14		х 15
	х 21		х 22		х 23		х 24		х 25
	х 31		х 32		х 33		х 34		х 35
	х 41		х 42		х 43		х 44		х 45

Строки этой таблицы отвечают поставщикам, а столбцы – потребителям.

Требуется найти оптимальный план поставок ; ; .

Прежде чем приступить к нахождению оптимального плана поставок, необходимо иметь какой-нибудь опорный план. Существуют различные способы построения опорных планов в Т-задаче, но по условию задачи требуется найти его методом северо-западного угла.

Построение опорного плана Т-задачи по правилу северо-западного угла.

Все расчеты представлены далее в табличной форме (табл. 32).

Таблица 32

	bj
аi
			–		–		–		–
					–		–		–
	–								–
	–		–		–

Берется северо-западный угол таблицы (клетка (1.1)) и планируется поставка от первого поставщика к первому потребителю в объеме . Эта поставка записывается в правый нижний угол клетки. Величина запланированной поставки вычитается из запаса груза и потребности . Неудовлетворенная потребность первого потребителя становится 58 – 30 = 28, а запас груза у первого поставщика полностью исчерпанным. Первая строка закрывается, т. е. она больше не участвует при построении начального опорного плана.

В оставшейся части таблицы снова берем северо-западный угол (клетка (2.1)). Полагая корректируем запас груза у второго поставщика. Потребность первого удовлетворена полностью, следовательно, первый столбец закрывается.

Берем клетку (2.2), полагаем и вычитаем величину этой поставки из оставшегося объема груза у второго поставщика и потребности второго потребителя.

В результате такой корректировки весь груз второго поставщика распределен (запас исчерпан) и полностью удовлетворена потребность в грузе второго потребителя.

Стоит обратить внимание, что если на каком-либо шаге применения метода северо-западного угла одновременно исчерпывается запас груза у поставщика и удовлетворяется полностью потребитель, то закрыть следует что-нибудь одно: либо строку, либо столбец. Соблюдение данного правила гарантирует занятость клеток опорным планом поставок (где и – количество поставщиков и потребителей соответственно). Это необходимо для нахождения потенциалов.

Итак, в случившейся ситуации можно закрыть либо вторую строку, либо второй столбец. Закроем вторую строку.

Затем берем клетку (3.2), находим и закрываем второй столбец.

В оставшейся части таблицы северо-западной клеткой будет клетка (3.3). Полагая для клетки (3.4) находим величину поставки После осуществления этой поставки одновременно удовлетворены потребность четвертого потребителя и полностью распределены грузы третьего поставщика. Закроем третью строку и перейдем к клетке (4.4), Находим, что . После записи нулевой поставки в клетку (4.4) таблицы ее столбец автоматически закрывается.

Последней рассматривается клетка (4.5), куда заносится объем поставки

За (m + n – 1) шагов находится опорный план.

Представленный в табл. 6 опорный план содержит 4 + 5 – 1 = 8 поставок, причем две из них – нулевые поставки.

Из самого способа построения опорного плана вытекает его сбалансированность по поставщикам и потребителям. Однако во избежание ошибок при вычислениях рекомендуется проверить все балансы путем суммирования поставок по строкам и столбцам.

Основные процедуры метода потенциалов:

1) вычисление потенциалов, согласованных с найденным опорным планом;

2) проверка плана на оптимальность с помощью потенциалов;

3) улучшение плана в случае его неоптимальности.

Шаг 1. Вычисление потенциалов, согласованных с опорным планом поставок. Потенциалы и поставщиков и потребителей находятся из уравнений вида . Такие уравнения составляются для всех занятых поставками клеток таблицы.

Занятые клетки	Система уравнений
(1.1)
(2.1)
(2.2)
(3.2)
(3.3)
(3.4)
(4.4)
(4.5)

Полагая, например, , найдем последовательно все остальные неизвестные: , , , , , , , .

Добавим к таблице 32 столбец справа для потенциалов поставщиков и строку снизу для потенциалов потребителей (таблица 33). В последней клетке расширенной таблицы 33 будем записывать сумму транспортных расходов. Обозначим для начального плана поставок суммарные затраты на перевозки через . Тогда

.

При практическом определении потенциалов необязательно выписывать на каждой итерации соответствующую систему уравнений. Можно находить потенциалы непосредственно по таблице, не выписывая в явном виде систему уравнений для заполненных клеток.

Предположим, что известен какой-нибудь потенциал. Тогда возможны два случая.

Случай 1. Известный потенциал относится к строке (поставщику). Тогда по данному потенциалу и по занятым клеткам этой строки (а в каждой строке и столбце обязательно есть хотя бы одна занятая клетка) можно определить потенциалы тех столбцов (потребителей), которым принадлежат рассматриваемые занятые клетки. Потенциалы потребителей определяются (правило 1) по формуле , где – известный потенциал поставщика, а – тариф, стоящий в занятой клетке.

Таблица 33

	bj
аi
		–								+
			–		–		–		–
		+		–
					–		–		–
				+					–
									–
								+		–

Случай 2. Известен потенциал какого-либо столбца. Тогда по занятым клеткам этого столбца определяются (правило 2) потенциалы строк, соответствующих этим клеткам, по формуле

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

Выбираем какую-нибудь одну строку (столбец) таблицы. Потенциал выбранной строки полагается равным произвольному числу, и по правилу 1 находим потенциалы всех столбцов, соответствующих занятым клеткам выбранной строки. Затем просматриваем столбцы с найденными потенциалами и по занятым в них клеткам по правилу 2 определяем потенциалы новых строк.

Процесс продолжается до тех пор, пока не будут использованы все занятые клетки и не найдены все потенциалы.

Применяя описанный способ к решению рассмотренной выше системы уравнений, процесс вычислений можно представить так.

Выбираем 1-ю строку и полагаем . В этой строке одна занятая клетка, расположенная в первом столбце, следовательно, можно найти потенциал по формуле . Просматривая 1-й столбец, находим в нем занятую клетку (2.1), не использованную еще для нахождения потенциалов. С ее помощью находим потенциал . С помощью и клетки (2.2) находим и т. д.

Шаг 2. Проверка плана на оптимальность. Пусть определены потенциалы, согласованные с некоторым опорным планом. Они удовлетворяют первому условию критерия оптимальности плана поставок в Т-задаче. Следовательно, для того чтобы узнать, оптимален ли анализируемый план или нет, нужно проверить, удовлетворяют ли эти потенциалы второму условию. Это равносильно проверке условий < для свободных клеток.

Обозначим . Тогда критерий оптимальности опорного плана поставок может быть сформулирован так: опорный план поставок оптимален тогда и только тогда, когда потенциалы, согласованные с ним, удовлетворяют условию < 0, где – свободные клетки таблицы.

Возвратимся к таблице 33 и с ее помощью вычислим величины для свободных клеток. Тогда будем иметь следующее:

;

;

;

;

;

;

;

;

;

;

;

.

Таким образом, условие < 0нарушается для многих клеток, поэтому найденный план не оптимален.

Шаг 3. Улучшение плана поставок.

1. Среди положительных величин выбирается максимальная. В нашем примере это две величины: и . Выбираем какую-нибудь из них, например, . Клетка (1.5) отмечается в таблице 7 знаком «·». Эта клетка в следующей таблице будет занята поставкой. Одновременно с занятием новой клетки происходит освобождение одной из занятых прежним планом клеток. Удаляемая из плана поставка находится с помощью цикла.

2. Смотрим, с какой занятой клеткой первой строки или пятого столбца можно соединить клетку (1.5) в табл. 7. Построим цикл, двигаясь от клетки (1.5), к другой занятой клетке, например, по часовой стрелке. В пятом столбце имеется единственная занятая клетка (4. 5), с которой может быть соединена клетка (1.5).

Следующее звено ломаной должно находиться в четвертой строке. Так как в этой строке тоже единственная занятая клетка (4.4), то ее следует соединить с клеткой (4.5).

Очередное звено ломаной должно находиться в четвертом столбце таблицы – это будет звено, соединяющее клетки (4.4) и (3.4).

Следующее звено должно находиться в третьей строке. В ней – две занятые клетки. Для отыскания нужной клетки применяется метод проб и ошибок. Попробуем соединить клетку (3.4) с клеткой (3.3). В одной строке таблицы не может быть более одного звена ломаной, поэтому следующее звено должно быть расположено после такого соединения в третьем столбце таблицы. Однако в третьем столбце нет больше занятых клеток, и поэтому нельзя замкнуть ломаную. Клетка (3.3), следовательно, является тупиковой, и ее нельзя соединять с клеткой (3.4). Остается единственная возможность – соединить клетку (3.4) с занятой клеткой (3.2).

Далее процесс построения цикла пойдет однозначно. Следующее звено должно находиться во втором столбце, поэтому соединяем клетки (3.2) и (2.2). Затем в цикл войдут клетки (2.1) и (1.1). Соединяя клетки (1.1) и (1.5), ломаная линия замыкается.

3. Начиная с клетки (1.5), обойдем клетки, лежащие в углах цикла, в каком-либо одном направлении (например, по часовой стрелке), отмечая их попеременно знаками «+» и «–».

Далее в минусовых клетках цикла находим минимальную поставку , которую обозначим через . В нашем примере четыре минусовых клетки в цикле: клетки (4.5), (3.4), (2.2). (1.1). Минимальная поставка находится в двух клетках – (2.2) и (3.4), – т. е. .

4. Переходим к новому плану поставок путем корректировки старого плана по следующим формулам:

Корректировку плана лучше начинать с перераспределения поставок в клетках цикла, добавляя к поставкам в плюсовых клетках цикла величину и вычитая ее из поставок в минусовых клетках. При этом рекомендуется обходить клетки цикла последовательно в одном направлении, начиная с новой занимаемой клетки (1.5). В таблице 34 представлен новый план:

Таблица 34

	bj
аi
		–								+
		+						–
								+		–

Следует отметить, что если минимальная поставка находится одновременно в нескольких минусовых клетках цикла, то при переходе к новому опорному плану освобождаются только одна из них, а остальные остаются занятыми нулевыми поставками. Так, при переходе от таблицы 33 к таблице 34 освободилась клетка (2.2), а другая клетка с минимальной поставкой – (3.4) – остается занятой (нулём). В таблице 34 по-прежнему 8 занятых клеток.

Суммарные транспортные расходы на новый план поставок могут быть получены путем корректировки суммы транспортных расходов на прежний план по формуле:

Получим:

На этом полностью заканчивается одна итерация метода оптимизации. Далее процесс продолжается аналогичным способом (см. итерации 2 – 4 в полной версии курса лекций).

В итоге полученбудет оптимальный план перевозок:

.

Затраты на перевозку в оптимальном плане: .

11. Модели конфликтных ситуаций в теории игр

Методы теории игр разработаны применительно к специфическим конфликтным ситуациям, которые обладают свойством многократной повторяемости. Целью теории игр является выработка рекомендаций по рациональному образу действия участников многократно повторяющегося конфликта.

Одним из основных видов игр являются матричные игры, которые называются парными играми с нулевой суммой (один игрок выигрывает столько, сколько проигрывает другой) при условии, что каждый игрок имеет конечное число стратегий. В этом случае парная игра формально задается матрицей А (платежной матрицей).

Каждой чистой стратегии игрока I (первого игрока) ставится в соответствие строка матрицы, а чистой стратегии игрока II (второго игрока) – ее столбец. Элемент этой матрицы аij характеризует платеж игроку I игроком II в ситуации (i, j), т. е. когда игрок I выбрал i-ю свою стратегию, а игрок II – j-ю свою стратегию. Матрица А называется поэтому платежной матрицей игры, или матрицей выигрышей игрока I. Если элемент аij положителен, то он показывает выигрыш игрока I (проигрыш игрока II) в ситуации (i, j), если же элемент аij отрицателен, то это означает проигрыш I (выигрыш игрока II).

В качестве примера игры двух лиц с нулевой суммой рассмотрим условную военную игру под названием «игра полковника Блотто». Две армии ведут борьбу за два населенных пункта. Армия полковника Блотто (игрок А) состоит из четырех формирований, армия противника (игрок В) – из трех.

Сформулируем правила игры. Армия, которая посылает больше формирований на один или другой пункт, занимает его и уничтожает посланные туда формирования противника, получая по единице за каждый занятый пункт и каждое уничтоженное формирование противника. В случае равенства сил на одном или другом пункте противники очков не получают. Общий выигрыш определяется как сумма выигрышей в двух пунктах. Платежная матрица игры представлена в таблице 41.

Таблица 41

Платежная матрица игры полковника Блотто

Вj Аi	(3, 0)	(0, 3)	(2, 1)	(1, 2)
(4, 0)
(0, 4)
(3, 1)		–1
(1, 3)	–1
(2,)2	–2	–2

11.2. Решение игры в чистых стратегиях

В теории игр наилучшим принято считать поведение игроков, при котором каждый игрок предполагает, что его противник не глупее (так называемый принцип разумности). В результате этого рекомендуется в качестве наилучшей стратегии выбирать ту, которая обеспечивает наибольший гарантированный выигрыш, т. е. выигрыш, не зависящий от действий противника и который противник никак не может уменьшить..

Исходя из указанного принципа, опишем формально действия игроков. Если игрок А выбрал стратегию i, то его гарантированный выигрыш составит где минимум берется по всем стратегиям игрока В (по строке платежной матрицы с номером i). Так как по каждой своей стратегии (по каждой строке матрицы) игрок А выбрал гарантированный выигрыш, он среди всех своих стратегий может теперь выбрать такую, которая обеспечит ему максимальный гарантированный выигрыш:

Стратегия, соответствующая максимальному значению минимумов строк, называется максиминной стратегией, а величина v ₁ – нижней ценой игры или максимином.

Игрок В, рассуждая аналогично, может среди всех своих стратегий выбрать ту, которая обеспечит ему минимальный гарантированный проигрыш:

Стратегия, соответствующая минимальному значению максимумов столбцов, называется минимаксной стратегией, а величина v ₂ – верхней ценой игры или минимаксом.

Если игрок А будет придерживаться максиминной стратегии, то он получит выигрыш не меньше максиминного значения, т. е.:

Если игрок В придерживается минимаксной стратегии, то его проигрыш будет не больше минимаксного значения, а именно:

В общем случае отношение между нижней и верхней ценой игры устанавливается неравенством:

Существуют игры, для которых Такие игры называются играми с седловой точкой. Соответствующие этим значениям стратегии игроков А и В являются оптимальными, а элемент платежной матрицы игры с седловой точкой, отвечающий этим оптимальным чистым стратегиям, называется седловой точкой. Элемент платежной матрицы, соответствующий ее седловой точке, является ценой игры. Обозначим ее через v. Тогда при наличии седловой точки имеет место равенство: Если v > 0, игра выгодна игроку А. При v < 0 игра выгодна игроку В. В случае v = 0 игра выгодна обоим игрокам и называется безобидной или справедливой.

В табл. 42 дан пример игры и ее решение. В данной игре каждый из двух игроков располагает четырьмя стратегиями и не имеет информации о том, какую стратегию применит противник.

Таблица 42

Поиск в игре седловой точки

Вj Аi	В 1	В 2	В 3	В 4
А1
А2
А3
А4

В первую очередь в каждой строке платежной матрицы выберем минимальные элементы и запишем их в последний столбец табл. 2, а в каждом столбце – максимальные и запишем их в последнюю строку той же таблицы.

Затем определяется нижняя и верхняя цена игры путем выбора максимального элемента в последнем столбце таблицы и минимального – в последней строке. В данном примере v ₁ = v ₂ = 7. Следовательно, платежная матрица имеет седловую точку и оптимальными для игроков являются чистые стратегии А ₂ и В ₂. Цена игры v = 7.

Если седловая точка платежной матрицы отсутствует, игра решается в смешанных стратегиях.

11.3. Решение игры без седловой точки

Игры с седловой точкой встречаются редко. Большинство игр седловой точки не имеют. К ним относится и рассмотренная игра полковника Блотто.

Если седловая точка отсутствует, то игрок А, применяя свою максиминную стратегию, выиграет не менее v ₁, а игрок В, применяя свою минимаксную стратегию, проиграет не более v ₂, где v ₁< v ₂. Применение чистых стратегий в каждой партии такой игры не дает возможности игрокам увеличить выигрыш (v ₁) или уменьшить проигрыш (v ₂). Для того чтобы это было возможно, необходимо применять не одну, а несколько чистых стратегий, чередуя их случайным образом с какими-то частотами. Такая стратегия получила название смешанной стратегии. Ее элементами являются чистые стратегии.

Поведение игрока, при котором он с определенной частотой или вероятностью случайно чередует все свои чистые стратегии, называется смешанной стратегией.

Обозначим смешанную стратегию игрока I как а смешанную стратегию игрока II как где p_i – вероятность выбора игроком I i -й чистой стратегии; q_j – вероятность выбора игроком II j -й чистой стратегии.

Результаты использования игроками смешанных стратегий p и q оцениваются с помощью функций выигрыша (платежной функции):

выражающей математическое ожидание выигрыша игрока I и соответственного проигрыша игрока II.

Для матричных игр справедлива следующая теорема Неймана:

Любая матричная игра имеет оптимальное решение в смешанных стратегиях.

Лишь в некоторых случаях оптимальное решение игры возможно в чистых стратегиях, когда оба игрока применяют в каждой партии одну чистую стратегию с единичной вероятностью, а остальные с нулевой вероятностью. Такое может быть только в играх с платежными матрицами, обладающими специальным свойством – седловой точкой.

Чистые стратегии игроков А и В, для которых вероятность p_i и q_j отличны от нуля, называются активными. В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна равна единице, смешанная стратегия превращается в чистую.

Решение игры, не имеющей седловой точки, может осуществляться различными методами. Рассмотрим некоторые из них.

1. Чаще всего матричная игра решается путем сведения ее к задаче линейного программирования, которая может быть решена, например, симплекc-методом. Далее находят решение исходной матричной игры.

2. Известны несколько методов приближенного решения матричной игры, например метод Брауна.

3. Если матица игры имеет размерность, равную двум (у одного из игроков имеется только две стратегии), то решение игры может быть получено графически.

Графический способ решения матричной игры. Найдем графическим методом решение следующей матричной игры:

Данная матричная игра неразрешима в чистых стратегиях.

Графически решается задача игрока, имеющего две стратегии, т. е. в данном случае первого игрока. Оптимальная стратегия второго игрока находится аналитическим путем после решения задачи первого игрока.

Максимальная стратегия первого игрока находится путем решения следующей задачи первого игрока:

Идея графического метода состоит в том, что функция , показывающая минимальные (гарантированные) выигрыши первого игрока при всевозможных его смешанных стратегиях р, строится графически. График этой функции называется нижней границей выигрышей первого игрока. Затем на нижней границе находится точка, соответствующая максимальному выигрышу первого игрока.

Графические построения осуществляются следующим образом. На горизонтальной прямой берется отрезок единичной длины. Каждой точке этого отрезка сопоставляется смешанная стратегия первого игрока по следующему правилу: р ₁ – это расстояние от точки до правого конца отрезка, а р ₂ – расстояние от точки до левого конца отрезка (рис. 21).

Рис. 21. Графическая интерпретация смешанной стратегии

Любой смешанной стратегии первого игрока на единичном отрезке будет отвечать некоторая единственная точка, найденная по указанному правилу. Таким образом, между точками отрезка и смешанными стратегиями первого игрока устанавливается взаимно однозначное соответствие.

Затем к концам единичного отрезка проводятся две вертикальные прямые (рис. 22). На левой вертикальной прямой откладываются выигрыши первого игрока, соответствующие первой его чистой стратегии (значения элементов первой строки платежной матрицы А), а на правой вертикальной прямой – выигрыши, соответствующие второй его стратегии (значения элементов второй строки матрицы А). Положительные значения элементов откладываются на прямых вверх от единичного отрезка, а отрицательные – вниз. Точки, соответствующие элементам одного столбца матрицы (стратегии второго игрока), соединяются отрезками с указанием их номеров (номеров соответствующих столбцов). На рис. 22 это четыре отрезка, соответствующие чистым стратегиям второго игрока.

Находим теперь нижнюю границу выигрышей первого игрока в виде ломаной линии, огибающей снизу все эти отрезки (эта граница показана жирной линией).

Рис. 22. Графическое решение парной игры

Расстояние от любой точки, расположенной на нижней границе, до ближайшей точки единичного отрезка, взятое с учетом знака («+», если точка границы находится выше единичного отрезка, и «–», если она расположена ниже единичного отрезка), характеризует тот выигрыш, который гарантирован первому игроку в случае выбора им смешанной стратегии . Другими словами, это расстояние совпадает с величиной , к максимизации которой стремится первый игрок.

Решение задачи первого игрока сводится, таким образом, к отысканию на нижней границе его выигрышей точки, соответствующей наибольшему выигрышу, т. е. наиболее удаленной точки от единичного отрезка. На рис. 2 это точка М, находящаяся на пересечении первого и второго отрезков. Первая и вторая чистые стратегии второго игрока называются активными, и он их должен использовать в своей оптимальной стратегии с ненулевой вероятностью. Третий же и четвертый отрезки не проходят через точку М, поэтому третья и четвертая стратегии, наоборот, называются пассивными – второй игрок не должен их использовать в оптимальной стратегии.

Далее определяются графически цена игры v как расстояние от точки М до единичного отрезка (взятое с учетом знака) и оптимальная смешанная стратегия .

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

(64)

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

.

Вычитая из первого уравнения системы второе, получим уравнение , откуда .

С учетом третьего уравнения находим , . Для определения величины v можно использовать либо первое, либо второе уравнение системы. Взяв первое, получим:

Найдем теперь оптимальную стратегию второго игрока. Как уже отмечалось, третья и четвертая стратегии его являются пассивными, поэтому . Остальные компоненты вектора находятся аналитически путем решения системы уравнений, составляемых также на основе приведенной матрицы (64).

При составлении системы для второго игрока строчки матрицы скалярно умножаются на строку неизвестных .

Приравнивая результаты умножения к цене игры v и добавляя уравнение , получим систему уравнений:

Так как значение v уже известно, для определения неизвестных достаточно взять какие-либо два уравнения этой системы. Возьмем, например, первое и третье уравнения:

Отсюда находим ,

В итоге получим следующее оптимальное решение игры в смешанных стратегиях и ее цену.

Оптимальная стратегия первого игрока:

Оптимальная стратегия второго игрока:

Цена игры:

В некоторых задачах раздела необходимо найти оптимальную игру с платежной матрицей размером m ´ 2, т. е. когда у второго игрока две стратегии. В этом

Дата добавления: 2015-07-11