Самостійна робота 1

 

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

 

1. Теоретичні відомості

 

Цільові функції та обмеження, які враховують при розв’язуванні задач оптимізації параметрів і режимів системи електропостачання, залежать від двох груп змінних: керованих та некерованих. При цьому задача полягає в тому, щоб вибрати такі значення керованих змінних, які б надавали цільовій функції, в залежності від змісту задачі, максимуму чи мінімуму, при дотриманні обмежень. В якості керованих змінних в задачах оптимізації можуть виступати потужності компенсувальних пристроїв, раціональні місця розімкнення розподільчих електричних мереж 6-20 кВ та ін. В якості некерованих змінних можуть виступати параметри системи електропостачання (активні та реактивні опори ліній електропостачання, потужності трансформаторів та ін.), а також окремі параметри режимів ЕЕС. В склад некерованих змінних може входити й час, якщо мова йде про аналіз динамічної системи, яка змінює свої властивості та поведінку протягом деякого періоду часу.

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

1.               Детерміновані змінні − фіксовані параметри, значення яких відомі при формуванні математичної моделі.

2.               Стохастичні змінні − випадкові величини, для яких відомі закони розподілення та відповідні характеристики законів розподілення.

3.               Невизначені змінні, для кожної з яких відома тільки область можливих значень змінної. Невизначені параметри можуть задаватися лише інтервалами чи діапазонами.

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

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

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

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

Нехай ми маємо цільову функцію багатьох змінних:

 

                                          (1.1)

 

Необхідно на множині допустимих розв'язків Ω знайти такий вектор  − точку в n-мірному евклідовому просторі , яка надає екстремуму цільовій функції, тобто:

 

 

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

Розглянемо, які типи обмежень можуть формувати множину (область) допустимих розв’язків Ω .

Обмеження можуть бути прямими, тобто безпосередньо відносяться до змінних . Ці обмеження можуть бути односторонніми:

                                                               (1.2)

                                                               (1.3)

або двосторонніми:

                                                       (1.4)

 

Крім обмежень, які безпосередньо накладаються на змінні, область допустимих розв’язків Ω може формуватися і за рахунок необхідності врахування функціональних обмежень, які можуть бути представлені у вигляді рівностей:

                                                 (1.5)

нерівностей:

                                                 (1.6)

 

                                                 (1.7)

 

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

 

 

де  − множина дискретних значень, яку може приймати змінна хі.

Крім того, в задачах комбінаторного або альтернативного характеру змінні є булевими, тобто можуть приймати значення 0 або 1. Проілюструвати такі змінні можна задачею управління електроспоживанням промислового підприємства. Якщо змінна хі відображає стан і-го споживача-регулятора, то хі=1 відповідає ввімкненому споживачу-регулятору, а хі=0 − вимкненому.

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

1)              за часом (статичні та динамічні моделі);

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

3)              за можливостю диференціювання цільової функції та функціональних обмежень;

4)              за типом керованих змінних (моделі з цілочисельними, дискретними, булевими змінними та безперервними змінними).

В тому випадку, якщо цільова функція (1.1) лінійна, а також лінійні обмеження (1.5)-(1.7), то маємо задачу лінійного програмування, розв’язок якої здійснюється з використанням апарату лінійного програмування.

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

Якщо серед функцій (1.1), (1.5)-(1.7) є хоча б одна не лінійна, то говорять про задачу нелінійного програмування. Методи аналізу таких задач називаються методами нелінійного програмування. Задачі нелінійного програмування звичайно поділяються на задачі випуклого програмування та не випуклого, або багато екстремальні.

Задача називається випуклою, якщо випукла цільова функція (1.1) і випукла множина допустимих розв’язків, яка визначається обмеженнями (1.5)-(1.7). Для аналізу моделей випуклого програмування розроблений потужний апарат випуклого програмування. Частковим випадком задач випуклого програмування є задачі квадратичного програмування, тобто такі, в яких цільова функція представляє суму лінійної та квадратичної форм:

                                 (1.8)

а обмеження − лінійні.

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

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

                                   (1.9)

або

                                  (1.10)

У випадку (1.9) F(х) називається адитивною, а у випадку (1.10) − мультиплікативною.

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

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

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

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

2)   відсутність серед функціональних обмежень нерівностей типу (1.6), (1.7);

3)   відсутність прямих, тобто беспосередньо накладених на змінні хі, обмеження, в тому числі обмежень по невід’ємним змінним;

4)   відсутність серед змінних хі цілочисельних, дискретних і булевих.

Необхідно відзначити, що із перерахованих вимог принциповими є вимоги 1 та 4.

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

 

                                                             (1.11)

 

яке є необхідним, але недостатнім. В точках х* , які отримуються в результаті розв’язку систем рівнянь (1.11), можуть мати місце мінімум, максимум функції F(х) або так звана сідлова точка. Тому точки х* називають стаціонарними. Ознакою існування мінімуму функції F(х) в стаціонарній точці х* є виконання умов мінімуму − випуклості функції, що може бути представлено наступним чином:

тобто усі визначники повинні бути додатними.

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

Процедура безумовної оптимізації функції класичним методом включає наступні етапи:

а)      розв’язування системи рівнянь (1.11) з метою визначення всіх стаціонарних точок;

б)      аналіз стаціонарних точок з метою виявлення всіх мінімумів або максимумів функції F(х);

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

Звернемось тепер до розв’язку класичним методом (методом неозначених множників Лагранжа) задачі умовної оптимізації:

 

                             (1.12)

 

де область Ω визначається тільки обмеженнями, які задані у вигляді рівнянь:

 

                               (1.13)

 

Введемо вектор і розглянемо функцію

 

                        (1.14)

 

Функція Ф() є функцією Лагранжа, а величина  − множником Лагранжа. Функція Ф() є функцією n+т змінних  і

Розглянемо стаціонарні точки функції Ф(), які можна отримати із розв’язку системи рівнянь:

                                   (1.15)

                     (1.16)

 

Треба відмітити, що рівняння (1.16) співпадає з обмеженнями (1.13) і як виходить з (1.14), при Ф()= F(х). В зв’язку з цим, якщо в стаціонарній точці () функція (1.14) досягає екстремуму, то х* забезпечує і екстремум функції F(х) при виконанні обмежень (1.13), тобто дає розв’язок задачі (1.12), (1.13).

Таким чином, задача на умовний екстремум цільової функції F(х) при наявності обмежень, які задаються у вигляді рівностей, зводиться до визначення стаціонарних точок функції Лагранжа (1.14). Аналіз цих стаціонарних точок здійснюється так само як і у випадку безумовної оптимізації. При цьому, якщо розв’язується задача мінімізації випуклої функції А(х), яка задана на випуклій множині допустимих розв’язків , то будь-який локальний мінімум F(х) буде глобальним. Крім того, при мінімізації випуклої функції на випуклій області можливе врахування обмежень, які безпосередньо накладаються на змінні хi.