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

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

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

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ В ЗАДАЧАХ ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ И РАЗВИТИЯ СЕТЕЙ

Специальность 01 01 09 - дискретная математика и математическая кибернетика

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

Москва 2007

003174184

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

Научный руководитель

Официальные оппоненты

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

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

кандидат физико-математических наук Д.Т Лотарев

Ведущая организация

ИПУ РАН

Защита диссертации состоится " 1 " ноября 2007 г. в час 00 мин на заседании диссертационного совета Д002 017 02 Вычислительного центра им. А А Дородницына Российской академии наук по адресу 119333 Москва, ул Вавилова, д 40.

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

Ученый секретарь диссертационного совета Д002.017 02, доктор физико-математических наук

В В Рязанов

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

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

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

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

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

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

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

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

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

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

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

сети

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ Во введении дается обзор работ по оптимизационным задачам на сетях Отмечены достигнутые результаты анализа многопродуктовых потоков в сетях общего вида и в специальных случаях плоских сетей Рассмотрены различные задачи синтеза многопродуктовых сетей Проанализирована трудоемкость алгоритмов нахождения кратчайших путей общег вида и в различных специальных случаях для плоских сетей. Целью диссертационной работы является разработка методов и алгоритмов оптимального анализа и синтеза многопродуктовых сетей общего вида, анализа и синтеза трехсвязной сети, разработка алгоритмов нахождения кратчайших путей, эффективных при применении их при решении оптимизационных задач на сетях

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

сети

Пусть имеется неориентированный граф G = {í/,F}, где U - множество

вершин, V - множество ребер Два пути, соединяющие вершины И,, и2 е U ? называются независимыми по вершинам, если они не содержат общих промежуточных вершин. Под связностью графа относительно пары вершин

и\-> и2 будем понимать максимальное количество независимых путей Р\ир Щ), которые могут быть организованы между вершинами Щ Связность графа С определим как Р = и2) Связность графа может быть достаточно

просто вычислена с помощью потоковых методов Однако этот способ требует большого объема вычислений

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

Сформулировано и доказано следующее утверждение Между двумя

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

Выводы.

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

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

Имеется конечная неориентированная сеть где и - множество

узлов, V - множество дуг Путём на сети 5, соединяющем корреспондирующую

пару узлов Щ , ик , будем, как обычно, считать последовательность узлов и дуг,

начинающуюся с узла Щ и заканчивающуюся узлом ик Обозначим через К

количество корреспондирующих пар, - множество всевозможных путей,

соединяющих к -ю корреспондирующую пару. IQk - количество каналов,

потребных к -й корреспондирующей паре, Ь1. емкость I -го элемента сети,

Ь1 > О Тогда условия существования на сети <5* требуемого потока (удовлетворения потребности всех корреспондирующих пар) могут быть записаны в виде

К

> О

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

П, ваш 1-й элемент сети входит в путь л, а1 = 4 51 [0, если не входит

УП . количество рёбер в сети »5" Не всегда можно сразу сказать, существует ли в заданной сети требуемый поток Однако ясно, что при достаточно малом

г >0 поток, удовлетворяющий ограничениям (I), (3) и

0)

(2) (3)

2Х

(4)

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

таХ2При(1), (3), (4)

(5)

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

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

начинаются с и идут подряд до к

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

шах

(6)

к — к],...,К,

(7)

К

к

X 2>л + £ ^

(8)

*=1 ^

и;,. >0

При решении задачи 2 методом Данцига-Вулфа генерируемые столбцы а] ,

м+м

обеспечивающие ^^ а,> , где , / = 1...|£/| + _ значения

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

|и|+М

с, =-1+ V<0 тг2 1-Х \и\ + \г\

неравенство } ' ч , где п, 1 1 '1 I I

/=1

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

Ж+Н л

Ш1П

ап

V У

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

21

М>М* =—!^

(2) Ж.

где % ~ - легко вычисляемые функции, зависящие

