Задачи и методы конечномерной оптимизации. Часть 3/Учебное пособие.
- Нижний Новгород: Изд-во Нижегородского ун-та, 2004. 150 с.
Часть 3 посвящена задачам дискретной оптимизации и методу
динамического
программирования как одному из наиболее эффективных инструментов их решения.
Для записи общих соотношений динамического программирования вводится концепция дискретной управляемой системы, формулируются задачи синтеза оптимальных траекторий. Полученные уравнения позволяют строить оптимальные траектории методами прямого и обратного счета. Показывается, что в терминах дискретных управляемых систем записываются и решаются многие задачи дискретной оптимизации, включая задачи синтеза расписаний обслуживания. В реальных системах качество принимаемых решений следует, как правило, оценивать по ряду показателей, поэтому значительное внимание уделяется многокритериальным задачам. При этом рассматриваются вопросы синтеза представительных совокупностей эффективных оценок и соответствующих Парето-оптимальных решений; излагаемые процедуры основываются на соответствующих модификациях метода динамического программирования. Приводятся постановки и решающие процедуры для
многокритериальных модификаций задачи о ранце, задачи коммивояжера, задач синтеза расписаний обслуживания и т.д. Значительное внимание уделяется вопросам вычислительной сложности. Для ряда труднорешаемых задач выделяются
полиномиально разрешимые подклассы, строятся эвристические процедуры синтеза
решений.
Пособие предназначено для студентов, специализирующихся в области прикладной математики и информатики.
программирования как одному из наиболее эффективных инструментов их решения.
Для записи общих соотношений динамического программирования вводится концепция дискретной управляемой системы, формулируются задачи синтеза оптимальных траекторий. Полученные уравнения позволяют строить оптимальные траектории методами прямого и обратного счета. Показывается, что в терминах дискретных управляемых систем записываются и решаются многие задачи дискретной оптимизации, включая задачи синтеза расписаний обслуживания. В реальных системах качество принимаемых решений следует, как правило, оценивать по ряду показателей, поэтому значительное внимание уделяется многокритериальным задачам. При этом рассматриваются вопросы синтеза представительных совокупностей эффективных оценок и соответствующих Парето-оптимальных решений; излагаемые процедуры основываются на соответствующих модификациях метода динамического программирования. Приводятся постановки и решающие процедуры для
многокритериальных модификаций задачи о ранце, задачи коммивояжера, задач синтеза расписаний обслуживания и т.д. Значительное внимание уделяется вопросам вычислительной сложности. Для ряда труднорешаемых задач выделяются
полиномиально разрешимые подклассы, строятся эвристические процедуры синтеза
решений.
Пособие предназначено для студентов, специализирующихся в области прикладной математики и информатики.