Конспект лекцій (стр. 12 )

Таким же шляхом визначаємо наступні рішення і відповідні їм значення цільової функції:

(6+2) > (5+2)

7. Будуємо наступний допустимий план (таблиця №4):

Таблиця №4

Отримувачі Виробники	П1	П2	П3	П4	Відправлено
ТП1	6 120	4	2 130	0	250
ТП2	5 20	3 90	2	0 50	160
Отримано	140	90	130	50

Значення цільової функції:

Для позначеного прямокутного контуру (таблиця №4) визначаємо і звіряємо суми тарифів діагоналей:

(6+0) > (5+0)

8. Будуємо новий допустимий план (таблиця №5):

Таблиця №5

Отримувачі Виробники	П1	П2	П3	П4	Відправлено
ТП1	6 70	4	2 130	0 50	250
ТП2	5 70	3 90	2	0	160
Отримано	140	90	130	50

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

1 контур (6+0) > (5+0) – не можна робити перерозподіл (тому що

діагональ з вільною ячійкою більша ніж з

заповненою)

2 контур (6+2) > (5+2) – не можна робити перерозподіл.

3 контур (6+3) = (5+4) – перерозподіл не має змісту, оскільки не

відбудеться поліпшення параметру, який

оптимізується.

Значення ЦФ при оптимальному варіанті розподілу:

Оптимальна схема електропостачання прийме такий вигляд:

10.3. Питання для самоконтролю:

1. Формулювання транспортної задачі?

2. Які моделі транспортної задачі бувають?

3. Метод північно-західного кута?

4. Коли припиняється процес оптимізації?

Лекція №11

Методи нелінійного програмування.

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

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

Задача нелінійного програмування може бути сформульована наступним чином:

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

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

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

Методи нелінійного програмування НП класифікуються:

1. за видом ЦФ:

- опукла;

- увігнута;

- квадратна.

2. за характером змінних керування:

- неперервні;

- дискретні;

- імовірні.

3. за особливостями способу розв’язання:

- аналітичні;

- чисельні;

- з дискретним кроком оптимізації.

Приклад №1. Для схеми наведеної на малюнку визначити потужність

конденсаторних батарей Q2 та Q3, які будуть мінімізувати

втрати у мережі.

МВАр

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

11.2. Метод Гаусса-Зейделя.

Сутність методу: Заснований на послідовному наближенні до екстремуму шляхом почергового варіювання кожної змінної до досягнення частинного екстремуму цільової функції.

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

Алгоритм розв’язку за методом Гаусса-Зейделя

1. Визначається вихідна точка. Найчастіше це змінна з нульовими значеннями.

2. Задається крок варіювання , по кожній незалежній змінній.

3. Визначається напрямок руху вздовж осі . З цією метою з точки для варіації параметрів здійснюються два пробних кроки:

4. Робиться порівняння значень ЦФ в пробних точках xi' та xi'' і визначається різниця між вихідним і пробними значеннями ЦФ.

При крок вважається вдалим.

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

6. Після кожного робочого кроку визначається значення ЦФ.

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

8. Отримана точка є вихідною для наступного циклу кроків по черговій змінній .

11.3. Метод покоординатного спуску.

Обираємо початкове наближення . Зафіксуємо і знайдемо min функції однієї змінної . Нехай він досягається при . Вздовж прямої, яка паралельна осі , здійснюємо спуск в точку . Фіксуємо та знаходимо min однієї змінної . Нехай це буде . З точки рухаємось по прямій, яка паралельна осі , до точки . Потім знову здійснюємо спуск з точки вздовж прямої, яка паралельна осі , і так далі.

Відомі деякі модифікації методу покоординатного спуску (ПКС):

1. ПКС з постійним кроком: у цьому випадку не потрібно на кожному кроці знаходити мінімум функції однієї змінної, а спуск в напрямку координатних осей здійснюється в сторону спадання функції з постійним кроком h. Як тільки функція цілі перестає спадати, спуск припиняється.

2. ПКС з оптимізацією кроку.

11.4. Покординатний спуск з оптимізацією кроку.

Якщо в кожній точці простору під час руху по будь-якій координаті можна розв’язати систему рівнянь виду:

то на кожному кроці можна знайти оптимальну його довжину.

Приклад №2. Маємо ЦФ з попереднього прикладу №1

1. Продиференціюємо ЦФ по :

Після перетворення отримаємо:

(1)

