ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 3, с. 71-85
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 519.854.33
ОПТИМИЗАЦИЯ СЕТИ И ЗАДАЧИ С ЗАЦЕПЛЯЮЩИМИСЯ ПЕРЕМЕННЫМИ
© 2014 г. А. С. Есенков, Д. И. Кузовлев, В. Ю. Леонов, А. П. Тизик, В. И. Цурков
Москва, ВЦ РАН Поступила в редакцию 20.12.13 г., после доработки 27.01.14 г.
Рассматриваются модели сетевой оптимизации. Постановки имеют большое количество переменных и связей. Для решения используются декомпозиционные подходы. В конкретных ситуациях промежуточные задачи алгоритмов имеют вид задачи о ранце. В случае лестничной структуры ограничений удается построить эффективный алгоритм. Конструкции последовательного пересчета коэффициентов функционала этого алгоритма распространяются для других задач с унимодулярными матрицами, в частности для транспортных задач различного вида.
БО1: 10.7868/8000233881403007Х
Введение. Постановки из области оптимизации на сетях [1—7], как правило, имеют большое количество переменных и ограничений. Одним из методов решения является сведение к линейному или нелинейному программированию с учетом целочисленности некоторых переменных. Для задач применяются методы декомпозиции Данцига—Вулфа (процедура генерации столбцов), разделение переменных Бендерса, алгоритмы блочного целочисленного программирования и т.д. [8—11].
При использовании указанных алгоритмов возникают специфические задачи. При наличии исходных бинарных переменных, которые означают, следует ли прокладывать тот или иной канал, решается целочисленная задача с булевыми переменными, которая в литературе известна как многомерная задача о ранце. При значительных размерностях ее решение становится весьма трудоемким. В специальном случае лестничной структуры ограничений удается построить эффективный алгоритм. Конструкции этого алгоритма применяются для разработки метода решения транспортных задач различных типов.
1. Задача развития сети. Имеется неориентированная сеть [12], заданная своим множеством узлов и линий, которые соединяют некоторые пары узлов. Для каждой линии установлена ее пропускная способность (количество каналов). Для некоторого подмножества пар узлов данной сети задана потребность в каналах для потока между ними. Различные пары узлов обмениваются потоками различных продуктов. Таким образом речь идет о многопродуктовом потоке в сети. Заранее неизвестно, реализуем ли в сети заявленный многопродуктовый поток. Ставим задачу максимизировать коэффициент удовлетворения заявленного многопродуктового потока на существующей сети. Если этот коэффициент больше или равен единице в оптимальном решении, то требуемый многопродуктовый поток может быть реализован на сети. В противном случае ставим задачу найти места строительства новых линий и их пропускные способности затем, чтобы добавление этих линий позволило реализовать заявленный многопродуктовый поток при минимуме ресурсов на строительство новых линий.
Формализация сводится к следующей линейной частично целочисленной задаче:
т
I=1 ]=1
ь
^< Ъ, + ^йуУу, I = 1 т,
I=1 1 =1
ь
^> 1, > 0.
I = 1
Здесь I — номер элемента сети (узла и линии); количество элементов в сети равно т; индексу — номер варианта прохождения совокупного продукта через 1-й элемент сети; 81 — количество этих вариантов; коэффициент а— необходимое количество каналов в 1-м элементе при 1-м варианте прохождения потока; Ь — количество этих вариантов; у у = {0,1} принимает нулевое значение, если в 1-м элементе не добавляется канал, и единичное, если добавляется; ёу — количество добавляемых каналов; ^ — список вариантов увеличенных каналов в 1-м элементе; Су — стоимость увеличения канала 1-й линииу-го варианта; — неизвестная величина, являющаяся коэффициентом использования у-го варианта пропускаемого через сеть потока; Ь1 — количество каналов в 1-м элементе сети.
Специфика частично целочисленной задачи — отсутствие непрерывных переменных в целевой функции и чрезвычайно большое количество непрерывных переменных в ограничениях.
При ограниченных капиталовложениях математическая постановка такова. Владелец сети предоставляет потребителям (соединяемым парам узлов) каналы, взимая тарифную плату за каждый канал. Тариф различен для различных пар узлов. Себестоимость эксплуатации одного канала в каждой линии передачи также может быть разной. Рыночный спрос на предоставление каналов между парами узлов ограничен сверху. У владельца для развития сети имеется ограниченная сумма средств. На эти средства могут быть построены новые линии, переоборудованы узлы. Целью владельца является такое использование имеющихся средств, которое позволит на модернизированной сети получить максимальную прибыль от предоставления каналов.
Итак, имеем оптимизационную задачу, содержащую как большое количество непрерывных переменных, так и большое количество целочисленных переменных, и поэтому она не может быть решена классическим подходом с помощью последовательности симплекс-метод — метод ветвей и границ и т.д.
2. Задача о ранце с лестничной структурой ограничений. В общем случае многомерная задача о ранце, к которой может быть сведена чисто целочисленная задача в процедуре разделения Бен-дерса при решении задачи развития сети, решается методом ветвей и границ, что уже при размерностях несколько десятков переменных и ограничений приводит к практически неосуществимым объемам вычислений.
Далее кратко излагается эффективный метод точного решения многомерных задач о ранце для одного частного вида матриц ограничений, состоящих из 0 и 1 [13]. Рассмотрим многомерную задачу о ранце:
£ ауХу < Ъ, ' = 1, т, (2.1)
у=1
п
£ СуХу ^ тах, ау > 0, Ъ > 0, с у > 0,
у=1
' = 1, т; у = 1, п; Ху принимают значения 1 или 0.
Те о р е м а 1. Пусть существуют такие X'у > 0, что
(2.2)
£ X 'у = 1 для у = 1, п (2.3)
'=1
и оптимальные решения т задач
£Х'уСуХу ^ тах, (2.4)
у=1
£ ауХу < Ъ1 (2.5)
у=1
п
т
т
при всех i = 1,m совпадают. Тогда оптимальное решение задачи (2.1), (2.2) может быть составлено из оптимальных решений задач (2.4), (2.5). Доказательство дается в [13].
Легко привести примеры, доказывающие, что не всякая многомерная задача о ранце может быть так решена. Рассмотрим многомерную задачу о ранце следующей специальной лестничной структуры:
n
ЕCjXj ^ max, j=1
Ji
Е X * bb
j=1
J2
Е X < h, (2.6)
j=Ji^./i
Е
xj < К
j = Jm-1-jm-1
Ь, I = 1, т — целые, е] > 0,у = 1,.
Множество индексов от] = 1, п разбивается на т пересекающихся подмножеств. Первое подмножество имеет вид 1, 2, ..., /1; второе подмножество начинается от 11 - 1 до J1, где]х — количество общих переменных первого и второго ограничений. При этом 1 < 11,1 > 0. Второе множество начинается от /2 - у2 до Jъ, где у2 < /3 - (/2 - у2) и у2 > 0. Дальнейшее построение множеств индексов выполняется аналогично.
Решение задачи (2.6) может быть представлено в соответствии с теоремой 1. Если рассматриваемая задача одномерна, т.е. содержит одно ограничение, то ее решение может быть получено просто выбором тахху- в количестве Ь1, которые имеют наибольшие коэффициенты ^ в целевой функции.
Оптимальное решение двумерной задачи о ранце обладает следующим очевидным свойством. Если некоторая переменная, общая для обоих ограничений, равна единице, то коэффициент целевой функции при ней больше или равен сумме двух любых коэффициентов при переменных, равных нулю и взятых по одному в каждом ограничении вне общей части. И наоборот, сумма коэффициентов при переменных, равных единице и взятых по одному вне общей части, больше или равна наибольшему коэффициенту при переменных общей части и равных нулю в оптимальном решении. Из этого свойства вытекает как простой алгоритм построения оптимального решения, так и еще одно свойство, важное для решения задач о ранце с коэффициентами 1—0 при большем количестве ограничений. Это свойство состоит в следующем. Двумерная задача о ранце может быть представлена в виде совокупности двух задач о ранце, с одним ограничением каждая, объединения оптимальных решений, для которых есть оптимальное решение исходной двумерной задачи.
Алгоритм решения лестничной задачи с тремя ограничениями выглядит следующим образом. Решается задача с двумя первыми ограничениями. Производится разбиение ее на две одномерные задачи, объединение оптимальных решений которых совпадает с оптимальным решением двумерной задачи. Далее решается двумерная задача со вторым и третьим ограничениями (часть коэффициентов целевой функции изменены при разбиении предыдущей задачи на одномерные). Эта двумерная задача также разбивается на две одномерные задачи. Сравнение оптимального решения одномерной задачи со вторым ограничением после решения двумерной задачи с первым и вторым ограничениями с оптимальным решением этой же задачи после решения двумерной задачи со вторым и третьим ограничениями показывает, что список переменных, равных единице среди переменных, общих для второго и третьего ограничений, во втором случае будет не длиннее, чем в первом случае (на эти переменные были наложены дополнительные ограничения). Этот факт с неизбежностью отразится на состоянии одномерной задачи с этим вторым ограничением. Коэффициенты целевой функции при переменных, общих для второго и третьего ограничений, будут не превосходить этих же коэффициентов в этой же одномерной задаче после
решения двумерной задачи с первым и вторым ограничениями. Отсюда следует, что во второй раз решенная задача с первым и вторым ограничениями удлинит список единиц среди переменных, общих для первого и второго ограничений. Следовательно, коэффициенты целевой функции при переменных, общих для первого и второго ограничений в одномерной задаче с первым ограничением увеличатся (так как коэффициенты целевой функции при переменных, присутствующих лишь в первом ограничении, не меняются), а у одномерной задачи со вторым ограничением — соответственно уменьшатся. Процесс монотонен, целочислен, следовательно, конечен. В [13] детально описан переход к четырем, пяти и т.д. ограничениям. Важно, что идеи последовательного решения двумерных задач с зацеплениями будут использоваться в дальнейшем п
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.