авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

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


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 17 |

«Институт проблем управления им. В.А. Трапезникова РАН УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ Специальный выпуск 30.1 ...»

-- [ Страница 6 ] --

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

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

n 1) l = li – интенсивность объединенного потока требо i = ваний, 1/час;

n l 2) m = l / i – интенсивность обслуживания объеди i =1 m i ненного потока требований, 1/час.

Обслуживающий прибор обслуживает требования в соот ветствии с принципом FIFO, т. е. «первый пришел, первым ушел».

Средняя длина очереди Lоч требований для системы массо вого обслуживания с бесконечным временем ожидания [13]:

r (2) Lоч =, 1- r Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

l где r = – коэффициент загрузки обслуживающего прибора m требованиями.

Среднее время ожидания в очереди tоч, находим по формуле Литтла:

L (3) t оч = оч.

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

Тогда все поступившие за период времени t требования будут обслужены.

По определению имеем:

1 1 (4) m СМО = =l.

= = t смо t об + t оч + t оч m Решим уравнение (4), для этого подставим в (4) вместо toч (3), а вместо Lоч (2). В результате получим, что такое возможно при коэффициенте загрузки обслуживающего прибора r 0,5.

6. Методика выбора оптимальных затрат на устройства телемеханики и автоматики на подстанции Коэффициент загрузки оперативного персонала требова ниями r – важнейший параметр ПС. При понижении коэффици ента загрузки оперативного персонала r уменьшаются затраты на ОО ПС, но, одновременно, растут капитальные затраты на устройства ТМиА.

Сокращение затрат на ОО ПС может быть достигнуто за счет применения различных средств, которые можно разделить на две группы. К первой группе (рис. 5,а) относятся мероприя тия уменьшающие интенсивность потока требований l: усиле ние изоляции, использование более надежного оборудования и т. п. Вторая группа мероприятий (рис. 5,б) – применение уст Технологические сети ройств обнаружения места повреждения, использование уст ройств телемеханики и т. п. – влияет на изменение среднего времени обслуживания одного требования. И, следовательно, согласно (1) вторая группа мероприятий влияет и на интенсив ность обслуживания µ одного требования.

Рис. 5. Зависимость приведенных затрат от:

а – интенсивности требований;

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

(5) ЗS = З ПС + ЗТМиА ® min, где ЗПС – приведенные затраты на обслуживание ПС, ЗТМиА – приведенные капитальные затраты на устройства ТМиА.

Затраты на ПС зависят то вида ОО. При обслуживании ПС ОВБ, затраты состоят из затрат на обслуживание требований (Зоб), затрат на доставку ОВБ (Здост) и затрат на ущерб оплачи ваемый потребителю (У), а при обслуживании ее ДЭ, состоят только из затрат на обслуживание требований и ущерба оплачи ваемого потребителю:

ЗПС _ ОВБ = Зоб + Здост + У, ЗПС _ ДЭ = Зоб + У.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Затраты на обслуживание требований также зависят то вида ОО. При обслуживании ПС ОВБ затраты на обслуживание требований прямо пропорциональны коэффициенту загрузки требованиями ОВБ со стороны ПС. Чем меньше коэффициент загрузки требованиями ОВБ со стороны ПС, тем большее коли чество ПС может быть обслужено ОВБ. Таким образом, затраты на обслуживание распределяются между всеми ПС пропорцио нально их коэффициенту загрузки требованиями ОВБ. При обслуживании ПС ДЭ либо ДЭ на дому, затраты на обслужива ние требований постоянны и практически не зависят от коэф фициента загрузки требованиями ОВБ.

r ПС Зоб _ ОВБ = 12 kсм З1ОВБ r, SПС Зоб _ ДЭ = 12 kсм З1 ДЭ, Зоб _ ДЭ _ на _ дому = 12 kсм З1 ДЭ _ на _ дому, где kсм – коэффициент сменности;

З1ДЭ, З1ДЭ_на_дому, З1ОВБ – ежеме сячные затраты на содержание ДЭ, ДЭ на дому и ОВБ, руб.;

rПС – коэффициент загрузки ОВБ требованиями с данной ПС;

rSПС – суммарная коэффициент загрузки ОВБ требованиями со всех обслуживаемых ею ПС.

Затраты на доставку ОВБ зависят от частоты выездов ОВБ на ПС и затрат на 1 час работы машины ОВБ:

Здост = 2 З1час l t год t дост, где З1час – затраты на содержание одной машины ОВБ, руб/ час;

l – интенсивность потока требований, 1/час;

tгод – количество часов в году, час;

tдост – время доставки ОВБ с базы на ПС, час.

Затраты на ущерб оплачиваемый потребителю:

l У = k ав с0 P t год, m где kав – коэффициент аварийных требований;

с0 –удельная величина ущерба, руб./кВтч;

m – интенсивность обслуживания Технологические сети требования, 1/час;

P – средняя мощность одного присоединения ПС, кВт.

Затраты на ТМиА:

ЗТМиА (l, m ) = ( E + a ам ) K (l, m ), где aам – ежегодные затраты на амортизацию и текущий ремонт устройств ТМиА;

E – нормативный коэффициент экономиче ской эффективности капитальных вложений;

К – капитальные затраты на устройства ТМиА, руб.

Минимуму целевой функции (5) будет соответствовать не которая экономическая lЭК или mЭК в зависимости от того, мероприятие какой группы проводилось. Далее по известной lЭК (mЭК) определяем оптимальные затраты на устройства ТМиА. Выбор коэффициента загрузки оперативного персонала аналогичен выбору сечения проводов и кабелей по экономиче ской плотности и экономическим интервалам [5]. Поэтому в общем случае целесообразно строить несколько кривых ЗТМиА для оборудования различных фирм и находить оптимальное решение методом экономических интервалов.

7. Методика выбора оптимального количества, вида и места размещения оперативного персонала Для определения вида ОО необходимо знать оптимальное количество ДЭ, ДЭ на дому и ОВБ. Математическая модель строится на основе функции годовых затрат на ОО и ограниче ния на загрузку требования обслуживающего прибора (табли ца 1).

Годовые затраты на систему ОО определяются по формуле:

Згод = 12 ( З1 ДЭ n ДЭ + З1 ДЭ _ на _ дому n ДЭ _ на _ дому + + З1ОВБ nОВБ ) + ЗТМиА + З1 машина t машин _ год + У, где nДЭ, nДЭ_на_дому, nОВБ – количество ДЭ, ДЭ на дому и ОВБ, tмашин_год – суммарное время работы всех машин ОВБ в год, час.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Целевая функция по минимуму затрат на систему ОО без учета ущерба выглядит как n Згод = 12 kсм ( З1 ДЭ x ДЭi + i = n m (6) + З1 ДЭ _ на _ дому x ДЭ_на_домуi + З1ОВБ y j ) + i =1 j = n m + З1час li tгод 2 tдостi, j xОВБ i, j ® min.

i =1 j = Таблица 1. Ограничения целевой функции Ограничение Описание Переменные могут принимать xОВБ i, j, x ДЭ_на_домуi, x ДЭ i, y j значения либо 0, либо – бинарные переменные Для каждой ПС должен быть m xОВБ i, j + x ДЭ_на_домуi + x ДЭ i = 1 выбран только один из об j = служивающих приборов Ограничение для индикатор n xОВБ i, j y j ;

y j x i, j ной переменной i = Загрузка ОВБ, ДЭ и ДЭ на n r i, j xОВБ i, j 0,5 ;

дому требованиями не должна i = быть более 0, r ДЭ i x ДЭ i 0,5 ;

r ДЭ_на_дому i x ДЭ_на_дому i 0, где xДЭi, xДЭ_на_домуi, xОВБi,j – переменные плана обслуживания, а yj – индикаторная переменная.

1, если i-ая ПС обслуживается ДЭ, x ДЭi = 0, иначе.

Технологические сети 1, если i-ая ПC обслуживается ДЭ, x ДЭ _ на _ домуi = 0, иначе.

1, если i-ая ПC обслуживается j -ой ОВБ, xОВБi, j = 0, иначе.

1, если xОВБi,j 0, yj = 0, иначе.

Методика нахождения решения целевой функции (6) за ключается в следующем:

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

2. Приводим целевую функцию и ограничения к следую щему виду:

A x b, Целевая функция: f x ® min, ограничения A eq x = b eq, T x бинарный, где f, b и beq – вектора, A и Aeq – матрицы, и x – решение, кото рое должно быть бинарным вектором, т. е. его элементами могут быть числа, которые принимают значения 0 либо 1.

3. Решение x получаем с помощью методов линейного дис кретного программирования. Решение x также может быть получено с помощью стандартных математических пакетов, например функции bintprog программы Matlab [4].

8. Методика выбора оптимальной структуры оперативного обслуживания Пусть существует некоторое множество D {d1,..., d k } до пустимых вариантов структуры ОО, где k – количество вариан тов. Пусть i-й вариант структуры имеет стоимость сооружения Ki. Требуется выбрать оптимальный вариант структуры ОО так, чтобы минимизировать стоимость сооружения и расходы на Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

обслуживание объектов. При этом срок окупаемости проекта равен T.

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

