Разработка методов и алгоритмов в задачах оптимального использования и развития сетей тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Думбадзе, Ламара Георгиевна

• Думбадзе, Ламара Георгиевна
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Думбадзе, Ламара Георгиевна

ВВЕДЕНИЕ

1. ГЛАВА

АНАЛИЗ РАЗВЕТВЛЕННОСТИ СЕТИ

1.1. Эффективный метод анализа разветвленности сети

1.1.1. Общее

1.1.2. Постановка задач и метод их решения

1.1.3. Методика проверки существования трёх независимых путей между любой парой узлов сети без использования компьютера

1.1.4. Пример

1.2. Задача об улучшении разветвленности сети.

2. Г Л А В А

МАКСИМИЗАЦИЯ ИСПОЛЬЗОВАНИЯ СЕТИ

2.1. Оптимальное использование сети для многопродуктового 49 одноприоритетного потока

2.1.1. Постановка задачи и алгоритм решения

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

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

2.2.1. Поля кратчайших путей

2.2.2. Модифицированный алгоритм Дейкстры для неориентированной

2.2.3. Модифицированный алгоритм Дейкстры для поля

2.2.4. Результаты вычислительного эксперимента

2.3. Задача эффективной эксплуатации сети связи 75 2.3.1. Постановка задачи

2.3.2. Алгоритм решения задачи

2.3.3. Пример решения задачи

3. ГЛАВА

ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ РАЗВИТИЯ СЕТИ

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

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

3.2. Задача развития сети при ограниченных капиталовложениях

3.2.1. Математическая постановка задачи

3.2.2. Алгоритм решения задачи развития сети при ограниченных капиталовложениях

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

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

3.3.1. Математическая постановка задачи

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

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

4. ГЛАВ А

МНОГОМЕРНАЯ ЗАДАЧА О РАНЦЕ СПЕЦИАЛЬНОЙ ЛЕСТНИЧНОЙ СТРУКТУРЫ С КОЭФФИЦИЕНТАМИ РАВНЫМИ 0 ИЛИ 1 В МАТРИЦЕ ОГРАНИЧЕНИЙ

4.1. Постановка и алгоритм решения задачи

4.2. Пример решения задачи

4.3. Абсолютно унимодулярные матрицы, состоящие из 0 и

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

4.3.2. Абсолютная унимодулярность выпуклых матриц 119 ЗАКЛЮЧЕНИЕ 129 СПИСОК ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Разработка методов и алгоритмов в задачах оптимального использования и развития сетей»

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

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

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

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

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

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

- задача развития сети до удовлетворения всех потребностей при минимуме капиталовложений;

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

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

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

- доказаны некоторые теоремы об абсолютно унимодулярных матрицах, состоящих из 0 и 1;

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

Многопродуктовые сетевые потоковые задачи возникают, когда несколько товаров используют пропускные способности ребер на сети. Это имеет место в системах связи, городских транспортных системах, железнодорожных системах, многопродуктовых распределительных системах также, как и во многих других [118].

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

Сеть-это конечное множество Vузлов, 1,.,Л/, и конечное множество Е упорядоченных пар узлов ет =(i,j), называемых ребрами. Ребро ет имеет пропускную способность bm,m = 1 ,.,М. Пусть есть К продуктов и хкт и скт означают поток и единицу стоимости, соответственно, для продукта к на ребре ет. Продукт к имеет единственный источник sk и единственный сток tk, каждый с предложением и спросом sk,k = 1,.,К. Поток продукта к через ребро ет ограничен верхней границей икт,к = ^.К и т = 1,.,М.

Задача нахождения многопродуктового потока минимальной стоимости (МПМС) состоит в определении многопродуктового потока минимальной стоимости через сеть, который удовлетворяет потребности в каждом продукте при условиях: 1) ограничений предложения, 2) ограничений пропускных способностей, 3) сохранении потока при прохождении через узлы.

Обозначим для сети (V,E) Вп с Е - множество дуг, входящих в узел п и Ап с Е - множество дуг, исходящих из узла п. Это задача экономного пропускания многопродуктового потока через сеть.

В задаче нахождения максимального многопродуктового потока (ММП) потребности sk для /с = 1.К являются переменными. Цель состоит в том, чтобы найти неотрицательные потоки, максимизируя ^Sk при условии к сохранения потока в дугах и не превышения их пропускных способностей.

Вышеописанную модель называют узло-реберной постановкой. Пусть рк.Р* } есть множество всех путей из ребер, соединяющих Sk и tk. Тогда можно матрицу реберно-путевых инциденций описать следующим образом: akmj =1, если emePjk для m = 1.М\к = \.,KJ = \.,пк akmj = 0 в остальных случаях.

Пусть Ху (переменная) обозначает общий поток продукта к по пути Рк. Стоимость пропускания единицы продукта к по пути Рк есть Су = ^а^с^,. т

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

Другие варианты вышеупомянутых моделей обычно включают дополнительные ограничения некоторой формы, например, на суммарный поток. В [58] развили это добавление с использованием реберно-путевой постановки.

Многопродуктовые модели предлагались для решения не только задач распределения продуктов, но и задач маршрутизации, составления расписаний, назначений. В [116] предлагается МПМС модель с дополнительными ограничениями для решения задачи расписаний железнодорожного транспорта. В [49] представлена реберно-узловая многопродуктовая задача расписания многоцелевого танкера. Узлы представляют грузы в заданном порту в заданное время, в то время как ребра представляют возможные грузы между этими портами. Танкеры различных типов представляют различные возможные продукты. Цель состоит в том, чтобы максимизировать полезность назначений танкеров. В [57] представлена МПМС модель для назначения студентов в школы для достижения требуемого этнического состава. Продукты представлены студентами различных этнических групп. Источники и стоки представляют соседей и школы соответственно. Цель - минимизировать совокупность времени проезда (т.е. автобусного времени) при условии ограничений емкости школ.

Модели многопродуктовых потоков сети были также предложены в области планирования городского транспорта. При таком виде сети узлы представляют зоны и перекрестки улиц на территории города, в то время как ребра представляют улицы, шоссе и т.д. Предложения и потребности задаются числом транспортных средств, которые едут между зонами за какой-то период времени (например, утренний час пик). Продукты могут быть представлены либо как потоки между конкретными пунктами, либо как потоки от каждого к каждому. Каждое ребро ет имеет фиксированную емкость Ьт, которая может быть увеличена на ут через усовершенствование дороги за единицу стоимости hm. Если обозначить через /? общий бюджет на увеличение емкостей, то ограничения на емкости для этой модели могут быть записаны следующим образом:

5>*<bOT+ym ут > OVm к

I]hmym<P т

Далее хорошо известно, что общее время проезда по ребру это нелинейная выпуклая функция (см. [53,85,1 13]). В большинстве из более ранних работ в этой области [52-54,85,95,96,109,111] предложена для этих нелинейных функций либо линейная либо кусочно-линейная аппроксимация.

Более поздние работы, такие как [112] сосредоточиваются непосредственно на нелинейных моделях.

Многопродуктовые модели были предложены также в области систем компьютерных сетей. В этих сетях ребра представляют терминалы. Предложения и потребности задаются нормами передачи между узлами. Как и в сети с городскими перевозками можно взять продукты, представляющие сообщения между парами узлов, либо сообщения от каждого к каждому. Каждая линия передачи ет имеет фиксированную емкость Ьт, которая может быть увеличена за единицу стоимости hm. Приняв ^переменной для обеспечения равенства увеличенной емкости ет, запишем целевую функцию m'nScmxm +^11тУт • Если обозначить через Рт максимум возможности т,к т увеличения пропускной способности, то ограничения для пропускных способностей в этой модели имеют вид:

