Единое окно доступа к образовательным ресурсам

Математические основы информатики: Методическое пособие. Часть 3

Голосов: 2

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
                           1




МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ
             ФЕДЕРАЦИИ

Нижегородский государственный университет имени
               Н.И.Лобачевского


 Факультет вычислительной математики и кибернетики
        МЕТОДИЧЕСКОЕ ПОСОБИЕ

                      по курсу
    "Математические основы информатики"
          для студентов факультета ВМК
      специальность "Прикладная информатика"
                   Часть 3




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


                             2



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



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

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


                                                                             3



ОГЛАВЛЕНИЕ

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

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

СОДЕРЖАНИЕ КУРСА .....................................................................................................................5

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ ...........................................................................................................6

ЛИТЕРАТУРА (основная) ..................................................................................................................7

ЛИТЕРАТУРА (дополнительная) .....................................................................................................7


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


                                                                               4


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

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

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

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

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

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

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

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

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


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

3.1. Задачи о ранце..............................................................................................................................53
  3.1.1. Решение задачи о ранце методом ветвей и границ ...........................................................53
  3.1.2. Решение задачи о ранце методом динамического программирования (табличная форма)
   ............................................................................................................................................................57
  3.1.3. Решение задачи о ранце методом динамического программирования (рекуррентная
  схема).................................................................................................................................................58
  3.1.4. Решить задачу о ранце ........................................................................................................59

3.2. Задачи коммивояжера ...............................................................................................................61
  3.2.1. Решение задачи коммивояжера методом ветвей и границ ................................................61
  3.2.2. Решение задачи коммивояжера с использованием рекуррентных соотношений
  динамического программирования.................................................................................................64
  3.2.3. Решить задачу коммивояжера ...............................................................................................65

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

3.4. Задачи о назначениях .................................................................................................................74
  3.4.1. Решить задачу о назначениях алгоритмом Куна .................................................................79

3.5. Минимаксные (максиминные) задачи о назначениях .........................................................82
  3.5.1. Решить минимаксные и максиминные задачи о назначениях............................................85

3.6. Задачи о назначениях с индивидуальными предпочтениями ............................................87
  3.6.1. Решить задачи о назначениях с индивидуальными предпочтениями методом ветвей и
  границ ................................................................................................................................................92

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

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


4. ДОМАШНИЕ КОНТРОЛЬНЫЕ ЗАДАНИЯ...........................................113


                                              5


5. ВОПРОСЫ К ЭКЗАМЕНУ......................................................................115



 1. РАБОЧАЯ ПРОГРАММА КУРСА "МАТЕМАТИЧЕСКИЕ
ОСНОВЫ ИНФОРМАТИКИ"
   Часть 3.
      Специальность:
          "Прикладная информатика"

ПРЕДИСЛОВИЕ


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




СОДЕРЖАНИЕ КУРСА
                                        3 семестр


                           6



           МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ

  2. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПЕРЕБОРНОГО ТИПА.

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

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
   ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПЕРЕБОРНОГО ТИПА.


                              7




   1.Решение канонической и многомерной задач о ранце
методом ветвей и границ.
   2.Решение задачи коммивояжера методом ветвей и
границ.
   3.Решение задачи целочисленного линейного
программирования методом ветвей и границ.
   4.Задачи теории расписаний.
   5.Расчет временных характеристик сетевой модели.
   6.Потоки в сетях. Алгоритм Форда-Фалкерсона.
   7.Решение задачи о назначениях алгоритмом Куна.
 8.Минимаксные и максиминные задачи о назначениях.
Задачи о назначениях с индивидуальными предпочтениями.


 ЛИТЕРАТУРА (основная)


   1.Корбут А.А., Финкельштейн Ю.Ю. Дискретное
программирование. М. Наука, 1969.
   2.Таха Х. Введение в исследование операций. М.
Мир,1985,Том 1.
   3.Вагнер Г. Основы исследования операций. М. Мир,
1972, том 1.

ЛИТЕРАТУРА (дополнительная)


   1.Танаев В.С., Шкурба В.В. Введение в теорию
расписаний. М.Наука,1975.
   2.Форд Л., Фалкерсон Д., Потоки в сетях. М. Мир, 1966.
   3.Филлипс Д., Гарсиа-Диас А. Методы анализа сетей.
М. Мир, 1984.
   4.Сергиенко И.В."Математические модели и методы
решения задач дискретной оптимизации" Киев, Наукова
думка, 1988.


                          8



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




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


                                  9


2.1.Задачи целочисленного булева программирования.
Под задачей математического программирования
понимается задача (1):
extr f(x),                            (1)
x∈ D
где D = {х   g (x)
              j
                     ≤ 0,   j=1,2,...,n, x ∈ Q, Q ⊆ Rm }.
Здесь g j (x), j=1,2,...,n, и f(x) - произвольные функции, а
extr - max или min. Функция f(x) называется целевой
функцией, функционалом или критерием задачи (1), а D -
множеством или областью допустимых решений задачи
(1).
Среди задач типа (1) выделяют задачи, которые называют
регулярными.
Для них:
- для каждого допустимого вектора x, x ∈D, может быть
определена непустая окрестность;
-можно указать достаточно эффективно проверяемые
необходимые     и     достаточные   условия   локальной
оптимальности, т.е. локальный оптимум может быть найден
на множестве D при помощи конечного процесса ( или
бесконечного сходящегося);
-локальный оптимум целевой функции совпадает с
глобальным.
Примерами регулярных задач являются задачи выпуклого
программирования (функция f(x) - вогнута, а функции
g(x) -выпуклые). Если функции f(x) и g(x) - линейные, то
задача называется задачей линейного программирования.
Если область Q не является связной, то задача (1)
называется   дискретной   задачей    математического
программирования       или      задачей дискретного
программирования. Если функции f(x) и g(x) при этом
являются линейными, то такая задача называется задачей
целочисленного линейного программирования. Если


                                    10



компоненты вектора x могут принимать лишь значения 0
или 1, то такая задача называется задачей целочисленного
булева программирования.

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


Содержательное описание.
Есть несколько “предметов” , о которых известны их “веса”
и     “полезности”.      Задан      “ранец”     определённой
грузоподъёмности. Требуется поместить в “ранец”
“предметы” таким образом, чтобы они все “убрались” в
“ранец” и суммарная “полезность” от них была
максимальна.
Математическая модель.
Исходные параметры модели.
Пусть i=1,2,...,m - номера предметов, v(i) - “вес”
“предмета” с номеров i, c(i) - “полезность” “предмета” с
номером i, i=1,2,...,m, v(0) - “вместимость” “ранца”.
Варьируемые параметры модели.
Обозначим через x - m мерный вектор, элементы которого
x(i)=1, если “предмет” с номером i будет помещен в “ранец”
и x(i)=0, если “предмет” с номером i не будет помещен в
“ранец”.

Ограничения математической модели.
m

∑ v(i) x(i) ≤ v(0) ,
i =1
                                   (1)

x(i)   ∈   {0,1},                    (2)

Постановка оптимизационной задачи.
Критерий оптимальности для задачи о “ранце” имеет вид:
            m
F(x) = ∑ c(i) x(i )    → max   .   (3)
            i =1



    
Яндекс цитирования Яндекс.Метрика