Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 3

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 2 < 3 > 4 5 6 7 8 9 .. 84 >> Следующая


дискретного программирования ........................ 195

9.3.1. Общая схема (195). 9.3.2. О применении полученных результатов при решении задач (199). 9.3.3. Применение разработанного подхода для параметризации алгоритма поиска є-оптимального решения задачи о ранце большой размерности (201).

Глава 10. Алгоритмы приближенного решения задачи коммивояжера большой размерности .............................. 204

10.1. Постановка задачи и общие сведения об алгоритмах ее решения ................................................... 204

10.1.1. Постановка задачи (204). 10.1.2. Декомпозиционный подход (204).

10.2. Декомпозиция....................................... 205

10.2.1. Постановка задачи разбиения (205). 10.2.2. Задание

начального разбиения (206). 10.2.3. Построение начального разбиения (208). 10.2.4. Улучшение начального разбиения (211). 10.2.5. Корректирующие процедуры (212).

10.2.6. Иерархические процедуры декомпозиции (213).

10.2.7. Последовательная (древовидная) декомпозиция (213).

10.2.8. Практическое решение задачи разбиения (214).
8

Оглавление

10.3. Решение подзадач

214

10.3.1. Построение начальных решений (214). 10.3.2. Улучшение начальных решений (215). 10.3.3. Оценка точности приближенных решений (216). 10.3.4. Диалоговые процедуры (216).

10.4. Формирование приближенного решения задачи из решений

подзадач ............................................... 217

10.4.1. Построение начальной последовательности подмно-

жеств, оценка трудоемкости (217). 10.4.2. Улучшение последовательности подмножеств (218). 10.4.3. Формирование решений (218). 10.4.4. Алгоритм объединения решений

подзадач и оценка его трудоемкости (219).

10.5. Бикритериальная задача коммивояжера..................... 221

10.5.1. Постановка задачи (221). 10.5.2. Оптимизация свертки критериев (222).

ЗАДАЧИ

224

УПРАЖНЕНИЯ

226

СПИСОК ЛИТЕРАТУРЫ

227
Памяти академика Н.Н. Моисеева посвящается

Предисловие

Учебное пособие, предлагаемое вниманию читателя, разработано на основе курса лекций «Дискретная математика», читаемого одним из авторов в течение ряда лет в Московском государственном университете путей сообщения (МИИТ) для студентов, обучающихся по специальности «Прикладная математика».

Дискретные оптимизационные задачи находят широкое применение в различных областях, где используются математические методы для анализа происходящих там процессов. Необходимость решения таких задач приводит к тому, что дискретная оптимизация становится важным элементом образования специалистов, связанных с ее применением при решении задач, возникающих в приложениях. Поэтому нам представляется, что технология решения задач дискретного программирования должна стать одной из важных составных частей современного математического образования для специалистов по прикладной математике.

Дискретное программирование сформировалось как самостоятельная и важная часть математического программирования в конце 60-х годов. Процесс формирования был фактически завершен после выхода в свет в 1969г. монографии А. А. Корбута и Ю.Ю. Финкель-штейна «Дискретное программирование». Это была первая в мировой научной литературе книга по дискретной оптимизации. Она сыграла выдающуюся роль в развитии дискретного программирования в Советском Союзе; ее название дало имя целому научному направлению в математическом программировании. В данном учебном пособии мы следуем этой монографии при изложении многих вопросов.

В настоящее время разработаны современные методы и алгоритмы решения задач дискретного программирования, они описаны в научной и учебной литературе. Разработаны пакеты прикладных программ, позволяющие решать ряд стандартных задач дискретного программирования, например задачи частично целочисленного линейного программирования. Применение этих пакетов разумно, оправдано и вполне возможно без знания алгоритмов решения задач и технологий, обеспечивающих реализацию алгоритмов. В то же время знание существа применяемых алгоритмов и технологий их реализации позволяет более эффективно использовать разработанные паке-
10

Предисловие

ты. При возникновении новых нестандартных задач реализация алгоритмов их решения требует информации о технологии решения задач дискретной оптимизации. Тем не менее, по нашему мнению, в учебной литературе не получила достаточного освещения технология решения задач указанного типа. Под технологией решения задач понимается четко описанная система действий, выполняемых при их решении: учет особенностей задач; построение начального решения; улучшение этого решения; получение приближенного решения с оценкой отклонения от оптимума; применение диалоговых средств; организация информации, возникающей в процессе решения задач и работа с этой информацией. Именно этим вопросам уделяется наибольшее внимание в нашем учебном пособии; здесь описана технология решения и показана ее реализация для типовых задач. При этом крайне важно отметить, что важнейшей частью этой технологии является алгоритмическая, а точнее, программная реализация алгоритма; неудачная реализация может уничтожить все достоинства алгоритма.
Предыдущая << 1 .. 2 < 3 > 4 5 6 7 8 9 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100