Задача про розподіл ресурсів (Динамічне програмування)

Задача про розподіл ресурсів

Ця задача має пряме відношення до прикладних економіч­них задач і може бути розв'язана методом динамічного програ­мування.

Сформулюємо умову цієї задачі:

Інвестиції у розмірі К одиниць коштів повинні бути розпо­ділені між п підприємствами. Відомо, який дохід pr[i,j] (j = 1,2,..., n) дає кожне з визначених підприємств при вкладанні у нього і оди­ниць коштів (1 < і < К). Необхідно визначити, як найкраще роз­поділити інвестиційні кошти між підприємствами, щоб сумарний дохід був максимальним. Під час розв'язування задачі врахувати, що змінні К та і набувають лише цілих невід'ємних значень.

Розглянемо конкретний приклад для випадку, коли інвестиції в розмірі 6 одиниць коштів вкладаються у 4 під­приємства. Дохід цих підприємств за­даний таблицею 1:

i	P1	P2	P3	P4
1	0,5	0,1	1,1	1,0
2	1,0	0,8	1,9	2,0
3	1,4	1,6	1,4	2,5
4	2,0	2,5	1,5	2,5
5	2,5	2,9	1,5	2,5
6	2,5	2,9	1,5	2,5

Які логічні висновки можна зробити, проаналізу­вавши ці дані? По-перше, дохід кожно­го підприємства зростає зі зростанням вкладених у його виробництво коштів. По-друге, для кожного підприємства настає момент насичення, тобто така ситуація, коли вкладення додаткових

коштів не дає прибутку. Це можна пояснити тим, що потуж­ність кожного підприємства (працівники, обладнання тощо) обмежена і є межа коштів, які кожне підприємство в змозі ре­алізувати. По-третє, видно, що четверте підприємство порів­няно з першим є потужнішим щодо росту ефективності вироб­ництва, однак меншим, ніж перше, оскільки межа вкладених коштів для нього становить 3, а для першого підприємства 5. З урахуванням усіх цих факторів навряд чи можна інтуїтивно знайти правильну оптимальну відповідь.

Звернемося до методу динамічного програмування. Чи може він бути застосований для розв'язання цієї задачі? Проаналі­зуємо наявність у даній задачі відомих нам основних характе­ристик задач динамічного програмування:

-     поділом на етапи може бути дослідження вкладення коштів для кожного окремого підприємства;

-     залежність між цими етапами так само очевидна: від того, яка сума коштів буде вкладена в перше підприємство, можна буде визначити, яким залишком цих коштів зможе скориста­тися решта підприємств. Аналогічна ситуація стосується й інших підприємств;

-     для кожного підприємства необхідно розглянути всі варіанти вкладення коштів від 0 до К і вибрати найкращий, тобто такий, який дає максимально можливий прибуток, збе-рігши його в таблиці.

Отже, наявні всі елементи, притаманні задачі динамічного програмування.

Перейдемо до розв'язування задачі й почнемо із структури даних, де зберігатиметься поточна інформація. Зрозуміло, що такою структурою є таблиця. Треба визначитися стосовно вмісту її рядків і стовпців. Для цього з'ясуємо кілька питань, По-перше, що є об'єктом нашого дослідження? Це окремі під­приємства. По-друге, які конкретні ситуації треба розглянути стосовно кожного з цих підприємств? Прибуток від вкладання в них інвестиційних коштів. Але оскільки невідомо, яким чи­ном уся сума має бути розподілена між підприємствами, то тре­ба передбачити розгляд усіх можливих її значень: 0, 1, 2, ...,К. Отже, розмістимо інформацію в таблиці так: рядки і - суми можливих інвестицій від 0 до К, стовпці j - інформація про підприємства, що складається із максимального прибутку pr[j], який дасть дане підприємство при вкладенні в нього інвес­тиційних коштів у розмірі inv[j] одиниць. Розмір коштів inv[j] - це один із можливих варіантів 0,1,2, ..., і (inv[j] <= і), при якому су­ма доходів підприємства j і доходів усіх попередньо розгляну­тих підприємств при вкладенні в них коштів у розмірі (i - inv[j] ) буде максимальною. Дані записуватимемо у таблицю 2:

