Аналіз чутливості використання методу Якобі для рішення задач лінійного програмування (стр. 1 из 4)

ЗМІСТ

УВЕДЕННЯ

1. ЗАГАЛЬНІ ЗВЕДЕННЯ ПРО КЛАСИЧНУ ТЕОРІЮ ОПТИМІЗАЦІЇ

1.1. Екстремальні задачі без обмежень

1.2. Необхідні і достатні умови існування єкстремума

1.3. Екстремальні задачі при наявності обмежень у виді рівності

2.АНАЛІЗ ЧУТЛИВОСТІ ЗА ДОПОМОГОЮ МЕТОДУ ЯКОБІ

2.1. Метод Якобі

2.2. Метод Лагранжа

3. ВИКОРИСТАННЯ МЕТОДУ ЯКОБІ ДЛЯ РІШЕННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

4. АЛГОРИТМ РІШЕННЯ ЕКСТРЕМАЛЬНИХ ЗАДАЧ МЕТОДОМ ЯКОБІ

5. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

5.1. Постановка задачі

5.2. Рішення задачі

УВЕДЕННЯ

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

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

Метод Якобі являє собою узагальнення симплекса-методу лінійного програмування. Дійсно, усі процедури, зв'язані з реалізацією симплекса-методу, можна обґрунтувати, користаючись методом Якобі. Метод Якобі може бути використаний для дослідження чутливості оптимального значення f до змін у правих частинах обмежень. Дослідження такого роду звуться аналізу чутливості; вони мають визначену подібність з відповідними процедурами в лінійному програмуванні. Однак, слід зазначити, що результати, отримані при аналізі чутливості в лінійному програмуванні, справедливі лише для малої околиці екстремальної крапки й обумовлені можливістю локальної лінеаризації.

Можна зробити трохи загальних висновків зі схеми застосування методу Якобі до рішення задач лінійного програмування. Розглянуті вище приклади показують, що необхідні умови наявності єкстремуми приводять до рівності нулю незалежних перемінни Достатні умови вказують на диагональність матриці Гессе. Таким чином, усі діагональні єкстенти цієї матриці повинні бути позитивними у випадку наявності мінімуму і негативними у випадку наявності максимуму.

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

Достатня умова приводить до висновку про можливу наявність точної відповідності між діагональними елементами матриці Гессе і двоїстими оцінками, отриманими за допомогою симплекса-методу.

1.ЗАГАЛЬНІ ЗВЕДЕННЯ ПРО КЛАСИЧНУ ТЕОРІЮ

ОПТИМІЗАЦІЇ

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

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

1.1.Екстремальні задачі без обмежень

Екстремальна крапка функції

визначає або максимум, або мінімум цієї функції. Крапка X₀=(x₁,…,x_j,…,x_n)є крапкою максимуму, якщо нерівність

(X₀=h)<

виконується для всіх h=(h₁,…,h_j,…,h_n)таких, що |hj| досить мало для всіх j. Іншими словами, X₀ є крапкою максимуму, якщо значення функції в кожній крапці досить малої околиці X₀ не перевищує (X₀). Аналогічно X₀ є крапкою мінімуму, якщо для вектора h, визначеного вище, справедлива нерівність

На мал. I показані максимуми і мінімуми функції одному перемінної

(x) на відрізку /a, b/. (Умова a<x<b не означає, що на (x) накладені обмеження.) Крапки x₁, x₂, x₃, x₄ і x₆ визначають єкстремуми (x), причому x₁, x₃ і x₆— максимуми, a x₂ і x₄— мінімуми. Тому що

те

являє собою глобальний, чи абсолютний, максимум, а і є локальними, чи відносними, максимумами. Аналогічно є локальний мінімум, — глобальний мінімум.

Максимум у крапці x₁ відрізняється від інших локальних максимумів тим, що значення функції принаймні в одній крапці околиці x₁ дорівнює

. З цієї причини x₁ називають крапкою нестрогого максимуму у відмінність, наприклад, від крапки x₃, що визначає строгий максимум . Під нестрогим максимумом, таким чином, розуміється наявність (нескінченної кількості) незбіжних крапок, яким відповідає те саме максимальне значення функції. У крапці x₄ спостерігається нестрогий мінімум, що визначається аналогічним образом. Узагалі говорячи, X₀ є крапкою нестрогого максимуму, якщо (X₀=h)< , і крапкою строгого максимуму, якщо (X₀=h)< , де h — вектор, визначення якого дано вище.

За допомогою мал. 1 неважко помітити, що перша похідна (тангенс кута нахилу дотичної до графіка) функції

прагне до нуля в міру наближення до екстремальних крапок. Однак це характерно не тільки для єкстремумів. Наприклад, тангенс кута нахилу дотичної до графіка в крапці x₅ також дорівнює нулю.

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

1.2. Необхідні і достатні умови існування єкстремумів

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

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

Теорема I. Якщо крапка Х₀є екстремальною крапкою функції

, то

З теореми 1 випливає, що умова

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

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

будемо називати стаціонарними. Наступна теорема встановлює достатні умови для того, щоб Х₀ була екстремальною крапкою.

Теорема 2. стаціонарна крапкаХ₀ є екстремальною, коли матриця Гессе Н^В крапціХ₀ виявляється (1) позитивно визначеною(тодіХ₀– крапка мінімуму); (2) негативно визначеною (тодіХ₀– крапка максимуму)