Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Графічний метод розв’язування задач нелінійного програмування

ЛЕКЦІЯ № 11. Постановка задачі нелінійного програмування. Графічний метод розв’язування задач нелінійного програмування. Метод множників Лагранжа. Опуклі та вгнуті функції. Теорема Куна-Такера

Означення 11.1. Задача знаходження екстремуму функції

 

(11.1)

 

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

 

(11.2)

 

називається загальною задачею математичного програмування.

Зауваження. Якщо функції є лінійними, тобто

 

;

,

 

то за умови невід’ємності розв’язку задача (11.1)–(11.2) перетворюється на задачу лінійного програмування.

Означення 11.2. Будь-яку задачу математичного програмування, яка не задовольняє умову лінійності називатимемо задачею нелінійного програмування (ЗНП).

 

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

Якщо в задачах лінійного програмування точки екстремуму є вершинами многогранників розв'язків, то в задачах з нелінійною цільовою функцією вони можуть лежати всередині області, на ребрі (грані) або у вершині многогранника. Ще більші труднощі виникають при розв'язуванні задач з нелінійними обмеженнями.

Для ЗНП універсального методу їх розв'язування не існує. Тому при розв'язуванні ЗНП доводиться застосовувати різні методи та обчислювальні алгоритми, які ґрунтуються, здебільшого, на теорії диференціального числення, і вибір яких залежить від конкретної постановки задачі та форми економіко-математичної моделі.

Методи нелінійного програмування бувають прямі та непрямі. Прямими методами оптимальні розв'язки шукають у напрямку найшвидшого збільшення (зменшення) цільової функції. Типовими для цієї групи методів є градієнтні. Непрямі методи полягають у зведенні задачі до такої, знаходження оптимуму якої вдається спростити. До них належать, насамперед, найбільш розроблені методи квадратичного та сепарабельного програмування.

Оптимізаційні задачі, на змінні яких не накладаються обмеження, розв'язують методами класичної математики. Оптимізацію з обмеженнями-рівностями виконують методами зведеного градієнта, зокрема, методом Якобі та множників Лагранжа. У задачах оптимізації з обмеженнями-нерівностями досліджують необхідні та достатні умови існування екстремуму Куна-Такера.

 

Графічний метод розв’язування задач нелінійного програмування

 

Одним із найпростіших типів ЗНП є ЗНП з двома змінними. Такі задачі мають вигляд:

(11.3)

(11.4)

(11.5)

Для їх розв'язання можна застосувати графічний метод:

 

1. Будується ОДР, що визначається обмеженнями (11.4)–(11.5).

 

2. Будуються лінії рівня, що визначаються цільовою функцією (11.3).

 

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

 

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

 

Розглянемо приклади розв'язування задач нелінійного програмування з двома змінними на основі використання графічного методу.

 

Приклад 11.1. Розв’язати ЗНП:

 

 

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

Якщо покласти ( ), то одержимо, що цільова функція визначає геометричне місце точок, яким є коло . Із зменшенням (збільшенням) (квадрата радіуса) значення функції відповідно зменшуються (збільшуються).

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

Далі встановлюються координати вказаних точок і значення цільової функції у них. Очевидно, що А(1;0), D(6; 0).

Значення цільової функції у цих точках дорівнюють , . Для визначення координат точки Н необхідно розв’язати систему рівнянь:

 

, .

Знайдена точка Н є точкою мінімуму.




Переглядів: 6330

<== попередня сторінка | наступна сторінка ==>
Загальні положення | Метод множників Лагранжа. Умовні екстремуми функцій кількох змінних

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.006 сек.