Алгоритм методу найшвидшого спуску

1 Приймаємо початкове (нульове) наближення .

2 Обчислюємо значення цільової функції в цій точці Z⁰.

3 Відповідно до виразу (2.17) для цієї точки обчислюємо grad Z.

4 З початкової точки у напрямі градієнту (оптимуму) цільової функції виконyємо два одиничні кроки (λ =1). В кінці кожного кроку обчислюємо значення цільової функції Z¹ і Z².

5 Отже, маємо три значення цільової функції Z⁰, Z¹ і Z², що відповідають нульовій (λ =0), одиничній (λ =1) і подвійній (λ =2) довжинам кроку. Ці три значення характеризують перетин цільової функції Z у вибраному напрямі "спуску".

6 Відомо, що через три точки можна провести єдину параболу де а, b,c - постійні коефіцієнти. Визначимо координату мінімуму цієї параболи, для чого прирівняємо до нуля першу похідну функції по змінній λ: звідки Отримане значення визначає оптимальну довжину кроку λ_опт.

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

7 З початкової точки слід виконати крок довжиною λ_опт. В результаті виходить перше наближення - точка з координатами . Обчислюємо значення цільової функції в цій точці Z¹.

8 Далі обчислювальну процедуру повторюємо: послідовно отримуємо 2-е, 3-є і 4-е наближення - точки з координатами, . Значення цільової функції в цих точках відповідно становлять Z²,Z³,Z⁴.

9 В результаті обчислювального процесу послідовно наближаємось до екстремуму функції. Обчислювальна процедура закінчується, коли відносна зміна цільової функції на попередньому і-му і подальшому (і+1)-му кроках буде меншою від заданої точності обчислень ε:

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

2.8 Метод проектування градієнту

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

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

Алгоритм методу проектування градієнту

1 У області допустимих значень довільно виберемо початкове (нульове) наближення - точку з координатами . Значення цільової функції в цій точці рівне Z⁰.

2 Згідно з виразом (2.18) обчислимо в цій точці величину градієнту функції Z. Виконаємо крок у напрямі спадання (зростання) цільової функції. Вибір величини кроку може здійснюватися різним чином. Виберемо крок відповідно до алгоритму методу "найшвидшого спуску" і отримаємо перше наближення - точку з координатами . Обчислюємо значення цільової функції в цій точці Z¹.

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

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

5 Повернення в область виконуємо таким чином. З точки з координатами опускаємо перпендикуляр на лінію обмеження, яке не виконується, тобто кінець вектора ^- проектуємо на цю лінію. В результаті отримуємо нове наближення - точку , яка належить області допустимих розв’язків. У цій точці обчислюємо значення цільової функції Z³.

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

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

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

Алгоритм методу невизначених множників Лагранжа

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

, (2.19)

(2.20)

……………………..,

2 Згідно з методом Лагранжа замість відносного екстремуму функції при обмеженнях шукаємо абсолютний екстремум функції Лагранжа, яка має наступний вигляд

(2.21)

де λ₁, λ₂... λ_т - невизначені множники Лагранжа, що є, як і змінні х₁, х₂... х_п, шуканими змінними.

У функцію Лагранжа входить цільова функція плюс кожне обмеження, помножене на множник Лагранжа. Доведено, що відносний екстремум цільової функції (2.19) при обмеженнях (2.20) співпадає з абсолютним екстремумом функції Лагранжа (2.21).

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

(2.22)

Останні т рівнянь є обмеженнями (2.20) оптимізаційної задачі. Система (2.22) містить (т+п) рівнянь і таку ж кількість невідомих. Розв’язок системи виконуємо відомими методами обчислювальної математики. Якщо система лінійна, використовується, як правило, метод Гауса. Якщо система нелінійна - метод Ньютона.

4 Розв’язок системи (2.22) дасть координати абсолютного мінімуму функції Лагранжа (2.21) або відносного мінімуму цільової функції (2.19) при обмеженнях (2.20).

3 ДИСКРЕТНІ ОПТИМІЗАЦІЙНІ ЗАДАЧІ

3.1 Задачі з цілочисловими змінними

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

, (3.1)

де k = 1, 2... l;

l - кількість цілочислових змінних.

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