k T at ( K i,t + З год i,t + У год i,t ) d i ® min, (7) i =1 t = где at – коэффициент дисконта;

Ki,t – капитальные затраты на систему ОО при i-м варианте в году t, руб;

Згодi,t – затраты на систему ОО при i-м варианте в году t, руб;

Угодi,t – ущерб, опла чиваемый потребителю при i-м варианте системы ОО в году t, руб.

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

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

1. Определяем оптимальные затраты на систему ОО для ПС для i-го варианта и года t с помощью (5);

2. Определяем оптимальные затраты на систему ОО для i-го варианта и года t с помощью (6);

3. Определяем полные дисконтированные затраты для i-го варианта;

4. Выбираем оптимальный вариант структуры ОО, кото рый имеет минимальные дисконтированные затраты (7).

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

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

Технологические сети Литература 1. БОЙЦОВ Ю.А., ВАСИЛЬЕВ А.П. Решение задачи ра циональной организации системы оперативного обслу живания электрических сетей // Проблемы энергетики.

Казанский государственный энергетический универси тет. – 2008. – № 1-2. – С. 40 – 45.

2. ВАСИЛЬЕВ А.П., ПАПКОВ Б.В., КАРАБАНОВ А.А.

Оптимизация структуры и оценка эффективности системы эксплуатации оборудования электрической сети // Задачи надежности систем энергетики для субъ ектов отношений в энергетических рынках: Сб. статей – К.: Знания Украины, 2007. – Вып. 57. – С. 204 – 211.

3. ГАЙИБОВ Т.Ш. Оптимизация состава работающих агрегатов электростанций кусочно-линейной аппрокси мацией нелинейных зависимостей // Электрические станции – 2009. – №5. – С. 32 – 37.

4. ДЬЯКОНОВ В., КРУГЛОВ В. Математические пакеты расширения MATLAB. Специальный справочник. – СПб.:

Питер. – 2001 – С. 376 – 379.

5. ИДЕЛЬЧИК В.И. Электрические сети и системы. – М.:

Энергоатомиздат. – 1989. – С. 263 – 274.

6. КОБЕЦ Б.Б., ВОЛКОВА И.О. Smart Grid – Концепту альные положения // Энергорынок. – 2010. – №3 (75) – С. 67 – 72.

7. МИСРИХАНОВ М.Ш., НАЗАРЫЧЕВ А.Н., ТАДЖИБА ЕВ А.И. и др. Анализ эксплуатационной надежности оборудования электрических сетей // Методические во просы исследования надежности больших систем энер гетики: Сборник научных трудов – М.: –Н. Новгород. – 2010. – Вып. 58 – С. 75 – 84.

8. ЗОРИН В.В., ТИСЛЕНКО В.В., КЛЕППЕЛЬ Ф., АДЛЕР Г. Надежность систем электроснабжения, К.:

Вища шк., Головное изд-во. – 1984. – С. 173 – 175.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

9. ПИЛИПЕНКО Г.В. Выбор оптимальной системы опе ративно-диспетчерского управления электростанции // Энергетик. – 2008. – №10. – С. 34 – 35.

10. Правила технической эксплуатации электроустановок потребителей. «НЦ ЭНАС», М.: 2005 (621.3, П-683). – С. 14 – 15.

11. Приложение к приказу ОАО «ФСК ЕЭС» от 13.04. № 136, нормы технологического проектирования под станций переменного тока с высшим напряжением 35 750 кВ (НТП ПС). – С. 5 – 6.

12. РД 153-34.0-03.150-00, Межотраслевые правила по ох ране труда (правила безопасности) при эксплуатации электроустановок. – М. – 2001. – С. 6.

13. СААКЯН Г.Р. Теория массового обслуживания: Текст лекций [Электронный ресурс]. – Режим доступа:

http://window.edu.ru/window_catalog/pdf2txt?p_id= (дата обращения: 01.03.2010).

14. СО 153-34.20.118-2003 «Методические рекомендации по проектированию развития энергосистем», – М: ФГУП НТЦ "Промышленная безопасность". – 2006. – С. 4.

15. Федеральный закон "Об электроэнергетике": собрание законодательства РФ, 31 марта 2003, №13, ст. 1177. – М.: Изд. «Юридическая литература». – 2003. – С. 2951 – 2995.

STRUCTURE MANAGEMENT FOR OPERATIVE SERVICE OF ELECTRIC NETWORKS Ivan Bandurin, Pskov State Polytechnic Institute, Pskov, assistant (bandurin_ivan@mail.ru).

Abstract: An adaptive approach is suggested to structure manage ment of operative service with the aim of minimization of mainte nance costs of the service. The technique is offered of choosing the optimal amount of expenses for automation and remote control Технологические сети devices on power substation. The mathematical model is developed of choosing optimal headcount, skills and disposition of operating staff.

Keywords: operational service, power substation, remote control, automation devices, power grid.

Статья представлена к публикации членом редакционной коллегии О. П. Кузнецовым Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 519.178 + 519.977. ББК 22. НЕКОТОРЫЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ И ВИЗУАЛЬНОГО ПРЕДСТАВЛЕНИЯ ТРАНСПОРТНЫХ ПОТОКОВ Гордийчук Т. В. 1 Ицков А. Г. (Ижевский Государственный Технический Университет, Ижевск) Приведен алгоритм поиска оптимального пути на графе с пере менными весами. Рассмотрены формулы построения двумерных кубических сплайнов дефекта 1 и их вывод.

Ключевые слова: взвешенный граф, кратчайший маршрут, куби ческий сплайн.

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

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

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

Годийчук Тарас Владимирович, студент Ижевского Государствен ного Технического Университета (tsimplex@gmail.com).

Ицков Александр Григорьевич, кандидат физико-математических наук, доцент (pmi.istu@gmail.com).

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

1. Постановка задачи Пусть заданы ориентированный граф G = (X, A), где X = {x1, x2,..., xn } – множество вершин, а A = {a1, a2,..., am } – множество дуг;

множество допустимых управлений U = {u1, u2,..., uk }, и выполнены следующие условия:

1) G – связный граф и для всех xi, xj X существует путь из xi в xj ;

2) для всех ai A существуют функции fi (t, u) (время выхода из дуги ai ) такие, что fi : I Ui I, где I = [0, +), Ui U = {u1, u2,..., uk }, где Ui – множество допустимых управлений на дуге ai ;

3) для всех t0, t1 I таких, что t1 t0 и для всех u Ui выполнено fi (t0, u) fi (t1, u), i = 1, 2,..., m (при одном и том же управлении – чем раньше произошло попадание в дугу, тем меньше будет время выхода из нее).

Тогда, если заданы начальная xн и конечная xк вершины и время начала движения Tн (время окончания движения Tк ), необ ходимо найти путь из xн в xк – {a0 }l, значения {u0 }l и время j j=1 j j= Tк (Tн ), так чтобы Tк Tн min.

При найденных значениях {a0 }l, {u0 }l и известном вре j j=1 j j= мени начала движения Tн время окончания движения Tк рассчи Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

тывается по следующему алгоритму:

t0 := Tн, t1 := f1 (t0, u0 ), 0 (t, u0 ), t2 := f2 1..................

Tк := tl := fl0 (tl1, u0 ), l где fj – вес дуги a0.

j Рассмотрим поставленную задачу на примере движения об щественного транспорта. Пусть известен граф и расписание дви жения маршрутов. Тогда мы будем рассматривать U, как множе ство всевозможных маршрутов в транспортной сети, а Ui – мно жество маршрутов проходящих через дугу с номером i. Функции fi (t, u) будут представлять собой сумму времени ожидания марш рута u (которое будет зависеть от времени попадания в начало дуги ai ) и времени прохождения дуги на маршруте u.

2. Алгоритмы 2.1. ПОИСК ОПТИМАЛЬНОГО ВРЕМЕНИ ПРОХОЖДЕНИЯ ДУГИ Пусть G — исходный граф, S — множество используемых маршрутов, t0 — начальное время, al — дуга графа G (она задает ся парой чисел (i, j), где i — номер вершины, соответствующей началу дуги, а j — номер вершины, соответствующей концу ду (kl) ги). tin — множество времен прибытия k-го маршрута в l-ую (kl) дугу, tout — множество времен отправления k-го маршрута из ду (kl) (kl) ги с номером l. Наборы tin и tout упорядочены по возрастанию.

(kl) Найдем в наборе tin ближайшее к начальному t0 время t(kl), удовлетворяющее условиям:

(kl) (kl) 1) t(kl) tin [p] (tin [p] — p-ый элемент набора);

(kl) 2) tin [p 1] t(kl).

Технологические сети (kl) Если не существует такого tin [p], которое удовлетворяет указан ным выше условиям, то k-ый маршрут не проходит через эту дугу при начальном времени t0. Зная индекс p находим время (kl) (kl) = tout [p] (оптимальное время прибытия в конец дуги al при использовании маршрута с номером k).

Для дуги al находим все маршруты, которые проходят через нее и попадают в множество используемых маршрутов S. Находя для каждого такого маршрута оптимальное время (kl) и миними зируя его по k, находим минимальное время выхода (l) из этой дуги и номер маршрута ul, на котором этот минимум достигается.

