Главная | Обратная связь | Поможем написать вашу работу!

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

Цей метод є класичним методом знаходження екстремуму функції кількох змінних у задачах нелінійного типу.

Основні вимоги до математичної моделі, які можна розв’язувати методом множників Лагранжа:

1) цільова функція та обмеження мають бути неперервні і диференційовні і повинні мати часткові похідні принаймні другого порядку;

2) обмеження повинні бути у вигляді строгих рівнянь;

3) відсутність вимог невід’ємності та цілочисловості змінних.

Загальний вигляд математичної моделі такої задачі такий:

– цільова функція

– обмеження

Залежності складових моделі можливі як лінійні, так і нелінійні.

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

де - множник Лагранжа, а

Згідно з цим складається система рівнянь

кількість яких дорівнює .

Приклад. Нехай задана математична модель

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

а потім рівняння

Розв’язуємо систему цих рівнянь і одержуемо

Градієнтні методи

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

Градієнт функції

а похідна за напрямком має вид

де – одиничний вектор за напрямком пошуку.

Рух до точки оптимуму відображується „градієнтною” траєкторією за напрямком променя

де – довжина кроку пошуку; – скаляр градієнта функції .

Градієнтними методами вдається розв’язувати значний клас задач нелінійного програмування, які мають опуклий характер; при цьому використовують умову

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

Градієнтні методи використовуються з постійним або змінним кроком пошуку.

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

де – задана точність розв’язування задачі, тобто радіус околу точки оптимуму (рис. 9.5).

F ₃

F ₂ F ₁

A M ₃ M ₂ M ₁

Рис. 9.5

Градієнтний метод зі змінним кроком передбачає корегування величини кроку переходу з однієї поверхні рівня до другої у процесі пошуку оптимуму. Це особливо важливо у задачах, які мають оптимум на межі області допустимих розв’язків. Поширеним методом цього типу розв’язування є метод крутого сходу (метод найскорішого спуску, метод Бокса-Уілсона). Ця модифікація припускає корегування напрямку пошуку не після кожного кроку, а при досягненні деякого часткового оптимуму, аналогічно методу Гаусса-Зейделя.

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

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

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

Задача без обмежень. Якщо у задачі відсутні обмеження, то з будь-якої початкової точки області допустимих розв’язків виконується перехід до точки оптимуму за напрямком променя

де значення знаходиться з умови

Процес розв’язування продовжується до виконання у точні умови .

Алгоритм розв’язування такої задачі наступний:

1) знаходження часткових похідних

2) обчислення скаляра

3) складання у загальному вигляді координат наступної точки

;

4) знаходження величини з умови

5) знаходження координат наступної точки ;

6) перевірка умови якщо умова виконується, то знайдено оптимальний варіант, у противному разі виконується перехід від -ї точки до -ї аналогічно пп. 2-5.

Розглянемо приклад розв’язування.

Задана цільова функція

та початкова точка пошуку . Знайти оптимальний розв’язок задачі.

Розв’язування наведено згідно з розглянутим алгоритмом:

5) звідси

Відповідь:

Розглянемо клас задач, в яких необхідні умови Куна-Таккера є достатні для знаходження точок екстремуму. У таких задачах цільова функція та область допустимих розв’язків повинні відображуватись визначними властивостями, які пов’язані з опуклістю та увігнутістю. До таких задач відносять, наприклад, задачі квадратичного програмування.

Задача з обмеженнями. Розглянемо таку математичну, модель:

цільова функція

яка має властивості опуклості;

обмеження лінійного типу

Згідно з тим, що цільова функція та обмеження опуклі, оптимальний розв’язок задачі знаходиться усередині або на межі області допустимих розв’язків. Геометрично процес пошуку у загальному вигляді можна відобразити так: з початкової точки, яка знаходиться усередині області допустимих розв’язків, здійснюється перехід згідно з напрямком градієнта до найближчої межі області, а потім, якщо це необхідно, виконується перехід по межі або паралельно їй до оптимальної точки. Причому у процесі переходу від однієї точки до другої виконується аналіз проміжних точок, якщо це потрібно. Такий процес зображено на рис. 9.6.

М ₂ F _опт

М ₃

М ₁

F _поч

Рис. 9.6

Алгоритм розв’язування двовимірної задачі такий.

1. Аналіз цільової функції на опуклість та увігнутість.

2. Вибір початкової точки пошуку та знаходження для неї значення .

Вдалий вибір точки істотно впливає на швидкість знаходження точки оптимуму. Але загальних правил вибору найбільш вдалої початкової точки на сьогодні поки що немає.

3. Знаходження часткових похідних у загальному вигляді для цільової функції

4. Знаходження скалярних значень відповідних часткових похідних

5. Рух за напрямком градієнта від точки до точки за допомогою рівняння променя

де – крок від точки до точки , який треба знайти.

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

Для цього в обмеження задачі треба підставити координати точки у вигляді променя

або

і розв’язати кожне рівняння відносно . Потім вибрати мінімальне його значення, тобто

для усіх рівнянь, де виконується умова

Якщо ця умова не виконується, то відповідні значення кроку .

