- •1. Теория графов
- •1.1 Остовные деревья минимального веса.
- •Алгоритм Прим
- •Алгоритм Краскал
- •1.2 Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дийкстры
- •Алгоритм Дийкстры
- •Модифицированный алгоритм Дийкстры
- •1.3 Нахождение кратчайших цепей между всеми парами узлов в сети
- •Алгоритм Флойда (Floyd r. W.)
- •Модификация алгоритма Флойда
- •1.4 Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
- •Алгоритм Форда-Фалкерсона
- •1.5 Обобщенные задачи о потоке
- •1.5.1 Построение потока в сети с двойным ограничением потока по дугам
- •1.5.2 Построение потока в сети с пропускными способностями узлов
- •1.5.3 Построение потока в сети с несколькими источниками-стоками
- •1.5.4 Построение потока в сети с неориентированными ребрами
- •1.6 Определение потока заданной величины минимальной стоимости. Алгоритмы Басакера-Гоуэна, Клейна
- •Алгоритм Басакера-Гоуэна (Basaker r.G., Gowen p.J)
- •Алгоритм Клейна (Klein m.)
- •2 Сетевое планирование
- •2.1 Построение сетевых моделей
- •2.2 Расчет и анализ сетевых моделей
- •Задача №1
- •Задача №2
- •I. Поиск критических путей
- •II. Поиск резервов работ
- •Правило №2.1
- •3 Линейное программирование
- •3.1 Примеры задач лп
- •3.2 Свойства решений задач линейного программирования
- •3.3 Двумерные задачи линейного программирования. Графический метод решения. Исследование на разрешимость
- •3.3.1 Построение области допустимых решений целевой функции f.
- •3.3.2 Построение прямой уровня
- •3.3.3 Максимизация целевой функции f
- •3.4 Симплекс-метод.
- •3.4.1 Построение начального опорного плана.
- •3.4.2 Симплексные таблицы
- •3.4.3 Примеры решения задач симплекс-методом
- •4. Теория двойственности в линейном программировании
- •4.1 Понятие двойственности. Построение пары взаимно двойственных задач
- •4.2 Теоремы двойственности и их экономическое содержание
- •4.3 Анализ решения задач линейного программирования
- •5. Транспортная задача
- •5.1 Постановка транспортной задачи в матричной форме. Построение исходного опорного плана
- •5.2 Метод потенциалов
- •5.3 Дополнительные условия в транспортных задачах.
- •6. Дискретное программирование.
- •6.1 Метод Гомори для решения задачи целочисленного линейного программирования
- •7. Динамическое программирование
- •7.1 Многошаговые процессы в динамических задачах
- •7.2 Принцип оптимальности и рекуррентные соотношения
- •7.3 Вычислительная схема динамического программирования
- •7.4 Оптимальное распределение средств на расширение производства
- •8. Матричные игры
- •8.1 Парные матричные игры с нулевой суммой
- •8.2 Платежная матрица
- •Нижняя и верхняя цена игры
- •8.3 Смешанные стратегии
- •8.3 Решение матричной игры сведением к задаче линейного программирования
- •8.4 Решение матричной игры графическим методом
- •8.5 Приближенный метод решения матричных игр
- •Практические работы Практическая работа №1 Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа
- •Практическая работа №2 Нахождение наикратчайших расстояний между всеми парами вершин графа. Алгоритм Флойда.
- •Практическая работа №3
- •Практическая работа №4 Нахождение потока заданной величины минимальной стоимости. Алгоритм Басакера-Гоуэна
- •Практическая работа №7 Оптимизация проекта по времени.
- •Практическая работа №8
- •Практическая работа №9 Оптимизация целевой функции с помощью двухфазного симплекс метода.
- •Практическая работа №10 Решение двойственных задач. Экономическая интерпретация задач линейного программирования.
- •Практическая работа №11 Решение транспортных задач.
- •Практическая работа №12 Дополнительные условия в транспортных задачах
- •Практическая работа №13 Метод Гомори для решения задачи целочисленного линейного программирования.
- •Практическая работа №14
- •Практическая работа №15 Решение матричных игр в чистых стратегиях
- •Практическая работа №16 Графический метод решения матричных игр.
- •Каркас минимального веса. Метод р. Прима.
- •Кратчайшие пути
- •Лабораторная работа №2 Кратчайшее расстояния от заданной вершины до всех остальных вершин графа.
- •Алгоритм Дийкстры.
- •Пути в бесконтурном графе.
- •Лабораторная работа №3 Кратчайшие пути между всеми парами вершин графа.
- •Алгоритм Флойда.
- •Лабораторная работа №4 Построение потока максимальной мощности.
- •Потоки в сетях.
- •Метод построения максимального потока в сети.
- •Лабораторная работа №5 Симплекс метод
- •Лабораторная работа №6 Транспортная задача
- •Список литературы
Лабораторная работа №3 Кратчайшие пути между всеми парами вершин графа.
Составить программу нахождения кратчайшего пути между всеми порами вершин графа по алгоритму Флойда.
Алгоритм Флойда.
Дан ориентированный граф G=<V,E> с матрицей весов А(Array [1..N,1..N] Of Integer).
В результате должна быть сформирована матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути.
Идея алгоритма. Обозначим через Dm[i,j] оценку кратчайшего пути из i в j с промежуточными вершинами из множества [1..т]. Тогда имеем:
D°[i,j]:=A[i,j] и
D(m+1)[i,j]= Min{Dm[i,j],Dm[i,m+1 ] +Dm[m+1,j].
Второе равенство требует пояснения. Пусть мы находим кратчайший путь из i в j с промежуточными вершинами из множества [1..(т+1)]. Если этот путь не содержит вершину (m+1), то D(m+1)[i,j]=Dm[i,j]. Если же он содержит эту вершину, то его можно разделить на две части: от i до (m+1) и от (m+1) до j.
Procedure Dist; (*А, D - глобальные структуры данных. *} Var m,i,j:Integer;
Begin
For i: =1 To N Do
For j:=1 To N Do D[i,j] :=A[i,j] ;
For i:=1 To N Do D[i,i]:=0;
For m:=1 Tо N Do
For i : = 1 To N Do
For j:=1 To N Do D[i,j] : =Min {D[i ,j] , D[i,m]+D[m,j] };
End;
Пример. На рисунке 7 представлены графа и значения матриц типа D при работе процедуры.
Верхний индекс у D (см. рис.8) указывает номер итерации (значение m в процедуре Dist).
Рис.7
Рис. 8
Расстояния между парами вершин дает D. Для вывода самих кратчайших путей введем матрицу М того же типа, что и D. Элемент M[i,j] определяет предпоследнюю вершину кратчайшего пути из i в j.
Процедура Dist претерпит небольшие изменения. В том случае, когда D[i,j] больше D[i,m]+D[m,j], изменяется не только D[i,j], но и M[i,j]. M[i,j] присваивается значение М[m,j]. Для нашего примера изменения М отражены на рис.9.
Рис.9
Например, необходимо вывести кратчайший путь из 3-й вершины во 2-ю. Элемент М[3,2] равен 1, поэтому смотрим на элемент М[3,1]. Он равен четырем. Сравниваем М[3,4] с 3-й. Есть совпадение, мы получили кратчайший путь: 3412.
Procedure All_Way (i, j : Integer) ;{*Вывод пути между вершинами i и j . *}
Begin
If M(i,j]=i Then
If i=j Write(i) Else Write (i, '-' ,j)
Else
Begin All_Way (i ,M[i, j] ) ;All_Way (M[i , j ] , j) ;
End;
End;
Лабораторная работа №4 Построение потока максимальной мощности.
Составить программу построения потока максимальной мощности по алгоритму Форда-Фалкерсона.
Потоки в сетях.
Постановка задачи
Одной из задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой вершине t (стоку). При этом каждой дуге (граф ориентированный) (ij) приписана некоторая пропускная способность C(i,j), определяющая максимальное значение потока, который может протекать по данной дуге. Содержательных интерпретаций задачи достаточно много, и, безусловно, они усилят и сделают более понятными сложные занятия по этой проблематике.
Метод решения задачи о максимальном потоке от s к t был предложен Фордом и Фалкерсоном, и их «техника меток» составляет основу других алгоритмов решения многочисленных задач, являющихся обобщениями или расширениями указанной задачи.
Одним из фундаментальных фактов теории потоков в сетях является классическая теорема о максимальном потоке и минимальном разрезе. Разрезом называют множество дуг, удаление которых из сети приводит к «разрыву» всех путей, ведущих из s в t. Пропускная способность разреза — это суммарная пропускная способность дуг, его составляющих. Разрез с минимальной пропускной способностью называют минимальным разрезом.
Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий этого значения.
Теорема устанавливает эквивалентность задач нахождения максимального потока и минимального разреза, однако не определяет метода их поиска.
П ример. Показана сеть (рис.10), источник — вершина 1, сток — вершина 6, в скобках у дуг указаны их пропускные способности. Минимальный разрез — дуги (1, 2) и (3, 4), следовательно, согласно теореме максимальный поток равен 4. Разрез определен путем простого перебора. Логика его «лобового» поиска очевидна. Осуществляем перебор по дугам путем генерации всех возможных подмножеств дуг. Для каждого подмножества дуг проверяем, является ли оно разрезом. Если является, то вычисляем его пропускную способность и сравниваем ее с минимальным значением. При положительном результате сравнения запоминаем разрез и изменяем значение минимума. Удачный выбор данных позволяет сделать программный код компактным, но очевидно, что даже при наличии различных отсечений в переборе метод применим только для небольших сетей. Однако, как найти максимальный поток, т. е. его распределение по дугам, по-прежнему открытый вопрос.
«Техника меток» Форда и Фалкерсона заключается в последовательном (итерационном) построении максимального потока путем поиска на каждом шаге увеличивающейся цепи, то есть пути (последовательности дуг), поток по которой можно увеличить. При этом узлы (вершины графа) специальным образом помечаются. Отсюда и возник термин «метка».
Пример. Рядом с пропускными способностями дуг указаны потоки, построенные на этих дугах. На рисунке поток через сеть равен 10 и найдена увеличивающаяся цепочка, выделенная «жирными» линиями. Обратите внимание на ориентацию дуг, входящих в цепочку. По данной цепочке можно пропустить поток, равный 1, пропускная способность дуги (5, 6). Изменяем суммарный поток, его значение становится равным 11. Поток увеличен, необходимо продолжить поиск увеличивающихся цепочек; если окажется, что построить их нельзя, то результирующий поток максимален. Заметим, что для данного примера это значение потока окончательное. Обратите внимание на то, как изменен поток на дугах сети в зависимости от их ориентации.
рис.10
рис.11