Введение к работе
Актуальность темы. Задачи о потоках в сетях занимают одно из важных мест в теории исследования операций. Во многих случаях они достаточно адекватно отражают существо практических задач и в этой связи являются ценным объектом исследований. Затраты на создание сетевых систем, как правило, чрезвычайно велики. Поэтому разработка методов решения оптимизационных задач на сетях, в том числе и методов решения задач о многопродуктовом потоке минимальной стоимости, без всякого сомнения является весьма актуальной.
Задачи синтеза сетей с вогнутыми целевыми функциями формулируются в тех случаях, когда стоимость передачи потока по дугам сети имеет ярковыракенный эффект экономии от масштаба. Характерной особенностью вогнутых задач является их многоэкстре-мальность. Локальные, в том числе и глобальный, минимумы вогнутой целевой функции достигаются в крайних точках допустимого множества решений. Это значит, что поиск глобального минимума требует просмотра и сравнения всех локально-оптимальных решений. Организация процедуры поиска и сравнения всех локальных минимумов представляет собой очень сложную вычислительную проблему .
Задачи синтеза сетей с вогнутыми функциями стоимости рассматривались в работах многих авторов, в том числе в работах В.Р.Хачатурова, А.В.Злотова, В.ПЛерешша, В.А.Трубина, Ю.Е.Ма-лашенко, А.К.Гнодяна, М.А.Мизина, Д.Д.Лозоввну, М.Мину, Ф.Гло-вера, Р.С.Барра, Д.Клингмана, П.Грэя, Г.Галло, К.Санди, К.Со-дини, Д.Кеншшгтона, Е.Ангара, К.Мурги, С.Сена, Б.Ягеда, Р.Со-ланда, М.А.Эфроимсона, Т.Л.Рэя, У.Зангвилла. Поскольку вогнутые потоковые задачи относятся к категории "трудных", решаемых с помощью переборных схем с отсечениями и, как правило, с учетом специфики рассматриваемого узкого класса задач, наибольшие успехи были достигнуты при разработке алгоритмов оптимизации в задачах синтеза однопродуктовых сетей (транспортные задачи, задачи о перевозках с промежуточными пунктами, задачи о размещении производства, задачи синтеза сетей с одним источником).
При рассмотрении многопродуктовых потоков приходится иметь дело с гораздо большим числом переменных и уравнений баланса продуктов в вершинах сети, что чрезвычайно усложняет поиск гло-
бального оптимума. По этой причине поиск решения в задачах синтеза мкогопродуктовых сетей обычно производится с помощью методов локальной оптимизации, а вопрос о качество получаемых решений остается открытым. Тем не менее разработка методов глобальной оптимизации применительно к задачам синтеза многопродуктовых сетей и использование их в комбинации с методами локальной оптимизации способствует улучшению качества получаемых решений, а стремительное развитие средств вычислительной техники в недалеком будущем значительно расширит сферу применения "точных" методов.
Особую значимость при решении слокных задач синтеза многопродуктовых сетей имеют процедуры оценивания глобально-оптимальных значений целевых функций. Если с помощью таких процедур удается найти хорошую нижнюю границу оптимальной стоимости сети, то она в известной степени позволяет оценить качество ло-кально-оптималъноых решений.
Цель работы. Основной целью диссертационной работы является:
разработка алгоритма поиска глобального минимума в задаче синтеза многопродуктовой сети с вогнутой целевой функцией достаточно общего вида;
создание процедуры оценивания глобально-оптимального значения целевой функции в задаче синтеза многопродуктовой сети с произвольной вогнутой целевой функцией.
Методика исследования базируется на математическом аппарате теории исследования операций, линейного и дискретного программирования, теории графов и сетей, потокового программирования.
Научная новизна диссертации заключается в следующем.
-
Предложен алгоритм решения задачи синтеза многопродуктовой сети с вогнутой функцией стоимости, основанный на последовательном перечислении путей соединения тяготеющих пар вершин.
-
В задачах синтеза сети с сэпарабельными целевыми функциями введены понятия нижнего и верхнего уровня затрат тяготеющей пары вершин на пути соединения источника со стоком, а также индивидуального уровня затрат тяготеющей пары. С помощью введенных понятий разработана процедура отсечения бесперспективных
ветвей дерева решений, а также процедура уменьшения размерности задачи синтеза путем априорного исключения части дуг из разрешающего графа.
3) Предложена процедура вычисления нижних оценок глобально-оптимального значения целевой функции в задаче синтеза многопродуктовой сети с произвольной вогнутой функцией стоимости. Главная идея процедуры заключается в декомпозиции исходной задачи на ряд подзадач меньшей размерности, нахождении в подзадачах глобально-оптимальных значений целевой функции и вычислении искомой оценки в виде взвешенной суммы найденных оптимальных значений.
Практическая ценность. Разработанные алгоритмы решения задачи синтеза шогопродуктовой сети и способ оценивания глобально-оптимального значения целевой функции могут быть использованы при проектировании сетей различного назначения, в частности при проектировании первичных и вторичных сетей междугородной телефонной связи.
Апробация работы. Основные результаты диссертационной работы докладывались автором на XXXVI, XLI, XLIII, XIV Всесоюзных научных сессиях НТОРЭС им.А.С.Попова, посвященных Дню Радио (Москва 1981, 1986, 1988, 1990), на Всесоюзном семинаре по оптимизации и ее приложениям (Душанбе, 1966) и семинарах Вычислительного центра РАН.
Публикации. По теме диссертации опубликовано 10 работ.
Структура и объем работы. Диссертация состоит из введения, двух глав, заключения, списка литературы и двух приложений. Основной текст диссертации звнимает 158 страниц. Общий объем диссертации вместе с приложениями составляет 249 страниц. Список литературы включает 130 наименований.