Задача з лінійною цільовою функцією й нелінійною системою обмежень



Скачати 77.94 Kb.
Дата конвертації22.04.2017
Розмір77.94 Kb.
Розглянемо різні види задач НП, що розв'язуються графічним способом.

Задача з лінійною цільовою функцією й нелінійною системою обмежень

7.1. Знайти найбільше і найменше значення функції за умов





Розв'язування. Область допустимих розв'язків зображена на рис.7.1.

Для цільової функції лінією рівня є пряма , де с — стала, з кутовим коефіцієнтом . Дослідимо її поведінку при різних значеннях с. При кожному значенні с отримаємо пряму, яка віддалена від початку координат вище, чим більше значення с. Отже, цільова функція набуває максимального значення в точці А, а мінімального - в точці В, в яких лінія рівня є дотичною, відповідно, до кривих і .

Для визначення координат точки А скористаємось рівністю кутових коефіцієнтів лінії рівня і кола . Розглядаючи як неявну функцію змінної почленно диференціюємо рівняння кола і отримуємо



Рисунок 7.1


Прирівнюючи знайдене значення виразу до числа , дістанемо одне з рівнянь для визначення координат точки А. За друге рівняння системи візьмемо рівняння кола. Маємо систему рівнянь:

Звідси . Отже, координати точки і максимальне значення

Аналогічно знайдемо координати точки В з системи рівнянь, де одне з рівнянь - це рівність кутових коефіцієнтів лінії рівня гіперболи , а друге рівняння - це рівняння гіперболи:

Звідси . Отже, координати точки і мінімальне значення



Задача з нелінійною цільовою функцією й лінійною системою обмежень

7.2. Знайти найбільше і найменше значення функції





Рисунок 7.2


Розв'язування. Область допустимих розв'язків - ОАВСD (рис.7.2).

Для квадратичної цільової функції , лінією рівня будуть концентричні еліпси: з центром у точці М(3,5; 4). Із збільшенням (зменшенням) числа с значення функції , відповідно збільшується (зменшується). З рис.8.4 бачимо, що мінімальне значення цільової функції досягається у точці Е, яка є точкою дотику прямої ВС до еліпса, а максимальне значення у початку координат. Звідси .

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

Звідси . Отже, координати точки Е(2,5;3,5) і мінімальне значення .



Задача з нелінійною цільовою функцією й нелінійною системою обмежень

7.3. Знайти найбільше і найменше значення функції за умов





Розв'язування. На відміну від наведених вище задач, область допустимих розв'язків задачі не є опуклою і складається з двох частий ABCD і KLMN. Лінії рівня цільової функції - концентричні кола , з центром у початку координат.

Рисунок 7.3


Збільшуючи значення с радіуса бачимо з рис.7.3, що мінімальне значення цільової функції досягається у точках А(1; 4) та L(4;1) і Zmin =17. З рис.7.3 видно, що цільова функція має два локальних максимуми в точках D і М. Знайдемо координати цих точок із системи рівнянь:

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



7.3. Класичний метод оптимізації. Метод множників Лагранжа

7.4. Знайти оптимальне значення функції





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

- критична точка.

Знайдемо частинні похідні другого порядку функції і запишемо матрицю Гессе:



Оскільки , то Х0 = (-1;1) –точка локального мінімуму. Найменше значення функції дорівнює Zmin=0.



Метод множників Лагранжа

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



(7.6) (7.7)

в якій двічі неперервно диференційовані функції.

У курсі математичного аналізу задачу (7.6)-(7.7) називають задачею на умовний екстремум або класичною задачею оптимізації, Умова (7.7) називається рівнянням зв'язку.

Для визначення оптимальних точок цієї задачі, введемо набір змінних , які називаються множниками Лагранжа, і побудуємо функцію Лагранжа



(7.8)

Відшукання умовного екстремуму задачі зводиться до знаходження безумовного екстремуму функції Лагранжа (7.8). Розглянемо систему рівнянь, які складаються з частинних похідних



(7.9)

з (п + т) невідомими . Розв'язок системи (7.9) визначає точку , яка є підозрілою на екстремум функції . Характер оптимальності з'ясовують аналогічно, як і у випадку безумовного екстремуму.



Алгоритм методу множників Лагранжа

