Синтез многопродуктовых сетей с вогнутыми функциями стоимости тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕШЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

ДЕМИДОВИЧ Олег Игоревич

СИНТЕЗ ЫНОГОПРОДУКТОВЫХ СЕТЕЙ С ВОГНУТЫМИ ФУНКЦИЯМИ стоимости

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1992

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

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

профессор В.Р.Хачатуров,

кандидат физико-математических наук А.Б.Смирнов.

Ведущая организация - Институт проблем кибернетики РАН.

Защита диссертации состоится М _ 1992 г.

в часов на заседании специализированного совета К.002.32.01 при Вычислительном центре Российской Академии наук по адресу: 117967, Москва, ул.Вавилова, дом 40, конференц-зал.

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

Автореферат разослан "_"_ 1992 г.

Ученый секретарь Специализированного совета К 002.32.01 при ВЦ РАН кандидат физ.~мат. наук

К.В.Рудаков

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

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

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

Задачи синтеза сетей с вогнутыми функциями стоимости рассматривались в работах многих авторов, в том числе в работах В.Р.Хачатурова, А.В.Злотова, В.ПЛеренина, В.А.Трубина, Ю.Е.Ма-лашенко, А.К.Гнодяна, И.А.Мизина, Д.Д.Лозовану, М.Мину, Ф.Гло-вера, Р.С.Барра, Д.Клингмана, П.Грэя, Г.Галло, К.Санди, К.Со-дини, Д.Кеннингтона, Е.Ангера, К.Мурти, С.Сена, Б.Ягеда, Р.Со-ланда, М.А.Эфроимсона, Т.Л.Рэя, У.Зангвилла. Поскольку вогнутые потоковые задачи относятся к категории "трудных", решаемых с помощью переборных схем с отсечениями и, как правило, с учетом специфики рассматриваемого узкого класса задач, наибольшие успехи были достигнуты при разработке алгоритмов оптимизации в задачах синтеза однопродуктовых сетей (транспортные задачи, задачи о перевозках с промежуточными пунктами, задачи о размещении производства, задачи синтеза сетей с одним источником).

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

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

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

Цель работы. Основной целью диссертационной работы является:

- разработка алгоритма поиска глобального минимума в задаче синтеза многопродуктовой сети с вогнутой целевой функцией достаточно общего вида;

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

Методика исследования базируется на математическом аппарате теории исследования операций, линейного и дискретного программирования, теории графов и сетей, потокового программирования.

Научная новизна диссертации заключается в следующем.

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались автором на XXXVI, XLI, XLIII, XIV Всесоюзных научных сессиях НТОРЭС им.А.С.Попова, посвященных Дню Радио (Москва 1981, 1986, 1988, 1990), на Всесоюзном семинаре по оптимизации и ее приложениям (Душанбе, 1966) и семинарах Вычислительного центра РАН.

Публикации. По теме диссертации опубликовано 10 работ.

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

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

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

Глава 1 посвящена решению задачи синтеза многопродуктовой

сети с вогнутой функцией стоимости.

В }1 приводится формальная постановка задачи синтеза многопродуктовой сети.