2.2. ПОИСК ОПТИМАЛЬНОГО ПУТИ Пусть существует граф G (граф со взвешенными вершина ми), который задан двумя таблицами: таблицей дуг и таблицей вершин, — таблица маршрутов и расписание движения, которое связывает все эти таблицы. Заданы начальное время t0 и две вер шины xin, xout (где xin — вершина отправления, xout — вершина прибытия, а t0 — время отправления). Построим неявно по этим данным граф G — граф с тем же множеством вершин, но с по (k) стоянными весами дуг. Обозначим через Cl (tin, tout ), а через Cl веса дуг al и al графов G и G соответственно. Будем строить граф G по правилу:

1) В графе G между вершинами xi и xj дуга будет только в том случае, если она является частью какого-либо пути, начинающегося на вершине xin.

2) Вес дуги Cl, который представляет собой пару чисел (in, out ), будет определяться из дуги al с помощью опи санного выше алгоритма.

Таким образом, зная начальную точку xin и время t0, нахо дим все дуги ai, выходящие из нее. По алгоритму поиска опти мального времени прохождения дуги определяем веса дуг Ci. Из них находим минимальные времена i попадания во все смежные с xin вершины и номера маршрутов на которых эти минимумы Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

достигаются. При этом для каждой из этих вершин, xin запи сывается в качестве предшествующей вершины. Далее для всех соседей находятся все смежные вершины, за исключением пред шествующей, и в качестве t0 берется значение i. Если на каком либо шаге текущее минимальное время в некоторой вершине xj меньше ранее вычисленного, то все, что было найдено из этой вершины ранее, становится неверным, а в качестве минимума берется текущее время, соответственно, изменяются предшеству ющая вершина и номер маршрута, на котором этот минимум был достигнут. Иначе вычисления из вершины xj прекращаются.

Такая реализация алгоритма позволяет найти кратчайшие (в смысле времени) пути между вершиной xin и всеми оставшимися вершинами при начальном времени t0 (и как следствие – путь из xin в xout ).

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

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

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

Пусть заданы те же начальные условия, только t0 — время прибытия в вершину xout. Необходимо найти оптимальное вре мя отправление из вершины xin. В этом случае существенных изменений в алгоритме не последует.

В алгоритме поиска оптимального прохождения дуги усло вия 1 и 2 заменяются на следующие:

(kl) 1) t(kl) tout [p], (kl) 2) t(kl) tout [p + 1], (kl) (kl) tin и tout меняются ролями, а когда будут найдены (kl), то вместо минимума по k берется максимум.

В алгоритме поиска оптимального пути за начальную точ ку берется xout ;

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

Если в такой формулировке задачи нас интересует сам путь, то за начальную вершину берется значение x, равное xin, условие выхода – сравнение x с xout и нулем. А последовательность тех значений, которые принимал x, записывается в прямом порядке.

2.3. МОДИФИКАЦИЯ ПОИСКА ОПТИМАЛЬНОГО ПУТИ Пусть заданы граф G (такой же, как и в предыдущем алго ритме), начальное время t0, вершина отправления xin и вершина прибытия xout. Проведем преобразование исходного графа.

Граф транспортной сети G содержит достаточно много вер шин, которым инцидентно ровно два ребра. Будем заменять ори ентированную цепь, содержащую такие вершины, одной дугой, для которой начальная и конечная вершины совпадают с началь ной и конечной вершинами цепи. Вес дуги будет равен суммарной Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

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

3. Интерполяционный кубический сплайн дефекта Определение. Кубическим сплайном дефекта 1, интерпо лирующим на отрезке [a, b] данную функцию f (x), называется функция (1) g(x) := gk (x) := ak +bk (xxk )+ck (xxk )2 +dk (xxk )3, при x [xk1, xk ]n, k= удовлетворяющая совокупности условий:

1) g(xk ) = fk (условие интерполяции в узлах сплайна);

2) g(xk ) C[a,b] (двойная непрерывная дифференцируе мость);

3) g (a) = g (b) = 0 (краевые условия) [1].

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

fk fk f (xk1, xk ) = ;

(2) xk xk ak = fk ;

(3) ck ck dk = ;

(4) 3hk Технологические сети 2 bk = f (xk1 ;

xk ) + hk ck + hk ck1 ;

(5) 3 hk1 ck2 + 2(hk1 + hk )ck1 + hk ck = (6) = 3f (xk1 ;

xk ) 3f (xk2 ;

xk1 ).

4. Построение двумерных сплайнов 4.1. ДВУМЕРНЫЙ НЕЗАМКНУТЫЙ КУБИЧЕСКИЙ СПЛАЙН ДЕФЕКТА Пусть задан упорядоченный набор точек на плоскости x1 x2 xn P1 =, P2 =,..., Pn =.

(7) y1 y2 yn Построим для этого набора непрерывную функцию S(t), которая проходит через эти точки и имеет непрерывные первую и вторую производные.

Для удобства возьмем t1 := 0, а tn = T, где T = n (xn+1 xn )2 + (yn+1 yn )2. Тогда так же, как и для клас i= сического кубического сплайна дефекта 1, функция S(t) имеет вид S(t) := Sk (t) := Ak +Bk (ttk )+Ck (ttk )2 +Dk (ttk )3, (8) при t [tk1, tk ]n.

k= и удовлетворяет условиям:

а) S(xk ) = Pk ;

б) S(xk ) C[0,T ] ;

в) S (0) = S (T ) = 0.

Стоит заметить, что формула (8) имеет тот же вид, что и формула (2), c той лишь разницей, что функция S есть вектор x(t) функция скалярного аргумента. То есть S(t) =. Учиты y(t) вая этот факт, уравнение (8) можно записать следующим образом:

x(t) := xk (t) := a1k+b1k (ttk )+c1k (ttk )2+d1k (ttk )3, y(t) := yk (t) := a2k+b2k (ttk )+c2k (ttk )2+d2k (ttk )3, (9) при t [tk1, tk ]n, k= где aik, bik, cik, dik, i = 1, 2, – компоненты соответствующих векторов.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Таким образом, исходную задачу можно свести к решению методом прогонки двух систем, организуя счет по форму лам (2)–(6).

4.2. ДВУМЕРНЫЙ ЗАМКНУТЫЙ КУБИЧЕСКИЙ СПЛАЙН ДЕФЕКТА Пусть задан упорядоченный набор точек (7). Построим для этого набора замкнутую кривую S(t), которая также имеет непре рывные первую и вторую производные.

Для удобства введем: Pn+1 := P0, Sn+1 = S0, t0 := n (xn+1 xn )2 + (yn+1 yn )2. Тогда и tn+1 := T, где T = i= функция S(t) имеет вид S(t) := Si (t) := Ai +Bi (tti )+Ci (tti )2 +Di (tti )3, (10) при t [ti, ti+1 ]n.

k= и удовлетворяет условиям:

а) S(xk ) = Pk ;

б) S(xk ) C[0,T ] ;

в) S (0) = S (T );

г) S (0) = S (T ).

Так как функция S(t) должна иметь непрерывные первую и вторую производные и проходить через узлы интерполяции, то Si (ti ) = Ai = Pi, Si (ti+1 ) = Si+1 (ti+1 ), i = 0, 1,..., n, (11) Si (ti+1 ) = Si+1 (ti+1 ), Si (ti+1 ) = Si+1 (ti+1 ), из формул (10) и (11) получаем Pi +Bi (ti+1 ti )+Ci (ti+1 ti )2 +Di (ti+1 ti )3 = Ai+1, Bi + 2Ci (ti+1 ti ) + 3Di (ti+1 ti )2 = Bi+1, (12) 2Ci + 6Di (ti+1 ti ) = 2Ci+1.

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

Выражая из третьего уравнения системы (12) Di и учитывая, Технологические сети что Sn+1 = S0, получаем Di = Ci+1 Ci, i = 0, 1,..., n 1, 3(ti+1 ti ) (13) D = C0 Cn.

n 3(tn+1 tn ) Из первого уравнения системы (12) получаем Bi = Pi+1 Pi Ci (ti+1 ti ) Di (ti+1 ti )2, ti+1 ti i = 0, 1,..., n 1, (14) B = P0 Pn C (t n n+1 tn ) Dn (tn+1 tn ).

n tn+1 tn Подставляем Di из (13) в формулу (14) Bi = Pi+1 Pi 2 Ci (ti+1 ti ) 1 Ci+1 (ti+1 ti ), ti+1 ti 3 i = 0, 1,..., n 1, (15) B = P0 Pn 2 C (t n n+1 tn ) C0 (tn+1 tn ) n tn+1 tn 3 Из формул (12), (13) и (15) получаем Ci (ti+1 ti ) + 2Ci+1 (ti+2 ti ) + Ci+2 (ti+2 ti+1 ) = = 3(P (t ;

t ) P (t ;

t )), i = 0,..., n 2, i+1 i+2 i i+ Cn1 (tn tn1 ) + 2Cn (t0 tn1 ) + C0 (t0 tn ) = (16) = 3(P (tn ;

t0 ) P (tn1 ;

tn )), Cn (t0 tn ) + 2Cn (t1 tn ) + C0 (t1 t0 ) = = 3(P (t0 ;

t1 ) P (tn ;

t0 )), где Pi+1 Pi P (ti ;

ti+1 ) =.

