о
в) якщо, то стовпець розбивається на два стовпці:
і
У знайденому вирішенні поставки в цих стовпцях сумуються.
Метод динамічного програмування
Метод динамічного програмування полягає в тому, що оптимальне управління будується поступово, крок за кроком.
I. Завдання про оптимальний розподіл ресурсів полягає в тому, що підприємство має можливість виділити З ден.ед. n філіям (залежно від вкладеної суми філія дає приріст прибутку) з метою максимізації прибутку підприємства.
симплексний перетворення алгоритм базисний змінний
Алгоритм розв'язання задачі про оптимальний розподіл ресурсів
1. Складається таблиця, де вводять послідовність функцій - максимальний прибуток фірми, якщо х коштів виділити одночасно
В
Очевидно, що
В
2. Виконується В«зворотний хідВ»:
а) з визначення
В
б) кошти в обсязі x розподіляються між першим і другим філіями: другому в обсязі x2 ден.ед., тоді коштів виділяється першого філіалу. Загальний прибуток двох філій
В
в) включається до розгляд 3-й філія: із загальної суми х виділяється третій філії х3 ден.ед., тоді інша частина коштів оптимальним чином розподіляється між двома першими філіями; загальний прибуток
В
р) аналогічно знаходиться
і т.д.
3. Виконується В«прямий хідВ»:
знаходиться і оптимальне таке, що, після чого результати обчислень проглядаються в зворотному порядку. Знаючи, знаходять - обсяг фінансування решти n-1 філій, а отже, і та, й т.д. до знаходження та.
II. Нехай відомі: вік обладнання на початок планового періоду років, залишкова вартість обладнання s (t) ден.ед., ціна нового обладнання p ден.ед., вартість продукції, виробленої за 1 рік на обладнанні віку і витрати на обслуговування обладнання віку. Для розрахунку оптимальної стратегії підприємства з заміни обладнання вводять функцію - максимальний прибуток за останні i років планового періоду. Очевидно, що
В
Алгоритм розв'язання задачі про заміну обладнання
1. Визначити з умови задачі
,
і праворуч таблицю доповнити стовпцем.
. Заповнити рядок, переписавши з таблиці даних відповідні значення, а всі значення замінити
числом, т.ч.,
3. Починаючи з індексу i = 2, розрахунок по рядках проводиться відповідно з формулами
В В
тобто в наступній послідовності:
а) обчислити
В
де береться з вже заповненого рядка;
б) обчислити
В
Одержувані значення вносити у відповідні клітини рядка, але починаючи з першого, залишилися клітини заповнити значенням mi;
в) клітини з першим значенням в процесі заповнення таблиці відокремити від значень, розташованих у рядку лівіше, розділової кордоном зміни управління;
р) аналогічно продовжити заповнення таблиці до останнього рядка, тобто перейти до п. а) даного алгоритму.
. Дійшовши до останнього кроку (i = n), потрапляємо в початок планового періоду, починають прямий хід: задаючи t0 і тривалість планового періоду, знаходимо і будуємо послідовність оптимальних управлінь, починаючи з першого року і закінчуючи останнім. p> Зауваження: використовуючи отримані розрахункові таблиці для задачі про оптимальний розподіл капіталовкладень і про заміну обладнання, можна отримати рішення з зміною (зменшенням) вихідних даних (кількості філій, виділених коштів або планового періоду відповідно). Це так званий В«принцип зануренняВ» методу динамічного програмування. p> III. Нехай попит споживачів на продукцію становить на 1-й, 2-й, 3-й етапи d1, d2, d3 одиниць відповідно. На початок першого етапу на складі є y1 одиниці продукції. Витрати на зберігання одиниці продукції на різних етапах різні і складають відповідно h1, h2, h3. Витрати на виробництво хj одиниць на j-му етапі визначаються функцією,. Для знаходження оптимальної кількості виробленої на кожному етапі продукції, щоб заявки були задоволені, а загальні витрати на виробництво і зберігання за всі три етапи були найменшими, рішення проводять за алгоритмом. p> Алгоритм розв'язання задачі про виробництво та зберіганні продукції
1. Складається таблиця значень функції витрат на виробництво
, де
2. Виконується В«зворотний хідВ»: складаються функціональні рівняння
В
мінімальні витрати за перші k місяців, обмеження за величиною запасу до кінця k-го місяця
, балансове рівняння
,
а з нього отримують обмеження
В
а) для k = 1: складаються обмеження
,
а також таблиця значень функції
В
б) для k = 2: залежно від значень зміною
В ...
