РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ

Иркутский государственный университет

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

ФИЛАТОВ Александр Юрьевич

РАЗВИТИЕ АЛГОРИТМОВ ВНУТРЕННИХ ТОЧЕК

И ИХ ПРИЛОЖЕНИЕ К СИСТЕМАМ НЕРАВЕНСТВ

05.13.18 - математическое моделирование,

численные методы и комплексы программ

ДИССЕРТАЦИЯ

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

д.т.н., проф. В.И.Зоркальцев Иркутск - 2001 Содержание Введение

Глава 1. Краткий обзор алгоритмов внутренних точек в линейном программировании

1.1. Теоретические основы линейной оптимизации

1.2. Аффинно-масштабирующие алгоритмы

1.3. Полиномиальные алгоритмы

Глава 2. Алгоритмы оптимизации в конусе скошенного пути для решения пары взаимно-двойственных задач линейного программирования................. 2.1. Несколько вспомогательных утверждений

2.2. Описание и теоретическое исследование алгоритмов оптимизации в конусе скошенного пути

2.3. Экспериментальное исследование алгоритмов

Глава 3. Решение систем уравнений и неравенств алгоритмами внутренних точек

3.1. Задача определения допустимых режимов электроэнергетических систем

3.2. Аффинно-масштабирующие алгоритмы применительно к решению линеаризованной подзадачи

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

Заключение

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

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

Важно отметить российский приоритет в теории оптимизации в целом и в теории линейной оптимизации в частности. Зарождение линейного программирования связано с именем Л.В.Канторовича, а фундаментальные работы по линейным неравенствам были выполнены С.Н.Черниковым. Среди других лидеров теории оптимизации в России отметим Н.Н.Моисеева и Б.Т.

Поляка (Москва), И.И.Еремина (Екатеринбург), В.А.Булавского и В.Т.Дементьева (Новосибирск), О.В.Васильева и В.П.Булатова (Иркутск). Крупный вклад в развитие методов оптимизации был внесен представителями украинской и белорусской школ Б.Н.Пшеничным, Н.З.Шором, Р.Габасовым, Ф.М.Кирилловой и другими. Среди зарубежных исследователей, заложивших фундамент современной теории оптимизации, следует выделить Дж.фон Неймана, Дж.Данцига, Г.Куна и А.Таккера.

Существует большое количество методов решения задач линейного программирования. Одним из активно развивающихся их направлений являются алгоритмы внутренних точек, первый из которых был опубликован в 1967 году И.И.Дикиным. До середины 80-х годов развитие алгоритмов внутренних точек осуществлялось исключительно в работах российских ученых, среди которых выделим Ю.Г. Евтушенко, В.И.Зоркальцева и В.Г.Жадана.

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность Разработанные алгоритмы могут быть использованы при реализации многих технических, экономических, экологических и других моделей, где возникает необходимость решения задач линейного программирования и систем линейных неравенств. Сюда относится и широкий класс существенно нелинейных моделей, при реализации которых применяется итеративная линеаризация. К настоящему времени предложенные в диссертации алгоритмы нашли непосредственное практическое применение на задаче определения допустимых режимов ЭЭС и внедрены в разработанный в ИСЭМ СО РАН программно-вычислительный комплекс “СДО” управления режимами ЭЭС.

Апробация работы Исследования выполнялись в рамках грантов РФФИ №97-01- (“Разработка и теоретические исследования проективных алгоритмов оптимизации с приложением в задачах энергетики”) и №00-01-00530 (“Развитие алгоритмов внутренних точек и их применение в задачах энергетики”).

Основные результаты опубликованы в 23 научных работах, в том числе, в статьях, а также докладывались и обсуждались на конференциях научной молодежи ИСЭМ СО РАН (1997-2000), XI и XII международных Байкальских школах-семинарах “Методы оптимизации и их приложения” (Иркутск, 1998, 2001), международных конференциях “Дискретный анализ и исследование операций” (Новосибирск, 1998, 2000), международной конференции “Математическое программирование и приложения” (Екатеринбург, 1999), международной конференции “Распределенные системы: оптимизация и приложения” (Екатеринбург, 2000), на семинарах

ИСЭМ СО РАН и ИДСТУ СО РАН.