ИССЛЕДОВАНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ЭЛЕКТРОСНАБЖЕНИЯ ЭЛЕКТРИФИЦИРОВАННЫХ ЖЕЛЕЗНЫХ ДОРОГ

Государственная Акционерная Железнодорожная Компания «Ўзбекистон темир йЎллари»

Ташкентский институт инженеров железнодорожного транспорта

На правах рукописи

ЯКУБОВ БУРХОН АБДУКАДЫРОВИЧ

ИССЛЕДОВАНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ЭЛЕКТРОСНАБЖЕНИЯ ЭЛЕКТРИФИЦИРОВАННЫХ

ЖЕЛЕЗНЫХ ДОРОГ.

Магистерская диссертация

5А 520205 – Электроснабжение

предприятий железнодорожного транспорта

Научный руководитель

кандидат технических наук

доцент Якубов М.С.

Ташкент – 2011

ОГЛАВЛЕНИЕ

Введение …………………………………………………………………	3
Глава 1. Обзор методов оптимизации основных задач электроснабжения……………………………….. ……….………	6
1.1. Основные понятия и определения ……………………………….......	6
1.2. Обзор и методология оптимизационного подхода к задачам электроснабжения	6
1.3. Перечень задач электроснабжения, рекомендуемые решению оптимизационными методами	13
1.4. Математические модели основных элементов систем электроснабжения	15
Выводы по первой главе……………………………………………..	18
Глава 2. Нелинейные оптимизационные задачи электроснабжения	19
2.1. Общие положения…………………………………………………..	19
2.2. Графическая иллюстрация задачи нелинейного программирования	21
2.3. Градиентные методы	23
2.4. Метод неопределенных множителей Лагранжа	31
2.5. Задача оптимального распределения активной мощности в Энергосистеме	34
2.6. Задачи оптимального распределения компенсирующих устройств в системах электроснабжения	36
Выводы по второй главе …..……………………………………….........	42
Глава 3. Оптимизационные задачи с целочисленными и дискретными переменными……………………………………………………………….…	48
3.1. Задачи с целочисленными перемнными	48
3.2. Двоичные переменные	51
3.3. Задачи с дискретными переменными	53
Выводы по третьей главе ……………………………………….......	58
Глава 4. Оптимизационные задачи при случайной исходной информации и многокритериальные задачи	59
4.1. Основные понятия	59
4.2. Математические модели стохастических задач	62
4.3. Детерминированный эквивалент стохастической задачи	63
4.4. Оптимизационные задачи при недетерминированной исходной Информации	68
4.5. Многокритериальные оптимизационные задачи	76
4.6. Определение коэффициентов веса каждого критерия	76
4.7. Оптимизация по обобщенной целевой функции	77
Выводы по четвертой главе	80
Заключение …………………………………………………….............	81
Список использованной литературы…………………….....................	83
Приложения ……………………………………………………............	86

Введение

Актуальность работы. Развитие рыночных отношений в электроэнергетике, высокие требования к надежности и качеству электрической энергии, интенсификация технологических процессов, влияющих на режимы работы электроустановок неизбежно ведет к необходимости оценки их влияния и на проблему оптимизации схем и параметров электроснабжения. Эти основные часты сохраняются все основные принципиальные черти системного похода при планировании самых различных производственных систем, а также особенностей изучаемой системы и типа решаемой задачи.

В настоящее время задачи оптимизации приобрели большое значение особенно в отрасли электроэнергетики. Электроэнергетика пронизывает всё народное хозяйство и образует иерархию больших управляемых систем, управление развитием и функционированием которых возможно только на основе современных методов оптимизации.

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

Цель работы. Целью диссертационной работы являются разработка и исследование математической моделей оптимизации периодичности профилактических работ, основного электрооборудования подстанций а также формирование модели, критерия оптимальности а также ограничений при распределении установок реактивной мощности.

Задачи исследования. Для достижения поставленной цели необходимо решение следующих задач:

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

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

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

- рассчитать оптимальное распределение заданной суммарной мощности компенсирующих устройств.

Научная новизна. Впервые к задачам оптимизации электроснабжения сделан методологический подход, объединяющий ряд задач, в в зависимости от технической и экономической исходной информации и целесообразности решения конкретной задачи оптимизационным методом.

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

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

Важним результатом является вывод о том, что при экономической оптимизации электроснабжения критерий надежности выступает в виде система ограничений.

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

Апробация работы. Основные результаты и положения диссертации доложены и обсуждены на научно–практических конференциях «Ёш илмий тадиодчи» с участием зарубежных ученых (Ташкент, 2009-2011г.),

Публикация: По результатом работы опубликовано 2 тезисы доклада на конференциях, проведенных в ТашИИТ.

Работа выполнена в Ташкентском институте инженеров железнодорожного транспорта на кафедре «Электроснабжение и микропроцессорное управление» (2009-2011 г.)

Структура работы. Диссертационная работа состоит из введения, 4 глав, общих выводов, заключения, списка использованной литературы, содержащего 31 отечественных и зарубежных источника, и приложения.

1 Глава. Обзор методов оптимизации основных задач электроснабжения

1.1. Основные понятия и определения

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

Система электроснабжения – это созданная человеком совокупность электроустановок, взаимно связанных с целью обеспечения производственных объектов электроэнергией номинального качества или и необходимого свойства. Свойство системы осуществлять одновременно и взаимосвязано процессы производства, передачи и распределения электроэнергии присуще системе, но не отдельным её элементам. Например, поток мощности по линии, соответствующий пределу статической устойчивости системы, обычно не равен предельному потоку этой же линии, взятой отдельно.

Структура системы – это строение, устройств системы, определяемое составом основных частей системы, их взаимосвязью и взаиморасположением. Под структурой электроснабжения понимают её основной состав – подстанции и основную электрическую сеть.

Производственно – экономическая система электроснабжения подразделяются на два типа – динамические и статические.

Динамическая система в технико – экономическом смысле – это система с переменными во времени составом параметров и характеристиками.

1.2. Обзор и методология оптимизационного подхода к задачам электроснабжения

Развитие рыночных отношений в электроэнергетике, высокие требования к надежности и качеству электрической энергии, интенсификация технологических процессов, влияющих на режимы работы электроустановок неизбежно ведет к необходимости оценки их влияния и на проблему оптимизации схем и параметров электроснабжения.

На основании анализа ряда фундаментальных работ, посвященных проблеме оптимизации [1,…5,6,7,8,9,10], задачи оптимизации электроснабжения электрифицированных железных дорог, также подразделяется на две основные группы:

К первой группе можно отнести, выбор оптимальных схемных решений электроснабжения, характеристик её электроустановок, а также электрический расчет схем для обеспечения технических характеристик установок в процессе определения эксплуатационно-технических характеристик. Ко второй группе относятся режимные задачи, прогнозирование надежности и стратегии оптимальной периодичности профилактического обслуживания электроустановок и пр.

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

В настоящее время методы поиска оптимума можно разделить на две группы: классические и алгоритмические [13].

К классическим методам относятся: дифференциальное исчисление [14], вариационное исчисление [15], динамического программирования максимума Понтрягина.

Алгоритмические методы в свою очередь подразделяются на детерминированные и случайные. К детерминированным методам поиска относятся:

итерационные [14];

градиентные [17];

направленного перебора [18];

линейного программирования [2,7];

нелинейного программирования [19];

к случайным методам поиска относятся;

методы Монте - Карло [14];

методы случайного перебора [4, 20].

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

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

1) по обеспечению физической реализуемости схемных решений, а также допустимых технических характеристик электроустановок;

2) по обеспечению требуемых уровней выходных параметров (тока, напряжения, мощности, качество электроэнергии, ).

3) ограничения, учитывающие статическую информацию, полученной при длительной эксплуатации и испытаниях аналогичных схем и их элементов;

4) часть ограничений могут иметь неполную или неопределенную информацию о законах изменения их параметров надежности, приводящик к применению оценочных моделей со всеми их достоинствами и недостатками.

Второй особенностью оптимизационных моделей задач электроснабжения являются: необходимость системного подхода, наличие особенностей больших систем, и учет необходимости её развития, т.е. рассмотрение её как динамической системы. Это противоречие нужно решать математически компромиссно, путем взаимных уступок.

Генеральным направлением сохранения надлежащей надежности электроснабжения является математическое формализация нормированных допустимых и необходимых значений, коэффициентов статической устойчивости с сохранением динамической устойчивости [4, 5, 6]. Следовательно при экономической оптимизации электроснабжения критерий надежности выступает в виде системы ограничения. Это является третьей особенностью оптимизационных задач электроснабжения.

Сложность учета этих особенностей заключается в том ,что при этом ограничивается использование упомянутых выше оптимизирующих моделей, имеющие с точки зрения общности решения задач, но с определенными недостатками, заключающиеся в обязательном применении итерационных методов оптимизации, т.к. надёжностные показатели имеют в большинстве случаев нелинейный характер. Например, вероятность безотказной работы однотрансформаторной подстанции, с последовательным соединением ЛЭП, разъединителя, выключателя, силового трансформатора проводов кабелей и пр. через интенсивность отказов определяется как вероятность безотказной работы всех элементов в течении времени t [11]:

где - интенсивность отказов.

А. вероятность безотказной работы систем электроснабжении с резервированием замещением, т.е. параллельном соединении определяется надежностью не только основных электроустановок но и устройств АВР, которые также выражаются через экспоненциальные законы.

Использование для определения экстремума целевой функции аналитических методов в электроснабжении связано со значительными трудностями. Для их преодоления вводится значительное количество допущений и упрощений, приводящих к тому, что результаты аналитической оптимизации даже для простых схем практически трудно реализуемы. От этого недостатка свободны алгоритмические методы, учитывающие только способ отыскания экстремума [9].

Во всех методах оптимизации как и в классической постановке имеются этапы: разработки модели системы, выбор критерия оптимальности, выбор целевой функции и ограничений, поиск оптимального решения и анализ полученных погрешностей.

Модель системы строится исходя из задачи оптимизации с учетом ограничений, требуемой точности и объема имеющейся реальной исходной аналитической информации о системе электроснабжения и функциально – количественной связи электроустановок.

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

В этом смысле модели электроснабжения, описываемые математически, устанавливающими количественные связи между элементами модели будут экономическими т.к. электроснабжение относятся к число систем, структура которых считаются достаточно хорошо известными. К ним, например можно отнести вероятностные модели надежности системы и их электроустановок с восстановлением и профилактической [11], логико-вероятностие методы расчета надежности с помощью дерева отказа, периодичность профилактического обслуживания основного силового оборудования на основе параметра потока отказов, выбор места установки батарей компенсирующих реактивную мощность, описываемые в интервале времени нормальной системой независимых дифференцируемых уравнениями, связывающих k выходных параметров системы с параметрами состояния (Е) и управляемыми параметрами (П) (системы профилактически обслуживаю профилактические работы и т.д.).

(1.1)

где