i	p1		p2		p3		p4
	inv1	pr1	inv2	pr2	inv3	pr3	inv4	pr4
0	0	0
1	1	0,5
2	2	1,0
3	3	1,4
4	4	2,0
5	5	2,5
6	6	2,5

Розв'язуватимемо задачу за залишковим принципом, тобто кожного разу аналізуватимемо поточну ситуацію з думкою, що вже деякі кошти на даний момент інвестовані, і визначатиме­мо, як треба найкраще розподілити їхній залишок. Наприклад, для першого підприємства цю ситуацію можна тлумачити так: між підприємствами р₂, р₃, ..., р_п кошти вже якимось чином розподілені і нам потрібно визначити найкращий варіант їх вкладення в підприємство p1. На наступному кроці виконання методу динамічного програмування розглядатимемо підприєм­ство р₂, вважаючи, що задача розв'язана для решти підприємств р₃, ..., р_п . Розмір коштів, які визначатимуться для вкладання у підприємство р₂, - це залишок від уже вкладених інвестицій у підприємства р₃, ...,р_п, що враховує також розраховані інтереси підприємства р_х. Останнє підприємство р_п розглядатиметься нами як те, з якого починається вкладання коштів, тобто ніякого залишку ще немає і в нашому розпорядженні є всі інвестиційні кошти.

З урахуванням вищезазначеного логічно вважати, що на першому кроці ітераційного алгоритму, що реалізовує метод динамічного програмування, виконується п-й етап, на друго­му - (п - 1)-й, на останньому - 1-й етап. Тобто можна говорити, що задачі лінійного програмування розв'язуються з кінця до початку.

Для більшої зрозумілості вищесказаного перейдемо до конк­ретного прикладу. Підприємства розглядатимемо в тому по­рядку, в якому вони задані в таблиці 1.

На першому кроці розв'язання задачі, що відповідає четвер­тому етапу, розглянемо підприємство p1. Оскільки ми домо­вилися задачу розв'язувати за залишковим принципом і поки що невідомо, яку суму найкраще віддати цьому підприємству, то розглянемо всі можливі випадки інвестування коштів від 0 до К. Ця інформація є у вхідній таблиці 1 і без змін пе­реноситься до обчислювальної таблиці в стовпець р1 (таблиця 2). Будемо її тлумачити так: якщо залишок коштів для під­приємства р1 становитиме 0, то прибуток буде також 0, якщо 1, то - 0,5, і так далі до залишку 6 одиниць і прибутку 2,5. При цьому матимемо на увазі, що на даному етапі для решти під­приємств р₂, р₃, р₄ відповідно виділяється 6, 5, 4, ..., 1, 0 оди­ниць коштів.

Тут слід знову нагадати суттєве для більшості задач динаміч­ного програмування зауваження, про яке згадувалося раніше: задача на всіх етапах розв'язується за залишковим принци­пом. Тобто на кожному етапі, розглядаючи підприємство Pj, вважатимемо, що для нього залишилось коштів у розмірі і оди­ниць, а саме 0,1,2,... або К.

На третьому етапі (другий ітераційний крок) алгоритму розглянемо підприємство р₂ за умови, що наступні за порядком задані підприємства отримали певну кількість коштів і для першого підприємства проведено аналіз розподілу решти коштів.

Починаємо заповнення інформації для і = 0. Зрозуміло, що при нульових інвестиціях прибуток також становитиме 0. Роз­глянемо випадок, коли при розподілі інвестицій черга дійде до другого підприємства і їхній розмір становитиме 1. Пам'ятаю­чи, що для попереднього підприємства інформація вже існує, цю суму можна розподілити так: другому підприємству від; 0 коштів, тоді попередньому дістанеться 1, або другому під ємству - 1, а попередньому - 0. У першому випадку приб; будуть такі: при нульових вкладеннях у підприємство р₂ буток становитиме 0, а при вкладеннях у розмірі 1 у попер підприємство - 0,5 (інформація з попереднього стовпця) сумарно становитиме прибуток у розмірі 0,5. У другому ві ку при вкладенні коштів у розмірі 1 у підприємство р₂ одержимо прибуток 0,1 (малюнок 1, 2-й стовпець), а нульових коштів у  попереднє підприємство - 0. Таким чином, сумарний приб у другому випадку становитиме 0,1. Порівнявши результати двох прорахованих варіантів і враховуючи те, що ми розв'язуємо задачу максимізації, виберемо з них більше значення, яке одержується за умови надання підприємству р₂ інвестицій у розмірі 0 одиниць, а попередньому (на даному етапі р1) - 1. Результат запишемо в таблицю 3 для підприємства р₂ і для i=1.