Введення додаткових обмежень по цілочисельності змінних істотно збільшує об'єм обчислень і ускладнює обчислювальну процедуру при пошуку оптимального розв’язку. Проте в заданому діапазоні цілочислова змінна має меншу кількість значень, чим безперервна. Зокрема, в діапазоні 0 < х < 3 цілочислова змінна х має чотири значення (х = 0, 1, 2, 3), а безперервна змінна - нескінченну кількість значень.

Спроба розв’язати цілочислову оптимізаційну задачу методом повного перебору значень змінних приводить до дуже великого об'єму обчислень. Так, наприклад, в задачі з трьома цілочисловими змінними і діапазоном їх зміни 0 < x_k < 10, k = 1, 2, 3 кількість цілочислових розв’язків складе 11³=1331. Ясно, що для реальних оптимізаційних задач метод повного перебору не прийнятний.

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

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

Існують різні методи розв’язку цілочислових оптимізаційних задач: метод відсікань (Гоморі), метод Беллмана, метод віток і меж. Зокрема, метод віток і меж заснований на переборі допустимих розв’язків не окремих розв’язків, а їх груп. Такий підхід скорочує загальний об'єм обчислень.

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

3.2 Метод Гоморі

За допомогою відсікань виділяють цілочислові частини області допустимих значень (ОДЗ). Існує можливість розв'язати дану задачу у певному розумінні частково, послідовно відсікаючи від множини ОДЗ деякі її частини за допомогою так званих відсікаючих площин. Ідея методів відсікання полягає в наступному: розв'язується ЗЛП, одержана з цілочислової відкиданням умови цілочисловості змінних. Якщо її розв'язок є цілочисловим, то він же є і розв'язком цілочислової задачі. Якщо ж задача розв'язку не має, то і ЦЗЛП розв'язку не має. Якщо розв'язок ЗЛП не є цілочисловими, то від розв'язаної ЗЛП переходять до нової допоміжної ЗЛП шляхом додавання лінійного обмеження, яке задовольняє усі цілочислові розв'язки ЦЗЛП, але не задовольняє одержаний нецілочисловий розв'язок початкової ЗЛП. Це додаткове лінійне обмеження визначає деяку відсікаючу площину і називається правильним відсіканням. Додавання нових правильних відсікань до початкової допоміжної ЗЛП здійснюється доти, поки на деякому кроці не буде одержаний цілочисловий розв'язок допоміжної задачі, який, очевидно, буде оптимальним розв'язком вихідної ЦЗЛП.

Алгоритм першого методу Гоморі

1 Розв'язуємо допоміжну ЗЛП. Нехай х (0) — її оптимальний розв'язок. Якщо оптимальний розв'язок не існує, то вихідна ЦЗЛП також не має оптимального розв'язку.

2 Нехай на s -й ітерації розв'язана допоміжна ЗЛП, що має m обмежень та n змінних, x(s) - її оптимальний розв'язок. Будемо вважати, що канонічні обмеження останньої ітерації, що визначають x (s), мають вигляд:

(3.2)

де

Розв'язком допоміжної ЗЛП є n -вимірний вектор .

3 Якщо , і=1,...,m,- цілі, то x(s) є оптимальним розв'язком задачі.

Якщо існує хоча б одне i таке, що - дріб, то переходимо до пункту 4.

4 Знаходимо I, що відповідає максимальні дробовій частині коефіцієнта { }, по всіх таких i, що - дріб, і формуємо додаткове обмеження, у якому коефіцієнти будуть дробовими частинами {g} коефіцієнтів попередніх обмежень

(3.3)

де - додаткова змінна.

5 Розширюємо симплекс-таблицю за рахунок (m+1)-го рядка (додаткове обмеження) та (n +1) - го стовпця, що відповідає додатковій змінній .

6 Розв'язуємо розширену таким чином ЗЛП двоїстим симплекс-методом і переходимо до пункту 2, змінюючи s на s+1. Якщо при цьому на якій-небудь ітерації двоїстого симплекс-методу одна з додаткових змінних задачі (тобто, тих, що з'явилися при побудові правильних відсіків) повторно стає базовою, то виключаються з подальшого розгляду відповідні їй рядок та стовпець.

3.3 Метод віток і меж

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

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

(3.4)

де D — скінченна множина.

Основу методу складають такі процедури.

1 Обчислення нижньої оцінки (границі ) для значень цільової функції Z(х) на допустимій множині D = D⁰ (або на деякій її підмножині), тобто, знаходження числа , такого, що для всіх . Питання про те, як знаходиться , вирішується окремо для кожної задачі.

