Методы оптимизации в экономике, страница 5

Для решения матричной игры любой размерности воспользуемся сведением этой игры к задаче линейного программирования [1,21. Не нарушая общности, будем считать, что элементы матрицы А положительны (а1 ~ 0). Если это не так, то, прибавив ко всем элементам А некО70рое ДОстаточно большое а ~ 0 > получим» трат» ги»ъ» ски эквивалентную игру, где Н = шах ~ а; ~ + 1. Обозначим через х произвольную стратегию 1-го игрока, х Е Х и через Р'(х) = ппп х А. а1 . аг1 где х А .. = [ х1 хг ... х,, 1 Из положительности элементов матрицы А следует, что У(х) «хА.,, у = 1,л . Оптимальность стратегии х равноси чала тому.

что и = щах~ (х) ~' (А) . (4.7) хЯХ Рассмотрим вектор х = — х, для которого из неравенства У(х) (4.6) имеем х А.1 ~ 1; х ~ О . Ш Поскольку х Е Х, то Х х,. - — или У(х) хХ = —;У 1 ш 1~(х) ~ пф Из (4.7) и (4.8) следует, что стратегия х оптимальна тогда и только тогда, когда ш1пх ~ У.

(4.9) хА. ~ 1; у=~и, Аналогичные рассуждения для стратегий у 2-го игрока приводят к задаче линейного программирования вида шаху ~л хА.;$" ~ 1; 1=Т,ж', которая является двойственной к задаче (4.9). Решение матричной игры получается из решения задачи линейного программирования (4.9) или двойственной к ней задачи (4.10). Задачу линейного программирования будем решать методом сим-~ ! плекс-таблиц (Ц. 4.2. Примеры игровых математических моделей в экономике Как правило, поведение индивидуумов или фирм экономической системы зависит от целого ряда факторов, которые заранее предан деть не представляется возможным, например, конъюнктура на рынке покупательский спрос, поставки смежных отраслей, погодные услови и т.д. Взаимодействие предприятий, фирм протекает в условиях конф ликта и неопределенности, что обусловливает целесообразность по строения игровых моделей.

1 П р и м е р 1, Б некотором городе имеется две фирмы, которые помимо своих основных изделий могут выпускать побочную продукцию одного н того же назначения, отличающуюся по оформлению, по удобству пользования и т.п. Первая фирма выпускает продукцию типа Д1, Д2, ..., Д, вторая — типа М1, М2, ..., М . Себестоимость и цена Р * и и ъ пп за ."ъв ъптют«ъ и с;л аидуо 11~иуд~ыцйь ицпаиаиои. ч иъ.,цьк ~ ыы ии ивам* . р * спроса установили, что в городе найдет сбыт М единиц продукции всех типов. Будем считать первую фирму 1-м игроком, вторую — 2-м игроком, тогда в городе найдет сбыт Р; Ж товаров типа Д и11 — Р;.)Ж товаров типа М, О < Р;.

< 1 . Принимая доход от продажи единицы товара равным 1, запишем матрицу выигрышей 1-го игрока в виде: Р11 ~~~ Р12 Л' Р21 ~~ Р22 ~ Матрица выигрышей для 2-го игрока записывается в виде 1а 1 = 11 — Р ) Ж, Так как в любой ситуации сумма доходов 1-го и Ц !/ 2-го игроков одинакова, т.е. М = Р; Ю + 11 — Р;.) Ж, то имеем конечную игру с постоянной суммой, являющуюся стратегически эквивалентной игре с нулевой суммой 11,21. Увеличение выигрыша 1-го игрока эквивалентно уменьшению выигрыша 2-го игрока, т.е. интересы игроков противоположны.

Поэтому 1-й игрок максимизирует сбыт Р; товаров, а 2-й — минимизирует. Следовательно, игра двух лиц, заданная матрицей А„моделирует рассматриваемый конфликт. Решение игры Г = сХ, У, А(т х а) > определяет оптимальные стратегии х,у 1-го и 2-го игроков, а также математическое ожидание выигрыша 1-го игрока, равное $'~А). Так как сумма проданных товаров равна Ф, математическое ожидание реализованных товаров 2-й фирмой равно Ж вЂ” К~А). Покажем решение этой игры на числовых примерах. а) Допустим, что 1-я фирма помимо своей основной продукции выпускает детские игрушки типа Д1 Д2,Дз Д4 Д5, а 2-я фирма — игрушки типа М1 М2,Мз М4 М5. Будем считать, что затраты на производство каждого типа игрушек одинаковы и цена одна. Прогноз сбыта игрушек задан в виде: 31 Первая фирма Ожидается, что всего будет реализовано 10000 игрушек.

Требуется определить типы игрушек, выпускаемых ка;кдой фирмой. Матрица выигрыша 1-го игрока будет иметь вид Согласно условиям стратегической эквивалентности, достаточно решить игру Г~ < Х,У,А~(5х5) >, где А~ = 0,001А, тогда 5 5 4 5 2 5 4 7 1 6 2 3 4 1 7 3 б 7 3 2 4 4 3 О 2 Из анализа матрицы А видно, что имеются доминирующие стратегии для 1-го и 2-го игроков, учет которых приводит к матричной игре вида 51 Г = < Хз, Уз, Аз ( 2 х 2 ) >, где Аз = Оптимальные стратегии находим по формулам (4.3)„(4.4), а цену игры — по формуле (4.5).

Г 2/3 ~ 5/9 В результате имеем хз = ~ 1, уз = 4, что соответствует оптимальным стратегиям исходной игры: 32 0 О О В результате получаем игровую математическую модель задачи: 8 2 11 1 7 З~ Г = «Х,У,А(Зх3) > А = Для определения решения этой игры воспользуемся формулами (4.9) и (4.10); Для 1-го игрока примем х = и получим задачу линейного программирования вида ш1п(х1 + хЗ + хЗ); Зх~ + 4х2 + хз ~ 1; 2х1 + 5хз + 7хз ~ 1; 4х~ + бхай + Зхз а 1, х; а О, ~' = 1,3; Таким образом, 1-я фирма выпускает игрушки типа Д~ и Дз с вероятностями 2/3, 1/3, а 2-я фирма выпускает игрушки типа М4 и М5 с вероятностями соответственно 5/9 и 4/9.

Вероятности соответствуют пропорциональности выпуска различных типов игрушек, Математическое ожидание числа реализованных игрушек первой и второй фирмой соответственно равно 11000/3 и 190093. Рассмотрим теперь случай, когда прогноз сбыта игрушек задан в виде: 1 2 31' ЗУ~ + 2У2 + 4Уз ~ 4~~ + 5Уз + б Уз ~ У~ + 7 Уз + 3 Уз ~ 1 1; У~0,~=1,3 Очевидно, что вторм задача линейного программировании требует меньше вычислений. Используем метод сиплекс-таблиц. Приведем задачу к канонической форме и составим для нее симплекс-таблицу: ша" ~~~ + У2 + Уз): 8 У~ + 2У2 + 4 Уз + У4 = 1; 4 У] + 512 + б1з + У5 = 1 ' У~ + 7 Уз + 3 Уз + У6 = 1 , У ~ 0 , у = 1,6 .

Из таблицы имеем Согласно двойственным переменным получаем оптимальную стра- тегию для 1-го игрока: х'т - Р~7 6~7 о) . Аналогично можно решить следующие задачи, исходные данные для которых приведены ниже . а) Рассмотреть случай, когда прогноз сбыта игрушек определяется следующим образом: б) Составить игровую математическую модель для примера 1, когда прогноз сбыта игрушек определяется в виде: в) Составить математическую модель для примера 1, сбыта игрушек определяется в виде: Приведем другие примеры экономических задач.

П р и м е р 2. Сельхозпредприятие может посеять одну из четырех культур А1, Аз, Аз, А4. Определить, какую из культур сеять, если при прочих равных условиях урожай зависит от погоды„а посев должен обеспечить наибольший доход. Составить математическую модель и найти решение. Рассмотреть следующие варианты: П р н м е р 3. На базе торговой организации имеется и *ипов ~оваро~, которые завоз~тс~ и ма~аз~~. В реал~ной ситуации имеется неопределенность покупательского спроса. Требуется выбрать товары таких типов. которые дадут магазину максимальный доход. Если товар типа 1',1' = Т,л, будет пользоваться спросом, то мага- и ации поч~чит прибыль Р:.

Если товар не будет пользоваться спросом, то убытки от его хранения, порчи принесут магазину убыток Математической моделью рассматриваемого примера будет игра, в которой в качестве 1-го игрока выступает магазин, а в качестве 2-го игрока — покупательский спрос. Каждая из сторон имеет п стратегий: 1-я стратегия 1-го игрока — заноз 1-го — товара, !' -я стратегия 2-го игрока — спрос на ! -й товар. Матрица выигрышей магазина определяет его доход. В этом случае антагонистическая игра за ается матрицей выигрышей для 1-го игрока Найти решение матричной игры. Рассмотреть следующие варианты: Б) Тип тонара Исходные условия 1.

Воробьев Н.Н. Лекции по теории игр для зкоиомистов-кибернетиков. — М.: Наука, 1986. 2. Волкова ТБ., Корнев Ю.Н. Методы и алгоритмы решения задач исследования операций с использованием ЗВМ. — М,: Изд-во МАЙ, 1992. Динамическим программирОВанием называют метод реш~ния задач Оптимального уп"авления многошаговыми динамическими процессами.

Основоположником метода динамического программирования, ПОЛУЧИВШИМ разВИТИЕ С 50-Х ГОДОВ, яВЛяется ""Ерих ЧСКИй Матсматнк Ричард Эрнест Беллман. В этой главе мы рассмотрим постановку задачи оптимального управления дискретным динамическим процессом, выведем уравнения Беллмана для такой задачи, изучим алгоритм ее решения с использованием урав, нения Беллмана и применим этот алгоритм для двух экономических задач: задачи замены оборудования и задачи распределения ресурса.

5.1. Задача оптимального управления дискретным динамическим процессом Рассмотрим процесс, протекающий с дискретным Временем А = О, 1, ...,Ф, где М вЂ” число шагов или этапов. В каждый момент времени Й (или на каждом к-м шаге) процесс характеризуется состоянием х~, принимающим значение из множества Возможных состояний Х~. Это множество может быть как непрерывным (например, множество действительных чисел от 0 до 5), так и дикретным (например, множество целых чисел от О до 5). Состояние процесса В момент Времени к + 1 зависит От состОяния процесса В момент Времени Й и От того, какое управление и~ воздействует на процесс в момент времени Й.

Управление и~ принимает значение из множества возможных управлений У~, которое, как и Х~, может быть как непрерывным, так и дискретным. Зависимость состояния х~ ~ от х~ и и~ называют уравнением состояния и записывают в виде х~+ 1 = ~к(~к п~). (5.1) Зная начальное состояние процесса х О и задавая на каждом шаге управление и~ (Й = О, 1, ..., Ф вЂ” 1), можно определить состояние процесса В каждый момент времени к (рис.5.1), Зафиксировав хо и задавая различные наборы управлений ( ио, и1, и2, ..., и~ 1 ), можно получить различные многошаговые процессы. Для того чтобы сравнить эти процессы между собой, вводят понятие качества или цены процесса. Введем оценку каждого перехода от состояния х~ к состоянию х~, ~, происходящего при Воздейст- вии на процесс управления и», и обозначим ее Г»(х»,и»), а также оценку Г~ (х,;) состояния системы на последнем шаге.