Ехк <Ь +V 0 < V < в V/77 лт — ит ^ У т w — У т — Ит к

Известны две основные задачи для модели компьютерной сети. В первой цель - определить пропускные способности ребер сети, которая удовлетворяет потребности при минимальной стоимости. Здесь скт обычно берется равным О, Ьт= 0, а Рт очень большие. Во второй - для имеющейся сети с фиксированными пропускными способностями определяются маршруты минимальной стоимости. Здесь (Зт берется равным нулю. В [63] формулируются и развиваются алгоритмы для различных моделей проектирования сети связи, которые являются нелинейными «несдерживаемыми» многопродуктовыми задачами. Более глубокое обсуждение этих и других подобных моделей можно найти в [56,73,85,94,115].

Заметим, что вышеописанные модели предполагают, что поток в ребре ет = (iJ) иДет от Узла ' к УЗЛУ У - Есть много реализаций, которые могут быть представлены как многопродуктовые потоковые задачи на неориентированной сети. Например, сообщения в сетях связи могут обычно проходить в обоих направлениях по ребру, но общий поток ограничивается суммой потоков в обоих направлениях. Многопродуктовые задачи этого типа могут быть смоделированы заменой каждого неориентированного ребра двумя ориентированными. Пусть для каждого ребра ет =(i,j), означает поток продукта к от узла /' к узлу j, а укт поток того же продукта от j к /'. Предполагается, что потоки одного и того же продукта в противоположных направлениях аннулируются, в то время как потоки различных продуктов объединяются, несмотря на направление. В этой модели ограничения по пропускным способностям имеют вид:

Vm к и

Ут+Ут-= 0, Vm,k

Если стоимостные коэффициенты неотрицательные, то полученную модель можно решать, игнорируя второе ограничение и используя симплекс-метод линейного программирования. Предположим, что в оптимуме существует ребро ет =(i,j), для которого У^+Ут- * Одля некоторого к. Тогда эти потоки могут быть отрегулированы так как во втором ограничении. Пусть fm равно чистому потоку в em =(/J) (т.е. % = укт+- уктЛ Если f* > 0, то равен и укт равен 0. Понятно, заменяя весь поток, для которого ограничения второго вида нарушены придем к альтернативному оптимуму, удовлетворяющему этим ограничениям.

Рассмотрим некоторые специальные случаи многопродуктовых потоковых задач [101].

Рассмотрим особенности двухпродуктовой потоковой задачи с минимизацией стоимости на неориентированной сети. Далее, поток может проходить в обоих направлениях по ребру ст, но общий поток не может к Г к к 1 превышать Ьт. Пусть вектора стоимости есть с = [сх ,.,смJ и пусть искомый вектор гк определяется следующим образом:

Гп =Sk, если n = Sk>

Г" если n = tk, rn = О в остальных случаях, n = 1

Приняв fx" x* 1 1 J мы можем поставить задачу двухпродуктового потока минимальной стоимости на неориентированной сети следующим образом:

11 2 2 mine х +с х

Ах1 = г1

Ах2 =г2 X Ъ к к к

X = \ X, ,. , М где А обозначает матрицу инциденций узлов-дуг, a b = [bu.,bM].

Задача двухпродуктового максимального потока на неориентированной сети принимает вид как в (1), кроме того, что S] и S2 -переменные и целевая функция есть max^j + S2).

Теперь покажем, что, используя переменную замещения, задачу максимального многопродуктового потока (7) можно преобразовать в две задачи однопродуктового потока минимальной стоимости на неориентированной сети. В [123] представлены подстановки: х1 = lf/] + if/1 - b и х1 = lf/X - у/2. Тогда (1) преобразуется: тт(с] +с2}/] +(с] - с2}//2 -с]Ь Ау/] + Ay/1 =г] + АЬ

Ау/Х - Ay/2 = г2 О <y/{<b, О <у/2<Ъ где О это вектор-столбец из нулей. После арифметических преобразований уравнений мы получим min [с1+с2У+{с1-с2)ц/2-с]Ь Ац/Х = 1 / 2 (л*1 +r2 + Abj Ai(/2=\l2{rx-r2 + Ab) 0<i//]<b, 0 <y/2<b которые разложимы на две однопродуктовые задачи. Достаточные условия для целочисленных потоков следуют непосредственно из (2).

Узел п назовем четным, если - четное целое. Сеть етеПп етеАп назовем эйлеровой, если Ьт - целое для всех дуг и все узлы четные. Заметим, что для эйлеровой сети АЬ состоит из четных целых элементов.

Теорема 1. (достаточное условие для целочисленности). Пусть Зачетные целые и пусть сеть эйлерова. Если задача двухпродуктового потока минимальной стоимости на неориентированной сети имеет допустимое решение, то существует целочисленный оптимум.

Ясно, что матрица ограничений в задаче (2) абсолютно унимодулярна. В [104] показано, что если и S2 выбраны переменными (т.е. задача максимального потока), то соответствующая матрица ограничений также абсолютно унимодулярна. Следовательно, имеет место

Теорема 2. ([77]). Если пропускные способности в задаче двухпродуктового максимального потока для неориентированной сети четные целые, то существует целочисленный оптимум.

Теорема 3. ([99]). Если в задаче двухпродуктового максимального потока неориентированная сеть эйлерова, то существует целочисленный оптимум.

В [104] показано, что Теорема 3 имеет место и в случае, когда источники и стоки не являются четными

Теперь представим свойства, которые используют понятие разрезающего множества. Многопродуктовое разрезающее множество это множество с Е, в котором для всех к каждый путь от sk к tk имеет по крайней мере одно ребро в С и оно минимально (т.е., не существует его собственного подмножества, также являющегося разрезающим множеством). Пропускная способность С, обозначенная д(С), определяется д(С) = ^Ът. Минимальное многопродуктовое разрезающее етеС множество это такое разрезающее множество, пропускная способность которого минимальна. *

Теорема 4. ([77]). Пусть S\ и S2 обозначают оптимальные потоки и д (С) обозначает пропускную способность минимального многопродуктового разрезающего множества в задаче двухпродуктового ♦ ♦ максимального потока на неориентированной сети. Тогда + S2 = д (С).

Алгоритмы для построения максимальных двухпродуктовых потоков приведены в [45,76,102,104]. Задача нахождения минимального многопродуктового разрезающего множества решается в [50,80,108]. Из * * теоремы 4 не следует целочисленность потоков при целых д (С),и S2-В [76] построен пример максимального двухпродуктового потока, в котором

5] = $2 = 1, но потоки равны 1/2 по двум путям от ^ к и по двум путям от S2 к t2. Кроме того, теорема 4 не может быть обобщена на трехпродуктовый поток. В [64] построен пример, в котором максимальный поток равен 1.5, хотя пропускная способность минимального разрезающего множества равна 2.

Пусть g{sk,tk} обозначает пропускную способность минимального разреза, разделяющего sk и tk. Также пусть g(s\,h?Н) означает пропускную способность минимального двухпродуктового разрезающего множества, отделяющего от t] и s2 от t2■ Пользуясь этими определениями, дадим необходимые и достаточные условия для реализуемости двухпродуктового потока.

Теорема 5. ([76]). Задача двухпродуктового потока минимальной стоимости на неориентированной сети имеет допустимое решение, если только g(s2,t2)>S2 и g(s],s2;t],t2)>Si+S2.

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

