Рекомендовано методичною

Частина 2

НЕЛІНІЙНЕ, ДИСКРЕТНЕ І ДИНАМІЧНЕ ПРОГРАМУВАННЯ

МЕТОДИЧНІ ВКАЗІВКИ

ДЛЯ САМОСТІЙНОЇ РОБОТИ З КУРСУ

Міністерство освіти і науки України

Івано-Франківський національний технічний

університет нафти і газу

Кафедра електропостачання та електрообладнання

О.В. Соломчак, І. І. Сорохтей

Алгоритмізація оптимізаційних задач електроенергетики

Частина 2

Нелінійне, дискретне і динамічне програмування

Методичні вказівки

для самостійної роботи з курсу

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

“Електротехніка і електротехнології”

Рекомендовано методичною

радою університету

Івано-Франківськ

МВ 02070855 – 2533 – 2009

Соломчак О.В., Сорохтей І.І. Алгоритмізація оптимізаційних задач електроенергетики. Частина 2. Нелінійне, дискретне і динамічне програмування: Методичні вказівки для самостійної роботи з курсу – Івано-Франківськ: ІФНТУНГ, 2009. – 79 с.

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

У методичних вказівках коротко викладено основні теоретичні відомості з розділів “нелінійне, дискретне і динамічне програмування” курсу “Алгоритмізація оптимізаційних задач електроенергетики”, містяться завдання на розрахункову роботу та приклади розрахунку. У додатках наведено опис та приклади використання Microsoft Office Excel для розв’язку оптимізаційних задач електроенергетики.

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

Рекомендовано методичною радою університету від

24 грудня 2009р., протокол №3

Ó Соломчак О.В.,

Сорохтей І. І., 2009

Ó ІФНТУНГ, 2009

ЗМІСТ

ВСТУП.. 5

1 Навчально – методичне забезпечення дисципліни 6

2 НЕЛІНІЙНі оптимізаційні задачі. 7

2.1 Математична модель задачі нелінійного програмування 7

2.2 Графічний метод. 9

2.3 Дослідження стаціонарних точок функції та визначення їх характеру 10

2.4 Метод Ньютона. 12

2.5 Градієнтний метод з постійним кроком.. 15

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

2.7 Метод найшвидшого спуску. 17

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

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

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

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

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

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

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

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

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

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

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

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

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

8 ПРИКЛАДИ РОЗРАХУНКУ.. 46

Додатки. 58

Додаток А Загальні відомості про Excel 59

Додаток Б Розв’язування задач лінійного програмування. 62

Додаток В Розв’язування задач цілочислового програмування 68

Додаток Г Розв’язок задач нелінійного програмування. 71

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

Додаток Ж Розв’язування багатокритерійних задач. 77

ВСТУП

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

У разі вивчення дисципліни студент повинен:

ЗНАТИ - основи лінійного математичного програмування; графічне та алгебраїчне розв’язання задач лінійного програмування; основи нелінійного математичного програмування; теорему Куна-Таккера; градієнтні методи; квадратичне програмування; дискретне програмування; метод віток та меж; метод поконтурної оптимізації; динамічне програмування; випадкові величини та розподіл імовірностей; елементи теорії кореляції.

ВМІТИ - розв’язувати задачі лінійного програмування; розв’язувати задачу оптимізації розвитку енергосистеми; знаходити оптимальний план паливопостачання електростанцій системи; розв’язувати задачі нелінійного програмування; знаходити економічний розподіл активних потужностей навантаження між станціями енергосистеми; визначати економічну доцільність і оптимальний варіант розміщення батарей конденсаторів; вибирати оптимальну схему розвитку електричної мережі; вміти викласти послідовність розв’язку задачі оптимізації розподілу потужності навантажень між агрегатами електростанції.

Перелік забезпечуючих дисциплін

„Вища математика”, „Теоретичні основи електротехніки”, „Математичне моделювання”, „Електричні системи і мережі”.

Перелік дисциплін, що забезпечуються даною дисципліною

„Електропостачання промислових підприємств”, „Електропостачання підприємств нафтогазової промисловості”, „Електропостачання технологічних комплексів”, „Математичні методи електроенергетики”.

1 Навчально – методичне забезпечення дисципліни

1 Сидоров В.С. Алгоритмізація задач електроенергетики. Навч. Посібник. -К.:НМК ВО, 1993.-227 с.

2 Кутковецький В.Я. Дослідження операцій: Навчальний посібник. - Київ:Вид-во ТОВ „Видавничий дім „Професіонал”, 2004.-350с.

3 Зайченко Ю.П. Дослідження операцій. Підручник-К:ВД «Слово», 2006-316.

4 Вентцель Е.С.Овчаров Л.А. Теория вероятностей и ее инженерные приложения.-М:Наука, 1988.-480 с.