2 Розбиття на підмножини (розгалуження ). Реалізація методу пов'язана з розгалуженням множини D (або деякої її підмножини) в дерево підмножин з наступним визначенням найбільш перспективної.

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

Алгоритм методу віток та меж (Ленд-Дойг)

1 Розв'язуємо задачу ЛП без врахування умови цілочисловості змінних. Якщо її розв'язок - цілочисловий, то він є розв'язком вихідної цілочислової задачі ЛП на множині D⁰. У протилежному випадку величина дає нижню оцінку (межу)цільової функції ЦЗЛП на множині D⁰.

2 Множину D ⁰ розбиваємо на дві підмножини , причому за умовою

(3.5)

де - нецілочислова компонента.

3 Розв'язуємо задачу ЛП на множині і знаходимо оптимальний розв’язок , аналогічно розв'язуємо задачу ЛП на множині і знаходимо оптимальний розв’язок .

4 Визначаємо оцінки , і перевіряємо умову оптимальності.

Якщо - цілочислова і , то - оптимальний розв'язок.

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

Поділ на підмножини у симплекс-методі здійснюється шляхом введення нових обмежень або .

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

3.4 Двійкові змінні

Окремим випадком цілочислових задач є задачі, в яких шукані змінні можуть приймати не будь-які цілі значення, а тільки одне з двох: 0 або 1. Такі змінні називаються двійковими або булевими.

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

На відміну від традиційних змінних х_i, двійкові змінні позначають δ_i, де i =1, 2... n.

Застосування двійкових змінних дозволяє накладати на розв’язувану задачу цілий ряд логічних умов типу «якщо..., то...».

Якщо в оптимальний розв’язок повинен входити один з двох (і чи j) варіантів, то сума змінних .

Якщо в оптимальний розв’язок повинні входити і i-й, і j-й варіанти, то сума змінних .

Якщо в оптимальний розв’язок може входити або не входити кожен з двох (і чи j) варіантів, то сума змінних .

Якщо при вході (не вході) в оптимальний розв’язок i -го варіанту в цей розв’язок повинен ввійти (не ввійти) j -й варіант, то .

Аналогічні умови можна записати для трьох і більше варіантів. Якщо з п можливих варіантів в оптимальний розв’язок повинні входити тільки т варіантів (т<п), то .

Очевидно, що кількість логічних умов типу «якщо..., то...» не обмежена.

4 ОПТИМІЗАЦІЙНІ ЗАДАЧІ ПРИ НЕВИЗНАЧЕНІЙ ПОЧАТКОВІЙ ІНФОРМАЦІЇ

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

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

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

Другий гравець - енергосистема, а точніше перспективні потужності споживачів енергії. Як розвиватиметься енергосистема, які будуть потужності споживачів в перспективі - однозначно невідомо. Стратегія енергосистеми - випадкова. Вона не прагне до максимального виграшу. Отже, енергосистему не можна вважати розумним гравцем.

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

Теорія ігор пропонує наступні основні стратегії вибору рішення.

1 Стратегія мінімуму середніх витрат. Відповідно до цієї стратегії для кожного ходу x_i людини визначаються середні витрати за всіма можливими ходами системи

(4.1)

Вибирається рішення, що відповідає мінімуму з сукупності i =1, 2,... n середніх витрат

(4.2)

При цій стратегії вважається, що всі ходи системи мають однакову імовірність, рівну 1/m. Для реальних задач таке припущення, як правило, не є правильним.

2 Мінімінна стратегія. Згідно з цією стратегією
вважається, що на кожен хід x_i людини система відповість ходом y_j, який відповідає мінімальним витратам

(4.3)

Вибирається рішення, що відповідає мінімуму з сукупності i =1, 2,... n мінімальних витрат

(4.4)

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

3 Мінімаксна стратегія. Згідно з цією стратегією вважається, що на кожен хід x_i людини система відповість ходом y_j, який відповідає максимальним витратам:

(4.5)

Вибирається рішення, що відповідає мінімуму з сукупності i =1, 2,…,n максимальних витрат:

(4.6)

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

4 Стратегія Гурвіца. Ця стратегія враховує як найсприятливішу, так і найнесприятливішу ситуації. Тут рішення вибирається за умовою

(4.7)

