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

Рішення:

Загальний вид цільової функції:

,

де ΔР∑ - сумарні втрати електроенергії;

К – вартість конденсаторної установки, К=Ко·Q∑;

Е – нормативний коефіцієнт відрахувань.

Знаходимо частинні похідні та прирівнюємо їх до нуля.

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

Розв’язання системи рівнянь дає оптимальне значення потужностей КБ, тобто:

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

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

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

Зокрема, якщо враховувати необхідність підтримки відхилень напруги на шинах споживачів V=±5%, які вимагаються, за умови, що на початку ЛЕП – 10 кВ створюється надбавка напруги En=2,5%, а в трансформаторах ТП відповідно Eт1=2.5% та Eт2=5%; втрати напруги в мережі 0,38 кВ ΔUв=5%, то нескладні розрахунки показують, що відхилення напруги у віддалених точках мережі виходять за межі допустимих як до, так і після оптимізації без урахування обмежень. Так у віддаленій точці мережі 0,38 кВ другої ТП після оптимізації прямим класичним методом напруга знаходиться в допустимих межах, а у віддаленій точці мережі 0,38 кВ першої ТП до оптимізації Vуд1=-8,52%, а після оптимізації Vопт. уд1=-6,50%.

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

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

до того ж обмеження зображуються у вигляді рівності.

Для рішення задачі варто сформувати функцію Лагранжа:

де λі – невизначені множники Лагранжа,

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

Отримуємо (n+m) рівнянь з (n+m) невідомими.

Рішення системи рівнянь дозволяє знайти вектор, який нас цікавить.

Приклад №2: За умовами прикладу №1 розв’язати задачу вибору оптимальної потужності КБ з урахуванням обмежень по режиму напруги.

Обмеження у вигляді рівності запишеться наступним чином:

,

(у формулі враховано те, що потужність – Qк [кВАр], напруга – U [кВ], відхилення напруги у відсотках, %:

Так як U=10 кВ, то отримуємо ),

тобто після компенсації відхилення напруги у віддаленій точці мережі 0,38 кВ першої ТП повинно бути рівним – 5%

Для умов, які задані, запишемо функцію Лагранжа:

У результаті диференціювання по та λ і прирівнювання похідних до нуля отримуємо систему з трьох рівнянь з трьома невідомими.

Розв’язання системи рівнянь (1) дає можливість отримати значення величин , які обертають в мінімум цільову функцію з урахуванням об­межень:

8.8. Деякі особливості застосування методу невизначених множників Лагранжа.

1. Метод може застосуватись, якщо цільова функція ЦФ диференційована. Якщо функція лінійна, то застосувати метод неможливо тому, що перші похідні є константами.

2. Якщо ЦФ або обмеження дискретні, то метод невизначених множників Лагранжа не застосовується.

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

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

5. Задача оптимізації може мати рішення, якщо (n-m)>0, тобто коли число змінних більше за число дисциплінарних умов.

Якщо m=n, то практично задача оптимізації неможлива і вирішується тільки по обмеженням, тобто виконується дисциплінарні умови.

Якщо n<m, задача практично нерозв’язана, так як не має жодної точки у просторі станів, яка задовольняє всім дисциплінарним умовам.

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

1. Дати визначення терміну «Дослідження операцій».

2. Що називається операцією?

3. Як може бути задана цільова функція?

4. Які основні принципи побудови цільової функції?

5. В чому вони полягають?

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

7. В чому полягає його сутність?

Лекція №9

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

9.1. Основна задача лінійного програмування (ОЗЛП)

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

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

ОЗЛП формулюється наступним чином:

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

(1)

та при зазначених умовах обертали б в мінімум чи максимум лінійну функцію

(2)

Областю допустимих рішень (ОДР) ОЗЛП називається сукупність невід’ємних змінних , які задовольняють систему обмежень (1).

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

Система обмежень може бути задана у вигляді нерівностей:

(3)

Щоб перейти до ОЗЛП необхідно ввести додаткові змінні в кожне рівняння, щоб вони перетворювали дані нерівності у рівності:

(4)

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

(5)

Задача полягає в тому, щоб знайти невід’ємні значення (n+m) змінних , щоб вони задовольняли систему m рівнянь і обертали в мінімум чи максимум лінійну цільову функцію ЦФ виду (2).

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

