Задачі динамічного програмування.

 

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

Однак, щоби прийняти рішення на останньому етапі (m) потрібно знати результат попереднього етапу (m-1). Оскільки його немає, то потрібно зробити різні допущення щодо стану S процесу управління після завершення попереднього кроку і при кожному із можливих станів вибрати оптимальне управління останнього етапу. Розв'язавши цю задачу, ми знайдемо умовно оптимальне управління на m-тому кроці, тобто управління, яке дозволить прийняти оптимальне рішення при будь-якому можливому стані системи на попередньому кроці.

Нехай умовно-оптимальне управління кроку m побудовано. Робимо всеможливі допущення про стан системи після (m-2) кроку і для кожного з них знаходимо таке управління на (m-1) кроці, щоби виграш за останні два кроки був максимальним. Таким чином знаходимо умовно-оптимальне управління для кроку (m-1). Продовжуємо процес, аж до побудови умовно-оптимального управління для першого кроку. Після цього ми можемо знайти оптимальне управління всього процесу.

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

Таким чином в процесі оптимізації управління методом динамічного програмування багатокроковий процес проходиться двічі:

- перший раз – від початку до кінця,в результаті чого знаходяться умовні оптимальні управління та виграші кожного етапу;

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

 

Принцип Беллмана та основне функціональне рівняння динамічного програмування.

 

В основу поетапної процедури побудови оптимального управління лежить принцип Беллмана:

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

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

Нехай ми вибираємо довільне управління на і-му кроці. При цьому ми отримуємо деякий виграш

(3.1)

який залежить як від стану системи, так і від вибраного управління. Крім того ми отримаємо деякий виграш на наступних кроках. Згідно принципу оптимальності будемо вважати, що він максимальний. Щоби знайти цей виграш ми повинні знати стан системи перед наступним і+1-им кроком. Цей новий стан буде залежати від стану системи S_i-1 та проведеного управління U_i

(3.2)

Виграш, який ми таким чином отримаємо на кроці і буде складати

(3.3)

Однак згідно принципу оптимальності ми повинні вибрати таке управління U_i, при якому величина виграшу на даному кроці буде максимальна

(3.4)

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

(3.5)

а рівняння (3.4) називається основним функціональним рівнянням динамічного програмування. Вона дозволяє встановити умовний оптимальний виграш на кроці і, коли цей виграш відомий для кроку і+1. Для останнього кроку потрібно просто максимізувати виграш при всіх допустимих станах системи перед останнім етапом:

(3.6)

Якщо в умові задачі задається область кінцевих станів S_e, то оптимізація проводиться не по всіх можливих управліннях , а лише по тих управліннях , які приводять систему в область S_e

(3.7)

Знаючи умовно оптимальне управління (3.6) на останньому кроці можемо за основним функціональним рівнянням динамічного програмування (3.4) знайти всі умовно-оптимальні виграші та умовно-оптимальні управління до першого кроку та . Оскільки дійсний початковий стан системи відомий, то можемо знайти оптимальний виграш при управлінні даною системою

(3.8)

а також побудувати ланцюжок,

(3.9)

який визначатиме це оптимальне управління:

(3.10)

 

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

Нехай існує 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