Динамічне програмування. Дослідження операцій

М Е Т О Д И Ч Н I В К А З I В К И

до вивчення тем

"Динамічне програмування", "Теорія ігор",

"Системи масового обслуговування"

курсу "Дослідження операцій"

 

студентами спецiальностi

"Економічна кібернетика"

 

Кафедра: Моделювання i оптимiзацiї економiчних систем та процесiв

 

Тернопiль — 2003

 

Методичнi вказiвки до вивчення тем "Динамічне програмування", "Теорія ігор", "Системи масового обслуговування" курсу "Дослідження операцій" студентами спецiальностi "Економічна кібернетика" / Укл. Пасічник Р.М.- Тернопіль: ТАНГ, 2000 -__с.

Укладач: Пасічник Р.М., к.ф.-м.н., доцент,

 

Відповідальний за випуск Гладій Г.М., к.е.н., зав. кафедри МОЕСП

 

Рецензенти:

Карпінський М.П., д.т.н., професор,

Маслияк Б.О., к.т.н., доцент

 

Задача розподілу коштів

Нехай існує n стратегій розвитку підприємства. Кожна стратегія вимагає вкладення коштів x_j, при прогнозованому прибутку F_j.

Знайти оптимальний розподіл коштів С по відповідних стратегіях, який забезпечував би максимальний прибуток.

Таблиця 3.1Прогнозовані прибутки реалізації проектів

Проект
x1	F1	x2	F2	x3	F3
Варіант
					-	-
	-	-			-	-

 

Коштів можна вкласти не більше с=5.

Математичну постановку задачі можна записати наступним чином

(3.11)

(3.12)

(3.13)

x_j – сума коштів по кожному проекту

D_j – множина варіантів розподілу коштів по j-му проекту.

Для розв'язання задачі використаємо метод динамічного програмування. Штучно введемо багатокроковий процес, вважаючи, що на кожному етапі виділяються кошти одному із підприємств. Стан системи S_j на j-му етапі описуємо загальною сумою коштів, розподілених після цього етапу, а управління – сумою коштів х_j, виділених для відповідного підприємства. При прийнятті рішення на j-му кроці отримується виграш

(3.14)

При цьому система переходить в стан S_j

(3.15)

Основне функціональне рівняння динамічного програмування визначатиме умовно-оптимальний виграш наступним чином:

(3.16)

Умовно-оптимальний виграш останнього етапу матиме простіший вигляд:

(3.17)

Наступні обчислення для побудови оптимального розподілу коштів зручно оформити у вигляді таблиць. Обчислення починаємо з останнього етапу, знаходячи на основі відповідних значень х₃ а також таблиці (3.1). Для кожного стану S₂ розглядаємо всеможливі розподіли коштів на другому етапі та їх відповідні виграші

m=3

S3	х3	S2	W3

 

m=2

S2	х2	S1	W3+F2 =W2
			0+0=0
			0+8=8
			0+9=9
		1 *	0+12=12
			3+0=3
		2 V	3+8=11
		1 *	3+9=12
			3+12=15

 

Щоб знайти умовно-оптимальні виграші другого етапу порівнюємо значення W₂, які відповідають однаковим станам S₁. Ту стрічку якій відповідає максимальне значення умовно-оптимального прибутку позначаємо міткою “V”, якщо таких стрічон є декілька, то їх позначаємо міткою “*”. Для першого етапу аналізуємо лише такі управління, які приводять до початкового стану S₀ = 0.

S1	х1	S0	W2+F1=W1
		0 *	11+6=17 max прибуток
		0 *	12+5=17 max прибуток
			15+0=15

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

Ланцюжки оптимальних управлінь знаходимо в ході перегляду побудованих таблиць в порядку зростання номерів етапів. Формувати ланцюжки починаємо з оптимальних управлінь першого етапу, які помічені *, або V. (для даної задачі починаємо формувати одразу два ланцюжки). У відповідні таблички заносимо управління та прибутки першого етапу. Для відповідних кінцевих станів першого етапу в попередній табличці вибираємо помічені управління. Якщо ці управління помічені *, то утворюєм відповідну кількість нових ланцюжків з ідентичними управліннями на попередніх етапах.

