2.4 Двойственные задачи и их решение

Каждой задаче линейного программирования ставят в соответствие другую задачу, построенную на основе тех же данных по определенным правилам.

Эти правила сводятся к следующему:

• все ограничения исходной задачи приводят к одному виду: в случае ограничения должны иметь вид неравенств типа “”, в случае - типа “”. Неравенства, не соответствующие этому условию, умножают на (- 1);

• выписывают матрицу коэффициентов при неизвестных и транспонируют ее ;

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

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

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

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

	- 1	- 2	- 4
	- 5	- 1	- 5
	- 1	1	3
	- 2	1

Запись одной задачи идет по строкам, другой – по столбцам.

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

Например, в рассмотренной задаче имели:

-строка		-8/3	0	0	0	-1/6	-7/6

Дополнительными были столбцы , , , поэтому получаем:

.

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

2.5 Анализ матричной игры

Теория игр – это математическая теория конфликтных ситуаций. Игра – конфликтная ситуация, регламентированная определенными правилами:

• порядок выполнения ходов;

• порядок выполнения каждого хода;

• количественный результат игры.

Наиболее изучены матричные игры. Например,

	3	4	5
	2	6	4
	5	3	2

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

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

а) Анализируем игру с позиций стороны . Если игрок выбирает стратегию, то его гарантированный выигрыш (или самое худшее, что его ожидает) равен 3. Если он выбирает вторую стратегию, то гарантированная величина выигрыша равна 2. Наконец, если он использует стратегию, то гарантирует себе выигрыш 2. Эти величины являются минимальными в строках. Очевидно, что из этих гарантированных выигрышей сторонапостарается выбрать наибольшее значение – это 3. Данную величину называютнижней ценой игры или максимином и обозначают: .

б) Анализируем игру с позиции стороны . Если игрок выбирает стратегию, то самое худшее для него – проигрыш 5. Если он остановится на стратегии, то худший исход – проигрыш 6. Если же он выберет стратегию, то наихудший для него результат – проигрыш 5. Эти величины являются максимальными в столбцах. Конечно, игроквыберет стратегиюили, чтобы уменьшить гарантированный проигрыш – это число 5. Эту величину называютверхней ценой игры или минимаксом и обозначают: .

в) Цена игры – это величина, отражающая объективное соотношение сил, она всегда удовлетворяет условию:. В данном примере:.

Если , то игра имеет решение в конкретных стратегиях, называемыхоптимальными. Эти оптимальные стратегии являются устойчивыми, обеспечивают равновесие в игре, а цена игры называется “седловой точкой”. Если такой ситуации нет, то оптимальные стратегии будут выглядеть так:

; .

где – вероятности стратегий стороны ;

–вероятности стратегий стороны .

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

Анализ матричной игры проводится в два этапа:

• формируются двойственные задачи, решают одну из них симплекс-методом и записывают решение обеих двойственных задач;

• определяют решение игры.

1. Запишем две двойственные задачи на основе приведенной платежной матрицы:

а) для участника	б) для участника

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

Данная задача приобретет вид:

В результате использования симплекс-алгоритма получим:

Базис			– 1	– 1	– 1	0	0	0
	0	1	3	4	5	1	0	0
	0	1	2	6	4	0	1	0
	0	1	5	3	2	0	0	1
-строка		0	1	1	1	0	0	0
	0	2/5	0	11/5	19/5	1	0	–3/5
	0	3/5	0	24/5	16/5	0	1	–2/5
	– 1	1/5	1	3/5	2/5	0	0	1/5
-строка		–1/5	0	2/5	3/5	0	0	–1/5
	– 1	2/19	0	11/19	1	5/19	0	–3/19
	0	5/19	0	56/19	0	–16/19	1	2/19
	– 1	3/19	1	7/19	0	–2/19	0	5/19
-строка		–5/19	0	1/19	0	–3/19	0	–2/19
	– 1	3/56	0	0	1	24/56	–11/56	–10/56
	– 1	5/56	0	1	0	–16/56	19/56	2/56
	– 1	7/56	1	0	0	0	–7/56	14/56
-строка		–15/19	0	0	0	–8/56	–1/56	–6/56

Решение будет иметь вид:

а)

б)

2. Найдем решение игры:

а) определим цену игры, – эта величина характеризует количественный результат игры:

.

б) найдем вероятности стратегий:

; .

; ; .

; ; .

в) составим оптимальные стратегии для участников

; .

Как видим, для достижения оптимального результата стороне рекомендуется из 15 раз стратегию использовать 3 раза, стратегию – 5 раз, стратегию – чаще всего, а именно 7 раз. Для стороны стратегию – рекомендуется использовать реже всего – 1 раз из 15, гораздо чаще нужно применять стратегию – 6 раз из 15, и более всего – стратегию . Если кто-то из участников отклонится от этих рекомендаций, то он ухудшит только свое собственное положение.