ti+1 ti Стоит заметить, что система (16) не является трехдиагональ ной, в следствие чего ее приходится решать методом Гаусса, но поскольку матрица системы имеет специфический вид, то прямой ход метода Гаусса необходимо применять лишь для двух послед них строк.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

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

Если ведется статистика, то можно определить плотность распределения p (x) случайной величины.

Если статистических данных нет, то предполагаем, что все i B(, ) (-распределение). Определяя математическое, мы преобразуем граф G, который являет ожидание M = + ся стохастической моделью движения общественного транспорта, в граф G — граф с детерминированными весами. Далее, находя кратчайшее расстояние между любыми двумя вершинами графа G по описанному выше алгоритму, мы найдем наиболее веро ятный наименьший по времени путь между теми же вершинами графа G.

Литература ВЕРЖБИЦКИЙ В. М. Основы численных методов. – М.:

1.

Высш. шк., 2002. – 840 с.

КРИСТОФИДЕС Н. Теория графов. Алгоритмический 2.

подход. – М.: Мир, 1978. – 432 с.

МАЙНИКА Э. Алгоритмы оптимизации на сетях и гра 3.

фах. – М.: Мир, 1978. – 324 с.

Технологические сети SOME ALGORITHMS OF OPTIMIZATION AND VISUALIZATION OF TRAFFIC FLOWS Taras Gordiychuk, Izhevsk state Technical University, student (tsimplex@gmail.com).

Alexander Itskov, Izhevsk state Technical University, Izhevsk, Cand.Sc., assistant professor (pmi.istu@gmail.com).

Abstract: The algorithm is given of optimal path search in a weighted graph with variable weights. The formula are derived for two dimensional cubic splines with defect 1.

Keywords: weighted graph, shortest path, cubic spline.

Статья представлена к публикации членом редакционной коллегии О. П. Кузнецовым Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 519.85+532. ББК 22.19+39. МОДЕЛЬ ГИДРАВЛИЧЕСКОЙ СЕТИ С РЕГУЛЯТОРАМИ РАСХОДА Епифанов С. П.2, Зоркальцев В. И.3, Медвежонков Д. С. (Учреждение Российской академии наук Институт систем энергетики им. Мелентьева СО РАН, Иркутск) Приводится система уравнений и неравенств, описывающая потокораспределение в трубопроводных системах с автома тическими регуляторами расхода на некоторых участках.

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

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

1. Введение В данной статье иллюстрируются возможности использо вания задач выпуклого программирования в решении одной из Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант № 09-01-00306а) Сергей Петрович Епифанов, кандидат физ.-мат. наук, старший научный сотрудник (epifanov@isem.sei.irk.ru).

Валерий Иванович Зоркальцев, доктор технических наук, профессор, заведующий лабораторией (zork@isem.sei.irk.ru).

Дмитрий Сергеевич Медвежонков, младший научный сотрудник (dmitry@isem.sei.irk.ru).

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

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

Для решения задачи потокораспределения в системах с ав томатическими регуляторами применялись модели и алгоритмы [3, 6–9], в которых переменными были гидравлические сопро тивления регуляторов. Это приводило к необходимости введе ния в модель нелинейных зависимостей между гидравлически ми сопротивлениями регуляторов и потерями напора в них.

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

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

Такой прием ранее эффективно применялся для исследования Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

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

2. Модель гидравлической сети с регуляторами расхода 2.1. ОПИСАНИЕ И ПОСТАНОВКА МОДЕЛИ Моделируемая гидравлическая система описывается ориен тированным графом. Пусть m – число узлов, n – число дуг этого графа, A – матрица инцидентности графа размера m n с эле ментами: aij = 1, если дуга j выходит из узла i;

aij = –1, если дуга j входит в узел i;

aij = 0, если дуга j не инцидентна узлу i. Далее считаем, что рассматриваемый граф связный. Тогда ранг матри цы A равен m – 1. Пусть Jr – множество дуг с регуляторами расхода, а J0 – множество остальных дуг. Эти подмножества являются разбиением множества всех номеров дуг:

Jr J0 = {1, 2, …, n} и Jr J0 =.

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

(1) Ax = b, (2) 0 x j x j j J r, j J0 J r, y j = f j ( x j ), (3) y j = c j + ( AT u ) j, j J 0, (4) Технологические сети { }, y j = min f j ( x j ), (c j + ( AT u ) j ) + j Jr.

(5) Заданными являются векторы: b Rm, c Rn и величины максимально допустимых расходов транспортируемой среды x j по дугам j Jr.

Компоненты вектора b – расходы среды из системы либо в систему (потребление из трубопроводной системы или поставки в неё транспортируемой жидкости) для узлов i = 1, …, m. При m bi = 0.

чём Если bi 0, то величина bi является расходом i = среды в систему в узле i. Если bi 0, то величина |bi| задает расход среды из системы в узле i. Компоненты вектора c (вели чины cj) – заданные приращения напора (в результате работы насосов) на дугах j = 1, …, n.

Искомыми величинами являются компоненты векторов:

x Rn, y Rn, u Rm. Величины xj – расходы транспортируемой среды на дугах j = 1, …, n. Величины yj – потери напора на дугах j = 1, …, n. Величины ui – пьезометрические напоры (далее их будем называть просто напоры) в узлах i = 1, …, m.

Уравнение (1) выражает баланс расходов транспортируе мой жидкости в узлах. Ограничения-неравенства x j x j для j Jr в условии (2) означают, что искомые расходы на дугах с регуляторами не могут превышать максимально допустимого расхода на каждой из этих дуг. Значение максимально допусти мого расхода задаётся «уставкой» регулятора. Для дуг с регуля торами расхода, в силу их конструктивных особенностей, не допускается движение потока в обратном направлении. Это условие задаёт ограничение xj 0 для j Jr. Далее считаем, что x j 0 для всех j Jr.

Условие (3) характеризует взаимосвязь между расходами транспортируемой среды xj и потерями напора yj на всех дугах j = 1, …, n (в теории гидравлических цепей [6] это условие принято называть «замыкающим соотношением»). Здесь fj, j = 1, …, n, – заданные функции вещественного аргумента.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Уравнения (4) и (5) выражают баланс потерь, приращений и разности напоров на дугах. Так, согласно (4), для дуг, где нет регуляторов расхода, потеря напора (yj) на дуге j представляется в виде суммы заданного приращения напора на этой дуге (вели чина cj) и разности напоров в концевых узлах дуги j (величина (ATu)j).

Для дуг с регуляторами расхода потеря напора определяет ся по более сложному, чем (4), правилу, выраженному условием (5). Если c j + ( ATu ) j 0, j J r, то, согласно (5), полагаем y j = 0, j J r.

Такая величина потери напора будет соответствовать в условии (3) нулевому расходу xj = 0. В выражении (5) символом ( )+ обозначена неотрицательная срезка вещественного числа:

a + = max{0, a } для любого вещественного.

Согласно (5), если величина cj + (ATu)j, j Jr, положитель ная и превосходит значение f j ( x j ), то y j = f j ( x j ). Это означа ет, что регулятор расхода дросселирует величину напора cj + (ATu)j до значения f j ( x j ), при котором расход по дуге будет равен максимально допустимому расходу x j.

Далее будем считать, что fj – вещественные функции веще ственного аргумента для всех j = 1, …, n. Они непрерывны, возрастают на всем интервале от – до +, со значениями, изменяющимися в интервале от – до + и равными нулю в нуле.

Замечание. Присутствие нелинейных ограничений в сис теме (1)–(5) затрудняет изучение вопросов существования и единственности решений непосредственно из анализа этой системы. Исследование этих вопросов облегчается при исполь зовании представления системы в виде экстремальных задач.

Такие задачи были рассмотрены в работе [4] для классической Технологические сети задачи потокораспределения, к которой сводится система (1)– (5) при Jr =. Оказывается, что системе (1)–(5) при Jr даже в случае наличия регуляторов расхода будет соответствовать задача выпуклого программирования. Это позволяет эффектив но использовать развитую теорию выпуклой оптимизации для исследования и решения системы (1)–(5).

Введем функции от векторов x, y Rn, n F ( x) = F j ( x j ), j = где xj f j ( z )dz, Fj ( x j ) = j = 1,..., n.

Задача оптимизации: найти вектор x Rn, являющийся решением экстремальной задачи (6) F ( x) - c T x ® min, при ограничениях (1), (2).

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

2.2. ТЕОРЕМА О СУЩЕСТВОВАНИИ И ЕДИНСТВЕННОСТИ РЕШЕНИЯ В качестве решения задачи (6) будем рассматривать три вектора: оптимальное значение вектора переменных задачи, который обозначим ~ ;

вектор множителей Лагранжа ограниче x ний (1), который обозначим u ;

вектор ~, с компонентами, ~ y определяемыми по правилу (3), исходя из вектора ~, т. е.

x ~ = f ( ~ ) для j = 1, …, n.

yj j xj Теорема. Задача (6) не имеет решения в том и только в том случае, если противоречивы ограничения (1), (2).