Так в даній задачі утворився третій ланцюжок оптимального управління. Кожен із наведених управлінь (розподілів коштів) забезпечує сумарний прибуток 17.

 

 

X	F		X	F

 

X	F

 

Метод дає економію в переборі варіантів коли перехід до більшості станів здійснюється за допомогою декількох управлінь. Тобто оптимізація за формулою (3.16) приводить до суттєвого зменшення аналізованих варіантів управлінь, оскільки із багатьох варіантів залишається один або декілька. Це трапляється коли множини варіантів розподілу співпадають для всіх проектів, а їх значення утворені з постійним кроком. Коли в кожний стан веде один шлях, метод зводиться до повного перебору при виконанні обмеження на суму коштів. В таких випадках доцільніше використовувати рекурсивний алгоритм (алгоритм з поверненням).

 

Рекурсивні алгоритми

Формується початковий розподіл коштів одразу по всіх етапах, який потім прагнуть покращити, причому завідомо неоптимальні варіанти виключаються.

Початковий план будується за принципом максимального включення: початковим етапам кошти виділяються по максимуму. Якщо при цьому останньому з етапів виділено максимальну кількість коштів, то початковий план – оптимальний.

Далі, починаючи з останнього етапу (m), іде поступовий перерозподіл коштів за рахунок попереднього (m-1). З попереднього знімається така кількість коштів, щоби прибуток на останньому етапі збільшувався. Коли кошти попереднього етапу вичерпуються переходять до більш раннього (m-2). При виділенні коштів з етапу m-2 для етапу m-1 кошти знову виділяються за принципом максимального включення. Після цього наступні модифікації починаються із відбирання коштів знову з етапу m-1. При побудові кожного нового варіанту його прибуток порівнюється із найкращим з попередньо досягнутих. При ручних обчисленнях зручно помічати (*) варіанти, які не є оптимальними. Якщо в даному варіанті отримано кращий виграш, то вже він помічається як поточний оптимальний варіант.

Алгоритм завершується при неможливості побудови нових варіантів. Варіанти, які на той момент були поточно-оптимальними будуть визначати оптимальні управління даного процесу. Даний алгоритм легко програмується з використанням рекурсивних процедур.

Приклад: В умовах попередньої задачі отримаємо наступну послідовність варіантів розподілу, яка приведе до тих же оптимальних розподілів, які отримуються методом динамічного програмування.

 

етапи	Сi	Fi	Сi	Fi	Сi
	5*	15*

 

етапи	Fi	Сi	Fi	Сi	Fi
				5*	15*

 

 

Теорія ігор

 

 

В багатьох сферах людської діяльності часто зустрічаються проблема прийняття управлінських рішень в умовах невизначеності. Ситуації, в яких ефективність рішення, що приймається однією стороною, залежать від дій іншої сторони, називаються конфліктними. Конфліктна ситуація буде антагоністичною, якщо збільшення виграшу однієї із сторін на деяку величину приведе до зменшення виграшу іншої сторони на таку ж величину.

Гра є математичною моделлю реальної конфліктної ситуації, аналіз якої ведеться згідно відповідних правил. В загальному випадку правила визначають послідовність ходів, обсяг інформації кожної сторони про поведінку іншої та результат гри.

Якщо в грі беруть участь дві сторони, вона називається парною, а якщо більше – то множинною. Учасники множинної гри можуть утворювати коаліції. Множинна гра перетворюється в парну, коли її учасники утворюють дві постійні коаліції. Сторони, що беруть участь у грі (конфлікті) називаються гравцями. Стратегією гравця є сукупність правил, які визначають вибір варіанту дій при кожному особистому ході гравця в залежності від ситуації, що склалася в грі. В простій одноходовій грі поняття стратегії та вибору ходу гравця співпадають.

