4. Задача про оптимальне використання ресурсу

Розглянемо наступну задачу дискретного програмування:

,

при обмеженнях ,

,

де і додатні цілі числа, функції – невід’ємні і приймають цілі значення, причому ; – довільні функції, такі, що .

Дана задача називається задачею про оптимальне використання ресурсу (ЗОВР).

4.1 Змістовна інтерпретація задачі про оптимальне використання ресурсу

4.1.1 Нехай маємо деяке підприємство, що випускає n видів продуктів і використовує для цього один ресурс.

Нехай - об’єм виробництва продукту . При виробництві одиниць j-го продукту ресурс споживається в кількості , а прибуток становить одиниць. Об'єми випуску продукції обмежені величинами . Визначити ассортимент випуску продукції, при якому сумарний прибуток максимальний і витрачається не більше одиниць ресурсу.

Відзначимо, що класична задача про рюкзак (ранець) є частковим випадком ЗОВР.

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

4.2 Побудова рекурентного співвідношення задачі 4.1.1

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

на першому кроці виробляється продукт 1,

на другому – продукт 2 , …,

на -му – продукт .

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

Позначимо через – максимальний прибуток, який можна отримати шляхом розподілу одиниць ресурсу на виробництво продуктів з номерами від 1 до включно. Будемо говорити, що виробництво одиниць -го продукту допустимо, якщо при цьому буде потрібно ресурсу не більше :

і при цьому , - ціле.

Якщо - вироблена кількість продукту , то ресурсу для цього використано і на виробництво продуктів пішло одиниць ресурсу. Тоді

(3)

є максимальним прибутком, який можна отримати від розподілу одиниць ресурсу на виробництво продуктів з номерами від 1 до включно за умови, що на кроці вироблено одиниць продукту .

Ресурс, використаний на виробництво продуктів , за визначенням функції , розподілений оптимально, тому сума (3) - це умовно максимальний прибуток.

Максимізуємо вираз (3) по допустимих значеннях

(4)

Вираз (4) справедливий і при , якщо покласти

Мета задачі – знайти .

4.3 Побудова рекурентного співвідношення задачі 4.1.2

У даному випадку в якості ресурсу, що розподіляється, виступають кошти, що вкладаються в модернізацію. При такій змістовній інтерпретації задачу називають задачею про оптимальне використання капіталовкладень (ЗОВК).

Задачу можна звести до багатокрокового процесу прийняття рішень, якщо припустити, що підприємства мають бути модернізовані одне за одним, тобто на першому кроці модернізується підприємство 1, на другому – підприємство 2 , …, на -му – підприємство .

Нехай модернізовані підприємства від 1-го до -го включно і на це використані кошти в розмірі . Дана ситуація описується за допомогою пари . Оскільки кошти споживаються цілими частинами, то є цілим числом і .

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

Якщо для модернізації підприємства обрано проект , то для цього потрібно витратити кошти в розмірі .

Тоді

(5)

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

Кошти, використані на модернізацію підприємств , за визначенням функції , розподілені оптимально, тому сума (5) – це умовно максимальний прибуток.

Максимізуємо вираз (5) по допустимих значеннях :

(6)

Вираз (6) справедливий і при , якщо покласти

Мета задачі – знайти .