Симметричная двойственность в выпуклой оптимизации и модели потокораспределения тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Медвежонков, Дмитрий Сергеевич

• Медвежонков, Дмитрий Сергеевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Медвежонков, Дмитрий Сергеевич

Содержание

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

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

§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. Нелинейная модель оценки возможностей ЕСГ или ЕСН в

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

Заключение

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

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

Введение диссертации (часть автореферата) на тему «Симметричная двойственность в выпуклой оптимизации и модели потокораспределения»

Введение

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

Математическое моделирование и методы оптимизации важны при поиске системных связей и закономерностей функционирования сложных систем, для повышения эффективности управления в технических, экономических, социальных системах. Современная теория оптимизации во многих случаях служит методической основой для выбора наилучших экономических и технических решений, средством математического моделирования, инструментом вычислительной математики. Весомый вклад в развитие теории и методов оптимизации внесли: А. Таккер, 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) Разработанный программный модуль, реализующий алгоритм внутренних точек для расчета нелинейной модели оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях, внедрен в программный комплекс «Нефть и газ России» (ИСЭМ СО РАН).

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

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

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

Соответствие диссертации паспорту научной специальности. В

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

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

Апробация работы

Исследования по теме диссертации выполнялись в рамках проектов РФФИ №05-01-00587а, №09-01-00306-а, РГНФ №06-02-00266а. Докладывались и обсуждались на 22 конференциях, из них: 5 международных и 7 всероссийских. В том числе: на научно-теор. конференциях молодых ученых

ИГУ (2006, 2007); на XXXVI-XXXXI конференциях научной молодежи ИСЭМ СО РАН (2006-2011); на Межвуз. конф. «Математика и проблемы ее преподав, в вузе» (2007, Иркутск, ИГГГУ); на IX Школе-семинаре молодых ученых "Мат. моделир. и инф. технологии" (2007, Иркутск, Ангасолка, оз. Байкал); на III и IV Всеросс. конф. «Проблемы оптимизации и экономические приложения» (2006, 2009, Омск, Омский филиал ИМ СО РАН); на Российской конф. "Дискретная оптимизация и исследование операций" (2007, Владивосток, ИМ СО РАН, ИАПУ ДВО РАН); на международной научно-практ. конф. «Актуальные проблемы математики, информатики, механики и теории управления» (2009, Алматы, Казахстан); на II Междунар. школе-семинаре «Нелинейный анализ и экстремальные задачи» (2010, Иркутск, ИДСТУ СО РАН); Всеросс. научн. семинаре с междунар. участием «Математические модели и методы анализа и оптимальн. синтеза развивающ. трубопроводных и гидравлич. систем» (2010, Ялта, Украина); на XIV Всеросс. конф. «Мат. про-граммир. и прилож.» (2011, ИММ УрО РАН, Екатеринбург); на Российско-Монгольской конф. мол. ученых по мат. моделир., вычисл.-инфор-мац. технологиям и управлению (2011, Ханх, Монголия); на XIV и XV Байкальской междунар. школе-семинаре «Методы оптимиз. и их приложения» (2008, Севе-робайк.; 2011, п. Листвянка, оз. Байкал). Работа обсуждалась на семинарах в научных институтах: на совместном заседании секций «Специализир. системы энергетики» и «Прикл. математика и информатика» ИСЭМ СО РАН (2010, Иркутск); на совм. заседании семинаров «Мат. экономика» и «Модели экономич. систем с иерархией в управлении» ИМ СО РАН (2011, Новосибирск); на объединенном семинаре ИВМиМГ и кафедры выч. математики НГУ (2011, Новосибирск); на семинаре Отделения методов управления и исследования операций ИДСТУ СО РАН (2011, 2013, Иркутск).

Публикации

Результаты опубликованы в 31 печатной работе [30, 32, 54-57, 60-64, 81-100]. Из этих работ 18 статей, в том числе: 5 статей в реферируемых

журналах из списка ВАК [32, 56, 64, 92, 100], 1 статья [62] в зарубежном журнале. В числе публикаций 6 текстов докладов [55, 57, 63, 95, 98, 99] в материалах международных конференций.

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

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

Глава 1. Обзор по теории симметричной двойственности, моделям потокораспределения и алгоритмам внутренних точек

§1.1. Основы симметричной двойственности задач оптимизации

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

В диссертации сформулированы и доказаны теоремы, обосновывающие симметричную двойственность задач выпуклого программирования с линейными ограничениями, в том числе с двусторонними неравенствами на значения переменных. Эти теоремы развивают исследования, начатые в работах [28, 29, 31, 50-53]. Для доказательства теорем симметричной двойственности и исследования свойств задач оптимизации используются факты теории альтернативных систем линейных неравенств и свойства преобразования Лежандра-Фенхеля.

Теория альтернативных систем линейных неравенств

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

ных неравенств с минимальным набором активных ограничений [116].

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

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