Решение ~, ~, u задачи (6) является решением системы xy~ (1)–(5), и наоборот – решение системы (1)–(5) будет решением задачи (6). Векторы ~, ~ имеют единственное значение для xy решения системы (1)–(5) и задачи (6).

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Доказательство. Из свойств производных функций Fj, j = 1, …, n, следует, что функция F(x) – cTx при любом заданном c Rn является строго выпуклой, и для любого множество векторов x, удовлетворяющих неравенству F(x) – cTx a, будет ограниченным или пустым. Поэтому, если задача (6) имеет допустимое решение, то она имеет и оптимальное реше ние. Поскольку функция F(x) строго выпукла, то задача (6) имеет единственное значение вектора x для любого оптимально го решения. Отсюда, в силу (3), следует единственность значе ния вектора y в оптимальном решении задачи (6).

Первая часть теорема доказана.

Вторая часть. По условиям оптимальности Куна–Таккера [1], чтобы вектор x был оптимальным решением задачи (6), необходимо и достаточно выполнения двух условий: 1) вектор x должен удовлетворять ограничениям (1), (2) задачи;

2) при некотором u Rm должны выполняться необходимые условия оптимальности:

(7) j F ( x) - c j = ( AT u ) j j J 0, (8) j F ( x) - c j = ( AT u ) j + a j - b j, j J r, (9) a j 0, b j 0, j J r, (10) a j x j = 0, j Jr, (11) b j ( x j - x j ) = 0, j J r.

Здесь u – вектор множителей Лагранжа ограничений равенств (1);

aj, b j – множители Лагранжа ограничений неравенств xj 0 и, соответственно, x j x j для j Jr. Соотно шения (10), (11) принято называть условиями дополняющей нежёсткости.

Так как F(x) = f(x) и f(x) = y, то условие (4) равносильно условию (7). Осталось доказать, что условия (8)–(11) при F(x) = f(x), f(x) = y и выполнении условия (2) равносильны условию (5).

Технологические сети Непосредственной проверкой можно убедиться, что из (5) для j Jr при aj = (–cj – (ATu)j)+, b j = (cj + (ATu)j – fj( x j ))+ следует выполнение соотношения (8)–(11). Докажем обратное, что из (8)–(11) при указанных условиях следует (5).

Поскольку F(x) = f(x), f(x) = y, то условие (8) можно пред ставить в следующем виде (12) y j = c j + ( AT u ) j + a j - b j, j J r.

Из (10), (11) и неравенства x j 0 следует, что величины aj и b j для данного j Jr не могут быть обе положительными.

Возможны три случая.

Если aj 0, то b j = 0. Согласно (10) величина xj и, следова тельно, величины fj(xj) и yj, равны нулю. Итак, yj = cj + (ATu)j + aj = 0, то есть cj + (ATu)j 0. Поэтому yj = (cj + (ATu)j)+.

При этом y j f ( x j ), так как f ( x j ) 0. Следовательно, для данного случая условие (5) выполняется.

Если b j 0, aj = 0. В этом случае, согласно (11), x j = x j, y j = f ( x j ). При этом, в силу (12) yj cj + (ATu)j, т. е. в этом случае { } y j = min f j ( x j ), c j + ( AT u ) j.

Это, в силу неравенства f ( x j ) 0, влечёт (5).

Осталось рассмотреть случай aj = 0, b j = 0. Из (12) получим (13) yj = cj + (ATu)j.

Из неравенства (2) и условия yj = fj(xj), следует, что (14) 0 y j f ( x j ).

Соотношения (13), (14) влекут выполнение условия (5).

Теорема доказана.

Замечания. Система уравнений и неравенств (1), (2), (7)– (11), представляющая необходимые и достаточные условия Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

оптимальности задачи (6), равносильна исходной системе (1)– (5). То есть модель потокораспределения гидравлической сис темы с регуляторами расхода можно представлять в виде систе мы (1), (2), (7)–(11).

Множители Лагранжа aj, b j ограничений-неравенств xj и, соответственно, x j x j для j Jr имеют следующий физиче ский смысл, вытекающий из уравнения (8) и условий (9)–(11).

Величина aj равна разности напоров после и до регулятора на дуге j, когда расход через него равен нулю (т. е. регулятор полностью закрыт). b j – величина потери напора в регуляторе на дуге j, при которой расход по дуге не будет превосходить мак симально допустимой величины x j.

Компоненты вектора u имеют неединственные значения в решении системы (1)–(5). Это связано, в том числе, с тем, что ранг матрицы A равен m – 1. Для того чтобы получить компо ненты вектора u, необходимо зафиксировать его значение в одном или более чем одном узле. Необходимость фиксации значения вектора u в нескольких узлах возникает, например, если между двумя множествами узлов, связанными в пределах этих множествами дугами, существует единственная связь, расход по которой достигает границ, задаваемых регулятором.

Величины aj и b j для j Jr в решении системы (1), (2), (7)–(11) могут иметь неединственные значения в описанной ситуации.

2.3. ОБ АЛГОРИТМАХ ПОИСКА РЕШЕНИЯ СИСТЕМЫ (1)–(5) Представление системы (1)–(5) в виде задачи оптимизации (6) полезно не только для выяснения теоретических вопросов существования и единственности решения. Это открывает широкие возможности для разработки и использования эффек тивных алгоритмов отыскания решения данной системы. Для этого могут быть использованы любые методы выпуклого программирования, изложенные, например, в [1]. При этом успешно можно использовать такие преимущества задачи (6), Технологические сети как линейность ее ограничений, дифференцируемость и стро гую выпуклость целевой функции.

Для решения задачи (6) нами был программно реализован метод внутренних точек [2], успешно используемый при реали зации ряда моделей энергетики (например, [5]).

При реализации алгоритма для ускорения расчетов учиты валась специфика матрицы A, а именно её разреженность. При этом сокращение времени счета для алгоритма, по сравнению с вариантом алгоритма, где данная специфика не учитывалась, для задач с сетями средней размерности (порядка 250 узлов и 500 дуг) составило от 20 до 30 раз.

2.3. ПРИМЕР Рассмотрим гидравлическую цепь, схема которой пред ставлена на рис. 1. На схеме 11 узлов и 18 дуг. Притоки и стоки отсутствуют, т. е. b = 0. Пъезометрический напор в узле равен 30 м. Компоненты вектора c приращений напора на дугах равны нулю, кроме c18 = 100 м.

6 7 7 1 11 1 2 3 17 10 9 Рис. 1. Схема гидравлической цепи При расчетах трубопроводных систем, по которым пере дается несжимаемая среда, обычно используется квадратичная зависимость потери напора от расхода транспортируемой среды fj(xj) = sj xj2sign(xj), j = 1, …, n, Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

где sj – заданный положительный коэффициент, называемый гидравлическим сопротивлением [6]. Такие зависимости ис пользовались и в рассматриваемом примере.

В таблице 1 приведены исходные значения гидравлическо го сопротивления sj и максимально допустимого расхода x j для всех дуг схемы.

Таблица 1. Исходные данные xj xj № дуги,j sj № дуги, j sj 1 6,5E–6 – 11 2E–5 – 2 7E–6 – 12 2E–4 3 8E–6 – 13 2E–4 4 5E–6 200 14 2E–4 5 4E–5 – 15 3E–4 6 3E–5 – 16 3E–4 7 2E–5 – 17 3E–4 8 5E–5 200 18 6E–6 – 9 4E–5 – 10 3E–5 – Для получения решения алгоритмом внутренних точек по требовалось 14 итераций. Погрешность (невязка) решения, т. е.

максимальная невязка среди условий оптимальности, менее 0,01. Результаты расчета приведены в таблице 2.

Из таблицы 2 видно, что все регуляторы осуществляют ре гулирование расхода до максимально допустимого, так как для всех дуг, на которых установлены регуляторы, b j 0, j {4, 8, 12, 13, 14, 15, 16, 17}. Соответственно, aj = 0 для этих же номе ров дуг, так как ни на одной из дуг с регулятором расход не равен нулю.

На дуге 18 насосами создается напор. За счет регуляторов на 4, 8, 12, 15, 13, 16, 14, 17 дугах расход по дуге 18 не может превышать суммарной максимальной пропускной способности этих дуг, что в итоге и происходит. Напор, создаваемый насоса Технологические сети ми на дуге 18 больше, чем тратится в системе при передаче по замкнутому циклу. Излишки напора дросселируются в результа те работы регуляторов на дугах 4, 8, 12, 15, 13, 16, 14, 17.


Если снизить напор на дуге 18 на величину, не большую чем min{b j: j Jr}, то расходы и потери напора в системе не изменятся, а напоры, теряемые в регуляторах уменьшаться на эту величину.

Таблица 2. Результаты расчета Напор, Потеря Напор в Номер Расход, теряемый в Номер напора, узле, дуги, j xj, т/ч регуляторе узла, i yj, м ui, м (j), м 1 1200 9,36 – 1 114, 2 800 4,48 – 2 105, 3 400 1,28 – 3 100, 4 200 0,2 39,32 4 99, 5 400 6,4 – 5 60, 6 600 10,8 – 6 53, 7 800 12,8 – 7 42, 8 200 2 37,52 8 60, 9 400 6,4 – 9 53, 10 600 10,8 – 10 42, 11 800 12,8 – 11 30, 12 200 8 32, 13 200 8 43, 14 200 8 63, 15 200 12 28, 16 200 12 39, 17 200 12 59, 18 1600 15,36 – 3. Выводы 1. Получены условия существования решения задачи пото кораспределения с регуляторами расхода. Для этого необходи мо и достаточно только совместности ограничений (1), (2).

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