1. Складаємо функцію Лагранжа.

2. Знаходимо частинні похідні функції Лагранжа за змінними і прирівнюємо їх до нуля.

3. Розв'язуючи систему рівнянь (9.27), знаходимо точки, в яких цільова функція може мати екстремум.

4. Серед підозрілих точок на екстремум виділяють такі, в яких досягається екстремум, і обчислюємо значення функції (9.24) у цих точках.

7.5. Знайти умовний екстремум функції





Розв'язування. Складемо функцію Лагранжа

Знайдемо її частинні похідні за всіма змінними та прирівняємо їх до нуля



З першого і другого рівняння виразимо змінні через і підставимо у третє і четверте рівняння системи. Таким чином, у точці функція має умовний екстремум.

Обчислимо частинні похідні другого порядку і запишемо матрицю Гессе:

Зважаючи, що то точка Х0(-16;12) є точкою мінімуму.



7.4 Необхідні умови існування сідлової точки


Для розроблення методів розв’язування окремих типів задач нелінійного програмування важливе значення має поняття сідлової точки, а також визначення необхідних і достатніх умов існування сідлових точок функції Лагранжа у (n+m)-вимірному просторі змінних за довільних умов, які можуть накладатися на їх знаки (необхідні і достатні умови існування сідлової точки функції Лагранжа за відсутності обмежень на знаки змінних розглянуто в п.9.4).

Розглянемо нелінійну задачу:



,

.

Причому на компоненти векторів накладено обмеження на знаки. Позначимо множину точок, що задовольняють такі обмеження, через .

Функція Лагранжа для цієї задачі має вигляд:

=. (7.10)

Точка називається сідловою точкою функції Лагранжа (9.12), якщо для всіх виконується співвідношення:



. (7.11)

Для диференційовних функцій та знайдемо необхідні умови існування сідлової точки.

Сідлова точка функції виду (7.11) за означенням задовольняє умову:

.

Нерівність виконується для всіх точок Х, тобто також і для тих, у яких лише одна координата відрізняється від Х*. Допустимо, що це хk, а всі інші збігаються з координатами сідлової точки .

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

Розглянемо спочатку випадок, коли , тобто лише частину координатної площини, для якої .

Можливі такі випадки:

1) коли всі , то максимальне значення функції L(xk) досягатиметься в точці, для якої (рис.7.5).



Рисунок 7.5


2) коли максимум функції L(xk) досягатиметься в точці і розглядувана частинна похідна також дорівнюватиме нулю: (рис.7.6).

Рисунок 7.6


3) коли точка максимуму функції L(xk) досягатиметься також у точці
, а частинна похідна (рис.7.7).

Рисунок 7.7


Узагальнюючи всі три ситуації, маємо:

для

та

.

Розглядаючи другу частину нерівності (7.11):

аналогічними міркуваннями, що проілюстровані рис.7.8-7.9, встановлюються необхідні умови для похідних по функції Лагранжа в сідловій точці.



Рисунок 7.8 Рисунок 7.9


Об’єднуючи всі три випадки для невід’ємних координат, маємо необхідні умови сідлової точки:

для тих індексів j, де . (7.12)

Зауважимо, що для маємо ті самі випадки, які зображено на рис.7.5-7.9, причому графіки будуть симетрично відоб­ражені відносно осі Оy, тобто для недодатних координат необхідна умова має вигляд:



для тих індексів j, де . (7.13)

І нарешті, як відомо з попереднього параграфа, якщо на знак хj умови не накладаються, то необхідною умовою є:



, – довільного знака. (7.14)

Узагальнення всіх випадків приводить до рівняння:



. (7.15)

Розглядаючи другу частину нерівності (7.11), за допомогою аналогічних міркувань встановлюємо необхідні умови для похідних по функції Лагранжа в сідловій точці:



для тих індексів і, де , (7.16)

для тих індексів і, де , (7.17)

для тих індексів і, де має довільний знак. (7.18)



Отже, справджується рівняння:

. (7.19)

Сукупність співвідношень (7.12)-(7.19) становить необхідні умови, які має задовольняти сідлова точка функції Лагранжа для точок, що належать множині . При цьому повинна мати частинні похідні по всіх компонентах векторів .


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка