Основная теорема двойственности

Если одна из двойственных задач имеет оптимальное решение, то вторая задача также имеет оптимальное решение, причем экстремальные значения целевых функций на этих решениях совпадают:

.

Если же одна из задач неразрешима из-за неограниченности целевой функции (или), то допустимое множество решений второй задачи пусто.

Из двух задач (1.8) и (1.9) первая решается симплекс-методом обычно легче.

Если в (1.8) все , то, приводя исходную задачу к основной форме, получим следующую систему ограничений:

Тем самым, сразу становится известен первый опорный план:

и, соответственно, первая симплекс-таблица:

Базис	x1	…	xn	xn+1	…	xn+m	bi
xn+1	a11	…	a1n	1	…	0	b1
…	…	…	…	…	…	…	…
xn+m	am1	…	amn	0	…	1	bm
	-c1	…	-cn	0	…	0

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

Базис	x1	…	xn	xn+1	…	xn+m	bi
…	…	…	…	…	…	…	…
	…	…	..		…

Вторая теорема двойственности

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

Третья теорема двойственности

Значения компонент в оптимальном решении двойственной задачи представляет собой коэффициенты чувствительности к изменениям значений свободных членов в исходной задаче.

Иначе говоря, пусть наряду с задачей ЛП (1.8) рассматривается также задача вида:

(1.12)

Пусть также и- оптимальные значения целевых функций соответственно задач (1.8) и (1.12),- оптимальный план задачи (1.9). Тогда значенияисвязаны соотношением:

(1.13)

Глава 2. Элементы матричных игр

2.1. Формальное представление игр. Понятие матричной игры

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

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

В силу такой значительной распространенности конфликтных ситуаций было бы интересно провести научный анализ обобщенной конфликтной ситуации и попытаться выработать разумные правила поведения для ее участников. Именно этим и занимается теория игр - математическая теория конфликтных ситуаций, в которой под игрой понимается математическая модель конфликтной ситуации.

Теория игр впервые была систематически изложена Дж. фон Нейманом и О. Моргенштерном в 1944 году в книге «Теория игр и экономическое поведение», хотя отдельные результаты были опубликованы еще в 20-х годах. В дальнейшем новая дисциплина получила как теоретическое, так и широкое прикладное развитие. Однако экономические вопросы, по-видимому, остаются главными объектами приложения теории игр.

Рассмотрим основные элементы, с помощью которых описывается любая игра (любой конфликт).

Пусть в игре участвуют nконфликтующих сторонP₁,P₂,…,P_n, называемых обычноигроками. Обозначим черезIмножество всех таких игроков:I={P₁,P₂,…,P_n}.

В течение одной партии (однократном осуществлении игры) каждый игрок P_iможет придерживаться одной из возможных линий своего поведенияs_i, называемыхстратегиями, выбираяs_iиз некоторого заданного множестваS_i. В результате таких выборов складывается некоторый набор стратегий всех игроков={s₁,s₂,…,s_n}, называемыйситуацией.

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

Таким образом, формальное определение игры сводится к заданию трех классов множеств:

а) множества игроков;

б) совокупности множеств стратегий каждого из игроков {S_i}_iI;

в) совокупности функций выигрыша каждого из игроков {H_i}_iI.

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

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

Матричная игра описывается следующим образом.

_{ В игре участвуют 2 игрока: допустим, игроки А и В.}

_{ Каждый из игроков располагает конечным набором стратегий: А1,…,АmиВ1,…,Вn- возможные стратегии игроков А и В ( в этом случае говорят, что игра имеет размерностьmхn).}

_{ Значения функций выигрыша НАиНВигроков в каждой ситуации (Аi,Bj) равны по величине и противоположны по знаку, то есть}

_{НА(Аi,Bj)=HB(Ai,Bj)= aij}

_{для всех i=1,…,m,j=1,…,n(выигрыш одного из игроков равен проигрышу другого).}

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

(2.1)

Строки этой матрицы соответствуют стратегиям игрока А, а столбцы - стратегиям игрока В; элементы а_ijзадают выигрыш игрока А в ситуации, когда А выбирает стратегиюА_i, а В – стратегиюВ_j.

Пример 2.1.Каждый из двух игроков А и В независимо друг от друга кладет на стол монету в 1 рубль или в 2 рубля. Если монеты одинаковые, то выигрывает игрок А, если разные - игрок В. Выигрыш равен сумме достоинств монет. Необходимо построить платежную матрицу игры.

Решение. Проанализируем поведение каждого из игроков. Игрок А может положить монету 1 руб. ( обозначим эту стратегию черезА₁) или монету 2 руб. (стратегияА₂). Точно также игрок В может положить монету 1 руб. ( стратегияВ₁) или монету 2 руб. ( стратегияВ₂).

Если игрок А положит 1 руб. и игрок В тоже положит 1 руб., то есть осуществится ситуация (А₁,В₁), то в силу одинаковости монет выигрывает игрок А, и его выигрыш равен а₁₁= Н_А(А₁,В₁)=1+1=2. Если игрок А положит 1 руб., а игрок В – 2 руб. ( ситуация (А₁,В₂) ), то игрок А проигрывает В 1+2=3 рубля, т. е. «выигрыш» А равен а₁₂=-3. Аналогично находим а₂₁=-(2+1)=-3, а₂₂=2+2=4. Таким образом, для заданной игры получим следующую платежную матрицу