Вклад в развитие теории альтернативных систем линейных неравенств внесли работы П. Гордана, Г. Минковского, Г. Фаркаша, Д. Гейла [10], С.Н. Черникова [125], И.И. Еремина [40], H.H. Астафьева [33], К.Г. Бройдена [147, 146], А.И. Голикова, Ю.Г. Евтушенко [12], В.И. Зоркальце-ва [116] и других.

Симметричная двойственность в линейном программировании

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

Одним из первых идею двойственности в задачах ЛП исследовал Л.В. Канторович. Развивая методы решения транспортной задачи, он еще в 1940 предложил метод разрешающих множителей, который можно рассматривать как идейную основу известного симплекс-метода, предложенного в 1947 г. Дж. Данцигом [15]. Развивая теорию и методы ЛП для реше-

ния задач экономики и производства, Л. В. Канторович ввел «двойственные оценки» ресурсов [71] (сам он называл их «объективно обусловленными оценками»), показывающие степень ценности этих ресурсов для общества. В своих работах Л.В. Канторович развил идею о том, что каждое оптимальное производственное и управленческое решение взаимосвязано с оптимальной системой цен, заданных двойственными оценками.

В работах И.И. Еремина исследовались постановки несобственных двойственных задач линейного программирования [34, 35], а также симметричных двойственных задач последовательного линейного программирования [36]. Перенос симметричной двойственности на ситуацию парето-лексикографических задач оптимизации, в частности в предположениях несобственности, реализован в работах [37-39].

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

Симметричная двойственность в нелинейном программировании

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

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

Симметричная двойственность для задач оптимизации вещественной

функции /(х,у), выпуклой по вектору переменных х и вогнутой по вектору переменных у формулируется в работах Г. Данцига, Е. Эйзенберга, и

Р. Коттла [150], а также Б. Монда [169]. Обобщение результатов Г. Данцига и др. выполнено в работах М. Базараа и Дж. Гуди [134], а также Г. Дэви [151]. Б. Монд и Т. Вейр в статье [170] сформулировали постановки симметричных двойственных задач с псевдовыпуклой-псевдовогнутой целевой функцией.

Список литературы диссертационного исследования кандидат наук Медвежонков, Дмитрий Сергеевич, 2013 год

СПИСОК ЛИТЕРАТУРЫ

1. Айзенберг Н. И. Теоретические основы регулирования естественных монополий. - Иркутск: ИСЭМ СО РАН, 2006. - 29 с.

2. Алексеев В.М., Тихомиров В.М., Фомин C.B. Оптимальное управление - М.: Наука. - Гл. ред. физ.-мат. лит., 1979. - 430 е., ил.

3. Андрияшев M. М. Техника расчета водопроводной сети. - М.: Сов. Законодательство, 1932. - 62 с.

4. Арнольд В.И. Математические методы классической механики: Учеб. пособие для вузов. - М: Наука, 1989 г. - 472 с.

5. Арнольд В.И. Геометрические методы в теории обыкновенных дифференциальных уравнений. - Ижевск: Иж. респ. типогр., 2000. - 400 с.

6. Брус Дж., Джиблин П. Кривые и особенности: Геометрическое введение в теорию особенностей: Пер. с англ. - М.: Мир, 1988. - 262 е., ил.

7. Васильев Ф.П. Методы оптимизации. - Москва: Изд-во «Факториал Пресс», 2002. - 824 с.

8. Васильева Е.М., Левит Б.Ю., Лившиц В.Н. Нелинейные транспортные задачи на сетях. - М: Финансы и статистика, 1981. - 105 с.

9. Войтов О.Н., Зоркальцев В.И., Филатов А.Ю. Определение допустимых режимов электроэнергетических систем алгоритмами внутренних точек. // "Сибирский журнал индустриальной математики", том 3, №1(5), 2000. - С.57-65.

10. Гейл Д. Теория линейных экономических моделей. - М: Изд-во иностранной литературы, 1963. - 419 с.

11. Глаголев К.В., Морозов А.Н. Физическая термодинамика - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 269 с.

12. Голиков А. И., Евтушенко Ю. Г. Применение теорем об альтернативах к нахождению нормальных решений линейных систем", Известия высших учебных заведений. Математика, 2001, № 12. - С. 21-31.

13. Гольштейн Е. Г. Выпуклое программирование (элементы теории).-

М: Наука. Главная редакция физико-математической литературы. - 1970. -68 с. - (Серия «Экономико-математическая библиотека»)

14. Гольштейн Е. Г., Третьяков Н. В. Модифицированные функции лангража: Теория и методы оптимизации. - М.: Наука. Гл. ред. физ.-мат. лит., 1989. - 400 с. - (Серия «Экономико-математическая библиотека»)

15. Данциг Дж. Линейное программирование, его применения и обобщения.-М.: Прогресс, 1966.

16. Деннис Дж. Б. Математическое программирование и электрические цепи. - М.: Изд-во иностранной литературы, 1961, - 216 с.

17. Дикин И.И. Итеративное решение задач линейного программирования. // Доклады АН СССР, т. 174, 1967.

18. Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования: алгоритмы метода внутренних точек. -Новосибирск: Наука. Сиб. отд-ние, 1980. - 144 с.

19. Дикин И.И. Применение метода внутренних точек при решении прикладных оптимизационных задач // Методы оптимизации и их приложения. - Иркутск: СЭИ СО РАН, 1988. - С. 14-17.

20. Дикин И.И., Попова О.М., Епифанов С.П. Применение методов вспомогательных функций и внутренних точек при расчетах потокорас-пределения в гидравлических системах. - Иркутск, 1999. - 25 с. (Препринт ИСЭМ СО РАН; - № 10).

21. Дубровин Б.А., Новиков С.П., Фоменко А.Т. Современная геометрия: Методы и приложения. - Том I. Геометрия поверхностей, групп преобразований и полей. Изд. 4-е, исправл. и дополн. - М.: Эдиториал УРСС, 1998. - 336 с.

22. Евдокимов А.Г., Тевяшев А.Д., Дубровский В.В. Моделирование и оптимизация потокораспределения в инженерных сетях. - М.: Стройиздат, 1990.-368 с.

23. Евтушенко Ю.Г., Жадан В.Г. Релаксационный метод решения задач нелинейного программирования // Журнал вычисл. математики и матем.

физики. 1977. - Том. 17. №4. - С. 890-904.

24. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. - М.: Наука, 1982.

25. Еделев А. В. Разработка специализированной инструментальной среды для исследования проблем живучести больших трубопроводных систем: Дисс... канд. техн. наук: 05.13.18. - Иркутск, 2001. - 107с.

26. Еделев A.B., Пяткова Н.И., Рабчук В.И., Чельцов М.Б., Сендеров С.М. Методические основы выбора направлений корректировки решений по развитию энергетики государства с позиций энергетической безопасности. - Известия РАН. Энергетика, 2006, № 3, - С. 21-27."

27. Еделев A.B., Еникеева С.М., Сендеров С.М. Информационное обеспечение при исследовании больших трубопроводных систем // Вычислительные технологии, 1999, т. 4, № 5, с. 30-35.

28. Епифанов С.П., Зоркальцев В.И. Симметричная двойственность и гидравлические цепи // Моделирование технических и природных систем: Труды XIII Байкальской междунар. школы-семинара «Методы оптимизации и их приложения», Том 5: Иркутск, ИСЭМ СО РАН.- 2005. - С. 119-123.

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

30. Епифанов С.П., Зоркальцев В.И., Медвежонков Д.С. Симметричная двойственность в оптимизации и модели потокораспределения // III Всероссийская конференция «Проблемы оптимизации и экономические приложения»: Материалы конференции (Омск, 11-15 июля 2006) / Омский филиал Института математики им. С. JI. Соболева СО РАН. - Омск: Изд-во ОмГТУ, 2006.-С. 26-27.

31. Епифанов С.П., Зоркальцев В.И. Приложение теории двойственности к моделям потокораспределения // Вычислительные технологии. -2009.-Т. 14, № 1. - С. 67-80.

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

33. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. - Москва: Наука, 1976. - 192с.

34. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования //Докл. АН СССР. 1981. Т. 256, № 2. С. 272-276.

35. Еремин И.И., Вл.Д.Мазуров, Н.Н.Астафьев, Несобственные задачи линейного и выпуклого программирования. - М.: Наука, 1983,336 с.

36. Еремин И.И. Симметричная двойственность для задач последовательного линейного программирования // Докл. АН СССР. 1991. Т. 317, № 5. С. 1045-1048.

37. Еремин И.И. Двойственность для парето-последовательных задач линейного программирования // Тр. Ин-та математики и механики УрО РАН. 1995. ТЗ. С. 245-260.

38. Еремин И.И. Двойственность для несобственных задач паретовской и лексикографической линейной оптимизации // Тр. Ин-та математики и механики УрО РАН. 1996. Т. 4. С. 322-336.

39. Еремин И.И., Теория двойственности в линейной оптимизации. -Челябинск: Изд-во ЮУрГУ, 2005, 195 с.

40. Еремин И.И. Системы линейных неравенств и линейная оптимизация. - Екатеринбург: Изд-во УрО РАН, 2007, 338 с.

41. Жадан В.Г. Метод Ньютона с наискорейшим спуском для задач линейного программирования. - М.: ВЦ РАН, 1997.

42. Зангвилл У. Нелинейное программирование. Единый подход. 1969г. Пер. с англ., под ред. Е. Г. Голыптейна. - М.: «Сов. радио», 1973. - 312 с.

43. Зоркальцев В.И. Итеративный алгоритм решения задачи линейного программирования. // Алгоритмы и программы решения задач линейной

алгебры и математического программирования. - Иркутск, СЭИ СО АН СССР, 1978, - С.77-89.

44. Зоркальцев В.И. Метод относительно внутренних точек. Сыктывкар: Коми фил. АН СССР РАН, 1986.