2. Доказано, что если система уравнений и неравенств (1)– (5) имеет решение, то оно единственно относительно перемен ных, составляющих векторы x, y.

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

Литература 1. ВАСИЛЬЕВ Ф.П. Методы оптимизации. – М.: Факториал Пресс, 2002. – 824 с.

2. ДИКИН И.И., ЗОРКАЛЬЦЕВ В.И. Итеративное решение задач математического программирования: алгоритм ме тода внутренних точек. – Новосибирск: Наука. Сиб. отд ние, 1980. – 144 с.

3. ДИКИН И.И., ПОПОВА О.М., ЕПИФАНОВ С.П. Примене ние методов вспомогательных функций и внутренних то чек при расчетах потокораспределения в гидравлических системах. – Иркутск, 1999. – 25 с.

4. ЕПИФАНОВ С.П., ЗОРКАЛЬЦЕВ В.И. Приложение теории двойственности к моделям потокораспределения // Вычис лительные технологии. – 2009. – Т.14, №1. – С. 67 – 80.

5. МЕДВЕЖОНКОВ Д.С. Транспортная модель c кусочно заданными нелинейными издержками // «Современные тех нологии. Системный анализ. Моделирование». – 2009. – №4 (24), – С. 220 – 225.

6. МЕРЕНКОВ А.П., ХАСИЛЕВ В.Я. Теория гидравлических цепей. – М.: Наука, 1985. – 294 с.

7. НОВИЦКИЙ Н.Н., ТОКАРЕВ В.В. Релейная методика расчета потокораспределения в гидравлических цепях с ре гулируемыми параметрами // Известия РАН Энергетика – 2001.– №2 – С. 88 – 98.

Технологические сети 8. СЕННОВА Е.В., СИДЛЕР В.Г. Математическое моделиро вание и оптимизация развивающихся теплоснабжающих систем. – Новосибирск: Наука, 1987. – 221 с.

9. ХАСИЛЕВ В.Я., МЕРЕНКОВ А.П., КАГАНОВИЧ Б.М. И ДР. Методы и алгоритмы расчета тепловых сетей. – М.:

Энергия, 1978. – 176 с.

MODEL OF HYDRAULIC CIRCUIT WITH FLOW REGULATORS Sergey Epifanov, Institute of Energy Systems of SB RAS, Irkutsk, Cand. Sc. {Physics and Mathematics}, the research officer of labora tory of Pipeline and hydraulic systems (epifanov@isem.sei.irk.ru).

Dmitry Medvezhonkov, Institute of Energy Systems of SB RAS, Irkutsk, Junior research assistant of laboratory of Methods for Math ematical Modeling and Optimization in Energy Sector (dmit ry@isem.sei.irk.ru).

Valery Zorkaltsev, Institute of Energy Systems of SB RAS, Irkutsk, Doctor of Science, professor, Head of laboratory of Methods for Mathematical Modeling and Optimization in Energy Sector (zork@isem.sei.irk.ru).

Abstract: The system is introduced of equations and inequalities describing flow distribution in pipeline circuits with automatic flow regulators installed on certain sections. The system under consid eration is shown to be equivalent to optimality conditions of some convex optimization problem. This equivalence allows building existence and uniqueness conditions of the solution of the consid ered system. The model is illustrated with the example.

Keywords: hydraulic circuit, flow regulator, convex optimization problem, interior-point method.

Статья представлена к публикации членом редакционной коллегии Д. А. Новиковым Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 519.83+621.311:51.001. ББК 31.27- МОДЕЛЬ ОПТИМИЗАЦИИ ДЕФИЦИТА МОЩНОСТИ ЭЛЕКТРОЭНЕРГЕТИЧЕСКОЙ СИСТЕМЫ Зоркальцев В. И.2, Пержабинский С. М. (Учреждение Российской академии наук Институт систем энергетики им. Л.А. Мелентьева СО РАН, Иркутск) Исследуется модель минимизации дефицита мощности в электроэнергетической системе. В модели учитываются нелинейные потери мощности в линиях электропередачи.

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

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

1. Введение В Сибирском энергетическом институте (СЭИ, ныне ИСЭМ СО РАН), разработана методика анализа надежности электро энергетических систем (ЭЭС) [2–6], базирующаяся на методе Работа выполнена при поддержке РФФИ, проект № 09-01-00306а Валерий Иванович Зоркальцев, доктор технических наук, профессор (Иркутск, ул. Лермонтова, д. 130, тел. (3952) 42-78-50).

Сергей Михайлович Пержабинский, инженер (sergey_per85@mail.ru).

Технологические сети многовариантных статистических испытаний (методе Монте Карло).

Методика состоит из трех блоков.

1. Вероятностный блок, в котором формируются случайным образом возможные состояния ЭЭС.

2. Блок оценки дефицита мощности сформированных рас четных состояний (модель минимизации дефицита мощности).

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

В данной методике блок расчета дефицита мощности зани мает центральное место. От его реализации зависит не только качество результатов, но и время проведения всего цикла расче тов. Поэтому к модели минимизации дефицита мощности предъявляются особые требования. Она должна быть агрегиро ванной, максимально адекватной действительности, легко реа лизуемой, рассчитываемой за максимально короткое время. Чем меньше время оптимизации, тем большее количество случайных состояний можно «проиграть» и тем самым увеличить точность оценки показателей Первые варианты модели оценки дефицита мощности ЭЭС, разработанные в СЭИ, представлялись в виде задачи о макси мальном потоке. Для их реализации применялся алгоритм Фор да–Фалкерсона. При использовании алгоритма Форда– Фалкерсона возникала неоднозначность распределения дефици та по узлам и, следовательно, неточность оценок вероятности и математических ожиданий дефицита в узлах системы. В связи с этим стала использоваться двухэтапная схема расчетов модели методом внутренних точек [1]. Сначала решалась задача мини мизации дефицита мощности. На втором этапе – задача равно мерного распределения по узлам пропорционально нагрузкам полученного минимального дефицита. В последующем была Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

предложена одноэтапная схема одновременной минимизации с равномерным распределением дефицита мощности [2].

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

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

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

Заданы располагаемая мощность xi, нагрузка yi в i-ом узле ЭЭС, предел пропускной способности zij линии электропереда чи, связывающей узлы i и j, i = 1, …, n, j = 1, …, n. Считается, что для всех i и j, xi 0, y i 0, z ij 0. Если z ij = 0 при неко торых i и j, то это означает, что фактически поток мощности из узла i в узел j не возможен.

Переменными задачи являются: xi – используемая мощ ность;

yi – покрываемая нагрузка в узле i;

zij – поток мощности из узла i в узел j.

Требуется минимизировать суммарный дефицит мощности в системе Технологические сети n ( y i - y i ) ® min, (1) i = учитывая балансы мощности в узлах n n (2) x i - y i + (1 - a ji z ji ) z ji - z ij = 0, i = 1,..., n, j =1 j = и линейные двусторонние ограничения-неравенства на пере менные (3) 0 y i y i, i = 1,..., n, (4) 0 xi xi, i = 1,..., n, (5) 0 z ij z ij, i = 1,..., n, j = 1,..., n.

Замечание. Коэффициенты aij, используемые для описания потерь при передаче электроэнергии из узла i в узел j, заданы и удовлетворяют условию 2a ij z ij 1 для всех i и j.

Это условие означает, что дополнительная единица мощно сти, передаваемая из узла i в узел j, достигает узла j с поло жительным значением: при любом z ij [0, z ij ) d ( zij - a ij ( zij ) 2 ) 0, i = 1,..., n, j = 1,..., n.


dzij Определение. Тройку векторов x, y, z, удовлетворяющих ба лансовым уравнениям (2) и неравенствам (3)–(5), будем назы вать допустимым решением задачи (1)–(5). Множество таких троек векторов образует множество допустимых решений.

