Содержание к диссертации
Введение
Глава 1 Анализ разветвленности сети 37
1.1. Эффективный метод анализа разветвленное сети 3 7
1.1.1. Общее 37
1.1.2. Постановка задач и метод их решения 39
1.1.3. Методика проверки существования трёх независимых путей между любой парой узлов сети без использования компьютера 43
1.1.4. Пример 45
1.2. Задача об улучшении разветвленности сети. 48
Глава 2 Максимизация использования сети 49
2.1. Оптимальное использование сети для многопродуктового одноприоритетного потока
2.1.1. Постановка задачи и алгоритм решения 49
2.1.2. Эффективный алгоритм генерации столбцов в задаче оптимального использования сети 57
2.2. Алгоритмы нахождения кратчайших путей в оптимизационных задачах на сетях связи 63
2.2.1. Поля кратчайших путей 64
2.2.2. Модифицированный алгоритм Дейкстры для неориентированной сети 70
2.2.3. Модифицированный алгоритм Дейкстры для поля 72
2.2.4. Результаты вычислительного эксперимента 74
2.3. Задача эффективной эксплуатации сети связи 75
2.3.1. Постановка задачи 75
2. Алгоритм решения задачи 78
3. Пример решения задачи 82
Глава 3 Оптимизационные задачи развития сети 85
Задача развития сети с минимизацией капиталовложений при обеспечении заданных объемов потоков каждого продукта 85
1. Линейная частично-целочисленная задача с большим количеством непрерывных переменных 85
Задача развития сети при ограниченных капиталовложениях 89
1. Математическая постановка задачи 89
2. Алгоритм решения задачи развития сети при ограниченных капиталовложениях 91
3. Пример решения задачи развития сети при ограниченных капиталовложениях 94 Задача развития сети с целью максимизации прибыли в условиях получения кредита. Оптимизация объема кредита. 101
1. Математическая постановка задачи 101
2. Алгоритм решения задачи развития сети с выбором оптимального кредита 103
3. Пример решения задачи развития сети с выбором оптимального кредита 104
Глава 4 Многомерная задача о ранце специальной лестничной структуры с коэффициентами равными 0 или 1 в матрице ограничений 107
Постановка и алгоритм решения задачи 108
Пример решения задачи 116
Абсолютно унимодулярные матрицы, состоящие из 0 и 1 119
4.3.1. Абсолютная унимодулярность матриц ограничений многомерной задачи о ранце специальной лестничной структуры 119
4.3.2. Абсолютная унимодулярность выпуклых матриц 119
Заключение 129
Список литературы 130
- Методика проверки существования трёх независимых путей между любой парой узлов сети без использования компьютера
- Эффективный алгоритм генерации столбцов в задаче оптимального использования сети
- Линейная частично-целочисленная задача с большим количеством непрерывных переменных
- Абсолютная унимодулярность матриц ограничений многомерной задачи о ранце специальной лестничной структуры
Введение к работе
Коммуникационные сети страны (связи, транспортные, энергетические и т.п.) являются сложными и капиталоемкими объектами. Оптимальное использование сети связи по имеющимся оценкам позволит повысить ее эффективность на 15%. Еще более важна оптимизация развития больших сетей, особенно учитывая возрастающие требования по объему, разнообразию и качеству услуг. Так, сети связи должны обеспечить передачу телефонных, телеграфных, факсимильных сообщений, данных, звукового вещания, телевизионного вещания, изображений газетных полос, кабельного телевидения, электронной почты и т.д.
Целью диссертационной работы является разработка методов и алгоритмов анализа и оптимального синтеза много продуктовых сетей. Основными задачами, решаемыми в работе, являются:
- разработка эффективного метода решения задачи анализа связности сети;
задача максимизации коэффициента удовлетворения одноприоритетного множества потребителей;
- задача максимального использования сети для одноприоритетного множества потребителей;
- задача максимизации прибыли владельца сети на существующей сети при предоставлении каналов потребителям;
- задача экономии вычислений при генерации столбцов в задачах оптимизации по последовательно применяемым критериям;
- задача развития сети до удовлетворения всех потребностей при минимуме капиталовложений;
- задача максимизации прибыли владельца сети на развиваемой сети при
предоставлении каналов потребителям в условиях ограниченных
капиталовложений на развитие сети; - максимизация прибыли владельца сети на развиваемой сети в условиях кредитования на развитие сети. Выбор оптимального объема кредита;
- разработка метода решения многомерной задачи о ранце с матрицей ограничений специальной лестничной структуры;
- доказаны некоторые теоремы об абсолютно унимодулярных матрицах, состоящих из 0 и
- предложен метод решения многомерной задачи о ранце общей лестничной структуры.
Многопродуктовые сетевые потоковые задачи возникают, когда несколько товаров используют пропускные способности ребер на сети. Это имеет место в системах связи, городских транспортных системах, железнодорожных системах, многопродуктовых распределительных системах также, как и во многих других [118].
Модели многопродуктовых сетевых потоков можно разделить на классы линейных и нелинейных моделей. Есть ряд работ, связанных с обоими классами моделей. Рассмотрим сначала линейные модели.
Сеть-это конечное множество Vузлов, 1,...,Л/, и конечное множество Е упорядоченных пар узлов em=(ij), называемых ребрами. Ребро имеет пропускную способность 1,...,М. Пусть есть К продуктов означают поток и единицу стоимости, соответственно, для продукта к на ребре ет. Продукт /симеет единственный источник sk и единственный сток tk, каждый с предложением и спросом sk,k = \...,K. Поток продукта к через ребро ограничен верхней границей ит,к = /\ К и /77 = 1,..., М.
Задача нахождения многопродуктового потока минимальной стоимости (МПМС) состоит в определении многопродуктового потока минимальной стоимости через сеть, который удовлетворяет потребности в каждом продукте при условиях: 1) ограничений предложения, 2) ограничений пропускных способностей, 3) сохранении потока при прохождении через узлы.
Методика проверки существования трёх независимых путей между любой парой узлов сети без использования компьютера
В основу положен метод сечений по узлам, т.е. такая совокупность узлов сети, удаление которых нарушает связность (под связностью сети понимается наличие хотя бы одного пути между всеми парами узлов сети), а возобновление любого, хотя бы одного узла, восстанавливает связность сети. На рис. 1, например, узлы 3, 5, 6 составляют сечение.
Два узла назовем соседними, если они соединены линией передачи. Условимся также считать, что если у узла 7V, имеется соседний узел Nc с двумя инцидентными ему рёбрами, то соседним узлом для 7V, является не Nc, а ближайший (по линиям) за узлом Nc узел не менее, чем с тремя инцидентными ему линиями. Например, для узла 1 на рис. 1 будем считать соседними узлы 3, 5, 6, но не узлы 2,4. Три независимых пути между парой несоседних узлов не существуют тогда и только тогда, когда в некотором сечении по узлам, разделяющем эту пару, содержится один или два узла (случай соседних узлов рассмотрен ранее). Для удобства поиска сечений рекомендуется изобразить сеть на одном листе. Сначала сеть анализируется на наличие сечений, состоящих из одного и двух узлов. Затем на основе найденных сечений для любой пары узлов сети решается вопрос о существовании трёх независимых путей. Для поиска сечений, состоящих из одного или двух узлов, поочерёдно рассматриваются все узлы сети. Для JV, эта процедура состоит в следующем. Каждые два узла, соседние с Nl, нужно попытаться соединить между собой (без использования N,) с образованием замкнутого контура. Если любые два узла, соседние с TV,, можно соединить подобным образом, то N, не входит ни в одно сечение из двух узлов. В простейшем, чаще всего встречающемся случае все узлы, соседние с А , легко объединяются с образованием одного замкнутого контура. Например, на рис.2 узел /V,=9. Его соседние узлы 2, 5, 6 связываются с образованием одного замкнутого контура 2, 5, 6, 4. Если для некоторой пары узлов Ncl и NC2, соседних с N]t контур не найден, то нужно взять произвольный, не содержащий узла JV, путь, их соединяющий (если такой путь не существует, то N} составляет сечение из одного узла (узел 7 на рис. 1)), и, поочерёдно исключая по одному узлу из этого пути, оценить возможность соединения Na и NC2 без этого узла и без узла iV,. Например, для JV,=2 на рис.1 при iVcl =1 и NC2 -5 необходимо рассмотреть путь 5, 6, 4, 1 . Если при исключенном из пути узле связь между NC] и NC2 существует, то присутствует и контур, содержащий Ncl и NC2. Если, при некотором изъятом из пути, соединяющем NC] и Nc2, узле N2, соединения между Ncx и NC2 не оказывается, то TV, и N2 составляют сечение из двух узлов. В рассматриваемом примере при выбрасывании из пути 5, 6, 4, 1 узла 6 связи без узла N{=2 между Na = 1 и NC2 =5 не существует. Следовательно, узлы 2 и 6 образуют сечение из двух узлов. При изъятии узла 4 выявляется сечение из узлов 2 и 4. Выделенные сечения нужно занести в список, который и будет определяющим при решении вопроса о существовании трёх независимых путей. Рассмотрим вопрос существования трёх независимых путей между двумя соседними узлами. Если соседние узлы TV, и N2 соединены двумя параллельными линиями, то следует удалить из сети обе эти линии и проверить ее связность. При сохранении связности обнаруживаются три независимых пути между Nl и N2 существует. Такую проверку целесообразно делать только в случае, когда Nl и N2 являются сечениями из одного узла. Для остальных пар соседних узлов, соединённых параллельными линиями, три независимых пути существуют всегда. Если два соседних узла N{ и N2 соединены одной линией, при удалении которой связность сети сохраняется (при потере связности без линии Nl, N2 между узлами Nx и N2 имеется только один путь, состоящий из одной линии), необходимо посмотреть список сечений из двух узлов. Трёх независимых путей между JV, и N2 в этом случае может не быть, когда существует узел N3, такой, что пары узлов iV,, N3, и N2, N3 составляют сечения из двух узлов. Проверка осуществляется следующим образом. Нужно удалить из сети линию Л , N2. Если в сети без линии N]f N2 узел yV3 представляет собой узел-сечение, разделяющее N, и N2, то трёх независимых путей между узлами Л и N2 не существует. В остальных случаях, когда узла N3 нет или он не является узлом-сечением, разделяющим iV, и N2 в сети без линии iV,,iV2, три независимых пути между соседними узлами N, и N2 не существуют.
Эффективный алгоритм генерации столбцов в задаче оптимального использования сети
На практике решение указанной задачи по методу Данцига-Вулфа требует большого количества итераций. При этом основной объём вычислений приходится на решение локальных задач. Это вызывает потребность в разработке быстродействующих алгоритмов нахождения кратчайших путей, учитывающих специфику решаемой задачи. Ясно также, что в оптимальном решении задачи (2.1.10) -(2.1.12) обязательно существуют такие корреспондирующие пары, соединения которых проходят по элементам с / . Далее, т.к. при переходе от одного оптимального базиса к другому, в базис вводятся столбцы с нулевой относительной оценкой, то множество корреспондирующих пар, пути для которых в оптимальных решениях непременно содержат линии с / ", определяется однозначно. Определение 1. Разрезающим множеством для некоторых корреспондирующих пар называется множество таких рёбер сети, удаление которых из сети нарушает связность сети для этих корреспондирующих пар. В критерии Ф фигурирует путь, следующий за кратчайшим для каждой корреспондирующей пары. Находить его нужно однажды для всего процесса решения задачи (2.1.17) - (2.1.21), содержащей много итераций, так что дополнительные вычисления, необходимые для получения коэффициента м. оправданы. 2.2. Алгоритмы нахождения кратчайших путей в оптимизационных задачах на сетях связи Ниже предлагаются - модификация алгоритма Дейкстры и новый алгоритм нахождения кратчайших путей в сети, ориентированные на использование в итерационных процессах решения оптимизационных задач. Приводятся результаты вычислительного эксперимента, подтверждающего повышенную эффективность алгоритмов.
При решении различных задач на сетях часто необходимо находить оптимальные (в частности кратчайшие) пути между заданными парами узлов. Наиболее распространенными алгоритмами нахождения кратчайших путей являются алгоритмы, основанные на идее расстановки пометок. Для случая, когда один узел соединяется со многими, классическим алгоритмом является алгоритм построения дерева кратчайших путей Дейкстры [17].
Существует много модификаций алгоритма Дейкстры, направленных на экономию вычислений, как общего характера, так и использующих специальную структуру сети. При этом основные усилия направлены на уменьшение вычислений при расстановке пометок для однократного получения каждого из путей.
Решая некоторые задачи, например, задачу распределения каналов на сети или развития сети, проектирования сети и другие, приходится многократно находить оптимальные пути в постепенно изменяющихся условиях. На определенном этапе при нахождении максимального многопродуктового потока единственной характеристикой элементов сети является наличие свободных каналов.
Назовем элемент сети свободным, если на нем имеются свободные каналы, и занятым, если свободных каналов нет. При решении вышеупомянутых задач, если элемент сети свободен, его длина считается равной нулю, длина занятого элемента сети не равна нулю.
Пусть имеется множество пар соединяемых узлов на сети. Задача состоит в многократном построении оптимальных путей в изменяющихся условиях на сети. Сгруппируем соединяемые пары по одинаковым концевым узлам. Общий для нескольких соединений концевой узел назовем начальным, второй концевой узел каждого соединения - конечным. При описании алгоритма для простоты изложения будем рассматривать один начальный узел (обозначим его «Ь ) и несколько конечных.
В начале решения задачи все элементы сети свободны, и естественно искать пути, содержащие минимальное количество дуг. Равнозначность элементов сети подсказывает идею: при расстановке пометок так направлять дуги, чтобы обеспечить возможность нахождения не одного пути с минимальным количеством дуг, а всех таких путей. Этого можно достигнуть при условии, если для каждого узла отмечать не единственный предыдущий, а все множество соседних узлов предыдущего ранга. Совокупность дуг, направленных таким образом, назовем полем. Очевидно, с помощью поля можно построить любой путь, содержащий минимальное количество дуг. Выбор того или иного пути будет определяться конкретной ситуацией на сети.
Линейная частично-целочисленная задача с большим количеством непрерывных переменных
Спецификой частично-целочисленной задачи (3.1.1) - (3.1.3) является отсутствие непрерывных переменных в целевой функции и чрезвычайно большое количество непрерывных переменных в ограничениях. Рассмотрим математическую постановку задачи максимизации прибыли оператора сети при ограниченных капиталовложениях [130]. Владелец сети предоставляет потребителям (соединяемым парам узлов) каналы, взимая тарифную плату за каждый предоставленный канал. Тариф различен для различных пар узлов. Себестоимость эксплуатации одного канала в каждой линии передачи также может быть различной. Рыночный спрос на предоставление каналов между парами узлов ограничен сверху. У владельца для развития сети имеется ограниченная сумма средств. На эти средства могут быть построены новые линии, переоборудованы узлы. Целью владельца является такое использование имеющихся средств, которое позволит на модернизированной сети получить максимальную прибыль от предоставления каналов.
Воспользуемся обозначениями, введенными в главе 2 (п.2.3.1) и дополнительно обозначим: у{ - переменная, принимающая значения 0 или 1 (1 соответствует строительству или переоборудованию /- го элемента сети пор варианту, 0 - его отсутствию), dip - приращение емкости /- го элемента сети при переоборудовании или строительстве по р-щ варианту, С-1р - стоимость /- го элемента сети при переоборудовании или строительстве по /7-му варианту, W - сумма выделенных средств на капиталовложения.
Таким образом, задача максимизации прибыли оператора при ограниченных капиталовложениях формально записывается как задача (3.2.1) -(3.2.5). По сравнению с задачей максимизации прибыли владельца на существующей сети [128] задача (3.2.1) - (3.2.5) является нелинейной оптимизационной задачей, содержащей как большое количество непрерывных переменных, так и большое количество целочисленных переменных, и поэтому не может быть решена классическим подходом с помощью последовательности симплекс-метод - метод ветвей и границ и т.д.
Необходимо, как и в [128], уменьшить без потери эквивалентности количество ограничений. Их уменьшение произведем точно так же, как и в [128]. Исключим временно из задачи (3.2.1) - (3.2.5) ограничения (3.2.2) и рассмотрим задачу (3.2.1), (3.2.3) -(3.2.5). Для решения задачи применим метод разделения переменных [92].
По теореме двойственности задача (3.2.5) - (3.2.7) допустима и имеет конечное оптимальное решение, так как, очевидно, при любых фиксированных УІР при / = 1,..., U\ +1 V\ и всех р, удовлетворяющих офаничениям (3.2.4), допустима и имеет конечное оптимальное решение двойственная к ней задача (3.2.1), (3.2.3), (3.2.5). Оптимальное решение задачи (3.2.5) - (3.2.7) достигается в одной из вершин многофанника, определяемого офаничениями (3.2.4), (3.2.5), (3.2.6). Обозначим вершины этого многофанника через ип у п = 1,..., N, где N - количество вершин многофанника, определяемого офаничениями (3.2.4), (3.2.5), (3.2.6). К сожалению, N достаточно велико даже для маленьких сетей и непосредственный их перебор практически нереализуем. Рассмотрим алгоритм монотонного перехода от вершины к вершине, позволяющий решить исходную задачу (3.2.1), (3.2.3) - (3.2.5).
Решим задачу (3.2.11) при ограничениях (3.2.4), (3.2.10), (3.2.12). У из оптимального решения этой задачи (обозначим его через УЪ ) подставим в задачу (3.2.5) - (3.2.7) и т. д. Через конечное число таких шагов [92] будет получено оптимальное решение (3.2.8), (3.2.9) или, что то же самое, исходной задачи. Пример решения задачи развития сети при ограниченных капиталовложениях. Предыдущая задача рассматривалась без привлечения понятия времени, точнее сказать, все рассмотрения неявно велись в масштабах одной абстрактной единицы времени. Теперь рассмотрим задачу максимизации прибыли, где время будет фигурировать в явном виде [132]. Прибыль будем считать поступающей непрерывно и при фиксированных условиях по линейному закону. Будем считать, что рыночный спрос на каналы достаточно велик, так что у владельца сети возникает желание расширить (развить) сеть. Может оказаться, что собственных средств на развитие сети у владельца сети в различных смыслах недостаточно. Предположим, что банк выдает ссуду на развитие сети под возврат в заранее оговоренные сроки. Задача состоит в том, чтобы развить сеть на заемные средства и вовремя расплатиться с банком. Таким образом, можно считать, что основной целью является выбор оптимального объема кредита.
Абсолютная унимодулярность матриц ограничений многомерной задачи о ранце специальной лестничной структуры
Для определенности рассмотрим матрицу, выпуклую по строкам. Выберем произвольный ее минор М . Очевидно, его матрица также будет выпукла по строкам. Выделим в матрице минора М все строки, единицы в которых начинаются с первого столбца (если таковых нет - минор равен нулю). Среди выделенных строк выберем такую, в которой минимальное количество единиц, прибавим выбранную строку к остальным выделенным строкам с обратным знаком. Эта операция не меняет величины Ми не нарушает выпуклости его матрицы. Кроме того, она позволяет свести вычисления минора М к вычислению с коэффициентом +1 минора М , порядка на 1 меньшего, чем у минора М. При этом матрица минора М также выпукла, тем самым, теорема доказана.
Определение выпуклости матрицы дано в терминах, зависящих от взаимного расположения строк (столбцов) матрицы. Абсолютная унимодулярность выпуклой матрицы не зависит от взаимного расположения строк (столбцов). Поэтому представляет интерес алгоритм проверки, является ли произвольная заданная матрица, состоящая из 0 и 1 выпуклой или нет. Как показывают построенные примеры, матрица, выпуклая по строкам, может оказаться не выпуклой по столбцам, и наоборот. Поэтому алгоритм проверки выпуклости матрицы состоит из двух частей: проверка выпуклости по строкам и проверка выпуклости по столбцам. Очевидно, выпуклость матрицы по строкам можно проверить перестановкой ее столбцов. Рассмотрим проверку выпуклости по строкам. Переставим столбцы рассматриваемой матрицы так, чтобы некоторая в ней строка стала выпуклой. Заметим, что после получения хотя бы одной выпуклой строки возможности перестановки столбцов сужаются. Следующую строку можно сделать выпуклой лишь при соблюдении условия сохранения выпуклости уже полученной строки. Эти условия состоят в следующем: единицы выпуклой строки между собой могут переставляться произвольно, нули выпуклой строки также могут переставляться между собой произвольно, допускается также перестановка влево и вправо до конца строки всех столбцов, содержащих единицы выпуклой строки, как единого целого. Пусть мы получили некоторое количество выпуклых строк проверяемой матрицы и пусть при рассмотрении очередной строки окажется, что строка не может быть сделана выпуклой без нарушения выпуклости других строк. Тогда, очевидно, матрица не является выпуклой по строкам. Аналогично может быть проведена проверка выпуклости матрицы по столбцам. Алгоритм проверки выпуклости объема, очевидно, не требует большого количества операций. В некоторых случаях проверка на выпуклость может быть осуществлена быстрее. Лемма 4.3.1. Пусть, например, рассматриваемая матрица является 0-выпуклой по строкам. Тогда, если она содержит два соседних столбца таких, что нули в них в сумме пересекают все строки, то эта матрица является выпуклой. Доказательство. Свернем рассматриваемую матрицу в цилиндр и развернем ее снова в плоскость так, чтобы упомянутые выше два столбца оказались первым и последним столбцами. Тогда в силу выпуклости по нулям исходной матрицы, преобразованная матрица, полученная по существу перестановкой столбцов, окажется выпуклой.
Таким образом, любая многомерная задача о ранце с выпуклой матрицей ограничений в силу ее унимодулярности может быть решена с помощью симплекс-метода. Структура матрицы ограничений многомерной задачи о ранце, рассмотренной в п.4.1, может быть названа специальной лестничной и сверху и снизу. Очевидно, что ее обобщение, лестничная матрица и сверху и снизу, в которой общие переменные содержатся не только в соседних ограничениях, также является выпуклой и по строкам и по столбцам и тоже может решаться с помощью симплекс-метода. Приведем пример, который показывает, что метод, предложенный для решения многомерной задачи о ранце с матрицей ограничений специальной лестничной структуры, не может быть перенесен на многомерную задачу о ранце с матрицей ограничений общей лестничной структуры (МЗРМООЛС).
После любого конечного числа шагов из оптимальных решений задач с двумя офаничениями оптимальное решение исходной задачи с тремя офаничениями сформировать, легко видеть, невозможно. Тем самым мы доказали, что метод решения, разработанный для многомерных задач о ранце с матрицей офаничений специальной лестничной структуры не переносится на задачи с матрицей офаничений общей лестничной структуры.
Полученная цепочка равенств позволяет получить решение, лучшее, чем оптимальное - следовательно, предположение о строго большем нуля минимуме в (4.3.2.1) неверно, и оптимальное решение задачи с к +1 ограничениями тоже может быть представлено как объединение оптимальных решений к + 1 задач с одним ограничением каждая и с целевыми функциями, сумма которых равна целевой функции исходной задачи. Теорема о разложимости доказана.