45. Зоркальцев В.И. Методы прогнозирования и анализа эффективности функционирования системы топливоснабжения. -М.: Наука, 1988.

46. Зоркальцев В. И. Модели рыночной экономики: Учеб. пособие. -Иркутск: Иркут. ун-т, 1993. - 144 с.

47. Зоркальцев В.И. Проективные алгоритмы оптимизации, использующие множители предыдущей итерации. // Журнал вычисл. Математики и матем физики. - 1994. - Т. 34, №7. - С. 943-950.

48. Зоркальцев В.И. Алгоритмы внутренних точек в линейном програм-мированиии // Оптимизация, управление, интеллект. 1995. №1.-С. 20-37.

49. Зоркальцев В.И., Ковалев Г.Ф., Лебедева Л.М. Модели оценки дефицита мощности электроэнергетических систем. / Препринт. - Иркутск: ИСЭМ СО РАН, 2000. - с. 17-22.

50. Зоркальцев В. И. Симметричная двойственность. Приложения к моделям электрических и гидравлических цепей. - Иркутск: ИСЭМ СО РАН, 2004. - 40 с. - Препринт №6.

51. Зоркальцев В.И. Симметричная двойственность в оптимизации при сепарабельных целевых функциях // «Оптимизация, управление, интеллект», №9, 2005, с. 72-83.

52. Зоркальцев В.И. Симметричная двойственность в оптимизации и ее приложения. // Известия высших учебных заведений. Математика, 2006, №2, с. 53-59.

53. Зоркальцев В. И., Хамисов О. В. Равновесные модели в экономике и энергетике. - Новосибирск: Наука, 2006. - 221 с.

54. Зоркальцев В.И., Медвежонков Д.С. Нелинейная транспортная модель. // Российская конференция «Дискретная оптимизация и исследо-

вание операций»: Материалы конференции (Владивосток, 7-14 сентября 2007). - Новосибирск: Изд-во Института математики, 2007. - С. 161.

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

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

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

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

59. Зоркальцев В.И. Двойственные алгоритмы внутренних точек // Известия высших учебных заведений. Математика, 2011. - С. 1-27.

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

61. Зоркальцев В.И., Медвежонков Д.С. Симметричная двойственность в задачах выпуклой оптимизации и модели потокораспределения // Информационный бюллетень Ассоциации математического программирования №12. (Тезисы докладов 14-ой Всероссийской конференции «Математическое программирование и приложения») Научное издание. Екатеринбург: УрО РАН, 2011. - С. 43-44.

62. Зоркальцев В.И., Медвежонков Д.С. Экспериментальные исследования алгоритмов внутренних точек на задачах потокораспределения // Научный журнал «Вестник университета «Туран». - Казахстан, Алматы: Университет Туран. - 2011. - № 4 (52) - С. 127-133.

63. Зоркальцев В.И. , Медвежонков Д.С. , Пержабинский С.М. Проекции точки на политоп. // Тезисы Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С.Н.Черникова, Екатеринбург, 14-19 мая 2012 г. - Екатеринбург: изд-во «УМЦ-УПИ», 2012. -С. 77-78.

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

65. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. - М: Наука. Главная редакция физико-математической литературы. - 1967. - 460 с. - (Серия «Экономико-математическая библиотека»)

66. Илькевич Н.И. Сооружение и эксплуатация газонефтепроводов и газонефтехранилищ. - Иркутск: Изд-во ИрГТУ, 2007. - 95 с.

67. Иоффе А. Д., Тихомиров В. М. Двойственность выпуклых функций и экстремальные задачи. // Успехи математических наук, Т. 23, вып. 6 (144), 1968.-С. 51-116.

68. Канторович Л.В. Математические методы организации и планиро-

вания производства. - Л.: Изд-во ЛГУ, 1949. - 68 с.

69. Канторович Л. В., Гавурин М. К. Применение математических методов в вопросах анализа грузопотоков // Проблемы повышения эффективности работы транспорта. - М.; Л.: Издательство АН СССР, 1949, с. 110-138.

70. Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. - М.: Изд-во АН СССР, (1959) 1960. - 347 с.

71. Канторович Л. В., Горстко А. Б. Оптимальные решения в экономике. - М.: Наука, 1972. - 232 с.

72. Киреев А.П. Международная экономика: Учебное пособие: В 2 ч. Ч. 1: Международная микроэкономика: движение товаров и факторов производства. - 2001. - 416 с.

73. Коваленко А.Г. О математическом моделировании рассредоточенного рынка // Экономика и математические методы.-1999.-Т. 35.-№ 3.-С.108-115.

74. Курант Р. Уравнения с частными производными.-М.: Мир, 1964. -830с.

75. Лившиц В.Н. Михайлова В.П., Хранович И.Л. О возможности решения транспортной задачи выпуклого программирования с помощью электрического моделирования // «Вопросы радиоэлектрон.». - Сер.7 - 1965.

