Курсовая работа - Сведение матричной игры к задаче линейного программирования

Подождите немного. Документ загружается.

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

двойственных задач.

Теорема. Если одна из двойственных задач имеет оптимальное решение, то и

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

Если же в одной задаче целевая функций не ограничена, то двойственная ей

задача противоречива.

7. Сведение матричной игры к двойственной задаче линейного

программирования.

Теперь рассмотрю Сведение матричной игры к двойственной задаче

линейного программирования. Предполагаю, что матрица Н не содержит

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

Соотношениям отыскания





можно поставить в соответствие

эквивалентные им задачи

  

.;:min

,;:max









yxM

(7.1)

Здесь

 





jiij

yxaYXM

;

есть математическое ожидание выигрыша

первого игрока.

Тогда для любой чистой стратегии y(j) игрока В

 

0,,0,1,0,,0,0

1121



 njjj

yyyyyyjy 

можно записать

  





iij

xajyxM

;

, (7.2)

а для любой чистой стратегии x(i) игрока А

 

0,,0,1,0,,0)(

111



 miii

xxxxxix 

можно записать

    





jij

yaiyixM

;

. (7.3)

Следовательно, задачи (7.1) – (7.3) допускают следующую запись в форме

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







iij

xmixnjxajyxM

}1;,1,0;,1,))(;(:max{



, (7.4)







ji j

ynjymiyayixM

}1;,1,0;,1,));((:min{



. (7.5)

Нетрудно видеть, что задачи (7.4) и (7.5) взаимно двойственные, а поэтому

их оптимальные значения должны совпадать, т.е.

оптопт





, где V – цена игры

(требуемое значение эффективности).

Для задачи (7.4) положим



, (7.6)

а для задачи (7.5) положим



. (7.7)

Тогда, отыскание оптимальной смешанной стратегии х

опт

игрока А приводит

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

минимизировать линейную функцию

tttT  

(7.8)

при условиях







iij

nj ,1

;

0

mi ,1

, (7.9)

а отыскание оптимальной смешанной стратегии у

опт

игрока В привело к

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

максимизировать линейную функцию

uuuZ  

(7.10)

при условиях







jij

mi ,1

;

0

nj ,1

. (7.11)

Исходя из основной теоремы теории двойственности, задачи (7.8) – (7.11)

имеют конечное решение и

maxmin

ZT 

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

линейного программирования, рассмотрю пример выбора оптимального

ассортимента и объёма продукции швейного предприятия.

Рассмотрю работу швейного предприятия, выпускающего детские костюмы,

платья и плащи, сбыт которых зависит от состояния погоды, при этом реализация

продукции происходит через фирменные магазины.

По данным наблюдений за предшествующие одиннадцать лет предприятие в

течение апреля – мая в условиях тёплой погоды может реализовать 600

костюмов, 2000 платьев и 300 плащей, в условиях прохладной погоды – 1000

костюмов, 500 платьев и 800 плащей и в условиях обычной погоды 800 костюмов,

1100 платьев и 600 плащей. Затраты на единицу продукции в течение указанных

месяцев составили для костюмов 30 ден. ед., для платьев 10 ден. ед. и плащей 15

ден. ед., а цена реализации равна соответственно 50 ден. ед., 20 ден. ед. и 28 ден.

ед.

Задача заключается в максимизации средней величины прибыли от

реализации выпущенной продукции с учётом неопределённости погоды в

рассматриваемые месяцы.

Подобная задача рассматривается как игра с природой. Её отличительная

особенность состоит в том, что в ней сознательно действует только один из

участников (предприятия), называемый игроком 1. Игрок 2 (природа) сознательно

против игрока 1 не действует, а выступает как не имеющий конкретной цели и

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

Первоочередной задачей является построение платёжной матрицы.

Предприятие располагает тремя чистыми стратегиями: стратегия Р

расчетом на тёплую погоду, стратегия Р

с расчётом на прохладную погоду и

стратегия Р

с расчётом на обычную погоду.

Природа, рассматривается как второй игрок, также располагает тремя

стратегиями: обычная погода (стратегия П

), прохладная погода ( стратегия П

) и

тёплая погода (стратегия П

Если предприятие выберет стратегию Р

, то в случае обычной погоды

(стратегия природы П

) доход составит

       

.,.17900)10002000(10203001528110010206003050 едден

в случае прохладной погоды (стратегия природы П

) доход будет равен

 

.,.5900500200010300135001060020 едден

и в случае теплой погоды (стратегия природы П

) имеем доход, равный

..359003001320001060020 едден

Если предприятие выберет стратегию Р

, то реализация продукции в

условиях обычной погоды даёт доход

   

,.2200060080013600100020600135001080020 едден

в условиях холодной погоды доход будет

.,.354008001350010100020 едден

а в условиях тёплой погоды имеем доход

   

..640030080013600100020300135001060020 едден

Если предприятие выберет стратегию Р

, то в случае обычной погоды доход

будет равен

.,.348006001310001080020 едден

при прохладной погоде имеем доход, равный

 

.,.22800500110010600135001080020 едден

и в случае тёплой погоды доход составит

   

едден.1600030060013600800203001311001060020 

Результаты вычислений сведены в табл. 7.1.

Платёжная матрица рассматриваемой производственной ситуации имеет вид















160002280034800

64003540022000

35900590017900

. (7.12)

Таблица 7.1

Платёжная матрица

Стратегия

природы

Стратегия

предприятия

Обычная

Прохладная

Тёплая

Тёплая – Р

17900 5900 35900

Прохладная – Р

22000 35400 6400

Обычная – Р

34800 22800 16000

Платит, естественно, не природа, а некая третья сторона (или совокупность

сторон, влияющих на принятие решений игроком 1 и объединённых в понятие

«природа»). В данной ситуации платит само предприятие, получая меньшую или

большую прибыль.

Для матрицы (7.12), исходя из общей постановки (7.8) – (7.11), имеем

следующую пару двойственных задач:

для определения оптимальной стратегии Р нужно решить задачу линейного

программирования: найти минимум функции

321

tttT 

(7.13)

при ограничениях















.3,2,1,0

,116000640035900

,122800354005900

,1348002200017900

321

ttt

(7.14)

Оптимальную стратегию игрока 2 определим, решив задачу линейного

программирования: найти максимум функции

321

uuuZ 

(7.15)

при ограничениях















.3,2,1,0

,1160002280034800

,164003540022000

,135900590017900

321

uuu

(7.16)

Решаю более простую обратную задачу (7.15) – (7.16). Вводя положительные

базисные переменные (б.п.)

654

,, uuu

, систему неравенств (7.16) записываем в

виде системы уравнений















,1160002280034800

,164003540022000

,135900590017900

321

6321

5321

4321

zuuu

uuuu

(7.17)

Систему (7.17) запишем в виде симплекс-таблицы 7.2.

Таблица 7.2

Симплекс-таблица

С.П.

Б.П.

17900 5900 35900 1

22000 35400 6400 1

34800 22800 16000 1

Z -1 -1 -1 0

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

Так как в табл. 7.3 все элементы в z – строке и 1 – столбце неотрицательны,

то получаем оптимальное решение.

Таблица 7.3

Симплекс-таблица

С.П.

Б.П.

908006790810248

11758766158



1410461980

14703

384005092896117

94597304902

6724002037243074

34323736801

01410461980

489549



04231385940

2094351

5289232245

35148

5289232425

113361

9649881772401474

611234067270

01410461980

524987



9536002037158446

94403163229



8599528076781399

93226653604

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

двойственных задач:

С.П. Б.П.

Транспортируем табл. 7.3, знаки перед всеми элементами, кроме элементов z

– строки, меняем на обратные, переменные

заменяем на соответствующие

переменные

, получаем табл. 7.4.

Таблица 7.4

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

С.П.

Б.П.

10259,0





10347,0





10697,0





10028,0





10104,0





10495,0





10372,0





10227,0





10903,0





10066,0





10216,0





10225,0





10217,0





10221,0





10041,0





10408,0





Из табл. 7.4 получаем оптимальное решение. Так как

1048,0





, то

цена игры

469,0V

. Из

10225,0





получаем

469,0

x

. Аналогично

получим

472,0

x

059,0

x

Это означает, что означает, что стратегию Р

нужно применять с

вероятностью

469,0

, стратегию Р

– с вероятностью

472,0

, и стратегию Р

– с

вероятностью

059,0

Формируем оптимальный план производства:

   

 472,0.800.500.1000469,0.300.2000.600 плащплаткостплащплаткост

 

.554.1239.801059,0.600.1100.800 плащплаткостплащплаткост 

Таким образом, предприятие при производстве 801 костюма, 1239 платьев и

554 плащей получит наибольшую прибыль, которая в среднем составит 20833

ден. ед.

Для приведённой формулировки производственной задачи получили

однозначный ответ.

Недостатком данного метода является достаточно большой объём

вычислительных операций даже для матрицы с размером

33

. Однако

применение ЭВМ снимает это неудобство.

7.1. Сведение задачи линейного программирования к матричной

игре.

Имеет место и обратное: всякую задачу линейного программирования можно

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

указать такую матрицу выигрыша, что решение соответствующей ей игры будет

эквивалентно решению данной пары двойственных задач линейного

программирования.

Отмечу, что задача (7.4) имеет и непосредственный экономический: к ней

сводится оптимизация плана выпуска продукций в заданном ассортименте.

Пусть имеется

режимов работы некоторого оборудования с фондом

полезного времени

 

0TT

для выпуска

продуктов; за I час работы в режиме

 

mi ,1

выпускается

продукта

 

njj ,1

. Требуется максимизировать выпуск

продукции в заданном ассортименте, причём, один ассортиментный набор

содержит

продукта

 

0Qj

Решение. Обозначая через R искомое количество ассортиментных наборов и

через

 

mix

,1

затраты времени на работу в режиме i, получаем задачу.

Найти вектор

 

xxxx ,,,



и число R, удовлетворяющие условиям

 

mix

,1,0 

, (7.18)





1

, (7.19)

 

njRQxq

jiij

,1, 



, (7.20)

maxR

. (7.21)

Полагая



a 



, сведём задачу (7.18) – (7.21) к виду (7.4):

   

}1,,1,0,,1,:max{

1 1

 

 



iiiij

tmitnjVtaV

. (7.22)

Следовательно, матрица выигрышей имеет вид

aH 

. К задачам (7.4) –

(7.4), а следовательно, (7.8) – (7.9) и (7.10) – (7.11), сводятся некоторые варианты

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

Приложение теории игр в принципе возможно во всех областях человеческой

деятельности, где наблюдается конфликты или же принятие решений происходит

в условиях неопределённости. Практическое же составление теоретико-игрвых

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

имеет объективные основания и связано с общей проблемой измерений величин в

экономике, психологии и т.д. Вместе с тем качественные выводы, даваемые

теорией игр, на основе использования приближённых или условных данных могут

принести большую пользу.