Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
6.2. ДРОБОВО-ЛІНІЙНЕ ПРОГРАМУВАННЯ
6.2.1. Постановка задачі
та алгоритм розв’язування
Розв’язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:
за умов
,
.
Припускають, що знаменник цільової функції в області допустимих розв’язків системи обмежень не дорівнює нулю.
Алгоритм розв’язування задачі дробово-лінійного програмування передбачає зведення її до задачі лінійного програмування. Щоб виконати таке зведення, позначимо
,
зробимо заміну змінних
.
і запишемо економіко-математичну модель:
за умов
,
,
.
Дістали задачу лінійного програмування, яку можна розв’язати симплексним методом. Нехай оптимальний план
Оптимальні значення x0j знайдемо за формулою
.
6.2.2. Приклади дробово-лінійних задач
Задача 6.14.
Сільськогосподарське акціонерне товариство з обмеженою відповідальністю, яке розміщене в Лісостепу України, має намір оптимізувати структуру виробництва. За критерій оптимальності взято максимізацію рентабельності як відношення прибутку до собівартості. Дані про види діяльності, що їх здійснюватиме товариство, наведено в таблиці:
|
Показник |
Діяльність з вирощування |
Ресурс |
||||||
|
озимої |
цукрових |
корів продуктивністю, кг |
кормових |
|||||
|
5000 |
4500 |
4000 |
3500 |
|||||
|
Урожайність, т/га |
4 |
35 |
— |
— |
— |
— |
6 |
— |
|
Собівартість, грн./т |
600 |
250 |
600 |
700 |
800 |
9000 |
200 |
— |
|
Ціна, грн./т |
800 |
300 |
1000 |
1000 |
1000 |
1000 |
— |
— |
|
Вихід кормів, тон кормо- |
0,8 |
2,0 |
— |
— |
— |
— |
6 |
— |
|
Витрати живої праці, |
4 |
25 |
6 |
6 |
6 |
6 |
3 |
26 000 |
|
Витрати механізованої праці, людино-днів/га |
2 |
8 |
3 |
3 |
3 |
3 |
2 |
11 000 |
|
Частка корів у стаді |
— |
— |
0,1 |
0,2 |
0,3 |
0,4 |
— |
|
|
Потреба в кормах, т/гол |
— |
— |
5 |
4,7 |
4,4 |
4,1 |
— |
— |
Акціонерне товариство має 2500 га ріллі.
Записати економіко-математичну модель і знайти оптимальну структуру виробництва.
Розв’язання. Введемо позначення:
х1 — площа посіву озимої пшениці, га;
х2 — площа посіву цукрового буряка, га;
х3 — площа посіву кормових культур, га;
х4 — кількість корів продуктивністю 5000 кг;
х5 — кількість корів продуктивністю 4500 кг;
х6 — кількість корів продуктивністю 4000 кг;
х7 — кількість корів продуктивністю 3500 кг.
Запишемо критерій оптимальності:
за розглянутих далі умов.
1. Обмеження за ресурсами.
1) Ріллі:
.
2) Живої праці:
.
3) Механізованої праці:
.
2. Обмеження сівозміни.
1) Посівна площа кормових має бути більша або дорівнювати площі під озимою пшеницею:
.
2) Посівна площа озимої пшениці має бути більша або дорівнювати площі під цукровими буряками:
.
3. Структура корів за продуктивністю.
1) Балансове рівняння щодо корів:
,
де — загальна кількість корів.
2) Частка корів продуктивністю 5000 кг:
.
3) Частка корів продуктивністю 4500 кг:
.
4) Частка корів продуктивністю 4000 кг:
.
5) Частка корів продуктивністю 3500 кг:
.
4. Забезпеченість корів кормами:
.
Невід’ємність змінних:
.
Щоб знайти розв’язок за цією моделлю, зробимо відповідну заміну й скористаємося симплексним методом:
.
Отже, маємо таку лінійну економіко-математичну модель:
за розглянутих далі умов.
1. ,
,
.
2. , або ,
, або .
3. ,
,
,
,
.
4. .
5. .
Задача 6.15.
Розв’язати графічно задачу дробово-лінійного прог рамування:
за умов
Розв’язання. Побудуємо на площині область допустимих роз в’язків задачі — трикутник АВС.
Цільова функція задачі являє собою пряму, яка обертатиметься навколо початку системи координат залежно від змінюваних параметрів х1, х2 так, що точки А і С будуть точками максимуму і мінімуму функції. Виразимо х2 із цільової функції:
.
Кутовий коефіцієнт цільової функції
.
Розглянемо похідну
.
Оскільки при будь-якому значенні Z вона від’ємна, то функція RZ є спадною (зі зростанням Z кутовий коефіцієнт RZ зменшується), а графік цільової функції обертатиметься навколо початку координат за годинниковою стрілкою. Отже, точка С є точкою максимуму, а точка А — мінімуму досліджуваної задачі.
Знайдемо координати цих точок.
Точка А:
Звідси
Точка А має координати (6/7; 24/7).
Точка С:
Звідси
Точка С має координати (9/2; 1).
Знайдемо значення цільової функції в цих точках:
Результати (ZC > ZA) підтверджують, що оптимуми знайдено правильно: максимум досягається в точці С, а мінімум — у точці А.
Задача 6.16.
Розв’язати задачу дробово-лінійного програмуван ня симплексним методом:
за умов
Розв’язування. Зведемо початкову задачу до задачі лінійного програмування згідно з розглянутими раніше правилами.
Позначимо .
Введемо нові змінні:
, .
Дістанемо задачу лінійного програмування:
за умов
Розв’яжемо задачу симплексним методом. У перше та останнє обмеження введемо штучні змінні y6, та y7.
Маємо оптимальний розв’язок перетвореної задачі:
, , , .
Знайдемо оптимальний розв’язок початкової задачі, враховуючи, що :
; ; ;
; .
Отже, ,
.
6.2.3. Приклади та завдання для самостійної роботи
Задача 6.17.
Розв’язати графічно задачі дробово-лінійного програмування.
|
1. за умов |
2. за умов |
|
3. за умов |
4. за умов |
|
5. за умов |
6. за умов |
|
7. за умов |
8. за умов |
|
9. за умов |
10. за умов |
Задача 6.18.
Розв’язати задачі дробово-лінійного програмування симплексним методом.
|
1. за умов |
2. за умов |
|
3. за умов |
4. за умов |
|
5. за умов |
6. за умов |
|
7. за умов |
8. за умов |
6.3. НЕЛІНІЙНЕ ПРОГРАМУВАННЯ
6.3.1. Постановка задачі
Розв’язуючи задачі оптимального управління (планування), дово диться враховувати нелінійний характер взаємозв’язків між економічними показниками. У загальному вигляді нелінійна економіко-математична модель має вигляд:
за умов
,
де і — нелінійні функції.
6.3.2. Труднощі розв’язування
задач нелінійного програмування
Задачу нелінійного програмування намагаються звести до лінійного вигляду. Проте в такому разі можливі значні похибки. Нехай, наприклад, собівартість продукції y визначено як функцію , де х — обсяги виробництва. Ввівши заміну , дістанемо лінійну залежність . За такої заміни похибки немає. А коли , то заміна цієї залежності деякою лінійною функцією призводить до значних похибок, що ілюструє рис. 6.3.
Рис. 6.3.
У точках х1 і х3 значення собівартості для обох розглядуваних функцій однакові, але в усіх інших точках ці значення відрізняються, причому в точці х2 значною мірою:
.
Отже, лінеаризація нелінійних процесів є досить складною математичною задачею.
Для лінійних задач можна завжди знайти оптимальний розв’я зок універсальним методом — симплексним. При цьому немає проблеми з доведенням існування такого розв’язку. Адже в результаті розв’язування задачі симплексним методом завжди дістаємо один із варіантів відповіді: 1) знайдено розв’язок; 2) задача суперечлива, тобто її розв’язку не існує; 3) цільова функція не-
обмежена, отже, розв’язку також немає.
Для задач нелінійного програмування не існує універсального методу розв’язування, тому щоразу слід доводити існування розв’язку задачі, а також його єдиність. Це досить складна математична задача.
Відомі точні методи розв’язування нелінійних задач, але при цьому постають труднощі обчислювального характеру. Навіть для сучасних ПЕОМ відповідні алгоритми є доволі трудомісткими.
Для розв’язування нелінійних задач застосовують наближені методи, стикаючись із проблемою локальних і глобальних оптимумів. Наприклад, на рис. 6.4. маємо на відрізку локальні оптимуми в точках х0, х1, х2, х3, х4, х5, х6, х7, х8, х9, а глобальний — у точці х4 і х6.
Рис. 6.4
Більшість наближених методів дають змогу знаходити локальний оптимум. Визначивши всі локальні оптимуми, методом порівняння можна знайти глобальний. Проте для практичних розрахунків такий метод не є ефективним. Часто наближені методи не «вловлюють» глобального оптимуму, зокрема тоді, коли глобальний оптимум лежить досить близько до локального. Якщо відрізок [x0, x10] розіб’ємо на десять підвідрізків і глобальний оптимум потрапить у відрізок [xi, xi+1] (див. рис. 6.4), а ліворуч від xi та праворуч від xi+1 крива y = f (x) підніматиметься, то глобальний оптимум буде пропущеним. Звернемо увагу ще на один дуже важливий момент. У задачах лінійного програмування точка оптимуму завжди була граничною. Для нелінійних задач точка, яка є оптимальним планом, може бути граничною або такою, що міститься всередині допустимої області розв’язків (планів).
6.3.3. Метод множників Лагранжа
Для розв’язування задач нелінійного програмування не існує, як уже зазначалося, універсального методу, а тому доводиться застосовувати багато методів і обчислювальних алгоритмів, які ґрунтуються, здебільшого, на теорії диференціального числення, і вибір їх залежить від конкретної постановки задачі та форми економіко-математичної моделі.
Методи нелінійного програмування бувають прямі та непрямі. Прямими методами оптимальні розв’язки відшукують у напрямку найшвидшого збільшення (зменшення) цільової функції. Типовими для цієї групи методів є градієнтні. Непрямі методи полягають у зведенні задачі до такої, знаходження оптимуму якої вдається спрос тити. До них належать, насамперед, найбільш розроблені методи квадратичного та сепарабельного програмування.
Оптимізаційні задачі, на змінні яких не накладаються обмеження, розв’язують методами класичної математики. Оптимізацію з обмеженнями-рівностями виконують методами зведеного градієнта, ска жімо методом Якобі, та множників Лагранжа. У задачах оптимізації з обмеженнями-нерівностями досліджують необхідні та достатні умови існування екстремуму Куна—Таккера.
Розглянемо метод множників Лагранжа на прикладі такої задачі нелінійного програмування:
(6.15)
за умов
(6.16)
,
де функції і диференційовані.
Ідея методу множників Лагранжа полягає в заміні даної задачі простішою: на знаходження екстремуму складнішої функції, але без обмежень. Ця функція називається функцією Лагранжа і подається у вигляді:
(6.17)
де λі — не визначені поки що величини, так звані множники Лагранжа.
Знайшовши частинні похідні функції L за всіма змінними і прирівнявши їх до нуля:
запишемо систему
(6.18)
що є, як правило, нелінійною.
Розв’язавши цю систему, знайдемо і — стаціонарні точки. Оскільки їх визначено з необхідної умови екстремуму, то в них можливий максимум або мінімум. Іноді стаціонарна точка є точкою перегину (сідлова точка). Отже, для визначення достатніх умов екстремуму та діагностування його типу існує спеціальний алгоритм [15].
Розв’яжемо методом множників Лагранжа наведену далі задачу.
Задача 6.19.
Акціонерне товариство з обмеженою відповідальністю відвело 1200 га ріллі під основні рослинницькі культури — озиму пшеницю та цукрові буряки.
Техніко-економічні показники вирощування цих культур відбиває таблиця:
|
Показник |
Площа, га, відведена |
|
|
під озиму пшеницю, х1 |
під цукровий буряк, х2 |
|
|
Урожайність, т/га |
4 |
35 |
|
Ціна, грн./т |
800 |
300 |
|
Собівартість, грн./т |
Знайти оптимальну площу посіву озимої пшениці та цукрових буряків.
Нехай х1 — площа ріллі, відведена під сотні га озимої пшениці; х2 — площа ріллі, відведена під цукрові буряки, сотні га.
Зауважимо, що собівартість однієї тони пшениці та цукрових буряків залежить від відповідної площі посіву.
Запишемо економіко-математичну модель. За критерій оптимальності візьмемо максимізацію валового прибутку:
за умов
.
Запишемо функцію Лагранжа:
Візьмемо частинні похідні і прирівняємо їх до нуля:
Із цієї системи визначимо сідлову точку. З першої та другої рівностей знайдемо вирази для 1 і прирівняємо їх:
,
або
(6.19)
Із останнього рівняння цієї системи маємо:
.
Підставивши значення у (6.19), дістанемо:
або .
Розв’язавши це квадратне рівняння, дістаємо (178 га); (553 га).
Відповідно дістаємо: (1022 га); (647 га). Тобто сідловими точками є такі:
Обчислимо значення цільової функції у цих точках:
Отже, цільова функція набуває максимального значення, якщо озима пшениця вирощується на площі 647 га, а цукровий буряк — на площі 553 га.
6.3.4. Приклади задач нелінійного програмування
Задача 6.20.
Попит на продукцію, що виготовляється на двох видах обладнання, становить 120 одиниць. Собівартість, тис. грн., виробництва одиниці продукції на обладнанні кожної групи залежить від обсягу такого виробництва — відповідно х1 і х2 — та подається у вигляді для першої групи: ; для другої групи: .
Знайти оптимальний план виробництва продукції на кожній групі обладнання, який за умови задоволення попиту потребує найменших витрат, пов’язаних із собівартістю продукції.
Розв’язування. Математична модель задачі:
за умов
Згідно з методом множників Лагранжа складемо функцію Лагранжа:
.
Прирівнявши до нуля частинні похідні цієї функції за невідомими параметрами Х1, Х2 і , дістанемо систему рівнянь:
Розв’язавши цю систему, знайдемо:
Отже, на першій групі обладнання необхідно випускати 66,5, а на другій 53,5 одиниць продукції. При цьому мінімальні витрати, тис. грн., становитимуть:
6.3.5. Приклади та завдання для самостійної роботи
Задача 6.21.
За методом Лагранжа знайти точку умовного екстремуму.
|
1. , . |
2. , . |
|
3. , . |
4. , . |
|
5. , . |
6. , . |
|
7. , . |
8. , . |
|
9. , . |
10. , . |
|
11. , . |
12. , . |
|
13. , . |
14. , . |
|
15. , . |
16. , . |
|
17. , . |
18. , |
|
19. , . |
20. , . |
|
21. , |
22. , . |
|
23. , |
24. , |
|
25. , |
26. , |
Задача 6.22.
На виробництво трьох видів продукції A, B і C витрачають матеріальні, трудові та фінансові ресурси. Норми витрат на одиницю продукції, сумарний запас, а також розмір прибутку від реалізації одиниці продукції, що залежить від обсягу виробництва (в умовних одиницях), відбиває таблиця:
|
Ресурси |
Продукція |
Запас |
||
|
А |
В |
С |
||
Матеріальні |
4 |
5 |
7 |
100 |
|
Трудові |
3 |
6 |
8 |
120 |
|
Фінансові |
2 |
1 |
4 |
75 |
|
Прибуток |
||||
|
Обсяг виробництва |
Попит на продукцію видів В і С відомий і становить 12 і 8 од. Визначити оптимальний план виробництва продукції кожного виду, якщо ресурси потрібно використати повністю. Знайти оцінки ресурсів і подати економічний аналіз оптимального плану.
6.4. ДИНАМІЧНЕ ПРОГРАМУВАННЯ
6.4.1. Сутність динамічного програмування.
Принципи оптимальності
Усі економічні процеси та явища є динамічними, оскільки функціонують і розвиваються не лише у просторі, а й у часі.
Народне господарство, його галузі, регіони чи окремі підприємства мають розробляти стратегічні і тактичні плани. Перші виз начаються з допомогою динамічних моделей, розв’язки яких знаходять методами динамічного програмування. Зауважимо, що сума оптимальних планів на окремих відрізках планового періоду Т не завжди являє собою план, оптимальний на всьому такому періоді.
Розглянемо задачу оптимального розподілу капітальних вкладень, які можуть бути використані двома способами: з метою розвитку рослинництва або тваринництва. Відомо, що за першого способу отримаємо прибуток g(x), а за другого — h(y).
У такому разі однокрокову задачу можна подати у вигляді:
(6.20)
за умов
(6.21)
Нехай
, , , .
Тоді дану задачу можна записати так:
Розглянемо її як задачу оптимального використання капітальних вкладень за окремими інтервалами планового періоду Т, маючи на меті розподілити залишок капітальних вкладень на кінець j-го інтервалу (j = 1, 2, …, n) двома зазначеними способами. При цьому критерій оптимізації не змінюється: максимізуємо обсяг прибутку за весь плановий період Т.
Якщо на першому інтервалі використано b1 капітальних вкладень, то на його кінець залишилося їх:
,
де с, d — коефіцієнти пропорційності, що характеризують використання капітальних вкладень першим і другим способами: .
Задачу для другого інтервалу подамо так:
за умов
.
Звідси для будь-якого j-го інтервалу маємо:
за умов
.
Загальна задача набирає вигляду:
(6.22)
за умов ,
, .
Таку задачу розв’язують спеціальними методами [4, 10].
6.4.2. Методика розв’язування динамічних задач
Динамічний процес розбивається на сукупність послідовних етапів, або кроків. Кожний крок оптимізується окремо, а рішення (розв’язок), згідно з яким система переходить із поточного стану до нового, вибирається з урахуванням його майбутніх наслідків і не завжди дає найбільший ефект на даному етапі. На останньому кроці приймається рішення (відшукується розв’язок), яке забезпечує максимальний ефект. З огляду на сказане, оптимізація методом динамічного програмування починається з кінця: насамперед планується останній крок. Спираючись на відому інформацію про закінчення передостаннього кроку, на підставі різних гіпотез щодо його закінчення, вибирають управління на останньому кроці. Таке управління називають умовно оптимальним, оскільки знаходять його за припущення, що попередній крок було здійснено згідно з однією з можливих гіпотез.
Нехай аналізується деякий керований процес, перебіг якого можна розбити на послідовні етапи (кроки), що задаються. Ефективність всього процесу Z є сумою ефективностей окремих кроків:
(адитивний критерій)
або
(мультиплікативний критерій).
З кожним кроком задачі пов’язане прийняття певного рішення, так званого крокового управління , що визначає як ефективність даного етапу, так і всієї операції в цілому.
У задачі динамічного програмування знаходять таке управління всією операцією, яке максимізує загальну її ефективність:
Оптимальним розв’язком цієї задачі є управління , що складається із сукупності оптимальних покрокових управлінь
і забезпечує максимальну ефективність Z*
.
Усі класи задач динамічного програмування розв’язують, керуючись основним принципом: яким би не був стан системи S перед черговим кроком, управління на цьому кроці слід вибрати так, щоб ефективність розглядуваного кроку плюс оптимальна ефективність на всіх наступних кроках була максимальною.
Отже, маємо алгоритм розв’язування задач динамічного програмування.
1. Специфікуємо стан заданої керованої системи та множину параметрів, що описують цей стан. Стан системи обираємо, маючи на меті забезпечити зв’язок між послідовними етапами перебігу процесу і знайти допустимий розв’язок задачі в цілому як результат оптимізації на кожному кроці окремо. При цьому опти мальні рішення на наступних етапах приймаємо, нехтуючи впли вом подальших рішень на прийняті раніше.
2. Розбиваємо динамічний процес (операцію) на кроки, що відповідають, як правило, часовим періодам планування або окремим об’єктам (підприємствам, видам продукції, устаткування і т. ін.), стосовно яких розробляються управлінські рішення.
3. Подаємо перелік управлінських рішень для кож ного кроку і відповідні обмеження щодо них.
4. Визначаємо ефект, що його забезпечує управлінське рішення на j-му кроці, якщо перед тим система була у стані S, як функцію ефективності:
5. Досліджуємо, як змінюється стан S системи під впливом управлінського xj на j-му кроці, переходячи до нового стану:
.
6. Будуємо для розглядуваної задачі рекурентну залежність, що визначає умовний оптимальний ефект , починаючи з
j-го кроку і до останнього, через вже відому функцію :
.
Цьому ефекту відповідає умовне оптимальне управління на
j-му кроці . Зауважимо, що за аргумент функції беремо не s, а змінений стан системи, тобто .
7. Здійснюємо умовну оптимізацію останнього п-го кроку, розглядаючи множину станів s, що на один крок віддалені від кінцевого стану, і визначаємо умовний оптимальний ефект на п-му кроці:
.
Далі знаходимо умовне оптимальне управлінське рішення xn(s), завдяки якому цей максимум досягається.
8. Виконуємо умовну оптимізацію (n – 1)-го, (n – 2)-го і т. д., тобто всіх попередніх кроків за рекурентними залежностями п. 6, і для кожного кроку знаходимо умовне оптимальне управління:
9. Здійснюємо безумовну оптимізацію управління у «зворотному» напрямі — від початкового стану до кінцевого. Для цього з урахуванням визначеного оптимального управління на першому кроці змінюємо стан системи згідно з п. 5. Далі для цього нового стану знаходимо оптимальне управління на другому кроці і діємо так до останнього кроку.
6.4.3. Приклади розв’язування динамічних задач
Задача 6.23.
Фірма планує нарощувати виробничі потужності на чотирьох підприємствах, маючи для цього 4 млн грн. Для кожного з підприємств розроблено інвестиційні проекти, які відбивають прогнозовані сумарні витрати С та доходи D, пов’язані з реалізацією кожного проекту. Зміст цих проектів ілюструє таблиця:
|
Проект |
Підприємство |
|||||||
|
1 |
2 |
3 |
4 |
|||||
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
1 |
3 |
1 |
4 |
2 |
4 |
1 |
2 |
|
3 |
2 |
5 |
2 |
6 |
3 |
9 |
2 |
8 |
|
4 |
3 |
7 |
3 |
8 |
4 |
12 |
3 |
5 |
Перший проект передбачає відмовитися від розширення підприємства, а тому має нульові витрати і доходи. Розробити план інвестування виділених коштів у зазначені підприємства так, щоб одержати максимальний прибуток.
Розв’язування. Спрощеним і найменш ефективним способом розв’язування таких задач є перебір усіх можливих варіантів. Проте на практиці їх так багато, що проаналізувати всі і вибрати серед них найефективніший неможливо. Головними недоліками такого способу розв’язування є великий обсяг обчислень, відсутність апріорної інформації про неприпустимі розв’язки, а також неможливість скористатися проміжними результатами аналізу для відкидання неоптимальних комбінацій проектів.
Розв’яжемо цю задачу за алгоритмом (методом) зворотного прогону. Кроками задачі вважатимемо кожне з чотирьох підприємств, оскільки для кожного з них маємо вибрати оптимальний інвестиційний проект за обмежених грошових ресурсів.
Зауважимо, що в цьому разі нединамічний процес розглядаємо як динамічний, аби скористатися методами динамічного програмування для знаходження оптимального розв’язку. Зв’язок між зазначеними кроками забезпечується обмеженнями на загальний обсяг виділених коштів — 4 млн грн.
Змінні задачі візьмемо так, щоб послідовно керувати процесом розподілу коштів:
— обсяг капіталовкладень, виділених на кроках 1—4;
— те саме на кроках 2—4;
— те саме на кроках 3 і 4;
— те саме на кроці 4.
— обсяги інвестицій на і-му підприємстві .
— оптимальні обсяги інвестицій на і-му підприємстві.
Рекурентне співвідношення для зворотного прогону від кроку 4-го до 1-го (від четвертого підприємства до першого) подається у вигляді:
,
, ,
де — сумарна ефективність інвестицій з і-го кроку до останнього.
Тут , оскільки п’ятого підприємства не існує.
Виконаємо поетапні розрахунки за цією моделлю.
Етап 4.
.
Результати розрахунків подамо таблицею:
|
Дохід |
Оптимальний розв’язок |
||||||
|
0 |
0 |
0 |
0 |
0 |
|||
|
1 |
0 |
2 |
2 |
1 |
|||
|
2 |
0 |
2 |
8 |
8 |
2 |
||
|
3 |
0 |
2 |
8 |
5 |
8 |
2 |
|
|
4 |
0 |
2 |
8 |
5 |
8 |
2 |
Етап 3.
за умов
,
Результати розрахунків відбиває таблиця:
|
Дохід |
Оптимальний |
|||||
|
0 |
0 |
0 |
||||
|
1 |
2 |
0 |
||||
|
2 |
8 |
0 |
||||
|
3 |
9 |
3 |
||||
|
4 |
12 |
2 або 4 |
Розрахунки виконуються так. Нехай потрібно знайти . Обчислюємо
.
Отже,
,
,
.
Зауважимо, що , оскільки для третього підприємства не існує проекту з інвестиціями в 1 млн грн. Значення беремо з попередньої таблиці. Далі маємо:
.
Етап 2.
за умов
, .
Результати розрахунків подаємо таблицею:
|
Дохід |
Оптимальний |
||||||
|
0 |
0 |
0 |
0 |
||||
|
1 |
4 |
4 |
4 |
1 |
|||
|
2 |
8 |
6 |
6 |
8 |
0 |
||
|
3 |
9 |
12 |
8 |
8 |
12 |
1 |
|
|
4 |
12 |
13 |
14 |
10 |
14 |
2 |
Етап 1.
за умов
, .
Виконуємо розрахунки лише для х1 = 4, подаючи їх у вигляді таблиці:
|
Дохід |
Оптимальний |
|||||
|
4 |
15 |
1 |
Знайдемо оптимальний план. Із таблиці першого кроку випливає, що , тобто для першого підприємства реалізується другий проект, який використовує 1 млн грн. інвестицій з ефективністю 3 млн грн. Отже, для другого, третього і четвертого підприємств залишається 4 – 1 = 3 млн грн. інвестицій. Із таблиці другого кроку
маємо, що за умов х2 = 3 максимальний ефект настає в разі реалізації для другого підприємства першого проекту (k2 = 1), ефективність становить 4 млн грн. Отже, х3 = 3 – 1 = 2, тобто для третього і четвертого підприємств слід використати 2 млн грн. інвестицій. Із таблиці третього кроку за умов х3 = 2 маємо, що k3 = 0. Отже, х4 = 2, а йому відповідають капітальні вкладення k4 = 2, ефективність яких 8 млн грн. Остаточно маємо: ефективність 4 млн грн. інвестицій становить 3 + 4 + 8 = 15 (млн грн.).
Задача 6.24.
Підприємство розробляє стратегію поповнення запасів деякої продукції для заданого періоду часу, який складається з N етапів (підперіодів). Для кожного з них відомий розмір попиту, причому він не є однаковим для всіх етапів. Щоб задовольнити попит, підприємство може придбати необхідну кількість продукції, замовивши її у виробника, або виготовити її самостійно. Передбачається, що запаси поповнюються миттєво, запізнення поставки та дефіцит неприпустимі. Залежно від ринкової кон’юнктури підприємству може бути вигідно створювати запаси продукції для задоволення попиту в майбутні періоди часу, що пов’язано, проте, з додатковими витратами на зберігання запасів.
Розробити програму управління запасами підприємства, тобто визначити обсяги замовлення й період його розміщення, щоб загальні витрати на постачання та зберігання продукції були мінімальними, а попит задовольнявся повністю й своєчасно.
Дані задачі вміщено в таблиці:
|
Період часу |
Попит |
Витрати |
Витрати |
|
1 |
4 |
7 |
2 |
|
2 |
5 |
8 |
3 |
|
3 |
3 |
6 |
1 |
|
4 |
2 |
9 |
0 |
Відомо, що на початку планового періоду запас становить 2 тис. од., а під час купівлі продукції діє система оптових знижок. Витрати на придбання 1 тис. од. продукції становлять 15 тис. грн., а коли розмір замовлення перевищує 3 тис. од., витрати знижуються на 12% і становлять 12 тис. грн.
Нехай — кількість етапів планового періоду. Тоді для і-го етапу застосуємо такі позначення: хі — запас продукції на початок етапу; yi — обсяг замовленої продукції (розмір замовлення); hi — витрати на зберігання 1 тис. од. продукції запасу; kі — витрати на розміщення замовлення; — попит на продукцію; Ciyi — витрати, що пов’язані із купівлею (виробництвом) продукції yi.
Визначимо f (xi, yi) як мінімальні витрати на етапах , якщо рівень запасів хі.
Рекурентні залежності, що відповідають схемі зворотного прогону, набирають вигляду:
за умов
, , .
Для N-го етапу маємо:
за умов
, .
Розглянемо покроковий розрахунок оптимальної стратегії управління запасами.
Етап 4. Маємо
за умов
.
Можливі варіанти розв’язків ілюструє таблиця:
|
Оптимальний |
|||||
|
0 |
39 |
2 |
|||
|
1 |
24 |
1 |
|||
|
2 |
0 |
0 |
Етап 3. Маємо
за умов
.
Результати розрахунків подамо у вигляді таблиці:
|
Доходи |
Оптимальний |
|||||||
|
0 |
|
|
66 |
5 |
||||
|
1 |
|
|
|
55 |
4 |
|||
|
2 |
|
|
53 |
3 |
||||
|
3 |
|
39 |
2 |
|||||
|
4 |
|
25 |
1 |
|||||
|
5 |
5 |
0 |
Розрахунки виконуємо так. Наприклад, обчислимо і . Оскільки за умовою , то може набувати значень 0, 1, 2, 3, 4, 5, а — відповідно значень 0, 1, 2, 3, 4, 5. Тепер знайдемо і для і . Для і маємо:
.
Аналогічно:
,
.
Далі обчислюємо:
Отже, при .
Так само виконуємо розрахунки для х = 1, 2, 3, 4, 5, а результати вміщуємо у відповідну таблицю.
Етап 2. У таблицю записуємо лише остаточні результати:
Маємо 3 = 5.
за умов
.
Етап 1. Діємо так, як і на етапі 2, складаючи таблицю результатів:
|
Оптимальні |
|||||||||||||
|
134 |
135 |
145 |
143 |
141 |
133 |
133 |
10 |
||||||
|
125 |
126 |
136 |
134 |
132 |
124 |
124 |
9 |
||||||
|
125 |
117 |
127 |
125 |
123 |
115 |
115 |
8 |
||||||
|
113 |
117 |
118 |
116 |
114 |
106 |
106 |
7 |
||||||
|
101 |
105 |
118 |
107 |
105 |
97 |
97 |
6 |
||||||
|
81 |
93 |
106 |
107 |
96 |
88 |
81 |
0 |
||||||
|
73 |
94 |
95 |
96 |
79 |
73 |
0 |
|||||||
|
74 |
83 |
74 |
79 |
74 |
0 або 2 |
||||||||
|
63 |
72 |
67 |
63 |
0 |
|||||||||
|
52 |
55 |
52 |
0 |
||||||||||
|
35 |
35 |
0 |
|
Оптимальні |
|||||||||||||
|
2 |
174 |
180 |
174 |
177 |
180 |
176 |
180 |
193 |
194 |
195 |
180 |
174 |
2 або 4 |
Маємо 1 = 4.
за умов
.
Отже, дістали два оптимальні плани управління запасами підприємства, яким відповідають мінімальні сумарні витрати на пос тачання та зберігання продукції.
Інформацію про перший оптимальний план містить таблиця:
|
Етап |
Запас |
Розмір |
Попит |
Залишок |
Витрати на придбання |
|
1 |
|||||
|
2 |
|||||
|
3 |
|||||
|
4 |
|||||
|
Разом |
174 |
Інформація про другий оптимальний план:
|
Етап |
Запас |
Розмір |
Попит |
Залишок |
Витрати на придбання |
|
1 |
|||||
|
2 |
|||||
|
3 |
|||||
|
4 |
|||||
|
Разом |
174 |
Порівнюючи ці два плани, бачимо, що відрізняються вони першими двома етапами і дають можливість маневрувати фінансовими ресурсами підприємства, що водночас вирішує ще низку проблем.
204