от значений двойственных переменных в задаче 1

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

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

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

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

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

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

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

Дополнительно обозначим ()к - верхняя граница потребности &-ой корреспондирующей пары, д* - нижняя граница потребностей к- ой корреспондирующей пары, - тариф для предоставления одного канала А:-ой корреспондирующей пары, И, - переменная часть себестоимости эксплуатации сети - себестоимость предоставления канала в 1-м элементе сети (линии или узле)

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

К

К—к

(9)

(10)

ч

(П)

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

к

- тах

к= 1 ^е^ 'е-чеЛ;

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

Г + 1 /=1

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

методом с генерацией столбцов с условными длинами линий А — Я", + Л, Если в оптимальном решении некоторые верхние ограничения не выполняются, то в задачу добавляется одно дополнительное ограничение и задача решается снова Так возникает конечная последовательность задач, в результате которой верхние ограничения будут выполнены Для удовлетворения нижних ограничений в (10) решается первая задача главы 2

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

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

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

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

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

т__

(12)

'=1 ieS,

/ei,

2>,>1, W;>0,

(13)

(14)

где Ь, имеют такие же значения и смысл, что и в ограничениях (1) - (3),

. Сц - строго положительные числа, неизвестные Уц принимают значения О

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

Рассмотрим особенности применения процедуры разделения Бендерса для

решения задачи (12) - (14) При фиксированных Уу выпишем задачу, двойственную к (12) - (14).

Г \

«=1 ^ jes,

т

-2>А,+ о.

+ г/ , max,

(15)

(16)

w, >0 / = 1,2,.,.,»i + l (17)

Согласно процедуре разделения Бендерса, оптимальные значения целочисленных переменных задачи (12) - (14) могут быть получены из следующей чисто целочисленной задачи min 2

р = 1,2,.. ,J ,

/

\

/еЧ

+ U

т+1

(18)

(19)

2Х

/=1

V

/eS,

+ Mm+I —

(20)

где Jр количество вершин, J г количество лучей многогранного множества, определяемого ограничениями задачи (15) - (17)

При фиксированных Уу задача (12) - (14) сводится к нахождению допустимого решения, удовлетворяющего ограничениям (13), (14) Для нахождения этих допустимых решений можно воспользоваться задачей вида (1) -

(3) Если в огггимальном её решении то ясно, что решений,

удовлетворяющих ограничениям (13), (14) нет

Условия разрешимости процедуры разделения Бендерса имеют вид

/=1 ^ yeS, ;

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

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

принимающая значения 0 или 1 (1 соответствует строительству или переоборудованию г- го элемента сети по р варианту, 0 - его отсутствию), с11р - приращение емкости /-го элемента сети при переоборудовании или

строительстве по р-му варианту, С1р - стоимость /-го элемента сети при

переоборудовании или строительстве по р-му варианту, Ш - сумма выделенных средств на капиталовложения

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

Х2ХЛ £б„1=1,м+м

к=1 чеХ,

(22)

fsk ^ 0 (23)

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

|Г/|+|К|

7=1 р

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

к

г = - X /?< тах (25)

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

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложены эффективные алгоритмы анализа разветвленности сети

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

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

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

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

Основное содержание диссертационной работы изложено в следующих публикациях

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

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

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

4 Думбадзе Л Г, Тизик АП Декомпозиционная методика решения одного класса задач линейного частично-целочисленного программирования // "Декомпозиционные методы в математическом моделировании и информатике" Тезисы докладов 2-й Московской конференции (Москва, 21-24 июня 2004г.) - М Вычислительный центр им А А Дородницына РАН, 2004, С.53-55

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

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

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

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25 09 2000 г Подписано в печать 25 09 07 Тираж 100 экз Уел пл 1,19 Печать авторефератов (495) 730-47-74, 778-45-60

ВВЕДЕНИЕ

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 глав, заключения, списка литературы.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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.