Гра називається скінченною, якщо число стратегій гравців скінченне і нескінченно, якщо хоча б у одного з гравців число стратегій нескінченне. Стратегія гравця називається оптимальною якщо вона забезпечує даному гравцю при багаторазовому повторенні гри максимально можливий середній виграш або мінімально можливий середній програш, незалежно від поведінки суперника.

Вибір однієї з передбачених правилами гри стратегій та її здійснення називають ходом. Ходи бувають особисті та випадкові. В особистому ході гравець свідомо вибирає один із можливих варіантів дій та здійснює його. При випадковому ході вибір відбувається не гравцем а механізмом випадкового вибору.

Використовують два способи описання ігор: позиційний та нормальний. Позиційний спосіб пов’язаний зводиться до графа послідовних кроків (дереву гри). Нормальний спосіб полягає представленні стратегій гравців та платіжної функції, яка визначає для кожної сукупності стратегій, що вибрані гравцями, виграш кожної із сторін. Якщо в партії виграш одного з гравців рівний програшу інших, то таку гру прийнято називати грою з нульовою сумою.

Для опису парної гри з нульовою сумою використовують платіжну матрицю, елементи якої визначають суму виграшу першого гравця та програшу другого гравця при виборі ними відповідних стратегій.

Приклад 1.Побудова платіжної матриці. Розглянемо парну скінченну парну гру з нульвою сумою. Кожен з гравців може записати одну із цифр {1,2,3}. Якщо різниця між очками додатня, то перший гравець виграє різницю, якщо від’ємна, то другий гравець виграє різницю. При рівності очок – нічия. Нижче наведено матрицю описаної гри

 

	B1=1	B2=2	B3=3
A1=1		-1	-2
A2=2			-1
A3=3

 

 

Гра 2Х2 без сідлових точок

 

Нехай гравець А має m а гравець В – n стратегій. Враховуючи, що при відсутності сідлових точок нижня та верхня ціни гри не співпадають (), природнім є бажання гравця А збільшити свій виграш а гравця В – зменшити програш. Пошук компромісу приводить до використання складної стратегії, яка називається мішаною. Мішані стратегії гравців будемо позначати відповідно та , де p_i, q_j – імовірності використання чистих стратегій А_і та В_j., причому

(4.7)

Стратегії гравців для яких імовірності використання в оптимальних мішаних стратегіях більші нуля, називаються активними.

В основній теоремі теорії ігор доводиться, що всяка скінченна парна гра з нульовою сумою має хоча б один розв’язок в мішаних стратегіях. В найпростіших випадках цей розв’язок нескладно знайти аналітично з використанням простого графічного аналізу. Розглянемо найпростіший випадок – гру 2х2 без сідлової точки. Оскільки сідлової точки не існує, то всі стратегії гравців будуть активними. При використанні оптимальної мішаної стратегії гравцем А ціна результат гри буде рівний її ціні при виборі довільної стратегії гравцем В:

(4.8)

(4.9)

Крім того слід врахувати, що

(4.10)

покладаючи отримуємо

(4.11)

(4.12)

(4.13)

Прирівнюючи (4.11) та (4.12), отримаємо рівняння відносно р₁:

 

(4.14)

яке при конкретних значеннях коефіцієнтів платіжної матриці розв'язується елементарно.

До рівняння (4.14) можна прийти також шляхом простого геометричного аналізу (див.рисунок). Для цього через кінці одиничного відрізка осі абсцис проведемо перпендикуляри, на яких будемо відкладати виграш гравця А при використанні чистих стратегій. Нехай лівому відрізку відповідає стратегія А₁, а правому – А₂. Відповідно на лівому перпендикулярі будуємо відрізки а₁₁ та а₁₂, а на правому – відрізки а₂₁ та а₂₂. Для побудови відрізка прямої, що відповідатиме результату гри при використанні другим гравцем стратегії В₁, проведемо аналіз співвідношень (4.11), (4.13). Рівняння (4.11) визначає пряму, аргументом якої служить p₁, а умова (4.13) зводить її до відрізка.

 

