Задача дробово-лінійного програмування. Математична модель задачі дробово-лінійного програмування

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

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

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

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

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

а загальні витрата на їх виробництво будуть рівні:

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

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

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

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

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

Отже, у загальній постановці задача дробово-лінійного програмування записується наступним чином: знайти мінімальне чи максимальне значення функції мети:

при наступних обмеженнях:

Додатково, до заданої системи обмежень вважається, що .

Як і в разі задачі лінійного програмування, свого максимального значення функція мети (1) досягає в одній з вершин опуклого багатокутника, що визначається системою обмежень (2) і (3) (природно, за умови, що задача має розв'язок). Якщо ж функція мети приймає свого екстремального значення більш, ніж в одній вершині, то вона досягає це значення в будь-якій точці, що є опуклою лінійною комбінацією даних вершин. Відмітимо, що детально ці властивості в даному матеріалі розглядати не будемо, вони будуть добре проілюстровані при розгляді геометричного способу рішення задач дробово-лінійного програмування, а перейдемо до розгляду конкретної задачі такого типу та побудови її математичної моделі.

Задача дробово-лінійного програмування — приклад:

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

Витрати часу на виготовлення пального

Витрати часу на виготовлення пального

Обладнання першого та третього типів підприємство може використовуват не більш як 26 та 39 годин. А обладнання другого типу доцільно використовуват не менш ніж 4 години. Потрібно визначити, скільки тонн кожного різновиду пального потрібно виготовити підприємству, щоб собівартість тонни пального булу мінімальною.

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

Далі, запишемо обмеження на час використання обладнання. Отже, виходячи з того, що витрати часу на виготовлення зазначеної кількості тонн пального на кожному з типів обладнання відповідно складає , та годин, а обладнання першого і третього типів може бути зайнято виготовленням пального типу  і  не більше ніж 26 і 39 годин відповідно, а обладнання другого типу — не менше 4 години, то повинні виконуватися наступні нерівності:

І на останньому кроці, записавши обмеження для змінних  та , які з економічної точки зору, можуть приймати тількі додатні значення, тобто:

отримаємо повноцінну математичну модель заданої задачі.

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар