Cтраница 1
Аддитивный алгоритм применяют непосредственно к исходной дискретной задаче, не используя, в отличие от первоначальных вариантов метода ветвей и границ, решения соответствующей задачи линейного программирования. Вычислительный процесс чрезвычайно прост, ибо в нем используются лишь операции сложения и вычитания; тем самым устраняется проблема ошибок округления. Важно также, что исходная матрица ограничений в ходе алгоритма не подвергается пересчету. [1]
Аддитивный алгоритм в форме, предложенной Балашем, по логике похож на метод возможных направлений. [2]
Рассмотрим аддитивный алгоритм решения задачи булевого программирования. [3]
Итак, аддитивный алгоритм ориентирован на скорейшее выполнение ограничений ( с помощью правила Балаша) и отсеивание тех наборов переменных ( в том числе и допустимых решений), которые заведомо дадут худший критерии. [4]
Грубо говоря, аддитивный алгоритм состоит в построении последовательности частичных планов и в исключении некоторых подмножеств их дополнений. [5]
Эффективные программы реализации аддитивного алгоритма на ЭВМ включают ряд оригинальных вариантов, в том числе упрощенное представление частичного решения, а также экономичный способ отображения основного списка. В случае положительного результата проверки такое дополнение представляет собой наилучшее допустимое дополнение п его нужно зафиксировать в соответствии с описанием алгоритма. [6]
Численные эксперименты с аддитивным алгоритмом позволяют сделать некоторые качественные выводы. [7]
Вычислительный опыт, подтверждающий эффективность аддитивного алгоритма, пока сравнительно небогат. [8]
По этой причине такой метод иногда называют аддитивным алгоритмом. [9]
По существу на близких к идеям ветвей и границ приемах основан аддитивный алгоритм Балаша [47] и его модификации; основному варианту этого метода будет посвящена гл. Томпсон [125] предложил алгоритм для решения линейных целочисленных задач ( симплекс-метод с остановками), близкий к алгоритму Лэнд и Дойг, но существенно более экономный в смысле требований к памяти. [10]
Для решения задач, содержащих только булевы переменные, обычно используется так называемый аддитивный алгоритм. Для решения нелинейных задач с булевыми переменными используется также обобщенный аддитивный алгоритм. [11]
Игнорирование этого обстоятельства приводит к еще более серьезным ошибкам, чем при замене аддитивного алгоритма мультипликативным, или наоборот. [12]
Недавно в статье Джеффриона [80] был предложен метод неявного перебора, который является по существу вариантом аддитивного алгоритма. Наконец, в последней работе Балаша [48] развивается метод фильтра, позволяющий ускорить сходимость аддитивного алгоритма. Ограниченный объем книги не позволяет здесь остановиться на этих интересных вопросах. [13]
После такого преобразования задачи (4.1), (4.3), (4.4) в задачу (4.8), (4.3), (4.4) к ней можно применять аддитивный алгоритм, хотя она записана и не в канонической форме (4.5) - (4.7), так как ограничение в (4.8) обеспечивает частичность перебора. Заметим также, что аддитивность алгоритма для внутриалгоритмических операций сохраняется; она теряется только при вычислении критерия f для допустимого решения. Кроме того, дополнительной работой, вносимой дроб-но-линейностью задачи, является пересчет коэффициентов в ограничении (4.8) в связи с изменением f для очередного лучшего допустимого решения. [14]
Следует обратить внимание на два основных различия между изложенным методом и методом ветвей и границ, рассмотренным в разд. Во-первых, в аддитивном алгоритме требуется выполнение только операций сложения и вычитания ( не нужно ни умножения. [15]