РАЗДЕЛ 2
РЕШЕНИЕ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ НА ОСНОВЕ РАНГОВОГО ПОДХОДА
2.1. Модель решения задачи ЦЛП с БП на основе рангового подхода
Задача линейного (0,1) программирования является формальной моделью широкого
класса задач теории исследования операций, решаемых при управлении сложными
системами. В ней требуется максимизировать (минимизировать) линейную форму
(2.1)
при ограничениях
; (2.2)
Сj і 0; aij і 0; bi > 0; Xj О {0,1}. (2.3)
Рассмотрим суть рангового подхода на примере одномерной задачи ЦЛП с БП.
Поставим в соответствие функционалу и ограничениям
f = c1x1 + c2x2 +...+ cnxn, (2.4)
a11x1 + a12x2 +...+ a1nxnЈb1; (2.5)
__
c1 і c2 і... і cn; a1j > 0; xj О {0,1}; j = (1,n), (2.6)
граф G (рис. Б1.1 приложения Б1), представляющий бинарное дерево всех решений,
число которых равно 2n [104, 106, 107]. Множество X всех векторов размерности
n, все компоненты которых принимают значения {0,1}, составляют множество
возможных значений. Некоторое его подмножество V, все вектора которого
удовлетворяют (2.5), образуют множество допустимых решений. Множество H М V
является множеством оптимальных решений исходной задачи, если для любых
векторов x О H функционал (2.4) достигает своего экстремального значения.
Все множество возможных решений можно разбить на группы векторов, содержащих:
одну компоненту xj = 1 и все остальные, равные 0; две компоненты xj = 1 и все
возможные их сочетания по 2, а остальные, равные 0; три компоненты xj = 1 и все
возможные их сочетания и т.д. n-компонент xj = 1. Если обозначить подмножества
векторов этих групп через mr , тогда множество всех возможных решений можно
рассматривать как объединение подмножеств mr
. (2.7)
Как показано в [106, 107], по графу G можно построить граф G' (рис. Б1.2), в
котором множество путей ранга r (ранг пути –число ребер, образующих путь)
соответствует группам подмножеств, описываемых соотношением (2.7). Для этого
вершину s соединим направленными ребрами с вершинами 1, 2, ... , n и т.д.;
вершину i соединяем с вершинами i + 1, ..., n. В последнюю вершину n входят
ребра, направленные из всех вершин, и ни одно ребро из этой вершины не
выходит.
Дерево путей DD графа G' из вершины s строится следующим образом [107]: на
нулевом ярусе расположим вершину s, на первом ярусе разместим все вершины графа
G', имеющие связь с вершиной s и соединим их с s (при этом образовалось
подмножество путей ранга r = 1). Во втором ярусе разместятся все вершины,
имеющие связь с вершинами первого яруса, без вершины с номером 1 и соединим их
с вершинами первого яруса (образованы все пути ранга r = 2) и т.д. до тех пор,
пока в последнем не останется одна вершина n (рис. Б1.3). В этом графе
DD каждому ребру, входящему в вершину j, соответствует два веса: вес сj, равный
коэффициенту при xj в функционале (2.4), и вес a1j, равный коэффициенту при xj
в ограничении (2.5). Путь msj в графе DD из вершины s в вершину j
характеризуется двумя длинами: dc(msj) – длиной повесам функционала и
da(msj)1 – длина пути по весам ограничений. Множество путей msr(j) в графе DD
к вершинам j, расположенным на ярусах от вершины s, можно представить в виде
, (2.8)
где mrsj – множество путей в графе DD от вершины s к вершинам j, расположенным
на r?х ярусах графа DD (ранг пути mrsjОmrsj определяется числом ребер,
образующих этот путь). Следует иметь ввиду, что множество путей msj r=k в графе
DD соответствует множеству векторов {x1, x2, ... , xn}, содержащих k единиц
(рис. Б1.4).
Следовательно, , т.е. каждому пути в множестве msjr соответствует некоторый
вектор (x1 x2 ... xn). Из (2.7) следует
.
Таким образом, граф DD представляет собой упорядоченный по рангам эквивалент
n?мерного единичного куба Bn , в котором пути msjrО msjr соответствуют вершинам
Bn. Длина каждого пути по весу функционала определяет значение функционала
(2.4) в вершинах единичного куба Bn. Длина по весам ограничений (2.5)
определяет соответствует ли данная вершина Bn ограничениям (2.5), т.е.
принадлежит вершина n – мерного единичного куба Bn гиперплоскости (2.5). Если
da(msj)1 Ј b1, то вершина принадлежит гиперплоскости (2.5) и будем говорить,
что путь msj удовлетворяет свойству n. Если da(msj)1 > b1, то вершина n?мерного
куба, соотвествующая пути msj, не принадлежит гиперплоскости (2.5), а путь msj
считаем неудовлетворяющим свойству n. Оптимальному решению задачи (2.4)-(2.6) в
DD соответствует самый длинный путь по весам функционала, удовлетворяющий
свойству n.
В случае m?мерной задачи ребрам, входящим в вершины графа DD, кроме веса сj
функционала, соответствует m весов aij ограничений, а путь msj характеризуется
длинами:
dc(msj) – длиной по весам функционала;
da(msj) – длинами по весам ограничений.
В основу построения приближенных и точных алгоритмов решения задач ЦЛП с БП
положен принцип оптимизации по направлению в дискретном пространстве состояний,
заданном графом DD. Представление n?мерного единичного куба в виде графа
DD позволяет разбить множество всех путей графа DD из вершины s на W локальных
областей, которое не превышает величину n2/2, поскольку число вершин в графе
DD определяется суммой чисел натурального ряда
(2.9)
причем W?области в графе DD упорядочены по рангам и пути следующего ранга могут
быть получены на основе путей предыдущего ранга за счет подсоединения к ним
ребра (j, p) в графе DD
(2.10)
Пусть заданы правила {Lw} отсечений путей msjr в множествах msjr. Тогда, если в
множествах содержатся пути, удовлетворяющие свойству n и правилам {
- Київ+380960830922