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

 

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

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

Введение в прикладное дискретное программирование

Автор: Сигал И.Х.
Другие авторы: Иванова А.П.
Издательство: М.: ФИЗМАТЛИТ
Год издания: 2003
Страницы: 240
ISBN 5-9221-0377-6
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
Скачать: vvedenievprikladnoeprogrammirovanie2003.djvu

УДК 519.8 ББК 22.18 С 34

Сигал И.X., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы:

Учеб. пособие. — Изд. 2-е, испр. — М.: ФИЗМАТЛИТ, 2003. — 240 с. — ISBN 5-9221-0377-6.

Излагаются современные комбинаторные алгоритмы для решения задач дискретной оптимизации с применением компьютерных средств. Рассматриваются: особенности задач дискретной оптимизации и их общие свойства; алгоритмы гарантированного функционирования; алгоритмы типа «greedy»; комбинированные алгоритмы различных типов для приближенного и точного решения задач; задачи большой размерности (параметризация и реализация). Основное внимание уделяется вычислительной реализации алгоритмов. Приводятся результаты вычислительного исследования алгоритмов для классических задач дискретной оптимизации — задачи о ранце и задачи о коммивояжере. Приведено много примеров для самостоятельной работы.

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

Первое издание — 2002 г.

Табл. 20. Ил. 57. Библиогр. 45 назв.

Рецензенты:

доктор физико-математических наук, профессор, академик РАЕН В.В. Шкурба (Московский государственный университет управления);

доктор технических наук, профессор, академик РАЕН В.Н. Бурков (Институт проблем управления РАН).

ISBN 5-9221-0377-6

© ФИЗМАТЛИТ, 2002, 2003 © И.Х. Сигал, А.П. Иванова, 2002, 2003

Оглавление

ПРЕДИСЛОВИЕ ............................................. 9

РАЗДЕЛ I ПРЕДМЕТ И МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

Глава 1. Постановка и особенности задач дискретного

программирования.................................. 17

1.1. Постановка задачи, примеры...................... 17

1.2. Особенности задач .............................. 20

1.3. Общие сведения о методах решения задач ......... 22

1.3.1. Методы отсечения (22). 1.3.2. Комбинаторные методы (24). 1.3.3. Приближенные методы (25).

1.4. Целочисленные многогранные множества ........... 25

Глава 2. Модели дискретного программирования ............ 29

2.1. Задачи транспортного типа ...................... 29

2.1.1. Транспортная задача в матричной постановке. Це-лочисленность опорных планов (29). 2.1.2. Задача о назначении (задача выбора) (31). 2.1.3. Задача коммивояжера (33). 2.1.4. Транспортная задача с фиксированными доплатами (39). 2.1.5. Распределительная задача (42)

2.2. Задача о ранце.................................. 44

2.2.1. Задача об одномерном ранце (44). 2.2.2. Задача о многомерном ранце (44). 2.2.3. Общие свойства задач о ранце (45).

2.2.4. Алгоритм Данцига для линейной одномерной задачи о ранце (46). 2.2.5. Алгоритмы последовательного назначения единиц для приближенного решения задачи об одномерном ранце (48). 2.2.6. Алгоритмы приближенного решения задачи о многомерном ранце (55). 2.2.7. Алгоритмы улучшения начального решения (57). 2.2.8. Алгоритмы «генетического»
4

Оглавление

типа (58). 2.2.9. Комбинированные эвристические алгоритмы для задачи о ранце (59). 2.2.10. Экспериментальные исследования системы комбинированных эвристических алгоритмов для приближенного решения задачи о ранце (59).

2.3. Задачи теории графов.................................... 63

2.3.1. Задачи о покрытиях графов (63). 2.3.2. Задача об изоморфизме графов (66). 2.3.3. Задачи о раскрасках графов (68).

2.4. Задача о покрытии конечного множества системой его подмножеств .................................................... 71

РАЗДЕЛ II КОМБИНАТОРНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

Глава 3. Метод ветвей и границ ........................... 75

3.1. Схема метода для общей задачи дискретного программирования .................................................. 75

3.2. Метод Ленд и Дойг для задачи частично целочисленного линейного программирования................................ 78

3.3. Метод Ленд и Дойг для задачи о ранце ............. 80

3.3.1. Основной алгоритм (80). 3.3.2. Модифицированный алгоритм (81). 3.3.3. Замечания о трудоемкости алгоритма (82). 3.3.4. Задача о построении всех близких к оптимуму решений и ее приложение (82). 3.3.5. Примеры (84).

3.4. Применение метода ветвей и границ для задачи коммивояжера ................................................... 92

3.4.1. Постановка задачи (92). 3.4.2. Приведение матрицы расстояний (92). 3.4.3. Ветвление (94). 3.4.4. Общий шаг алгоритма (96). 3.4.5. Пример (98). 3.4.6. Пример решения симметричной задачи (100). 3.4.7. Замечание о приведении матрицы расстояний (101). 3.4.8. Применение задачи о назначении для вычисления оценки и ветвления (102).

3.5. Применение метода ветвей и границ для симметричной задачи коммивояжера ...................................... 102

3.5.1. Определение 1-дерева (102). 3.5.2. Ветвление (103).

3.5.3. Пример (103). 3.5.4. Некоторые рекомендации для практического решения задач (107).

3.6. Некоторые вопросы вычислительной реализации алгоритмов
< 1 > 2 3 4 5 6 7 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100