Синтез структуры клиентской сети

Как было показано в п. 4.1, процесс синтеза топологической структуры АСДП можно рассматривать, как сумму задач синтеза топологических структур клиентской сети (КС) и сети доставки (СД) АСДП.

 Поэтому, на основании приведенной выше общей постановки задачи синтеза топологической структуры системы, уточним ее формулировку применительно к клиентской сети:

Пусть X = { x_i }, i =  - множество абонентов рассматриваемой КС (х₁ - пункт, где расположен ЛПС);  - вектор интенсивностей потоков доставляемых заказов λ₁, передаваемых от ЛПС к клиенту x_i, i = ; С_э = = { c _{э j} } - множество эффективных пропускных способностей ПСв, j = ; В = { b_j } - множество относительных затрат на оборудование и штат работников, необходимых для обеспечения функционирования ПСв, с эффективными пропускными способностями c _{э j}, j = ; n ₀ – общее число клиентов К C; m ₁ - число различных технологий реальных и средств используемых в создаваемой АСДП.

Будем считать, что структура КС ищется в классе двухуровневых иерархических структур [16, 5]. При этом на нулевом уровне располагается ЦС (виртуальная ЦС), на первом - ЛПС, на втором - кленты. Считаем, что задано множество Y = { y_j }, j =  мест возможного размещения ПС, .

Будем считать, что затраты на развёртку ПС постоянны и не зависят от структуры АСДП, причем их доля в общих затратах является незначительной по сравнению с затратами на штат сотрудников, вовлечённых в процесс сборки и доставки заказа [13]. Поэтому при формировании функции цели они не учитываются.

Введем следующие переменные:

где , .

Ограничения рассматриваемой задачи имеют следующий вид:

1) Каждый клиент  может быть определён только к одному ЛПС, т. е. ;

2) Матрица расстояний || L || задает расстояния между узлами КС посредством имеющихся в наличии на ПСв свободных штатных и технических ресурсов, необходимых для осуществления доставки заказа клиенту. Т. е. среди элементов l_ij могут встретиться l_ij = ∞, и для элементов матрицы || L || неравенство треугольников может не выполняться;

3) КС должны обеспечивать среднее время доставки заказа из ЛПС клиенту, равное Т ₁;

4) В рамках КС реализуется так же ПС.

С учетом введенного выше критерия сравнения вариантов топологической структуры АСДП задача синтеза оптимальной топологической структуры КС имеет вид

,                  (4.23)

где l_ij - элементы матрицы || L ||; R ' _{i 1} – загруженность персонала и технических средств, занятых доставкой заказа между ЛПС и клиентом x_i; R ' _{i 2} - загрузка ПСв между клиентом x_i и ЦС (ПС более высокого уровня) y_j.

Вычисление параметров R ' _{i 1} и R ' _{i 2} осуществляется следующим образом:

;                                       (4.24)

, если , ;                       (4.25)

;                                      (4.26)

, если , .     (4.27)

Параметр β _i определяется при заданных требованиях к вероятности того, что время доставки превысит допустимое. Значения пропускных способностей ПСв c _{э i} и соответствующие им значения b_i выбираются по вычисленным значениям С _{i 1} и С _{i 2}. При этом выбираемое значение c _{э i} должно быть ближайшим большим, чем С _{i 1} или С _{i 2}, т. е. должны выполняться условия

С _{i 1} ≤ c _{э i}, С _{i 2} ≤ c _{э i},                                   (4.28)

Если , а , то  и для этого ПС

.        (4.29)

При одинаковых требованиях к среднему времени передачи заказа β _j = β, j = .

Таким образом, задача (4.23) - (4.29) сводится к определению максимального значения функционала Ф следующего вида:

,                   (4.30)

где                  ; 

; ;

,

 

Для решения задачи (4.30) разработан алгоритм, реализующий метод «ветвей и границ» [14] с учетом специфики решаемой задачи. Новые ветви дерева ветвлений, а следовательно, и новые задачи в основном списке задач на каждом шаге решения формируются следующим образом.

На текущем шаге решения задачи будем считать заданным пункт , в котором предполагается размещение ПС. По результатам решения задачи на предшествующих шагах формируется множество клиентов X ' X, заказы которых уже обрабатываются ЛПС непосредственно, т. е. , если z_{i 1} = 1, i = . Параметры, описывающие множество X ' и y_j, составляют исходные данные для решения задачи оптимизации на текущем шаге.

Определим границы возможного изменения значения Ф _j на текущем шаге доставки заказа. Нижняя граница Ф _{j mln} = 0 соответствует случаю, когда на текущем шаге решения задачи все z_ij = 0, . Значение верхней границы Ф _{j max} определяется решением задачи

,     (4.31)

где значения параметров R ' _{i 1}, R ' _{i 2}, R ' _{j 1}, R ' _{j 2} определяются соответственно с (4.45) Ф _j > 0, .

Рассмотрим возможность точного решения задачи (4.19). Введем следующие обозначения:

, , , тогда

. (4.32)

 

В (4.20) при фиксированном значении j имеем, что A_ij = const, D_j = const.

Значение выражения:

