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

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

МЕДВЕЖОНКОВ Дмитрий Сергеевич

СИММЕТРИЧНАЯ ДВОЙСТВЕННОСТЬ В ВЫПУКЛОЙ ОПТИМИЗАЦИИ И МОДЕЛИ ПОТОКОРАСПРЕДЕЛЕНИЯ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в технике, экологии и экономике)

5 ДЕК 2013

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Иркутск - 2013

005542707

005542707

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте систем энергетики им. Л.А. Мелентьева Сибирского отделения Российской академии наук

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

Официальные оппоненты:

доктор технических наук, профессор Зоркальцев Валерий Иванович

доктор технических наук, профессор

Тятюшкин Александр Иванович,

ИДСТУ СО РАН, главный научный сотрудник

доктор физико-математических наук, профессор Жадан Виталий Григорьевич, ВЦ РАН, заведующий отделом

Ведущая Институт математики и механики УрО РАН

организация: (г. Екатеринбург)

Защита состоится 26 декабря 2013 г. в 14.00 ч. на заседании диссертационного совета Д003.021.01 в Федеральном государственном бюджетном учреждении науки Институте динамики систем и теории управления СО РАН (ИДСТУ СО РАН) по адресу: 664033, г. Иркутск, ул. Лермонтова, 134.

С диссертацией можно ознакомиться в библиотеке и на официальном сайте http://www.idstu.irk.ru/ ИДСТУ СО РАН.

Автореферат разослан 25 ноября 2013 г.

Ученый секретарь диссертационного совета, к.ф.-м.н. " Т.В. Груздева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Математическое моделирование и методы оптимизации важны при поиске системных связей и закономерностей функционирования сложных систем, для повышения эффективности управления в технических, экономических, социальных системах. Современная теория оптимизации служит методической основой для выбора наилучших экономических и технических решений, средством математического моделирования, инструментом вычислительной математики. Весомый вклад в развитие теории и методов оптимизации внесли Л.В. Канторович, Дж. Данциг, X. Кун, А. Таккер, Е.Г. Гольштейн, И.И. Еремин, Ю.Г. Евтушенко и многие другие.

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

Случай, когда двойственная задача оптимизации к двойственной задаче совпадает с исходной, в математическом программировании называют симметричной двойственностью. Такая двойственность имеет место для задач линейного программирования. Задачи нелинейной оптимизации не обладают в общем случае свойством симметричной двойственности, хотя для некоторых типов нелинейных задач симметричная двойственность имеет место. Например, в работах У. Дорна, Дж. Денниса, СМ. Зуховицкого, Л.И. Авдеевой рассматривалась симметричная двойственность задач квадратичного программирования. Симметричная двойственность задач оптимизации с целевой функцией, выпуклой по одному векторному аргументу и вогнутой по другому, исследовалась в работах Дж. Данцига, Б. Монда, М. Базара, Г. Дэви и др.

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

Теория симметричной двойственности применена в работе для исследования моделей потокораспределения. Эти модели включают нелинейные транспортные задачи и гидравлические цепи, используемые для описания различных трубопроводных систем, например, систем водо-, нефте-, газоснабжения. Линейные транспортные модели начали разрабатываться с 30-х годов А.Н. Толстым, Л.В. Канторовичем, Л. Фордом, Р. Фалкерсоном и др., а с конца 40-х гг. XX века активно ведутся исследования нелинейных транспортных задач в работах

Г. Биркхофа, Д. Денниса, В.Н. Лившица, Л.Д. Попова, Е.А. Нурминского и др.

В начале XX века в работах М.М. Андрияшева, В.Г. Лобачева, X. Кросса были предложены первые методы расчета гидравлических сетей. С середины 60-х годов начала активно формироваться теория гидравлических цепей, обобщающая методы моделирования и оптимизации трубопроводных систем. Основоположниками этой теории являются В.Я. Хасилев, А.П. Меренков, М.Г. Сухарев и др. В настоящей работе исследованы свойства моделей потокораспре-деления при наличии ограничений-неравенств (в том числе двусторонних) на значения переменных с позиций теории симметричной двойственности.

В качестве метода для решения задач потокораспределения в диссертации рассмотрены алгоритмы внутренних точек из особого класса, в которых ограничения-неравенства на переменные учитываются путем введения квадратичной штрафной функции (с итеративно меняющимися весами) в целевую функцию вспомогательной задачи поиска направления улучшения решения. Пионерами в разработке алгоритмов этого класса были в 60 - 70-х гг. XX века И.И. Дикин, Ю.Г. Евтушенко, В.Г. Жадан, С.М. Анцыз, В.И. Зоркальцев. В середине 80-х годов этот класс алгоритмов привлек повышенное внимание исследователей во всём мире. Вклад в развитие алгоритмов внутренних точек внесли И. Адлер, Р. Вандербей, Н. Кармаркар, М. Коджима, Р. Монтейро, A.C. Неми-ровский, Ю.Е. Нестеров, М. Тодц, Т. Тсучия и др. Эти алгоритмы для рассматриваемых задач выполняют роль обобщений (на случай наличия ограничений-неравенств) хорошо зарекомендовавших себя при расчетах гидравлических цепей методов контурных расходов и узловых давлений. К тому же в настоящее время является общепризнанной их высокая численная эффективность.

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

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

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

