Головна |
Завдання нелінійного програмування - великий клас різноманітних завдань, з яких будемо розглядати тільки зводяться до завдань лінійного програмування.
Раніше в задачах лінійного програмування можна було отримати, що собівартість, ціна та ін. Показники ефективності на од. продукції не залежать від зміни обсягу виробництва. Однак в загальному випадку залежності між змінними в обмеженнях і цільової функції не можуть бути лінійними. Наприклад, собівартість одиниці продукції знижується при збільшенні обсягу виробництва.
Завдання, в яких залежності між змінними в цільової функції і / або в обмеженнях нелінійні, називають завданнями нелінійного програмування.
Якщо позначити цільову функцію та обмеження через узагальнену функцію h(xj), То все різноманіття завдань нелінійного програмування можна звести до класифікації (табл. 7.1).
У загальному вигляді задача НЛП полягає у визначенні максимуму (мінімуму) функції
f(x1, x2, ..., xn) (1)
за умови, що її змінні задовольняють умовам
де f и gi деякі відомі функції n змінних; bi - Задані числа.
Тут мається на увазі, що в результаті рішення задачі буде визначена точка x0 = (x10, x20, ..., xn0), Координати якої задовольняють співвідношенням (2), і така, що для будь-якої іншої точки x = (x1, x2, ..., xn), Що задовольняє умовам (2), виконується нерівність
f (x10, x20, ..., xn0) ? f (x1, x2, ..., xn) при max цільової функції або
f (x10, x20, ..., xn0) ? f (x1, x2, ..., xn) - При min цільової функції.
якщо f и gi - Лінійні функції, то завдання (1), (2) - завдання лінійного програмування.
Співвідношення (2) утворюють систему обмежень і включають умови невід'ємності змінних, якщо такі є. Умови невід'ємності змінних можуть бути задані і безпосередньо.
Нелінійні задачі вирішуються за допомогою методу кусково-лінійної апроксимації або методу множників Лагранжа. У завданнях квадратичного програмування застосовується метод Била, Баранкіна-Дорфман, градієнтні методи (метод Франка-Вулфа, штрафних функцій, метод можливих напрямків). В градієнтних методах ітераційний процес здійснюється до того моменту, поки градієнт функції f(x) В черговій крапці xk + 1 не стане рівним нулю або поки |f(xk + 1) -f(xk) | ? e (досить мале позитивне число, що характеризує точність отриманого рішення).
Таблиця 6.1
Відрізок, що з'єднує дві точки | вид функції | число оптимумів | Графік | |
збігається | лінійна | |||
вишевершіни | > 0 | опукла вниз | ||
ніжевершіни | <0 | опукла вгору (увігнута вниз) | ||
по обидві сторони від вершини | змінює знак | змішана | кілька |
Крок 3. Пошук мінімального набору рядків і стовпців, що містять нулі. | Метод множників Лагранжа
приклад 7 | блочне програмування | Елементи теорії графів | приклад 1 | транспортна задача | приклад 2 | Оптимізація мережевого графіка | Задача про найкоротший шлях | Завдання про призначення | приклад 1 |