Множество допустимых решений задачи (1)–(5), как прави ло, невыпукло (за исключением некоторых вырожденных слу чаев). Действительно, пусть существуют такие допустимые решения ( ~, ~, ~ ), ( y, x, z ), что ~ z, тогда их выпуклая z yxz ~ + (1 - l ) y, l ~ + (1 - l ) x, l ~ + (1 - l ) z ) не комбинация (ly x z удовлетворяет балансовым ограничениям (2). Значения функций a (~ - z ji ).

n в левой части ограничений (2) равны l (1 - l ) z ji ji j = Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Эти величины будут положительны для l (0, 1) и всех i таких, что существует номер j, при котором ~ ji z ji.

z Для представления задачи (1)–(5) в виде эквивалентной за дачи выпуклого программирования заменим ограничения (2) на следующие:

n n (6) xi - y i + (1 - a ji z ji ) z ji - z ij 0, i = 1,..., n.

j =1 j = Множество векторов, соответствующих ограничениям (3)– (6), является выпуклым, для любой выпуклой комбинации двух допустимых решений ( ~, ~, ~ ), ( y, x, z ) выполняются огра yxz ничения (3)–(6).

Вместо задачи (1)–(5) можно использовать задачу выпукло го программирования (1), (3)–(6), множество решений которой содержит множество допустимых решений исходной задачи. В [3] доказано следующее утверждение.

~, ~,~, Теорема 1. Пусть значения переменных y i xi z ij i = 1, …, n, j = 1, …, n, являются оптимальным решением зада чи (1), (3)–(6), тогда существуют такие xi, zij, что значения ~, x, z, i = 1, …, n, j = 1, …, n, составляют переменных y i i ij оптимальное решение задачи (1)–(5) Из приведенной выше теоремы следует, что распределение дефицита мощности по узлам системы, найденное в результате решения задачи (1), (3)–(6), будет оптимальным и в задаче (1)– (5).

Задача (1), (3)–(6) имеет решение, так как множество до пустимых решений не пусто (значения y = 0, x = 0, z = 0 со ставляют допустимое решение), выпукло и ограничено (в силу условий (3)–(5)), целевая функция линейна. Из существования решения в задаче (1), (3)–(6) следует (согласно Теореме 1) существование решения в задаче (1)–(5). Докажем, что решение в задаче (1), (3)–(6) единственно по переменным, составляющим компоненты вектора y.

Технологические сети Теорема 2. Решение задачи (1), (3)–(6) единственно по пе ременным yi, i = 1, …, n.

Доказательство.

Предположим, что у задачи (1), (3)–(6) существует два оп тимальных решения ( ~, ~, ~ ) и ( y, x, z ) такие, что yxz ~ y.

(7) y Оба решения, поскольку они оптимальные, имеют одно и то же значение целевой функции n n (y - y ) = (y - ~ ).

(8) y i i i i i =1 i = Для задачи выпуклого программирования множество опти мальных решений выпукло, следовательно, оптимальным реше нием должен быть и набор векторов (y*, x*, z*) таких, что (9) y * = 0,5( ~ + y ), x* = 0,5( ~ + x), z * = 0,5(~ + z ).

y x z В силу (7) для некоторого h {1,..., n} значения перемен ных ~h и yh будут различаться. Следовательно, одна из этих y величин будет меньше другой. Пусть для определенности (10) ~h yh yh.

y То есть для решения ( ~, ~, ~ ) узел с номером h будет де yxz фицитным. Вследствие этого, (11) ~h = xh, ~hj = 0 для всех j {1,..., n}.

z x Действительно, если ~ x, то можно сократить дефицит в x h h узле h, а, значит и суммарный дефицит, увеличивая значение xh.

Если ~hj 0 для некоторого j, то передаваемая мощность из z узла h в узел j доходит в меньшем объеме, чем ~ на величину z hj потерь. Поэтому такой поток способствует меньшему сокраще нию суммарного дефицита по всем узлам. Если этот поток уменьшить на единицу, то это приведет к сокращению на еди ницу дефицита в данном узле и возможному увеличению, меньшему, чем на единицу, дефицита в других узлах. Следова тельно, суммарный дефицит сократится. Итак, для оптимально Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

го решения из дефицитного узла не может быть потоков мощ ности. Свойства (11) доказаны.

Представим в виде функции n n (12) f ( y, x, z ) = xh - yh + (1 - a jh z jh ) z jh - zhj j =1 j = выражение в левой части условия (6) для узла h. В силу дефи цитности для узла h решения ( ~, ~, ~ ) условие (6) должно yxz выполняться в виде равенства (13) f ( ~, ~, ~ ) = 0.

yxz Иначе, если бы значение f при таких аргументах было бы положительным, величину ~h можно было бы увеличить, не y нарушая условие (6). Тем самым сократив дефицит в узле h, сократим и суммарный дефицит, что противоречит оптимально сти решения ( ~, ~, ~ ).

yxz Из (11)–(13) следует, что n n (14) ~ = x + ~ - a ( ~ ) 2.

y z z h h jh jh jh j =1 j = Согласно условию (6) (15) f ( y, x, z ) 0.

Отсюда, учитывая, что xh xh, ~hj 0 для всех j = 1, …, n z имеем n n (16) yh xh + z jh - a jh ( z jh ) 2.

j =1 j = Предположим, что для всех j = 1, …, n ~ =z.

z jh jh Тогда из (14), (16) будет следовать, что yh ~h.

y Это противоречит (10). Предположение не верно. Для неко торого j (17) ~jh z jh.

z Множество таких номеров j обозначим J. Отметим, что Технологические сети ( ) ( ) (18) 0,5~ jh + 0,5 z 2 - 0,25 ~ jh + z jh = 0,25 ~ jh - z jh.

z2 jh z z Из определения функции f, условия (9) и равенства (18) следует, что ( ) f ( y *, x*, z * ) = 0,5 f ( ~, ~, ~ ) + 0,5 f ( y, x, z ) + 0,25a jh ~ jh - z jh 2.

yxz z jJ Из (17) и условия J f следует, что третья составляющая поло жительна. Отсюда (19) f(y*, x*, z*) 0.

Из (9), (10) следует, что ~ y* y y h yh h.

h Это означает, что оптимальное решение (y*, x*, z*) будет да * вать дефицит ( yh - yh ) в узле h. Вместе с тем неравенство (19) означает, что значение переменной yh можно увеличить, не нарушая условия (6). Тем самым будет сокращаться дефицит в узле h и суммарный дефицит. Это противоречит тому, что ре шение (y*, x*, z*) является оптимальным. Полученное противоре чие доказывает ошибочность исходного предположения о суще ствовании двух оптимальных решений, удовлетворяющих условию (7). Теорема доказана.

3. Замечания по реализации модели оценки дефицита мощности электроэнергетической системы с учетом квадратичных потерь мощности в сети Для сокращения количества неизвестных при реализации модели следует учитывать только такие связи, по которым можно осуществлять реальные потоки мощности. То есть необ ходимо исключить из состава переменных связи, для которых zij = 0. Более того, потоки в обоих направлениях между узлами i и j можно задавать с помощью не двух, как ранее, а одной переменной. Пусть l = 1, …, m – номера дуг в направленном графе, описывающем ЭЭС, m – общее количество дуг. Обозна Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

чим через til элементы матрицы (размера n m) инциденций узлов и дуг графа, - 1, если узел i является началом связи l, tij = 1, если узел i является концом связи l, 0, если узел i не прилегает к связи l.

Затем, в отличие от ранее использовавшегося обозначения, через zl обозначим переменную, соответствующую объему потока мощности по связи l.

Ограничения (5), (6) примут следующий вид (20) z l zl zl, l = 1,..., m, m m ~ (21) xi - yi + til zl - a il ( zl )( zl ) 2 0, i = 1,..., n.

l =1 l = ~ Функции a il ( zl ) определяются следующим образом a, если til zl 0, ~ a il ( zl ) = l 0, если til zl 0, i = 1, …, n, l = 1, …, m. Величина z l = - zl для всех l.

При нахождении минимального суммарного дефицита мощности возможна ситуация, когда в результате решения задачи (1), (3), (4), (20), (21) получено отрицательное значение потока мощности между узлами, т. е. zl 0. Это означает, что поток мощности по l-ой связи направлен в обратную, относи тельно заданного направления, сторону.

Некоторые узлы i могут не обладать генерирующими мощ ностями ( xi = 0 ). Обозначим через L множество номеров узлов с нулевой располагаемой мощностью. Далее рассматривается только случай, когда во всех узлах yi 0 и у всех связей zl 0, z l 0.

Для решения задачи (1), (3), (4), (20), (21) используется ал горитм метода внутренних точек, основывающийся на методе линеаризации [1]. На каждой итерации k = 1, 2, … в точке ли неаризации xk yk zk нелинейные ограничения-равенства заменя ются на их линейную аппроксимацию. Для уменьшения по Технологические сети грешностей линеаризации при решении нелинейных задач оптимизации можно учитывать квадратичные составляющие разложения функций-ограничений в ряд Тейлора. А именно, можно при поиске направления улучшения решения включать в целевую функцию вспомогательной задачи квадратичные со ставляющие аппроксимаций функций-ограничений исходной задачи с весами, равными оценкам множителей Лагранжа этих ограничений. Такие идеи высказывались ранее применительно к разным алгоритмам оптимизации, в частности, Б.Н. Пшеничным для разрабатываемого им метода линеаризации [8]. Проведен ные ранее экспериментальные исследования для задач с нели нейными ограничениями [7] показали, что метод внутренних точек, использующий квадратичные аппроксимации, работает быстрее, чем метод внутренних точек, базирующийся только на линеаризации.

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

m ( yi - yi ) + N xi ® min, (22) y, x i =1 iL при m m ~ (23) xi - yi + til zl - a il ( zl )( zl ) 2 0, i = 1,..., n, l =1 l = 0 yi yi, i = 1,..., n, (24) 0 xi xi, i L, (25) xi 0, i L, (26) z l zl zl, l = 1,..., m.

(27) Здесь N – число, большее единицы, чем обеспечивается приоритет минимизации фиктивной переменной xi, i L по Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

отношению к минимизации суммарного дефицита. В расчетах использовалось N = 2.

Будем считать, что изначально потоков мощности в сети нет, т. е. zl0 = 0, l = 1, …, m. Для всех узлов i в качестве старто вых значений переменных xi, yi возьмем такие xi0, yi0, удовлетво ряющие ограничениям (24)–(26), чтобы xi0 было больше yi0.

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

4. Алгоритм метода внутренних точек, использующего квадратичные аппроксимации Представим описание алгоритма внутренних точек, исполь зующего квадратичные аппроксимации, для задачи минимиза ции линейной функции при выпуклых квадратичных ограниче ниях (28) c T x ® min, (29) x T Ai x + d iT x 0, i = 1,..., m, (30) x x x.

Переменные x образуют вектор из Rn. Заданными являются матрицы Ai размера n n, i = 1, …, m, векторы c Rn, d Rn, x R n, x R n. Предполагается, что матрицы Ai симметриче ские неотрицательно-определенные, что обуславливает выпук лость функций xTAix + diTx, i = 1, …, m. Задача (28)–(30) содер жит частный случай исследуемой нами задачи (22)–(27). При этом задача (28)–(30) более удобна для краткого описания алгоритма внутренних точек.

Предполагаем известным начальное приближение x0 Rn, удовлетворяющее условиям (29), (30) в строгой форме ( x 0 ) T Ai x 0 + d iT x 0 0, i = 1,..., m, x x0 x.

Технологические сети На итерации k, k = 1, 2, …, сначала вычисляется направление корректировки Dxk Rn, являющееся решением следующей задачи:

1 Tk 1 (31) c T Dx + Dx D1 Dx + Dx T D2 Dx + Dx T D3k Dx ® min, k 2 2 где ( { }) - D1k = diag min x j - x k, x k - x j, j j m D2 = vik -1 Ai, k i = ( Ai x k + d )( Ai x k + d ) T m D3k =, (( x k ) T Ai x k + d T x k ) i = { } vik - = max 0, u ik -1, uik-1 - оценки множителей Лагранжа ограничений (29), вычис ленные на (k – 1)-ой итерации. При k = 1 положим vi0 = 1, 1 Tk Dx D1 Dx, Dx T D3k Dx, добавляемые i = 1, …, m. Слагаемые 2 в целевую функцию вспомогательной задачи, можно интерпре тировать как штрафы за приближение к границам допустимой m области. Матрица D2 = vik -1 Ai представляет собой сумму k i = квадратичных составляющих функций-ограничений с весами, равными приближениям к множителям Лагранжа этих ограни чений. В методе внутренних точек, базирующемся на линеари зации, вместо матрицы D2k используется единичная матрица того же размера.

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

( D1k + D2 + D3 )Dx = -c.

k k Для решения этой системы можно воспользоваться методом квадратного корня.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

После нахождения направления корректировки вычисляет ся шаг корректировки по следующему правилу:

{ } (32) lk = g min l1, l2 при заданном g (0, 1), k k где l1k = max{l : ( x k + lDx k ) T Ai ( x k + lDx k ) + + d T ( x k + lDx k ) 0, i = 1,..., m}, l2 = max{l : x x k + lDx k x }.

k Итеративный переход осуществляется по формуле (33) x k +1 = x k + lk Dx k для всех k = 1, 2,...

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

m (34) c + vik ( Ai x k + d ) + h k - V k e 1, i v (-( x k ) T Ai x k - d T x k ) e 2, i = 1,..., m, k i (35) h k ( x k - x k ) e 2, j j j V k ( x kj - x kj ) e 2, j = 1,..., n, j при заданных малых положительных числах 1, 2. Здесь hk, zk Rn – векторы приближений к множителям Лагранжа ограничений (30).

Оценки множителей Лагранжа ограничений (29), (30) нахо дятся по формулам ( Ai x k + d ) T Dx k u ik =, i = 1,..., m, (( x k ) T Ai x k + d T x k ) Dx k j h k = max 0,, j (xk x k ) j j - Dx j k V k = max 0, k, j = 1,..., n.

j ( x j - xk ) j Технологические сети Для вырабатываемых алгоритмом приближений к опти мальному решению ограничения (29), (30) на каждой итерации выполняются в строгой форме ( x k ) T Ai x k + d iT x k 0, i = 1,..., m, x xk x.

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

Если вектор xk не удовлетворяет условиям (34), (35), то из выполнения неравенства - c T Dx k и правил определения шага корректировки (32) следует, что значение целевой функции уменьшится:

c T x k +1 c T x k.

Если неравенства (34), (35) в точке xk выполняются, то вычисли тельный процесс останавливается.

5. Результаты экспериментальных расчетов Экспериментальные исследования проводились на серии из 50 режимов, сформированных при помощи датчика случайных чисел, для схемы ЭЭС [4], представленной на рис. 1.

Рис. 1. Тестовая расчетная схема ЭЭС В таблице 1 и таблице 2 приведены основные характеристики узлов и связей одного из тестовых режимов.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Таблица 1. Характеристика узлов расчетного режима тесто вой схемы ЭЭС Номер Располагаемая Максимальная Баланс в i узле узла, i мощность нагрузка yi, МВт xi - yi, МВт xi, МВт 1 2458 2734 – 2 1600 1760 – 3 383 528 – 4 1350 170 5 409 1647 – 6 921 514 7 0 200 – Итого 7121 7553 – Таблица 2. Характеристика связей расчетного режима тесто вой схемы ЭЭС Номер Максимально возможные потоки по Коэффициент связи, связи j, МВт потерь мощно сти в связи, a j j zj zj I –360 360 0, II –150 150 0, III –200 200 0, IV –800 800 0, V –1200 1200 0, VI –300 300 0, VII –150 150 0, Тестовая схема по заданным режимам рассчитывалась дву мя алгоритмами: методом внутренних точек, использующим квадратичные аппроксимации, и методом внутренних точек, базирующимся на линеаризации. В таблице 3 и таблице 4 указа но минимальное, максимальное и среднее число итераций, Технологические сети потребовавшееся для решения всех тестовых задач при задан ных 1, 2. В условиях (34), (35) использовались разные 1, 2.

Таблица 3. Результаты расчетов тестовой схемы ЭЭС по заданным режимам Число итераций Метод Точность Мини- Макси- Сред мальное мальное нее Метод внутренних точек, использую щий квадратичные 1 = 0,05, 14 49 19, 2 = 0, аппроксимации Метод внутренних точек, базирующий- 1 = 0,05, ся на линеаризации 14 83 24, 2 = 0, Таблица 4. Результаты расчетов тестовой схемы ЭЭС по заданным режимам Число итераций Метод Точность Мини- Макси- Сред мальное мальное нее Метод внутренних точек, использую щий квадратичные 1 = 0,01, 16 74 23, 2 = 0, аппроксимации Метод внутренних точек, базирующий- 1 = 0,01, ся на линеаризации 16 147 40, 2 = 0, Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

6. Заключение 1. Для модели оценки дефицита мощности ЭЭС с квадра тичными потерями мощности в ЛЭП предложен способ пред ставления модели в виде задачи выпуклого программирования путем замены балансовых ограничений-равенств на ограниче ния, записанные в форме неравенств.

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

3. Результаты экспериментальных исследований подтверди ли работоспособность метода внутренних точек, использующе го квадратичные аппроксимации, и показали пригодность для решения задачи нахождения минимального суммарного дефи цита мощности с учетом ее квадратичных потерь в сетях. Зна чимость применения данного алгоритма для решения задачи (1), (3), (4), (13), (14) состоит в том, что благодаря учету активных ограничений задачи и эффективной минимизации погрешностей линеаризации увеличивается скорость работы алгоритма, по сравнению с исходным методом, основанном на линеаризации.

4. Для решения задачи поиска минимального суммарного дефицита мощности требуется найти значения 2n + m перемен Технологические сети ных, где m – число связей;

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

Литература 1. ДИКИН И.И., ЗОРКАЛЬЦЕВ В.И. Итеративное решение задач для математического программирования (алгорит мы метода внутренних точек). – Новосибирск: Наука, 1980. – 143 с.

2. ЗОРКАЛЬЦЕВ В.И., КОВАЛЕВ Г.Ф., ЛЕБЕДЕВА Л.М.

Модели оценки дефицита мощности электроэнергетиче ских систем – Иркутск: ИСЭМ СО РАН, 2000. – 25 с.

3. ЗОРКАЛЬЦЕВ В.И., ЛЕБЕДЕВА Л.М., ПЕРЖАБИН СКИЙ С.М. Модель оценки дефицита мощности электро энергетической системы с учетом квадратичных потерь мощности в линиях электропередач // Сиб. журн. вычисл.

математики / РАН. Сиб. отд-ние. – Новосибирск, 2010. – Т.

13, № 3. – С. 285 – 295.

4. КОВАЛЕВ Г.Ф., ЛЕБЕДЕВА Л.М. Комплекс моделей оп тимизации режимов расчетных состояний при оценке на дежности электроэнергетических систем – Иркутск:

ИСЭМ СО РАН, 2000. – 73 с.

5. КОВАЛЕВ Г.Ф., ЛЕБЕДЕВА Л.М. Модель оценки надеж ности электроэнергетических систем при долгосрочном планировании их работы // Электричество. - 2000. - №11. С. 17 – 24.



Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 17 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.