Туркин Д.Г. Математические задачи энергетики. Методические указания

Подождите немного. Документ загружается.

4.2 Нелинейные оптимизационные задачи

Большинство реальных оптимизационных задач являются нелинейными.

Нелинейная целевая функция может иметь один или несколько

экстремумов. При многоэкстремальной целевой функции диапазон изменения

переменных (4.3) разбивается на ряд более узких диапазонов, например

< х

< a

, a

< х

< b

, b

< х

< D

, i = 0, 1, 2, ... n, (4.13)

в каждом из которых ищется локальный экстремум целевой функции. Из

полученных локальных экстремумов выбирается глобальный экстремум.

Наиболее простыми задачами нелинейного программирования являются

задачи безусловной оптимизации.

В этих задачах ищется абсолютный экстремум целевой функции без

ограничений и граничных условий.

Из курса высшей математики известно, что в точке экстремума

(минимума, максимума) нелинейной функции все ее частные производные

равны нулю. Следовательно, для нахождения экстремума нелинейной функции

n переменных необходимо определить ее частные производные по всем

переменным и приравнять их к нулю. Решение полученной системы n

уравнений c n неизвестными даст значения переменных, при которых

достигается экстремум функции.

Задачи безусловной минимизации на практике встречаются редко, однако

методы их решения являются основой решения большинства практических

задач условной оптимизации.

В этих задачах ищется условный экстремум целевой функции, т.е.

экстремум функции при наличии ограничений и граничных условий.

Естественно, что решение задач условной оптимизации значительно

сложнее решения задач безусловной оптимизации.

Поэтому стремятся свести задачи условной оптимизации (поиска

относительного экстремума) к более простой задаче безусловной оптимизации

(поиска абсолютного экстремума).

Такая процедура осуществляется в методе Лагранжа.

Рассмотрим сущность этого метода.

Необходимо найти условный экстремум нелинейной функции

Z(x

, x

, ... x

) → extr (4.14)

n переменных, при m ограничениях

, x

, ... x

) > b

, x

, ... x

) = b

, (4.15)

……………………..

, x

, ... x

) < b

Ограничения-неравенства преобразуются в равенства, а свободные члены

переносятся в левые части ограничений, т.е. система (4.15) приводится к виду

, x

, ... x

, b

) = 0,

, x

, ... x

, b

) = 0, (4.16)

……………………….

, x

, ... x

, b

) = 0.

В соответствии с методом Лагранжа вместо относительного экстремума

функции (4.14) при ограничениях (4.16) ищется абсолютный экстремум

функции Лагранжа, которая имеет следующий вид:

L = Z(x

, x

, ... x

) + λ

, x

, ... x

, b

)+λ

, x

, ...

... x

) + ... + λ

, x

, ... x

, b

) → extr, (4.17)

где λ

, λ

, ... λ

- неопределенные множители Лагранжа, являющиеся, как и

переменные x

, x

, ... x

, искомыми переменными.

Видно, что в функцию Лагранжа входит целевая функция плюс каждое

ограничение, умноженное на множитель Лагранжа.

Доказано, что относительный экстремум целевой функции (4.14) при

ограничениях (4.16) совпадает с абсолютным экстремумом функции

Лагранжа (4.17).

Поиск абсолютного экстремумам функции (4.17) выполняется

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

частные производные функции Лагранжа:

∂L/∂x

= ∂Z/∂x

+ λ

∂f

/∂x

+ λ

∂f

/∂x

+ ...+λ

∂f

/∂x

=0,

∂L/∂x

= ∂Z/∂x

+ λ

∂f

/∂x

+ λ

∂f

/∂x

+ ...+λ

∂f

/∂x

=0,

……………………………………………………………..

∂L/∂x

= ∂Z/∂x

+λ

∂f

/∂x

+ λ

∂f

/∂x

+ ...+λ

∂f

/∂x

=0, (4.18)

∂L/∂λ

= f

, x

, ... x

, b

)= 0,

∂L/∂λ

= f

, x

, ... x

, b

)= 0,

………………………………….

∂L/∂λ

= f

, x

, ... x

, b

)= 0.

Последние m уравнений представляют собой ограничения (4.16)

оптимизационной задачи.

Система (4.18) содержит (m + n) уравнений и такое же количество

неизвестных. Решение системы (4.18) даст координаты абсолютного минимума

