02 АЗЭ Лекционный материал / лекция 16

Лекция №16 Тема 5. Основные положения применения методов и алгоритмов ма-

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

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

Задачи математического программирования Общая задача математического программирования может быть сформу-

лирована следующим образом: требуется найти значения п переменных х1

,х2,…,хn, которые удовлетворяют т уравнениям или неравенствам

gi (x1, x2 ,...,xn ) , , bi i=1,2,…,m,

(16.1)

и максимизируют или минимизируют функцию

z = f(x1 , x2,..., хn) (16.2)

Условия (16.1) называются ограничениями, а функция (16.2) — целевой функцией.

Предполагается, что функции gi (x1 , x2 ,...,xn ) известны, а bi - заданные константы. Кроме того, в каждом из ограничений (16.1) сохраняется только один из знаков , = или , однако разные ограничения могут, конечно, иметь разные знаки. Величины m и п между собой не связаны, так что т может быть больше, меньше или равно п. В частности, т может быть и нулем, так что в рассмотрение включается и случай, когда ограничения (16.1) отсутствуют.

В некоторых случаях переменные xj сами оказываются функциями одного или нескольких параметров. Задача состоит тогда в определении функций Хи х1 ,х2,…,хn, оптимизирующих выражение (16.2) при условиях (16.1) и, воз-

можно, некоторых добавочных ограничениях на функции xj.

Если в (16.1) и (16.2)

n
gi (x1 , x2 ,...,xn ) aij x j , i=1,2,…,m,	(16.3)

j 1

и

n
f (x1 , x2 ,...,xn ) c j x j	(16.4)
j 1

где aij и сj - известные константы, то задача называется линейной при условии, что нет других ограничений.

Обычно в формулировке общей задачи линейного программирования тре-

буется, чтобы все переменные были неотрицательными, т. е.
x j 0, j=1,2,…,n	(16.5)

так как такая форма задачи более удобна для численного решения. Задача,

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

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

aij x j , , bi j

и максимизирующих или минимизирующих линейную функцию

z c j x j

j

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

нелинейной.

Методы решения нелинейных задач так или иначе включают в себя алго-

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

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

ких задач.

Вычислительные методы.

Симплексный алгоритм для решения общей задачи линейного програм-

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

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

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

щих только приближенное решение или требующих для сходимости беско-

нечного числа шагов.

Один из наиболее мощных методов решения задач нелинейного програм-

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

пускающему применение симплексного алгоритма. Таким образом, оказыва-

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

ным методом для решения некоторых типов задач нелинейного программи-

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

Достоинства и недостатки динамического программирования.

Основное достоинство метода том, что он позволяет решать задачи в си-

туациях, при которых многие другие метода просто неприемлемы, а именно:

неединственность экстремума, недифференцируемость целевой функции,

дискретное изменение переменных, многошаговый характер решения. Дру-

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

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

ды решения как детерминированных, так и стохастических задач. Использо-

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

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

должения. В результате область применения ДП резко расширилась. ДП ис-

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

нике и экономике.

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

Недостаток метода ДП - так называемое "проклятие размерности", свя-

занное с большим объемом накапливаемой информации в памяти ЭВМ. По-

явление современных быстродействующих ЭВМ третьего и четвертого поко-

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

Вычислительный метод ДП является весьма своеобразным по сравнению с методами линейного и нелинейного программирования. Формулировка той или иной задачи в терминах ДП, не является стандартной, а требует творче-

ского подхода. Поэтому, используя идеи ДП в каждом отдельном случае,

необходимо разрабатывать такие алгоритмы, которые бы обеспечивали пра-

вомерное применение этого математического аппарата и давали приемлемые инженерные решения, учитывая возможности современных ЭВМ.

Трудности, порождаемые нелинейностями.

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

a) множество допустимых решений (т. е. множество всех точек [x1 ,

х2....,xn].

б) множество всех точек [x1 , х2....,xn] n-мерного пространства, в которых целевая функция принимает заданное значение, есть гиперплоскость. Кроме того, гиперплоскости, соответствующие разным значениям целевой функции,

параллельны.

в) локальный максимум или минимум является также глобальным макси-

мумом или минимумом целевой функции на множестве допустимых реше-

ний, т. е. не существует локального оптимума целевой функции, отличного от глобального оптимума.

г) если оптимальное значение целевой функции ограничено, то по край-

ней мере одна крайняя точка множества допустимых решений является оп-

