About possibility of reduction of sort out in Balash's algorithm.pdf Широкий класс задач дискретной математики сводится к анализу и решению систем нелинейных уравнений. Известны методы сведения этих систем [1, 2] к системам линейных ограничений вида aiixi +-----+ ai„x„ ^ bi, . (1) amixi + ■ ■ ■ + amnxn ^ bm, где aj-, b — целые числа; xi G {0,1}, i = 1,..., m, j = 1,..., n. Для нахождения решения (1) можно использовать как методы, работающие в действительной области, так и методы, позволяющие искать целочисленное решение [2-4]. Одним из таких алгоритмов является алгоритм Балаша, который предназначен для решения задач целочисленного программирования с булевыми переменными [1, 3, 5]. Для изложения алгоритма определим невязку системы (1) формулой Mx) = Е P(x,Li^ biS "ij Xj >0 j где x = (xi,...,xn); p(x, Li) —расстояние от вершины n-мерного куба x до плоскости Li, задаваемой i-м уравнением системы. Невязка ^(x) характеризует близость точки x к невыполнившимся неравенствам. С геометрической точки зрения неравенства системы (1) задают разделяющие плоскости в n-мерном пространстве и введённая невязка представляет собой сумму расстояний от вершины x до отсекающих её плоскостей. Алгоритм Балаша является локальным детерминированным траекторным алгоритмом. В качестве начального приближения x0 берётся вектор (0,... , 0). В процессе поиска решения опробуются ближайшие к текущему векторы, на них вычисляется значение невязки системы, и следующим текущим становится вектор, на котором значение невязки минимально. Процесс продолжается до тех пор, пока не получим решение (нулевую невязку) или не попадём в тупиковую точку. Тупиковая точка характеризуется тем, что опробование всех векторов, отличающихся от полученного на предыдущем шаге одной ненулевой координатой, не приводит к уменьшению невязки. Существует несколько стратегий выхода из тупиковых точек, каждая из которых в конечном итоге приводит к увеличению числа опробуемых векторов и в худшем случае — к тотальному перебору. Для некоторых классов систем вычислительная сложность работы алгоритма линейна [2, 3, 6]. При решении произвольной системы неравенств не всегда удаётся избежать попадания в тупиковую точку, в этом случае число итераций алгоритма зависит от количества встретившихся тупиковых точек. Естественно, что оптимизирующие модификации алгоритма должны тем или иным способом вести к уменьшению их количества. Одним из вариантов возможных модификаций является изменение критерия выбора приоритетного направления перемещения по вершинам n-мерного куба на основании учёта геометрических особенностей расположения плоскостей в окрестностях тупиковых точек. Анализ причин попадания в тупиковые точки в процессе поиска решения с помощью алгоритма Балаша позволяет выявить в процессе работы алгоритма направления, продвижения в сторону которых приведёт к попаданию в тупиковую точку. Предположим, что на i-м шаге алгоритма при текущем векторе xi минимальная невязка достигается на векторе x, получаемом изменением j-й координаты xi, и при этом вектор x не является решением. Далее опробуются смежные с x векторы y1,... , y^, полученные заменой одной из его нулевых координат на 1. Рассмотрим следующие случаи расположения некоторой плоскости и вершин x, y1,... , : 1) плоскость отсекает вершину x и y1,... , ; 2) плоскость отсекает y1,..., . Переход в вершину x при выполнении одного из условий обязательно приведёт в тупиковую ситуацию. Поэтому вершина x не может стать текущей, даже если невязка для неё минимальна при опробовании на предыдущем шаге всех непройденных и смежных с вершиной xi вершин. Из изложенного можно сделать вывод о том, что j -я координата вектора-решения равна нулю. Такой подход позволяет расставлять не только единицы, но и нули, строя приближение к вектору решений. С алгоритмической точки зрения попадания в тупиковую ситуацию в ряде случаев можно избежать, анализируя состояние системы в момент перехода в следующую вершину. При этом достаточно ввести для опробуемых и текущей вершин векторы-индикаторы выполнившихся неравенств. С их помощью легко выявить возникновение в ходе работы алгоритма случаев 1 и 2. Модификация алгоритма требует дополнительной емкостной сложности O(m) и вычислительной сложности O(n). Проиллюстрируем работу модифицированного алгоритма на примере решения следующей системы линейных ограничений: x1 + x2 + 2x3 + 5x5 — 6x6 + x7 ^ —5, — 3x1 — x2 — 2x3 — x4 — 2x5 — x6 — x7 ^ —3, x1 + 2x2 + 3x3 — 7x4 + 5x5 + 2x6 + x7 ^ —3, —x1 — 3x2 + 4x3 + 2x4 + 6x5 + 5x6 + 8x7 ^ 4, (2) x11 + x2 + 4x3 — 3x4 + 2x5 + 5x6 + 6x7 ^ 3, —x1 + 7x2 + x3 + 8x4 + 2x5 + 3x6 + 8x7 ^ 12, x2 — x3 + x4 — 2x5 + x6 — 4x7 ^ 0. Традиционный алгоритм Балаша стартует из вершины x0 = (0, 0, 0, 0, 0, 0, 0), в которой невязка системы p(x0) = 19. Опробование одной проставленной единицы даёт минимальное значение невязки, равное 8, на векторе x1 = (0,0, 0, 0, 0,0,1). Из этого вектора, в свою очередь, последовательно переходим в x2 = (0,1, 0, 0, 0, 0,1) с ^(x2) = 3, x3 = (0,1, 0, 0, 0,1,1) с ju(x3) = 2, x4 = (0,1,0,1,0, 0,1) с ^(x4) = 2 и попадаем в тупиковую точку. Эта ветвь алгоритма потребовала проведения 25 вычислений невязок и так и не привела к успеху. Предложенный модифицированный алгоритм уже на первом шаге устанавливает запрет на проставление единицы в первой и седьмой координатах вектора и присваивает шестой координате значение 1: xi = 0, x7 = 0 и x6 = 1. Отметим, что срабатывают первый и второй случаи стратегии запрета перехода в следующую вершину и блокируются возможности расстановки единиц соответственно по переменным x7 и xi, при этом ^(0, 0, 0, 0,0, 0,1) = 8 и является минимальной из всех посчитанных на первом шаге. В результате xi = (0, 0,0, 0, 0,1, 0). На втором шаге запрещается присваивание единицы переменным x3 и x5, переменной x2 даётся значение 1 и получается вектор x2 = (0,1, 0, 0, 0,1, 0). Присваивание единицы четвёртой координате приводит к нахождению решения x3 = (0,1,0,1, 0,1,0). При этом модифицированная версия алгоритма потребовала вычисления невязки всего 11 раз. Экспериментальные исследования, которые проводились на случайных системах неравенств, показали, что эффективность применения как базового алгоритма Ба-лаша, так и его модификации зависит от структуры системы неравенств. Основным достоинством предложенной модификации алгоритма Балаша является исключение попадания в целые классы тупиковых точек.

Скачать электронную версию публикации