1. Основні поняття
1.1. Модель динамічного програмування
1.2. Принцип оптимальності. Рівняння Беллмана
2. Оптимальний розподіл ресурсів
2.1 Постановка задачі
2.2 Двовимірна модель розподілу ресурсів
2.3 Дискретна динамічна модель оптимального розподілу ресурсів
2.4 Облік післядії у завданнях оптимального розподілу ресурсів
Висновок
Список використаних джерел
Додаток 1. Лістинг програми для вирішення задачі оптимального розподілу ресурсів заданими параметрами. Результати роботи програми
Вступ
Протягом усієї своєї історії люди за необхідності приймати рішення вдавалися до складних ритуалів. Вони влаштовували урочисті церемонії, приносили в жертву тварин, ворожили по зірках та стежили за польотом птахів. Вони покладалися на народні прикмети і намагалися дотримуватись примітивних правил, що полегшують їм важке завдання прийняття рішень. В даний час для ухвалення рішення використовують новий і, мабуть, більш науковий «ритуал», що ґрунтується на застосуванні електронно-обчислювальної машини. Без сучасних технічних засобівлюдський розум, ймовірно, не може врахувати численні та різноманітні фактори, з якими стикаються при управлінні підприємством, конструюванні ракети чи регулюванні руху транспорту. Існуючі нині численні математичні методиоптимізації вже досить розвинені, що дозволяє ефективно використовувати можливості цифрових та гібридних. обчислювальних машин. Одним з цих методів є математичне програмування, що включає як окремий випадокдинамічне програмування.
Більшість практичних завданьмає кілька (а деякі, можливо, навіть нескінченне число) рішень. Метою оптимізації є знаходження найкращого рішеннясеред багатьох потенційно можливих відповідно до деякого критерію ефективності або якості. Завдання, яке допускає лише одне рішення, не потребує оптимізації. Оптимізація може бути здійснена за допомогою багатьох стратегій, починаючи з дуже складних аналітичних та чисельних математичних процедур та закінчуючи розумним застосуванням простої арифметики.
p align="justify"> Динамічне програмування - метод оптимізації, пристосований до операцій, в яких процес прийняття рішень може бути розбитий на окремі етапи (кроки). Такі операції називаються багатокроковими.
Як розділ математичного програмування, динамічне програмування (ДП) почало розвиватися у 50-х роках XX ст. завдяки роботам Р. Беллмана та його співробітників. Вперше цим методом вирішувалися завдання оптимального керування запасами, потім клас завдань значно розширився. Як практичний методОптимізації метод динамічного програмування став можливий лише при використанні сучасної обчислювальної техніки.
У основі методу динамічного програмування лежить принцип оптимальності, сформульований Беллманом. Цей принцип та ідея включення конкретного завданняоптимізації у сімейство аналогічних багатокрокових завдань призводять до рекурентних співвідношень - функціональних рівнянь - щодо оптимального значення цільової функції. Їхнє рішення дозволяє послідовно отримати оптимальне управління для вихідного завданняоптимізація.
1. Основні поняття
1.1 Модель динамічного програмування
Дамо Загальний описмоделі динамічного програмування
Розглядається керована система, яка під впливом управління переходить із початкового стану
у кінцевий стан. Припустимо, що процес управління системою можна розбити на пкроків. Нехай , ,…, - стану системи після першого, другого,..., п-го кроку. Схематично це показано на рис. 1.
Малюнок 1
Стан
системи після k-гокроку ( k = 1,2 …,n) характеризується параметрами , ,…, які називаються фазовими координатамиСтан можна зобразити точкою s-вимірного простору званого фазовим простором.Послідовне перетворення системи (по кроках) досягається за допомогою деяких заходів , , ..., які складають управління системою
, де - управління на k-м кроці, що переводить систему зі стану в стан (рис. 1) Управління на k-ом кроці полягає у виборі значень певних управляючих змінних. Припускаємо, що стан системи в кінці k-гокроку залежить лише від попереднього стану системи
та управління на даному кроці(Рис. 1). Така властивість отримала назву відсутності післядії.Позначимо цю залежність у вигляді
, (1.1)
Рівності (1.1) отримали назву рівнянь станів.Функції
вважаємо заданими.Варіюючи управління U , отримаємо різну «ефективність» процесу, яку оцінюватимемо кількісно цільовою функцією Z , залежить від початкового стану системи
та від обраного управління U : . (1.2)Показник ефективності k-гокроку процесу управління, який залежить від стану
на початку цього кроку та управління , обраного на цьому кроці, позначимо через розглянуту задачу покрокової оптимізації цільова функція (1.2) повинна бути адитивною, тобто.
. (1.3)
Якщо властивість адитивності цільової функції Z не виконується, цього іноді можна домогтися деякими перетвореннями функції. Наприклад, якщо Z-мультиплікативна функція, задана у вигляді
, можна розглянути функцію , яка є адитивною. Зазвичай умовами процесу управління на кожному кроці
накладаються деякі обмеження. Управління, які відповідають цим обмеженням називаються допустимими .Завдання покрокової оптимізації можна сформулювати так: визначити сукупність допустимих управлінні
Є певна кількість ресурсів s 0 , яку необхідно розподілити між n господарюючими суб'єктами на поточну діяльність протягом періоду, що розглядається (місяць, квартал, півріччя, рік тощо) з метою отримання сукупного максимального прибутку. Розміри вкладень ресурсів x i (;) у діяльність кожного суб'єкта господарювання кратні певній величині h. Відомо, що кожен суб'єкт господарювання залежно від обсягу використовуваних коштів x i за аналізований період приносить прибуток у розмірі f i (xi) (не залежить від вкладення ресурсів в інші суб'єкти господарювання).
Представимо процес розподілу ресурсів між суб'єктами господарювання як n-кроковий процес управління (номер кроку збігається з умовним номером господарюючого суб'єкта). Нехай s k () - Параметр стану, тобто. кількість вільних коштів після k-го кроку для розподілу між господарюючими суб'єктами, що залишилися (n - k). Тоді рівняння станів можна записати у такому вигляді:
Введемо на розгляд функцію - умовно оптимальний сукупний прибуток, отриманий від k-го, (k+1) - го, …, n-го суб'єктів господарювання, якщо між ними оптимальним чином розподілялися ресурси в обсязі s k-1 (). Безліч можливих управлінських рішеньщодо обсягу розподілених ресурсів на k-ом кроці можна наступним образом: .
Тоді рекурентні рівняння Р.Е. Беллмана (зворотна схема) матимуть вигляд:
приклад.Є певна кількість ресурсів s 0 =100, яку необхідно розподілити між n=4 суб'єктами господарювання на поточну діяльність протягом аналізованого періоду (місяць) з метою отримання сукупного максимального прибутку. Розміри вкладень ресурсів x i (;) у діяльність кожного суб'єкта господарювання кратні величині h = 20 і задані вектором Q. Відомо, що кожен суб'єкт господарювання залежно від обсягу використовуваних коштів x i за аналізований період приносить прибуток у розмірі f i (xi) () (не залежить від вкладення ресурсів в інші суб'єкти господарювання):
Необхідно визначити, який обсяг ресурсів потрібно виділити кожному підприємству, щоб сумарний прибуток був найбільшим.
Рішення.Складемо рекурентні рівняння Беллмана (зворотну схему):
Визначимо умовні максимуми відповідно до (13), результати розрахунків представлені у таблиці 1.
Таблиця 1. Розрахунок умовних оптимумів
|
22+20=42 |
|||||||||||
|
22+33=55 |
17+42=59 |
||||||||||
|
22+46=68 |
17+55=72 |
14+59=73 |
|||||||||
|
67+20=87 |
|||||||||||
За результатами умовної оптимізації визначимо оптимальне розподілення ресурсів:
Таким чином, оптимальний розподіл ресурсів:
яке забезпечить найбільший прибуток у розмірі 87 ум. ден. од.
Відповідь:раціональний розподіл ресурсів: , що забезпечує максимальний прибуток в 87 ум. ден. од.
Висновок
p align="justify"> Динамічне програмування - це область математичного програмування, що включає сукупність прийомів і засобів для знаходження оптимального рішення, а також оптимізації кожного кроку в системі та виробленні стратегії управління, тобто процес управління можна уявити, як багатокроковий процес. p align="justify"> Динамічне програмування, використовуючи поетапне планування, дозволяє не тільки спростити вирішення завдання, але і вирішити ті з них, яким не можна застосувати методи математичного аналізу. Спрощення рішення досягається за рахунок значного зменшення кількості досліджуваних варіантів, тому що замість того, щоб один раз вирішувати складне багатоваріантне завдання, метод поетапного планування передбачає багаторазове рішення щодо простих завдань. Плануючи поетапний процес, з інтересів всього процесу загалом, тобто. При ухваленні рішення на окремому етапі завжди необхідно мати на увазі кінцеву мету. Проте динамічне програмування має свої недоліки. На відміну від лінійного програмування, в котрому симплексний методє універсальним, у динамічному програмуванні такого методу немає. Кожне завдання має свої труднощі, і в кожному випадку необхідно знайти найбільш підходящу методику розв'язання. Нестача динамічного програмування полягає також у трудомісткості вирішення багатовимірних завдань. Завдання динамічного програмування має задовольняти дві умови. Першу умову зазвичай називають умовою відсутності післядії, а друге – умовою адитивності цільової функції завдання. Насправді зустрічаються такі завдання планування, у яких помітну роль грають випадкові чинники, що впливають як стан системи, і на выигрыш. Існує різниця між детермінованою та стохастичною задачами динамічного програмування. У детермінованій задачі оптимальне управління є єдиним і вказується заздалегідь як жорстка програмадій. У стохастичній задачі оптимальне управління є випадковим і вибирається в ході самого процесу в залежності від ситуації, що склалася. У детермінованій схемі, проходячи процес по етапах від кінця до початку, теж знаходиться на кожному етапі цілий ряд умовних оптимальних управлінь, але з усіх цих управлінь, зрештою здійснювалося лише одне. У стохастичній схемі це негаразд. Кожне з умовних оптимальних управлінь може бути фактично здійсненим, якщо попередній перебіг випадкового процесу приведе систему у відповідний стан. Принцип оптимальності є основою поетапного розв'язання задач динамічного програмування. Типовими представниками економічних завданьдинамічного програмування є звані завдання виробництва та зберігання, завдання розподілу капіталовкладень, завдання календарного виробничого планування та інші. Завдання динамічного програмування застосовують у плануванні діяльності підприємства з урахуванням зміни потреби у продукції у часі. В оптимальному розподілі ресурсів між підприємствами у напрямі чи часі. Опис характеристик динамічного програмування та типів завдань, які можуть бути сформульовані в його рамках, за потребою має бути дуже загальним та дещо невизначеним, оскільки існує неосяжна безліч різних завдань, що укладаються у схему динамічного програмування. Тільки вивчення великої кількостіприкладів дає чітке розуміння структури динамічного програмування.
Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче
Студенти, аспіранти, молоді вчені, які використовують базу знань у своєму навчанні та роботі, будуть вам дуже вдячні.
Розміщено на http://www.allbest.ru/
Завдання розподілу ресурсів методом динамічного програмування
Для розширення виробничих потужностей трьох підприємств А, В і С виділяється кілька одиниць додаткової електроенергії в обсязі х 0 =8 одиниць. Електроенергія може виділятися у вигляді 1, 2, 3, 4, 5, 6, 7 та 8 одиниць. Вкладаючи у розвиток i-того підприємства х i одиниць електроенергії можна отримати дохід у i одиниць на підприємстві. Існують різні варіантих i (к) виділення додаткової електроенергії. Вони приносять дохід у i (к), =1,n. Можливі варіантирозвитку підприємств наведено у табл.1. Сумарний дохід у всіх підприємствах може бути максимальним, тобто у=? у i(к)>max
Табл. 1. Варіанти розвитку підприємств
|
Варіант до |
Підприємство А |
Підприємство В |
Підприємство С |
||||
Математична постановка завдання:
у=? у i (к)> max
х i (к)?х 0
Рішення:
Почнемо розгляд процедури вирішення поставленого завдання з останнього (3 кроки) етапу (Табл.2), на якому інвестиції виділяються підприємству С. Умовно-оптимальне управління на третьому етапі шукається як рішення рівняння
g C (S 2) = max k f c , x C (k)? S 2 k = 1,2,3,4
Табл. 2. Умовно-оптимальні рішення (крок 3)
|
Стан |
Управління |
|||||||
Є чотири можливості вкладення коштів - чотири крокових управління х З (1) = 0од., Х (2) = 1од., Х (3) = 2од., Х (4) = 3од. і дев'ять теоретично можливих станів системи S 2 , що передують виділенню коштів підприємству С - обсяги не розподілених до 3-го етапу інвестицій: 0,1,2,3,4,5,6,7,8.
Припустимо, що система знаходилася в стані S 2 = 2. Тоді, для крокового управління х С (2) = 1 дохід у С (2) дорівнюватиме 3од. (Табл.3), а крокове керування х З (3)=2 буде оптимальним для цього стану, що дає умовно-максимальний виграш g c (S 2)=5. Якщо система перебувала в стані S 2 =3, то допустимі всі крокові управління х З (1) = 0од., Х (2) = 1од., Х (3) = 2од., Х (4) = 3од. , а оптимальним буде керування х З (4)=3, яке забезпечує умовно максимальний виграш g c (S 2)=6.
Табл.3 динамічний програмування розподіл інвестицій
Аналогічно заповнюються усі можливі станипопередні 3-го етапу. Оптимальні значенняпоказників виділено у таблицях жирним шрифтом.
Далі так само розглядається другий етап (Табл.4), що у виділенні інвестицій підприємству А. На другому етапі загальний виграш складається з виграшів, одержуваних третьому і другому етапах, і задається співвідношенням:
g А (S 1) = max k f А + g c], x А (k)? S 1, k = 1,2,3,4
Так, для стану S 1 =3 з кроковим керуванням A (2)=1 отримуємо:
g А (S 1) = max k f А + g c]
Max k 4+g c =4+5=9 де знаходимо з таблиці 1, а g c з таблиці 3. Аналогічно заповнюються всі стани.
Табл. 4. Умовно-оптимальні рішення (крок 2)
|
Стан |
f А +g c |
Управління |
||||||
Тут виникають ситуації, при яких оптимальне рішення буде не єдиним. 1) = 9
Табл. 5. Безумовно-оптимальні рішення (крок 1)
У першому етапі (Табл.5)-выделение інвестицій підприємству У - є лише одне попереднє стан системи, відповідне початковому стану S 0 =8. Безумовно оптимальний виграш визначається виразом:
у * = g (S 0) = max k (f А + g А) x (k)? S 0 = x 0, k = 1,2,3,4,5
Безумовно-оптимальні управління, які забезпечують максимальний дохідможуть бути різними.
Схема знаходження всіх оптимальних варіантіврозподілу інвестицій між підприємствами (табл.6) представлена малюнку 1.
Табл. 6. Оптимальні розподіли інвестицій.
Рисунок 1. Схема оптимального розподілу інвестицій між підприємствами
Висновок: розглянувши завдання розподілу ресурсів шляхом динамічного програмування виявили два варіанти раціонального розподілу ресурсів.
Розміщено на Allbest.ru
...Подібні документи
Загальна характеристикаі економічні показникидіяльності трьох досліджуваних підприємств. Розв'язання задачі планування виробництва, а також розподілення інвестицій методом лінійного та динамічного програмування. Порівняльний аналізрезультатів.
курсова робота , доданий 25.04.2015
Багатокрокові процеси в динамічних завданнях. Принцип оптимальності та рекурентні співвідношення. Метод динамічного програмування. Завдання оптимального розподілу коштів на розширення виробництва та планування виробничої програми.
курсова робота , доданий 30.12.2010
Метод динамічного програмування та його основні етапи. Оптимальна стратегія заміни обладнання. Мінімізація витрат на будівництво та експлуатацію підприємств. Оптимальний розподіл ресурсів у ТОВ "БУДКРОВЛЯ" та інвестицій ПКТ "Хімволокно".
курсова робота , доданий 08.01.2015
Математична модель планування виробництва. Складання оптимального плану виробничої діяльностіпідприємства методом лінійного програмування. Знаходження оптимального способурозподілу грошових ресурсів протягом запланованого періоду.
дипломна робота , доданий 07.08.2013
Розрахунок вартості перевезень методом мінімальних витрат. Знаходження умовної оптимальної рівності у процесі динамічного програмування. Лінійне рівняння алгебри Колмогорова для середнього часу безвідмовної роботи резервованої системи.
курсова робота , доданий 14.01.2011
Графічний методрозв'язання задачі оптимізації виробничих процесів. Застосування симплекс-алгоритму на вирішення економічної оптимізованої завдання управління виробництвом. Метод динамічного програмування для вибору оптимального профілю шляху.
контрольна робота , доданий 15.10.2010
Оптимальний план розподілу грошових коштівміж підприємствами Розробка плану для кожного підприємства, при якому прибуток від вкладених коштів прийме найбільше значення. Використання методів лінійного та динамічного програмування.
курсова робота , доданий 16.12.2013
Характерні риси задач лінійного програмування. Загальна постановка задачі планування виробництва. Побудова математичної моделірозподіл ресурсів фірми. Аналіз чутливості раціонального рішення. Складання звіту зі стійкості.
презентація , доданий 02.12.2014
Знаходження оптимального портфеля цінних паперів. Огляд методів розв'язання поставленого завдання. Побудова математичної моделі. Завдання конусного програмування. Залежність вектора розподілу початкового капіталу від однієї з початкових параметрів.
дипломна робота , доданий 11.02.2017
Модель динамічного програмування. Принцип оптимальності та рівняння Беллмана. Опис процесу моделювання та побудови обчислювальної схеми динамічного програмування. Завдання про мінімізацію витрат на будівництво та експлуатацію підприємств.
p align="justify"> Динамічне програмування (ДП) - це метод знаходження оптимальних рішень в задачах з багатокроковою (багатоетапною) структурою.
Наведемо загальну постановку задачі ДП. Розглядається керований процес (розподіл коштів між підприємствами, використання ресурсів протягом кількох років тощо). В результаті управління система (об'єкт управління) переводиться з початкового стану в стан 
. Припустимо, що управління можна розбити на 
кроків. На кожному кроці вибирається одне з безлічі допустимих управлінь 
, що переводить систему в один із станів безлічі 
. Елементи множини 
і 
визначаються за умов конкретного завдання. Послідовність станів системи можна зобразити як графа станів, представленого на рис. 3.1.
На кожному кроці nдосягається ефект 
. Припустимо, загальний ефект є сумою ефектів, досягнутих кожному кроці. Тоді завдання ДП формулюється так: визначити таке допустиме управління 
, що перекладає систему зі стану 
у стан 
, при якому функція мети 
набуває найбільшого (найменше) значення, тобто.
Розв'язання задач методом ДП здійснюється на основі принципу оптимальності, який був сформульований американським ученим Р.Беллманом: яким би не було стан системи в результаті якогось числа кроків, на найближчому кроці потрібно вибирати управління так, щоб воно в сукупності з оптимальним керуваннямна всіх наступних кроках призводило до оптимального виграшу на всіх кроках, що залишилися, включаючи даний.
Позначимо через 
умовно-оптимальне значення цільової функції на інтервалі від кроку nдо останнього 
-го кроку включно, за умови, що перед n-им кроком система знаходилася в одному зі станів множини 
, а на n-ом кроці було обрано таке управління з множини 
, що забезпечило цільову функцію умовно-оптимальне значення, тоді 
умовно-оптимальне значення цільової функції в інтервалі від ( n+1
)-го до 
-го кроку включно.
У прийнятих позначеннях принцип оптимальності Беллмана можна записати в математичній формі таким чином
Рівність (3.1) називається основним функціональним рівнянням динамічного програмування. Для кожної конкретної задачі рівняння має особливий вигляд.
Обчислювальна процедура методу ДП розпадається на два етапи: умовну та безумовну оптимізацію.
На етапі умовної оптимізаціївідповідно до функціонального рівняння визначаються оптимальні управління для всіх можливих станів на кожному кроці, починаючи з останнього.
На етапі безумовної оптимізаціїкроки розглядаються, починаючи з першого. Оскільки вихідний стан 
відомо, вибирається оптимальне управління з множини 
. Вибране оптимальне керування 
приводить систему у цілком певний стан 
. Завдяки тому, що вихідний стан 
на початку другого кроку відомо, стає можливим вибрати оптимальне керування на другому кроці 
і т.д. Таким чином, будується ланцюг взаємозалежних рішень безумовної оптимізації.
3.1. Завдання оптимального розподілу ресурсів
Нехай на реконструкцію та модернізацію основного виробництва об'єднанню виділяється певний обсяг матеріальних ресурсів Х. Є Nпідприємств, між якими потрібно розподілити даний ресурс. Позначимо через 
прибуток, якому приносить народному господарству виділення j-му підприємству 
одиниць ресурсу. Передбачається, що розмір прибутку залежить як від кількості ресурсу, і від підприємства. Причому прибуток, одержуваний підприємствами вимірюється в тих самих одиницях і загальний прибуток об'єднання складається з прибутків окремих підприємств. Необхідно знайти оптимальний планрозподіл ресурсів між підприємствами, при якому загальний прибуток об'єднання буде максимальним.
Поставлене завдання слід розглянути як багатокрокове.
На етапі умовної оптимізації будемо розглядати ефективність вкладення коштів на одному (наприклад, на першому підприємстві), на двох підприємствах разом (на першому та другому), на трьох підприємствах разом (на першому, другому та третьому) тощо, і нарешті , на всіх Nпідприємствах разом. Завдання полягає у визначенні найбільшого значення функції 
за умови, що 
.
Скористаємося рекурентним співвідношенням Беллмана (3.1), яке для даної задачі призводить до наступних функціональних рівнянь при 
:
Тут функція 
визначає максимальний прибутокпершого підприємства при виділенні йому xодиниць ресурсу, функція 
визначає максимальний прибуток першого та другого підприємств разом при виділенні ним xодиниць ресурсу, функція 
визначає максимальний прибуток першого, другого та третього підприємств разом при виділенні їм xодиниць ресурсу і т.д., і нарешті, функція 
визначає максимальний прибуток усіх підприємств разом при виділенні їм xодиниць ресурсу.
На етапі безперечної оптимізації визначається оптимальний план розподілу ресурсів між підприємствами.
Приклад 3.1.
Для збільшення обсягів випуску продукції, що користується підвищеним попитом, чотирьом підприємствам виробничого об'єднання виділені кошти в розмірі 50 млн. руб. Кожному підприємств може бути виділено: 0, 10, 20, 30, 40 чи 50 млн. крб. При цьому щорічний приріст випуску продукції кожним із підприємств 
залежно від капіталовкладень відомий та наведений у табл. 3.1.
Таблиця 3.1
|
Обсяг виділених коштів x(млн. руб.) |
Щорічний приріст випуску продукції (млн. руб.), Залежно від обсягу виділених коштів |
|||
|
|
|
|
|
|
Знайти оптимальний план розподілу коштів між підприємствами, який би максимальний щорічний приріст випуску продукції виробничим об'єднанням.
Призначення сервісу. Цей сервіспризначений для вирішення завдання оптимального розподілу інвестиційв онлайн режимі. Результати обчислень оформлюються у звіті формату Word(Див. Приклад оформлення).Такі завдання засновані на функції Беллмана і під час вирішення використовується метод зворотної прогонки (див. Типові завдання). Також можна скористатися сервісом Процедура прямого прогону.
Інструкція. Виберіть кількість підприємств та кількість рядків (кількість варіантів ефективного вкладення), натисніть Далі (див. Приклад заповнення). Якщо дохід та залишки підприємств задані у вигляді функцій f(x) і g(x), завдання вирішується через цей калькулятор.
Приклад №1. Визначте оптимальний план розширення виробництва трьох підприємств, якщо відомий їх прибуток у рік за відсутності вкладень та за інвестування 1, 2, 3 або 4 млн. Визначте, за якого інвестування буде максимальний відсоток приросту прибутку.
| f1 | f2 | f3 | x i |
| 40 | 30 | 35 | 0 |
| 90 | 110 | 95 | 1 |
| 395 | 385 | 270 | 2 |
| 440 | 470 | 630 | 3 |
| 620 | 740 | 700 | 4 |
І етап. Умовна оптимізація.
Перший крок. k = 3.
| e 2 | u 3 | e 3 = e 2 - u 3 | f 3 (u 3) | F* 3 (e 3) | u 3 (e 3) |
| 1 | 0 | 1 | 35 | ||
| 1 | 0 | 95 | 95 | 1 | |
| 2 | 0 | 2 | 35 | ||
| 1 | 1 | 95 | |||
| 2 | 0 | 270 | 270 | 2 | |
| 3 | 0 | 3 | 35 | ||
| 1 | 2 | 95 | |||
| 2 | 1 | 270 | |||
| 3 | 0 | 630 | 630 | 3 | |
| 4 | 0 | 4 | 35 | ||
| 1 | 3 | 95 | |||
| 2 | 2 | 270 | |||
| 3 | 1 | 630 | |||
| 4 | 0 | 700 | 700 | 4 |
Другий крок. k = 2.
| e 1 | u 2 | e 2 = e 1 - u 2 | f 2 (u 2) | F* 2 (e 1) | F 1 (u 2 ,e 1) | F* 2 (e 2) | u 2 (e 2) |
| 1 | 0 | 1 | 30 | 95 | 125 | 125 | 0 |
| 1 | 0 | 110 | 0 | 110 | |||
| 2 | 0 | 2 | 30 | 270 | 300 | ||
| 1 | 1 | 110 | 95 | 205 | |||
| 2 | 0 | 385 | 0 | 385 | 385 | 2 | |
| 3 | 0 | 3 | 30 | 630 | 660 | 660 | 0 |
| 1 | 2 | 110 | 270 | 380 | |||
| 2 | 1 | 385 | 95 | 480 | |||
| 3 | 0 | 470 | 0 | 470 | |||
| 4 | 0 | 4 | 30 | 700 | 730 | ||
| 1 | 3 | 110 | 630 | 740 | 740 | 1 | |
| 2 | 2 | 385 | 270 | 655 | |||
| 3 | 1 | 470 | 95 | 565 | |||
| 4 | 0 | 740 | 0 | 740 |
Третій крок. k = 1.
| e 0 | u 1 | e 1 = e 0 - u 1 | f 1 (u 1) | F* 1 (e 0) | F 0 (u 1 ,e 0) | F* 1 (e 1) | u 1 (e 1) |
| 1 | 0 | 1 | 40 | 125 | 165 | 165 | 0 |
| 1 | 0 | 90 | 0 | 90 | |||
| 2 | 0 | 2 | 40 | 385 | 425 | 425 | 0 |
| 1 | 1 | 90 | 125 | 215 | |||
| 2 | 0 | 395 | 0 | 395 | |||
| 3 | 0 | 3 | 40 | 660 | 700 | 700 | 0 |
| 1 | 2 | 90 | 385 | 475 | |||
| 2 | 1 | 395 | 125 | 520 | |||
| 3 | 0 | 440 | 0 | 440 | |||
| 4 | 0 | 4 | 40 | 740 | 780 | 780 | 0 |
| 1 | 3 | 90 | 660 | 750 | |||
| 2 | 2 | 395 | 385 | 780 | |||
| 3 | 1 | 440 | 125 | 565 | |||
| 4 | 0 | 620 | 0 | 620 |
Примітка: Стовпці 1 (вкладені кошти), 2 (проект) та 3 (залишок коштів) для всіх трьох таблиць однакові, тому їх можна було б зробити загальними. Стовпець 4 заповнюється на основі вихідних даних про функції доходу, значення в стовпці 5 беруться зі стовпця 7 попередньої таблиці, стовпець 6 заповнюється сумою значень стовпців 4 і 5 (у таблиці 3 кроку стовпці 5 і 6 відсутні).
У стовпці 7 записується максимальне значенняпопереднього стовпця для фіксованого початкового стану, і в 8 стовпці записується управління з 2 стовпця, на якому досягається максимум 7.
Етап ІІ. Безумовна оптимізація.
З таблиці 3-го кроку маємо F * 1 (e 0 = 4 млн. руб.) = 780 тис. руб., тобто максимальний прибуток від інвестування e 0 = 4 млн. руб. дорівнює 780 тис. руб.
З тієї ж таблиці отримуємо, першому підприємству слід виділити u* 1 (e 0 = 4 млн.руб.) = 0 млн.руб.
У цьому залишок коштів становитиме: e 1 = e 0 - u 1 , e 1 = 4 - 0 = 4 млн.руб.
З таблиці 2-го кроку маємо F* 2 (e 1 = 4 млн.руб.) = 740 тыс.руб., тобто. максимальна прибуток за e 1 = 4 млн.руб. дорівнює 740 тис. руб.
З цієї таблиці отримуємо, що другому підприємству слід виділити u * 2 (e 1 = 4 млн. руб.) = 1 млн. руб.
У цьому залишок коштів становитиме: e 2 = e 1 - u 2 , e 2 = 4 - 1 = 3 млн.руб.
Останньому підприємству дістається 3 млн. руб. Отже, інвестиції у вигляді 4 млн.руб. необхідно розподілити так: першому підприємству нічого не виділяти, другому підприємству виділити 1 млн.руб., третьому підприємству виділити 3 млн.руб., що забезпечить максимальну прибуток, рівну 780 тис.руб.
Приклад №2. Є 4 підприємства, між якими необхідно розподілити 100 тис. ум. од. коштів. Значення приросту випуску продукції для підприємства залежно від виділених коштів Х представлені таблиці. Скласти оптимальний план розподілу коштів, що дозволяє максимізувати загальний приріст випуску продукції.