Задан ориентированный граф й=(и,У) без петель с множеством вершин и и множеством дуг У. Предполагается, что вершины графа и его дуги пронумерованы, причем |и|, (V[=К. Дуга (1,3), имеющая номер 1с, обозначается через к(1,3). Граф С называется разрешающим.

В множества и выделены пары вершин, называемые тяготеющими. Совокупность всех тяготеющих пар образует множество Р. Предполагается, что элементы этого множества пронумерованы и |Р|=Ь. Если вершины е и Г образуют тяготеющую пару, то эта пара обозначается через (е,1), то есть так же как и дуга графа й (даже если такая дуга в графе отсутствует). Условимся обозначать через (е1Д1) тяготеющую пару (е,1), имеющую номер 1. Между вершинами е2 и 1 пары (е1,Г1)еР требуется передать продукт величины гх>0. Продукты разных тяготеющих пар считаются различными. Вершина еа считается источником, а вершина - стоком 1-го продукта. Для каждой вершины 1 введем в рассмотрение множества А(1) ={3€11: (1,3)€У| и Б(1)=|зеи: (3,1)еУ].

Обозначим через х^ величину продукта 1-й тяготеющей пары, проходящего по дуге (1,3) еУ. Припишем величинам х^ при 1=1 ,Ь, к(1,3)еУ номера, вычисляемые с помощью выражения К(1-1 )+к. Упорядоченная таким образом совокупность значений х^ образует вектор х, который называется потоком, если для произвольных заданных значений га выполнены условия

㻈в(1)

г _

п!

Га, есж 1=ех; 1=Т7ы;

О, если _!_' (1)

х т -1 т

.-г^ если 1=ГХ; ¿~t.ii.

О, (1,3)€У, 1Й7Ь. (2)

Пусть задано такое разбиение множества дуг V на подмножества У1 лг,...,У , при котором У/0, т=Т7м; УшП^п=0, и^п;

м • .

иУт=У. Обозначим через хт вектор с . компонентами

т=1

к(1,3)€У . 1=Т7ь, расположенными в порядке возрастания величин К(1-1 )+к. Передача потока по дугам подмножества У требует оп-

ределенных затрат- Предполагается, что величина этих затрат может быть записана в виде í^CrJ, где f - вогнутая функция своих аргументов, определенная в неотрицательном гипероктанте. Под задачей синтеза многопродуктовой сети понимается отыскание такого потока, который минимизирует общие затраты на eró'передачу

м . ■.

F(x) = £ îmUm) -»min. (3)

m=1 x

В 52 обсуждаются свойства оптимальных решений сформулированной задачи синтеза сети.

Множество допустимых решений Т>, заданное ограничениями (1 ) -(2), является замкнутым и ограниченным снизу. Поскольку глобальный минимум функции (3) по предположению конечен, то он достигается в одной или более крайних точек множества 2?. Известно, что базисные допустимые решения, системы уравнений (1) и только они являются крайними точками множества !), причем в каждом базисном допустимом решении передача любого продукта осуществляется по одному из элементарных путей, идущих из источника этого продукта в соответствугащеий сток.

Для заданной тяготеющей пары (e^f^cP, (líl^L), множество всех элементарных путей, исходящих из вершины е1 и входящих в вершину íx, обозначим через П1. Совокупность ,ц2,... ,¡iL) путей из G, в которой 1=1 ,L, назовем системой представи-

телей множеств путей соединения различных тяготеющих пар или просто системой представителей. Множество всевозможных систем представителей обозначим через S. Между системами представителей из множества S и крайними точками множества V можно установить взаимно однозначное соответствие. Поэтому перебор различных элементов из 3 эквивалентен перебору крайних точек множества V. Очевидно, что по заданной системе представителей £=((х1, (i.2,... легко определить базисное решение х(|), которому она соответствует:

í г . если (U)e|J. , _

xj,(?) = ] 1 (i,J)eV; 1=1,Ь. (4)

13 I О, если (l.J)Ai1;

Таким образом, исходная задача вогнутого программирования при линейных ограничениях эквивалентна задаче определения минимума функции F(|)=F(x(Ç)) на конечном множестве систем представителей 2:

(Р) F(£) — min.

les

В 53 описывается процесс построения дерева решений.

Рассмотрим на множестве S систему подмножеств S. Каждое подмножество в этой системе имеет обозначение, сходное с обозначением (ц1,ц2,...,ць) системы представителей, с той лишь разницей, что на любом месте вместо символа, обозначаюцэго путь, может стоять точка. Наличие такой точки на 1-й позиции в обозначении подмножества означает, что среди его элементов имеются системы представителей, включающие в себя любой наперед заданный путь из множества то есть любой из путей соединения тяготеющей пары (e1,f1)€P.

Дадим формальное определение системы подмножеств S в следующем виде:

1) любая система представителей из S является элементом системы подмножеств 3;

А

2) элементом S является также любое подмножество множества 3, предетавимое в виде

(А1.....Л1"1..,А1+1,...,AX)=U (Л1.....А1"1 .^.Л141.....Дь),

где А1 при 1£L<L обозначает точку или некоторый фиксированный путь из nif а величина 1 принимает произвольное целое значение в пределах 1<L<L.