Потім, якщо це необхідно, у діапазоні для різних значень знаходяться координати проміжних точок і значення і з них вибирають екстремальну точку. Таким чином точка може бути або на межі області допустимих розв’язків (випадок ), або всередині цієї області (випадок ).

6. Рух паралельно межі області допустимих розв’язків або безпосередньо по прямій межі, на якій знаходиться точка . Такий рух виконується згідно з проекцією за напрямком руху.

З цією метою знаходяться компоненти одиничного вектора , який показує напрямок руху. Для цього складається система рівнянь:

– рівняння прямої, де лежить точка (початок координат перенесено у точку ):

де та – коефіцієнт при відповідних змінних того рівняння, для якого вибрана величина ;

– рівняння довжини одиничного вектора

Після розв’язання такої системи знаходяться величини та .

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

Для цього для точки складається рівняння променя

Оскільки необхідною та достатньою умовою оптимуму у точці є умова стаціонарної точки

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

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

Найкраще значення цільової функції відповідатиме оптимальному розв’язку задачі.

Блок-схема алгоритму розв’язування наведена на рис. 9.7.

При користування алгоритму розв’язку треба пам’ятати таке:

– якщо , то необхідно рухатися у протилежний бік від градієнта, тобто брати з протилежним знаком;

– якщо є умова , то для всіх значень знаходяться величини

а для значень величини ;

потім крок переходу знаходиться як

─ якщо , то аналіз проміжних точок у діапазоні не проводиться;

─ у процесі знаходження кроку переходу треба стежити, щоб обмеження задачі не порушувались; у випадку порушення деякого обмежен-

Треба додаткові дослідження

Ні

Так

min

max

Ні

Так

Рис. 9.7

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

Розглянутий алгоритм розв’язування наведено для двовимірної задачі. Для розв’язування п -вимірної задачі необхідно розв’язати самостійну додаткову задачу оптимізації:

─ цільова функція

─ обмеження

де – координати точок – коєфіцієнти прямої обмеження, для якої – складові одиничного вектора.

Розв’язування такої задачі пов’язано з додатковими труднощами, тому, як правило, розглянутий алгоритм використовуються тільки для двовимірної задачі.

Розглянемо приклад:

Знайти оптимальний розв’язок

Проведемо аналіз поведінки цільової функції:

частинні похідні

гессіан

головні мінори

Оскільки та , то цільова функція увігнута, тобто має збіг абсолютного та локального максимумів, тобто згідно з умовою Куна-Таккера.

Здійснемо розв’язування для :

Знайдемо

тому

Проведемо аналіз у діапазоні (0; 1) значень :

Приймемо максимальне значення :

Рух до точки

розв’язок S ₁ = 0,7, S ₂ = -0,7.

Тоді:

Знаходимо крок :

Приймаємо

Розв’яжемо для :

Проведемо аналіз у діапазоні :

Спостерігається тенденція до зменшення цільової функції і приймається:

Рух до точки

Тоді і

Приймаємо

Перевірка у діапазоні

Тенденція до збільшення, тому

Висновки

1. Класичні методи знаходження точок екстремуму мало пристосовані до практичного використання у задачах нелінійного програмування з обмеженнями.

2. Для нелінійних задач не існує універсальних алгоритмів розв’язування. Тому для задач цього типу є кілька спеціальних методів, які можна використовувати тільки для знаходження розв’язків окремих видів нелінійних задач.

3. Для окремих нелінійних задач, в яких умови Куна-Таккера є також і достатніми, розроблено алгоритми їх розв’язування.

4. Найкраще розроблено методи розв’язування для задач квадратичного програмування з лінійними обмеженнями.

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

Контрольні запитання

1. Які виникають труднощі у процесі розв’язування нелінійних задач?

2. Які ознаки увігнутості та опуклості цільової функції у заданій точці?

3. Що таке стаціонарна точка?

4. Які задачі відносяться до задач квадратичного програмування?

5. Що таке гессіан функції?

6. Як здійснювати аналіз на наявність точки екстремуму у задачах квадратичного програмування?

7. Яка умова Куна-Таккера для існування точки екстремуму?

8. Для чого вводяться множники у методі множників Лагранжа?

Список літератури

1. Акулич И.Л. Математическое программирование в примерах и задачах.- М.: Высш. шк., 1986. - 320 с.

2. Вітлінський В.В., Наконечний С.І., Терещенко Т.О., Математичне програмування: Навч.-метод. Посібник.- К.: КНЕУ, 2001.- 248с.

3. Костевич И.Д., Лапко А. А. Теория игор. Исследование операций. -Минск: Вышэйш. шк. 1982. - 232 с.

4. Кузнецов Ю.Н.. Кузубов В.М. Волощенко А.Б. Математическое программирование. - М.: Высш. шк., 1985. - 304 с.

5. Кузнецов А. В. Холод Н.И. Матаматическое программирование - Минск: Вышэйш. шк., 1984. – 221 с.

6. Максимов О.В., Афанасьєва М.Г., Липовик В.В., Щербак А.Ф., Математичне програмування: Навчальний посібник. - Кривий Ріг. Видавничий дім. 2003. – 274с.