2. Аналогічно знаходимо другу частину похідну по :

Після перетворення отримаємо:

(2)

3. З отриманих рівнянь (1) і (2) складаємо систему:

(3)

Алгоритм розв’язку системи (3):

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

;

2. Виконуємо перший крок змінюючи координату при незмінній .

Для цього в першому рівнянні системи (3) підставляємо значення координати .Отримуємо

Отже після першого кроку отримуємо точку першого наближення .

3. Розв’язуємо систему (3) відносно при незмінній .

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

тобто отримуємо точку .

4. Продовжуючи розрахунки по даній схемі отримуємо точки:

, ,

Ознакою зупинки повинна бути наперед задана точність розрахунку .

Даний метод дозволяє значно швидше досягти оптимального значення, ніж метод Гауса-Зейделя.

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

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

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

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

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

11.6. Метод простого спуску по антиградієнту.

Градієнтом ЦФ в n-мірному просторі змінних керування називається вектор, координати якого дорівнюють частинним похідним по кожній змінній.

Кожна координата градієнту характеризує інтенсивність змінювання ЦФ по кожній зі змінних.

Градієнт – це вектор, по якому ЦФ зростає найбільш інтенсивно в порівнянні з іншими напрямками.

Довжина вектору-градієнту виражає інтенсивність зростання ЦФ.

Антиградієнт – вектор, який однаковий за довжиною, але протилежний за напрямком градієнту.

Алгоритм розв’язання задачі:

1. Обирається в якості початкової довільна точка у просторі станів.

2. Будь-яким способом визначається градієнт ЦФ в даній точці.

3. Обирається крок руху по антиградієнту довжиною .

4. Обчислюється крок руху в напрямку антиградієнту по кожній координаті:

5. Повторюється виконання алгоритму по пунктах 2 – 4 до тих пір, поки довжина кроку не стане рівною нулю (тобто досягнута точка екстремуму).

11.7. Спуск по антиградієнту з оптимізацією кроку

В цьому випадку оптимізація кроку може бути здійснена шляхом розв’язання системи рівнянь виду:

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

При розв’язанні за допомогою ряду Тейлора можна обмежитися трьома першими членами ряду. Без розв’язку представимо отриманий вираз для визначення оптимального кроку:

.

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

1) Визначаємо градієнт:

.

2) Визначаємо другі похідні:

(1)

3) Обираємо вихідну точку початкового наближення х0 Q2=0; Q3=0

4) Для цієї точки обчислюємо gradΔP:

5) Визначаємо для початкового кроку, знаючи значення других похідних (1)

6) Виконуємо перший крок і визначаємо перше наближення (нову координату):

Координати нової точки (перше наближення): х1(18,5;14)

7) Для цієї точки х1 обчислюємо градієнт:

8) Визначаємо новий оптимальний крок для руху по антиградієнту:

9) Виконуємо другий крок:

Координати другої точки (друге наближення): х2(22,7; 8,7)

10) Розрахунок продовжується до досягнення заданої точки

При виконанні наступних кроків отримуємо наступні координати:

х3(23,5; 9,5)

х4(23,8; 9,1)

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

11.8. Проблема багатоекстримальності.

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

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

Порівнюючи значення ЦФF знаходимо, що F=min в т. .

Універсального методу боротьби з багатоекстримальністю не існує. Самий простий прийом полягає у наступному: пошук проводять декілька раз, починаючи його з різних точок. Якщо при цьому отримують різні значення відповідей, то порівнюють в них значення ЦФ і обирають найменше.

Розрахунки припиняються після того, як декілька нових пошуків не змінюють отриманого раніше результату.

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

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

11.9. Питання для самоконтролю:

1. Яка відмінність методів нелінійного програмування?

2. Формулювання задачі нелінійного програмування?

3. Класифікація методів нелінійного програмування?

4. Сутність методу Гауса-Зейделя?

5. Модифікації методу покоокдинатного спуску?

6. Дати визначення терміну «Градієнт фінкції».

ЛІТЕРАТУРА:

1. , , Численные методы в инженерных исследованиях. – К.: Вища школа, 1989.

2. Численные методы. – М.: Наука, 1982.

3. Основные понятия вычислительной математики. М. Наука, 1992.

4. , , Зінько П. Н. Методы и алгоритмы решения задач оптимизации. К. Вища школа. 1993.

5. Базара М, Нелинейное программирование. Теория и алгоритмы. М. Энергия, 1989