6.2.3.3. Алгоритм устранения нарушения ограничений

Так как соблюдение ограничений на объем сегментов (6.2.12) имеет больший приоритет, чем оптимизация значений критерия, то в этом случае критерием выбора операции и сегмента является только нарушение ограничений. Алгоритм устранения нарушений состоит в следующем:

1. Определяется номер сегмента, в котором нарушается ограничение:

Если таких сегментов несколько, то все они, кроме одного исключаются из рассмотрения до тех пор, пока не будет устранено нарушение (6.2.51).

2. Среди оставшихся сегментов, удовлетворяющих ограни чению, ищется сегмент с максимальным «запасом»:

3. В сегменте определяется вершина, вес которой максимально приближается снизу к запасу (6.2.52), т. е. решается задача

Здесь возможны два варианта. Если такая вершина находится в то с ней производится операция первого рода (6.2.43), а далее — переход к п. 1. Если же такой вершины не найдется, то следует обращаться к операции второго рода.

4. Для этого из всех оставшихся сегментов случайно выби рается один с вероятностью

(кликните для просмотра скана)

5. В сегменте случайно выбирается одна вершина , а в сегменте ищется вершина, обладающая свойством

Если такая вершина в найдется, то производится операция второго рода вида (6.2.47). При этом в случае

нарушение в устраняется полностью, далее — по . В противном случае нарушение уменьшается и следует обратиться к При этом новую вершину целесообразно исключить из случайного «розыгрыша».

Если же в не найдется вершины, удовлетворяющей условию (6.2.55), то следует обратиться к исключив из рассмотрения

Указанное исключение вершин в конце концов исчерпывает сегмент что заставляет обращаться к т. е. к другому сегменту, исключая из дальнейшей «игры».

Блок-схема этого алгоритма показана на рис. 6.2.3.