- •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 Транспортная задача
- •Список литературы
Каркас минимального веса. Метод р. Прима.
Дано. Связный неориентированный граф G=<V,E>. Ребра имеют вес. Граф описывается матрицей смежности А (Array [1..N,1..N] Of Integer). Элемент матрицы, не равный нулю,определяет вес ребра.
Результат. Каркас с минимальным суммарным весом Q=(V,T), где T E.
Отличие от метода Краскала заключается в том, что на каждом шаге строится дерево, а не ациклический граф, т. е. добавляется ребро с минимальным весом, одна вершина которого принадлежит каркасу, а другая нет. Такой принцип «добавления» исключает возможность появления циклов. Для реализации метода необходимы две величины множественного типа SM и SP (Set Of 1..N). Первоначально значением SM являются все вершины графа, a SP пусто. Если ребро <i,j> включается в 7\ то один из номеров вершин i и / исключается из SM и добавляется в SP (кроме первого шага, на котором оба номера переносятся в SP).
рис.2
Пример. На рисунке 2 приведен граф, для которого последовательно строится каркас. Процесс построения (изменения SM, SP) показан на следующих рисунках.
SM-[1,2,5..7]
SP-[3,4]
SM-[1,5..7]
SP-[2.-4]
рис.3
Логика построения каркаса.
Procedure Tree; { *А - глобальная структура данных. *}
Var SM,SP:Set Of 1. .N;
min,i,j,1,k,t:Integer;
Begin
min:=maxint; SM:=[1..N];
SP:=[];
{*Включаем первоеребро в каркас. *}
For i:=l То N-l Do
For j:=i+l To N Do
If (A[i,j]<min) And (A[i,j]<>0) Then
Begin
min:=A[i,j];1:=i;t:=j;
End;
SP: = [l,t] ;SM:=SM-[l,t] <выводим илизапоминаем ребро <l,t»;
{^Основной цикл. *} While SM<>[] Do Begin min:=maxint;l:=0;t:=0; For i:=l To N Do If Not (i In SP) Then For j : =1 To N Do If (j In SP) And (A[i,j]<min) And (A[i,j]<>0) Then
Begin min:=A[j,k]; 1:=i;t:=j;End; SP:=SP+[1];SM:=SM-[1]; <выводим или запоминаем ребро <lft»;
End;
End;
Кратчайшие пути
Постановка задачи. Вывод пути
Дан ориентированный граф G=<V,E>,
веса дуг — A[i,j] (i,j=l..N, где N — количество вершин графа), начальная и конечная вершины — s, t V. Веса дуг записаны в матрице смежности А, если вершины i и j не связаны дугой, то A[i,,j]= . Путь между s и t оценивается Необходимо найти путь с минимальной оценкой.
Пример. Кратчайший путь из 1 в 4 проходит через 3-ю и 2-ю вершины и имеет оценку 6 (см. рис 4.23)
Особый случай — контуры с отрицательной оценкой.
Пример. При s=l и t=5, обходя контур 3423 (см. рис. 4.) достаточное число раз, можно сделать так, что оценка пути между вершинами 1 и 5 будет меньше любого целого числа. Оценку пути назовем его весом или длиной. Будем рассматривать только графы без контуров отрицательного веса.
рис.4
Необходимо найти кратчайший путь, т. е. путь с минимальным весом, между двумя вершинами графа. Эта задача разбивается на две подзадачи: сам путь и значение минимального веса.
Обозначим ее через D[s, t]. Неизвестны алгоритмы, определяющие только D[s,t], все они определяют оценки от вершины s до всех остальных вершин графа. Определим D как Array[1..N] Of Integer. Предположим, что мы определили значения элементов массива D — решили вторую подзадачу. Определим сам кратчайший путь. Для s и t существует такая вершина v, что D[t]=D[v]+A[v,t]. Запомним v (например, в стеке). Повторим процесс поиска вершины и, такой, что D[v]=D[u]+А[u,v], и так до тех пор, пока не дойдем до вершины с номером s. Последовательность t, v, u, ...., s дает кратчайший путь.
Procedure Way(s,t:Integer);
{*D, A - глобальные
структуры данных. St - локальная структура данных для хранения номеров вершин. *)
Var v,u:Integer;
Procedure Print; {*Выводит содержимое St.*}
Begin
…
End
Begin
<почистить St>;
<Занести вершину с номером t в St>; v:=t;
While v<>s Do
Begin u:=<номер вершины, для которой
D[v] =D[u] +A[u,v]>;
<занести вершину с номером v в St>;
V:=u;
End;
End;
Итак, путь при известном D находить мы умеем. Осталось научиться определять значения кратчайших путей, т. е. элементы массива D. Идея всех известных алгоритмов заключается в следующем. По данной матрице весов А вычисляются первоначальные верхние оценки. А затем пытаются их улучшить до тех пор, пока это возможно. Поиск улучшения, например для D[v], заключается в нахождении вершин и, таких, что D[u]+A[u,v]<D[v]. Если такая вершина u есть, то значение D[v] можно заменить на D[u]+A[u,v].