76. Лившиц В.Н., Левит Б.Ю. Оценка эффективности некоторых алгоритмов оптимального распределения потоков на сети // Труды симпозиума «Вопросы точности и эффективности вычислительных алгоритмов». - Киев. - 1969. - №4.

77. Лившиц В.Н. Определение эффективности капитальных вложений на транспорте // Сб. трудов ВНИИСИ. - М., 1982, вып.8.

78. Лившиц В.Н., Браславский А.Л., Позамантир Э.И. Реформирование железнодорожного транспорта. Либерально-рыночный или социально-рыночный вариант? //«Бюллетень транспортной информации». №5. 2001.

79. Лобачев В. Г. Вопросы рационализации расчетов водопроводных

сетей. - М.: ОНТИ, 1936. - 148 с.

80. Магарил-Ильяев Г. Г., Тихомиров В. М. Выпуклый анализ и его приложения. (2-е изд.) - М.: Едиториал УРСС, 2003. - 179 с.

81. Медвежонков Д.С., Зоркальцев В.И. Теория и методы расчета моделей потокораспределения // Вестник Иркутского университета. Спец. вып.: Материалы ежегодн. научн.-теор. конф. мол. уч. - Иркутск: Иркут. ун-т, 2005.-С. 105-107.

82. Медвежонков Д.С. Преобразование Лежандра и его применение // Системные исследования в энергетике. - Иркутск: ИСЭМ СО РАН, 2006. -(Труды молодых ученых ИСЭМ СО РАН, Вып. 36) - С. 235-241.

83. Медвежонков Д.С. Анализ эффективности некоторых экстремальных алгоритмов расчета гидравлических цепей // Системные исследования в энергетике. - Иркутск: ИСЭМ СО РАН, 2006. - (Труды молодых ученых ИСЭМ СО РАН, Вып. 36) - С. 47-53.

84. Медвежонков Д.С. Преобразование Лежандра и его применение // Вестник Иркутского университета. Спец. вып.: Материалы ежегодн. на-учн.-теор. конф. мол. уч. - Иркутск: Иркут. ун-т, 2006. - С. 116-117.

85. Медвежонков Д.С. Нелинейная двойственная модель транспортной задачи. // Математика и проблемы ее преподавания в вузе: Труды III межвузовской зональной конференции, посвященной памяти профессора Б.А.Бельтюкова - Иркутск: Изд-во Иркут. гос. пед. ун-та, 2007. С. 102-104.

86. Медвежонков Д.С. Нелинейная модель транспортной задачи. // Информационный бюллетень Ассоциации математического программирования №11. (Тезисы докладов 13-ой Всероссийской конференции «Математическое программирование и приложения») Научное издание. Екатеринбург: УрО РАН, 2007.-С. 130-131.

87. Медвежонков Д.С. Нелинейная транспортная задача с переменным спросом и предложением // Системные исследования в энергетике. - Иркутск: ИСЭМ СО РАН, 2007. - (Труды молодых ученых ИСЭМ СО РАН,

Вып. 37)-С. 101-107.

88. Медвежонков Д.С., Зоркальцев В.И. Нелинейная транспортная модель. // Тезисы докладов IX Школы-семинара молодых ученых "Математическое моделирование и информационные технологии: Управление, искусственный интеллект, прикладное программное обеспечение и технологии программирования", ММИТ'07. Иркутск, ИДСТУ СО РАН, 2007.-С. 111-114.

89. Медвежонков Д.С. Нелинейная транспортная модель с ограничением пропускной способности ветвей // Системные исследования в энергетике. - Иркутск: ИСЭМ СО РАН, 2008. - (Труды молодых ученых ИСЭМ СО РАН, Вып. 38)-С. 81-88.

90. Медвежонков Д.С. Нелинейная транспортная модель с двусторонними ограничениями на объемы перевозок // Теория и методы согласования решений: сб. науч. тр. - Новосибирск: Наука, 2009 - С. 146-159.

91. Медвежонков Д.С. Транспортная модель с кусочно-заданными издержками и недостатком или избытком возможностей генерации. // IV Всероссийская конференция «Проблемы оптимизации и экономические приложения»: Материалы конференции (Омск, 29 июня - 4 июля 2009) / Омский филиал Института математики им. С. Л. Соболева СО РАН. -Омск: Полиграфический центр КАН, 2009. - С. 235.

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

93. Медвежонков Д.С. Транспортная модель с минимизацией кусочно-заданных нелинейных издержек при суммарно допустимом объеме снабжения, не равном суммарной потребности // Системные исследования в энергетике. - Иркутск: ИСЭМ СО РАН, 2009. - (Труды молодых ученых ИСЭМ СО РАН, Вып. 39) - С. 179-187.

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

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

96. Медвежонков Д.С. Исследование прямого и двойственного алгоритма внутренних точек на классе задач потокораспределения // Системные исследования в энергетике. - Иркутск: ИСЭМ СО РАН, 2011. - (Тезисы статей) - С. 19.

