Cтраница 1
Дискретные оптимизационные задачи находят широкое применение в различных областях, где используются математические методы для анализа происходящих там процессов. Необходимость решения таких задач приводит к тому, что дискретная оптимизация становится важным элементом образования специалистов, связанных с ее применением при решении задач, возникающих в приложениях. Поэтому нам представляется, что технология решения задач дискретного программирования должна стать одной из важных составных частей современного математического образования для специалистов по прикладной математике. [1]
Для дискретных оптимизационных задач таким параметром служит прежде всего размерность задачи и некоторые другие параметры ( количество ограничений, особая структура этих ограничений и др.) - Следует отметить, что понятие размерности задачи не имеет общего толкования для всех дискретных оптимизационных задач. Для определения размерности линейной целочисленной задачи используют сумму или произведение величин п и т, характеризующих количество переменных и количество ограничений соответственно. Для изложения материала настоящей книги более удобным оказалось представлять размерность задачи как мощность комбинаторного пространства, в терминах которого представлена задача. [2]
Решение этой дискретной оптимизационной задачи эквивалентно решению исходной задачи гибридного оптимального управления. [3]
В случае дискретных оптимизационных задач применение таких общих свойств весьма затруднительно, поскольку отсутствуют необходимые исследования в теории функций дискретной переменной. [4]
Эта процедура легко переносится на решение дискретных оптимизационных задач, при этом состояния физической системы заменяются конфигурацией системы, изменением критерия качества, а произведение Ы заменяется обобщенным понятием температуры Т, которая может рассматриваться как управляющий параметр оптимизационной процедуры. [5]
Важное значение имеют вопросы эффективности алгоритмов решения дискретных оптимизационных задач. Ясно, что для дискретных задач не всегда пригодны критерии оценки эффективности алгоритмов оптимизации, используемые для непрерывных задач. Так, например, такой критерий, как скорость сходимости минимизирующей последовательности к точке минимума, не может применяться к конечношаго-вым алгоритмам дискретной оптимизации. [6]
Здесь же мы попытаемся привести несколько формальных постановок дискретных оптимизационных задач различного содержания, представляющих в данном случае методический интерес, и показать, каким образом они могут быть интерпретированы как задачи из имеющихся в пакете ВЕКТОР-1 классов. [7]
Настоящий параграф носит иллюстративный и методологический характер, поэтому остановимся как на общеизвестных дискретных оптимизационных задачах ( классических), так и формализованных сравнительно недавно. [8]
Вместе с тем, нельзя не отметить, что метод динамического программировании оказывается весьма эффективным при решении дискретных оптимизационных задач. [9]
Под методами ветвей и границ подразумевают алгоритмы перебора, которые появились не так давно как фундахментальный общий метод нахождения оптимальных решений дискретных оптимизационных задач. Методика ветвей и границ быстро развилась, и сейчас полный список работ, связанных с ней, насчитывает несколько сотен наименований. Хотя метод ветвей и границ был развит и обобщен многими авторами [1, 7, 60, 107, 113, 120, 123], очень немногие из них рассматривали зависимость относительных потребностей в вычислительных ресурсах от выбора параметров алгоритма. [10]
Для дискретных оптимизационных задач таким параметром служит прежде всего размерность задачи и некоторые другие параметры ( количество ограничений, особая структура этих ограничений и др.) - Следует отметить, что понятие размерности задачи не имеет общего толкования для всех дискретных оптимизационных задач. Для определения размерности линейной целочисленной задачи используют сумму или произведение величин п и т, характеризующих количество переменных и количество ограничений соответственно. Для изложения материала настоящей книги более удобным оказалось представлять размерность задачи как мощность комбинаторного пространства, в терминах которого представлена задача. [11]
Данная задача принадлежит, как показано в [40], к классу TVP-полных задач, которые будут рассмотрены в последующей главе. Точными методами решения подобных дискретных оптимизационных задач является, в частности, метод ветвей и границ. [12]
Примером такого класса задач являются оптимизационные задачи, возникающие, в частности, при проектировании ЭВМ. Наряду с этим представление дискретных оптимизационных задач в комбинаторной форме позволило развить класс так называемых комбинаторных методов, наиболее изученным среди которых является метод ветвей и границ. [13]
В данном параграфе приводятся некоторые общие сведения, относящиеся в первую очередь к численным методам безусловной и условной минимизации функции конечного числа непрерывно изменяющихся переменных. Такие методы занимают центральное место в численной оптимизации; они, в частности, используются при решении дискретных оптимизационных задач и задач оптимального управления. [14]
Методы типа ветвей и границ - это наиболее широко используемые в настоящее время методы решения не только целочисленных и частично целочисленных задач ЛП, но и других дискретных оптимизационных задач. Различные методы типа ветвей и границ существенно используют специфику конкретных задач и поэтому заметно отличаются друг от друга. Однако все они основаны на последовательном разбиении допустимого множества на подмножества ( ветвлении) и вычислении оценок ( границ), позволяющем отбрасывать подмножества, заведомо не содержащие решений задачи. [15]