тимальным решением.

Кроме того, начав с произвольной вершины множества допустимых ре-

шений, можно достичь оптимальной крайней точки в конечное число шагов,

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

Окончательно, данная вершина является оптимальной тогда и только тогда,

когда значение целевой функции в ней по крайней мере не меньше, чем зна-

чения целевой функции во всех примыкающих вершинах.

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

	x1	x2	6,
	x1	x2	1,		(16.6)
	2x1 x2			4,
	x1	1, x2		0

найти max z = 0,5x1+ 2х2.

Графическое решение показано на рис. 16.1. Область допустимых реше-

ний заштрихована. Оптимум достигается в вершине. Значения переменных,

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

динатами точки пересечения линий x1+х2 = 6, 0,5,х1-х2=-4. Оптимальные зна-

чения переменных есть x* 4 / 3,	x* 14 / 3 . Максимальное значение целе-
1	2
вой функции z* 10 .

Рассмотрим теперь задачу нелинейного программирования, которая отли-

чается от предыдущей только тем, что целевая функция имеет вид z=10(x1-3.5)2+20(x2 - 4)2. (16.7)

Пусть решается задача на минимум. Заметим, что здесь мы имеем сепара-

бельную целевую функцию. Графическое решение задачи дано на рис. 16.2.

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

трами в точке x1 = 3,5, x2 = 4.

Оптимальное решение есть точка, в которой эллипс касается границы вы-

пуклого множества. Если обозначить оптимальные значения переменных че-

рез x* и	x* , а минимальное значение целевой функции через z*, то из рис.
1	2
16.2 следует, что x* x* 6 и z*=10(x1* - 3,5)2+ 20(x2* - 4)2.
	1	2

Рис.16.1.

Кроме того, тангенс угла наклона касательной к кривой z* = 10(x1 - 3,5)2+20(x2 - 4)2 в точке ( x1* , x2* ) должен равняться - 1, так как таков он у пря-

мой x1 x2 6 . Таким образом, мы получаем дополнительное уравнение x2*- 4=0.5(x1*-3.5). Всего же, следовательно, имеется 3 уравнения относительно x1* , x2* и z*. Их единственное решение есть x1*=2,5, х2* = 3,5, z*= 15.

Точка, в которой целевая функция принимает наименьшее значение, ле-

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

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

z*=10(x1 - 2)2+ 20(x2 - 3)2 (16.8)

а множество допустимых решений то же, что и раньше (рис. 16.3). Опти-

мальные значения x1, x2 и z есть х1* = 2, x2* = 3, z* = 0.

Рис. 16.2.

Таким образом, оптимизирующая точка не обязательно лежит на границе.

Отметим, что в рассмотренном случае минимум целевой функции при нали-

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

В каждом из рассмотренных примеров локальный оптимум совпадал с глобальным. Легко, однако, привести примеры, где это будет не так. Рас-

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

x1	x2	2,
x1	x2	2,
x1	x2	6	(16.9)
x1	3x2 2

x1 , x2 0 найти max z =25(x1 – 2)2+(x2 – 2)2.

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

левой функции.

Рис. 16.3.

Рис.16.4.

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

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

щей относительный экстремум целевой функции по сравнению со всеми со-

седними вершинами.

Рис.16.5.

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

	(x1 1)x2	1,	(16.10)
	x1 x2	3.5

Пусть, например, ограничения имеют вид и переменные должны быть не-

отрицательны. Множество допустимых решений в этом случае состоит из двух отдельных частей, ни одна из которых не выпукла (рис. 5.5). Если мно-

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

Для задач нелинейного программирования, имеющих отличные от гло-

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

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

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

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

го программирования. Следовательно, если задача может быть решена с по-

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

Последней мы рассмотрим следующую задачу целочисленного програм-

мирования:

0,5x1 x2 1.75; x1 0.30x2 1.50,

x1, x2 0,x1 ,x2 - целые; найти max z = 0,25x1+x2

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

При учете требования целочисленности переменных xj имеется лишь че-

тыре допустимых решения Если игнорировать требования целочисленности,

то решение соответствующей задачи линейного программирования есть х1* = 0, x2:* =1,75, z*= 1,75. Однако при учете целочисленности оптимальным ре-

шением будет х1* = 1, x2*= 1, z*=1.25.

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

лением результатов до ближайших целых, удовлетворяющих ограничениям

(таким путем мы получили бы ,x1*=0, x2* = 1 и z=1).