1).
Якщо ж на початку (n-1)-го року вибрано управління заміна, то прибуток за два останні роки складе s (t) - p + r (0) - u (0) + z1 (1), отже,
z2 (t) = max
Аналогічно для i останніх років:
zi (t) = max
Дійшовши до останнього кроку (i = n), потрапляємо в початок п/п, де t відомо: t = t0, і, отже, можна почати прямий хід.
Задаючи t0 і тривалість п/п, знаходимо F * = zn (t0) і будуємо послідовність оптимальних управлінь, починаючи з першого року і закінчуючи останнім.
в) Розрахунок.
Для заповнення розрахункової таблиці можна використовувати наступний алгоритм.
. Визначити? (T) = r (t) - u (t), m1 = S (t) - p +? (0):
якщо m1 = const, то праворуч до таблиці додається додатковий стовпець mi;
якщо m1 = m1 (t), те над кожним рядком zi (t) вводиться додатковий рядок mi = mi (t) (або mi (t) вписується в клітини значень zi (t) як тарифи транспортної задачі).
. Заповнити рядок z1 (t), переписавши з таблиці даних відповідні значення? (T)? m1, всі значення? (t)
. Починаючи з індексу i = 2, розрахунок по рядках проводиться в такій послідовності:
а) обчислити mi = m1 + zi-1 (1), де zi-1 (1) береться з вже заповненого рядка;
б) обчислити zi (t) = z1 (t) + zi-1 (t +1), де сума і доданки утворюють трикутник, у якого одна з вершин завжди в першому рядку над шуканим значенням, а 2-а - в останній заповненої рядку наступного стовпця. Отримувані значення zi (t)? mi вносити у відповідні клітини рядка; починаючи з першого zi (t)
в) клітини з першим значенням zi (t)
г) якщо таблиця не заповнена до останнього рядка, перейти до п. а) і виконати розрахунок для наступного значення індексу i. p> Зауваження:
. Для задачі про оптимальний розподіл капіталовкладень за отриманою розрахунковій таблиці можна отримати стратегію вкладення коштів, наприклад, тільки в перші 3 філії, виключивши з розгляду 4-й, або, наприклад, для суми в 150 млн. руб. (А не 200) між 4-ма філіями, або тільки 3-ма першими і т.д.
Для задачі про заміну по розрахунковій таблиці можна отримати рішення на будь п/п тривалістю, що не перевищує вихідний.
Це так званий В«принцип зануренняВ» методу динамічного програмування.
2. Вирішену задачу про заміну обладнання можна ускладнити, наприклад, допускаючи заміну не новим обладнанням, а вже пропрацювали деякий час. При цьому мається три можливих управління: зберегти старе, купити нове, купити не нове. br/>
5. Завдання управління виробництвом і запасами
Підприємство виробляє партіями деякі вироби. Воно отримало замовлення на n місяців. Необхідно скласти план виробництва на зазначені n місяців з урахуванням витрат на виробництво і зберігання. Позначимо:
) xj - число виробів, що виробляються в j-му місяці;
) yj - величина запасу до початку j-го місяця (Це число не містить виробів, вироблених в j-й місяць, величина запасу на початок 1-го місяця (y1) і до кінця останнього (yn +1) задані) ;
) dj - число виробів, які повинні бути відвантажені в j-й місяць;
) - функція витрат на виробництво xj виробів у j-му місяці (може мати й інший вигляд);
) hj - витрати на зберігання одиниці запасу, що переходить з місяця j на місяць (j +1);
) - функція витрат на виробництво і зберігання в j-му місяці.
Завдання полягає у визначенні плану виробництва (х1, х2, ..., хn), компоненти якого задовольняють умовам матеріального балансу
xj + yj-dj = yj +1
і мінімізують сумарні витрати за весь період
.
За змістом,,. Зауважимо, що:
1) для будь-якого місяця j величина запасу до кінця місяця повинна задовольняти обмеженням
,
тобто обсяг виробленої продукції xj в j-му місяці може бути настільки великий, що запас yj +1 задовольняє попит на всіх наступних місяцях, але не має сенсу мати yj +1 більше сумарного попиту всіх наступних місяців;
) з балансового рівняння отримаємо.
Якщо врахувати, що xj і yj повинні бути цілими і невід'ємними, то маємо задачу цілочисельного нелінійного програмування.
Складемо функціональні рівняння. Нехай Fk (yk +1) - мінімальні витрати за перші k місяців. p> Для k = 1:
В
при й. На початковому етапі при фіксованому значенні y1 вихідного запасу кожному значенню y2 відповідає тільки одне значення x1. p> Для k 2:
при, і.
Застосувавши процедуру динамічного програмування, на останньому кроці k = n визначається значення xn * оптимального рішення, а інші компоненти визначаються в результаті прямого ходу за формулою
...