.          (4.33)

зависит от числа z_ij = 1.

Определим границы изменения параметров, входящих в (4.33). Можно показать, что

,

где   

                                 ,

.

 

Значениями параметров S ₁ и S ₂ однозначно определяется область возможных изменений значений параметров β _{j 2}, c _{э j 2}, внутри которой они изменяются дискретно. Таким образом, имеем, что

c _{э j 2 min} ≤ c _{э j 2}≤ c _{э j 2 max},                    (4.34)

где c _{э j 2 min} и c _{э j 2 max} - ближайшие большие, чем S ₁ и S ₂ соответственно значения эффективных пропускных способностей реальных ПСв и служб, вовлечённых в доставке..

Решение задачи (4.45) может привести к выбору любого значения c _{э j 2}, удовлетворяющего ограничениям (4.34).

После соответствующих преобразований формулы (4.33) получим:

,                            (4.35)

где

, .

Значение параметра Е’ при фиксированном c _{э j 2}, удовлетворяющем условию (4.34), не зависит от z_ij. Параметр F ’ зависит только от значения  и не зависит от того, какие именно z_ij = 1.

Пусть

,                                              (4.36)

тогда значение параметра G ' должно удовлетворять ограничению

0 ≤ G ' ≤ n ₂ - 2.                                (4.37)

При фиксированном G ', удовлетворяющем условию (4.34), задача (4.45) сводится к определению максимума функции

                       (4.38)

при выполнении ограничения

,                                  (4.39)

где

.                               (4.40)

При фиксированных значениях c _{э j 2} и G ' значение параметра Н' = const.

Задача (4.36) - (4.39) является задачей целочисленного программирования с одним линейным ограничением. Для ее решения используем аддитивный алгоритм, обеспечивающий получение точного решения за конечное число шагов [15]. Условия целочисленности в данном случае сведены к .

Указанный алгоритм является наиболее эффективным для решения поставленной задачи, так как использование условия (4.28) приводит к тому, что вычисления ограничиваются операциями сложения (вычитания). Это определяет простоту реализации компьютерного моделирования алгоритма.

Схема аддитивного алгоритма решения задачи (4.36) - (4.39) приведена на рис. 3.17, где использованы следующие обозначения: , ; ; Ф⁰ - целевая функция, соответствующая оптимальному варианту;  - целочисленные переменные, соответствующие оптимальному варианту, ; Ф, z_i - целевая функция и целочисленные переменные на текущем шаге решения задачи соответственно, .

Набор исходных данных, используемых в алгоритме, включает в себя , , H ', Н ₁, а результаты, получаемые в процессе его выполнения, представлены значением Ф⁰ и набором , , соответствующих решению задачи (4.37) - (4.39).

Решим задачу (4.37) - (4.39) n ₀ - 2 раз для значений G ', удовлетворяющих условию (4.36). Выберем так же среди целевых функций ту, в которой значение Ф _j будет максимально. Это позволит нам получить набор z_ij = 1, соответствующих оптимальному решению при фиксированном значении параметра c _{э j 2}. При этом учитываются только те решения, для которых Ф _j > 0.

Просматривая последовательно все значения F ’, определяемые из выражения (4.34), и сравнивая получаемые при этом решения с наилучшими, в конечном итоге фиксируем множество z_ij = 1, соответствующее решению задачи (4.45). Если считать, что число возможных значений E ’, задаваемых ограничением (4.34), равно m ₁ то решение задачи (4.37) требует m ₁(n ₀ - 2) итераций решения задачи (4.37) - (4.28).

В тех случаях, когда значением β при определении пропускных способностей КСв можно пренебречь, решение задачи (4.37) существенно упростится. При β = 1 имеем

C_{i 1} = C_{i 2}, R’_{i 1} = R’_{i 2}, ;                          (4.41)

A = R’_{i 1} (1/ l_ij – 1/ l_{i 1}), i ≠ j, ;                 (4.42)

;                        (4.43)

;                                  (4.44)

; F ’ = 1.                         (4.45)

Рис. 4.6 Алгоритм решения задачи 4.36-4.38

В этом случае задача (4.36) - (4.38) сводится к следующей задаче целочисленного программирования:

                   (4.44)

при выполнении условия:

                                  (4.45)

и условиях целочисленности:

                                   (4.46)

где .

В данном случае решение задачи (4.37) сводится к m ₁-кратному решению задачи (4.40) - (4.45), т. е. требует в n ₀ - 2 раза меньше итераций, чем решение задачи (4.38) с учетом значения параметра β.

 

Рис. 4.7 Алгоритм решения задачи 4.40-4.50

Алгоритм решения задачи (4.49), схема которого приведена на рис. 4.7, он включает в себя описанный выше аддитивный алгоритм. В качестве исходных данных, используемых в алгоритме решения задачи (3.38), выступают:

n ₀ - общее число клиентов АСДП;

j - номер клиента y_j относящегося к данному ЛПС;

Т ₁ - среднее время задержки доставки заказа, установленное для СД;

μ - параметр распределения объёма заказов;

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

λ _i - интенсивности потоков доставляемых заказов;