функции Лагранжа (4.17) или относительного минимума целевой функции

(4.14) при ограничениях (4.16).

Решение системы (4.18) выполняется известными методами

вычислительной математики.

Если система (4.18) линейная, используется, как правило, метод Гаусса.

Если система (4.18) нелинейная - метод Ньютона.

Особенности применения метода неопределенных множителей

Лагранжа

1. Метод применяется, когда целевая функция дифференцируема. Если

целевая функция линейная, то применить метод невозможно, т.к. 1-я

производная является константой.

2. Если целевая функция и ограничения являются дискретными – метод

применить нельзя.

3. Возможна алгоритмизация процессов вычисления производных,

должна обеспечиваться принципиальная возможность вычисления 2-х

производных.

4. Решение реальных задач связано с большой размерностью, что

накладывает большие трудности на решение систем большего порядка.

5. Решение этой задачи возможно при условии, когда n – m > 0, т.е.

число переменных больше числа условий-ограничений.

6. Если n = m решение задачи оптимизации практически невозможно. В

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

7. Если n < m – задача неразрешима, т.е. нет ни одной точки в

пространстве состоянии, в которой удовлетворялись бы условий-ограничений.

4.3 Многокритериальные оптимизационные задачи

Рассмотренные выше решения оптимизационных задач выполнялись по

одному критерию (по одной целевой функции). На практике не всегда удается

свести задачу к одному критерию, поскольку желаемых целей может быть

несколько.

Задачи, в которых оптимизация проводится по нескольким критериям,

называют задачами многокритериальной оптимизации. Такая оптимизация

представляет собой попытку найти компромисс между принятыми критериями.

Важным моментом нахождения такого компромисса является назначение

коэффициентов веса каждого критерия. В конечном итоге решение

многокритериальной задачи сводится к оптимизации по одному обобщенному

критерию, в который входят все принятые критерии со своими весовыми

коэффициентами. Существует достаточно много способов определения весовых

коэффициентов. Рассмотрим один из них, а именно, способ экспертных оценок.

Суть этого способа заключается в следующем.

Для решения оптимизационной задачи принят ряд критериев (в общем

случае s). Собирается группа экспертов – специалистов в той области, к

которой относится оптимизационная задача. Каждому эксперту предлагается

оценить в баллах от 0 до 1 каждый критерий. При этом выдвигается условие,

чтобы сумма баллов каждого эксперта по всем критериям была бы равна 1.

В качестве весового коэффициента i-го критерия (i = 1, …, s) принимается

среднее значение оценок каждого эксперта по этому критерию.

Одним из возможных решений многокритериальной задачи является

оптимизация по обобщенной целевой функции, в которую входят все принятые

к рассмотрению критерии со своими весовыми коэффициентами.

Эта обобщенная функция записывается следующим образом:









iнорм

об

→ max, (4.19)

где Z

– i-я целевая функция, выражающая i-й критерий;

i норм

– нормированное значение i-й целевой функции;

– коэффициент веса i-й целевой функции;

s – количество целевых функций (принятых критериев).

Если i-я целевая функция максимизируется, перед ней под знаком суммы

ставится плюс. Если i-я целевая функция минимизируется, перед ней под

знаком суммы ставится минус.

Весовые коэффициенты могут быть определены, например, с помощью

экспертных оценок.

Нормированное значение i-й целевой функции Z

i норм

принимается по

результатам решения оптимизационной задачи только по одному i–му

критерию.

Целевые функции в общем случае имеют разные единицы измерения.

Поэтому в (4.19) введено деление каждой целевой функции на ее

нормированное значение. Такое действие приводит все целевые функций к

единой размерности (к относительным единицам, о.е.).

Составление ограничений и граничных условий для многокритериальной

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

однокритериальной задачей.

Контрольные вопросы

1. Симплекс метод как метод линейного программирования.

2. Общая постановка оптимизационных задач в энергетике.

3. Запишите математическую модель транспортной задачи.

4. Опорный план – способы построения.

5. Сформулируйте принцип отыскания допустимого решения в

транспортной задаче.

6. Метод потенциалов как модификация транспортной задачи.

7. Транспортная задача с учетом транзита мощности.

8. Транспортная задача с учетом ограничения пропускной способности

линий электропередач.

