Головна

Класифікація і загальна постановка задач нелінійного програмування

  1.  Amp; завдання 7.1
  2.  Amp; Завдання 9.2 Визначення категорії приміщення цехуфарбування
  3.  Amp; 31. Види режимів майна подружжя та їх загальна характеристика.
  4.  ATP У XXI СТОЛІТТІ: Загальна характеристика ракурсі РЕГІОНАЛЬНОГО КОНФЛІКТУ
  5.  CТРОЕНІЕ атома. МЕТОДИКА РІШЕННЯ ТИПОВИХ ЗАВДАНЬ
  6.  D) РЕКОНСТРУКЦІЯ ТА ІНТЕГРАЦІЯ ЯК ЗАВДАННЯ герменевтики
  7.  D. До завдань соціальної комунікації не відноситься

Завдання нелінійного програмування - великий клас різноманітних завдань, з яких будемо розглядати тільки зводяться до завдань лінійного програмування.

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

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

Якщо позначити цільову функцію та обмеження через узагальнену функцію 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 |

© 2016-2022  um.co.ua - учбові матеріали та реферати