7. Романюк Т.П., Терещенко Т.А., Присенко Г.В., Городкова І.М. Математичне програмування: Навч.посібник. – К.: ІЗИН, 1996.- 312с.

8. Сакович В.А. Исследование операций, - Минск: Вышзйш. шк, 1985. - 256 с.

9. Сакович В.А. Оптимальные решения экономических задач.- Минск: Вышейш. шк. 1982.- 272с.

10. Степанюк В. В. Методи математичного програмування. - К.: Вища шк., 1977.-272с.

11. Ульянченко О.В. Дослідження операцій в економіці: Підручник для студентів вузів.- Харків. Гриф. 2002.-580с.

12. Щербак А.Ф. Математичне програмування: Практичний посібник.- К.: КДЕУ, 1994.- 216с.

ЗМІСТ

ВСТУП....................................................................................................................5

РОЗДІЛ 1. Загальна задача лінійного програмування.............................10

1.1. Деякі поняття та означення...........................................................10

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

1.3. Основні типи прикладних задач лінійного програмування.......17

1.4. Графічний метод............................................................................23

1.5. Симплексний метод.......................................................................27

1.6. Рекомендації щодо розвязування задачі лінійного програму-вання................................................................................................49

Висновки….....................................................................................51

Контрольні запитання…................................................................51

РОЗДІЛ 2. Двоїсті задачі лінійного програмування..................................53

2.1. Взаємно двоїсті задачі....................................................................53

2.2. Алгоритм перетворення….............................................................54

2.3. Математичні моделі двоїстої пари задач та приклади їх

побудови..........................................................................................56

2.4. Економічний зміст двоїстої пари задач…...................................59

2.5. Теореми двоїстості.........................................................................61

2.6. Розв’язування двоїстої задачі........................................................63

2.7. Двоїстий симплекс-метод..............................................................66

2.8. Двоїсті оцінки................................................................................71

Висновки........................................................................................78

Контрольні запитання...................................................................79

РОЗДІЛ 3. Транспортна задача.....................................................................80

3.1. Властивості та типи транспортних задач....................................80

3.2. Умови оптимальності....................................................................82

3.3. Випадок виродження....................................................................84

3.4. Метод розв’язування транспортної задачі...................................85

3.5. Альтернативний оптимум............................................................96

3.6. Рекомендації щодо розв’язування методом потенціалів........100

Висновки.......................................................................................102

Контрольні запитання..................................................................103

РОЗДІЛ 4. Параметричне програмування................................................104

4.1. Економічна інтерпретація задач параметричного програму-

вання..............................................................................................104

4.2. Типи задач параметричного програмування............................106

4.3. Геометрична інтерпретація.........................................................108

4.4. Розв’язування задач.....................................................................108

4.5. Інші типи задач.............................................................................116

Висновки.......................................................................................117

Контрольні запитання..................................................................118

РОЗДІЛ 5. Елементи теорії ігор...................................................................119

5.1. Загальна характеристика та класифікація ігрових задач..........119

5.2. Матрична гра з нульовою сумою................................................121

5.3. Мішані стратегії...........................................................................126

5.4. Розв’язування матричної гри......................................................129

Висновки......................................................................................138

Контрольні запитання.................................................................138

РОЗДІЛ 6. Елементи динамічного програмування.................................139

6.1. Основні властивості задач динамічного програмування та недоліки методу..........................…..............................................139

6.2. Загальна математична модель.....................................................142

6.3. Розв’язування дискретних задач.................................................144

6.4. Випадок двосторонніх обмежень на змінні...............................155

6.5. Задачі з багатьма видами ресурсів.............................................156

6.6. Неперервні моделі........................................................................157

6.7. Задача управління запасами........................................................158

Висновки.......................................................................................160

Контрольні запитання..................................................................160

РОЗДІЛ 7. Дискретне програмування.......................................................162

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

7.2. Лінійні цілочислові задачі...........................................................163

7.3. Задачі з бульовими змінними......................................................172

Висновки.......................................................................................191

Контрольні запитання..................................................................192

РОЗДІЛ 8. Програмування на мережах.....................................................193

8.1. Основні поняття теорії графів.....................................................193

8.2. Засоби завдання графів. Зважені графи та мережі....................196

8.3. Потоки на мережах. Поняття розрізу.........................................197

8.4. Задача про максимальний потік..................................................199

8.5. Задача про найкоротшу відстань................................................205

8.6. Транспортна задача у сітьовій постановці.................................209

Висновки.......................................................................................212

Контрольні запитання..................................................................213

РОЗДІЛ 9. Нелінійне програмування.........................................................214

9.1. Властивості нелінійних задач.....................................................214

9.2. Деякі поняття та визначення.......................................................218

9.3. Задачі опуклого програмування..................................................219

9.4. Аналіз цільової функції на екстремум.......................................221

9.5. Алгоритми розв’язування найпростіших нелінійних задач....222

ВИСНОВКИ...........................................…........................................................237

КОНТРОЛЬНІ ЗАПИТАННЯ........................…...........................................237

СПИСОК ЛІТЕРАТУРИ..............................…..............................................238

⇐ Предыдущая 1 2 3 45