Сопоставим каждому элементу feS дискретную задачу математического программирования

<Р|) PCO —min.

Cef

Очевидно, что общее число таких задач равно числу элементов системы подмножеств S. Так как SeS, то в множестве рассматриваемых задач имеется задача (IV,), которая совпадает с (Р) и называется исходной или начальной. Пусть f^E, f2eS и Хл*\г• Если подмножества ^ и |2 множества S удовлетворяют соотношению ^ с|2, то задачу ) назовем подзадачей задачи (Р^ ). Поскольку для любого СеЗ, то каждая задача (Р|) при является подзадачей начальной задачи (Р).

Воспользуемся совокупностью задач (Р|), для построения дерева решений. Будем считать, что все пути соединения каждой тяготеющей пары пронумерованы и через обозначен путь 1-й тяготеющей пары, имеющий номер 1. Пусть q обозначает число элементов множества Зададимся некоторой перестановкой из L

чисел (i ,i2,...,). Рассмотрим подмноже ство T)j = (•••.....• .,•).

в обозначении которого на 11 -й позиции располагается некоторый путь Ц^еП^ (KJ^q^), а на остальных местах - точки а также подмножества

= .....= s=23.

где J,k,...,m,n - s натуральных чисел, удовлетворяющих неравенствам KJö}^, 1 Ck^q^, ... , ICn^q^, Kns^. Очевидно, что совокупность подзадач (Рг&зг-з^). n=T7q,, в целом представляет собой задачу (Р'Уг-л^), так как разрешение всех, этих' подзадач

приводит к. решению указанной задачи.

Из самого способа построения подмножеств следует,'

что равенства = 0 и "П^у""^Пffi^l^ = 0 имеют место

тогда и только тогда, когда векторы [J,k,...,п] и [1,т,...,р] не равны друг другу. Отсюда вытекает, что задача (P^wO яв-

•lm—p—q

ляется подзадачей задачи (P^Wj-is) лишь в случае [3,k,...,n] =

=[1,и,...,р]. Таким образом,; разбиение задач на подзадачи (называемое также ветвлением) описывается деревом, изображенным на рис.1.

В J4 описывается способ вычисления нижних оценок значений целевых функций в задачах (Р|), |еЗ. Оказывается, что

min P(i) *

» min Fj^d^n^p.x3*^).....хЧц^Д^ц1*).^.....^) +

+ min ? ЛхЧфАФ.....+

цЧц. ^ J +....................+

+ min Fli^Ji(x1»(^),xIa(|^),...,xis(^),Ö,Ö.....Ö.x^iA)) -

[

F., .....х^Л.О.г1*«.....f"L) +

+ 0,0,г*».....i*> +■

+

+

+ i^S*1^) . •. .х^Ц^.О.б.....0.f*>].

где х^Сг^.х^,...,*^] при 1=TTL и при k(l,3)eV; г1=[г1,

тх.....rj при 'l=77l; Fliia_li(xli,xl2,...,xJ'.) = P(x1txz.....х1); 0 =