9.2. Геометрична інтерпретація ОЗЛП

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

Приклад №3. Для наведеної на мал. 1 схеми мережі необхідно вибрати такі ємності конденсаторних батарей на стороні 10 і 0,4 кВ ТП, щоб при мінімумі капітальних вкладень виконувалися наступні вимоги:

а) за вимогою енергосистеми повинно бути скомпенcовано не менш 300 кВАр.

б) щоб відхилення напруги на лініях НН ТП не перевищували +5% повинно виконуватися умова.

в) оскільки трансформатор перевантажений на стороні 0,4 кВ ТП потуж­ність конденсаторних батарей повинна бути не менш 100 кВАр.

Вартість конденсаторних батарей:

Позначимо змінні:

Тоді цільову функцію запишемо у вигляді рівняння:

(6)

Обмеження запишуться у виді систем нерівностей:

(7)

Оскільки ЦФ (6) і обмеження (7) лінійні, задача може бути вирішена методами лінійного програмування.

На мал. 2 побудовані лінії (1,2,3), які відповідають обмеженням. Проведені до кожної з них нормалі вказують область рішень, яка допустима даними обмеженнями. Наявність замкнутого багатокутника допустимих рішень (усі нормалі обмежень спрямовані у середину багатокутника, обмеження 4 – умова невід’ємності змінних) говорить про те, що в даному випадку рішення існує.

Будується лінія, що визначає ЦФ.

(8)

У початковому положенні – у силу невід’ємності змінних (мінімальна ЦФ).

Щоб визначити екстремум, необхідно рухатися по нормалі (у напрямку найбільшого зростання ЦФ) до і будувати лінії паралельні лінії (8). Тоді перша вершина багатокутника допустимих рішень, якої торкнеться одна х паралельних ліній, буде визначати мінімум ЦФ, а остання – її максимум.

Відповідно до геометричних побудов, оптимальним є рішення:

Перевірки показують виконання обмежень, які накладаються. Значення ЦФ в оптимальній точці.

грн.

Аналіз результатів геометричної побудови дозволяє зробити висновки:

1. Рішення ОЗЛП, якщо воно існує, не може знаходитися всередині області допустимих рішень, а знаходиться тільки на її границі.

2. Рішення ОЗЛП може бути не єдиним. Якщо основна пряма F0 паралельна стороні багатокутника допустимих рішень, де досягається мінімум ЦФ, тоді мінімум досягається не в точці, а на всій стороні багатокутника, тобто маємо нескінченну безліч рішень.

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

9.3. Симплекс-метод розв’язання задач лінійного програмування.

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

Нехай необхідно мінімізувати лінійну цільову функцію F при наявності m незалежних лінійних обмежень з n невідомими xi.

Якщо система рівнянь незалежна, то число вільних змінних дорівнює (n-m=k), а число базисних змінних дорівнює xі. (i=m)

Вільні змінні позначаємо x1,x2,…,xk, а базисні змінні xk+1,xk+2,…xn.

Припустимо, що вдалося одну частину змінних – базисні виразити через іншу частину змінних – вільні. Тоді задачу лінійного програмування в загальному вигляді можна записати наступним чином:

– функція вільних змінних (9)

при

– базисні змінні (10)

Далі припустимо, що x1=x2=…=xk=0. Тоді базисні змінні приймуть значення:

(11)

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

Це перше рішення може бути оптимальним чи неоптимальним.

Перш ніж викладами загальну схему переходу до наступного базисного рішення, перепишемо вирази в такому вигляді:

Позначимо:

Отримаємо: (12)

(13)

Якщо коефіцієнти усі від’ємні, то збільшуючи змінні, ми не можемо далі мінімізувати ЦФ F, і отриманий розв’язок буде оптимальним.

Якщо ж серед коефіцієнтів є додатні, то збільшуючи ті зі змінних, у яких коефіцієнти додатні, можна зменшувати значення ЦФ F.

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

Перепишемо систему обмежень у спрощеному вигляді:

Збільшення не викликає зменшення базисних змінних, у яких і за їх зміною можна не стежити.

Розглянемо базисні змінні, у яких .

Базисна змінна обертається в нуль при