4.5. Задача розподілу ресурсів (задача 2)

Умова задачі

На реконструкцію і модернізацію основного виробництва об’єднанню виділяється деякий обсяг матеріального ресурсу Х₀. Маємо n підприємств, між якими потрібно розподілити даний ресурс. Позначимо через прибуток i-го підприємства при виділенні йому одиниць ресурсу. Передбачається, що розмір прибутку залежить від виділеної кількості ресурсу і від підприємства.

Потрібно так розподілити ресурс між n підприємствами, щоб об'єднання дістало максимальний прибуток.

Допущення при розрахунку:

1. Прибуток кожного підприємства вимірюється в тих самих одиницях;

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

3. Загальний прибуток об’єднання дорівнює сумі прибутків усіх підприємств;

4. Обсяг виділеного ресурсу X може змінюватися від нуля до X₀.

Розробка математичної моделі задачі

Максимальний прибуток об’єднання залежить від кількості підприємств та обсягу виділеного їм матеріального ресурсу.

= (4.1)

Задача оптимального розподілу виникає через те, що обсяг матеріального ресурсу X обмежений

, 0  X  X₀ (4.2)

Граничні умови (4.3)

Тоді задачу розподілу ресурсу можна сформулювати в такий спосіб: визначити такі невід’ємні значення параметрів x_i (4.3), що забезпечують максимальний прибуток об’єднанню (4.1) з урахуванням обмеження на обсяги ресурсу (4.2).

Тут функції (4.1) і (4.2) залежать від n змінних, тобто задача багатовимірна. При розв’язуванні задач методом динамічного програмування багатовимірна задача зводиться до рішення n одномірних задач, у яких функціональні рівняння залежать від однієї змінної. Розглянемо методику перетворення багатовимірної задачі в n одновимірних.

Будемо розглядати максимальний прибуток об’єднання як функцію, що залежить від кількості підприємств і виділеного йому обсягу ресурсу, тобто

(4.4)

у припущенні, що виконується обмеження (4.2). Тоді вираження (4.4) можна записати у виді

(4.5)

Вираз (4.5) являє собою математичну модель оптимізації у формі Беллмана, тобто в одному записі відбивається і цільова функція, й обмеження.

Для об’єднання, що складає з одного першого підприємства, рівняння (4.5) набуде вигляду

(4.6)

Отже, під час розв’язування задачі методом динамічного програмування необхідно багатовимірну задачу (4.5) для визначення прибутку об’єднання, що складається з 1, 2, …, n підприємств, подати у вигляді послідовності функціональних рівнянь, у яких була б тільки одна змінна х_і, як у формулі (4.6). Розглянемо методику одержання таких залежностей.

Запишемо прибуток об’єднання, що має два підприємства:

(4.7)

де – прибуток об'єднання, що має одне підприємство; - прибуток другого підприємства при виділенні йому ресурсу в обсязі х₂, тобто в об’єднання з двох підприємств окремим блоком входить об’єднання з одного підприємства, прибуток якого можна визначити заздалегідь за виразом (4.6). Отже, потрібно визначити змінні х₁, х₂, що забезпечують максимальний прибуток об’єднанню.

Це виражається записом виду

(4.8)

де , тобто прийшли до рівняння з однією змінною і виконуємо оптимізацію за :

(4.9)

Одержуємо математичну модель прибутку об’єднання, що має три підприємства. Будуємо прибуток об’єднання за аналогією

Подамо у вигляді функції

Тоді Знову маємо функцію однієї змінної і виконуємо оптимізацію за :

(4.10)

Таким чином, для об’єднання з підприємств при = маємо такі рекурентні формули:

;

;

; (4.11)

……………………………………......

.

Це математична модель, побудова якої починається з першого підприємства. У цьому випадку спочатку вибирають перше підприємство, а потім до нього підбирають інші підприємства. Часто роблять і навпаки, тобто в об’єднання на першому кроці включають останнє підприємство. У цьому випадку розрахункові формули мають вигляд:

;

; (4.12)

……………………………………………..

.

Обчислювальна схема розв’язання задачі розподілу ресурсу методом динамічного програмування полягає в такому. Оскільки під час розв’язування функціональних рівнянь (4.11) або (4.12) неможливо визначити всі значення прибутку для кожного підприємства при 0  Х  Х₀, то проміжок [0, Х₀] розбивають на m інтервалів із кроком h і вважають, що функції та визначені тільки в точках X=0, h, 2h, 3h,…, причому mh=X₀ . Значення для інших X одержують інтерполяцією. Якщо розв’язування ведеться за формулами (4.11), то функція визначається рівністю = . Безліч значень записують у таблицю. Знаючи значення , переходять до обчислення значень функцій відповідно до виразу (4.9)

,

потім обчислюються значення і т. д. На останньому етапі досягається максимальне значення прибутку об’єднання, що має n підприємств.

Приклад 1. Об’єднання має чотири підприємства, між якими потрібно розподілити 400 одиниць обмеженого ресурсу. Одержуваний підприємствами прибуток залежно від виділеного обсягу ресурсу X подано в табл. 4.6. Як видно з табл. 4.6 крок зміни ресурсу h=80. Визначити план розподілу ресурсу між підприємствами, що забезпечує максимальний прибуток об’єднанню.

Таблиця 4.6

Вихідні дані

Виділений обсяг ресурсу
0 80 160 240 320 400	0 30 57 120 150 180	0 28 62 122 146 175	0 35 67 130 144 180	0 27 73 125 152 178

Примітка. Дослідження показують, що функції такі,як , як правило, мають вигляд, наведений на рис 4.6. Ця крива має такі особливості:

1. Невелика кількість виділеного ресурсу не приносить відчутного ефекту;

2. Для кожного підприємства є точка, починаючи з якої подальше збільшення йому даного ресурсу не ефективне.

Р ис.4.6. Залежність прибутку від виділеного ресурсу

Розв’язання. Розрахунок ведемо по формулах (4.11) і результати поміщаємо в табл. 4.7.

(4.13)

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

Прибуток об’єднання, що має два підприємства (перших і друге), розраховуємо за формулами (4.13) і (4.14).

, (4.14)

Таблиця 4.7