В [119] представлен алгоритм для получения максимального потока, когда каждый узел графа есть сток для всех кроме одного продукта.

Максимальный поток не равен пропускной способности минимального разрезающего множества для задачи многопродуктового максимального потока на ориентированной сети даже для двух продуктов [118],[120].

Теорема 6. ([121]). Задача о максимальном многопродуктовом потоке на полностью планарном графе целочисленна и величина многопродуктового потока равна пропускной способности минимального многопродуктового разрезающего множества.

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

В [14] указан широкий класс многопродуктовых потоковых задач, разрешимых в полуцелых числах.

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

Рассмотрим методы решения вышеупомянутых задач.

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

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

Axk=rk, Ук[пк) Y,xk+s = b (Л)

И)

12) (13)

О <хк<ик, Ук s> О,

14)

15) a s- это где А- матрица инциденций узлов-дуг, и = вектор слабых переменных, Кк и Л - двойственные переменные, связанные с (12) и (13) соответственно.

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

Пусть Хк={хк :Ахк =гк,0<хк <ик], к = \,.,К и пусть yk,.,ykqk обозначены экстремальные точки Хк. Если Хк- пустое множество для любого к, то исходная задача не имеет решения. Полагая

Хк Ф Ф и Хк ограничено, можно выразить хк = хк е где j к

У Я] = 1, Яу >0. Подставляя хкв (11) - (15), мы получаем j min

1Л укЛ+5 = Ь (а) v* (А) (16) j

4>0,V/,к, где (X и f3k -двойственные переменные. Уменьшенные цены, соответствующие этим переменным (16): ат Для Sm с = а-ск)ук;+{]к для Я)

Каждая переменная с уменьшенной стоимостью, большей нуля, является кандидатом для ввода в базис. Эта задача называется координирующей задачей. Нахождение наибольшей уменьшенной стоимости некоторого Як-, включает решаемые локальные задачи вида min(c* -а)хк

Ахк = гк (17)

0 <хк<ик

Задача (16) называется координирующей задачей, а К задач вида (17) называются локальными задачами. Координирующая задача решается модифицированным симплекс-методом с использованием локальных задач для проверки оптимальности и выбора кандидатов для ввода в базис координирующей задачи. Локальные задачи представляют собой однопродуктовые задачи и могут быть эффективно решены методами, представленными в [43,51,66,67,122,91,105].

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

Шаг 0. Инициализация. Найти начальный допустимый базис для координирующей задачи (16) и соответствующие двойственные переменные. Если допустимый базис построить невозможно, то могут быть использованы искусственные переменные и двухфазовая процедура.

Шаг 1. Назначение цен. Обозначим у оптимальную точку для zk = rnin{(c*-а)хк : Ахк = гк,0 < хк < ик}. Если нет решения, то координирующая задача (16) не имеет решения. Если fik-zk> 0, то у является кандидатом для ввода в базис основной задачи. В противном случае, никакая оптимальная точка из Хк не является кандидатом для ввода в базис. Если ат > 0, то sm кандидат для ввода в базис.

Существует ли хотя бы один кандидат для ввода в базис?

Если да, то перейти к шагу 2. Если нет, то закончить: оптимум достигнут.

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

Возможны другие варианты выбора алгоритма декомпозиции с использованием двойственных переменных. Например, несколько экстремальных точек, цены которых подходят на шаге 1 могут быть введены в базис на шаге 2 в координирующей задаче. Также, экстремальные точки, которые вышли из базиса в координирующей задаче, могут быть сохранены и их цены пересчитываются перед возвратом к шагу 1. Решенный пример задачи с использованием вышеописанного метода решения приведен в [48].

В [62] впервые применен этот подход для решения многопродуктовых потоковых задач на сети. Там представлен метод генерации столбцов для дуго-путевой постановки задачи многопродуктового максимального потока. В [82-84] сообщается, что эта работа послужила основой для хорошо известного метода декомпозиции Данцига-Вулфа [59].

В [110] 1) расширен метод генерации столбцов Форда-Фалкерсона в задаче нахождения потока минимальной стоимости, 2) специализирована декомпозиция Данцига-Вулфа для узло-дуговой постановки этой задачи и 3) показано, что эти две процедуры по вычислениям эквивалентны. Эти задачи рассматриваются также в [52] и [78].

В [111] впервые распространены приемы декомпозиции с использованием двойственных переменных для задачи многопродуктового потока минимальной стоимости. Полагается, что икт =оо\/к и т, а, следовательно, локальные задачи могут быть решены с использованием метода кратчайших путей. То есть, так как нет ограничений на емкости дуг, то нужно только определить кратчайший путь от sk к tk и удовлетворить требование, использующее этот путь. Этот метод выполняет по сути и содержанию инверсию базиса основной задачи.

В [55] метод декомпозиции с использованием двойственных переменных распространен для задачи максимального многопродуктового потока.

В [79] представлена схема генерации столбцов для дуго-путевой постановки задачи многопродуктового потока с нижними границами на потоки по дугам и с ограничениями (верхними границами) пропускных способностей. Показано, что эта задача может быть решена симплекс-методом с верхней границей, которому требуется рабочий базис размера М {М - количество дуг) и множества, которые используются, чтобы избежать необходимости следить за переменными на их верхних границах. Результаты вычислительных экспериментов не приведены.

Процедуры декомпозиции с использованием двойственных переменных для обобщенной задачи многопродуктового потока минимальной стоимости можно найти в [58,87,90,106,107,114,117]. Эти обобщения учитывают ограничения пропускных способностей узлов, выражение продуктовых потоков в виде натуральных единиц и совместные ограничения емкостей. Совместные ограничения подразумевают, что вместо назначенной верхней границы для потока через каждое ребро, верхняя граница назначается некоторой положительной комбинации потоковых дуг.

Рассмотрим методы декомпозиции по ресурсам. В [97] предложен подход декомпозиции по ресурсам для решения задач многопродуктового потока, но не специализирована какая-либо схема выполнения. В целом подход состоит в разделении пропускных способностей дуг среди отдельных продуктов таким образом, что решение К подзадач образует оптимальный поток для исходной задачи. На каждой итерации делается размещение и решаются А^задач однопродуктового потока минимальной стоимости. Сумма пропускных способностей для размещения на ребрах всех продуктов меньше или равна пропускной способности ребра в исходной задаче. Следовательно, объединенный поток от решений подзадач обеспечивает допустимый поток для исходной задачи. Затем проверяется оптимальность и процедура либо завершается, либо производится новое размещение по пропускным способностям дуг.

После добавления искусственных переменных исходная задача (11) -(15) принимает вид: к к

Ахк+ак =гк, \/к к

0 <xk<u\ Vk ak,S> 0, где у большая положительная величина, ак - вектор искусственных переменных, 1 - единичный вектор. (18) эквивалентна следующей записи:

19) к

0 <ук<ик, s> о, где

Vk{ук)= min{скхк + у\ак: Ахк + ак = гк,0<хк <ук)= max\rkjuk -ykvk :/ikA-vk <ck,juk <y l,vk >o} по теореме двойственности. Различные методики декомпозиции по ресурсам отличаются друг от друга в основном тем, как решается полученная задача. Некоторые методики рассматривались в литературе и три типичных подхода рассматриваются ниже. Другие методики представлены в [65,72,92].

Рассмотрим метод тангенциального приближения. juk,vk):jukA-vk <ck,juk <yl,vk >0,a(juk,vk экстремальная точка

Тогда задача (19) может быть записана как: тт^сгк (20)

Пусть ^к ~ " ак>гк^1к-укук^кУ)еЯкиУк

21) (22)

0 <ук<ик

23)

S> О (24)

Предположим, что Qk <^Rk. Пусть z{R) означает значение целевой функции в оптимальном решении (20)-(24) и пусть z{Q) означает значение целевой функции в оптимальном решении (20)-(24) при подстановке Qk в Rk в (21). Тогда z{Q)<z{R) обеспечивает нижнюю границу для (18).

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

Шаг 0. Инициализация. Множество /<—0 и пусть Уо ={уо,~.,Уо) является некоторым элементом \ ^Гук < Ь, 0 < ук <

I к ик

Множество Qk <— Ф и ак <--оо \/к.

Шаг 1. Решение локальных задач (определение верхней границы). Решить: ir i к\ • к к 1 к

Ук \У; ) = min с xt +/Ц (двойственные переменные) Ахк+ак=гк [Мк) хк<ук [vf) хк >0 к = \,.,К.

Шаг 2. Проверка оптимальности (нижняя граница = верхняя граница)

7k = ^Ук(ук)? Если да, то конец. Оптимум задается (xj,.,xk) и к к

Если нет, то добавить к Qk Vk и перейти к шагу 3.

Шаг 3. Решение координирующей задачи. Положить / <— / +1. Решить min2>* к ak>rk //-y\v V* и v(ju\vk)eQk к

0 <yf<u\\fk 5>0 и перейти к шагу 1. локальных задач, которые должны быть решены на шаге 1 это однопродуктовые задачи и они могут быть эффективно решены методами, представленными в [43,51,67,122,91,105]. Далее в задачах произошли изменения для дальнейших итераций только в верхних границах и можно использовать двойственный симплекс-метод для последующей оптимизации. Координирующая задача имеет два блока диагональной структуры и генерируемые верхние ограничения, которые могут быть использованы.

Рассмотрим метод возможных направлений. Хорошо известно ([65], теорема 2), что §{у)> даваемое (4) выпукло в выпукла, а ограничения линейны, то может быть использован метод возможных направлений.

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

Так как в (4) целевая функция

Нахождение производной f по направлению а в точке X по определению: f(x; а) = lim^o+ [f(x + to)-f{x)]lt.

Для определения локально лучшего направления ищется направление, на котором минимизируется производная направления g{y) среди рассматриваемых возможных. Пусть J = j j : ^ ук =bj к - множество индексов ограничений у. Задача поиска направления может быть записана: min ^(у\.,уК;а\.,аК)=^У'к{ук;ак) (25) к ak<0,jeJ (26) к

-\<ак<\ Vj,k, (27) j где g' и Vk означают производные направления g и Vk соответственно. Вектор v это субградиент выпуклой функции f: R-^D при yeR если f(y)-f[y)>v[y-y)\/yeR. Множество всех субградиентов Vk для у это множество j, называемое субдифференциалом. Связь между производной направления и субдифференциалом задается:

Теорема 7. ([92]). V'k[y \ак)= max^v:VесЖа(/|. Элементы dVk[y j являются отрицательными оптимальными двойственными к к переменными для ограничений х < у в задаче

Vk[у )= min\кхк +у\ак\Ахк+ак=гк,ак>Ъ,Ъ<хк<у ([65], теорема 6). Индекс к пока опущен. Обозначим двойственные переменные для v(y) через (w,v) и пусть - оптимум для v(y).

24 Следовательно, если (w,v) - оптимально для т. то - vedv(y). Тогда задача поиска требуемого направления задается: max- <9v (28)

У и,а» - v, < с,, если х, = 0 ' У J J' У / (29)

У ;; — сесли 0 < х, < V, Z—i ' {/ У' J ' J i (30)

Yj Uiaij ~ Vj = ' 0 < = У j I (31)

My < еслм = 0 (32) ui = если а, > 0 (33) v. > 0,если Xj = yj, (vj = 0, если Xj < у^ ) (34)

Восстановив индекс к и включив (28) - - (34) в (25) - (27), получив min^max^j %(-akvk) при (26), (27) и (29) - (34). Приняв h к к

Cj = с - — 2, и переходя к двойственности по отношению к внутреннему к п а/ >0 максимуму, можно записать задачу нахождения направления, как 4

Z-* 1 ~к 2 3 1 у:дгу=0 j:0<xj<ykj j:0<xkj<ykj j-xkj =0 j:0<xkj<yk j:0<xj=yk

W)k -aj (vA; и j: x) = o) -w)k>-a) [vkuj: 0<х)=у)) 0, V/eJ к

-\<ak: <1, V/ и к wl> 0, w4 >0.

Заметим, что задача поиска направлений блочно-диагональна и, следовательно, поддается специальным методам решения. После задания допустимого направления а, размещение задается выражением у) = ~ykj + adj V/, к.

Рассмотрим метод субградиентной оптимизации. В [75] предложен метод субградиентной оптимизации для решения задачи максимального многопродуктового потока. Прямое описание работы для задачи многопродуктового потока минимальной стоимости, содержащей икт - со\/т и к содержится в [89]. Обе работы исходят из того, что нахождение лучшего возможного направления требует большого объема вычислений и проще применять некоторые субградиенты для определения направления перемещения. Эти методы также не совершают попыток минимизации функции в выбранном направлении. Выбор длины шага не сильно зависит от поведения функции. С выбранным шагом в этом способе часто новая точка оказывается недопустимой (т> Ьт). Тогда к происходит возврат в допустимую область. Предложены эффективные средства для возвращения у в допустимую область у1,.,/): =6,7 > О к

Математическая запись задачи оптимизации имеет вид:

ГП1ГК т,к J

Эта задача декомпозируется на М задач квадратичного программирования, каждая с одним уравнением, которые могут быть легко решены простой процедурой поиска (подробности приведены в [75]).

Размер шага, который обычно использовался в методах субградиентной оптимизации равен: tn - A,n[g(Y)—g* /уу,где Яп это невозрастающая последовательность с 0<Лп<2, g это нижняя граница в (19) а V это субградиент g(y) в Y. Сходимость этой процедуры гарантируется, когда * g - оптимальное значение целевой функции. Однако, так как оптимальное значение целевой функции обычно не известно заранее, то использовалась * оценка g и было обнаружено, что алгоритм работает вполне удовлетворительно [89].

Алгоритм субградиентной оптимизации состоит из следующих шагов. Шаг 0 Инициализация. Выбранный £ > О будет использоваться для ограничения, если найден s - оптимум. Выберем целое L> О, означающее максимальное количество перемещений и последовательность из

Я. Определим допустимую точку и нижнюю границу LB.

Назначить w —> со и / —»1.

Шаг 1. Решение однопродуктовых задач. Пусть zk = тт{скхк +у\ак \Ахк +ак =г\ 0<х* <ук,ак >о}. Если <w*, к то сохранить потоки, назначить w и перейти к шагу 2; в противном к случае, перейти к шагу 3.

Шаг 2. Проверка на конец. Если w* - LB < s{LB) и ак = 0 или / = L, то конец; в противном случае, перейти к шагу 3.

Шаг 3. Определение новой точки. Назначить /—>/ + 1, определить новую допустимую точку и перейти к шагу 1 .

Большую часть вычислений в вышеописанной процедуре составляет решение задач потока минимальной стоимости на шаге 1. Реализация, представленная в [89] использует двойственный симплекс-метод, который начинается с базиса из предыдущего положения. Субградиент вектор двойственных переменных), который требуется на шаге 3 - это результат вычислений шага 1. Эта реализация приблизительно на 50% быстрее, чем AFEX III [44] на множестве тестовых задач, линейные системы для которых содержали 192 строки и 704 столбца. Подобный подход также приведён в [68].

