- •Міністерство освіти і науки України
- •Математичні моделі економічних задач
- •1.1. Задача планування виробництва
- •1.2. Задача складання раціону (задача про дієту, задача про суміші)
- •1.3. Транспортна задача
- •1.4. Задача про мінімізацію відходів
- •К 2ількість шматків
- •1.5. Задача про призначення
- •Загальна постановка задач лінійного програмування (лп)
- •Перелік питань для самоперевірки
- •Лекція 2
- •Тема 2. Геометрична інтерпретація задач лінійного програмування. Задача лінійного програмування, форми її запису
- •Приведення задачі лп до канонічного виду
- •Приведення задачі лп до симетричного виду
- •Перелік питань для самоперевірки
- •3.1. Визначення вихідного опорного плану
- •3.2. Симплексні таблиці
- •3.3. Поняття про м-метод
- •Перелік питань для самоперевірки
- •Лекція 4
- •Тема 4. Двоїстість у лінійному програмуванні
- •Перелік питань для самоперевірки
- •Лекція 5
- •Тема 5. Методика розв’язування транспортної задачі
- •5.1. Приведення задачі до замкненої форми
- •5.2. Визначення вихідного опорного плану
- •5.3. Метод потенціалів
- •Перелік питань для самоперевірки
- •6.1. Метод відсікань Гоморі
- •Перелік питань для самоперевірки
- •Лекція 6
- •Тема 7. Елементи теорії ігор
- •7.1. Графічний метод
- •7.2. Приведення матричної гри до задачі лінійного програмування
- •Перелік питань для самоперевірки
- •8.2. Задачі нелінійного програмування з нелінійною цільовою функцією та лінійною системою обмежень
- •Перелік питань для самоперевірки
- •Лекція 8
- •Тема 9. Динамічне програмування
- •9.1. Задача про розподіл коштів між підприємствами
- •Рішення
- •9.2. Задача про заміну обладнання
- •Рішення
- •Перелік питань для самоперевірки
- •Список рекомендованої літератури
9.1. Задача про розподіл коштів між підприємствами
Задача 9.1. Планується діяльність чотирьох промислових підприємств на черговий рік. Початкові кошти: тис. грош. од. Коштиx, виділені k-му підприємству (k=1,2,3,4), приносять наприкінці року прибуток . Функціїзадані таблично (табл. 9.1). Визначити, скільки коштів потрібно виділити кожному підприємству, щоб сумарний прибуток був найбільшим.
|
Таблиця 9.1 | ||||
---|---|---|---|---|---|
x |
|
|
|
| |
75 |
100 |
110 |
100 |
120 | |
150 |
200 |
210 |
210 |
210 | |
225 |
250 |
250 |
260 |
260 | |
300 |
350 |
340 |
360 |
340 |
Рішення
Система управління – чотири підприємства, а управління полягає у розподілі коштів між ними. Процес управління розбиваємо на чотири кроки: номер кроку – номер підприємства,n=4. Параметр стану –(k=1,2,3,4)–кошти, що підлягають розподілу між4–kостанніми підприємствами, кінцевий стан– усі кошти мають бути вкладені у виробництво. Змінна управління –(k=1,2,3,4)– кількість коштів, виділених k-му підприємству. Схема процесу розподілу коштів наведена нарис. 9.2.
Рис. 9.2
Рівняння станів (9.1) у даній задачі мають вид:
, k=1,2,3,4.
Показник ефективності k-го кроку – прибуток, отриманий k-м підприєм-ством наприкінці року: ,k=1,2,3,4.
Сумарний показник ефективності – сумарний прибуток .
Нехай – умовний оптимальний прибуток, отриманий відk-го, (k+1)-го, …, 4-го підприємств, якщо між ними кошти () розподілялися оптимально. Тоді оптимальний сумарний прибуток.
Рівняння Беллмана мають вид:
, (9.4)
, (9.5)
, (9.6)
. (9.7)
Послідовно розв’язуємо записані рівняння, здійснюючи умовну оптимізацію (див. рис. 9.2) кожного кроку.
IV крок. У табл. 9.1. прибутки монотонно зростають, тому умовний оптимальний прибуток від 4-го підприємства (див. формулу (9.4)):
при .
Для можливих значень одержимо:
, ,
, .
III крок. Умовний оптимальний прибуток від 3-го і 4-го підприємств (див. формулу (9.5)) для можливих значень :
при ;
при ;
при ;
при .
II крок. Умовний оптимальний прибуток від 2-го, 3-го і 4-го підприємств (див. формулу (9.6)) для можливих значень :
при ;
при ;
при ;
при .
I крок. Оптимальний прибуток від чотирьох підприємств (9.6):
при .
На цьому умовна оптимізація закінчується. Використовуючи її результат, одержимо
, ,
,
, .
Отже, оптимальне управління: .
Висновок: максимум сумарного прибутку дорівнює 440 тис. грош. од. за умови, що 1-му підприємству кошти не виділяються; 2-му підприємству виділяється 75 тис. грош. од.; 3-му підприємству – 150 тис. грош. од.; 4-му підприємству – 75 тис. грош. од.