5. Нелінійне програмування

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

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

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

,

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

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

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

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

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

,

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

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

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

(5.1)

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

(5.2)

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

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

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

,

, де .

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

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

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

.

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

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

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

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

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

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

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

,

при умові

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

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

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

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