ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 6, с. 58-65
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 519.85
ЗАДАЧИ ЭФФЕКТИВНОГО ИСПОЛЬЗОВАНИЯ И РАЗВИТИЯ СЕТИ ПРИ КАПИТАЛОВЛОЖЕНИЯХ И КРЕДИТАХ
© 2007 г. В. В. Григорьев, Л. Г. Думбадзе, В. Ю. Леонов
Москва, ВЦ РАН Поступила в редакцию 21.06.07 г.
Задача максимизации прибыли при эксплуатации сети связи решается как задача линейного программирования большой размерности как по количеству ограничений - до нескольких тысяч, так и по количеству переменных - до нескольких миллионов. Исходная задача сводится к конечной последовательности задач линейного программирования, у которых ограничений на порядок меньше, переменных - до нескольких миллиардов. Задачи из последовательности решаются модифицированным симплекс методом с генерацией столбцов. Решены задачи максимизации прибыли владельца развиваемой сети, сдающего каналы в аренду, при ограниченных капиталовложениях и при получении кредита, определен оптимальный объем кредита. Предложены алгоритмы решения, основанные на процедуре разделения переменных. Приведены численные примеры.
Введение. Линейные многопродуктовые сетевые модели, как правило, имеют большую размерность [1, 2]. В [3, 4] рассматривалась задача максимального использования каналов сети при заданных соотношениях потребностей в каналах между парами ее узлов. В рыночных условиях важным фактором становится прибыль при эксплуатации сети. Для достижения этой цели может потребоваться изменение трасс соединения узлов и количество предоставляемых каналов.
Проблема рационального вложения капиталов на развитие сети может быть исследована с различных точек зрения. Во-первых, это задача максимизации прибыли, во-вторых, можно поставить вопрос: следует ли использовать выделенные средства на развитие сети или эффект от капиталовложений будет незначительным? Возможно, что на развитие сети необходимо взять кредит. В этом случае необходимо определиться с размером кредита и о возвращении его в срок. В статье будут рассмотрены эти постановки.
1. Постановка задачи эффективного использования сети. Владелец сети предоставляет потребителям (парам узлов) каналы, взимая тарифную плату за каждый использующийся канал. Для обеспечения нормативных показателей надежности должен быть обеспечен 100%-ный резерв - передача по двум независимым путям. Тариф варьируется для различных пар узлов. Себестоимость эксплуатации одного канала в каждой линии передачи также может отличаться. Рыночный спрос на предоставление каналов между парами узлов допускает ограничение сверху. Этот же спрос, исходя из социальных условий, может быть ограничен и снизу. Целью владельца сети является максимизация прибыли в подобных условиях.
Для формальной записи задачи введем необходимые обозначения. Рассматриваемый объект есть неориентированная сеть £ = {и, V}, где и - множество узлов, V - множество дуг. Узлы и дуги будем называть элементами сети. Пронумеруем дуги номерами от 1 до IV], а узлы - от IV + 1| до IV + и|.
Путем на сети £, соединяющим корреспондирующую пару узлов и1, ик будем считать последовательность узлов и дуг, начинающуюся с и1 и заканчивающуюся ик. Двумя независимыми путями на сети £ для каждой корреспондирующей пары узлов назовем два пути, соединяющие эту пару узлов и не имеющие общих промежуточных узлов (а следовательно, и общих линий передачи).
Обозначим через К количество корреспондирующих пар, - множество всевозможных двоек независимых путей, объединяющих к-ю пару узлов, Qk - верхняя граница потребности к-й корреспондирующей пары, Ь - емкость 7-го элемента (линии или узла) сети, Ь7 > 0, ^ - количество свободных каналов в 7-м элементе сети, gk - тариф для предоставления одного канала к-й корреспондирующей паре, к7 - переменная часть себестоимости эксплуатации сети - себестоимость предоставления канала в 7-м элементе сети (линии или узле).
Ограничения на совместное предоставление каналов для всех корреспондирующих пар узлов могут быть записаны в виде
К
^^ ^^ ^^к^£к < Ь 7' к = 1 е £к
7 = 1, \и\ + VI
£ Д < Qk, к =1, К, /к < 0,
(1.1)
(1.2) (1.3)
где — величина потока (количество каналов) для £-й корреспондирующей пары узлов по двум независимым путям sk е при этом аг равно
единице, если 7-й элемент сети входит в один из двух путей sk, и нулю в противном случае. Заметим, что переменные в ограничениях (1.1)—(1.3) изменяются в широком диапазоне от нуля до Qk и при достаточно малых / ограничения (1.1)—(1.3) совместны, т.е. для малых / > 0 поток, удовлетворяющий ограничениям (1.1)—(1.3), существует всегда.
Целевая функция максимизации прибыли владельца сети от предоставления каналов К соединяемым парам запишется следующим образом:
2 =
К
ни - I ь) л
k = 1 sk е Sk г е sk е Sk
тах.
(1.4)
длины линий себестоимости предоставления каналов в элементах сети. В соответствии с построенным маршрутом сформируем столбец коэффициентов матрицы ограничений следующим образом: в компоненты столбца, соответствующие используемым в маршруте элементам сети, поставим единицы; остальные компоненты приравняем нулю. Прибыль владельца сети от предоставления одного канала данной соединяемой паре по сформированному маршруту составит
М + V
С = &
I aгslhг
Совокупность (1.1)—(1.4) — формальная запись задачи максимизации прибыли владельца сети от предоставления каналов К соединяемым парам при заданных тарифах и себестоимости эксплуатации. Задача (1.1)—(1.4) является задачей линейного программирования очень большой размерности как по количеству переменных, так и по числу ограничений. Например, для сети, содержащей 100 узлов, ограничений (1.1)—(1.4) может оказаться несколько тысяч, а переменных Лч — несколько миллионов. Ниже представлен алгоритм для решения поставленной задачи.
2. Алгоритм решения задачи эффективного использования сети. Заменим решение задачи (1.1)—(1.4) решением нескольких последовательно формируемых более простых задач, результат последней из которых даст нам решение исходной задачи (1.1)—(1.4). Первую задачу из указанной последовательности получим, отбросив ограничение (1.2). Рассмотрим задачу (1.1), (1.3), (1.4), которая содержит |М| + \У\ ограничений, и их количество не допускает сокращения. Соответствующая матрица ограничений, тем не менее, не может быть выписана, так как в ней фигурируют пути, количество которых слишком велико, и, кроме того, они могут быть получены только полным перебором, что практически невозможно. Тем не менее, задачу вида (1.1), (1.3), (1.4) решить можно, если использовать закономерности, которым подчиняются элементы матрицы ограничений и целевой функции.
Первоначально в задаче (1.1), (1.3), (1.4) все /ч =
= 0, г = 0, начальный базис составляют слабые переменные и их значения равны емкостям элементов сети. Возьмем одну из связываемых пар и составим для нее маршрут соединения по паре путей кратчайшей суммарной длины, приняв за
Таким образом, в задаче (1.1), (1.3), (1.4) имеем начальный базис и полученный столбец коэффициентов при одном из неизвестных. Этого достаточно для совершения одной итерации симплекс-метода. Последующие итерации производятся со столбцами, формируемыми в соответствии с модифицированным симплекс-методом с генерацией столбцов, описанным, например, в [3—6], который используется в задачах оптимизации на сетях [7—9]. Маршрут соединения строится по двум независимым путям минимальной суммарной длины, в качестве длин элементов сети применяются величины /7
1г = Пг + Ьг ■
Элемент целевой функции искомого столбца с^ вычисляется следующим образом:
М + V
С^ = - I аг5к(Пг + Ь) ■
г = 1
Сформированный столбец р^ перед итерацией должен быть умножен слева на матрицу, обратную текущему базису ВТ
1 о-1 Р^ = Вт Р^.
Итерации проводятся до тех пор, пока имеются столбцы, пригодные для ввода в базис. При наличии отрицательных величин ^ может оказаться затруднительным построение кратчайшего маршрута. В этом случае в базис может быть введен соответствующий столбец из матрицы ВТ . Если таких столбцов уже нет, то задача (1.1), (1.3), (1.4) решена. Ее результат — количество предоставленных каналов соединяемым парам с максимальной прибылью для владельца сети. Если при этом окажется, что выполняется ограничение (1.2), то тем самым решена и задача (1.1)—(1.4).
Рассмотрим случай, когда ограничение (1.2) не выполняется. Это означает, что существуют такие соединяемые пары, которым предоставлено каналов больше их верхнего предела. Напомним, что условия (1.2) были исключены для уменьше-
г = 1
ния количества ограничений. Сформулируем вторую задачу из последовательности задач, в которой количество ограничений будет на единицу больше по сравнению с количеством ограничений в задаче (1.1), (1.3), (1.4).
Из (1.1), (1.3), (1.4) изымем все переменные х, сопутствующие соединяемым парам узлов, для которых в оптимальном решении задачи (1.1), (1.3), (1.4) не выполняются ограничения (1.2), и добавим в (1.1), (1.3), (1.4) переменные х,, , = 1, 2, ..., со столбцами коэффициентов, представляющих суммы коэффициентов тех столбцов, которые соответствуют соединяемым парам, получившим каналов выше верхнего предела. Дополним так преобразованную задачу (1.1), (1.3), (1.4) ограничением
£ х, <£ Qk, (2л)
к
Таблица 1. Характеристики существующей сети
Номер линии Пропускные способности линий, каналы Эксплуатационные издержки за один канал, усл. ед.
1 30 2
2 56 3
3 48 5
4 45 2
5 37 4
6 50 3
7 45 5
8 40 1
9 32 2
10 25 5
11 36 3
12 55 4
13 46 2
14 58 2
15 38 1
где суммирование слева распространяется на введенные переменные, а суммирование справа - на те индексы к, для которых не справедливы ограничения (1.2).
Решим теперь задачу (1.1), (1.3), (1.4), (2.1), в которой соединяемые пары при постановке (1.1),
(1.3), (1.4) получили каналов больше своего верхнего предела, очевидно, наделяются количеством каналов, равным верхнему пределу. При этом, возможно, возникнут другие соединяемые пары с числом каналов, превышающим их верхний предел. Сформируем третью задачу последовательности вида (1.1), (1.3), (1.4), (2.1), пополнив список соединяемых пар, подчиненных ограничению (2.1).
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.