с ограничением в виде

(1.2)

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

В транспортных задачах электроснабжения, таких как ограничение передаваемой мощности по существующим линиям с учетом допустимых нагревов её проводов, расчет передачи мощности через транспортные узлы и др., целевая функция представляет собой сумму произведений удельных стоимостей Zij на величины передаваемых мощностей Xij от узла i к узлу j:

(1.3)

где n, m- соответственно количество источников и количество потребителей.

Для оптимизации таких функций составляется транспортная матрица с применением симплекс-метода, распределительного метода потенциалов

Особую группу составляют оптимизационные задачи при случайной исходной информации. К ним можно отнести, например, задачи расчетов мощности нагрузок, изменения напряжений в узлах эксплуатируемых систем электроснабжения, расчет оптимальной периодичности проведения профилактических ремонтов основного электрооборудования и др., решаемых методами статического программирования. В этих задачах случайные величины, являющиеся коэффициентами целевой функции, должны быть заменены их математическими ожиданиями с последующим получением детерминированного эквивалента целевой функции:

(1.4)

Если случайными величинами являются коэффициенты или , то, детерминированными эквивалентами -го ограничения будут соответственно выражения:

(1.5)

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

Обобщенная целевая функция многокритериальных многопараметрических задач электроснабжения записывается следующим образом:

(1.5)

где zk – целевая функция, выражающая k-й критерий.

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

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

S – количество принятых критериев.

Деленные zk на нормированное значение Zkнор приводит каждую целевую функцию к единым относительным единицам.

Решение многокритериальных задач не требует специфики по сравнению с однокритериальной задачей.

Решение выше приведенных систем выполняется известными методами вычислительной математики. При линейной системе используется метод Гаусса, а при нелинейной – метод Ньютона с помощью программного обеспечения Excel. 7.0.

1.3. Перечень задач электроснабжения, рекомендуемые решению оптимизационными методами.

Вопрос оптимального управления ресурсами в системе электроснабжения в настоящее время имеет первостепенное значение. В литературе имеется достаточное число опубликованных работ, отражающих управление ресурсами при решении вопросов обеспечения надежности и качества электроэнергии. Назрела необходимость разрешить перечень задач, решаемых оптимизационными методами как на стадии практирования так на стадии эксплуатации, модернизации и реконструктирования.

Необходимо сказать что оптимизационные методы приминяются при решении прямой задачи, обеспечивающие наиболее эффективное значение рассматриваемы показателей надежности и качества электроэнергии при заданных затратах, так и решении обратной задачи, при котором заданное значение показателей достигается при минимальных затратах.

Ниже приведем основные задачи электроснабжения электрифицированных железных дорог решаемых на различных стадиях с учетом известных в настоящая время математических методов оптимизации [1,2, 11].

1. Оптимизация схемы электрической сети по критерию минимума удельных затрат.

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

3. Расчет расстояний между тяговыми подстанциями и их нагрузок:

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

5. Оптимальное резервирование тяговых подстанций по мощности.

6. Распределение заданных компенсирующих устройств по узлам потребления с учетом минимума суммарные затраты и минимума потерь активной мощности.

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

8. Оптимизация технического с учетом экономического обслуживания ущерба.

9. Оптимизация периодичности профилактического обслуживания тяговых трансформаторов.

10. Одноцелевая оптимизация при вероятностной и неопределенной информации.

11. Электроэнергии и охраны окружающей среды.

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

13. Оптимизация нагрузок ТП с учетом их внешних характеристик.

14. Оптимизация расчетов по заданному графику движения.

15. Расчет допустимой несимметричности нагрузки трехфазной системы (критерий напряжение обратной последовательности).

16. Оптимизация компенсирующих устройств и коэффициента мощности при поперечной и продольной мощности.

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

18. Оптимальное распределение числа поездов и интервалов в рассматриваемой зоне.

19. Оптимальный уровень напряжения в тяговой сети.

20. Оптимизация показателей надежности система электроснабжения.

21. Оптимальное резервирование элементов системе электроснабжения.

22.Оптимизационные задачи электроснабжения с целочисленными и дискретными переменными.

23. Оптимизационные стохастические задачи электроснабжения.

24. Оптимизационные задачи электроснабжения по обобщенной целевой функции.

1.4. Математические модели основных элементов систем электроснабжения

При технико – экономическом исследовании, заключающемся в экономическом обосновании принимаемых технических решений, необходимо иметь математическую модель, отражающую основные свойства и закономерности исследуемого объекта.

Рассматриваемые в данной работе математические модели элементов системы электроснабжения характеризуется не только физическими величинами, но и стоимостными показателями. Их можно назвать технико-экономическими моделями.

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

А. Линия электропередачи (ЛЭП). Пусть имеем ЛЭП длиной l, км, и напряжением u, кв. Затраты на потери электроэнергии в линии З, т.руб/год. определяются, как известно, выражением [3]:

где S – передаваемая мощность, кВ.А;

F – сечение проводов, мм2;

Зэ – удельные затраты на компенсацию потерь электроэнергии,

сум/кВт.ч.;

p – удельное сопротивление материала проводов линии;

- время потерь, ч/год.

Рассматриваемый показатель зависит от ряда свойств ЛЭП, которые характеризуются соответствующими величинами. Каждая из этих величин с математической точки зрения может рассматриваться в качестве независимой переменной, получающей новое численное значение при изменении исходных условий. Изменение любой из этих величин приведет к образованию нового варианта и изменению затрат. Однако с экономической точки зрения существенным для изменения затрат оказывается изменение не отдельных величин, а их вполне определенные совокупности. Например, если уменьшились удельные затраты Зэ , а время потерь во столько раз увеличилось, то затраты Зэ – остаются неизменными.

Существенные величины, значения которых требуется обосновать в процессе решения технико-экономических задач, называются оптимизируемыми параметрами. Все же остальные величины, объединяем в обобщенные константы. Они характеризуют исходные данные решаемой задачи.

Например, если оптимизируемым параметром является сечение проводов F, то выражение (6) можно записать в виде

где

Если же оптимизируемыми параметрами будут величины F и u то выражение (7) примет вид:

Таким образом, в зависимости от характера решаемой задачи одна и та же величина может выступать то как константа, известная до решения задачи, то как оптимизируемый параметр, численное значение которого требуется экономически обосновать в процессе решения задачи. Так как в практических расчетах приходится учитывать не один эффект, а несколько, модель линии электропередачи усложняется. Например, если в качестве технико-экономической модели линии принять выражение приведенных затрат, то модель ЛЭП будет иметь вид [4]:

Здесь , руб./км, и , руб./км мм2, характеризуют соответствующие удельные затраты на строительство характеризуют соответствующие удельные затраты на строительство 1 км линии.

С увеличением сечения проводов затраты на строительство ЛЭП увеличиваются, а затраты на потери энергии снижаются, т.е. по сечению проводов в формуле затрат образуются конкурирующие группы эффектов. Само же сечение можно рассматривать в качестве оптимизируемого параметра, численное которого нужно определить на стадии анализа исследуемого объекта. Объединяя все величины, за исключением оптимизируемого параметра , в обобщенные константы отдельных эффектов в формуле (9), можно записать в виде

Это формула и рассматривается в дальнейшем как один из возможных вариантов обобщенной технико-экономической модели линии электропередачи. В некоторых случаях в качестве оптимизируемого параметра также рассматривают u. В этом случае в качестве другой модели линии можно иметь в виду формулу

В этой модели два оптимизируемых параметра: сечение проводов F и напряжение линии u. По каждому из оптимизируемых параметров в модели имеются конкурирующие эффекты. Обобщенные константы и объединяют целую совокупность свойств отдельных эффектов исследуемого объекта, но не включают оптимизируемые параметры.

Рассмотренные технико-экономические модели (9), (11) справедливы для линии электропередач переменного тока напряжением до 110 кВ включительно. для линий напряжением выше 110 кВ необходимо применять более сложные модели, учитывающие большее количество эффектов, характерных для электропередач данного класса напряжений (например, корона).

Выводы по первой главе

1. Особенностью оптимизационных задач электроснабжения электрифицированных железных дорог является необходимость применения как классических так и алгоритмических методов, так как в них необходимо комплексное определение требуемых характеристик электроустановок и режимов работы систем, обеспечивающих оптимальный уровень безотказности заданной структуры с учетом ограничений технических характеристик, определяющих качество функционирования.

2. Второй особенностью оптимизационных моделей задач электроснабжения являются: необходимость системного подхода, наличие особенностей больших систем, и учет необходимости её развития, т.е. рассмотрение её как динамической системы. Это противоречие нужно решать математически компромиссно, путем взаимных уступок.

ГЛАВА 2

Нелинейные оптимизационные задачи электроснабжения

2.1. Общие положения

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

(2.1)

п переменных, при т ограничениях, заданных в форме равенств и (или) неравенств

(2.2)

и граничных условиях, задающих диапазон изменения переменных

(2.3)

Если в математической модели оптимизационной задачи имеются нелинейные зависимости, для решения этой задачи используются методы нелинейного программирования.

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

Как уже отмечалось, нелинейная целевая функция может иметь один или несколько экстремумов. Существующие методы нелинейного программирования позволяют найти один экстремум целевой функции и не дают ответа на вопрос: является ли этот экстремум локальным или глобальным?

Поэтому при многоэкстремальной целевой функции диапазон изменения переменных (1.3) разбивается на ряд более узких диапазонов, например

(2.4)

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

Для случая (1.4) оптимизационная задача решается трижды: в диапазоне изменения переменных в диапазоне а, и в диапазоне В результате получаем три локальных экстремума. Из трех локальных экстремумов выбирается глобальный экстремум.

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

Из курса высшей математики известно, что в точке экстремума (минимума, максимума) нелинейной функции все ее частные производные равны нулю. Следовательно, для нахождения экстремума нелинейной функции п переменных необходимо определить ее частные производные по всем переменным и приравнять их к нулю. Решение полученной системы п уравнений с п неизвестными даст значения переменных, при которых достигается экстремум функции.

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

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

В большинстве практических оптимизационных задач искомые переменные принимают только положительные или нулевые значения. В этом случае граничные условия имеют вид

(2.5)

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

2.2. Графическая иллюстрация задачи нелинейного программирования

Графическую иллюстрацию нелинейной оптимизационной задачи рассмотрим для случая двух переменных х1 и х2. Пусть нелинейная целевая функция

(2.6)

имеет вид, показанный на рис. 2.1.

Рис. 4.1. Нелинейная целевая функция и ее представление

линиями равного уровня

Пересечем функцию Z плоскостями, параллельными горизонтальной плоскости. Точки пересечения спроектируем на плоскость х1, х2. На плоскости х1, х2 получим замкнутые концентрические кривые. На каждой из этих замкнутых кривых значение целевой функции неизменно

(2.7)

Полученные замкнутые кривые Z = const называются линиями равного уровня целевой функции Z. Напомним, что для линейной задачи линии равного уровня Z=const представляли собой прямые линии (рис. 2.2).