97. Медвежонков Д.С. Сравнение сходимости прямого и двойственного алгоритма внутренних точек на классе задач потокораспределения // Тезисы Российско-Монгольской конференции молодых ученых по математическому моделированию, вычислительно-информационным технологиям и управлению. - Иркутск: РИО ИДСТУ СО РАН, 2011. - С. 54.

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

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

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

101. Меренков А.П., Хасилев В.Я. Теория гидравлических цепей - М.: Наука, 1985.-278 с.

102. Меренков А. П., Сеннова Е. В., Сумароков С. В. и др. Математическое моделирование и оптимизация систем тепло-, водо-, нефте- и газоснабжения. - Новосибирск: Наука, 1992. - 407 с.

103. Методы и модели исследования живучести систем энергетики/Антонов Г.Н., Черкесов Г.Н., Криворуцкий Л.Д. и др. - Новосибирск: Наука. Сиб. отд-ние, 1990. - 285 с.

104. Надежность систем энергетики и их обрудования / Под общей редакцией Ю.Н. Руденко: В 4-х т. Т. 1: Справочник по общим моделям анализа и синтеза надежности систем энергетики / Под ред. Ю.Н. Руденко. -М.:Энергоатомиздат, 1994. - 480 е.: ил.

105. Надежность систем энергетики: достижения, проблемы, перспективы / Г.Ф. Ковалев, Е.В. Сеннова, М.Б. Чельцов и др. / Под ред. Н.И. Во-ропая. - Новосибирск: Наука. Сибирское предприятие РАН, 1999. - 434 с.

106. Надежность топливо- и энергоснабжения и живучесть систем энергетики регионов России / Л.Л. Богатырев, A.B. Бочегов, Н.И. Воропай [и др.]; ред. Н.И. Воропай, А.И. Татаркин; рец. Х.Н. Гизатуллин, Ю.Я. Чукре-ев. - Екатеринбург: Изд-во Урал, ун-та, 2003. - 391 с.

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

108. Попов Л.Д. Введение в теорию, методы и экономические приложения задач о дополнительности: Учеб. пособ. Екатеринбург: Изд-во Урал, ун-та, 2001. 124 с.

109. Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи. - М:

Наука. Главная редакция физико-математической литературы. - 1980.

110. Пяткова Н.И, Сендеров С.М. Использование двухуровневой технологии исследований при решении проблем энергетической безопасности // Методические вопросы исследования надежности больших систем энергетики. Вып. 59. - Иркутск: ИСЭМ СО РАН, 2009. - С. 274-283.

111. Рокафеллар Р. Выпуклый анализ. - М.: Мир, 1973. - 470 с.

112. Рубинштейн Г. Ш. Двойственность в математическом программировании и некоторые вопросы выпуклого анализа. // Успехи математических наук, Т. 25, вып. 5 (155), 1970. - С. 171-201.

113. Сендеров С.М., Еделев A.B. Технология поиска "узких" мест в работе ЕСГ и выбор путей преодоления ЧС с газоснабжением потребителей. // Методические вопросы исследования надежности больших систем энергетики. Вып. 59. / Отв. ред. Н.И. Воропай. - Иркутск: ИСЭМ СО РАН, 2009. - С. 249-254.

114. Сеннова Е.В., Сидлер В.Г. Математическое моделирование и оптимизация развивающихся теплоснабжающих систем. - Новосибирск: Наука, 1987.-221 с.

115. Стрекаловский A.C. Элементы невыпуклой оптимизации. - Новосибирск: Наука, 2003. - 356 с.

116. Системы линейных неравенств: учебное пособие / В. И. Зоркальцев, М. А. Киселева - Иркутск: Изд-во Иркутского гос. ун-та, 2007. - 128с.

117. Толстой А. Н. Методы нахождения наименьшего суммарного километража при планировании перевозок в пространстве // Планирование перевозок, Сборник первый - М: Транспечать НКПС, 1930. - С. 23-55.

118. Толстой А. Н. Методы устранения нерациональных перевозок при планировании. // Социалистический транспорт, № 9, 1939. - С. 28-51.

119. Толстой А. Н. Методы устранения нерациональных перевозок при составлении оперативных планов. - М.: Трансжелдориздат, 1941.

120. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. - М.: Мир, 1972. — 240с.

121. Филатов А.Ю. Развитие алгоритмов внутренних точек и их приложений к системам неравенств: Дис. ... канд. физ.-мат. наук. - Иркутск, 2001.-123 с.

122. Форд JI. Р., Фалкерсон Д. Р. Потоки в сетях. - М: Мир, 1966. -276 с.

123. Хасилев В.Я., Меренков А.П., Каганович Б.М. и др. Методы и алгоритмы расчета тепловых сетей. - М.: Энергия, 1978. - 176 с.

124. Ху Т. Целочисленное программирование и потоки в сетях. Пер. с англ. - М.: Мир, 1974. - 520 с.

125. Черников С.Н. Линейные неравенства. - М.: Наука, 1968. - 488 с.

