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

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

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

Pages:   || 2 |

Разработка методов и алгоритмов в задачах оптимального использования и развития сетей

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

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

Думбадзе Ламара Георгиевна

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ

В ЗАДАЧАХ ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ

И РАЗВИТИЯ СЕТЕЙ

Специальность 01.01.09 – дискретная математика и

математическая кибернетика

Автореферат

диссертации на соискание ученой степени

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

Москва 2007

Работа выполнена в Вычислительном центре им. А.А. Дородницына Российской академии наук

Научный руководитель: доктор физико-математических наук

В.И. Цурков

Официальные оппоненты: доктор физико-математических наук

А.П. Абрамов,

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

Д.Т. Лотарев

Ведущая организация: ИПУ РАН

Защита диссертации состоится “___” ноября 2007 г. в __ час. __ мин. на заседании диссертационного совета Д002.017.02 Вычислительного центра им. А.А. Дородницына Российской академии наук по адресу: 119333 Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан “___”______________2007 г.

Ученый секретарь диссертационного совета Д002.017.02,

доктор физико-математических наук В.В. Рязанов

В.В.Рязанов

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

Актуальность темы. Линейные частично-целочисленные оптимизационные задачи требуют для своего решения значительного объема вычислений. Как хорошо известно, сочетание симплекс-метод – метод ветвей и границ может оказаться непригодным уже при количестве ограничений/переменных порядка сотни.

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

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

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

Цель работы.

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

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

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

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

Методы исследования. Исследования проводились с использованием методов Данцига-Вулфа, разделения Бендерса, потоковых методов, методов анализа структуры графа, дискретной оптимизации.





Научная новизна. Разработан оригинальный метод анализа разветвленности сети.

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на VII научно-технической конференции молодых ученых и специалистов Министерства связи СССР (Москва, 1987); на Всесоюзном совещании “Автоматизация управления первичными сетями” (Москва, 1988); на НТС ЦНИИ связи и его секциях (Москва, 1989); на 2-й Московской конференции “Декомпозиционные методы в математическом моделировании и информатике” (Москва, 2004).

Публикации. По теме диссертации опубликовано 7 печатных работ.

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

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

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

В первой главе излагается разработанный метод анализа разветвленности сети.

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

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

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



Выводы.

В главе 1 предложены алгоритмы анализа связности графа, являющиеся в некоторых приложениях существенно эффективнее существующих потоковых.

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

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

(1)

(2)

(3)

где - часть заявки для -й корреспондирующей пары по пути

- количество рёбер в сети . Не всегда можно сразу сказать, существует ли в заданной сети требуемый поток. Однако ясно, что при достаточно малом поток, удовлетворяющий ограничениям (1), (3) и

(4)

существует всегда, таким образом, возникает задача

при (1), (3), (4) (5)

После необходимых преобразований задача 1 может быть решена методом Данцига-Вулфа.

С помощью значений двойственных переменных в оптимальном решении задачи 1 выделяется подмножество коррепондирующих пар (корреспондирующие пары задачи 2), и ставится задача 2: сохраняя оптимальность решения задачи 1, максимизировать удовлетворение для всех корреспондирующих пар задачи 2. Не умаляя общности, можем считать, что номера корреспондирующих пар задачи 2 начинаются с и идут подряд до .

Формально задача 2 может быть записана

(6)

(7)

(8)

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

Константа определяется из условия

,

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

Аналогичным образом формулируется и решается задача 3 и т.д. Количество задач в возникающей иерархии зависит от исходных данных и в конкретной серии доходило до 8.

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

Другим подходом использования большого количества нулевых длин является построение поля кратчайших путей. Рангом вершины называется минимальное количество линий в возможных путях ее соединения с начальной вершиной. Поле кратчайших путей определяется как ориентированный граф, в котором дуги ориентируются от любой вершины к вершинам следующего ранга. Поля (по одному для каждой начальной вершины) строятся в начале решения задачи (при нулевых длинах). Пути соединения каждой вершины с начальной находятся последовательным переходом в произвольную вершину меньшего ранга. Подполем, зависящим от некоторой дуги называется множество дуг поля, на которые можно пройти вдоль ориентации дуг лишь через дугу . После совершения очередной итерации наступают изменения двойственных оценок при слабых переменных. Корректировка поля состоит из двух операций – освобождение подполей, если соответствующие двойственные оценки изменились и стали равными нулю, и закрытие подполей, если соответствующие двойственные оценки, изменившись, стали не равными нулю. Пути строятся по свободной части поля. Использование полей при решении задачи оптимального использования сети уменьшило объем вычислений на 10-15%. Поля нашли применение также и при нахождении троек независимых путей.

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

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

Дополнительно обозначим: Qk - верхняя граница потребности -ой корреспондирующей пары, qk - нижняя граница потребностей -ой корреспондирующей пары, gk - тариф для предоставления одного канала -ой корреспондирующей пары, hi - переменная часть себестоимости эксплуатации сети - себестоимость предоставления канала в - м элементе сети (линии или узле).

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

(9)

(10)

(11)

Целевая функция:

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

,

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

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

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

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

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

(12)

(13)

(14)

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

Рассмотрим особенности применения процедуры разделения Бендерса для решения задачи (12) - (14). При фиксированных вы­пишем задачу, двойственную к (12) - (14):

(15)

(16)

(17)



Pages:   || 2 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

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