Загальна задача динамічного програмування

Загальна задача динамічного програмування

Після розгляду найтиповіших задач динамічного програмування, простіше  сформулювати його основні ідеї. Почнемо із формулювання загальної задачі динамічного програмування в алгоритмічних термінах.

Нехай розв'язується деяка задача S. Для її розв'язання зада­ні вхідні дані S_o, що надалі оброблятимуться. У результаті за­стосування до цих вхідних даних розробленого оптимізаційного алгоритму U її буде перетворено у вигляд S_n. Процес виконання алгоритму можна представити як деяку функцію W(U), що дає кілька варіантів розв'язків. Оскільки задача динамічного програмування є задачею оптимізаційною, то серед усіх отриманих варіантів відповідей треба вибрати найкращий W*(U).

Методика розв'язування задач динамічного програмування бу­ла запропонована Р.Беллманом у 1955 р. і полягає в наступному.

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

Кожний з етапів є окремою підзадачею поставленої загаль­ної задачі і розв'язується одним і тим самим розробленим оптимізаційним алгоритмом. Однак вибір розв'язків кожної на­ступної підзадачі залежить від розв'язків попередньої, і тому їх можна назвати залежними. Будемо вважати, що на першому етапі вхідна інформація S_o перетворюється алгоритмом U у вигляд S1. Тепер при виконанні наступного етапу вхідними даними для нього буде вже S1. При цьому застосування алго­ритму на даному етапі може дати багато варіантів розв'язків w₁(u), серед яких ми вибираємо ті, які надалі приведуть до найкращого кінцевого результату, тобто є перспективними. Позначимо їх w*₁(u). Аналогічно будуть перетворюватися вхідні дані на наступних етапах S₂, ..., S_n-1. Отже, оптимізація всієї задачі зводиться до визначення оптимальних результатів застосування розробленого алгоритму w*_i(u) на кожному окре­мому етапі.

P. Беллманом був сформульований принцип оптимальності: якою не була б інформація, що обробляється, перед черговим етапом необхідно вибрати стратегію на поточному етапі так, щоб виграш на цьому етапі плюс оптимальний виграш на всіх наступних етапах був максимальним.

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

Таким чином, згідно з принципом Беллмана розв'язування задачі динамічного програмування доцільно починати з визначення оптимального розв'язку на останньому n-му етапі. Для того, щоб знайти цей розв'язок, необхідно зробити різні передбачення щодо закінчення передостаннього етапу. Така стратегія, що вибрана при певних передбаченнях про те, як може закінчитися попередній етап, називається умовно оптимізаційною стратегією. Тобто принцип оптимальності вимагає знаходити на кожному етапі умовно оптимальну стратегію для будь-якого з можливих результатів попереднього етапу.

Поступово здійснюючи описаний ітераційний процес, дійдемо до першого етапу. На цьому етапі нам відомо, в якому стані може знаходитись інформація, що обробляється, а тому немає потреби робити передбачення щодо її допустимих станів. 3aлишається лише вибрати стратегію, яка є найкращою з урахуванням умовно оптимальних стратегій, уже прийнятих на всіх попередніх етапах.

Таким чином, проходячи послідовно всі етапи з кінця до початку, можна визначити максимальне значення виграшу з n кроків.

Щоб знайти оптимальну стратегію, тобто визначити шуканий розв'язок задачі, необхідно пройти всю послідовність етапів у зворотному порядку. Теоретично ця послідовність виглядає так: на першому етапі в якості оптимальної стратегії необхідно взяти знайдену умовну оптимальну стратегію. На другому етапі визначити стан інформації S1*, яка отримується для задачі в результаті вибору умовної оптимальної стратегії и*_1. Цей стан визначає знайдена умовна оптимальна стратегія и(0)_2, яку тепер вважатимемо оптимальною і т. д. У результаті цього знаходимо розв'язок задач, тобто максимально можливий виграш та оптимальну стратегію U*, що включає в себе умовну оптимальну стратегію на окремих етапах: U* = (и*₁, и*₂, ... , и*_n).

Зробимо ще одне зауваження: у будь-якій задачі динамічно­го програмування «початок» і «кінець» можна поміняти місця­ми. Це повністю рівнозначне описаній вище методиці щодо ви­конуваних розрахунків, однак при такому підході виникають незручності щодо пояснення ідеї методу: простіше аргументу­вати, посилаючись на умови, що «вже склалися» до початку да­ного кроку, ніж на ті, які ще «попереду» цього кроку. По суті, обидва підходи абсолютно рівносильні і досить умовні. При­кладом цього може служити перша розглянута задача про прокладання найвигіднішого шляху між двома пунктами. Ми її розв'язували від пункту А до пункту В, а можна було навпа­ки. При цьому результуюча відповідь була б однаковою.

У кожній розглянутій задачі визначалася оцінка ефектив­ності роботи розробленого для її розв'язання алгоритму. І справді, оцінку менше ніж О(пт) для задач динамічного про­грамування отримати неможливо, оскільки у кращому разі нам доводиться хоч один раз обробляти кожний елемент таб­лиці розмірністю п*т. Але трапляються й об'ємніші щодо часу виконання задачі. З цим ми ознайомилися в задачі про роз­поділ ресурсів. Ученими доведено, що максимальною оцінкою ефективності роботи алгоритмів, які базуються на методі ди­намічного програмування, можна вважати О(пт log(nm)).

Критерії застосування задач динамічного програмування

Як розпізнати задачу динамічного програмування?

Насамперед варто зазначити, що найкращим критерієм «впізнавання» задач динамічного програмування є власний значний досвід у розв'язуванні таких задач. Разом з тим, можна дати й деякі поради.

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

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

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

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

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

Інвестиції у розмірі К одиниць коштів повинні бути розпо­ділені між п підприємствами. Відомо, який дохід 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. Зрозуміло, що вона буде залежати більшою мірою від розміру інвестиційних коштів. Щодо дослідження впливу прибуткої ефективності підприємств на результат розподілу коштів між ними, то можна запропонувати згенерувати такі вхідні дані:

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

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

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

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

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