Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

9.3. Задача про розподіл капіталовкладень між підприємствами

Планується на наступний рік діяльність виробничої системи, яка складається з n підприємств. Відома початкова сума коштів — , що має бути розподілена між всіма підприємствами. Сума вкладень х приносить k-му підприємству прибуток . Значення функції , задані таблицею.

Необхідно визначити — кошти, які потрібно виділити k-му підприємству так, щоб отримати максимальний сумарний прибуток від вкладення коштів в усі підприємства .

Позначимо кількість коштів, що залишилися після k-го кроку (тобто кошти, які необхідно розподілити між рештою (n – k) підприємств через :

.

Задача розв’язується поетапно. В даному разі етапами є вкладення коштів в кожне підприємство.

І етап. Кошти вкладаються лише в одне (наприклад, перше) підприємство. Найбільший прибуток (ефективність першого етапу), що може бути отриманий, позначимо через . Маємо:

.

ІІ етап. Порівняємо ефективність, яку отримаємо, вкладаючи кошти лише у перше підприємство та вкладаючи кошти одночасно і в перше, і в друге підприємства. Якщо позначити ефективність другого етапу через , то отримаємо:

.

Для k-го етапу маємо рекурентне співвідношення:

.

Послідовно розв’язуючи отримані рівняння, визначаємо оптимальні рішення на кожному етапі.

Наведемо найпростішу задачу динамічного програмування.

Виробнича система складається з чотирьох філіалів. За умови здійснення реконструкції обладнання на кожному філіалі можна досягти певного приросту прибутку. Фірма виділяє на додаткові капітальні вкладення 200 тис. ум. од. (для спрощення розрахунків допустимо, що додаткові вкладення будуть здійснені в обсягах 50, 100, 150 та 200 тис. ум. од.).

Необхідно визначити оптимальний розподіл коштів між філіалами для максимізації загального прибутку від усіх чотирьох філіалів за умови, що відомі прирости прибутку для кожного з них (табл. 9.1):

Таблиця 9.1

Капіталовкладення, тис. ум. од.	Приріст прибутку в філіалах, тис. ум. од.
	1	2	3	4
50	25	30	36	28
100	60	70	64	56
150	100	90	95	110
200	140	122	130	142

Розв’язання. В даному прикладі етапами задачі буде не час, як у попередніх викладках, а розподіл коштів між філіалами. Отже, маємо чотирьохетапну задачу динамічного програмування. Відповідно до введених раніше позначень вважатимемо, що  — приріст прибутку в і-му філіалі за умови капіталовкладень у нього обсягом х тис. ум. од. Умова задачі має вигляд (табл. 9.2):

Таблиця 9.2

Приріст прибутку в філіалах, тис. ум. од.
25	30	36	28
60	70	64	56
100	90	95	110
140	122	130	142

І етап

Найпростіший спосіб розподілу коштів, з якого починаємо розв’язування задачі, — це вкладення коштів лише у перший філіал. Якщо маємо в розпорядженні суму коштів  тис. ум. од., то ефективність вкладення цієї суми відповідає прибутку, що його буде отримано від інвестування в перший філіал — 25 тис. ум. од. Ефективність першого етапу позначимо через :

.

Аналогічно поступаємо у разі, коли в розпорядженні маємо суму  тис. ум. од. Тоді з наявних коштів вкладати можна суму величиною , що може набувати таких значень: , або , або  тис. ум. од. Очевидно, що з трьох названих можливих варіантів найбільшу ефективність будемо мати, вклавши кошти в сумі 100 тис. ум. од. Отже, фіксуємо найбільшу ефективність на другому кроці першого етапу — , потім на третьому кроці —  тис. ум. од. і т. д.

Узагальнимо всі випадки першого етапу у вигляді «таблиці найбільших ефективностей», де відображено можливі прибутки за умови різних вкладень тільки в першу філію (табл. 9.3):

Таблиця 9.3

50	25
100	60
150	100
200	140

ІІ етап

На кожному етапі необхідно зіставити ефективності прийнятих рішень на попередньому та поточному етапах. Тобто, тепер розглянемо розподіл коштів одночасно між двома філіалами фірми, порівнюючи отриманий прибуток з ефективністю попереднього етапу. Скористаємося формулою для загального випадку:

.

Для нашого прикладу величина — ефективність, що дають вкладення на попередньому етапі (в даному прикладі — в перший філіал фірми), яка була розрахована на першому кроці, і позначалась через , а величина — прибуток, що дає другий філіал від залишку суми.

За введених у даному прикладі позначень формула набуває вигляду:

Знову спочатку допускаємо, що розподіляється сума . Тоді можливі два варіанти вкладення: (вкладаємо кошти лише в другий філіал) або (вкладаємо кошти лише в перший філіал), тоді:

.

Для наочності подамо проміжні розрахунки у вигляді табл. 9.4:

Таблиця 9.4

0	50	0	30	0 + 30 = 30
50	0	25	0	25 + 0 = 25

Стрілкою позначено найбільший з можливих прибутків за умови розподілу вкладення 50 тис. ум. од. одночасно в перший та другий філіали фірми.

У такий спосіб визначено наступний елемент «таблиці найбільших ефективностей» для випадку, коли (табл. 9.5):

Таблиця 9.5

50	25	30
100	60
150	100
200	140

Потім розглядаються можливі варіанти розподілу коштів, якщо , тоді вкладати лише в другий філіал можна суму . може набувати таких значень: , ,  тис. ум. од. Маємо такі результати: (табл. 9.6):

Таблиця 9.6

0	100	0	70	0 + 70 = 70
50	50	25	30	30 + 25 = 55
100	0	60	0	60 + 0 = 60

З табл. 9.6 висновуємо, що вкладаючи 100 тис ум. од., з усіх варіантів найбільший прибуток буде дорівнювати 70 тис. ум. од. Отже, таблиця найбільших ефективностей після цього кроку поповнюється наступним елементом (табл. 9.7):

Таблиця 9.7

50	25	30
100	60	70
150	100
200	140

Аналогічно проводимо обчислення для та  тис. ум. од.

Нехай (розглядається чотири можливих варіанти розподілу, табл. 9.8):

Таблиця 9.8

0	150	0	90	0 + 90 = 90
50	100	25	70	25 + 70 = 95
100	50	60	30	60 + 30 = 90
150	0	100	0	100 + 0 = 100

Нехай (розглядається п’ять можливих варіантів розподілу, табл. 9.9):

Таблиця 9.9

0	200	0	122	0 + 122 = 122
50	150	25	90	25 + 90 = 115
100	100	60	70	70 + 60 = 130
150	50	100	30	100 + 30 = 130
200	0	140	0	140 + 0 = 140

Внесемо всі розрахунки другого етапу в таблицю максимальних ефективностей, табл. 9.10:

Таблиця 9.10

50	25	30
100	60	70
150	100	100
200	140	140

ІІІ етап

Знову необхідно зіставити ефективності попереднього та поточного етапів. Отже, використовуємо дані, що описують прибуток, який можна отримати від вкладення одразу в перший та другий філіал (стовпчик ) та прибуток від вкладення одночасно в три філіали. Знову використаємо формулу:

Аналогічно попереднім випадкам спочатку беремо , тоді або  тис. ум. од., маємо (табл. 9.11):

Таблиця 9.11

x1
0	50	0	36	0 + 36 = 36
50	0	30	0	30 + 0 = 30

.

Другий крок: , тоді може набувати таких значень: , ,  тис. ум. од. В результаті маємо (табл. 9.12):

Таблиця 9.12

0	100	0	64	0 + 64 = 64
50	50	30	36	36 + 30 = 66
100	0	70	0	70 + 0 = 70

.

При величина може набувати чотирьох значень: , , ,  тис. ум. од., які означають частини загальної суми вкладення коштів лише в третє підприємство, відповідні їм чотири випадки: — лишки коштів, що необхідно вкладати в перші два філіали. Маємо (табл. 9.13):

Таблиця 9.13

0	150	0	95	0 + 95 = 95
50	100	30	64	30 + 64 = 94
100	50	70	36	70 + 36 = 106
150	0	100	0	100 + 0 = 100

Отже, .

Обчислення для останнього (четвертого) кроку третього етапу наведені в табл. 9.14:

Таблиця 9.14

0	200	0	130	0 + 130 = 130
50	150	30	95	30 + 95 = 125
100	100	70	64	70 + 64 = 134
150	50	100	36	100 + 36 = 136
200	0	140	0	140 + 0 = 140

. Запишемо значення у вигляді наступного стовпчика таблиці найбільших ефективностей (табл. 9.15).

Таблиця 9.15

50	25	30	36
100	60	70	70
150	100	100	106
200	140	140	140

Аналогічно проводяться обчислення для , які наводяться без коментарів.

Таблиця 9.16

0	50	0	28	0 + 28 = 28
50	0	36	0	36 + 0 = 36

Таблиця 9.17

0	100	0	56	56 + 0 = 56
50	50	36	28	36 + 28 = 64
100	0	70	0	70 + 0 = 70

Таблиця 9.18

0	150	0	110	110 + 0 = 110
50	100	36	56	36 + 56 = 92
100	50	70	28	70 + 28 = 98
150	0	106	0	106 + 0 = 106

Таблиця 9.19

0	200	0	142	142 + 0 = 142
50	150	36	110	36 + 110 = 146
100	100	70	56	70 + 56 = 126
150	50	106	28	106 + 28 = 134
200	0	140	0	140 + 0 = 140

.

Остаточно маємо табл. 9.20:

Таблиця 9.20

50	25	30	36	36
100	60	70	70	70
150	100	100	106	110
200	140	140	134	146

З табл. 9.20 легко помітити, що найбільший прибуток, який дадуть всі чотири філіали за умови вкладення коштів у розмірі 200 тис. ум. од., становить 146 тис. ум. од. Повертаючись до останнього кроку розрахунків (табл. 9.19) бачимо, що число 146 відповідає змінній , .

Звідси маємо, що 150 тис. ум. од. необхідно вкласти в четвертий філіал, а 50 тис. ум. од. розподілити між трьома іншими. Знову повертаємося до елементів табл. 9.20. Використання 50 тис. ум. од. на трьох перших філіалах дає загальний прибуток обсягом 36 тис. ум. од. (виділений елемент таблиці 9.20). Це значення було розраховано на ІІІ етапі, на першому кроці: у такий спосіб (табл. 9.21):

Таблиця 9.21

0	50	0	36	0 + 36 = 36
50	0	30	0	30 + 0 = 30

Отже, маємо: , а . Це означає, що 50 тис. ум. од. виділяються третьому філіалу, , — що в перші два філіали кошти взагалі не вкладаються.

Отже, оптимальним планом задачі є: тис. ум. од.). У разі такого розподілу коштів між філіалами фірми максимальний прибуток становитиме 146 тис. ум. од.