l_pk -расстояния между абонентами и ЛПС;

c _{э k}, b_k - пропускные способности и затраты на КС соответственно, k =, где n1 - число существующих методов доставки, включающих в себя некие особые условия (рефрижератор, перевозка хрупких грузов и пр.).

 

На основании описанного набора исходных данных:

1.   Блок 1 алгоритма (см. рис. 4.7) предусматривает определение параметров R ' _{i 1}, R ' _{i 2}, A_ij в соответствии c выражениями, приведенными в данном параграфе;

2.   В блоке 2 определяются границы изменения параметра в соответствии с ограничением (4.37);

3.   В блоках 3 и 4 происходит формирование начальных значений переменных F ' _opt и , , описывающих оптимальное решение задачи;

Блоки 5-11 реализуют непосредственно процесс решения задачи, который включает в себя:

4. Задание начального значения c _{э j 2} (блок 5);

5. Подготовку исходных данных и решение задачи (4.3) - (4.38) с использованием аддитивного алгоритма (блок 6);

6.  Формирование оптимального решения по результатам текущего и предшествующих шагов (блоки 17 - 9);

7.  Определение значения для следующего шага решения задачи и момента окончания процесса решения (блоки 10, 11);

8. В блоке 12 фиксируются результаты, соответствующие по­лученному оптимальному решению.

В программной реализации алгоритма для решения задачи синтеза оптимальной топологической структуры АСДП алгоритмы, представленные на рис. 4.17 и 4.8, оформлены в виде процедур.

Параметр Ф _j, значения которого удовлетворяют ограничениям 0 ≤ Ф _j ≤ Ф _{j max} (4.32), определяет новые задачи, вводимые в основной список на текущем шаге решения.

Множество значений параметра Ф _j, удовлетворяющее ограничениям (4.32), и соответствующие им наборы переменных z_ij,  формируются в результате решения задачи (4.37) - (4.39) для значений c _{э j 2}, удовлетворяющих условию (4. 28).

В исходных данных задач, водимых в основной список на текущем шаге, будут исключены абонент y_j, а также абоненты x_i, для которых на текущем шаге решения задачи переменная z_ij = 1.

Условия, ограничивающие процесс ветвлений, имеют вид

Ф _{j max} = 0, Х’ = 0, Y ’ = 0,                               (4.46)

где Y ' - множество возможных мест расположения УК на текущем шаге решения задачи. Выполнение хотя бы одного из условий (4.46) свидетельствует о том, что процесс ветвлений в данном направлении закончен.

С учетом вышеизложенного на 1-м шаге решения задачи (4.32) должны выполняться следующие операции:

1) Если основной список пуст, то перейти к п. 18, иначе - к п. 2;

2) Выбор задачи из основного списка;

3) Формирование множеств Y ’ и Х';

4) Исключение рассматриваемой задачи из основного списка;

5) Если Y ’ = 0 или X ' = 0, то перейти к п. 6, иначе к п. 8;

6) Фиксация решения. Сравнение решения с наилучшим, из полученных на предшествующих шагах, с целью формирования оптимального решения;

7) Переход к п. 1;

8) Выбирается ;

9) Формируются исходные данные для решения задачи (4.19) на i -м шаге;

10)Определяется множество значений { c _{э j} }, удовлетворяющих (4.22);

11)Решение задачи (4.19);

12)Если Ф _{j max} ≤ 0, то перейти к п. 6, иначе к п. 13;

13)Выбрать c _{э j} из множества { c _{э j} };

14)Решение задачи (4.26) - (4.28);

15)Если Ф _j > 0, то перейти, к п. 16, иначе к п. 117;

16)Внести новую задачу в основной список;

17)Если просмотрены все значения c _{э j} { c _{э j} }, то перейти к п. 1, иначе - к п. 13;

18)Вывод результатов, соответствующих оптимальному решению.

 

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

В реализации предложенного алгоритма для упрощения процесса выбора задачи из основного списка на каждом шаге формируется только одна новая задача, которая и решается на следующем шаге. Остальные задачи перед их решением возобновляются по специальным ключевым параметрам, введенным для их описания. Для уменьшения затрат реального времени на решение задачи (4.18) в алгоритме могут быть сделаны несущественные изменения, позволяющие получать приближённо-оптимальные решения [16]. Эти изменения относятся к процедуре введения новых задач в основной список и сводятся к тому, что на каждом шаге решения задачи (4.32) в основной список вводится только одна задача, соответствующая Ф _{j max}. Получаемое в этом случае решение не будет отличаться от оптимального в том случае, когда множества x_j, включающие в себя клиентов, заказ которых уже обрабатывается ЛПС через y_j и соответствующих Ф _{j max}, не будут пересекаться для всех , т. е. .

Если в постановке задачи синтеза КС положить R ' _{i 2} = R ' _{i 1} = 1, c _{э i} = b_i = 1, , то в этом случае задача сводится к поиску кратчайшей связывающей сети с максимальным числом переменных участков, равным двум. Алгоритмы построения кратчайшей сети без дополнительных точек основаны на принципах, сформулированных Р. Примом в работе [6].