Математическая постановка задачи

Лабораторная работа № 1

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

Цель работы: приобретение навыков в постановке и решении экономических задач, которые описываются игровыми моделями m × n, методами линейного программирования в среде электронных таблиц MS Excel.

1. Сведение игры m × n к ЗЛП (основные положения)

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, но не имеет принципиальных трудностей, если ее решение свести к решению задачи линейного программирования (ЗЛП).

Пусть игра m × n задана платежной матрицей

Н = (h_ij), i =1,2,...,m; j=1,2,...,n.

Игрок А обладает стратегиями A₁ , A₂ ,..., A_m , игрок В - стратегиями B₁ , B₂ ,..., B_n, которые игроки А и В могут применить с вероятностями соответственно p₁, p₂, …, p_m и q₁, q₂,..., q_n (рисунок 1).

стратегии игрока А	Ai Вj		стратегии игрока В
В1	В2	…	Вn
	вероятности	q1	q2	…	qn
A1	p1	h11	h12	…	h1n
A2	p2	h21	h22	…	h2n
…	…	…	…	…	…
Am	pm	hm1	hm2	…	h2m

Рисунок 1 – Исходные данные игры m × n.

Необходимо определить оптимальные стратегии

S*_A = (p*₁,p*₂,...,p*_m) и S*_B = (q*₁,q*₂,..., q*_n),

где p*_i, q*_j - вероятности применения соответствующих чистых стратегий A_i, B_j,

причем p*₁ + p*₂ +...+ p*_m =1,

q*₁ + q*₂ +...+ q*_n = 1.

Математическая постановка задачи

1. Определение оптимальной стратегии игрока А

Оптимальная стратегия S*_A удовлетворяет следующему требованию: она должна обеспечивать игроку А

· средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В, и

· выигрыш, равный цене игры v, при оптимальной стратегии игрока B.

Замечание: без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы h_ij ≥ 0.

Средние выигрыши игрока А, если он применяет оптимальную смешанную стратегию S*_A = (p*₁,p*₂,...,p*_m) против любой чистой стратегии B_j игрока В, равны

h_1j p₁ + h_2j p₂ +...+ h_{m j} p_m,

где j =1,2,...,n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁,A₂ ,...,A_m и результаты складываются), и они должны быть не меньше цены игры ν:

(1)

Разделим каждое из неравенств на число v > 0 и введем новые переменные:

x₁ = , x₂ = ,..., x_m = (2)

Тогда система неравенств (1) примет вид:

(3)

Цель игрока А - максимизировать свой гарантированный выигрыш, т.е. цену игры v.

Разделив на v ≠ 0 равенство p₁+ p₂ +...+ p_m = 1, получим, что переменные x_i (i=1,2,...,m) удовлетворяют условию:

x₁ + x₂ +...+ x_m = .

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

определить значения переменных x_i ≥ 0, i=1,2,..., m, такие, чтобы они удовлетворяли системе ограничений (3) и при этом целевая функция обращалась в минимум:

Z = x₁ + x₂ +...+ x_m = (4)

Решив эту ЗЛП в постановке (3)-(4), можно получить оптимальное решение - оптимальную стратегию S^*_A: вероятности применения стратегий A₁,A₂,...,A_m соответственно p*₁, p*_2,..., p*_m.

2. Определение оптимальной стратегии игрока В

Оптимальная стратегия игрока В: S*_B = (q*₁, q*₂,..., q*_n), состоит в том, что игрок В стремится минимизировать свой гарантированный проигрыш, т.е. найти максимум целевой функции. .

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

Поэтому переменные q₁ , q₂,..., q_n удовлетворяют неравенствам:

(5)

Введем новые переменные y_j, разделив каждое неравенство системы (5) на v ≠ 0:

y_j = , где j = 1, 2,..., n (6)

Тогда система неравенств (5) будет иметь вид:

(7)

Переменные y_j (1, 2,..., n) удовлетворяют условию у₁ + у₂ +... + у_n = .

Игра свелась к следующей задаче:

определить значения переменных y_j ≥ 0, j = 1, 2,..., n, которые удовлетворяют системе неравенств (7) и максимизируют линейную функцию

Z' = y₁ + y₂ +...+ y_n= (8)

Решение ЗЛП (6)-(7) позволяет определить оптимальную стратегию S*_B: вероятности применения стратегий В₁,В₂,...,В_n соответственно q*₁, q*₂,..., q*_n.

При этом цена игры v= = (9)

При сравнении математических постановок задач определения оптимальной стратегии S^*_A игрока А: (3)-(4), и оптимальной стратегии S*_B игрока В: (7)-(8), (рисунок 2) можно сделать следующий вывод: эти ЗЛП (3)-(4) и (7)-(8) являются взаимно-двойственными.

Рисунок 2 – Сравнение математических постановка ЗЛП нахождения оптимальных стратегий игроков А и В

Действительно, двойственная задача формулируется по следующим правилам:

1. каждому i – тому ограничению исходной задачи соответствует переменная у_i 0 двойственной задачи;

2. каждой переменной исходной задачи х_j соответствует ограничение двойственной задачи;

3. матрица коэффициентов при двойственных переменных в ограничениях двойственной задачи получается путем транспонирования матрицы коэффициентов при переменных в исходной задаче;

4. если в исходной задаче ограничения имеют знаки неравенств , то в двойственной они будут - , и наоборот;

5. правые части ограничений в двойственной задаче равны соответствующим коэффициентам при переменных в целевой функции исходной задачи;

6. коэффициенты при двойственных переменных в целевой функции двойственной задачи равны правым частям ограничений исходной задачи;

7. если исходная задача решается на максимум целевой функции, то двойственная – на минимум, и наоборот.

По теореме двойственности решение одной из двойственных задач дает решение и прямой, и обратной задачи.

2. Решение экономической задачи, описываемой игровой моделью m × n, методами линейного программирования в среде MS Excel

При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы:

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

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

3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.

Условие задачи:

предприятие может выпускать три вида продукции (A ₁, A ₂ и A ₃ ), получая при этом прибыль, зависящую от спроса, который может быть в одном из четырех состояний (B ₁, B ₂, B ₃, B ₄ ).

В таблице 1 приведены значения прибыли h_ij, которую получит предприятие при выпуске i -и продукции с j -м состоянием спроса.

Таблица 1. Прибыль от реализации определенного вида продукции при соответствующем состоянии спроса

Ai Вj	В1	В2	В3	В4
A1
A2
A3

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

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