= [0,0.... ,0]; а х1^)-вектор размерности К с компонентами (I,J(см.(4)). Иными словами определение нишей границы требует решения ряда задач такого же типа как исходная, но однопродуктовых. При- произвольных целевых функциях может оказаться, что поиск оптимального решения задачи

(SB) Р — min

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

Рис. 1.

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

« (V

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

В $5 рассматривается поиск оптимального решения задачи синтеза сети при сэпарабельной целевой функции:

а.яет

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

х

что линейное преобразование у = У переводит многогранник

з.^ 2. — 1 **

допустимых решений г>сйкь в многогранник ёс ик, на котором фактически осуществляется поиск минимума целевой функции (Б). В то же время это линейное преобразование не всякую крайнюю точку множества V переводит в крайнюю точку множества Ъ. Поровдение некоторой подзадачи в текущем дереве решений и ее последующее разрешение является нецелесообразным, если образ точки х(£) не является крайней точкой множества V для каждой системы представителей £ет?. Такую подзадачу можно вполне назвать избыточной.. Пусть (Р±111г_15Ч) - произвольная подзадача дерева решений.

В данной подзадаче продукты тяготеющих пар с номерами 1 ,12,.. ..Дз_1 передаются по путям М^еП^, ц^П^,..., М-^еП^.

Теорема 12 (достаточное условие избыточности). Если объединение каких-либо двух путей из множества .....содержит цикл, и этот цикл не, является контуром, то подзадача (Р^-^ч) является избыточной.

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

Чк-лп

формирования заведомо избыточных подзадач необходимо выделить в множестве П, подмножество путей П. (а1.1,^,... .ц3®^) сП, , обладаю-

Ц 3 к т ц

щее следующим свойством: подзадача (Р^у^л^) удовлетворяет доп

статочному условию избыточности при Ип^ЧП^Ц^.Ц^.....ц^) и

не удовлетворяет этому условию при ц^П, (|дЛ,цХ... .ц1^1). в дис-сертащш приводится описание процедуры перечисления путей из множества

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

Пусть (Р:^.^) - произвольная подзадача задачи синтеза

многопродуктовой сети, сформулированной в виде (1)-(2),(5). Обозначим через Пх некоторое подмножество множества П2 (1С<Ь). Положим по определению

^ "П^: .., цЦ]. (6)

Рассмотрим задачу (Р^^-л^) при П =П , Очевидно, что лю-

бое ее оптимальное решение является оптимальным решением задачи так как в этом случае Л^Ц^4 = ^¿л1" Вв®дам в Рас~

' ц1, если ,1г,...,1в_1|,

смотрение множества дуг V =• (

и Ц • если 1е[13,1а+1,...,1Л, _ __> ^

1=1,Ь, векторы 6(71)еВк, 1=1,1, с компонентами

, 1, если (р^)еУ ,

6оа(71> = 1 (р.ЯНУ,

рч 1 I л если

т

и::

X

и вектор ревк с компонентами р = ) б (V, )г., (р^)еУ. Поло-

рч я . рч ц

t=s

ким г=х'1(ц^)4х12(^)-1-.. , где 21(|х1) - поток 1-го про-

дукта, определенный равенствами

г , если (р^)ец1, 1 (р^)еУ.

если (р^)Д(х1,

Пусть £=(ц.1 ,ц2,....ц.1) е Т^Г^4 ~ произвольная система пред-

X»

ставителей и у (£)= ^Г х1 (ц1). Каждому пути ^ЧП^, поста-

1=1

вим в соответствие величины

UBin1«) =P(Z+xV*)) -?(*) = £ [WZpq+IV "^Р^-

IB (цЧ p ) = f (z+p ) - I (z+p-x^Cii1*)) =

Elf (z +p ) - f (z +p -Г, )1 . L pq pq "pq pq pq Kpq VJ

Назовем величины ЬВ(цЧр) и UB (цЧ соответственно нижним и верхним уровнем затрат 1-й тяготещей пары на пути цЧ Наименьший верхний уровень затрат UB1= min 1ГО(цЧ назовем индивидуальным уровнем затрат It-ft тяготеющей пары.

ПРАВИЛО ОТСЕЧЕНИЯ 1. Подзадача (Р^л^) при ЬВ(ц1',р)>Ш^

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

В диссертации предложена итеративная процедура изменения вектора р с целью увеличения нижних уровней затрат. Наибольшие нижние уровни затрат обозначаются через ЬВ(цЧ. Введение наибольших нижних уровней затрат позволяет сформулировать более жесткое правило отсечения.

ПРАВИЛО - ОТСЕЧЕНИЯ 2. Подзадача (Рдад^^) при lB(|xl4)>UB

'jk-m n ^

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

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

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

В §8 описывается схема получения нижних оценок значений целевой функции на основе декомпозиции исходной задачи. Запишем исходную задачу (1)-(3) в следующем виде:

Найти ?<зо - мл (6)

х

при ограничениях

Ах = Сг, х»0, (7)

где ,г2,...,rj. Обозначим через z=[z1,z2,....zj вектор, компоненты которого будем полагать независимыми переменными,

принимающими неотрицательные значения. Заменим в системе ограничений (7) вектор г на вектор г: ~

Ах = Сг, х»0. (50

Предположим, что различные базисные решения системы уравнений Ах = Си пронумерованы и общее их число равно Б. Пусть ^-произвольное из них, имеющее номер а, Вз - соответствующий базис, а? - вектор базисных переменных. Тогда если - совокупность небазисных столбцов, а? - вектор не базисных переменных, то систему уравнений Ах=Сг можно записать в виде В х3 + И Xй = Сг. Учитывая, что в базисном решении х^О, получаем

= Сг. Отбросив избыточные уравнения переходим к системе В'х® = С'г, откуда хв= (Б')_1С'2. Обозначив 0 = (В*)~1С*, имеем

3 3 Э Э £ 3

х^=Озг, б=1В результате проведенных рассуждений выявлена линейная зависимость между вектором базисных переменных х^. и вектором г. В силу того, что х^=0, аналогичная линейная зависимость от г имеет место для каждого базисного решения хз = хд(г), зиХ

Теорема 13. Если г>0 (т.е. гх>0, 1=1,1), то для з=1неравенство хз(г)>0 имеет место тогда и только тогда, когда х (г)50. Если г^О (т.е. 1=1 ,Ь), то из хд(г)>0 следует

х (2)50 (1 ^з^Б).

3 4.

Обозначим через Б* множество значений индексов з, для которых базисное решение ха(г) является допустимым,, то есть ха(г)гю. Предполагается, что 3^0. Для веБ^ положим Р(хз(2) ) = =Ра(г). На основании теоремы 13 функции Р (г) определены при

Теорема 14. Для зеБ^ функции Рд(г) вогнуты по г в неотрицательном ортанте.

Условимся обозначать через х*(г) глобально-оптимальное решение задачи (6)-.($) при заданном г. Рассмотрим функцию Ф(г) =

= т1п |рз(й)|.

г

Теорема 15. Для каждого вектора г^О, определяющего некоторую конкретную задачу (6)^(8), Ф(г) представляет собой значение целевой функции этой задачи в точке ее глобального оптимума, то есть Ф(г) = Р(х*(2;)).

Теорема 16. Функция Ф(а) вогнута по ъ в неотрицательном

гипероктанте.

Зададимся произвольным натуральным числом г. Выберем произвольным образом векторы и числа а1^0, 1=1,1;, но так,

чтобы 2^ = 1 и г= ]> а 21, где г = [г ,г2,... .г^] - заданный

г 1;

а фА г по т* = Гт»

1=1 1=1 вектор. Поскольку Ф(г) - вогнутая функция, то

г

ф(г)-ф[ I а^1] ^ а±ф(2±)-1=1 1=1

Отсюда

ъ 1=1

Величина Н = а^РСх* (а1)) представляет собой нижнюю оцен-1=1

ку значений целевой функции (3) на множестве Т>. Очевидно, что эта оценка определяется конкретным выбором векторов г1 и величин а , 1=1,г. Очевидно также, что указанный выбор можно осуществить достаточно произвольно.

Определение значений Г(х*(г1)) при вычислении нижней оценки Н ■ предполагает отыскание глобально-оптимальных решений х*(21)'в задачах (6)-(7) при , 1=1,X. Сложность решения каждой из этих задач существенно зависит от числа нулевых компонентов вектора г1. Чем их больше, тем меньше размерность соответствующей задачи и, следовательно, легче поиск х*(и1). С другой стороны, чем меньше нулевых компонентов в каждом г1, тем сложнее решение задач, отвечающих этим параметрам, но значение искомой оценки мохеч оказаться лучше.

В 59 рассматривается способ построения неубывающей последовательности нижних границ.

Среди различных способов задания векторов ъ1 и величин а , 1=1,1, влияющих на величину нижней оценки, следует выделить

один, весьма удобный при проведении вычислений. Пусть 1 и

ь

Обозначим через ^ вектор размерности Ь, 1-й компо-

1=1

нент которого равен единице, а остальные - нулю. Воспользуемся символом П для обозначения совокупности всех натуральных чисел от 1 до I. Обозначил через 7 = |о^|1=1,1;|- некоторое разбиение множества П на подмножества, при котором 0^0, 1=1,г;

- и -

í$n= = Совокупность всех возможных разбиений

13 1=1 множества fl образует множество Г. Для произвольного разбиения

7 = jfl]|i=1 ,t| еГ определим величины at и векторы z1 в виде

ai=ai(T) IV zi=zi(T) £ Vi]-

jen] rj jen]

jen]

Этому разбиению отвечает определенное значение нижней оценки t

= Н(7) = a1(7)í,(x*(zi(7))). Таким образом, на множестве Г оп-1=1

ределена действительная функция Н:Г —» R. Множество еэ значений представляет собой совокупность нижних оценок для глобально-оптимального значения целевой функции исходной задачи.

Введем на множестве Г отношение частичного порядка (квазипорядка) следующим образом. Для двух разбиений 7 = |fl]|I=1 ,tj t Г

и б = |п®11=1 ,р| € Г пишем ]í5 и говорим, что 7 предшествует б

(5 следует за 7), если для любого i (l^l^t) существует 3

(1 при котором ítfcfi® .

1 i

Теорема 17. Если разбиения 7 = jn] | i=ÍTtj е Г и Q = |fi®|i=

=1 ,р| е г таковы, что 7^6, то H(7)<H(S).

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

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

В заключении сформулированы основные результаты диссертации, выносимые на защиту.

В приложении 1 содержится обзор методов решения различных

задач о штоках минимальной стоимости.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

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

фа. При этом разным тяготеющим тарам ставятся в соответствие

разные разрешающие графы.

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Деиидович О.И. Вопросы оценивания в проектировании многопродуктовых сетей // Тезисы докладов XLI Всесоюзной научной сессии НТОРЭС им. А.С.Попова, посвященной Дню Радио. - М.: Радио и связь, 1986. - Часть 1. - С. 58.

2. Деиидович О.И. Вычисление нижних оценок в многоэкстремальной задаче о штоке минимальной стоимости. - М.: ВЦ АН СССР, 1988. - 24 с.

3. Деиидович О.И. Метод ветвей и границ для решения задачи о многопродуктовом потоке с вогнутой функцией стоимости. - М.: ВЦ АН СССР, 1987. - 66 с.

4. Деиидович О.И. Метод решения одного класса задач о потоке минимальной стоимости // Тезисы докладов XUII Всесоюзной научной сессии НТОРЭС им. А.С.Попова, посвященной Дню Радио. -М.: Радио и связь, 1988. - Часть 1. - С. 52.

5. Деиидович О.И. Методы решения задач синтеза потоковых сетей с вогнутыми целевыми функциями. Часть I. - М.: ВЦ АН СССР, 1992. - 66 с.

6. Деиидович О.И. Методы решения задач синтеза сетей с вогнутыми целевыми функциями. Обзор. // Тезисы докладов XLV Всесоюзной научной сессии ВНТОРЭС им. А.С.Попова, посвященной Дню Радио. - М.: Радио и связь, 1990. - Часть 2. - С. 40.

7. Деиидович О.И. Определение множества эффективных маршрутов в задаче синтеза сети связи // Техника средств связи. Серия "Системы связи". - 1985. - Вып.1. - С. 16-23.

8. Деиидович О.И., Малашенко D.E. Задача о многопродуктовом штоке с нелинейным функционалом // Тезисы докладов ХХХУ1

, Всесоюзной научной сессии НТОРЭС им. А.С.Попова, посвященной Дню Радио. - М.: Радио и связь, 1981. - Часть 3. - С. 101.

9. Деиидович О.И., Малашенко Ю.Е. О решении многопродуктовой задачи с вогнутой функцией стоимости // Тезисы докладов Всесоюзного семинара по оптимизации и ее приложениям (Душанбе, 25-31 октября 1986 г.). - Душанбе, 198S. - С. 78-79.

10. Деиидович О.И.. Малашенко Ю.Е. Синтез сети связи методами линейного программирования. - М.: ВЦ АН СССР, 1986. - 56 с.

Олег Игоревич Демидович

Синтез многопродуктовых сетей с вогнутыми функциями стоимости

Подписано в печать 17.03.92. Формат бумаги 60*84 1/16 Тира« 100. Заказ 34-. Бесплатно

Отпечатано на ротапринтах ВЦ РАН 117967, Москва, ул.Вавилова, 40.