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

Загальна постановка задачі

НЕЛІНІЙНЕ ПРОГРАМУВАННЯ

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

і має екстремум цільової функції

,

де - змінні, ; - задані функції від п змінних, - фіксовані значення (вільні члени).

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

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

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

,

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

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

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

(5.1)

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

(5.2)

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

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

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

,

, де .

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

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

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

.

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

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

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

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

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

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

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

,

при умові

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

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

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

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

Дата добавления: 2015-05-23