Материал: Исследование оптимизационных задач электроснабжения электрифицированных железных дорог

Пример. В существующей схеме электроснабжения (рис. 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 и начнем "спуск".

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

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

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

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

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

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

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

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

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

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

Рис. 2.11

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

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

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 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 можно дополнительно ввести ограничения:

х2£11, х3£8;

х2£11,х3³9;

х2³12, х3£8;

х2³12, х3³9

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

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

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

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

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

Таблица 3.1

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

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

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

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

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

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

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

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

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

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

                                     (3.2)

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

                                     (3.3)

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

                                     (3.4)

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

                                  (3.5)

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

                               (3.6)

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

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