Cтраница 4
Решения, полученные при помощи описанных выше двух алгоритмов, являются приближенными решениями. Локальное решение задачи (6.5) гарантировано в том случае, если продолжить счет, например, по методу вектора спада. Как показали численные эксперименты, алгоритмы декомпозиционного типа дают достаточно хорошее приближение, а применение метода вектора спада после них позволяет получить такое локальное решение, которое трудно достичь только методом вектора спада, если исходить из случайных начальных приближений. [46]
Применение метода последовательной статистической оптимизации дает в среднем результат 164 усл. Ненаправленный случайный перебор за то же время позволил получить значение длины полосы, равное 173 усл. При использовании метода вектора спада ( см. алгоритм II 1.3) определен локальный оптимум в окрестности единичного радиуса в пространстве перестановок с инверсной метрикой. [47]
Одна из возможных формулировок задачи приведена в гл. Задача о рюкзаке имеет особое значение в дискретном программировании, так как к ней приводятся задачи целочисленного программирования с ограниченным множеством допустимых решений; кроме того, для решения такой задачи разработан ряд эффективных методов. Не останавливаясь подробно на свойствах различных типов задач о рюкзаке и методах их решения, изложим метод вектора спада применительно к задаче о рюкзаке, сформулированной в § 4 гл. [48]
Некоторые замечания относительно особенностей решения ЗП (4.38), (4.34), (4.37) в реальных условиях работы АСОД. При сравнительно больших значениях индексов j, fc, /, г в этой задаче ее эффективное решение становится затруднительным. Это происходит потому, что поиск даже локального ее решения занимает слишком много времени. Последним обстоятельством и объясняется тот факт, что когда задачи такого типа приходится решать в процессе функционирования АСОД, то для их решения, как правило, выбираются различного рода приближенные методы. В частности, для решения этой задачи в системе ЦЕНТР АС [8], предназначенной для автоматизированного управления специализированным кустовым ВЦ, использована модификация метода вектора спада. [49]
Задачи геометрического проектирования, как правило, имеют большую размерность. Вместе с тем эффективность точных методов решения задач дискретной оптимизации существенно зависит от размерности, причем с ее возрастанием резко увеличивается объем вычислений, необходимых для отыскания точного решения. Обычно он настолько велик, что точно решить задачу за реальное время не возможно. Поэтому возникает необходимость в выборе эффективных приближенных методов дискретной оптимизации. В настоящее время разработано большое число приближенных методов, например [5, 22, 33, 43, 44, 151, 155, 160,161] и др., успешно применяемых при решении различных практических задач, в том числе задач геометрического проектирования. Ниже описан метод вектора спада согласно работам [114, 115] и его применение иллюстрируется к задачам разбиения и покрытия. [50]