Рассмотрим методы разделения. Методы разделения это специализации симплекс-метода, в которых текущий базис разделён для использования его специальной структуры. к 1

Предположим, что ит=сот,к. С этим предположением задача многопродуктового потока минимальной стоимости может быть переписана в виде [92,118]: minJVjt* (36) к kxk+s = b (37) к

Акхк = гк к (38) 0, хк > 0, \/к (39) где Еа единичные матрицы соответствующих размеров. Предположим, что ограничения (37) разделены на два множества, называемые текущими ограничениями и вторичными ограничениями. Тогда (37) запишется ckxk+sc=bc, ^E'kxk+ss=b' к к

Предполагается, что Ак для к = \,.,К полного ранга. Если это не так, то к соответствующим ограничениям добавляются искусственные переменные, чтобы обеспечить полный ранг. Разделим Ак на [Bk,Nk], где det^^O и

Вкгк >0. Если это невозможно для некоторого ограничения (38), то (36)

39) не имеет допустимого решения. Следовательно, (36) - (39) может быть записано как: к к к к \ mm вхв + 44) НО) к

TxkN)+s<=b< (41) к

Y,Eskxk+ss=bs (42) к xk=B~lrk-BklNk 4, У к (43) sc>0, xkN > 0, У к (44)

0, х*>0, \/к (45) где все разделения совместимы с Ak=[Bk>Nk]. В [71] предложена релаксационная процедура с ослабленными ограничениями (45). Тогда (43) может быть использована для исключения хв из задачи и релаксированная задача может быть записана: minY И^'+Н-^ЧМ} («) к it

Е?(47) к к sc > О, х*>0, к = \,.,К (48)

Основная стратегия процедуры релаксации это решать релаксационную задачу (46) - (48) для xkN k = \,.,K. Если ослабленные ограничения удовлетворены текущим решением, то решение оптимально. С другой стороны, разделение на базисные и небазисные переменные изменяется таким образом, к что некоторые отрицательные переменные в х5 меняются с положительными переменными в xN. Доказательство того, что такая замена возможна приведено в [98]. Если ограничения sc > 0 нарушены, то разделение Е на EC,ES^ корректируется перемещением текущих нарушенных ограничений из Es в Ес. Вышеописанная процедура может рассматриваться как специальное применение двойственного симплекс-метода. Тем не менее вместо того, чтобы хранить обратный базис для (37) и (38), лучше хранить рабочий обратный базис для (47).

Есть два мотива для применения вышеописанной процедуры к многопродуктовым задачам. Первый, структура сети сохраняется, то есть хв + BklNkxkN = Blxrk может быть сгенерировано из множества меток, когда требуется. Второй, если связывающих ограничений по пропускной способности в оптимуме немного, то матрицы Еск должны оставаться достаточно маленькими на протяжении всей процедуры. Следовательно, двойственные итерации выполняются в маленькой системе. Метод неудобен тем, что применяется двойственная техника и допустимости нет, пока не достигнут оптимум.

Другие методы разделения для этого класса задач были предложены в [74,88,93,103,94,69,70,81]. В [94] дана специализация процедуры обобщённых верхних границ, в то время как [69,70] включают процедуры факторизации.

В [46,47] рассматриваются другие декомпозиционные подходы.

Рассмотрим вопросы вычислительной эффективности вышеописанных методов.

Декомпозиция с использованием двойственных переменных имеет репутацию метода с плохой сходимостью. Однако в [111,106,107,55] достигнуты некоторые успехи в использовании этого метода для решения многопродуктовых задач.

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

Субградиентный подход успешно развит для решения сетевых задач в

11,18].

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

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

В [19,20] рассматриваются вопросы проектирования сравнительно небольших сетей (30 - 40) узлов с наличием ряда дополнительных ограничений.

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

0.4 < от <0.6.

Искомый глобальный оптимум удовлетворяет условию Куна-Таккера. Однако, условию Куна-Таккера удовлетворяет также и любой локальный оптимум, что и предопределяет фундаментальные трудности в решении этой задачи. Одним из шагов по преодолению этой трудности является теорема, в которой получено более строгое необходимое условие глобального оптимума. Показано, что оптимальное решение обладает тем свойством, что каждое соединение проходит по одному пути. Разработан алгоритм, основанный на этом условии (алгоритм типа "жадный"). Сложность алгоритма для худшего случая может быть оценена как C)[m2N2], где м - количество линий в начальном решении, N- количество узлов. Алгоритм может быть применён для сетей средних размеров (например, N от 30 до 50 для полных сетей).

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

Тем не менее (несмотря на отсутствие гарантии) улучшенный жадный алгоритм может быть применён к таким случаям, так как из экспериментов следует, что в большинстве случаев он дает то же решение, что и стандартный жадный алгоритм. Кроме того, ввиду его огромной эффективности он может быть применён для довольно больших задач (решение задач до 200 узлов).

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

В [40] рассматриваются методы отыскания локального решения задачи нелинейного программирования с ограничениями типа равенства и неравенства: минимизировать f{x), xeRn, при ограничениях сг(х) =0,i е Е, xj^O, iel.

Для решения этой задачи авторами разработаны методы, использующие лишь значения первой производной, благодаря чему они лишены неудобств, связанных с выводом выражений для вторых производных, а также с необходимостью хранения и вычисления этих выражений. Эти методы на каждой итерации решают подзадачи линейного программирования: это позволяет избежать трудностей, связанных с решением квадратичных подзадач и необходимостью манипулировать с полной п х п - матрицей Гессе. Подзадача линейного программирования включает ограничения на доверительную область: вместе с использованием /, -точной штрафной функции это даёт возможность доказать глобальную сходимость при очень слабых условиях. Ограничение на доверительную область также позволяет использовать достоинство методов квадратичного программирования, в которых получается точная оценка активных ограничений в решении. Информация второго порядка представлена в виде редуцированной матрицы Гессе, размерность которой равна {n-t)x {n-t), где t - число активных ограничений.

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

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

При составлении проектов развития сетей связи важно выбрать (синтезировать) топологическую структуру будущей сети. Указанная проблема синтеза является сложной многоэкстремальной задачей больших размеров. Для поиска её решения обычно прибегают к эвристическим процедурам. Выбор структуры сетей и другие вопросы синтеза анализируются в работах [27-29,30

33]. Методы решения этих моделей имеют чисто эвристический характер [34].

В [34] имеется обширная библиография по оптимизации сетей.

Задача синтеза сети с вогнутыми функциями стоимости на дугах рассматривается в ряде работ, в том числе [24,42,25]. Показано, что задача относится к классу NP- полных задач. Применение метода ветвей и границ для отыскания глобального оптимума в задачах с достаточно произвольными исходными данными осуществимо лишь для малоразмерных сетей с числом вершин не более 15-17. Поэтому основные усилия большинства авторов сосредоточены на разработке эффективных эвристических алгоритмов решения поставленной задачи [26].

В [35] решаются задачи нахождения многопродуктового потока для специального случая в плоских сетях. Рассматриваются задачи на неориентированных планарных графах таких, что если соединить все источники данного графа G, с соответствующими стоками, то полученный таким образом граф Ga является планарным. Количество операций для определения f 3/>,