Таким образом, нелинейную функцию двух переменных Z(х1, х2) можно представить в двумерной плоскости х1, х2 линиями равного уровня Z=const. Эти концентрические линии стягиваются в точку с координатами х10 и х20, являющуюся минимумом целевой функции Z.

Ограничения (4.2) могут быть линейными и нелинейными, заданными в виде неравенств или равенств. Как было показано при рассмотрении задач линейного программирования, линейные ограничения представляют собой прямые линии. Очевидно, что нелинейные ограничения будут представлять собой кривые линии. При ограничениях-равенствах допустимые значения переменных принадлежат прямой (кривой) линии, при ограничениях-неравенствах допустимые значения переменных принадлежат полупространству, расположенному по одну сторону от прямой (кривой) линии.

На рис. 2.2 показан случай, когда два ограничения 1 и 2 являются линейными неравенствами, а одно ограничение 3 - нелинейным неравенством. Штриховка у каждого ограничения направлена в сторону допустимых значений переменных.

Рис. 2.2. Иллюстрация области допустимых значений переменных и относительного минимума функции Z

Как и в случае линейной задачи, система ограничений (4.2) образует в пространстве переменных х1, и х2 область допустимых значений переменных. В общем случае эта область представляет собой замкнутый многогранник (многогранник аbс на рис. 2.2) с прямолинейными и криволинейными гранями.

При рассмотрении линейной задачи было показано,, что оптимальное решение всегда лежит в одной из вершин многогранника . Для нелинейной оптимизационной задачи это условие может не выполняться. Оптимальное решение может лежать на одной из граней области или внутри этой области.

Для случая, приведенного на рис. 2.2, оптимальному решению соответствует точка с координатами и лежащая на грани ас области . Эта точка представляет собой относительный минимум функции Z, т.е. минимум функции Z при наличии ограничений.

2.3. Градиентные методы

Как следует из названия, эти методы решения нелинейных оптимизационных задач используют понятие градиента функции. Градиентом функции Z(x1, х2 ... хn) называется вектор

(2.8а)

где - единичные вектора (орты).

Величина этого вектора определяется по выражению

(2.8)

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

Физический смысл градиента функции в том, что он показывает направление (2.8а) и скорость (2.8) наибольшего изменения функции в рассматриваемой точке. Если в некоторой точке , функция в этой точке не изменяется (не возрастает и не убывает). Эта точка соответствует экстремуму функции.

Сущность градиентных методов решения нелинейных оптимизационных задач поясним для случая отыскания абсолютного минимума функции двух переменных Z(х1,х2), иллюстрируемого рис. 2.3. Этот минимум находится в точке с координатами x10 и x20.

В соответствии с граничными условиями (2.5) областью допустимых значений переменных будет первый квадрант системы координат и х1 и х2. В этой области произвольно выберем исходное (нулевое) приближение - точку с координатами . Значение целевой функции в этой точке составляет Z0. В соответствии с выражением (2.8) вычислим в этой точке величину градиента функции Z.

Рис. 2.3. Иллюстрация градиентного метода с постоянным шагом =1

Выполним шаг единичной длины (=1) в направлении убывания функции Z. В результате выполненного шага получим первое приближение - точку с координатами . Значение целевой функции в этой точке составляет Z1.

Далее вычислительная процедура повторяется: последовательно получаем 2-е, 3-е и 4-е приближения - точки с координатами ; и . Значения целевой функции в этих точках соответственно составляют Z2, Z3 и Z4.

Из рис. 2.3 видно, что в результате вычислительного процесса последовательно осуществляется "спуск" к минимуму функции Z. Вычислительная процедура заканчивается, когда относительное изменение целевой функции на предыдущем i-м и последующем (i+1)-м шагах оказывается меньше заданной точности вычислений е:

(2.9)

Рассмотренная вычислительная процедура носит название градиентного метода с постоянным шагом. В этом методе все шаги выполнялись одинаковой длины Метод достаточно прост. Основной его недостаток - большая вероятность зацикливания вычислительного процесса в окрестности минимума функции Z. В соответствии с рис. 4.3 вычислительный процесс зациклится между точками с координатами и . При этом в качестве искомого решения следует принять одну из этих точек.

Для получения более точного результата необходимо выбрать шаг меньшей длины. При этом объем вычислений (количество шагов) увеличится.

Таким образом, точность и объем вычислений в градиентном методе с постоянным шагом определяются величиной этого шага.

Метод покоординатного спуска. Как и в предыдущем методе, выберем исходное (нулевое) приближение - точку с координатами (рис. 2.4). Значение целевой функции в этой точке составляет z . В соответствии с выражением (2.8) вычислим частные производные целевой функции Z. Из совокупности частных производных выберем наибольшую по модулю производную. Пусть это будет производная Следовательно, в направлении переменной х2 функция Z имеет наибольшее изменение. Если производная положительная, при увеличении переменной х2 функция увеличивается. Если производная отрицательная, при увеличении переменной х2 функция уменьшается.

Рис. 2.4. Иллюстрация метода покоординатного "спуска"

Осуществляем "спуск" по переменной х2 в направлении уменьшения целевой функции (выполняем единичные шаги ). Последовательно получаем 1-е, 2-е, 3-е приближения - точки с координатами На каждом шаге вычисляем значение целевой функции: Пусть

Следовательно, 3-й шаг в направлении переменной х2 выполнять нецелесообразно, целевая функция начинает увеличиваться. Осуществляется возврат в предыдущую точку с координатами .

Из точки с координатами продолжаем "спуск" в направлении другой переменной х1 Единичные шаги () в направлении переменной Xi выполняются до тех пор, пока целевая функция не начнет увеличиваться Получаем точки с координатами

Вычислительная процедура повторяется до достижения точности, соответствующей выбранному шагу. Если в некоторой точке, например с координатами единичный шаг по любой переменной приводит к увеличению целевой функции, процесс заканчивается. Точка с координатами находится в окрестности минимума целевой функции Z.

Метод скорейшего спуска. Как было отмечено выше, точность и объем вычислений в градиентных методах с постоянным шагом X определяются величиной этого шага. При увеличении длины шага объем вычислений (количество шагов) уменьшается, однако уменьшается и точность определения минимума целевой функции. При уменьшении длины шага точность увеличивается, однако объем вычислений (количество шагов) возрастает.

Поэтому вопрос о выборе рациональной длины шага в градиентных методах является своего рода оптимизационной задачей.

Один из способов определения оптимальной длины шага иллюстрируется на рис. 2.5 и носит название метода скорейшего "спуска".

Рис. 2.5. Иллюстрация метода скорейшего "спуска" (а) и параболическая аппроксимация целевой функции для выбора оптимального шага (б)

Начало вычислительной процедуры такое же, как и в градиентном методе с постоянным шагом:

принимается исходное (нулевое) приближение ;

вычисляется значение целевой функции в этой точке Z0;

в соответствии с выражением (2.8) для этой точки вычисляется grad Z.

Из исходной точки в направлении убывания целевой функции выполним два единичных шага (). В конце каждого шага вычислим значения целевой функции Z1 и Z2.

Итак, имеем три значения целевой функции Z0,Z1 и Z2, отвечающие нулевой (=0), единичной (=1) и двойной (=2) длинам шага (рис. 2.5,6). Эти три значения характеризуют сечение целевой функции Z в выбранном направлении "спуска".

Известно, что через три точки можно провести единственную параболу

(2.10)

где а, b, с - постоянные коэффициенты.

Определим координату минимума этой параболы, для чего приравняем к нулю первую производную функции (4.10) по переменной

(2.11)

откуда = -b/2а.

Полученное значение и будем считать оптимальной длиной шага опт.

Выполненная процедура называется параболической аппроксимацией сечения целевой функции Z. Заметим, что для аппроксимации сечения целевой функции Z могут использоваться и другие стандартные кривые, например гипербола.

Итак, из исходной точки (рис. 2.5,а) следует выполнить шаг длиной опт. В результате получается первое приближение - точка с координатами Вычисляется значение целевой функции в этой точке Z1.

Из точки с координатами вычислительная процедура повторяется. Получаем следующее приближение - точку с координатами и значением целевой функции Z2 . Процесс продолжается до достижения требуемой точности в соответствии с соотношением (2.9).

В методе скорейшего спуска, по сравнению с градиентным методом с постоянным шагом, количество шагов меньше, точность получаемого результата выше, отсутствует зацикливание вычислительного процесса, однако объем вычислений на одном шаге больше.

Метод проектирования градиента. Рассмотренные выше градиентные методы предполагали отыскание абсолютного минимума целевой функции Z. При наличии в математической модели ограничений (2.2) ищется уже не абсолютный, а относительный минимум целевой функции Z.

Рассмотрим один из методов отыскания относительного минимума целевой функции, получивший название метода проектирования градиента. Для упрощения алгоритма метода допустим, что имеется одно ограничение в виде линейного неравенства

(2.12)

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

Рис. 2.6. Иллюстрация метода проектирования градиента

Начало вычислительной процедуры такое же, как и в предыдущих методах:

в области принимается исходное (нулевое) приближение ;

вычисляется значение целевой функции в этой точке z ;

в соответствии с выражением (2.8) в этой точке вычисляется градиент целевой функции grad Z;

из исходной точки в направлении убывания целевой функции выполняется шаг.

Выбор величины шага может осуществляться различным образом. Выберем шаг в соответствии с алгоритмом метода скорейшего "спуска" и получим первое приближение - точку с координатами . Вычисляется значение целевой функции в этой точке Z1.

Необходимо проверить, принадлежит ли точка с координатами области Q допустимых значений переменных. Для этого проверяется неравенство (4.12), в которое подставляются координаты :

(2.13)

Если это неравенство выполняется, вычислительный процесс продолжается.

Из точки с координатами Х\1, х2 выполняется следующий шаг. В результате этого шага имеем второе приближение - точку с координатами . Значение целевой функции в этой точке Z .

Пусть для этой точки неравенство

не выполняется. Следовательно, точка с координатами вышла из области Q и необходимо выполнить возврат в эту область.

Возврат в область Q выполняется следующим образом. Из точки с координатами опускается перпендикуляр на прямую , т.е. конец вектора () проектируется на эту прямую. В результате получается новое приближение - точка с координатами которая принадлежит области Q. В этой точке вычисляется значение целевой функции Z3.

Дальнейший "спуск" к относительному минимуму целевой функции продолжается из точки . На каждом шаге вычисляется значение целевой функции и проверяется принадлежность нового приближения к области Q. Вычислительный процесс заканчивается при выполнении условия (2.9).

2.4. Метод неопределенных множителей Лагранжа

Естественно что решение задач условной оптимизации значительно сложнее решения задач безусловной оптимизации. Естественно стремление сведения задачи условной оптимизации (поиска относительного экстремума) к более простой задаче безусловной оптимизации (поиска абсолютного экстремума). Такая