2) на базе теории симметричной двойственности исследовать свойства нелинейных моделей потокораспределения с ограничениями-неравенствами;

3) провести сравнительные экспериментальные исследования вариантов

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

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

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

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

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

Предложена новая нелинейная модель оценки возможностей Единой системы газоснабжения (ЕСГ) или Единой системы нефтеснабжения (ЕСН) в чрезвычайных ситуациях, являющаяся развитием существующей в ИСЭМ СО РАН кусочно-линейной модели. Для предложенной модели даны рекомендации по использованию двойственных оценок для более детального ранжирования «узких» мест транспортной сети, что является новым в работах по исследованию живучести ЕСГ и ЕСН. Предложены новые интерпретации постановок нелинейных транспортных задач на базе теории симметричной двойственности.

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

Практическая значимость

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

энергетики в чрезвычайных ситуациях.

2) Разработанный программный модуль, реализующий алгоритм внутренних точек для расчета нелинейной модели оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях, внедрен в программный комплекс «Нефть и газ России» (ИСЭМ СО РАН).

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

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

5) Материалы диссертации используются в спецкурсе «Сетевые модели экономики и энергетики», читаемом студентам ИМЭИ ИГУ.

Соответствие диссертации паспорту научной специальности. В соответствии с паспортом специальности 05.13.01 в диссертации проведено развитие теории симметричной двойственности в оптимизации; выполнена формализация и постановка задач потокораспределения; усовершенствованы критерии оценки эффективности решения задач оптимизации для исследования энергетической безопасности; разработано специальное математическое и программное обеспечение для решения этих задач, а также для визуализации исходных данных (пп. 1-3, 5, 12 области исследований).

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

Апробация работы. Исследования по теме диссертации выполнены в рамках проектов РФФИ №05-01-00587а, №09-01-00306-а, РГНФ №06-02-0026ба и были представлены на 22 конференциях, в том числе: 5 международных, 7 всероссийских. Диссертация обсуждалась на совместном заседании секций «Специализированные системы энергетики» и «Прикладная математика и информатика» ИСЭМ СО РАН (2010, Иркутск); на совместном заседании семинаров «Математическая экономика» и «Модели экономических систем с иерархией в управлении» ИМ СО РАН (2011, Новосибирск); на объединенном семинаре ИВМиМГ и кафедры вычислительной математики НГУ (2011, Новосибирск); на семинаре Отделения методов управления и исследования операций ИДСТУ СО РАН (2011, 2013, Иркутск).

Публикации. Результаты, изложенные в диссертации, опубликованы в 31 работе^ среди которых 18 статей, в том числе в реферируемых журналах из спи-

ска ВАК - 5 статей. Результаты главы 2 опубликованы в [1-5, 7, 9], главы 3 - в [4-6,8, 11], главы4-в[1-3, 7, 9, 10, 12].

Личный вклад автора. Все основные научные результаты, выносимые на защиту, получены автором самостоятельно и не нарушают авторских прав других лиц. Из совместных публикаций с В.И. Зоркальцевым, С.П. Епифановым, С.М. Пержабинским в диссертационную работу включены результаты, не затрагивающие интересы соавторов. A.B. Еделев осуществлял консультирование и помощь с внедрением нелинейной модели оценки возможностей ЕСГ или ЕСН.

Структура и объем работы. Диссертация изложена на 135 страницах и состоит из введения, четырех глав, заключения, списка литературы, который содержит 188 наименований, и приложения. В диссертации содержится 7 рисунков, 16 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Основное внимание уделяется важному для многих приложений подклассу задач минимизации сепарабельной строго выпуклой функции при линейных ограничениях в виде равенств и неравенств на отдельные переменные. Теоретической основой для симметричной двойственности здесь служит теория альтернативных систем линейных неравенств и преобразование Лежандра-Фенхеля, известное из выпуклого анализа Приводится определение этого преобразования, рассматриваются некоторые его свойства и области применения в математике и физике. Указанный подкласс задач исследовался ранее в работах В.И. Зоркальцева, причём рассматривались только ограничения-равенства и односторонние ограничения-неравенства на переменные. Есть необходимость в развитии симметричной двойственности на случай наличия двусторонних ограничений на отдельные переменные. Такое развитие необходимо для реализации и исследования некоторых моделей экономических и технических систем, в том числе рассматриваемых в диссертации.

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

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

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

В работе рассмотрены также нелинейные транспортные модели, в которых затраты на перевозки по отдельным дугам заданы в виде нелинейных функций от объемов перевозок. Во многих случаях такие модели более адекватны действительности, чем традиционно рассматриваемые линейные. Особое внимание уделено транспортным моделям, применяемым для исследования проблем обеспечения энергетической безопасности страны и её регионов. В §1.2 приводится постановка линейной модели, используемой в ИСЭМ СО РАН для оценки производственных возможностей отраслевых систем энергетики в экстремальных ситуациях и при наличии разного рода возмущений в системе. С целью более адекватного описания рисков от использования на отдельных дугах режимов повышенной нагрузки предложено рассмотреть возможность использования нелинейной транспортной модели с двусторонними ограничениями на отдельные переменные. Для интерпретации решений таких нелинейных транспортных моделей, в том числе для улучшения существующей методики ранжирования «узких мест», представляется целесообразным использовать теорию симметричной двойственности.

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