1 а для нахождения допустимости многопродуктового потока о п 2 log п f 5. V многопродуктового потока - о п/2 logпJ, где п - количество вершин в графе.

Вычисления проводятся на графе Ga, двойственном графу Ga.

Алгоритм находит многопродуктовые потоки, величины которых по-луцелочисленны, если емкости и потребности целочисленны. Целые многопродуктовые потоки получаются, если суммы весов рёбер е , инцидентных каждой вершине в Ga, равны одному и тому же числу. Веса рёбер е , обозначаемые ca'.Ea^>R для Ga=(V,Ea) определяются следующим образом: с(е), если ееЕ -dj, если е = еа.

Ф)= где Е - множество рёбер графа, G, V - множество вершин графа, Ga, Еа- множество рёбер графа Ga, dt - величина требуемого потока /-го продукта, с(е) - пропускная способность рёбер графа G.

Найденные с помощью алгоритма многопродуктовые потоки могут быть разложены на 0(п) однопутевых потоков.

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

В работах [36,37] задача проектирования спутниковой сети формулируется как модель целочисленного (один-ноль) квадратичного программирования (ЦКП) с целевой функцией, которая не является ни выпуклой, ни вогнутой. Задача эквивалентным образом преобразуется в модель линейного (один-ноль) программирования (ЦЛП) с большим числом переменных и ограничений. Решения находятся методом ветвей и границ и "жадными" эвристическими алгоритмами. Эти решения сравниваются между собой, а также с решениями, полученными инженерным способом. Приводятся результаты экспериментов, показывающие, что процедура ветвей и границ очень эффективна при решении задач с не более чем 40 городами и что одна из реализованных версий "жадных" эвристик в основном находит оптимальные или близкие к оптимальным решения.

В [38] обсуждается задача многопродуктового потока в планарном графе, в котором все стоки и источники находятся на одной стороне. Стороной плоского графа G называется подмножество его вершин Г таких, что добавление в граф G ещё одной вершины у и рёбер, соединяющих её со всеми вершинами Г, не нарушает планарности графа G. Доказывается теорема о том, что проверка допустимости многопродуктового потока в п -вершинном планарном графе, у которого все источники и стоки находятся на одной стороне, ограниченной рёбрами, Ь<2к, могут быть выполнены за o[bn + n<Jb\ogn) операций.

