justify"> або запис умов дискретності множин:
В
Набір обмежень, що визначають безліч D, при необхідності завжди можна звести або до системи, що складається з одних нерівностей:
В
або, додавши фіктивні змінні у, до системи рівнянь:
В
Властивості ЗНП, які істотно ускладнюють процес їх вирішення в порівнянні з завданнями лінійного програмування:
. Безліч допустимих планів D може мати дуже складну структуру (наприклад, бути неопуклого або незв'язним). p align="justify">. Глобальний максимум (мінімум) може досягатися як усередині безлічі D, так і на його кордонах (де він, взагалі кажучи, буде не збігатися ні з одним з локальних екстремумів). p align="justify">. Цільова функція f може бути недиференційованої, що ускладнює застосування класичних методів математичного аналізу. p align="justify"> У силу названих чинників задачі нелінійного програмування настільки різноманітні, що для них не існує загального методу рішення.
2. Практична частина
.1 Метод Ньютона
Метод Ньютона, алгоритм Ньютона (також відомий як метод дотичних) - це ітераційний чисельний метод знаходження кореня (нуля) заданої функції.
Щоб чисельно розв'язати рівняння f (x) = 0 методом простої ітерації, його необхідно привести до наступної форми:, де - стискуюче відображення.
Для найкращої збіжності методу в точці чергового наближення повинна виконуватися умова. Рішення даного рівняння шукають у вигляді, тоді:
В
У припущенні, що точка наближення В«досить близькаВ» до кореня, і що задана функція неперервна, остаточна формула для така:
В
З урахуванням цього функція визначається виразом:
В
Ця функція в околиці кореня здійснює стискуюче відображення, і алгоритм знаходження чисельного рішення рівняння зводиться до ітераційної процедури обчислення:
В
За теоремою Банаха послідовність наближень прагне до кореня рівняння.
В
Рис. 2. - Ілюстрація методу Ньютона (синім зображена функція f (x), нуль якої необхідно знайти, червоним - дотична в точці чергового наближення xn). br/>
Геометрична інтерпретація
Основна ідея методу полягає в наступному: задається початкове наближення поблизу предположительного кореня, після чого будується дотична до досліджуваної функції в точці наближення, для якої знаходиться перетин з віссю абсцис. Ця точка і береться в якості наступного наближення. І так далі, поки не буде досягнута необхідна точність. p> Нехай - визначена на відрізку і дифференцируемая на ньому вещественнозначная функція. Тоді формула ітеративного обчислення наближень може бути виведена наступним чином:
В
де - кут нахилу дотичної в точці xn.
Отже шуканий вираз для xn +1 має вигляд:
В
Ітераційний проц...