процедура осуществляется в методе Лагранжа. Рассмотрим сущность этого метода.

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

(2.14)

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

(2.15а)

Ограничения-неравенства преобразуются в равенства, а свободные члены переносятся в левые части ограничений, т.е. система (2.15а) приводится к виду

(2.15)

В соответствии с методом Лагранжа вместо относительного экстремума функции (2.14) при ограничениях (2.15) ищется абсолютный экстремум функции Лагранжа, которая имеет следующий вид:

(2.16)

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

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

Доказано, что относительный экстремум целевой функции (2.14) при ограничениях (2.15) совпадает с абсолютным экстремумом функции Лагранжа (2.16).

Поиск абсолютного экстремумам функции (2.16) выполняется известными методами. В частности, определяются и приравниваются к нулю частные производные функции Лагранжа:

2.17

Последние т уравнений представляют собой ограничения (2.15) оптимизационной задачи.

Система (2.17) содержит (т+п) уравнений и такое же количество неизвестных.

Решение системы (2.17) даст координаты абсолютного минимума функции Лагранжа (2.16) или относительного минимума целевой функции (4.14) при ограничениях (2.15).

Решение системы (2.17) выполняется известными методами вычислительной математики. Если система (2.17) линейная, используется, как правило, метод Гаусса. Если система (2.17) нелинейная - метод Ньютона.

2.5. Задача оптимального распределения активной мощности в

энергосистеме

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

В существующей энергосистеме необходимо так распределять активную нагрузку между электростанциями, чтобы затраты на выработку электроэнергии были бы минимальными. Основной составляющей этих затрат является стоимость топлива. Поэтому в качестве минимизируемой целевой функции примем суммарный расход топлива в энергосистеме.

Пусть в энергосистеме имеется п тепловых электростанций. Для агрегатов каждой электростанции известны расходные характеристики, т.е. зависимости расхода топлива В от активной мощности Р; вырабатываемой станцией. Эти расходные характеристики имеют нелинейный характер и следующий общий вид:

(2.18)

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

(2.19)

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

(2.20)

Выражение баланса активной мощности (2.20) и является техническим ограничением в рассматриваемой оптимизационной задаче.

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

. (2.21)

Соотношения (2.19), (2.20) и (2.21) представляют собой математическую модель поставленной оптимизационной задачи.

Для решения воспользуемся методом Лагранжа. Составим функцию Лагранжа

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

(2.23)

Из системы (2.23) следует, что она имеет решение при условии

(2.4)

и выполнении баланса мощности (2.20).

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

2.6. Задачи оптимального распределения компенсирующих устройств в системах электроснабжения

Большинство потребителей электроэнергии кроме активной мощности потребляет и реактивную мощность. В отличие от активной мощности реактивную мощность можно получить непосредственно у потребителей от специальных источников реактивной мощности.

Расстановка источников реактивной мощности в схеме электроснабжения называется компенсацией реактивной мощности, а сами источники - компенсирующими устройствами. Подробно вопросы компенсации реактивной мощности рассматриваются в специальных курсах.

Основная идея компенсации реактивной мощности заключается в следующем. Рассмотрим простейшую схему электроснабжения (рис. 2.7), включающую в себя линию с активным сопротивлением R, связывающую источник питания напряжением U и потребитель мощностью P+jQ.

Рис. 2.7. Простейшая схема компенсации реактивной мощности

Потери активной мощности в линии при отсутствии у потребителя компенсирующего устройства (Qk=0) составляют

(2.25)

при установке у потребителя компенсирующего устройства (Qk0) эти потери уменьшатся до величины

(2.26)

Таким образом, компенсация реактивной мощности позволяет уменьшить потери активной мощности в схеме электроснабжения и,

следовательно, улучшить технико-экономические показатели этой схемы.

Из выражений (2.25) и (2.26) видно, что потери мощности АР имеют две составляющие: потери от протекания по линии активной мощности Р и потери от протекания по линии реактивной мощности Q или (Q-Qk). Поскольку компенсация реактивной мощности влияет только на вторую составляющую потерь, в дальнейшем будем рассматривать потери от протекания по линиям только реактивных мощностей.

При проектировании схемы электроснабжения, как правило, минимизируются денежные затраты на эту схему. Снижение потерь мощности за счет установки компенсирующих устройств уменьшает затраты на схему, поскольку каждый потерянный кВт мощности необходимо выработать на электростанциях и, следовательно, затратить на это денежные средства. Однако и компенсирующие устройства требуют денежных затрат.

В связи с этим возникает задача определения оптимальной мощности компенсирующих устройств, отвечающей минимуму суммарных затрат. Такая задача относится к задаче безусловной оптимизации и может быть решена, например, градиентными методами.

Для системы электроснабжения величина суммарной мощности компенсирующих устройств Qk может быть заданной какими-то техническими условиями. В этом случае заданную мощность Qk требуется оптимальным образом распределить внутри системы электроснабжения. Это уже задача условной оптимизации и решается, например, методом Лагранжа.

Рассмотрим такую задачу для радиальной схемы электроснабжения (рис. 2.8). Источник питания имеет напряжение U. От этого источника питаются п потребителей с реактивными мощностями Q1, Q2…Qn. Активные сопротивления линий между источником и потребителями составляют R1, R2, … Rn. У каждого i-ro потребителя может устанавливаться компенсирующее устройство мощностью Qki.

Требуется найти оптимальное распределение между потребителями 1, 2,…п заданной суммарной мощности «компенсирующих устройств Qk. Критерий оптимальности – минимум потерь активной мощности в схеме.

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

(2.27)

Рис.2.8. Радиальная схема электроснабжения

Относительный минимум целевой функции ищется при ограничении

или (2.28)

Запишем функцию Лагранжа:

(2.29)

(2.30)

(2.31)

Рассмотрим задачу оптимального распределения заданной мощности компенсирующих устройств Qk между потребителями 1, 2,...п в магистральной схеме электроснабжения (рис. 2.9).

Подлежащая минимизации целевая функция имеет следующий вид:

Рис. 2.9. Магистральная схема электроснабжения

Относительный минимум целевой функции ищется при ограничении

или (2.33)

Запишем функцию Лагранжа

(2.34)

Для отыскания минимума функции L вычислим ее частные производные и приравняем их к нулю:

(2.35)

где

Из 1-го уравнения системы (4.35) следует, что

(2.36)

С учетом этого соотношения из 2-го уравнения системы следует, что

(2.37)

Подставив соотношения (4.36) и (4.37) в 3-е уравнение системы, получим

(2.38)

и так далее. Из третьего снизу уравнения системы (4.35) получим, что

(2.39)

Из предпоследнего уравнения системы получим

или (2.40)

Как следует из (4.40), у последнего n-го потребителя следует установить компенсирующее устройство мощностью, равной реактивной мощности этого потребителя. В таком случае говорят о полной компенсации реактивной мощности потребителя.

Из (2.39), (2.38) и (2.37) следует, что у (n-1)-го, ... 3-го и 2-го потребителей также следует выполнить полную компенсацию реактивной мощности.

Однако при расстановке компенсирующих устройств необходимо учитывать ограничение - последнее уравнение системы (2.34).

Таким образом, в магистральной схеме электроснабжения компенсирующие устройства следует устанавливать в соответствии с условиями полной компенсации реактивной мощности Qki = Qi начиная от конца магистральной схемы к ее началу (от п-го потребителя к 1-му потребителю), до выполнения условия Qki = Qk, i=l, 2,... п.

Если у i -гo потребителя это условие выполнилось, то у потребителей 1, 2, ... i-1 компенсирующие устройства не устанавливаются.

Пример. В существующей схеме электроснабжения (рис. 2.10) требуется определить мощности компенсирующих устройств QKl и Qk2 в узлах 1 и 2 исходя из условия минимума суммарных затрат на установку этих устройств и покрытие потерь активной мощности в схеме.

Исходные данные:

напряжение схемы U= 10 кВ;

сопротивления линий Ri=6 Ом, R2=4 Ом;

реактивные нагрузки узлов 1 и 2 Qi=600 квар и Q2=800 квар;

удельные затраты на установку компенсирующих устройств zo=0,5 у.е./квар;

удельные затраты на покрытие потерь активной мощности со=10 у.е./кВт.

Рис. 2.10. Схема электроснабжения

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

где

Введение числового коэффициента 1O'J необходимо для приведения всех составляющих целевой функции к одной размерности (у.е.).

Для решения задачи выберем метод покоординатного "спуска". Определим частные производные целевой функции Z по переменным Qki и Qk2.

Примем исходное приближение: Для этих значений вычислим значения целевой функции и ее частных производных:

Очевидно, что в направлении переменной Qk2 целевая функция Z убывает сильнее, чем в направлении переменной Qk1, поскольку

В направлении переменной Qk2 и начнем "спуск".

Примем величину шага =400 квар. Первое приближение (первый шаг) будет квар. Значение целевой функции

Второй шаг: квар. Значение целевой функции Z2=616y.e.

Третий шаг: квар. Значение целевой функции Z3 = 689 у.е.

Очевидно, что "спуск" по координате Qk2 целесообразно прекратить, поскольку Z:>>Z1, и вернуться к значениям переменных квар, полученным на втором шаге.

Выполним новый третий шаг =400 квар в направлении другой переменной квар, квар. Значение целевой функции Z3 = 624 у.е. Движение в направлении переменной Qk1 нецелесообразно, поскольку Z3>Z2.

Точка с координатами Qk1=0, квар находится в окрестности минимума целевой функции Z. При принятой длине шага ,=400 квар более точное решение получено быть не может.

Решение этой нелинейной задачи производится с помощью программного обеспечения Excel 7.0. Результаты решения следующие:

Qk1=183 квар, квар, Z=596 у.е.

Это решение более точное, значение целевой функции на 28 у.е. меньше, чем в методе покоординатного спуска с постоянным шагом.

Пример. В схеме электроснабжения контактной сети электрифицированной железной дороги следует распределить между узлами 1,2,3, соответственно с реактивными нагрузками Q1, Q2, Q3, заданную Q суммарную мощность компенсирующих устройств (см. рис. 1)

Рис. 2.11.

Напряжение схемы кВ. cсопротивления линий Ом; реактивные нагрузки узлов кВар;

Суммарная мощность компенсирующих устройств 500 кВар.

Критерием оптимальности в этой задаче является минимум потерь активной мощности:

где

Qi - реактивные нагрузки узлов, соответственно кВар.

Qki – устанавливаемые компенсирующие устройства

Минимум целевой функции ищется при ограничении источников реактивной мощности:

Абсолютный экстремум функции Лагранжа записывается в виде:

Минимальные значение этой функции определяются приравниванием к нулю производных по всем переменным:

Постановляя выражение из первого уравнения во второе, и третье получаем соответственно:

решая которое получите кВар;

откуда кВар. Из последнего уравнения системы (10) вычисляется кВар.

Множитель Лагранжа находится из выражения

(11)