5 Зайченко Ю.П., Зайченко О.Ю. Дослідження операцій: збірник задач.-К: ВД»Слово»,2007.-472 с.

6 Аввакумов В.Г. Постановка и решение электроэнергетических задач исследования операций.-К:Вища шк.,1983.-240с.

7 Давыдов Э.Г. Исследование операций:Учебн. пособие для студентов вузов.- М.: Высш. Школа, 1990. - 383 с.

8 Арзамасцев Д.А. и др. Модели оптимизации развития энергосистем: Учебн. Для вузов.- М.Высш. школа, 1987.-272 с.

9 Соломчак О.В. Алгоритмізація оптимізаційних задач електроенергетики. Частина1. Лінійне програмування: Методичні вказівки з курсу. - Івано-Франківськ: Факел, 2002.- 31 с.

10 Соломчак О.В. Алгоритмізація оптимізаційних задач електроенергетики”. Частина 1. Метод. вказівки до лабораторних робіт для студ. спец.7.090603. Івано-Франківськ: "Факел",2000.-24 с.

11 Соломчак О.В., Сорохтей І.І. Алгоритмізація оптимізаційних задач електроенергетики. Частина 2. Нелінійне програмування: Методичні вказівки з курсу. - Івано-Франківськ: Факел, 2009.- 81 с.

2 НЕЛІНІЙНі оптимізаційні задачі

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

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

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

Математична модель задачі НП має вигляд

, (2.1)

при

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

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

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

Функція є опукла на інтервалі , якщо для будь-яких 2-х точок та з цього інтервалу справедлива нерівність:

, (2.2)

при .

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

Рисунок 2.1 – Перевірка опуклості функції

Таке визначення опуклості справедливе також і для функцій з декількома змінними . У цьому випадку кожна точка являє собою n-мірний вектор з координатами .

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

Методів розв’язання нелінійних задач існує багато:

- графічний метод;

- градієнтний метод;

- метод покоординатного спуску;

- метод найшвидшого спуску;

- метод проектування градієнту;

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

- метод Ньютона.

2.2 Графічний метод

Графічне розв’язання задачі НП можливе лише за наявності однієї, двох та трьох змінних. Випадку однієї змінної задача розв’язується на прямій, для двох – на площині, для трьох у просторі.

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

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

2 На основі обмежень на площині (для двох змінних), або у просторі (для трьох змінних) будуємо область допустимих розв’язків (ОДР).

3 З усієї множини точок нам потрібна лише одна – у якій цільова функція набуває найбільшого (найменшого) значення. Вибираємо довільну точку ОДР і підставляємо її координати в цільову функцію. Визначаємо z₀ і будуємо її проекцію на ОДР.

4 Визначаємо напрям покращення цільової функції у порівнянні з z₀. Для цього вибираємо довільну точку ОДР по один бік від z₀, обчислюємо значення z₁ і порівнюємо з z₀.

5 З теорії НП відомо, що оптимальне значення цільової функції знаходиться в крайній точці ОДР, тому переміщаємо z₀ в бік оптимуму. При цьому оптимальне z_max(min) може мати:

- одну спільну точку з ОДР, яка і буде оптимальною;

- відрізок спільних точок з ОДР, множина яких буде розв’язком;

- необмежену кількість точок, якщо z не виходить за межі ОДР.

2.3 Дослідження стаціонарних точок функції та визначення їх характеру

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

Теорема 1. Якщо функція у внутрішній точці відрізку має екстремум, то в цій точці похідна , якщо вона існує, дорівнює 0.

(2.3)

Внутрішня точка проміжку називається стаціонарною точкою функції , якщо в цій точці .

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

Достатню умову існування екстремальної точки формулює наступна теорема.

Теорема 2. Стаціонарна точка є екстремальною, коли матриця Гессе H у точці буде:

1) додатньо означена, тоді - точка мінімуму;

2) від’ємно означена, тоді – точка максимуму.

Якщо Н – невизначена матриця, то – є сідловою точкою.

Критерій Сільвестра визначає чи є квадратна матриця додатньоозначеною (від'ємноозначеною). Названий по імені англійського математика Джеймса Джозефа Сильвестра.

Якщо квадратична форма в деякому базисі має матрицю .

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

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

Для функції з трьома змінними матриця Гессе Н матиме вигляд

(2.4)

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

Нехай - стаціонарна точка, тоді:

1) – достатня умова існування max в точці ;

2) – достатня умова існування min в точці .

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

Якщо , то необхідно досліджувати похідні вищих порядків.

Теорема 3. Якщо в стаціонарній точці перші похідних функції перетворюються в нуль, а , то при функція має:

1 точку перегину, якщо n-непарне;

2 екстремальну точку, якщо n-парне.

Екстремальній точці відповідає максимум при і мінімум при .