1 Епифанов С. П. Приложение теории двойственное™ к моделям потокораспределения: Дисс... канд. физико-математических наук: 05.13.18. - Иркутск, 2006.-97С.

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

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

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

Пусть Z - класс функций одного вещественного аргумента, которые равны нулю в нуле и имеют непрерывные, возрастающие производные. Требуется также, чтобы для производной g функции G из класса Z выполнялось равенство g(0) = 0 и она обладала следующими свойствами: g(ar)-»-oo при а->-со; g(a) -» +00 при а +со.

Каждой функции G е Z соответствует единственная функция Н е Z такая, что производные функций G и Н будут взаимно обратными функциями. Данная функция Н является преобразованием Лежандра-Фенхеля функции G, функция G в этом случае является преобразованием Лежандра-Фенхеля функции Н. Эти функции называются сопряженными.

Пусть задана матрица А размера тхп, вектор b е Rm, вектор sei?", множество номеров J = {1,...,«}. Множества L, Н являются подмножествами J. Заданы величины х,, je L, xr j е Н и функция F(x) = £ F/ (х{), где Fj е Z, j е J.

Рассмотрим исходную задачу оптимизации:

F(x) + s'x->min, (1)

Ах = Ь, (2)

Xj<Xj,jeL, (3)

xi j е Н ■ (4)

Расширенным решением исходной задачи назовем набор, состоящий из вектора исходных переменных х е R", вектора u е R'" множителей Лагранжа ограничений (2), векторов I е R" и h е R", содержащих множители Лагранжа ограничений (3) и (4), причем ¡¡ = 0, j eJ\L и hj = О, j е J\Н, а также вектора уе/?" с компонентами у, =fj(x,), где ft - производная функции Fhj е J.

Пусть - функция из Z, являющаяся преобразованием Лежандра-Фенхеля

функции Fj для jeJ. Введём функцию Ф(у) = Х^Д-Уу) вектора у & R". Обо-

ieJ

значим cpj производную функции Ф,.

Рассмотрим двойственную задачу оптимизации:

Ф(у) -b' u - ^Xjlj + Yßihi min (5>

y'si jell

y+s-I + h = ATu, (6)

>0, jeL, hj >0, /еЯ, (?)

lj=0, jeJ, jiL, A, = 0, j & J, j i H. (8)

Переменными в задаче являются векторы у е R", u е Rm, I е R", h sR .

Расширенным решением двойственной задачи назовем набор из векторов х, у, u, I, h, где х е R" - вектор множителей Лагранжа ограничений (6).

Рассмотрим систему уравнений и неравенств относительно векторов х е R", и е 7Г, у e R" и чисел /,, j е L; h.b jeH, содержащую условия (2)-(4), (8), а

также следующие условия:

y,=fj(Xj),jeJ, (9).

/у(*;)=[А(Ю)

fj{xj) = шах{fM,\ [Aru]y-Sj}, j&L\H, (П)

/Д*,) = тт{/ДхД [A7u],-sy}, jeH\L, (12)

=min{/¡(Xj),max{ fj(xj), [A7u],-Sy}}, jeLr>H, (13)

ijHfMJ+sriАЧь (14)

hj = ([A7 u], — /J (xy) > У'еЯ- (15)

Здесь J" =J\(LkjH); символом ()+ обозначена неотрицательная срезка: («)+ = max{0, а}.

Теорема. Любое решение системы (2)-(4), (8), (9)-(15) является расширенным решением исходной задачи оптимизации ОН4)- Любое расширенное

решение исходной задачи оптимизации является расширенным решением двойственной задачи оптимизации (5)-(8). Любое расширенное решение двойственной задачи оптимизации является решением системы (2)-(4), (8), (9)-0 5)- Для существования решений трех рассматриваемых задач достаточно совместности условий (2)-(4).

Приведенная теорема устанавливает эквивалентность трех введенных задач: решение любой из них позволяет получать решения остальных двух задач. В силу строгой выпуклости функций F и Ф для любого решения рассматриваемых задач векторы х и у имеют единственное значение. Отметим, что использование функций шах и min в (11)-(13) и неотрицательной срезки в (14), (15) позволяет исключить билинейные условия дополняющей нежесткости, традиционно присутствующие в условиях оптимальности Куна-Таккера.

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

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

Согласно доказанной теореме для выявления случая отсутствия решения у рассматриваемых задач требуется показать несовместность условий (2)-(4). В диссертации получен конструктивный критерий для выявления такого случая, который состоит (согласно теории альтернативных систем линейных неравенств) в констатации существования решения у системы, содержащей условия (7), (8), а также условия

Ауи + 1 -И = 0, + >0- <16)

уе/. ,/€Я

Если система (7), (8), (16) имеет решение, то ограничения исходной задачи несовместны, а целевая функция двойственной задачи не ограничена снизу.

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

В главе 3 приводятся результаты экспериментальных исследований прямых и двойственных алгоритмов внутренних точек для взаимно двойственных задач оптимизации на моделях потокораспределения. Итерационный процесс прямых алгоритмов внутренних точек решения исходной задачи ОМ4) заключается в последовательном построении нового приближения х*+| =х* + ХкА\к, где Дх* - направление корректировки текущего приближения, Лк - величина шага вдоль этого направления. Процесс начинается из точки

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

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

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

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

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

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

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