Таким образом минимальные потери активной мощности в рассматриваемой схеме электроснабжения при ограничении суммарной мощности компенсирующих устройств составляет:

Выводы по второй главе

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

2. Одной из важных оптимизационных задач электроэнергетики является задача распределения суммарной активной мощности потребителей энергосистемы между электрическими станциями этой системы. Рассмотрим эту задачу в общем виде для наиболее простого случая, когда в энергосистеме имеются только тепловые электростанции, работающие на одном виде топлива.

3. Для электрифицируемой железной дороги. Приведен инженерный метод и расчет распределения между узлами с реактивами нагрузками заданной суммарной мощности компенсирующих устройств.

Глава 3

Оптимизационные задачи с целочисленными и дискретными переменными

3.1. Задачи с целочисленными переменными

В изложенном выше материале по решению оптимизационных задач методами линейного и нелинейного программирования все искомые переменные имели непрерывный характер. Эти переменные в заданном диапазоне изменения могли принимать любые значения.

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

хk-целое, k=1,2, ... l, (3.1)

где l - количество целочисленных переменных, l п;

п - общее количество переменных.

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

Введение дополнительных ограничений по целочисленности переменных существенно увеличивает объем вычислений и усложняет вычислительную процедуру при поиске оптимального решения. Однако в заданном диапазоне изменения переменной целочисленная переменная имеет меньшее количество значений, чем непрерывная переменная. В частности, в диапазоне 0 х 3 целочисленная переменная х имеет четыре значения (х = 0, 1, 2, 3), а непрерывная переменная - бесконечное количество значений.

Попытка решить целочисленную оптимизационную задачу методом полного перебора значений переменных приводит к очень большему объему вычислений. Так, например, в задаче с тремя целочисленными переменными и диапазоном их изменения 0 хk 10, k= 1, 2, 3 количество целочисленных решений составит 113=1331. Ясно, что для реальных оптимизационных задач метод полного перебора не приемлем.

Другая попытка решения целочисленной задачи заключается в решении этой задачи без наложения ограничений вида (3.1). В этом случае решается обычная задача с непрерывными переменными, а полученные непрерывные переменные округляются до целых чисел.

В задаче примера 2, решенной с непрерывными переменными, был получен следующий результат:

x1=0; x2=11,76; х3=8,82 изд.; значение целевой функции Z= 235,29 у.е.

Переменные х1, х2, х3 представляют собой количества изделий 1, 2 и 3-го видов и не могут быть дробными числами. Поэтому округлим непрерывные переменные до ближайших больших и меньших целых чисел. В результате получим 4 решения:

х1 = 0, х2 = 12, х3 = 9, значение целевой функции Z = 240 у.е.; решение недопустимое, поскольку не выполняются первое (20+212+39=51>50) и второе (60+5,512+49=102>100) ограничения;

x1 = 0, х2 - 12, хз = 8, значение целевой функции Z = 228 у.е.; решение допустимое, все ограничения выполняются;

x1 = 0, х2 = 11, х3 = 9, значение целевой функции Z = 229 у.е.; решение допустимое, все ограничения выполняются;

x1 = 0, х2 = 11, хз = 8, значение целевой функции Z = 217 у.е.; решение допустимое, все ограничения выполняются.

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

округление непрерывных переменных до ближайших целых чисел привело к недопустимому решению (x1 = 0, х2 = 12, х3 = 9);

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

Решение целочисленной задачи можно свести к решению непрерывной задачи, вводя дополнительно более простые ограничения, чем ограничение типа (5.1). Так для задачи примера 2 можно дополнительно ввести ограничения:

х211, х38;

х211,х39;

х212, х38;

х212, х39

и четыре раза решать задачу с непрерывными переменными. Однако и в этом случае нет гарантии, что среди решений будет оптимальное целочисленное решение.

Существуют различные методы решения целочисленных оптимизационных задач: метод отсечений, метод Беллмана, метод ветвей и границ. В частности, метод ветвей и границ основан на переборе допустимых решений, но на переборе не отдельных решений, а их групп. Такой подход сокращает общий объем вычислений.

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

Ввод исходных данных целочисленной задачи отличается от ввода исходных данных задачи с непрерывными переменными заданием дополнительных ограничений вида (3.1).

Решение задачи примера 2 с требованием непрерывними целочисленности переменных непрерывными и целочисленными переменными представлены в табл. 3.1.

Таблица 3.1

Непрерывные переменные	Целочисленные переменные
x1	x2	x3	Z	x1	x2	x3	Z
0	11,76	8,82	235,29	0	10	10	230

Из сопоставления двух решений можно сделать следующие выводы.

1. Как и следовало ожидать, значение целевой функции Z в
   целочисленной задаче ухудшилось, поскольку введено
   дополнительное ограничение: х1, х2, х3- целые.
2. Округление непрерывных переменных до целых чисел как в
   большую, так и в меньшую сторону может привести к
   неоптимальному и даже недопустимому решению.

3. Оптимальным решением целочисленной задачи может
оказаться такое решение, в котором переменные не являются
ближайшими к переменным в оптимальном решении непрерывной
задачи.

3.2. Двоичные переменные

Частным случаем целочисленных задач являются задачи, в которых искомые переменные могут принимать не любые целые значения, а только одно из двух: либо 0, либо 1. Такие переменные называются двоичными или булевыми.

Распространенными задачами с двоичными переменными являются задачи выбора оптимального решения (варианта) из определенного числа заданных решений (вариантов). Если вариант входит в оптимальное решение, то двоичная переменная, соответствующая этому варианту, равна 1. Если вариант не входит в оптимальное решение, то соответствующая двоичная переменная равна 0. Например, если линия электропередачи входит в оптимальную электрическую сеть, то двоичная переменная, соответствующая этой линии равна 1; если линия электропередачи не входит в оптимальную электрическую сеть, то соответствующая двоичная переменная равна 0.

В отличие от традиционных переменных х, двоичные переменные будем обозначать i где i =1,2, ... п.

Применение двоичных переменных позволяет накладывать на решаемую задачу целый ряд логических условий типа «если ... , то...».

Если в оптимальное решение должен входить один из двух (i и j) вариантов, то сумма переменных

(3.2)

Если в оптимальное решение должны входить и i-й и j-й варианты, то сумма переменных

(3.3)

Если в оптимальное решение может входить или не входить, каждый из двух (i и j) вариантов, то сумма переменных

(3.4)

Если при входе (не входе) в оптимальное решение i–го варианта в это решение должен войти (не войти) и j-й вариант, то

(3.5)

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

(3.6)

Очевидно, что количество логических условий типа «если ... , то ...» не ограничено.

3.3. Задачи с дискретными переменными

В ряде практических оптимизационных задач заранее известен набор допустимых решений, из которых требуется выбрать оптимальное решение. Например, одно компенсирующее устройство заданной мощности Qk можно разместить в узлах 1,2, ... п системы электроснабжения. Требуется выбрать оптимальный узел размещения компенсирующего устройства, соответствующий выбранному критерию.

В ряде других задач искомые переменные могут принимать не любые, а только определенные значения, из которых требуется выбрать значения переменных, отвечающие оптимальному решению. Например, в заданном узле системы электроснабжения нужно установить компенсирующее устройство, мощность которого может быть равной значениям Qk1, Qk2… Qkn Из этого ряда требуется выбрать оптимальное значение мощности компенсирующего устройства, соответствующее выбранному критерию.

Указанные задачи относятся к задачам выбора вариантов из числа заданных и решаются методами дискретного программирования. В этих методах наряду с традиционными переменными используются двоичные переменные, возможности которых по заданию логических условий рассмотрены в п. 3.2.

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

Пусть в оптимизационной задаче имеется п искомых переменных

xi(i=1, 2, ... n). Дискретные значения каждой переменной заданы. В оптимальное решение должны войти к переменных (k < п). Каждой переменной xi поставим в соответствие двоичную переменную 8,. Если в процессе решения задачи i=1, то переменная xi, войдет в оптимальное решение; если i=0, то переменная xt не войдет в оптимальное решение.

Целевая функция включает в себя и дискретные х1 х2, ... хn двоичные переменные

(3.7)

В систему ограничений входят и дискретные и двоичные переменные

(3.8)

К этой системе добавляются ограничения вида

(3.9)

,- двоичные, i =1, 2, ... п.

Граничные условия, как таковые, не записываем, поскольку возможные значения дискретных переменных являются заданными, а значения двоичных переменных могут быть только 0 или 1.

Не вдаваясь в подробности методов дискретного программирования, отметим, что программное обеспечение Excel 7.0 позволяет решать оптимизационные задачи с дискретными переменными. Поэтому предоставим пользователю составление математической модели оптимизационной задачи и ввод исходной

информации в компьютер, а вычислительную процедуру предоставим компьютеру.

Пример. Составить математическую модель для определения в схеме электроснабжения (рис. 3.1) оптимального узла установки компенсирующего устройства, заданной мощности Qk. Критерий оптимальности - минимум потерь активной мощности в схеме.

Исходные данные:

напряжение схемы U= 10 кВ;

сопротивления линий Ri=0,4, i?2=0,5, R3=0,6 Ом;

реактивные нагрузки узлов 1, 2 и 3 Qi=600, <22=500, <2з=400 квар;

мощность компенсирующего устройства Qk =1000 квар

Рис. 3.1. Схема электроснабжения

Решение. В рассматриваемой схеме имеются три узла 1, 2 и 3, в каждом из которых можно установить компенсирующее устройство. Обозначим переменными Qk1, Qk2 и Qk3 мощности компенсирующих устройств, размещаемых соответственно в узлах 1, 2 и 3. Это дискретные переменные, каждая из которых может принимать два значения 0 или 1000 квар.

Каждой переменной Qk1, Qk2 и Qk3 поставим в соответствие двоичную переменную 1, 2 и 3.

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

где ai=Ri/U2 (i=1,2,3).

Выражение для потерь мощности предусматривает возможность установки компенсирующего устройства в каждом из трех узлов. Однако в зависимости от величины двоичной переменной компенсирующее устройство в узле i должно быть установлено при i =1 или не должно быть установлено при i =0.

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

и - двоичные.

Величина дискретной переменной Qkl будет зависеть от значения соответствующей двоичной переменной i;. Переменная Qk, = Qk при i=l и Qki = 0 при i =0. Запишем эти условия

Qk1= Qk1;

Qk2= Qk2;

Qk3= Qk3.

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

Результаты решения задачи с помощью программного обеспечения Excel приведены в приложении П5:

1=0, 2 =1, 3 = 0, Qk1 = 0, Qk2 = 1000 квар, Qk3= 0, Р - 2010 Вт.

Таким образом, для обеспечения минимальных потерь мощности компенсирующее устройство мощностью 1000 квар следует установить в узле 2 схемы электроснабжения.

Пример. Составить математическую модель для определения оптимальной мощности компенсирующего устройства в узле 2 схемы электроснабжения (рис. 5.1). Критерий оптимальности - минимум потерь активной мощности.

