Дробово-лінійне програмування

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

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

,

де постійні коефіцієнти і .

 

Графічний метод

Розглянемо задачу дробово-лінійного програмування у вигляді

 

(5.1)

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

(5.2)

Будемо вважати, що

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

Із виразу (5.1) знайдемо :

,

, де .

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

Графічна інтерпретація моделі дробово-лінійного програмування

 

Встановимо, як буде себе вести кутовий коефіцієнт при монотонному зростанні . Знайдемо похідну від по .

 

.

 

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

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

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

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

4. Область припустимих розв’язків необмежена. Максимум і мінімум є асимптотичними

 

Зведення задачі до симплексного методу

Задачу дробово-лінійного програмування можна звести до задачі лінійного програмування і розв’язати симплексним методом. Для цього позначимо

,

при умові

 

і введемо нові змінні .

Тоді задача набуде вигляду

 

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

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