i	p1		p2		p3		p4
	inv1	pr1	inv2	pr2	inv3	pr3	inv4	pr4
0	0	0	0	0
1	1	0,5	0	0,5
2	2	1,0	0	1,0
3	3	1,4	3	1,6
4	4	2,0	4	2,5
5	5	2,5	4	3,0
6	6	2,5	4	3,5

Аналогічно робляться розрахунки для інших значень і = 2, 3, 4, 5, 6. На малюнку 4 наведено приклад розрахунку значень inv₂ i pr₂ для підприємства р₂ при і = 3.

p2		p1		Cума прибутків
inv2	pr2	inv1	pr1
0	0	3	1,4	1,4
1	0,5	2	1,0	1,5
2	1,0	1	0,5	1,5
3	1,6	0	0	1,6

На третьому ітераційному кроці розглянемо другий етап розв'язування задачі і дослідимо підприємство р₃. Попередньою інформацією для нього є варіанти розподілу різних за значеннями залишкових інвестицій між підприємствами p1 i p2. Ця інформація вже прорахована і міститься в наступному стовпці таблиці 5:

i	p1		p2		p3		p4
	inv1	pr1	inv2	pr2	inv3	pr3	inv4	pr4
0	0	0	0	0	0	0
1	1	0,5	0	0,5	1	1,1
2	2	1,0	0	1,0	1	1,6
3	3	1,4	3	1,6	1	2,1
4	4	2,0	4	2,5	1	2,7
5	5	2,5	4	3,0	1	3,6
6	6	2,5	4	3,5	1	4,1

 Не варто наводити всі розрахунки для інвестицій у розмірах 0, 1, 2,..., 6. Зробимо це лише для і = 5 (таблиця 6)

