Практические занятия

Лекции

Часть 2

МЕТОДИЧЕСКИЕ ПОСОБИЯ

по курсу "Математические основы информатики"

для студентов факультета ВМК

специальность "Прикладная информатика"

Нижний Новгород - 2007 год

Методические пособия по курсу "Математические основы информатики", часть 2, для студентов факультета ВМК, специальность "Прикладная информатика" / Нижег.гос.ун-т, 2007, с.77

В методических пособиях излагается материал по курсу лекций "Математические основы информатики", читаемых автором в третьем семестре дневного отделения факультета ВМК. Пособия содержат материалы курса, связанные с экстремальными задачами переборного типа.

Методические пособия подготовлены д.т.н., профессором М.Х.Прилуцким.

СОДЕРЖАНИЕ

1. РАБОЧАЯ ПРОГРАММА КУРСА "МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ" 4

Предисловие. 5

Лекции. 5

Практические занятия. 6

Литература (основная) 6

Литература (дополнительная) 6

2. КРАТКИЙ КОНСПЕКТ ЛЕКЦИЙ.. 7

2.1.Задачи целочисленного булева программирования. 7

2.2. Каноническая и многомерная задачи о ранце и их интерпретации. 8

2.3. Задача коммивояжера и ее интерпретации. 9

2.4. Задачи о назначениях и их интерпретации. 11

2.5. Задача целочисленного линейного программирования в общей постановке 12

2.6. Метод ветвей и границ. 13

2.7. Общая схема метода ветвей и границ Джеффриона-Марстена. 14

2.8. Решение канонической задачи о ранце методом ветвей и границ. 15

2.9. Решение многомерной задачи о ранце методом ветвей и границ. 16

2.10. Решение задачи коммивояжера методом ветвей и границ. 17

2.11. Решение задачи целочисленного линейного программирования методом ветвей и границ 18

2.12. Решение задачи о ранце с использованием табличной схемы.. 19

2.13. Решение задачи о ранце с использованием рекуррентных соотношений динамического программирования. 20

2.14. Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования. 20

2.15. Задачи теории расписаний. 21

2.16. Задачи теории расписаний с одним обслуживающим прибором.. 21

2.17. Перестановочный прием в задачах теории расписаний. 23

2.18. Теорема Лившица-Кладова. 24

2.19. Задачи теории расписаний в общей постановке. 24

2.20. Задача Джонсона. Графики Ганта. 25

2.21.Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования. 26

2.22. Сетевые модели. Расчет временных характеристик сетевых моделей. 28

2.23. Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потоке. 29

2.24. Алгоритм Форда-Фалкерсона нахождения максимального потока в транспортной сети 32

2.25. Решение задачи о назначениях алгоритмом Куна. 33

2.26. Минимаксные задачи о назначениях. 34

2.27. Задачи о назначениях с индивидуальными предпочтениями. 35

3. ЗАДАЧНИК С РЕШЕНИЕМ ТИПОВЫХ ЗАДАЧ.. 36

3.1. Решение задачи о ранце. 36

3.1.1. Решение задачи о ранце методом ветвей и границ. 36

3.1.2. Решение задачи о ранце методом динамического программирования (табличная форма) 38

3.1.3. Решение задачи о ранце методом динамического программирования (рекуррентная схема) 39

3.1.4. Решить следующие задачи о ранце. 40

3.2. Решение задачи коммивояжера. 41

3.2.1. Решение задачи коммивояжера методом ветвей и границ. 41

3.2.2. Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования 43

3.2.3. Решить задачи коммивояжера. 44

3.3. Решить задачу Джонсона для двух станков, построить график Ганта для оптимального расписания 46

3.4. Решение задачи о назначениях алгоритмом Куна. 49

3.5. Решение минимаксных (максиминных) задач о назначениях. 55

3.6. Решить задачи о назначениях с индивидуальными предпочтениями. 58

3.7. Нахождение максимального потока в транспортной сети алгоритмом Форда-Фалкерсона 65

3.8. Расчет временных характеристик сетевых моделей. 71

4. Контрольные задания. 76

5. Вопросы к экзамену. 77

1. РАБОЧАЯ ПРОГРАММА КУРСА "МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ"

Часть 2.

Специальность:

"Прикладная информатика"

Предисловие

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

Материалы данного курса будут использоваться в курсах "Прикладная информатика", " Теория вероятности и математическая статистика", "Модели и методы принятия решений", и др.

Задачи целочисленного булева программирования. Каноническая и многомерная задачи о ранце и их интерпретации. Задача коммивояжера и ее интерпретации. Задачи о назначениях и их интерпретации. Задача целочисленного линейного программирования в общей постановке. Метод ветвей и границ. Общая схема метода ветвей и границ Джеффриона-Марстена. Решение канонической задачи о ранце методом ветвей и границ. Теорема Данцига об оптимальном решении непрерывной приведенной задачи о ранце. Решение многомерной задачи о ранце методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ. Решение задачи целочисленного линейного программирования методом ветвей и границ. Решение задачи о ранце с использованием табличной схемы. Решение задачи о ранце с использованием рекуррентных соотношений динамического программирования. Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования. Задачи теории расписаний. Задачи теории расписаний с одним обслуживающим прибором. Перестановочный прием в задачах теории расписаний. Теорема Лившица-Кладова. Задачи теории расписаний в общей постановке. Задача Джонсона. Графики Ганта. Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования. Сетевые модели. Расчет временных характеристик сетевых моделей. Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потоке. Алгоритм Форда-Фалкерсона поиска максимального потока в транспортной сети. Алгоритмы решения задач о назначениях. Минимаксные (максиминные) задачи о назначениях. Задачи о назначениях с индивидуальными предпочтениями.

1.Решение канонической и многомерной задач о ранце методом ветвей и границ.

2.Решение задачи коммивояжера методом ветвей и границ.

3.Решение задачи целочисленного линейного программирования методом ветвей и границ.

4.Задачи теории расписаний.

5.Расчет временных характеристик сетевой модели.

6.Потоки в сетях. Алгоритм Форда-Фалкерсона.

7.Решение задачи о назначениях алгоритмом Куна.

8.Минимаксные и максиминные задачи о назначениях.

9.Задачи о назначениях с индивидуальными предпочтениями.

Литература (основная)

1.Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М. Наука, 1969.

2.Таха Х. Введение в исследование операций. М. Мир,1985,Том 1.

3.Вагнер Г. Основы исследования операций. М. Мир, 1972, том 1.

Литература (дополнительная)

1.Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М.Наука,1975.

2.Форд Л., Фалкерсон Д., Потоки в сетях. М. Мир, 1966.

3.Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М. Мир, 1984.

4.Сергиенко И.В."Математические модели и методы решения задач дискретной оптимизации" Киев, Наукова думка, 1988.

5.Батищев Д.И., Прилуцкий М.Х. "Оптимизация управленческих решений в сетевых моделях" Учебное пособие. Горький, ГГУ,1985.

6.Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Учебное пособие. Изд. ННГУ, Н.Новгород, 1994.

Дата добавления: 2017-02-01; Просмотров: 88; Нарушение авторских прав?; Мы поможем в написании вашей работы!