Исходные данные те же, что и в примере 9. Мощность компенсирующего устройства может принимать следующие дискретные значения: 1100, 1200 или 1300 квар.

Решение. В рассматриваемом примере имеем одну дискретную переменную - мощность компенсирующего устройства во 2-м узле. Эта переменная может принимать три дискретных значения Qk1=1100, Qk2=1200 и Qk3=1300 квар. Каждому значению дискретной переменной поставим в соответствие двоичную переменную и .

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

где ai/U2 (i=l, 2, 3).

Рассмотрим ограничения. Поскольку дискретная переменная должна принять только одно значение, сумма двоичных переменных должна быть равна 1

и - двоичные.

Других ограничений нет.

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

Результаты решения задачи:

1=0, 2 =1, 3 = 0, Qk1 = 0, Qk2 = 1200 квар, Qk3= 0, Р - 1770 Вт.

Таким образом, для обеспечения минимальных потерь мощности в схеме электроснабжения величину мощности компенсирующего устройства в узле 2 следует принять равной 1200 квар.

Выводы по третьей главе

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

2. Одной из важных оптимизационных задач электроэнергетики является задача распределения суммарной активной мощности потребителей энергосистемы между электрическими станциями этой системы. Рассмотрим эту задачу в общем виде для наиболее простого случая, когда в энергосистеме имеются только тепловые электростанции, работающие на одном виде топлива.

Глава 4

Оптимизационные задачи при случайной исходной

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

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

В предыдущих главах рассматривалось решение оптимизационных задач, в которых вся исходная информация была однозначно определена. Такая информация называется детерминированной. Примером детерминированной исходной информации могут служить однозначные значения коэффициентов zi <3у и aij и bj (i=1 1, 2,...п; j=1, 2,...m) в линейной математической модели (2.1). В практических задачах далеко не всегда исходная информация бывает детерминированной.

Достаточно часто исходная информация или ее часть представляют собой случайные величины или случайные функции. В частности, мощности нагрузок в проектируемой системе электроснабжения можно считать случайными величинами, а изменения во времени напряжений в узлах существующей системы электроснабжения - случайными функциями. Для решения оптимизационных задач со случайной исходной информацией используются методы стохастического программирования.

Известно, что случайными величинами занимается раздел высшей математики - теория вероятностей. Поэтому прежде чем перейти к методам решения оптимизационных задач вспомним некоторые понятия этой теории.

Случайной величиной s называется такая величина, которая может принять то или иное значение, причем заранее неизвестно, какое именно.

Случайная величина s может быть непрерывной или дискретной. В заданном диапазоне изменения случайной величины количество значений дискретной случайной величины ограничено, а количество значений непрерывной случайной величины не ограничено. Примером непрерывной случайной величины является величина напряжения в некотором узле системы электроснабжения. Примером дискретной случайной величины является количество генераторов, одновременно работающих в энергосистеме.

Математическим ожиданием случайной величины называется ее среднее значение, полученное в результате п реализаций:

, (4.1)

где Si - значение случайной величины в i-й реализации.

Среднеквадратичное (стандартное) отклонение определяет разброс значений случайной величины относительно ее математического ожидания:

(4.2)

Важной характеристикой случайной величины служит вероятность Р появления этой случайной величины в конкретном интервале значений.

Для количественной оценки вероятности случайной величины вводится функция распределения вероятности. Допустим, что случайная величина s может принимать значения от - до +. Функция распределения P(s) этой случайной величины показывает вероятность того, что случайная величина попадет в интервал от - до s. Следовательно,

Р(-) = 0, Р(+)=1. (4.3)

Наибольшее распространение на практике получил нормальный закон распределения. В соответствии с этим законом с вероятностью 0,999 случайная величина s (-00 < s < +00) находится в интервале

M[s] - 3[s] s M[s] + 3[s], (4.4)

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

При решении практических задач достаточно часто применяют
нормальный стандартный закон распределения. Этот закон
описывает вероятность появления стандартной случайной величины , имеющей математическое ожидание М[]=0 и среднеквадратичное отклонение []=1, в интервале -3 3 (рис. 4.1).

С помощью этого графика решаются две обратные друг другу задачи. С одной стороны, определяется, каково должно быть значение случайной величины , чтобы вероятность ее появления составила, например Р()=0,8. Это значение случайной величины составляет 0,84. С другой стороны, определяется вероятность появления случайной величины, не превышающей, например значения 0,84 P (0,84). Эта вероятность составляет Р()=0,8.

Рис. 4.1. Функция распределения нормального стандартного закона

В Excel эти вычисления выполняются с помощью статистических функций НОРМСТОБР(0,8)=0,84 и НОРМСТРАСП(0,84) = 0,8 после обращения к мастеру функций fх в главном меню.

От функции распределения нормального стандартного закона можно перейти к функции распределения нормального закона любой cлучайной величины s оптимизационной задачи. Связь между этой случайной величиной стандартной случайной величиной т) выражается зависимостью

s = M[s] + [s]. (4.5)

4.2. Математические модели стохастических задач

Следует иметь в виду, что универсальных методов решения задач стохастического программирования, пригодных для всех классов оптимизационных задач, нет. Поэтому ограничимся рассмотрением математических моделей только одного класса стохастических задач, а именно, стохастических задач линейного программирования.

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

(4.6)

В детерминированной постановке оптимизационной задачи коэффициенты zi, аji и bj (i=1,2,... n; j=1,2,... m) и границы di и Di диапазона изменения переменных однозначно определены.

Если коэффициенты zi целевой функции являются случайными величинами, ищется экстремальное значение математического ожидания целевой функции

М[Z] extr; (4.7)

Если коэффициенты аji и (или) bj системы ограничений являются случайными величинами, то для каждого j-го ограничения задается значение вероятности Рзад j, с которой должно выполняться это ограничение. Вероятность выполнения каждого j-го ограничения должна быть не меньше заданной

(4.8)

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

Итак, математическая модель задачи стохастического программирования имеет следующий вид:

М[Z] extr;

(4.9)

4.3. Детерминированный эквивалент стохастической задачи

Стохастические задачи, математические модели которых представлены в виде (4.9), непосредственно решены быть не могут. Как правило, задачи со случайной исходной информацией сводят к их детерминированному эквиваленту. Для этого случайные величины заменяются их характеристиками (математическим ожиданием, стандартным отклонением) и считается, что случайная величина имеет нормальный закон распределения.

Если случайными величинами являются коэффициенты Z; целевой функции, эти коэффициенты заменяются их математическими ожиданиями. В результате такой замены получим детерминированный эквивалент целевой функции

M[Z] = M[z1]x1+M[z2]x2+...M[zn]xn extr. (4.10)

Для каждого j-го ограничения задается вероятность Рзад j с которой должно выполняться это ограничение. По значению Рзад j находится значение стандартной случайной величины . С учетом соотношения (4.5) осуществляется переход от стандартной случайной величины к случайным величинам оптимизационной задачи аji и bj

Если случайной величиной являются коэффициенты аji то детерминированный эквиваленту j-го ограничения будет иметь вид

(4.11)

Если случайной величиной являются коэффициенты аji, то детерминированный эквиваленту j-го ограничения будет иметь вид

(4.12)

Граничные условия остаются без изменения в виде

Таким образом, математическая модель стохастической задачи сводится к детерминированному эквиваленту (4.10), (4.11) и (4.12).

Следует отметить, что в основной массе стохастических задач далеко не все коэффициенты zi, аji 1 и bj (i=1,2,...n; j=1,2,...m) могут быть случайными величинами. Часто такими величинами могут быть один или несколько коэффициентов.

Пример. Составить математическую модель задачи распределения ресурсов (примеры 1 и 2) для случая, когда количество сырьевого ресурса на предприятии является случайной величиной. Известна поставка сырья за некоторый предыдущий период.

Решение. В примерах 1 и 2 была получена следующая детерминированная математическая модель задачи:

В п. 4.1. к этой модели было добавлено условие целочисленности переменных:

В поставленной задаче коэффициент Ь3 (количество сырьевого ресурса) является случайной величиной.

Поставка сырья за некоторый предыдущий период представлена в виде табл. 6.1.

Таблица 4.1

День	1	2	3	4	5	6
Поставка сырья, е.с.	180	150	125	120	170	155	150	23,9

В этой же таблице приведены рассчитанные по выражениям (4.1) и (4.2) значения математического ожидания и стандартного отклонения ст сырьевого ресурса. Отметим, что математическое

ожидание сырьевого ресурса равно его детерминированному значению (150 е.с).

Поскольку в 3-м ограничении b3 является случайной величиной, перепишем это ограничение в соответствии с выражением (4.11):

или

4x1+ 6х2+$х3<150 +23,9.

Зададимся вероятностями выполнения 3-го ограничения Рзад 3 = 0,4; 0,5 и 0,6.

Тогда в соответствии с рис. 6.1 стандартная случайная величина будет соответственно равна = - 0,25; 0 и 0,25. Рассматриваемое 3-е ограничение будет иметь вид

4х2+6х2< 150 - 0,2523,9

или

4x1+ 6x2+8 х3< 150

или

4x1+ 6х2+8 х3 < 150 + 0,2523,9.

Видно, что при вероятностных исходных данных в ограничении появляется дополнительный сырьевой ресурс. Величина и знак этого дополнительного ресурса зависят от Рзад 3 задаваемой вероятности выполнения ограничения.

Полученный детерминированный эквивалент рассматриваемой стохастической задачи имеет следующий вид:

целевая функция

Z = 8x1+llx2+12x3 max;

ограничения

2х1+ 2х2 + Зх350,

6x1+5,5x2+4x3100,

4х1+ 6х2+8 х3 150 + 23,9;

х1+х2+х5 15;

условие целочисленности

хi - целое;
граничные условия

xi0, i=l, 2, 3.

Решение этой стохастической задачи полностью аналогично решению линейной целочисленной задачи.

Приведем несколько примеров.

Периодичность плановых предупредительных ремонтов, Тпл служащие для технико – экономического обоснования правил технической эксплуатации оптимизируется обычно по критерию минимума ежегодных затрат и недоотпуска энергии:

где - суммарная стоимость предупредительных ремонтов; - суммарная стоимость видов аварийных ремонтов и недоотпуска электроэнергии;

- виды отказов, характеризуемых интенсивностью. Последнее выражение однозначно соответствует критерию минимума удельных затрат:

где - параметр потока отказов; Тпл – периодичность предупредительных ремонтов; - параметр потока видов отказов, аппроксимируемых функцией

Дифференцируя последнее по Тплj и приравнивая соответствующие частные произведения к нулю, получим условие оптимума по каждому Тплj:

Значение Тпл, удовлетворяющее условию (6) является оптимальным.

Рис. 4.2. Графическое изображение оптимальной периодичности техобслуживания при многофакторный отказа

4.4. Оптимизационные задачи при недетерминированной исходной