p3		p2		Cума прибутків
inv3	pr3	inv2	pr2
0	0	5	3,0	3,0
1	1,1	4	2,5	3,6
2	1,3	3	1,6	2,9
3	1,4	2	1,0	2,4
4	1,5	1	0,5	2,0
5	1,5	0	0	1,5

 і прокоментуємо для цієї ситуації вибір інвестицій у підприємство р₃ значення 1 як найкраще. Загальний розмір інвестицій, які можуть бути надані підприємству р₃, обмежені значенням 5. Цю суму можна повністю віддати підприємствам р₁ і р₂ і мати при цьому прибуток у розмірі 3,0. Це зафіксовано в таблиці 5 (в рядку 5 і стовпці, який містить інформацію про р₂₎. У такому разі підприємству не залишиться ніяких коштів і прибуток становитиме 0. Сумарний прибуток при такому розподілі інвести­ційних коштів становитиме 3,0 (1-й рядок таблиці 6). Якщо підприємству р₃ виділити з 5 одиниць інвестицій 1 одиницю, то його прибуток становитиме 1,1. У такому разі підприємствам р₁ і р₂ залишиться 4 одиниці коштів і їх загальний прибуток становитиме 2,5 (4-й рядок, стовпець для підприєм­ства р₂, таблиця 5). Тепер визначимо суму прибутків від такого розподілу коштів у 5 одиниць: вона становитиме 3,6 (2-й рядок таблиці 6). Проаналізувавши всі рядки таблиці 6, можна зробити висновок, що найбільший і прибуток буде тоді, коли підприємству р₃ буде виділено 1 оди­ницю коштів із 5 можливих.

На останньому, першому етапі немає потреби розглядати всі можливі варіанти інвестування коштів від 0 до К у підприємство р₄. Ми розв'язуємо задачу на кожному етапі за залишковим принципом, тобто ніби рухаємося з кінця до початку, розгляда­ючи спочатку останнє підприємство, якому залишилися певні кошти, потім передостаннє і насамкінець початкове (у нашому випадку p₄), з якого починається розподіл інвестицій. Тому вва­жатимемо, що у цього підприємства на початку є всі можливі інвестиційні кошти в розмірі К одиниць. А от визначитися, яку частину з цієї суми краще віддати йому, а скільки залишити для інших підприємств, ми й повинні на цьому етапі. Це можна зробити за тією самою схемою, що і на попередніх етапах задачі. Розглянемо всі варіанти розподілу суми К одиниць між під­приємством p₄ і рештою підприємств p1, р₂, р₃: 0 - 6; 1 - 5; 2 - 4; З- 3; 4- 2; 5 - 1;6 - 0. Уся необхідна інформація для визначен­ня кращого з усіх цих варіантів щодо розміру прибутків міс­титься в останньому стовпці вхідної таблиці 1 та в по­передньому стовпці таблиці 7:

i	p1		p2		p3		p4
	inv1	pr1	inv2	pr2	inv3	pr3	inv4	pr4
0	0	0	0	0	0	0
1	1	0,5	0	0,5	1	1,1
2	2	1,0	0	1,0	1	1,6
3	3	1,4	3	1,6	1	2,1
4	4	2,0	4	2,5	1	2,7
5	5	2,5	4	3,0	1	3,6
6	6	2,5	4	3,5	1	4,1	2	4,7

 Розрахунок усіх можливих варіантів розподілу коштів для підприємства p₄ представлено в таблиці 8:

p4		p3		Cума прибутків
inv4	pr4	inv3	pr3
0	0	6	4,1	4,1
1	1,0	5	3,6	4,6
2	2,0	4	2,7	4,7
3	2,5	3	2,1	4,6
4	2,5	2	1,6	4,1
5	2,5	1	1,1	3,6
6	2,5	0	0	2,5

 Кращим варіантом розподілу інвестиційних коштів є такий: підприємству p₄ надати 2 одиниці, а решті підприємств - 4. При цьому марний прибуток у розмірі 4,7 одиниць буде найбільшим.

Отримано розв'язок поставленої задачі: максимальний прибуток при вкладенні інвестиційних коштів у розмірі 6 одні у підприємства р1, р₂, р₃, р₄ становитиме 4,7 одиниць.

Залишилося відкритим запитання: а як ці кошти розподілити між підприємствами для отримання такого сумарного прибутку? Відповідь міститься безпосередньо у таблиці 7. Для останнього розглянутого підприємства р₄ відповідь однозначна: йому треба надати інвестиції у розмірі 2 одиниці. При цьому решті підприємствам залишається 4 одиниці. Переходимо до інформації, що міститься в попередньому стовпці матриці 7. У четвертому її рядку міститься інформація про те, що за наявності 4 одиниць інвестицій підприємству р₃ слід виділити з них 1 одиницю. Тепер у нас залишилося 3 одиниці інвестиційних коштів для розподілу їх  підприємствам р1 і р₂. Переходимо до інформації про підприємство р₂ і визначаємося зі стратегією подальших дій щодо цього підприємства. У третьому рядку і стовпці, що стосується різних варіантів розподілу коштів для підприємства р₂, розміщена інформація і про те, що за наявності 3 одиниць інвестиційних коштів підприємству р₂ треба виділити 3 одиниці, отримавши при цьому прибуток 1,6 одиниць. Таким чином, залишок інвестицій на поточний момент становить 0 одиниць. Саме стільки з шається підприємству р₁. У таблиці 7 півжирним курсивом виділена інформація про розподіл інвестиційних коштів між усіма підприємствами для нашого конкретного прикладу.

Як бачимо, розв'язання задачі про розподіл ресурсів вимагає додаткових проміжних обчислень, оптимальний результат яких записується в таблицю. Відповідь виконання алгоритму розміщена, як і в попередніх задачах, у правому нижньому елементі таблиці, а розподіл коштів між окремими підприємства­ми можна визначити із самої таблиці.

Незважаючи на нібито складний алгоритм розв'язання за­дачі, його програмний код, що супроводжується коментарями, виглядає досить акуратно і зрозуміло. Пояснимо призначення деяких змінних. У двовимірному масиві profit[i,j] міститься вхідна інформація про прибуткову ефективність підприємств. Для розрахунків значень таблиці використовується дво­вимірний масив с[i,j] типу record з полями invest, де міститься розмір інвестицій, та prof - розмір прибутків. Змінна max_prof використовується для визначення максимального значення по­точного прибутку.

for І := 0 to k do   {Визначення прибутку для підприємства р1 від вкладання i коштів.}

 begin

        с[і, 1].invest := і;

        с[і, 1].prof := profit[i, 1];

end;

for j := 2 to n do       {Розрахунок значень таблиці для підприємств р₂, р₃, ... , р_п.}

for і := 1 to k do

 begin

   maxprof := 0;                                  {Початкове значення максимуму.}

   for t := 0 to i do   {Пошук максимального значення сумарного прибутку між}

                                                                                                          {підприємством p_j}

           if profit[t, j] + c[i - I, j - 1].prof > max.prof        {і рештою підприємств.}

              then begin

                  max_prof := profit[t, j] + c[i -1, j - 1].prof;

                  maxjnv := i

             end;

  c[i, j].invest := maxjnv; c[i, j].prof := maxprof; {Занесення обчислених}

end;          , {оптимальних значень у результуючу таблицю.}

Виведення розподілу інвестиційних коштів між усіма під­приємствами може бути таким:

{Виведення значення максимального сумарного прибутку}

writeln(f, c[k, n].prof:0:2);

і := k; j := n;          {Початок виведення розподілу коштів між підприємствами.}

while j > 0 do                        {Поки не розглянуті всі підприємства, вивести}

begin                                 {розмір інвестицій для Pj при залишку / одиниць,}

  write(f_out, j, '-- > ', с[і, j].invest, '; ');

  dec(i, c[i,j].invest); {обчислити нове значення залишку інвестиційних коштів,}
  dec(j);                                     {перейти до попереднього підприємства.}

end;

Для визначення оцінки ефективності роботи алгоритму роз­в'язування задачі про розподіл ресурсів між підприємствами, проаналізуємо кількість виконаних дій на кожному етапі. Зага­лом обчислювалися елементи таблиці розмірністю n*k, для чого було виконано відповідно n*k операцій. Для обчислення кожного і-го елемента таблиці аналізуються значення від 0 до і. Оскільки і змінюється від 0 до k, то в середньому таких обчислень буде k/2. Таким чином одержимо загальну кількість виконуваних дій nk²/2, тобто приблизно nk². Ми вийшли на оцінку ефективності роботи описаного алгоритму в такому вигляді: O(nk²). Це дещо більше, ніж було в попередній задачі, однак значно вигідніше, ніж повний перебір усіх можливих варіантів і визначення кращого з них. Під час тестування розробленого алгоритму у вигляді програми слід передбачити обробку інформації для невеликих значень пік (наприклад, п <= 10, k <= 10) та значно більших (наприrлад, п <= 100, k<= 100). Цікаво також дослідити кількість виконуваних операцій при п<= 10, k <= 100 та п <= 100, k <= 10. Зрозуміло, що вона буде залежати більшою мірою від розміру інвестиційних коштів. Щодо дослідження впливу прибуткої ефективності підприємств на результат розподілу коштів між ними, то можна запропонувати згенерувати такі вхідні дані:

-    усі підприємства мають однакову прибуткову ефективність:

-    підприємства утворюють зростаючу послідовність щодо прибуткової ефективності;

-    підприємства утворюють спадну послідовність щодо прбуткової ефективності;

-    підприємства суттєво відрізняються один від одного щодо прибуткової ефективності.

До речі, слід зазначити, що при зміні послідовності розгляду досліджуваних підприємств оптимальна відповідь збережеться, а от розподіл інвестицій між ними може виявити іншим. Варто дослідити це під час тестування.