Принцип оптимальности и реккурентные соотношения.

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

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

 

 

 

31. Задача распределения капитальных вложений: постановка, математическая модель и решение методом динамического программирования.

Данная задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.

Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f_i(x_i) прирост мощности или прибыли на j-м предприятии, если оно получит x_i рублей капитальных вложений. Требуется найти такое распределение (x₁,x₂,..., x_n) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли z = f₁(x₁) + f₂(х₂) +... + f_n(x_n)

при ограничении по общей сумме капитальных вложений x₁ + x₂ +... + x_n = b

причем будем считать, что все переменные x_j принимают только целые неотрицательные значения

x_j = 0, или 1, или 2, или 3,...

Функции f_j(x_j) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача. Воспользуемся методом динамического программирования для решения этой задачи.

Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры.

Введем параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получают x рублей. Параметр x может изменяться от 0 до b. Если из x рублей k-е предприятие получит x_k рублей, то каково бы ни было это значение, остальные x - x_k рублей естественно распределить между предприятиями от первого до (k-1)-го так, чтобы была получена максимальная прибыль F_k-1(x - x_k). Тогда прибыль k предприятий будет равна f_k(x_k) + F_k-1(x - x_k). Надо выбрать такое значение x_k между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению F_k(x)=max{ f _k(x _k) + F_k-1(x- x _k)}

0 £ x _k £ x

для k = 2, 3, 4,..., n. Если же k=1, то F₁(x) = f₁(x)

Рассмотрим пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций f_j(x_j) приведены в таблице 1, где, например, число 88 означает,

что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.

Таблица I

Прежде всего, заполняем табл. 2. Значения f₂(x₂) складываем со значениями F₁(x - x₂) = f₁(x- x₂) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.

Продолжая процесс, табулируем функции F₃(x), (x) и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700. Наибольшее число на этой диагонали: Z_max = 155 тыс. руб.,

причем четвертому предприятию должно быть выделено х^*₄ = ₄ (700) = 300 тыс. руб.

На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено x^*₃ = ₃ (700-x^*₄) = ₃ (400) = 200 тыс. руб.

Продолжая обратный процесс, находим x*₂ = ₂ (700 - x*₄ - x*₃) = ₂ (200) = 100 тыс. руб.

На долю первого предприятия остается x*₁ = 700 - x*₄ - x*₃ - x*₂ = 100 тыс. руб.

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям: x*₁ =100; x*₂ =100; x*₃ = 200; x*₄ = 300.

Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 155 тыс. руб.

Студенту рекомендуется проверить выполнение равенства f₁(x*₁) + f₂(x*₂) + f₃(x*₃) + f₄(x*₄) = z _max

 

Таблица 2

	x - x2	0 100 200 300 400 500 600 700
x2	F1(x - x2) f2(x2)	0 20 34 46 53 55 60 60
		0 20* 34 46 53 55 60 60
		18 38* 52* 64 71 73 78
		29 49 63 75 82 84
		45 65* 79 91 98
		62 82* 96 108
		78 98* 112*
		90 110
		98.

Таблица 3

x	0 100 200 300 400 500 600 700
F2(x)	0 20 38 52 65 82 98 112
` (x)	0 0 100 100 300 400 500 500

Таблица 4

	x - x3	0 100 200 300 400 500 600 700
x3	F2(x - x3) f3(x3)	0 20 38 52 65 82 98 112
0		0 20 38 52 65 82 98 112
		25* 45* 63* 77 90 107 123
		41 61 79* 93 106 123
		52 72 94* 112 126
		74 94* 112* 126*
		82 102 120
		88 106
		90.

Таблица 5

x	0 100 200 300 400 500 600 700
F3(x)	0 25 45 63 79 94 112 126
(x)	0 100 100 100 200 400 400 400

Таблица 6

	x - x4	0 100 200 300 400 500 600 700
x4	F3(x - x4) f4(x4)	0 25 45 63 79 94 112 126
		155*
		125.

33. Матричная игра как модель конфликтной ситуации. Матричная игра двух лиц с нулевой суммой. Нижняя и верхняя цена игры, седловая точка. Чистые и смешанные стратегии игроков.

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

Такие ситуации называются конфликтными. Например: борьба фирм за рынок сбыта, аукцион, спортивные состязания, карточная игра.

Рассмотрим конфликт двух участников с противоположными интересами. Математической моделью такого конфликта является игра с нулевой суммой. Участники это – игроки.

Стратегия игрока – это осознанный выбор одного из множества возможных вариантов его действий.

Рассмотрим конечные игры, в кот. множества стратегий игроков конечны; стратегии первого игрока пронумеруем от 1 до m, а стратегии второго игрока – от 1 до n.

Если первый игрок выбрал свою i-ю стратегию, а второй игрок свою j-ю стратегию, то результатом такого совместного выбора будет платеж a_ij второго игрока первому. Таким образом, игра с нулевой суммой однозначно определяется платежной матрицей.

а₁₁ а₂₁ а_1n

П= а₂₁ а₂₂ а_2n

 

а_m1 а_m2 а_mn

 

Строки - соответствуют стратегиям первого игрока, столбцы -второго игрока. Игра происходит партиями.

Если выбор игрока не меняется от партии к партии – это чистая стратегия. У 1-го игрока m чистых стратегий, у 2-го n.

При любой стратегии первого игрока, второй игрок будет выбирать стратегию обеспечивающий ему наибольший выигрыш, поэтому с точки зрения первого игрока надо выбирать такую стратегию, при которой второй игрок, действуя разумно заплатит наибольшую сумму. Такая стратегия первого игрока называется максиминной, а величина = max min a_ij называется нижней ценой игры.

i j

Т.е. первый игрок, применяя свою максиминную стратегию обеспечивает себе выигрыш не меньше . Аналогично (с точки зрения второго игрока) определяется верхняя цена игры =min max a _ij

j i и соответствующая ей минимаксная стратегия второго игрока. То есть, принимая свою минимаксную стратегию второй игрок проиграет не больше .

Всегда . Если , то игра имеет седловую точку. При этом цена игры: = , а стратегия игроков соответствующие седловой точке называются оптимальными чистыми стратегиями (наиболее выгодные для обеих игроков)

 

34. Ряд распределения выигрышей в матричной игре. Средний ожидаемый выигрыш и риск. Оптимальные стратегии игроков и цена игры.

Смешанной стратегий первого игрока называется вектор P (p_1, p_2,…p_m), где все p_{i 0} (i=1,2,…,m), а p =1. при этом p - вероятность, с которой первый игрок выбирает вою i-ю стратегию. Аналогично определяются смешанные стратегии и Q (q₁, q₂,…q_n)второго игрока. Чистая стратегия также попадает под определение смешанной – если все вероятности равны нулю, кроме одной, равной единице.

Пусть игроки – Первый и Второй, играют в матричную игру с матрицей . Пусть стратегия Первого есть , а Второго – . Тогда выигрыш Первого есть случайная величина (с.в.) с рядом распределения:

W(P,Q):	a11		…		aij		…		amn
	p1 q1		…		pi qj		…		pm qn

Если игроки применяют свои смешанные стратегии P (p_1, p_2,…p_m)и Q (q₁, q₂,…q_n) соответственно, Выигрыш первого: выигрыш a_ij

Вероятность p_i q_j.

То есть первый игрок с вероятностью p_i g_j. выигрывает a_ij.. Математическое ожидание выигрыша первого игрока равно М(P,Q)= p_i q_j a_ij есть средний выигрыш.