- •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 Транспортная задача
- •Список литературы
7.3 Вычислительная схема динамического программирования
Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения (1). Чтобы определить его, необходимо:
1) записать функциональное уравнение для последнего состояния процесса (ему соответствует l = n −1):
2) найти R n(S n- 1,Un) из дискретного набора его значений при некоторых фиксированных Sn−1 и Un из соответствующих допустимых областей (так как f 0 (S n ) = 0, то В результате после первого шага известно решение Un и соответствующее значение функции f 1 (S n-1);
3) уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При l = n − k (k = 2,n) оно имеет вид
(2)
4) найти условно-оптимальное решение на основе выражения (2);
5) проверить, чему равно значение l. Если l = 0 , расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l ≠ 0 , перейти к выполнению п. 3;
6) вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.
Пример. Требуется перевезти груз из города А в город В. Сеть дорог, связывающих эти города, изображена на рис. 1. Стоимость перевозки груза из города s ( s =1, 9) в город j ( j = 2,10) проставлена над соответствующими дугами сети. Необходимо найти маршрут, связывающий города А и В, для которого суммарные затраты на перевозку груза были бы наименьшими.
Рис.7.1
Решение На рис. 7.1 вершинам сети поставлены в соответствие города, а дугам — транспортные магистрали. Разобьем все множество вершин (городов) на подмножества. В первое подмножество включим исходную вершину 1, во второе — вершины, в которые входят дуги, выходящие из вершины 1, в третье — вершины, в которые входят дуги, выходящие из вершин второго подмножества. Таким образом, продолжая разбиение, получаем пять подмножеств: {1}, {2, 3, 4}, {5, 6, 7}, {8, 9}, {10}. Очевидно, что любой маршрут из города 1 в город 10 содержит ровно четыре дуги, каждая из которых связывает вершины, принадлежащие соответствующим подмножествам. Следовательно, процесс решения задачи (нахождения оптимального маршрута) разбивается на четыре этапа. На первом этапе принимается решение, через какой город, принадлежащий второму подмножеству, везти груз из города 1. На втором этапе необходимо определить, через какой город третьего подмножества везти груз из некоторого города, принадлежащего второму подмножеству, и т. д.
Перенумеруем этапы от конечной вершины сети к начальной (см. рис. 1) и введем обозначения: n — номер шага (n = 1,2,3,4); fn (s) — минимальные затраты на перевозку груза от города s до конечного города, если до конечного города осталось п шагов; jn(s) — номер города, через который нужно ехать из города s, чтобы достичь fn (s); csj — стоимость перевозки груза из города s в город j. Здесь все обозначения несут важную смысловую нагрузку: f означает целевую функцию, s — состояние системы (номер города), индекс п несет динамическую информацию о том, что из города s до конечного города осталось п шагов.
Предположим, что груз доставлен в город 10, следовательно, число оставшихся шагов равно нулю (n = 0) и f n (s) = f0 (10)= 0, так как из города 10 груз везти не надо.
Рассмотрим последний шаг (п = 1) и вычислим для него значение функции. Очевидно, что в город 10 груз может быть доставлен или из города 8, или из города 9. Вычислим затраты на перевозку для этих двух состояний:
Чтобы произвести расчет для п = 2, выдвинем гипотезы о месте нахождения груза: 1-я гипотеза — груз находится в городе 5; 2-я гипотеза — груз находится в городе 6; 3-я гипотеза — груз находится в городе 7.
Из города 5 в город 10 можно провезти груз или через город 8, или через город 9. Поэтому оптимальный маршрут из города 5 найдется из выражения
Здесь s = 5 и j2(5) =9, т.е. условно-оптимальный маршрут проходит через город 9.
Аналогично находим значения функции для s = 6 и s = 7:
Все вычисления удобно выполнять в таблицах. Расчеты первого (n =1, csj + f0 (j)) и второго (n =2, csj + f1 (j)) этапов помещены в табл. 7.1 и 7.2 соответственно.
Таблица 7.1
s
j |
10 |
|
f1 (s) |
j1 (s) |
8 |
5+0 |
|
5 |
10 |
9 |
3+0 |
|
3 |
10 |
Таблица 7.2
s
j
|
8 |
9 |
|
f2 (s) |
j2 (s) |
5 |
9+5 |
8+3 |
|
11 |
9 |
6 |
|
5+3 |
|
8 |
9 |
7 |
7+5 |
12+3 |
|
12 |
8 |
Цифры в столбцах таблиц, находящиеся слева от двойной вертикальной черты, представляют собой сумму стоимости csj доставки груза из города s в город j и стоимости fn-1(j) − доставки груза из города j в город В. В каждой строке выбирается наименьшая из этих сумм. Этим определяются условно-оптимальные затраты на доставку груза из города s в конечный город. Затраты (значение функции) обозначены f n(s) и записаны в первом столбце справа от вертикальной черты, а город, через который проходит условно-оптимальный маршрут, обозначен jn(s).
Рекуррентное соотношение для п = 3 имеет вид
Отметим, что для подсчета условно-оптимальных значений используется значение
f2(j), полученное на предыдущем шаге, из табл. 2.
Вычисления для третьего шага (n =3, csj + f2 (j)) приведены в табл. 7.3. Здесь две клетки
заштрихованы, поскольку из городов 2 и 3 нельзя попасть в город 7.
Таблица 7.3
s
j
|
5 |
6 |
7 |
|
f3 (s) |
j3 (s) |
2 |
3+11 |
4+8 |
|
|
12 |
6 |
3 |
1+11 |
6+8 |
|
|
12 |
5 |
4 |
4+11 |
6+8 |
4+12 |
|
14 |
6 |
Таблица 7.4
s
j
|
2 |
3 |
4 |
|
f4 (s) |
j4 (s) |
1 |
4+12 |
11+12 |
3+14 |
|
16 |
2 |
Вычисления для четвертого шага (n =4, csj + f3 (j)) приведены в табл. 7.4, из которой
видно, что минимальные затраты на перевозку груза f4(1) = 16 и оптимальный маршрут
проходит через второй город, так как, j4(1) = 2. Далее из табл. 3 при s = 2 следует, что
оптимальный маршрут проходит через город 6, так как j3(2) = 6. Продолжая рассмотрение
таблиц, для п=2 определяем, что оптимальный маршрут проходит через город 9 (j2(6) = 9).
Наконец, из города 9 груз доставляется в конечный город 10 (место назначения). Таким
образом, двигаясь от последней таблицы к первой, мы определили оптимальный маршрут
μ = (1 —2 — 6 — 9 — 10), затраты на перевозку груза по которому составляют
f4(1) = 4 + 4 + 5 + 3 = 16.