Побудуємо цей відрізок прямої за його крайніми точками. Зокрема в точці А₁ p₁=1 i . В точці А₂ р1=0 і . Оскільки пряма однозначно визначається двома точками, то сполучивши точки (0,а₁₁) і (1,а₂₁), отримаємо графік залежності результату гри при стратегії В₁ від імовірності р₁. Величина р₁ будується на відрізку [0,1] як віддаль поточної точки до точки А₂ (віддаль до одиниці). Аналогічно будується пряма для стратегії В₂, що сполучає точки (0,а₂₁) і (1,а₂₂).

Для знаходження оптимального значення побудуємо нижню границю виграшу гравця І, тобто ломану B₂NB₁. Із цієї нижньої межі виграшів гравець І прагне вибрати максимальне значення, якому відповідає точка N. Ордината цієї точки рівна ціні гри а абсциса дозволяє знайти параметри оптимальної мішаної стратегії гравця І:

(4.15)

Щоб знайти точне числове значення величини , потрібно розв'язати рівняння (4.14).

.

Оптимальна мішана стратегія гравця В знаходиться аналогічно. Однак відрізки, які будуть відкладатися на вертикалях В1 та В2 повинні відповідати вже результатам гри при цих стратегіях.Гравець В передбачає найбільш несприятливі для себе дії гравця A отримуючи верхню межу програшу – ламану A₁NA₂, ціну гри та параметри своєї оптимальної мішаної стратегії.

Слід відзначити, що розв'язок гри не завжди визначається точкою перетину ліній, що визначають результати гри для певних стратегій. На наступному малюнку показано, коли нижня границя виграшу гравця А співпадає з лінією В₂В₂.

Стратегія В₁ для гравця В явно невигідна, тому гравець А аналізує лише його стратегію В₂, вибираючи єдину оптимальну для себе стратегію А₂. Отже дана гра має сідлову точку А₂В₂.Наступний малюнок представляє також випадок наявності сідлової точки, хоча точка перетину оціночних прямих існує. Тут оптимальною є стратегії А₁В₂

Спрощення ігор

 

Якщо платіжна матриця гри не містить сідлової точки, то складність розв'язання задачі можна значно знизити, якщо зменшити розмірність платіжної матриці шляхом викреслювання дублюючих та заздалегідь невигідних стратегій.

Дублюючим стратегіям відповідають рівні стрічки (стовпчики) платіжної матриці. Якщо всі елементи i-ої стрічки (стовпчика) платіжної матриці не більші відповідних елементів стрічки (стовпчика) j, то стратегія А_і (В_j) називається заздалегідь невигідною.

М Е Т О Д И Ч Н I В К А З I В К И

до вивчення тем

"Динамічне програмування", "Теорія ігор",

"Системи масового обслуговування"

курсу "Дослідження операцій"

 

студентами спецiальностi

"Економічна кібернетика"

 

Кафедра: Моделювання i оптимiзацiї економiчних систем та процесiв

 

Тернопiль — 2003

 

Методичнi вказiвки до вивчення тем "Динамічне програмування", "Теорія ігор", "Системи масового обслуговування" курсу "Дослідження операцій" студентами спецiальностi "Економічна кібернетика" / Укл. Пасічник Р.М.- Тернопіль: ТАНГ, 2000 -__с.

Укладач: Пасічник Р.М., к.ф.-м.н., доцент,

 

Відповідальний за випуск Гладій Г.М., к.е.н., зав. кафедри МОЕСП

 

Рецензенти:

Карпінський М.П., д.т.н., професор,

Маслияк Б.О., к.т.н., доцент