126. Шамрай Н. Б. Применение вариационно-подобных неравенств для решения задач транспортного ценового равновесия // «Информатика и системы управления». - 2006. - №1(11). - С.62-72

127. Экланд И., Темам Р. Выпуклый анализ и вариационные проблемы. Пер с англ. Тихомиров В. М. - М.: Мир, 1979. - 400 с.

128. Эльстер К.-Х. и др. Введение в нелинейное программирование / Эльстер К.-Х., Рейнгардт Р., Шойбле М., Донат Г. / Пер. с нем. под ред. И.И. Еремина. - М.: Наука. Главн. ред. физ.-мат. литературы, 1985г. - 264с.

129. Ahuja R.K., Magnati T.L., Orlin J.B. Network Flows: Theory, Algorithms and Applications. - Prentice Hall, New Jersey, 1993.

130. P. R. Amestoy, T. A. Davis, and I. S. Duff. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Applic., 17(4):886-905, 1996.

131. P. R. Amestoy, T. A. Davis, and I. S. Duff. Algorithm 837: An approximate minimum degree ordering algorithm. ACM Trans. Math. Softw., 30(3): 381-388,2004.

132. AWWA (American Water Works Association). Computer Modeling Of Water Distribution Systems. (Manual of water supply practices - M32, 2nd ed.) - American Water Works Association, Denver, Colorado, USA, 2005. - 159 p.

133. Barnes E. A variation on Karmarkar's algorithm for solving linear programming problems // Mathematical programming, 1986, №36, pp. 174-182.

134. Bazaraa M. S. and Goode J. J., "On symmetric duality in nonlinear programming," Operations Research, vol. 21, pp. 1-9, 1973.

135. Bazaraa, M.S. and Jarvis, J.J.: Linear Programming and Network Flows, Wiley, New York, 1977. - 574 s.

136. Bazaraa, M. S., Sherali H. D., Shetty C. M.: Nonlinear Programming: Theory and Algorithms, 3rd ed. - Wiley-Interscience, Hoboken, New Jersey, 2006. - 853 p.

137. Beraldi P., Guerriero F., Musmanno R. Parallel Algorithms for Solving the Convex Minimum Cost Flow Problem // Computational Optimization and Applications. - Kluwer Academic Publishers, 2001, №18. - pp. 175-190.

138. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey, 1989.

139. Bertsekas D. P. Nonlinear Programming. - Athena Scientific, Belmont, Massachusetts, 1995. - 800 p.

140. Bertsekas D. P., Polymenakos L. C., Tseng P. e-relaxation and auction methods for separable convex cost network flow problems // Network Optimization, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, N.Y., 1998, pp. 103-126.

141. Bertsekas D.P., Network Optimization: Continuous and Discrete Models, Athena Scientific, Belmont, Massachusetts, 1998. - 608 p.

142. Bertsekas D. P., Nedic A., Ozdaglar A. E., Convex Analysis and Optimization. - Athena Scientific, Belmont, Massachusetts, 2003. - 560 p.

143. Birkhoff G., Diaz J.B. Nonlinear network problems // Quarterly of applied mathematics. - 1956. Vol. 13, N4. - P. 431—443.

144. Borwein J.M., Lewis A.S. Convex analysis and nonlinear optimization. - SpringerVerlag, New York, 2000.

145. Boyd S., Vandenberghe L., Convex optimization. - Cambridge University Press, 2004.

146. Broyden C.G. A simple algebraic proof of Farkas's lemma and related

theorems // Optimization methods and software. - 2000. - Vol. 8. - P. 185-199.

147. Broyden C.G. On theorems of the alternative // Optimization methods and software.-2001.-Vol. 16.-P. 101-111.

148. Cross H., Analysis of flow in networks of conduits or conductors // Urbana Illinois: Eng. Exp. Station of Univ. of Illinois. - 1936. - November. -Bull. N 286. - 29 p.

149. Dafermos S. Traffic Equilibrium and Variational Inequalities // «Transportation Science». - 1980. - V.14. - P.42-54.

150. Dantzig G. B., Eisenberg E., and Cottle R.W., "Symmetric dual nonlinear programs," Pacific Journal of Mathematics, vol. 15, pp. 809-812,1965.

151. Devi G., Symmetric duality for nonlinear programming problem involving r|-bonvex functions, European J. Oper. Res. 104 (1998) 615-621.

152. Dorn W.S., A symmetric dual theorem for quadratic programming, Journal of the Operations Research Society of Japan 2 (1960) 93-97.

153. Fenchel W. Convex Cones, Sets and Functions. - Princeton University Press, Princeton, New Jersey. - 1951.

154. Fletcher R. Practical methods of optimization. 2nd ed. Wiley-Interscience, New York, 2000. - 450 p.

155. Ford L.R., Fulkerson D.R., Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962.

156. George, A. , Liu, J. W. H. The evolution of the minimum degree ordering algorithm. SIAM Review, 31(1): 1-19, 1989.

157. Gill, P. E., Murray W., and Wright M. H.: Practical Optimization, Academic Press, London, 1981.