В [39] приводятся алгоритмы, которые вычисляют максимальные потоки в планарных ориентированных сетях либо за o[(logw)3j параллельных операций, использующих процессоров, либо за o((logft)2) параллельных операций на о[п6) процессорах. Потребление ресурсов этими алгоритмами доминируется стоимостью нахождения величины максимального потока. Когда такая величина задана или когда вычисления проводятся на неориентированной сети, то требуется o((log«)2] операций на о[пъ) процессорах. Не известен эффективный параллельный алгоритм для задачи максимального потока в общих сетях. В [38] приводится алгоритм нахождения кратчайших путей в плоских графах. Алгоритм находит дерево кратчайших путей за время o{riyj\ogn^ в то время как для стандартного алгоритма

Дийкстры требуется время 0(n\ogn). Улучшение достигается за счёт разбиения графа на специальные области.

Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Думбадзе, Ламара Георгиевна

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные результаты.

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

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

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

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

Установлена абсолютная унимодулярность выпуклых матриц.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Думбадзе, Ламара Георгиевна, 2007 год

1. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. М.: Наука, 1985.

2. Малашенко Ю.Е. Нормативный подход к анализу многопродуктовых сетей // Изв. АН СССР. Техн.кибернет. 1988. №3.

3. Малашенко Ю.Е., Новикова Е.М. Обобщенная задача анализа многопродуктовой сети // Изв. АН СССР. Техн.кибернет. 1989. №4.

4. Тизик А.П. Оптимизация загрузки сети многопродуктовым потоком // Труды НИИР. 1981. №4 , с. 75-79.

5. Тизик А.П., Цурков В.И. Декомпозиционная методика для одного класса задач блочного программирования // Ж.вычисл.матем. и матем.физ. 1989. Т. 29. №10.

6. Тизик А.Н., Цурков В.И. Оптимальное распределение каналов на сети связи // Изв. АН СССР. Техн.кибернет. 1989. №4.

7. Тизик А.П. Метод анализа связности сети // Сб.научн.тр. Центр.науч.-исслед. ин-та связи. Местные и междугородные сети связи.

8. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука,1985.

9. Тизик А.П., Думбадзе Л.Г. Алгоритмы нахождения кратчайших путей в оптимизационных задачах на сетях связи // Сб.научн.тр. Центр.науч.-исслед. ин-та связи. Цифровые системы передачи и интегральные сети. 1988.

10. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: Сов.радио, 1975.

11. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наук.думка, 1979.

12. Хачатуров В.Р. Аппроксимационно-комбинаторный метод, и его применение для решения задач регионального планирования. Дисс. .док.физ.-мат.наук. М., 1984.

13. Сергейчик В.А. Некоторые вопросы анализа и оптимизации сетей сбора и передачи данных // Сборник "VI конференция по теории кодирования и передачи информации, ч.З. Доклады". Москва-Томск. 1975, с.206-211.

14. Карзанов А.В., Ломоносов М.В. В кн.: Математическое программирование. М.: ВНИИСИ, 1978, вып.1., с. 59-66.

15. Карзанов А.В. О многопродуктовых потоковых задачах с целочисленными оптимальными решениями. М.: Наука, 1984.

16. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.

17. Ху Т. Целочисленное программирование и потоки в сетях. М: Мир, 1974.

18. Шор Н.З., Жуббенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов // Кибернетика. 1971. N3.

19. Геденидзе Г.С., Читишвили Т.Н., Борохович А.С. Проектирование первичной внутризоновой сети с помощью ЭВМ // Электросвязь. 1979. N4.

20. Гильченок Л.З. Алгоритм построения внутризоновой первичной сети // Электросвязь. 1985. N1.

21. Михалевич B.C., Сергиенко И.В., Шор Н.З. и др. Пакет программ ДИСПРО-3: назначение, классы решаемых задач, системное и алгоритмическое обеспечение // Кибернетика. 1985. №1.

22. Ахмедов Ф.Б. Метод последовательного назначения нулей для приближённого решения многомерной задачи о ранце // Тезисы доклада VI Всесоюзного симпозиума "Системы программного обеспечения решения задач оптимального планирования" М.: ЦЭМИ АН СССР, 1980.

23. Алиев А.А., Ахмедов Ф.Б., Бабаев Дж.А. Пакет прикладных программ РАНЕЦ-1 для приближённого решения многомерной задачи о ранце // Кибернетика. 1986. №2 .

24. Йенсен П., Барнес Д. Потоковое программирование. М.: Радио и связь, 1984.

25. Трубин В.А. Свойства и методы решения задач оптимального синтеза сетей. Киев: Знание, 1982.

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

27. Вышинская МЛ, Болдырев ВБ., Малашенко Ю.Е., Ушаков НА Стратегия модернизации сети связи // Сб. Техника средств связи. Сер. Системы связи. 1981. Вып. 4.

28. Давыдов Г.Б. Вопросы оптимизации развития сети связи // Электросвязь. 1977. №1.

29. Лочмелис Я.Я. Машинный метод оптимизации построения сетей связи // Сб. Радиоэлектроника и электросвязь. Исслед. по электродинам, и теории цепей. Рига. 1981.

30. Ляховецкий Л.З. Планирование прироста производственных мощностей отраслей электрической связи // Тр.учеб. ин-тов связи. 1975. Вып. 72.

31. Малашенко Ю.Е. Синтез сетей с учётом динамики их развития // Изв. АН СССР. Техническая кибернетика. 1981. №1.

32. Малашенко Ю.Е., Ушаков И. А. О построении математических моделей сложных технических систем (на примере сети связи) // Изв. АН СССР, Техническая кибернетика. 1982. №1.

33. Проблемы и перспективы развития связи // Тр. учебн.ин-тов связи. М-во связи СССР. 1976. Вып. 75.

34. Малашенко Ю.Е. Обзор моделей перспективного планирования сетей связи. М.: ВЦ АН СССР, 1984.

35. Matsumoto К., Nishizeki Т., Saito N. Planar Multicommodity Flows, Maximum Matchings and Negative Cycles //SIAM J. COMPUT. 1985, May. Vol. 15. №2.

36. Helme M.P., Magnanti T.L. Designing Satellite Communication Networks by Zero-One Quadratic Programming // NETWORKS. 1989. Vol. 19.

37. Helme M.P., Magnati T.L. Designing Satellite Communication Networks by Zero-One Quadratic Programming // Working Paper OR159.87. Operations Research Center. M. I. T. Cambridge. MA. 1987.

38. Frederickson G.N. Fast Algorithms for Shortest Paths in Planar Graphs, with Applications //SIAM J. COMPUT. December, 1987. Vol. 16, №6.

39. Johnson D.B. Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks // Journal of the Association for Computing Machinery. October, 1987. Vol. 34, № 4.

40. Fletcher R., Sainz de la Maza E. Nonlinear programming and nonsmooth optimization by succesive linear programming // Math. Progr. 1989. №3.

41. Minoux M. Network Synthesis and Optimum Network Design Problems: Models, Solution Methods and Applications //NETWORK. 1989. Vol 19.

42. Minoux M. Recherche de la configuration optimale d'un reseau de telecommunications avec fonctions de cout concaves. Annales des Telecommunications. 1974. №1,2. pp. 25 42; N3,4. pp. 139 -171.

43. Aashtiani H.A., Magnanti T.L. Implementing Primal-Dual Network Flow Algorithm. // Technical Report OR 055-76. Operations Research Center. M.I.T. Cambridge, Mass. 1976.

44. APEX III Reference Manual. CDC Corp. Publication №76070000. Minneapolis, Minn. 1974.

45. Arinal J.C. Maximal Biflow in an Undirected Network // IBM J. Res. Develop. 1969. №13.

46. Balas E. An Infeasibility-Pricing Decomposition Method for Linear Programs // Opns. Res. 1966. №14.

47. Bazaraa M.S. An Infeasibility Pricing Algorithm for the Multicommodity Minimum Cost Flow Problem. Working Paper, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta (undated).

48. Bazaraa M.S., Jarvis J.J. Linear Programming and Network Flows. New York: 1977.

49. Bellmore M., Bennington G., Lubore S. A Multivehicle Tanker Sheduling Problem // Trans. Sci. 1971. № 5.

50. Bellmore M., Greenberg H.J., Jarvis JJ. Multi commodity Disconnecting Sets // Management Sci. 1970. №16.

51. Bradley G.H., Brown G.G., Graves G.W. Design and Implementation of Large Scale Primal Transshipment Algorithms // Report № NPS55ZBW76091. Naval Postgraduate School, Monterey, California. 1976.

52. Bradley S.P. Solutions Techniques for the Traffic Assignment Problem. // ORC 65-35, Operations Research Center, University of California. Berkeley. 1965.

53. Carter E.C., Stowers J.R. Models for Funds Allocation for Urban Highway Systems Capacity Improvements // Highway Res. Rec. 1963. №20.

54. Charnes A., Cooper W.V. Multicopy Traffic Network Models // Theory of Traffic Flow. Robert Herman (Ed.), Elsevier Publishing Co., Amsterdam. 1961.

55. Chen H., Dewald C.G. A Generalized Chain Labelling Algorithm for Solving Multicommodity Flow Problems // Comput. Opns. Res. 1974. №1.

56. Chien R.T., Gomoiy R.E., Ни T.C. Communication Networks // IEEE Trans. Circuit Theory CT-11. 1964.

57. Dantzig G.B., Wolfe P. Decomposition Principle for Linear Programs // Opns. Res. 1960. №8.

58. Evans J.R. Theoretical and Computational Aspects of Integer Multicommodity Network Flow Problems, unpublished dissertation. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta. 1975.

59. Evans J.R., Jarvis J.J., Duke R.A. Graphic Matroids and the Multicommodity Transportation Problem // Math. Programming.1977. №13.

60. Ford L.R., Fulkerson D.R. A Suggested Computation for Maximal Multicommodity Network Flows // Management Sci. 1958. №5.

61. Fratta L. ,Gerla M. ,KIeinrock L. The flow Deviation Method: An Approach to Store-And-Forward Communication Network Design // Networks. 1973. №3.

62. Fulkerson D. R. Flows in Networks // Recent Advanced in Mathematical programming, R. L. Graves and Philip Wolfe (Eds.), McGraw Hill. New York. 1963.

63. Geoffrion A.M. Primal Resource-Directive Approaches for Optimizing Nonlinear Decomposable Systems // Opns.Res. 1970. №18.

64. Glover F., Karney D., Klingman D. The Augmented Predecessor Index Method for Locating Stepping-Stone Paths and Assigning Dual Prices in Distribution Problems // Trans. Sci. 1972. №6.

65. Glover F., Karney D., Klingman D., Napier A. A Computation Study on Start Procedures, Basis Change Criteria, and Solutions Algorithms for Transportation Problems // Management Sci. 1974. № 20.

66. Gratzer F.J., Steiglitz K. A Heuristic Approach to Large Multicommodity Flow Problems // Proceeding of the Symposium on Computer-Communication Networks and Teletraffic at Polytechnic Institute of Brooklyn. 1972.

67. Gravers G.W., McBridge R.D. Linear Programming with Linked Lists and Dynamic Factorization. Presented at the National Meeting of ORSA in San Juan. Puerto Rico. 1974.

68. Graves G.W., McBridge R.D. The factorization Approach to Large-Scale Linear-Programming // Math. Programming. 1976. №10.

69. Grigoriadis M.D., White W.W. A Partitioning Algorithm for the Multicommodity Network Flow Problem // Math. Programming. -1972. №3.

70. Grinold R.C. Steepest Ascent for Large Scale Linear Programs // SI AM Reviev. 1972. №14.

71. Hakimi S.L. Simultaneous Flows through a Communication Network // IRE Trans. Circuit Theory CT-9. 1962.

72. Hart man J.K., Lasdon L.S. A Generalized Upper Bounding

73. Algorithm for Multicommodity Network Flow Problems // Networks. 1972. №1.

74. Held M., Wolfe P., Crowder H. Validation of Subgradient Optimization // Math. Programming. 1974. №6.

75. Ни T.C. Multi-Commodity Network Flows // Opns. Res. -1963. №11.

76. Hu T.C. On the Feasibility of Simultaneous Flows in a Network // Opns. Res. 1964. № 12.

77. Jarvis J.J. On the Equivalence between the Node-Arc and Arc-Chain Formulations for the Multi-Commodity Maximal Flow Problem // Naval Res. Logist. Quart. 1969. №16.

78. Jarvis J.J., Keith P.D., Multi-Commodity Flows with Upper arid Lower Bounds. Working Paper, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta. 1974.

79. Jarvis J.J., Tindall J.B. Minimal Disconnecting Sets in Directed Multi-Commodity Networks // Naval Res.Logist.Quart. 1972. №19.

80. Jewell W.S. A Primal-Dual Multi-Commodity Flow Algorithm. ORC 66-24, Operations Research Center, University of California, Berceley. 1966.

81. Jewell W.S. Multi-Commodity Network Solutions. ORC 66-23, Operations Research Center. University of California, Berkeley. 1965.

82. Johnson E.L. Programming in Networks and Graphs. ORC Report 65-1. University of California, Berkeley. 1965.

83. Johnson E.L. Networks and Basic Solutions // Opns. Res. 1965. №14.

84. Jorgenson N.O. Some Aspects of the Urban Traffic Assignment Problem. Graduate Report, Institute of Transportation arid Traffic Engineering, University of California. Berkeley. 1963.

85. Kalaba R.E., Juncosa M.L. Optimal Design and Utilization Networks // Management Sci. 1957. №3.

86. Kalan J.E. Aspects of Large-Scale In-Core Linear Programming. Proceeding of the 1971 Annual Conference of the ACM, Chicago. 1971.

87. Kleitman D.J. An Algorithm for Certain Multi-Commodity Flow Problems // Networks. 1971. № 1.

88. Langley R.W., Kennington J.L., Shetty C.M. Efficient Computational Devices for the Capasitated Transportation Problem // Naval Res. Legist. Quart. 1974. №21.

89. Lasdon L.S. Optimization Theory for Large Systems. MacMillan Co., New York. 1970.

90. Maier S.F. A Compact Inverse Scheme Applied to a K'ulti commodity Network with Resource Constraints. Optimizations Methods for Resource Allocation, Richard Cottle and Jacob Krarup (Eds.), The English Universities Press, London. 1974.

91. McCallum C.J. A Generalized Upper Bounding Approach to a Communication Network Planning Problem. Working Paper, Bell Laboratories, Holmdel, New Jersey. 1974.

92. Potts R.B., Oliver R.M. Flows in Transportation Networks. Academic Press, New York. 1972.

93. Prager W. Problems of Traffic and Transportation. Proceedings of the Symposium on Operations Research in Business and Industry, Kanzas City, Mo. April 1954.

94. Robacker J.T. Notes of Linear Programming: Part XXXVII Concerning Multicommodity Networks. RM-1799, The Rand Corporation, Santa Monica, Calif. 1956.

95. Rosen J.B. Primal Partition Programming for Block Diagonal Matrices//Numer. Math. 1964. №6.

96. Rothschild В., Whinston A. On Two Commodity Network Flows // Opns. Res. 1966. №14.

97. Rothschild В., Whinston A. Feasibility of Two Commodity Network Flows // Opns. Res. 1966. №14.

98. Rothschild В., Whinston A. Multicommodity Network Flows. Working Paper, Krannert School, Purdue University, Lafayette, Ind. 1959.

99. Rothschild В., Whinston A., Kent J. Computing Two Commodity Flows // Opns. Res. 1968. №16.

100. Saigal R. Multicommodity Flows m Directed Networks. ORC 57-38, Operations' Research Center, University of California. 1966.

101. Sakarovitch M. Two Commodity Network Flows and Linear Programming // Math. Progr. 1973. №4.

102. Srinivasan V., Thompson G.L. Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm // J.Assoc. Comput. Machinery. 1973. №20.

103. Swoveland C. Decomposition Algorithms for the Multi-Commodity Distribution Problem. Working Paper No. 184, Western Management Science Institute, University of California, Los Angeles. 1971.

104. Swoveland C. A Two-Stage Decomposition Algorithm for Generalized Multi-Commodity Flow Problem // INFOR. 1973. № 11

105. Tindall Т. B. Minimal Disconnecting Sets in Directed Multi-Commodity Networks. unpublished dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta. 1972.

106. Tomlin J.A. A Linear Programming Model for the Assignment of Traffic // Proceedings of the Third Conference of the Australian Road Research Board. 1966. Vol. 3, Part 1.

107. Tomlin J.A. Minimum-Cost Multicommodity Network Flows // Opns. Res. 1966. №14.

108. Tomlin J.A. Mathematical Programming Models for Traffic Network Problems unpublished dissertation, Department of Mathematics, University of Adelaide, Australia. 1967.

109. Tomlin J.A. A Mathematical Programming Model for the Combined Distribution Assignment of Traffic // Transportation Set. 1971. №5.

110. Wardrop J.G. Some Theoretical Aspects of Road Traffic Research // Institute of Civil Engineers, London Proceedings. June 1952. Vol. 1. Part 2.

111. Weigel H.S., Cremeans J.E. The Multicommodity Network Flow Model Revised to Include Vehicle Per Time Period and Node Constraints // Naval Res. Log. Quart. 1972. №19.

112. White W.W. Mathematical Programming Multicommodity Flows, and Communications Nets // Proceedings of the Symposium on Computer-Communications Networks and Teletraffic. Polytechnic Institute of Brooklyn. 1972.

113. White W.W., Wrathall E. A system for Railroad Traffic Scheduling. Tech. Report No. 320-2993, IBM-Philadelphia Scientefic Center. 1970.

114. Wollmer R.D. Multicommodity Networks With Resource Constraints: The Generalized Multicommodity Flow Problem // Networks. 1972. №1.

115. Kennington J.L. A survey of linear cost multicommodity network flows // Oper. Res. 1978. V. 26. №2.

116. Rothearb W., Shein N.P. Frisch. Common Terminal Multicommodity Flow // Opns. Res. 1968. № 16.

117. Ford L.R., Fulkerson. Flows in Networks. Princeton. University Press. Princeton. 1962.

118. Sakarovitch. The Multi-Commodity Maximal Flow Problem. ORC Report 66-25. Operations Research Center. University of California, Berkeley. 1966.

119. Johnson E.L. Programming in Networks and Graphs. ORC Report 65-1. University of California. Berkeley. 1965.

120. Sakarovitch. The Multi-Commodity Maximal Flow Problem. ORC Report 66-25. Operations Research Center. University of

121. California, Berkeley. 1966.

122. Лэсдон Л. С. Оптимизация больших систем М.: Наука, 1975.

123. Tsurkov V.I. Hierarchical optimization and mathematical physics // Kluwer Academic Publishers. 2000.

124. Tsurkov V.I. Large-scale optimization. Problems and methods // Kluwer Academic Publishers. 2001.

125. Думбадзе Л.Г., Тизик А.П. Многомерная задача о ранце специальной лестничной структуры // Известия РАН. Теория и системы управления. 1996. №4.

126. Думбадзе Л.Г., Тизик А.П., Тресков Ю.П. Задача эффективной эксплуатации сети связи // Известия РАН. Теория и системы управления. 2003. №6.

127. Григорьев В.В., Думбадзе Л.Г., Тизик А.П. Максимизация прибыли оператора при ограниченных капиталовложениях на развитие сети // Труды института системного анализа РАН. Динамика нелинейных систем. Вып.17(1). М.: 2005.

128. Думбадзе Л.Г., Тизик А.П., Тресков Ю.П. Эффективный метод анализа разветвленности сети // Известия РАН. Теория и системы управления. 2006. №4.

129. Григорьев В.В., Думбадзе Л.Г., Леонов В.Ю. Максимизация прибыли владельца сети при взятии кредита на развитие сети // Труды института системного анализа РАН. Динамика неоднородных систем. Вып. 10(1). М.: 2006.