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

Линейная математическая модель в общем случае имеет следующий вид:

Z = z1x1 + z2x2 + ... + znxn → extr

a11x1 + a12x2 + ... + a2nxn ≤ b1,

a21x1 + a22x2 + ... + a2nxn = b2,                                                                          (2.1.1)

. . . . . . . . . . . . . . . . . . . . . . . .

am1x1 + am2x2 + ... + amnxn ≥ bm,

xi ≥ 0, i = 1,2, ... n,

где zi, bj, aji, - заданные постоянные величины i = 1,2, ... n; j = 1, 2, ... m.

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

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

Допустим, что в линейной математической модели ищется минимум целевой функции

Z = z1x1 + z2x2 + ... + znxn → min                                                                  (2.1.2)

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

Z = - z1x1 - z2x2 - ...- znxn → min                                                           (2.1.3)

Таким образом,

min (- z1x1 - z2x2 - ...- znxn) = max (z1x1 + z2x2 + ... + znxn).                           (2.1.4)

 

2. Транспортные задачи электроэнергетики

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

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

Пусть в проектируемой системе электроснабжения имеется i = 1,2, ... n узлов источников питания и j = 1,2, ... m,узлов потребителей. Мощность каждого из источников составляет Ai,а мощность каждого из потребителей – Bj единиц мощности (е. м.). известно взаимное расположение узлов источников и потребителей. Стоимость передачи мощности от источника i к потребителю j (удельная стоимость) составляет zij у.е./е.м.

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

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

       n   m

Z =∑ ∑  zij xij → min                                                                                     (2.2.1)

     i=1  j=1

С позиций теоретической электротехники электрическая сеть является электрической цепью и для этой сети применимы все законы электротехники, в частности 1-й закон Кирхгофа. Для каждого i-источника питания сумма мощностей, оттекающих по линиям ко всем  j = 1,2, ... m узлам потребителей, равна мощности Ai этого источника

 

 m

∑ xij = Ai.                                                                                                       (2.2.2)

j=1

Для каждого j-го потребителя сумма мощностей, притекающих по линиям от всех i = 1,2, ... n источников, равна мощности Bj этого потребителя

 n

∑ xij = Bj.                                                                                                        (2.2.3)

i=1

Соотношения (2.6) и (2.7), представляющие собой балансы мощности в каждом из узлов, являются ограничениями при решении транспортной задачи. Общее количество ограничений равно количеству узлов источников и потребителей n + m.

Из теоретической электротехники известно, что для любой электрической сети количество независимых уравнений, составленных по 1-му закону Кирхгофа , на единицу меньше количества узлов и составляет (n + m - 1). Следовательно, количество независимых ограничений составляет (n + m - 1). Количество базисных (не равных нулю) переменных равняется количеству независимых переменных и составляет (n + m - 1). Остальные переменные являются свободными (равными нулю). Количество свободных переменных составляет (nm -(n + m - 1)).

Каждая базисная переменная xij соответствует присутствию в схеме линии между узлами i и  j, поскольку мощность, протекающая между узлами i и  j, не равна нулю. Каждая свободная переменная xij соответствует отсутствию в схеме линии между узлами i и  j, поскольку мощность, протекающая между узлами i и  j, равна нулю.

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

xi ≥ 0, i = 1,2, ... n; j =1,2, ... m.                                                                     (2.2.4)

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

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

Особенности транспортной задачи следующие:

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

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

 

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

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

Z(x1, x2, … xn) → extr                                                                                   (2.3.1)

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

f1(x1, x2, … xn) = b1,

f2(x1, x2, … xn) ≥ b2,

. . . . . . . . . . . . . . . . .                                                                                      (2.3.2)

fm(x1, x2, … xn) ≤ bm,

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

di ≤ xi ≤ Di, i=0,1,2, ... n.                                                                                (2.3.3)

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

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

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

di ≤ xi ≤ ai, ai ≤ xi ≤ bi, bi ≤ xi ≤ Di, i=0,1,2, ... n.                                            (2.3.4)

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

Для вышеуказанного случая оптимизационная задача решается трижды: в диапазоне переменных di ≤ xi ≤ ai, ai ≤ xi ≤ bi, и bi ≤ xi ≤ Di. Получаем три локальных экстремума. Из трех локальных выбирается один глобальный экстремум.

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

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

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

• градиентный метод с постоянным шагом;
• метод покоординатного и скорейшего спуска;
• метод проектирования градиента;
• метод неопределенных множителей Лагранжа.

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

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

xi ≥ 0, i = 0, 1, 2, ... n.                                                                                   (2.3.5)

Раздел III. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ С ЦЕЛОЧИСЛЕННЫМИ И ДИСКРЕТНЫМИ ПЕРЕМЕННЫМИ

 

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

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

xk – целое, k = 0, 1, 2, ... l,

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

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

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

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

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

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

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

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

 

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

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

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

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

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

Раздел IV. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ ПРИ СЛУЧАЙНОЙ ИСХОДНОЙ ИНФОРМАЦИИ