158. Goh C.-J.,Yang X.Q. Duality in optimization and Variational inequalities. - Taylor & Francis, 2002.-313 p.-(Optimization theory and applications, vol. 2)

159. Gueye O. M., Dussault J.-P., Mahey P. Separable Augmented Lagran-gian Algorithm with Multidimensional Scaling for Monotropic Programming // Journal of optimization theory and applications. - Springer Science, 2005, Vol.

127, No. 2.-pp. 329-345.

160. Harris T.E., Ross F.S., Fundamentals of a Method for Evaluating Rail Net Capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, California, 1955.

161. Haurie A., Marcotte P. On the relationship between Nash-Cournot and Wardrop equilibria // Networks 15. - 1985. - P.295-308.

162. Hitchcock F.L., The distribution of a product from several sources to numerous localities // J. of Mathematics and Physics, vol. 20, 1941. - pp. 224-230.

163. Ibaraki S., Fukushima M., Ibaraki T. Primal-Dual Proximal Point Algorithm for Linearly Constrained Convex Programming Problems // Computational Optimization and Applications. - Kluwer Academic Publishers, 1992, №1. -pp. 207-226.

164. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica, 1984, №4, pp.373-395.

165. Koopmans Tj.C., Optimum utilization of the transportation system, in: The Econometric Society Meeting (Washington, D.C., 1947; D.H. Leavens, ed.) [Proc. of the International Statistical Conf. - Volume V], 1948, pp. 136-146.

166. Koopmans Tj.C., Reiter S., A model of transportation, in: Activity Analysis of Production and Allocation - Proceedings of a Conference (Tj.C. Koopmans, ed.), Wiley, New York, 1951, pp. 222-259.

167. Kuhn H. W. and Tucker A. W. "Nonlinear Programming", Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability (J. Neyman, ed.), Berkeley, University of California Press, 1951, pp. 481-492.

168. Mays L. W., Water distribution systems handbook. - McGraw-Hill, 2000. 912 p.

169. Mond B., "A symmetric dual theorem for non-linear programs", Quarterly ofApplied Mathematics, vol. 23, pp. 265-269, 1965.

170. Mond B., Weir T., Generalized concavity and duality, in: S. Schaible, W.T. Ziemba (Eds.), Generalized Concavity in Optimization and Economics,

Academic Press, New York, 1981.

171. Nagurney A., Siokos S., Financial Networks: statics and dynamics, Springer-Verlag, 1997.

172. Nagurney A. Network Economics: a Variational Inequality Approach. -Dordrecht: «Kluwer Academic Publishers». - 1999.

173. Nagurney A. (Ed.), "Innovations in Financial and Economic Networks", New Dimensions in Networks, 2003. - 352 p.

174. Nesterov, Y., and A. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming // Studies in Applied Mathematics, Vol. 13. - Society for Industrial and Applied Mathematics, 1994.

175. Ouorou A. A Primal-Dual Algorithm for Monotropic Programming and its Application to Network Optimization// Computational Optimization and Applications. - Kluwer Academic Publishers, 2000, №15. - pp. 125-143.

176. Rockarellar R.T. Conjugate Duality and Optimization. - SIAM, Philadelphia, 1974.-80 p.

177. Rockafellar R. Tyrrell: Network flows and monotropic optimization. -Pure and Applied Mathematics. - New York: Wiley-Interscience, 1984. - 616 p.

178. Rockafellar R.T., Wets R. J.-B. Variational analysis. - Springer-Verlag, Berlin, Heidelberg, 1998. - 733 p.

179. Singer I. Duality for nonconvex approximation and optimization. -Springer, 2006. - 375 p.

180. Sinha S.M. Mathematical programming. - Elsevier, 2006. - 570 p.

181. Smith M. The existence, uniqueness, and stability of traffic equilibria // «Transport. Research». - 1979 - P.259-304.

182. Vanderbei R., Meketon M., Freedman B. A modification of Karmarkar's linear programming algorithm // Algorithmica, 1986, №1, pp. 395-407.

183. Ventura J. A. Computational development of a lagrangian dual approach for quadratic networks // Networks. - Wiley Periodicals, 2006, Volume 21, Issue 4, Pages 469 - 485.

184. Walk M. Theory of Duality in Mathematical Programming. - SpringerVerlag, 1989.- 178 p.

185. Walski T. M., Haestad Methods, Inc.: Advanced Water Distribution Modeling and Management. - Haestead Press, 2003

186. Wardrop J. Some theoretical aspects of road traffic research // Proc. Inst. Civil Engineers II. - 1952. - P.325-378.

187. Zenios S.A., Mulvey J.M. Relaxation techniques for strictly convex network problems // Annals of Operations Research. - Scientific Publishing Company, 1985, №5. - pp. 517-538.

188. Wolfe, P., A Duality Theorem for Nonlinear Programming, Quarterly of Applied Mathematics, Vol. 19, pp. 239-244, 1961.