Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. CИТУАЦИОННЫЕ ЗАДАЧИ
  2. CИТУАЦИОННЫЕ ЗАДАЧИ
  3. CИТУАЦИОННЫЕ ЗАДАЧИ
  4. CИТУАЦИОННЫЕ ЗАДАЧИ
  5. CИТУАЦИОННЫЕ ЗАДАЧИ
  6. CИТУАЦИОННЫЕ ЗАДАЧИ
  7. CИТУАЦИОННЫЕ ЗАДАЧИ

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

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

 

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

 

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

 

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

 

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

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

Игрок А обладает стратегиями A1 , A2 ,..., Am , игрок В - стратегиями B1 , B2 ,..., Bn, которые игроки А и В могут применить с вероятностями соответственно p1, p2, …, pm и q1, q2,..., qn (рисунок 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*1,p*2,...,p*m) и S*B = (q*1,q*2,..., q*n),

где p*i, q*j - вероятности применения соответствующих чистых стратегий Ai, Bj,

причем p*1 + p*2 +...+ p*m =1,

q*1 + q*2 +...+ q*n = 1.

 

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

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

 

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

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

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

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

Средние выигрыши игрока А, если он применяет оптимальную смешанную стратегию S*A = (p*1,p*2,...,p*m) против любой чистой стратегии Bj игрока В, равны

 

h1j p1 + h2j p2 +...+ hm j pm,

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

 

 

(1)

 

 

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

x1 = , x2 = ,..., xm = (2)

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

 

 

(3)

 

 

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

Разделив на v ≠ 0 равенство p1+ p2 +...+ pm = 1, получим, что переменные xi (i=1,2,...,m) удовлетворяют условию:

x1 + x2 +...+ xm = .

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

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

 

Z = x1 + x2 +...+ xm = (4)

 

Решив эту ЗЛП в постановке (3)-(4), можно получить оптимальное решение - оптимальную стратегию S*A: вероятности применения стратегий A1,A2,...,Am соответственно p*1, p*2,..., p*m.

 

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

 

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

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

Поэтому переменные q1 , q2,..., qn удовлетворяют неравенствам:

 

 

(5)

 

 

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

 

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

 

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

 

 

(7)

 

 

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

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

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

 

Z' = y1 + y2 +...+ yn= (8)

 

Решение ЗЛП (6)-(7) позволяет определить оптимальную стратегию S*B: вероятности применения стратегий В12,...,Вn соответственно q*1, q*2,..., 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 1, A 2 и A 3 ), получая при этом прибыль, зависящую от спроса, который может быть в одном из четырех состояний (B 1, B 2, B 3, B 4 ).

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

 

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

 

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

 

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


Дата добавления: 2015-07-08; просмотров: 185 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Последовательность расчета| Решение

mybiblioteka.su - 2015-2024 год. (0.014 сек.)