информации

В реальных оптимизационных задачах часто приходится искать решение в условиях неопределенности. Основной причиной неопределенности является недостаток исходной информации. Применительно к области электроэнергетики примером неопределенной (недетерминированной) информации может служить перспективный рост мощностей в развивающейся электроэнергетической системе.

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

В соответствии с этой теорией оптимизационная задача представляется игрой двух игроков. Первый игрок - человек, который принимает решение. В приведенном примере человек должен принять решение по расположению в энергосистеме новых электростанций, строительству линий электропередачи и подстанций. Человек -разумный игрок. Его стратегия - максимальный выигрыш или минимальный проигрыш. Другими словами - человек минимизирует затраты.

Второй игрок - энергосистема, а точнее перспективные мощности потребителей энергии. Как будет развиваться энергосистема, каковы будут мощности потребителей в перспективе -однозначно неизвестно. Стратегия энергосистемы - случайная. Она не стремится к максимальному выигрышу. Следовательно, энергосистему нельзя считать разумным игроком.

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

Допустим, что платежная матрица составлена (табл.4.1).

Имеется набор ходов человека, которые обозначим как x1, х2, ... хп. Имеется набор ходов энергосистемы у1, у2,…ут. Если человек выберет ход хi, а система ответит ходом уj то затраты при таком раскладе составят zij Оптимальное решение выбирается в результате анализа платежной матрицы.

Таблица 4.2

	у1	у2	…	уj	…	уm
x1	z11	z12	…	Z1j	…	z1m
x2	z21	z22	…	Z2j	…	z2m
…	…	…	…	…	…	…
xi	ZI1	zi2	…	zij	…	zim
…	…	…	…	…	…	…
xn	ZN1	zn2	…	znj	…	znm

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

1. Стратегия минимума средних затрат. В соответствии с этой стратегией для каждого хода х; человека определяются средние затраты по всем возможным ходам системы

(4.13)

Выбирается решение, отвечающее минимуму из совокупности i -1, 2, ... п средних затрат

(4.14)

При этой стратегии считается, что все ходы системы имеют

одинаковую вероятность, равную 1/т. Для реальных задач такое предположение, как правило, не является истиной.

2. Миниминная стратегия. В соответствии с этой стратегией
считается, что на каждый ход хi человека система ответит ходом уj

соответствующим минимальным затратам

(4.15)

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

(4.16)

Принятие решения по этой стратегии может привести к крупным просчетам, поскольку здесь учитывается самая благоприятная ситуация. Систему нельзя считать разумным игроком, однако она не будет играть и в поддавки.

3. Минимаксная стратегия. В соответствии с этой стратегией считается, что на каждый ход хi человека система ответит ходом yj соответствующим максимальным затратам:

(4.17)

Выбирается решение, отвечающее минимуму из совокупности i =1, 2, ... п максимальных затрат:

(4.18)

В этой стратегии учитывается самая неблагоприятная ситуация. Считается, что система является разумным игроком и стремится к максимальному выигрышу. Такое предположение не соответствует действительности.

4. Стратегия Гурвица. Эта стратегия учитывает как самую благоприятную, так и самую неблагоприятную ситуации. Здесь решение выбирается по условию

(4.19)

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

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

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

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

анализа решений, полученных по каждой стратегии;

опыта проектировщика;

особенностей конкретной задачи.

Пример.. В развивающейся энергосистеме требуется определить оптимальный объем ввода генерирующих мощностей электростанций. Перспективный рост энергопотребления в системе недостаточно определен. Известно лишь, что суммарная мощность потребителей энергосистемы в будущем может иметь значения 15, 20, 25 и 30 е.м. (единиц мощности).

На момент принятия решения мощность собственных электростанций энергосистемы составляет 10 е.м. Затраты на ввод каждой новой единицы мощности составляют 5 у.е./е.м.

В перспективе энергосистема может оказаться на самобалансе (будет обеспечивать потребителей за счет собственных электростанций) или при дефиците мощности. Во втором случае недостающую мощность можно получить из соседней энергосистемы. При этом за каждую единицу мощности, взятую из соседней системы, необходимо платить 7 у.е./е.м.

Решение. Имеем четыре возможных хода энергосистемы (y1=15; y2=20; y3=25; y4=30 е.м.) Примем четыре возможных хода человека (x1=15; x2=20; x3=25; x4=30е.м.). Составим платежную матрицу и заполним ее (табл. 4.3).

Таблица 7.2

	у1=15	у2=20	у3=25	у4=30
x1=15	25	60	95	130
x2=20	50	50	105+57	120
х3=25	75	75	75	110
x4=30	100	100	100	100

Процесс заполнения платежной матрицы поясним на следующем примере. Человек выбирает ход х2 = 20 е.м., а энергосистема - ход у3 = 25 е.м. В соответствии с ходом человека дополнительно вводятся 10 е.м. Затраты на их ввод составят 105=50 у.е. В соответствии с ходом энергосистемы дефицит мощности составит 5 е.м. Эту мощность необходимо купить в соседней энергосистеме. Затраты на покупку составят 57=35 у.е. Итоговые затраты составят 50+35=85 у.е. Остальные клетки платежной матрицы заполняются аналогично.

Рассмотрим выбор решений по различным стратегиям теории игр.

Средние затраты для каждого хода человека составят:

Zcp1= (25+60+95+130)/4 = 77,5 у.е.

Z cp2= (50+50+85+120)/4 = 76,25 у.е.

Zcp3= (75+75+75+110)/4 = 83,75 у.е.

Zcp4= (100+100+100+100)/4 = 100 у.е.

По стратегии средних затрат следует принять решение х2, соответствующее вводу 10 е.м.

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

Zmin1= min(25+60+95+130) =25 у.е.

Zmin2= min(50+50+85+120) = 50 у.е.

Zmin 3= min(75+75+75+l 10) = 75 у.е.

Zmin4= min(100+100+100+100) = 100 у.е.

По миниминной стратегии следует принять решение x4, соответствующее вводу 5 е.м.

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

Zmax1= max(25+60+95+130) =130 у.е. Zmax2=max(50+50+85+120)= 120 у.е. Zmax3=max(75+75+75+110)= 110 у.е. max(100+100+100+100) = 100 у.е.

По минимаксной стратегии следует принять решение х4, соответствующее вводу 20 е.м.

При применении стратегии Гурвица примем коэффициент k=0,5. При таком коэффициенте миниминная и минимаксная стратегии учитываются с одинаковым весом, поскольку k=0,5 и (1-k)=0,5.

Затраты для каждого хода человека составят:

Z1= 0,5130+0,525= 77,5 у.е.

Z2= 0,5120+0,5-50 = 85 у.е.

Z3= 0,5110+0,575 = 92,5 у.е.

Z4= 0,5100+0,5100 = 100 у.е.

Руководствуясь стратегией Гурвица, следует принять решение х2 соответствующее вводу 5 е.м.

Итак, по стратегии средних затрат следует принять решение х2 (ввод 10 е.м.); по миниминной стратегии – решение x1 (ввод 5 ем); по

минимаксной стратегии - решение х4 (ввод 20 е.м.); по стратегии Гурвица - решение х1 (ввод 5 е.м.).

Разные стратегии предлагают разные решения. Причем две стратегии предлагают одинаковое решение х1. Окончательный выбор остается за человеком.

Поскольку решение х3 (ввод 15 е.м.) не дала ни одна стратегия, это решение не принимаем. Не будем принимать решения х1 и х4, диктуемые самой благоприятной и самой неблагоприятной ситуациями развития энергосистемы. Остается решение х2, отвечающее вводу в энергосистеме 10 е.м. Это решение и будем считать оптимальным.

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

4.6. Определение коэффициентов веса каждого критерия

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

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

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

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

Пусть для решения оптимизационной задачи приняты, например, три критерия (критерий А, критерий В и критерий С). Собирается группа экспертов - специалистов в той области, к которой относится оптимизационная задача. Пусть, группа экспертов состоит, например, из трех человек (1-й эксперт, 2-й эксперт и 3-й эксперт). Каждому эксперту предлагается оценить в баллах от 0 до 1 каждый критерий. При этом выдвигается условие, чтобы сумма баллов каждого эксперта по всем критериям была бы равна 1.

В табл. 4.4 представлены результаты экспертизы. В качестве весового коэффициента i-го критерия (i=A, В, С) принимается среднее значение оценок каждого эксперта по этому критерию (последняя строка табл. 4.4).

Таблица 4.1

	Критерии
Эксперты	А	В	С	Сумма
1-й	0,2	0,2	0,6	1,0
2-й	0,4	0,3	0,3	1,0
3-	0,3	0,2	0,5	1,0
Коэф.веса	0,3	0,23	0,47	1,0

4.7. Оптимизация по обобщенной целевой функции

Одним из возможных решений многопараметрической задачи является оптимизация по обобщенной целевой функции, в которую входят все принятые к рассмотрению критерии со своими весовыми коэффициентами. Эта обобщенная функция записывается следующим образом:

(4.20)

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

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

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

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

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

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

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

Целевые функции в общем случае имеют разные единицы измерения. Поэтому в (8.1) введено деление каждой целевой функции на ее нормированное значение. Такое действие приводит все целевые функций к единой размерности (к относительным единицам, о.е.).

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

Пример. Рассмотрим задачу распределения ресурсов {примеры 1 и 2), в которой требуется определить оптимальный выпуск изделий трех видов (х1, х2 и х3), обеспечивающий предприятию максимальную прибыль при минимальном расходе энергетических ресурсов.

Решение. Решение задачи только по критерию максимальной прибыли вйполнено ранее (см. приложение П.З) и дало следующий результат:

x1=0, х2=10, xз=10, прибыль Z1=230 y.e.

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

Z2=2xl+ 2х2 +3х3 -> min. (4.21)

Из системы ограничений исключаем неравенство, ограничивающее расход энергоресурсов (2x1+2x2+3x350), поскольку левая часть этого неравенства стала целевой функцией. В результате имеем следующую систему ограничений, состоящую из. трех неравенств:

6 х1+ 5,5x2 +4х3 100, (4.22)

4 х1+ 6х2 + 8 х3150,

x1+ x2 15.

Условия целочисленности переменных

xi - целое, i=1, 2, 3 (4.23)

и граничные условия

xi 0, i=2=1,2,3 (4.24)

остаются без изменений.

Решение задачи по 2-му критерию Z2 min дает следующий результат:

x1 =0, x2=15, х3=0, расход энергии Z2 = 30 е.э. (единиц энергии).

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

Zo6 = 1Z1/Z1 норм - 2Z2/Z2Hopм max.

Предположим, что в результате экспертных оценок получены следующие весовые коэффициенты:

1= 0,6 и 2= 0,4.

Обобщенная целевая функция будет иметь следующий вид.

Zoб=0,6(8 x1 + 11 х2 + 12х3) / 230 - 0,4(2х1 2х2 + 3х3) /30.