Характеристики задач Среднее кол-во итераций для вар-тов алгоритма

узлов ветвей решено задач среднее число двусторонних ограничений Прямой | Двойств. Прямой ) Двойств.

Квадратичные весовые коэффиц. Линейные весовые коэффициенты

25 39 2 29,6 43,5 44,4 30,2 17,9

25 48 2 40,0 52,9 33,2 30,0 17,3

50 60 2 35,4 62,5 37,9 52,3 23,5

50 136 2 93,8 90,9 46,6 25,0 25,5

100 116 2 40,2 66,9 24,2 31,7 23,0

100 195 2 84,3 53,5 83,7 32,0 26,5

200 300 2 150,0 82,3 34,8 31,8 20,3

338 712 2 500,0 101,8 82,4 32,4 26,7

среднее геометрическое: 66,7 44,4 32,5 22,3

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

Для прямого алгоритма в случае двусторонних ограничений на переменные квадратичные коэффициенты представлялись в виде = (тш(х* -хпх) -**))2,

а линейные - в виде г/* = тт(.х* -х* )/тах(<-52, /*"', А*"1), где 8г - ма-

лая константа. Критерием остановки алгоритмов было выполнение условий (2)-(4), (8), (9)—(15) с заданной точностью.

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

В другом эксперименте были проведены расчеты для сравнения скорости достижения требуемой точности решения по исходным и по двойственным переменным. Точность текущего приближения вычислялась по норме отклонения его от предварительно найденного решения, для которого максимальная невязка условий (2)—(4), (8), (9>—<15) была менее 10'7. На рис. 1 приведены графики изменения нормы отклонения текущего приближения от точного решения по исходным и двойственным переменным в процессе решения задачи потокорас-пределения с матрицей А размера 200x300 прямым и двойственным алгоритмами с линейными весовыми коэффициентами.

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

-ю

Номер итерации

—«—Прямой алг. (по исходи, перем.)

—В- Прямой алг. (по двойств, перем.)

—»—Деойств. алг. (по двойств, перем.)

—©—Двойств, алг. (по исходи, лерем.)

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

Зоркальцев В.И. Класс алгоритмов внутренних точек // Журнал вычислительной математики и математической физики. - 2009. - № 12. - С. 3-28.

зовать двойственные алгоритмы внутренних точек.

Был реализован двойственный алгоритм внутренних точек с линейными весовыми коэффициентами, использующими множители Лагранжа, учитывающий разреженность матрицы инциденций в задачах потокораспределения (ДАВТР). Алгоритмы и процедуры для работы с разреженными матрицами были взяты на сайте университета Флориды.

Таблица 2. Сравнение алгоритма внутренних точек с решателями ТОМЬАВ

Характер, задач Время расчетов решателями оптимизационной среды ТОМЬАВ, сек Время расчетов для ДАВТ_Р, сек Ускорение, разы

узлов ветвей МИМОЗ юмтио СОГЧ'ОРТ БРЮРТ №50Ь РОСО миним. время

50 136 0,203 0,187 0,125 0,078 0,234 0,281 0,078 0,015 5,2

100 П6 0,031 0,203 0,031 0,031 0,062 24,820 0,031 0,015 2,1

100 195 0,218 0,328 0.218 0,062 0,624 0.655 0,062 0.008 7,8

100 195 0,203 0,281 0.218 0.094 0,530 0,764 0,094 0,015 6,3

200 300 0,250 0,577 0,281 0,047 3,401 8,159 0,047 0,016 2,9

200 300 0,234 0,640 0,071 0,140 2,465 13,400 0,071 0,016 4,4

338 712 1,950 3,994 5,179 0,390 52,151 27,940 0,390 0,062 6,3

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

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

|х!Нх->тт, х-АХ = 0, егХ = 1, Х>0, (17)

где заданы матрица Ае Л'"""; вектор Ь е /?", Ь >0 с соответствующей ему диагональной матрицей Н = diag{hl}\ вектор е е Я"1, е = (1,...,1)т. Переменными задачи являются векторы х е Я", X е У?'".

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

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

ван направленный граф с узлами / = 1, ..., т и дугами у" = 1,..., п. В данном случае А - матрица инциденций узлов и дуг. Компоненты вектора Ь - объемы ресурса, входящего в сеть или выходящего из сети в каждом узле. Переменная х, характеризует объем передачи ресурса по дуге ]. Условия (2) задают баланс ресурса в каждом узле (первый закон Кирхгофа). Условия (3), (4) задают ограничения снизу и сверху на потоки некоторых дуг. Если х, = 0, то это означает возможность потока по дуге} е Ь только в одном направлении (например, при наличии запирающего клапана в гидравлической цепи).

Модель гидравлической системы с автоматическими регуляторами расхода. Эта модель может быть описана с помощью системы (2)-(4), (8), (9)-(15). Считаем, что здесь £ = Н, и множество Н задает номера дуг с автоматическими регуляторами расхода. Величины х/е// описывают максимально возможные расходы на дугах. Поток в обратном направлении на дугах с регуляторами запрещён, поэтому х, = 0, /е/„ Зависимость потери напора от расхода на дуге обычно задается в форме Дарси: /,(*,) = , где aJ - коэффици-

ент гидравлического сопротивления. Компоненты вектора -ее/Г есть приращения напора на дугах в результате работы насосов. Согласно доказанной теореме, модель гидравлической системы с автоматическими регуляторами может быть представлена не только в виде системы (2)—(4), (8), (9)-(15), но и в виде исходной (1 )-(4) или двойственной (5)-{8) задач оптимизации.

Компоненты вектора и описывают пьезометрические напоры в узлах. Уравнения (10), (13) выражают баланс потерь, приращений и разности напоров на дугах. Так, согласно (9), (10), для дуг, где нет регуляторов расхода, потеря напора yJ представляется в виде суммы заданного приращения напора на

дуге у и разности напоров [А'и]; в концевых узлах дуги у. Для дуг с регуляторами расхода потеря напора определяется по более сложному правилу, выраженному условием (13). Поскольку ¿=Я и/Дху) = 0, у'е#, то с учетом (9) условие (13) можно представить в виде:

^ = тт{/,(*Д([А:ги],+с/)Л, ;еЯ. (18)

Согласно (18), если [АТи^<0, то у1=0, ;еЯ. Такая величина потери напора у] будет соответствовать нулевому расходу, = Если величина

[Ати];+с; положительная и превосходит значение Д3с;), то у, =Дх/) при Это означает, что регулятор расхода уменьшает (дросселирует) величину напора с; +(Ати); до значения /Дх^, при котором расход по дуге будет равен максимально допустимому расходу х,.

Множители Лагранжа /; и /;, ограничений-неравенств х,> 0, у е I и, соответственно, х) < х) для у е Н, вычисляемые по правилам (14), (15), имеют сле-

дующий физический смысл: величина /у равна разности напоров после и до регулятора на дуге когда расход через него равен нулю; И, - величина дросселируемого напора в регуляторе, когда расход по дуге равен х1.

Особый интерес для модели гидравлической системы с автоматическими регуляторами расхода представляет двойственная задача оптимизации (5)—(8), в которой не используются в явном виде переменные расхода хп j eJ. Решение

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

Нелинейная модель оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях служит для расчета потокораспределения в системе и определения дефицитов поставок газа или нефти потребителям, а также для выявления и ранжирования «узких» мест в транспортной подсистеме ЕСГ или ЕСН. Использование двойственных оценок позволяет численно описать цены на ресурс в узлах, тарифы на перевозку, а также более детально проранжировать «узкие» места в сети.

Множество / = {1,...,/и} номеров узлов разбито на подмножества: - узлы-источники, /' - узлы-потребители, 1Г - узлы разветвления. Модель представлена задачей, неизвестные в которой составляют веторы х е /?" и Ь 6 Кт: £(/?(*,)+.?/,)+ -¿>)->тт, (19)

/Ь/ /е/1

Ах = Ь, 0 < х < х, (20)

Ь,<Ь,<0, /е/*, 0 <Ь,<Ьп / е /г, ¿,=0, /е/г. (21)

Компоненты вектора х - объемы передачи ресурса по дугам сети. Величины ¡6,1, / е /л соответствуют объемам поставок ресурса в сеть в узлах-источниках, Ьп / е Iе - объемы отбора ресурса из сети в узлах-потребителях. Условия (21) ограничивают объемы ввода ресурса в сеть в узлах-источниках и объемы вывода ресурса из сети в узлах-потребителях.

Целевая функция содержит суммарные издержки от передачи ресурса по всем дугам + 5,*,) и суммарный штраф ^г:(Ь, ~Ь:) за неполное

удовлетворение потребности в узлах-потребителях.

В задаче (19)—<21) заданы: г: > 0, /е /! - коэффициенты штрафа за неполное удовлетворение потребности в узлах; величины Sj, jeJ - линейные коэффициенты издержек на передачу; ,(■*>)» у е-/ — нелинейные функции такие, что Р¡(х,) = 0 при 0 < х] < х , и /^(Ду) = Р, (х. - Зс;) при х; > х], где Fj е 2.

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

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

Вектор и множителей Лагранжа ограничений-равенств из (20) имеет смысл цен на ресурс в узлах. В нормальном режиме приращение цены ресурса [А и], на дуге у равно Если дуга находится в режиме повышенной нагрузки, то [Лги]7 > я,, а величина Р/х,) > 0 отражает возможные ущербы от выхода из строя оборудования в этом режиме. Нелинейная функция лучше подходит для моделирования, чем линейная. В случае нелинейной целевой функции решение по Xj в режиме повышенной нагрузки может лежать внутри отрезка [Зс,, х/[. В случае линейной целевой функции решение достигается на одной из границ указанного отрезка, если такое решение допустимо.

Если х]> то дуга у считается «узким» местом. Ранжирование «узких» мест в системе нужно проводить с учетом величины х/-х/г характеризующей объем передачи при повышенной нагрузке, а также с учетом функции возможных ущербов /^(х,) от выхода из строя оборудования в режиме повышенной нагрузки. Дуги с большими значениями функции Р/х^ должны иметь больший приоритет при проведении работ по увеличению пропускной способности «узких» мест. Полезна и информация, которую содержат множители Лагранжа /гу ограничений х; <х, ,jsJ. Если > 0, то для уменьшения целевой функции (19) требуется увеличение пропускной способности х, на дуге у. Чем выше И,-, тем больший приоритет должен быть у дуги

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

Предложенная нелинейная модель лучше описывает возможные ущербы от выхода из строя оборудования в чрезвычайных ситуациях, чем ранее использовавшаяся в ИСЭМ СО РАН линейная модель. Информация, которую содержат двойственные оценки, полезна для решения задач ранжирования узких мест систем ЕСГ или ЕСН.

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

В приложении представлена справка о внедрении программного модуля, реализующего алгоритм внутренних точек для нелинейной модели оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях, в программный комплекс «Нефть и газ России», разработанного под руководством д.т.н. С.М. Сендерова.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

2) На основе теории симметричной двойственности получена содержательная интерпретация нелинейных моделей потокораспределения с двусторонними ограничениями на переменные. Разработана нелинейная модель оценки возможностей функционирования в чрезвычайных ситуациях Единых систем газо- или нефтеснабжения. Для этой модели даны рекомендации по использованию двойственных оценок при ранжировании «узких» мест сети.

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

Публикации в изданиях из списка ВАК по теме диссертации

1. Зоркальцев В.И., Медвежонков Д.С. Транспортная модель с нелинейными затратами на перевозку // Современные технологии. Системный анализ. Моделирование. - Иркутск: ИрГУПС. -2008. -№3 (19). - С. 87-97.

2. Медвежонков Д.С. Транспортная модель с кусочно-заданными нелинейными издержками // Современные технологии. Системный анализ. Моделирование. - Иркутск: ИрГУПС. - 2009. - №4 (24). - С. 220-225.

3. Епифанов С. П., Зоркальцев В. И., Медвежонков Д. С. Модель гидравлической сети с регуляторами расхода// Управление большими системами. - М.: ИПУ РАН, 2010. - Специальный выпуск ЗОЛ "Сетевые модели в управлении". - С. 286-299.

4. Медвежонков Д.С. Экспериментальные исследования алгоритмов внутренних точек на нелинейных задачах потокораспределения // Вестник Бурятского гос. ун-та.-2013.-Вып. 9.-С. 12-16.

5. Зоркальцев В.И., Медвежонков Д.С. Численные эксперименты с вариантами алгоритмов внутренних точек на нелинейных задачах потокораспределения // Управление большими системами: электрон, журн. 30.11.2013. URL: http://ubs.mtas.ru/uploacl/librarv7UBS4602.pclf (дата обращения: 30.11.2013).

Публикации в зарубежных журналах

6. Зоркальцев В.И., Медвежонков Д.С. Экспериментальные исследования ал-

горитмов внутренних точек на задачах потокораспределения // Вестник университета «Туран». - Казахстан, Ллматы: Университет Туран. - 2011. - № 4 (52). -С. 127-133.

Публикации и трудах международных конференций

7. Зоркальцев В.И., Медвежонков Д.С. Нелинейная транспортная модель // Тр. Всерос. конф. «Равновесные модели экономики и энергетики» и секции Математической экономики XIV Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». - Иркутск: ИСЭМ СО РАН, 2008.-С. 586-600.

8. Зоркальцев В.И., Медвежонков Д.С., Пержабинский С.М. Опыт использования алгоритмов внутренних точек в моделях энергетики // Междунар. научно-практическая конф. «Актуальные проблемы математики, информатики, механики и теории управления»: Материалы конференции (19-20 ноября 2009 года, Алматы, Казахстан). - С. 158-166.

9. Зоркальцев В.И., Епифанов С.П., Медвежонков Д.С. Симметричная двойственность в оптимизации и модели потокораспределения при ограничениях неравенствах на переменные // Математическое моделирование трубопроводных систем энергетики / Тр. XII Всерос. науч. семинара с междунар. участием «Математические модели и методы анализа и оптимального синтеза развивающихся трубопроводных и гидравлических систем». - Иркутск, ИСЭМ СО РАН. - 2010. - С. 123-139.

10. Медвежонков Д.С. Нелинейная сетевая модель для исследования живучести отраслевых систем газо- и нефтеснабжения в чрезвычайных ситуациях // II Междунар. школа-семинар «Нелинейный анализ и экстремальные задачи»: Тезисы. -Иркутск: Изд-во ИДСТУ СО РАН, 2010. - С. 54.

11. Медвежонков Д.С. Экспериментальные исследования прямого и двойственного алгоритма внутренних точек на классе задач потокораспределения // Тр. XV Байкальской междунар. школы-семинара "Методы оптимизации и их приложения". Т. 2: Математическое программирование - Иркутск: РИО ИДСТУ СО РАН, 2011.-С. 131-138.

12. Медвежонков Д.С. Моделирование транспортных систем с использованием двойственных задач выпуклой оптимизации // Тр. XV Байкальской междунар. школы-семинара "Методы оптимизации и их приложения". Т. 6: Математическая экономика. - Иркутск: РИО ИДСТУ СО РАН, 2011.-С. 191-196.

Редакционно-издательский отдел ФГБУН Института динамики систем и теории управления СО РАН 664033, Иркутск, ул. Лермонтова, д. 134

Подписано к печати 18.11.2013 Формат бумаги 60x84 1/16, объем 1,2 п.л.

_Заказ 6. Тираж 120 экз.

Отпечатано в ИДСТУ СО РАН

Федеральное государственное бюджетное учреждение науки Институт систем энергетики им. Л.А. Мелентьева Сибирского отделения Российской академии наук

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

0«0К5«35

МЕДВЕЖОНКОВ Дмитрий Сергеевич

СИММЕТРИЧНАЯ ДВОЙСТВЕННОСТЬ В ВЫПУКЛОЙ ОПТИМИЗАЦИИ И МОДЕЛИ ПОТОКОРАСПРЕДЕЛЕНИЯ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в технике, экологии и экономике)

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д.т.н., проф. В.И. Зоркальцев

Иркутск -2013

Содержание

Введение 3 Глава 1. Обзор по теории симметричной двойственности, моделям

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

§1.1. Основы симметричной двойственности задач оптимизации -§1.2. Модели потокораспределения и задачи оптимизации 20 §1.3. Метод внутренних точек как способ расчета моделей 27 §1.4. Выводы по главе 30 Глава 2. Симметричная двойственность в задачах выпуклой оптимизации с ограничениями-неравенствами 33 §2.1. Двойственность задач оптимизации со строго выпуклой дифференцируемой целевой функцией -§2.2. Обсуждение свойств двойственных задач оптимизации 47 Глава 3. Реализация и исследование вариантов алгоритмов внутренних точек 49 §3.1. Прямые алгоритмы внутренних точек 50 §3.2. Двойственные алгоритмы внутренних точек 55 §3.3. Численные эксперименты на задачах потокораспределения 60 §3.4. Расчеты на задачах проекции точки на политоп 73 Глава 4. Нелинейные модели потокораспределения в экономике и

энергетике 81 §4.1. Модель гидравлической системы с автоматическими регуляторами расхода -§4.2. Нелинейная транспортная модель (экономическая интерпретация; варианты потокораспределения и тарифообразования) 89 §4.3. Нелинейная модель оценки возможностей ЕСГ или ЕСН в

чрезвычайных ситуациях 102

Заключение 111

Список литературы 116

Приложение. Справка о внедрении 135

Введение

Актуальность проблемы

Математическое моделирование и методы оптимизации важны при поиске системных связей и закономерностей функционирования сложных систем, для повышения эффективности управления в технических, экономических, социальных системах. Современная теория оптимизации во многих случаях служит методической основой для выбора наилучших экономических и технических решений, средством математического моделирования, инструментом вычислительной математики. Весомый вклад в развитие теории и методов оптимизации внесли: А. Таккер, J1.B. Канторович, Дж. Данциг, X. Кун, Г. Зойтендейк, Е.Г. Гольштейн, И.И. Еремин, В.П. Булатов, Б.Т. Поляк, Ф.П. Васильев, Н.З. Шор, Б.Н. Пшеничный, В.Ф. Демьянов, Ю.Г. Евтушенко, У. Зангвилл и многие другие. [7, 13, 14, 24, 33, 42, 109, 128, 136, 139, 142, 144, 145, 154, 157, 167, 174, 180].

Одним из важнейших разделов теории оптимизации является теория двойственности [7, 13, 39, 67, 112, 158, 184, 188]. Двойственные задачи оптимизации применяются для доказательства оптимальности полученного решения, для анализа его устойчивости к варьированию исходных данных, для содержательной интерпретации математических моделей, теоретического обоснования и разработки новых алгоритмов решения задач математического программирования.

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

ность имеет место. Например, в работах У. Дорна [152], Дж. Денниса [16], а также С.И. Зуховицкого, Л.И. Авдеевой [65] формулируются симметричные двойственные задачи квадратичного программирования. Симметричная двойственность задач оптимизации с целевой функцией, выпуклой по одному векторному аргументу и вогнутой по другому, исследовалась в работах Г. Данцига, Е. Эйзенберга, Р. Коттла [150], М. Базара, Дж. Гуди [134], Г. Дэви [151], Б. Монда, Т. Вейра [169, 170] и др.

Основное внимание в диссертации уделяется симметричной двойственности на важном во многих приложениях подклассе задач минимизации се-парабельной дифференцируемой строго выпуклой функции при линейных ограничениях в виде равенств и неравенств на значения отдельных переменных. Теоретической основой для симметричной двойственности на этом классе задач служит теория альтернативных систем линейных неравенств [10, 40, 116, 125, 146, 147] и преобразование Лежандра-Фенхеля [80, 111, 127, 153, 176], известное из выпуклого анализа. Указанный подкласс задач исследовался ранее в работах научного руководителя, причём рассматривались только ограничения-равенства и односторонние ограничения-неравенства на переменные [28, 31, 50-53]. Теоремы, доказываемые в диссертации, развивают существующие исследования на случай задач оптимизации с двусторонними ограничениями-неравенствами на отдельные переменные.

В качестве объекта приложения симметричных двойственных задач оптимизации в диссертации рассматриваются модели потокораспределе-ния. Рассматриваемые модели можно разбить на два класса, различающиеся содержательной интерпретацией: гидравлические цепи и нелинейные транспортные модели (обобщающие линейные транспортные задачи).

В начале XX века в работах М.М. Андрияшева, В.Г. Лобачева, X. Кросса [3, 79, 148] были предложены первые методы расчета гидравлических сетей. С середины 60-х годов XX в. начала формироваться (в рамках системных научных исследований) теория гидравлических цепей, обобщаю-

щая методы моделирования и оптимизации трубопроводных систем. Вклад в ее развитие внесли В.Я. Хасилев, А.П. Меренков, М.Г. Сухарев, А.Г. Евдокимов, А.Д. Тевяшев, C.B. Сумароков, Е.В. Сеннова, H.H. Новицкий и др. [20, 22, 73, 101, 102, 107, 114, 123, 132, 168, 185].

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

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

В качестве объекта приложения теории симметричной двойственности в диссертации рассматриваются также нелинейные транспортные модели, в которых затраты на перевозки по отдельным дугам задаются в виде нелинейных функций от объемов перевозок. Во многих случаях такие модели более адекватны действительности, чем традиционно рассматриваемые линейные транспортные модели [15, 68-71, 117-119, 122, 135, 155,

160, 162, 165, 166]. Нелинейные транспортные модели исследовались с конца 40-х гг. XX в работах Р.Д. Даффина, Г. Биркхофа, Д. Диаза, Д. Денниса, Миллара, Г.Д. Минти, В.Н. Лившица, Р. Рокафеллара, Д. Бертсекаса, Л.Д. Попова, Е.А. Нурминского и других [8, 16, 75-78, 108, 129, 138, 141, 143, 177]. Одним из важных аспектов нелинейных транспортных моделей, рассматриваемых в диссертации является выбор альтернативы формирования тарифов на перевозки - по предельным или по средним затратам.

В диссертации подробно рассматривается одно из конкретных приложений транспортных моделей для исследования проблем обеспечения энергетической безопасности страны и её регионов. В качестве развития линейной модели оценки производственных возможностей отраслевых систем энергетики в экстремальных ситуациях, используемой в ИСЭМ СО РАН, в диссертации предлагается рассмотреть нелинейную транспортную модель с двусторонними ограничениями-неравенствами. Нелинейная целевая функция более адекватно описывает риски от использования на отдельных транспортных ветвях режимов повышенной (относительно нормы) нагрузки. Для улучшения существующей методики ранжирования «узких мест» представляется целесообразным использовать факты симметричной двойственности.

Для расчета моделей потокораспределения могут применяться различные алгоритмы [137, 140, 159, 163, 175, 183, 187], в том числе из имеющегося большого разнообразия методов выпуклого программирования. В диссертационной работе акцент сделан на сравнительных экспериментальных исследованиях вариантов алгоритмов внутренних точек из особого класса, в которых ограничения-неравенства на переменные учитываются путем введения квадратичной штрафной функции (с итеративно меняющимися весами) в целевую функцию вспомогательной задачи поиска направления улучшения решения. Пионерами в разработке этих алгоритмов были в СССР в 60 - 70-х гг. XX века С.М. Анцыз, И.И. Дикин, Ю.Г. Евтушенко, В.Г. Жа-дан, В.И. Зоркальцев [17, 18, 23, 24]. В СО РАН эти алгоритмы использова-

лись при реализации ряда моделей энергетики [19, 20, 44, 45, 49].

Повышенный интерес к алгоритмам внутренних точек во всем мире возник в 80-х годах прошлого века благодаря работам Л.Г. Хачияна, Д.Б. Юдина, Н. Кармаркара, A.C. Немировского, Ю.Е. Нестерова над полиномиальными методами. Эти работы послужили импульсом для появления большого числа публикаций, посвященных теоретическим и экспериментальным исследованиям алгоритмов внутренних точек. Весомый вклад в развитие алгоритмов внутренних точек внесли зарубежные ученые: И. Адлер, Р. Вандербей, М. Коджима, Г. Мак-Кормик, Р. Монтейро, Ш. Мицу-но, М. Тодд, Т. Тсучия, А. Фиакко и др. [120, 133, 164, 174, 182].

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

Можно выделить два подмножества алгоритмов внутренних точек рассматриваемого класса: прямые и двойственные алгоритмы. Симметричная двойственность имеет принципиальное значение для двойственных алгоритмов внутренних точек; без этого свойства их использование было бы невозможным. Частным случаем рассматриваемых алгоритмов является известные affine scaling method [133, 182] и dual affine scaling method для решения задач линейного программирования.

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

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

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

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

2) на базе теории симметричной двойственности исследовать свойства нелинейных моделей потокораспределения с ограничениями-неравенствами;

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

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

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

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

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

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

2) На основе теории симметричной двойственности получена содержательная интерпретация нелинейных моделей потокораспределения с двусторонними ограничениями на переменные. Разработана нелинейная модель оценки возможностей функционирования в чрезвычайных ситуациях Единых систем газо- или нефтеснабжения. Для этой модели даны рекомендации по использованию двойственных оценок при ранжировании «узких» мест сети.

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

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

таких задач.

Предложена новая нелинейная модель оценки возможностей Единой системы газоснабжения (ЕСГ) или Единой системы нефтеснабжения (ЕСН) в чрезвычайных ситуациях, являющаяся развитием существующей в ИСЭМ СО РАН линейной модели. Для предложенной модели даны рекомендации по использованию двойственных оценок для более детального ранжирования «узких» мест транспортной сети, что является новым в работах по исследованию живучести ЕСГ и ЕСН. Предложены новые интерпретации постановок нелинейных транспортных задач на базе теории симметричной двойственности.

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

Практическая значимость

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

2) Разработанный программный модуль, реализующи