де коефіцієнти k і (1-k) грають роль вагових коефіцієнтів, з якими враховуються мінімаксна і мінімінна стратегії. При k=1 маємо мінімаксну стратегію, а при k=0 маємо мінімінну стратегію.

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

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

- аналізу рішень, отриманих за кожною стратегією;

- досвіду проектанта;

- особливостей конкретної задачі.

5 БАГАТОКРИТЕРІЙНІ ОПТИМІЗАЦІЙНІ ЗАДАЧІ

5.1 Визначення коефіцієнтів ваги кожного критерію

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

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

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

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

Нехай для вирішення оптимізаційної задачі прийнято три критерії (критерій А, критерій В і критерій С). Збирається група експертів - фахівців в тій галузі, до якої відноситься оптимізаційна задача. Нехай група експертів складається, наприклад, з трьох чоловік (1-й експерт, 2-й експерт і 3-й експерт). Кожному експертові пропонується оцінити в балах від 0 до 1 кожен критерій. При цьому висувається умова, щоб сума балів кожного експерта за всіма критеріями дорівнювала 1. Як ваговий коефіцієнт і-го критерію приймається середнє значення оцінок експертів.

5.2 Оптимізація за узагальненою цільовою функцією

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

(5.1)

де z_k - k-а цільова функція, що відображає k-й критерій;

z_kнорм - нормоване значення k -ї цільової функції;

- коефіцієнт ваги k -ї цільової функції;

n - кількість цільових функцій (прийнятих критеріїв).

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

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

Нормоване значення k-ї цільової функції z_kнорм приймається за результатами рішення оптимізаційної задачі лише за одним k-им критерієм.

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

6 ДИНАМІЧНЕ ПРОГРАМУВАННЯ

Динамічне програмування присвячено теорії і методам розв’язання багатокрокових задач оптимального керування. Основоположником методів динамічного програмування є американський математик Річард Беллман.

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

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

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

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

Динамічне програмування зазвичай дотримується двох підходів до вирішення задач:

1 Низхідне динамічне програмування: задача розбивається на підзадачі меншого розміру, вони розв’язуються і потім комбінуються для вирішення початкового задачі. Використовується запам'ятовування для розв’язку підзадач, що часто зустрічаються.

2 Висхідне динамічне програмування: всі підзадачі, які згодом знадобляться для вирішення вихідної задачі прораховуються заздалегідь і потім використовуються для побудови рішення початкової задачі. Цей спосіб краще низхідного програмування в сенсі розміру необхідного стека і кількості виклику функцій, але інколи буває нелегко заздалегідь з'ясувати вирішення яких підзадач нам буде потрібно надалі.

Класичні задачі динамічного програмування:

- задача про найбільшу загальну підпослідовність;

- задача пошуку найбільшої зростаючої підпослідовності;

- задача про редакційну відстань (відстань Левенштейна);

- задача про обчислення чисел Фібоначчі;

- задача про порядок перемножування матриць;

- задача про вибір траєкторії;

- задача послідовного ухвалення рішення;

- задача про використання робочої сили;

- задача управління запасами;

- задача про ранець;

- задача пошуку найкоротшої дороги в мережі;

- алгоритм Флойда-Уоршелла;

- максимальна незалежна множина вершин в дереві.

7 ЗАВДАННЯ НА РОЗРАХУНКОВУ РОБОТУ “Нелінійне і дискретне програмування”

Задача 1. Графічним методом розв’язати задачу нелінійного програмування: знайти мінімум функції z при заданих обмеженнях.

Варіант 1	Варіант 2
Варіант 3	Варіант 4
Варіант 5	Варіант 6
Варіант 7	Варіант 8
Варіант 9	Варіант 10
Варіант 11	Варіант 12
Варіант 13	Варіант 14
Варіант 15	Варіант 16
Варіант 17	Варіант 18
Варіант 19	Варіант 20
Варіант 21	Варіант 22
Варіант 23	Варіант 24
Варіант 25	Варіант 26

Задача 2. Визначити стаціонарні точки функції Z та їх характер

Варіант 1	Варіант 2
Варіант 3	Варіант 4
Варіант 5	Варіант 6
Варіант 7	Варіант 8
Варіант 9	Варіант 10
Варіант 11	Варіант 12
Варіант 13	Варіант 14
Варіант 15	Варіант 16
Варіант 17	Варіант 18
Варіант 19	Варіант 20
Варіант 21	Варіант 22
Варіант 23	Варіант 24
Варіант 25	Варіант 26