Система ограничений остается в виде (4.3), условие целочисленности переменных - в виде (4.4), граничные условия - в виде (4.5).

Решение рассматриваемой двухкритериальной задачи дает следующий результат:

х1=4, х2=1, х3=16;

обобщенная целевая функция

Zоб= 0,6 235 / 230 + 0,458 / 30 = 0,28 о.е.

Результаты решений (значения переменных х1, х2, х3), полученных при максимизации прибыли (Z1 max), минимизации энергетических ресурсов (Z2 min) и максимизации обобщенной целевой функции (Z0б max), приведены в табл. 8.2.

таблица. 4.5.

	Z1max	Z2min	Zобmax
x1	0	0	4
x2	10	15	1
х3	10	0	13

Видно, что результат решения двухкритериальной задачи отличается от результатов решения задачи по каждому из двух критериев.

Выводы по четвертой главе

1. Для решения оптимизационных задач со случайной исходной информацией используются методы стохастического программирования.

В Excel эти вычисления выполняются с помощью статистических функций НОРМСТОБР(0,8)=0,84 и НОРМСТРАСП(0,84) = 0,8 после обращения к мастеру функций fх в главном меню.

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

С учетом видов отказов происходящих по стохасти ческами законам.

Заключение

1. Изучая те или иные частные задачи оптимизации электроснабжения нужно отметить что их успешное решения возможно только тогда, исследователь обладает достаточным потенциальном в данной области, математическими знаниями а также непременно пониманием сущности и особенностей задачи в целом.

2. Слагающими математической, физической и технико-экономических знаний к проблеме оптимизации задачи электроснабжения является системный подход и системный анализ, методы вычислительной математически, программирования и рассмотрение её как динамической системы.

3. Особенностью оптимизационных задач электроснабжения является необходимость применения как классических так и алгоритмических методов, так как в них необходимо комплексное определение требуемых характеристик электроустановок и режимов работы систем, обеспечивающих оптимальный уровень безотказности заданной структуры с учетом ограничений технических характеристик, определяющих качество функции.

4. Оптимизация транспортных задач электроснабжения в части пропускной способности ЛЭП необходимо решать методом потенциалов, распределительным методом и симплекс-методом. Причем при решении транспортных задач с транзитом мощности целевая функцию необходимо представить как сумму производный удельных стоимостей на величину передаваемой мощности.

5. Оптимизационные задачи электроснабжения являются нелинейными с одним или несколькими экстремумами. Простые задачи оптимизации, как например, расчет распределения заданной суммарной реактивной мощности по узлам электроснабжения целесообразно решать как задачу безусловной оптимизации.

6. В электроснабжении особую роль играют критерии надежности и критерии качества электроэнергии, которая должна формализоваться математически как ограничения.

7. Особую группу оптимизационных задач электроснабжения при случайной исходной информации. К ним относятся задачи расчетов мощности нагрузок, изменение напряжений в узлах эксплуатируемых систем электроснабжения, расчет оптимальной периодичности проведения профилактических ремонтов основного электрооборудования, решаемых методами статистического программирование.

СПИСОК ИСПОЛЬЗОВАННЫХ ЛИТЕРАТУР

1. Воронин А.А., Мишин С.П. Оптимальные иерархические структуры. М.: ИПУ РАН, 2003-210 с.

2. Применение цифровых вычислительных машин в электроэнергетике. /Под.ред. О.В. Шербачева. –Л.: Энергия, 1980.

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

4. Модели и методы оптимизации развития энергосистем. Арзамасцев Д.А., Липес А.В., Мызин А.Л.-Свердловск, 1976.

5. Методология установления норм на электрические параметры полупроводниковых приборов./ВВ. Ведерников, В.М. Дроневич, Н.Н. Горюнов - Электронная техника. Сер 8, 1978, вып. 2(20).18с.

6. Баркалов С.А., Бурков В.Н., Новиков Д.А., Шульженко Н.А. Модели и механизмы в управлении организационными системами. М.: Изд. «»Тульский полиграфист», 2003. Том 1.-560 с. Том 2., 380.

7. Баркалов С.А., Бурков В.Н., Курочка П.Н. Образцов. Задачи управления материально техническими снабжением в рыночной экономике.

8. Бурков В.Н., Багатурова О.С., Иванова С.И. Оптимизация обменных производственных схем в условиях нестабильной экономики. М.: ИПУ РАН, 1996-48 с.

9. Курицкий Б.Я. Поиск оптимальных решений средствами ЕXCEL 7.0-СПБ.: ВHV-Санкт-Петербург, 1997.

10. Оптимизация радиоэлектронной аппаратуры. Под.ред. проф. А.Я. Маслова. М.: Радио и связь. 19982.

11. Ю.Б. Гук. Теория надежности в электроэнергетике. Ленинград.: Энергоатомоиздат. 1990. 207 с.

12. Бурков В.Н., Горгиазде И.А. Ловецкий С.Е. Прикладные задачи теории графов. Тбилиси.: Мацниереба, 1974-234 с.

13. Монсеев Н.Н. Методы оптимизации. М.: Наука, 1978.-351 с.

14. Демидович Б.П., Марон И.А. Основы вычислительной математики. –М.: Наука, 1970-664 с.

15. Воробьев Л.М. Воробьева Т.М. Нелинейные преобразования в прикладных вариационных задачах. –М.: Энергия, 1972,-208с.

16. А.В. Котельников, А.В. Наумов, А.А. Наумов, Е.Э. Закиев, Оптимизация параметров цепей обратного тока тягового электроснабжения в уcловиях интенсификации движения и повышения весовых норм поездов. Вес
тник ВНИЖТ, №1, 2006.

17.Мелентьев Л.А. Системние исследования в энергетике элементы теории, напрвления развития. 2-е изд.-М.: Наука,1983.-454 с.

18. Гук Ю.Б. Теория надежности в электроэнергетике Л.: Энергоатомиздат 1990, 204 с.

19. Руденко .Ю .Н Ушаков И. А. Надежность систем энергетики. Новосибирск, Наука 1968, 252 с.

20. Макаров А.а., меленнтьов Л.А. методы исследования и оптимизации энергетического хозяйства. – Новосибирск: наука. Сиб. Отд. 1973.-274 с.

21. Арзамасцев Д.А. Веление в многоцеловую оптимизацию энергосистем.-свердловск: Изд. УПК, 1984-82 с.

22. Липес А.В. Применение методов математической статистики для решения электроэнергетических задач.-Свердловск: Изд. УПИ, 1983-86с.

23. Проблемы оптимизационных задач электроснабжения электрофицированных железных дорог. Якубов Б. Материалы IX-межвузовской научно-практической конференции студентов бакалавриатура, магистратура стажеров и соискателей на базе ГАЖК «УТЙ» и ТашИИТ 5-7 апреля 2011. Ташкент, изд. ТашИИТ. 2011.

24. Горидиевский И.Г., Лордкипанидзе В.Д. Оптимизация параметров электрических сетей.-М.: Энергия, 1978-144 с.

25. Ходли Д. Нелинейное и динамическое программирование: пер. с англ/под.ред Г.П. Акилова. –М.: Мир, 1967-506 с.

26. Растригин Л.А. Статические методы поиска. –М.: Наука, 1986-376 с.

27. А.В. Котельников, А.В. Наумов, Е. Закиев. Оптимизация параметров цепей обратного тока тягового электроснабжения в условиях интенсификации движения и повышения весовых норм поездов. Вестник ВНИИНОСТ, №1, 2006.

28. Фазилов Х.Ф., Насыров Т.Х. Установившиеся режимы электроэнергетических систем и их оптимизация.-Т.: Молия, 1999.-370 с.

29. Идельчик В.И. Расчеты и оптимизация режимов электрических сетей и систем.-М.: Энергоатомиздат, 1988.

30. Аллаев К.Р. Электромеханические переходные процессы.-Т.ТГТУ, 2008,-287 с.

31. К.Г. Маркварт. Электроснабжение электрофицированных железных дорог. Москва «Транспорт» 1982. 527 с.

п р и л о ж е н и я

Приложение

Общие сведения об Excel

Материал приложений рассчитан на пользователя, знакомого с основами работы в Excel. Напомним лишь некоторые основные моменты. Общий вид электронной таблицы показан на рис. П.1. В верхней части таблицы указано имя файла, с которым работает пользователь (Книга 1), ниже располагается главное меню (Файл, Правка, ... Сервис, ...), далее - панель инструментов, строка ввода и рабочее поле электронной таблицы

Рабочее поле состоит из строк (1, 2, 3, ...) и столбцов (А, В, С, ...). На пересечении строк и столбцов находятся рабочие ячейки. Каждая ячейка таблицы имеет свой адрес, например Л1,54, С7, ...

В рабочие ячейки заносится различная информация:

текстовая или комментарии (слово «задача» в ячейке В2; комментарий «Z=» в ячейке ВЗ);

цифровая (число «7,34» в ячейке С6; число «12,5» в ячейке D6);

вычислительная.

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

В ячейку F4 занесено выражение «=5,3+3,5*2». Это выражение автоматически вьиисляется и в ячейке F4 приводится результат (12,3).

В ячейку F6 занесено выражение «=C6+D6». Это выражение автоматически вычисляется и в ячейке F6 приводится результат суммы содержимых ячеек С6 и D6 (19,84).

В ячейку Е2 занесено выражение «4,5-С6». Это выражение автоматически вычисляется и в ячейке Е2 приводится результат разности между числом 4,5 и содержимым ячейки Св. Этот результат равен -2,84.

Таким образом, после внесения в рабочую ячейку вычислительной информации внешний вид ячейки и ее содержание отличаются по виду. Внешний вид отражает результат вычислений, а содержание - вычисляемое выражение.

Содержимое любой ячейки можно просматривать, изменять и удалять. Для этого к ячейке мышкой подводится курсор, и после нажатия левой кнопки мышки (МЛ) ячейка выделяется. Содержимое ячейки отражается в строке ввода. На рис. П.1 в строке ввода показано содержимое ячейки Е2.

Для исправления или удаления содержимого ячейки мышкой вводится курсор в строку ввода, МЛ курсор фиксируется на нужном месте и с клавиатуры компьютера вводится исправление или удаление содержимого ячейки.

Последовательность операций при решении оптимизационных задач с помощью программного обеспечения Excel следующая [1]:

1. Размещение комментариев и исходной информации в ячейках
рабочего поля.

2. Вызов из главного меню МЛ команды «Сервис»; из
содержания этой команды вызвать МЛ команду «Поиск решения»; на
экране появляется диалоговое окно «Поиск решения»; в это
диалоговое окно вводится исходная информация (адрес ячейки
целевой функции, вид экстремума целевой функции, адреса ячеек
искомых переменных, ограничения).

ИССЛЕДОВАНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ЭЛЕКТРОСНАБЖЕНИЯ ЭЛЕКТРИФИЦИРОВАННЫХ ЖЕЛЕЗНЫХ ДОРОГ