Приклади задач лінійного програмування.

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

1. Задача планування виробництва. Для виробництва певних то­варів використовується деяке число різного роду ресурсів (сиро­вина, знаряддя, праця тощо). Відомо, скільки одиниць кожного ресурсу використовується для виробництва одиниці кожного то­вару, запас кожного ресурсу, а також прибуток від реалізації оди­ниці кожного товару.

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

Складемо математичну модель задачі.

Нехай

- число ресурсів, що використовуються у виробництві;

- число товарів, що можуть вироблятись з наявних ре­сурсів;

- кількість одиниць - го ресурсу, що використовується для виробництва одиниці -го товару;

максимальна кількість одиниць - го ресурсу, що можна використати у виробництві (запас одиниць - го ресурсу);

- прибуток від реалізації одиниці -го товару;

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

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

Оскільки ця кількість одиниць не може перевершувати запас - го ресурсу, то

Очевидно,

Прибуток, одержаний від виробництва одиниць - го товару, становить , а загальний прибуток від виробництва

Таким чином, математична модель задачі є такою:

за умов

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

Ця задача має назву загальної задачі розподілу ресурсів. Кількість одиниць - го ресурсу, виділених на виконання робіт -го виду, позначи­мо через .

Математична модель розглядуваної задачі така:

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

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

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

.

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

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

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

Математична модель цієї задачі має такий вигляд:

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

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