Задача 3. Розв’язати методом Ньютона (3 ітерації) наступне рівняння (початкове наближення дорівнює 0).

Варіант 1	Варіант 2
Варіант 3	Варіант 4
Варіант 5	Варіант 6
Варіант 7	Варіант 8
Варіант 9	Варіант 10
Варіант 11	Варіант 12
Варіант 13	Варіант 14
Варіант 15	Варіант 16
Варіант 17	Варіант 18
Варіант 19	Варіант 20
Варіант 21	Варіант 22
Варіант 23	Варіант 24
Варіант 25	Варіант 26

Задача 4. Розв’язати задачу методом покоординатного спуску

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

Рисунок 7.1 - Схема електропостачання

Вихідні дані:

Напруга схеми . Опори ліній , .

Реактивне навантаження вузлів 1 і 2 і .

Варіант

Варіант

Варіант

Питомі витрати на встановлення компенсувальних пристроїв ; норматив щорічних витрат на експлуатацію ; норма дисконту Е= 0,1; час найбільших втрат ; час використання максимального навантаження ; питомі витрати на покриття втрат активної потужності ; тариф на відпускну електроенергію електростанцій ; економічний еквівалент реактивної потужності D =0,02.

Задача 5. Розв’язати задачу методом невизначених множників Лагранжа.

Для заданої схеми електропостачання (рис. 7.2) потрібно розподілити між вузлами 1, 2 і 3 компенсувальні пристрої сумарною потужністю 1000 кВАр. Критерій оптимальності – мінімум втрат активної потужності в мережі.

Рисунок 7.2 - Схема електропостачання до задачі 5

Вихідні дані: напруга схеми .

Варіант
	0,4	0,5	0,4	0,3	0,5	0,6	0,4	0,5	0,3	0,2
	0,6	0,4	0,3	0,5	0,6	0,4	0,5	0,3	0,2	0,3
	0,5	0,3	0,4	0,4	0,4	0,4	0,2	0,4	0,4	0,4

Варіант
	0,5	0,6	0,4	0,5	0,5	0,6	0,4	0,5	0,3	0,2
	0,6	0,4	0,5	0,3	0,6	0,4	0,5	0,3	0,2	0,3
	0,4	0,4	0,2	0,4	0,4	0,4	0,2	0,4	0,4	0,4

Варіант
	0,4	0,4	0,5	0,5	0,6	0,4
	0,6	0,5	0,3	0,6	0,4	0,5
	0,5	0,2	0,4	0,4	0,4	0,2

Задача 6. Розв’язати задачу на дискретні двійкові змінні з використанням математичного апарату Excel.

Скласти математичну модель для визначення оптимального вузла встановлення конденсаторної батареї, заданої потужності ,в схемі електропостачання (рис. 7.3) та розв’язати її на ЕОМ з використанням математичного апарату програми Excel.

Критерій оптимальності – мінімум втрат активної потужності в схемі.

Рисунок 7.3 - Схема електропостачання до задачі 6

Вихідні дані: напруга схеми потужність конденсаторної батареї кВАр.

Варіант
	0,5	0,6	0,4	0,5	0,5	0,6	0,4	0,5	0,3	0,2
	0,6	0,4	0,5	0,3	0,6	0,4	0,5	0,3	0,2	0,3
	0,4	0,4	0,2	0,4	0,4	0,4	0,2	0,4	0,4	0,4

Варіант
	0,4	0,5	0,4	0,3	0,5	0,6	0,4	0,5	0,3	0,2
	0,6	0,4	0,3	0,5	0,6	0,4	0,5	0,3	0,2	0,3
	0,5	0,3	0,4	0,4	0,4	0,4	0,2	0,4	0,4	0,4

Варіант
	0,4	0,5	0,4	0,3	0,5	0,6
	0,6	0,4	0,3	0,5	0,6	0,4
	0,5	0,3	0,4	0,4	0,4	0,4

Задача 7 Розв’язати задачу з дискретними змінними, використавши математичний апарат Excel.

Скласти математичну модель для визначення оптимальної потужності конденсаторної батареї у вузлі 2 схеми електропостачання (рис.7.4). Критерій оптимальності – мінімум втрат активної потужності.

Вихідні дані наведені з прикладу 6.

Потужність конденсаторної батареї може приймати наступні дискретні значення: 1100, 1200, 1300 кВАр.