РАЗДЕЛ 2
РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ РЕШЕНИЯ А, - В, - С ЗАДАЧ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ В АСУ СКЛАДАМИ СУПЕРМАРКЕТОВ
2.1. Модель решения задачи А на основе рангового подхода
Формальной моделью научно-технической задачи (1.7 - 1.10) является m-мерная задача 0,1-рюкзак, которая в общем случае может быть представлена в следующем виде
(2.1)
при ограничениях
(2.2)
В основе рангового подхода к решению задач дискретной оптимизации лежит представление n-мерного единичного куба Вn в виде графа G? [81]. На рис. 2.1 изображен граф G? для n = 4.
Геометрически вершина k графа G? ранга r- это множество векторов (x1,x2,...,xk,...,xn), у которых xk = 1, а на позициях от 1 до k находится r единиц (рис. 2.2). Ребру, входящему в вершину k графа G? , соответствует единичный вектор (0,
0, ..., 0, 1, 0,...0) в n-мерном единичном кубе Bn с единицей в k-той позиции.
Тогда, пути ранга r в графе G? соответствует вектор , равный сумме единичных векторов ребер, по которым он достиг вершину j ранга r, начиная с вершины s.
Например, пути соответствует вектор , который образуется суммой нулевого вектора {0000} и единичных векторов = {0100}, = ={0001},т.е. = {0000} + {0100} + {0001} = {0101).
Пусть в графе G? каждому ребру, входящему в вершину j, соответствует m + 1 вес: вес сj, равный коэффициенту при xj в функционале (2.1), и m весов аij, равных коэффициентам при xij в ограничениях (2.2). Тогда, путь в
графе G? из вершины s в вершину j характеризуется m + 1 длинами: -
длиной по весам функционала и - длинами по весам ограничений. Множество путей в графе G? к вершинам j, расположенным на ярусах от вершины s, можно представить в виде
(2.3)
где - множество путей в графе G? от вершины s к вершинам j, расположенным на r-х ярусах графа G? (ранг пути ? определяется числом ребер, образующих этот путь). Следует иметь в виду, что множество путей в графе G? соответствует множеству векторов , содержащих k единиц. Следовательно, т.е. каждому пути в множестве соответствует некоторый вектор . Из (2.3) следует
(2.4)
Таким образом, граф G? представляет собой упорядоченный по рангам эквивалент n-мерного единичного куба Bn, в котором пути ? соответствуют вершинам Bn (2.4). Длина каждого пути по весу функционала определяет значение функционала (2.1) в вершинах единичного куба Bn. Длина по весам ограничений определяет, соответствует ли данная вершина Bn ограничениям (2.2), т.е. принадлежит вершина n-мерного единичного куба Bn соответствующей гиперплоскости (2.2). Если то вершина принадлежит соответствующей гиперплоскости (2.2) и будем говорить, что путь удовлетворяет свойству ?. Если то вершина n-мерного куба, соответствующая пути , не принадлежит ни одной гиперплоскости (2.2), а путь считаем не удовлетворяю-
щим свойству ?.
Оптимальному решению задачи (2.1) - (2.2) в G? соответствует самый длинный путь по весам функционала, удовлетворяющий свойству ?.
В основе математической модели рангового подхода для построения алгоритмов решения задач ЦЛП с БП положен принцип оптимизации по направлению в дискретном пространстве состояний, заданном графом G? [81]. Представление n-мерного единичного куба в виде графа G? позволяет разбить множество всех путей графа G? из нулевой вершины s на ? локальных областей, где не превышает величину , поскольку число вершин в графе G? определяется суммой чисел натурального ряда
,
причем ?-области в графе G? упорядочены по рангам и пути следующего ранга могут быть получены на основе путей предыдущего ранга за счет подсоединения к ним ребра (j,p) в графе G?
. (2.5)
Пусть заданы некоторые правила отсечений {Lw} путей в множествах . Тогда, если в множествах содержатся пути, удовлетворяющие свойству ? и правилам {Lw}, то под оптимизацией по направлению в графе G? к вершине p будем понимать формирование множеств следующего ранга, которые получаются за счет выделения в путей, подсоединение к которым ребра (j,p) позволит в множестве получить пути, удовлетворяющие правилам {Lw} на основе следующего рекуррентного соотношения:
(2.6)
где - путь из вершины s графа G? в вершину p, проходящий через промежуточную вершину j и удовлетворяющий правилам {Lw}, т.е. получаемый за счет подсоединения к пути ребра (j,p), если такое соединение не противоречит правилам {Lw}. В дальнейшем для упрощения изложения, если путь удовлетворяет правилам {Lw}, то будем говорить, что он удовлетворяет и свойству ?.
Как показано в [81], для решения задачи (2.1) - (2.2), используя правила {Lw} и оптимизацию по направлению (2.5) - (2.6), предложена обобщенная процедура А0, позволяющая формировать множества локальных экстремумов ? и выделять среди них глобальный. Описание обобщенной процедуры более подробно будет рассмотрено при разработке алгоритмов в следующем разделе.
Таким образом, из представленной математической модели n-мерного единичного куба Bn в виде графа G? и сформулированного принципа оптимизации по направлению на основе рангового подхода, вытекают следующие задачи:
1. Определения стратегий отсечений {Lw} неперспективных путей в множествах , приводящих к приближенным и точным решениям задачи ЦЛП с БП.
2. Построения приближенных и точных алгоритмов на основе выбранных правил отсечений {Lw} для решения многомерных задач ЦЛП с БП.
2.2. Организация вычислений при решении задачи А
В работах [71, 81, 84] рассмотрены различные алгоритмы решения задачи (2.1 - 2.2). Среди алгоритмов, предложенных в [71], наиболее эффективными можно считать многоэтапные алгоритмы, позволяющ