9. Критерии оптимальности структуры транспорта в транспортной задаче.

10.Цикл пересчета при оптимизации транспортной задачи.

11.Определите основные понятия математической модели: целевая

функция, ограничения, граничные условия.

12.Назовите основные методы решения линейных оптимизационных задач

и основные этапы этих методов.

13.Поясните суть метода экспертных оценок.

14.Запишите обобщенную целевую функцию многокритериальной задачи.

15.Поясните понятие «нормированное значение целевой функции».

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Пугачев В.С. Теория вероятностей и математическая статистика. - М.:

Физматлит, 2003. – 532 с.

2. Магнус, Я., Нейдекер Х. Матричное и дифференциальное исчисление с

приложениями к статистике и экономике. - М.: Физматлит, 2003. – 332 с.

3. Электрические системы. Математические задачи электроэнергетики:

Учебник для студентов вузов/Под ред. В.А. Веникова – 2-е изд., перераб. и доп.

– М.: Высш. школа, 1981. – 288 с., ил.

4. Электрические системы. Электрические сети.: учеб. для электроэнерг.

спец. ВУЗов / Под ред. В.А. Веникова, В.А.Строева. – М.:ВШ, 1998

5. Вентцель Е.С. Исследование операций: задачи, принципы,

методология. – М.: Наука, Главная редакция физико-математической

литературы, 1980. – 208 с.

6. Щукин Б.Д., Лыков Ю.Ф. Применение ЭВМ для проектирования

систем электроснабжения. - М.: Энергоатомиздат, 1982.

7. Идельчик В.И. Электрические системы и сети: Учебник для ВУЗов.–

М.: Энергоатомиздат, 1989

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..................................................................................................................3

1 ЭЛЕМЕНТЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ............................................................4

1.1 Основные понятия.................................................................................................4

1.2 Основные теоремы................................................................................................6

1.2.1 Теорема сложения вероятностей................................................................7

1.2.2. Теорема умножения вероятностей............................................................9

1.2.3 Формула полной вероятности..................................................................12

1.3 Случайные величины и законы их распределения...........................................13

1.3.1 Закон распределения.................................................................................13

1.3.2 Плотность распределения.........................................................................16

1.3.3 Числовые характеристики случайных величин......................................19

1.4 Законы распределения случайных величин в задачах надежности

электроснабжения......................................................................................................27

1.4.1 Биномиальное распределение..................................................................27

1.4.2. Распределение Пуассона..........................................................................29

1.4.3 Нормальный закон распределения...........................................................32

2 УРАВНЕНИЯ СОСТОЯНИЯ УСТАНОВИВШЕГОСЯ РЕЖИМА

ЭЛЕКТРИЧЕСКОЙ СИСТЕМЫ..............................................................................34

2.1 Схема замещения как связанный граф..............................................................34

2.2 Матрица соединений (первая матрица инциденций).......................................38

2.3 Матрица контуров (вторая матрица инциденций)...........................................41

2.4 Обобщенное уравнение состояния....................................................................42

2.5 Разделение схемы на дерево и хорды................................................................43

2.6 Топологические свойства графа.........................................................................46

2.7 Решение уравнений состояния...........................................................................47

3 МЕТОДЫ РЕШЕНИЯ УРАВНЕНИЙ СОСТОЯНИЯ ЭЛЕКТРИЧЕСКОЙ

СИСТЕМЫ.................................................................................................................49

3.1 Решение уравнений состояния прямыми методами.........................................51

3.1.1 Алгоритм метода Гаусса с обратным ходом...........................................51

3.1.2 Алгоритм метода Гаусса без обратного хода (схема Жордана)............53

3.1.3 Факторы, влияющие на точность решения.............................................54

3.2 Решение уравнений состояния итерационными методами.............................58

3.2.1 Метод простой итерации..........................................................................59

3.2.2 Метод Зейделя............................................................................................61

4 ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ В ЭНЕРГЕТИКЕ........................................64

4.1 Линейные оптимизационные задачи.................................................................67

4.1.1 Симплекс-метод.........................................................................................67

4.1.2 Транспортная задача.................................................................................73

4.2 Нелинейные оптимизационные задачи.............................................................87

4.3 Многокритериальные оптимизационные задачи.............................................90

БИБЛИОГРАФИЧЕСКИЙ СПИСОК......................................................................93

100