- •1.1. Введение.
- •1.2. Оптимизационные задачи в 2.
- •1.4. Понятие о nр-полноте.
- •Условие целочисленности решения задачи лп.
- •Критерий полной унимодулярности.
- •Задача о назначениях.
- •Задача коммивояжера.
- •2. Принятие решений и элементы теории игр.
- •2.1. Задачи многокритериальной оптимизации.
- •2.3. Игры.
- •Дележи.
- •3. Сетевые модели.
- •3.1. Способы задания графов.
- •3.2. Изоморфизм графов.
- •П оиск простейших узких мест графа за o(|e|).
- •3.3. Остовные деревья.
- •Описание алгоритма Прима:
- •Корректность алгоритма Прима.
- •3.4. Кратчайшие пути в графах. Волновой алгоритм построения дкп (Дейкстра)
- •Нахождение кратчайшего пути для ациклического орграфа
- •3.5. Потоковые задачи Задача о максимальном потоке (змп).
- •На входе: матрицы а –пропускных способностей, и c – цен, c ij 0 - стоимость пропуска единицы потока по ребру (I,j), f0 - ограничение на величину потока.
- •3.6. Приближенное решение np-полных задач.
- •Задача о максимальной клике.
- •3.7. Точные методы решения np-полных задач.
- •4. Элементы теории массового обслуживания.
- •4.1. Пуассоновский поток событий
- •4.2. Моделирование простейшего потока.
- •4.3. Процессы гибели и размножения.
- •Классификация систем массового обслуживания:
- •4.4. Открытая система м | м | 1 (один врач).
- •4.5. Замкнутые системы с резервированием. Будем различать горячий и холодный резервы, т.Е. Исправные, но включенные или выключенные приборы.
- •4.6. Задачи проектирования сетей технического обслуживания.
- •3.5. Алгоритм Тарьяна (для планарных графов мод строится за o(n)).
3.3. Остовные деревья.
Пусть G = (V , E )– граф, V и E - множества его вершин и ребер. G - подграф графа G, если G = (V , E ), и E (V V ) E. Подграф G называют остовным деревом, если V = V и G является деревом. Всего в графе n n-2 остовных деревьев. Пусть заданы длины ребер. Минимальное остовное дерево (МОД)– остовное дерево с минимальной суммой длин всех ребер. Деревом кратчайших путей (ДКП) из фиксированной вершины назовем объединение кратчайших по длине путей из нее во все остальные.
П ример: пусть центр обслуживания размещен в крайней левой точке.
Исходная сеть дорог. Dмод=3, Rmax=3. Dдкп=4, Rmax=2
Для укладки асфальта лучше строить МОД, а для аварийной службы – ДКП.
№19. Волновой алгоритм нахождения МОД (Прим).
Алгоритм по очереди включает вершины. Введем следующие обозначения.
W – множество включенных, = V \ W - множество невключенных вершин.
Множество W можно понимать как характеристический вектор = функцию w:
W = w –1 (1) = {i | wi = w(i) = 1 } = w –1 (0) = {i | wi = 0 }
Разрез R (W) = {(v1, v2) E | v1 W , v2 W }
O(i) – отец i-ой вершины = ближайшая из включенных ранее вершин. В процессе работы до включения вершины ее отец может меняться.
D(i)=d(i,O(i)) – расстояние от i-ой вершины до ее текущего отца.
На выходе алгоритма получаем множество включенных ребер {(i,O(i))}, т.е. ориентированный по включению граф. Эту ориентацию можно не учитывать. В худшем случае алгоритм имеет трудоемкость T=O(n2).
Рассмотрим работу алгоритма на примере:
O |
1 |
1 |
1 4 |
1 |
4 |
3 5 |
2 8 6 |
6 7 |
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
D |
|
1 |
3 1 |
2 |
2 |
4 1 |
6 2 1 |
4 2 |
|
W |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
N |
W O-1(>0) ={i} |
{Di} |
Dk= min Di |
k= argmin |
W S(k) |
j |
Oj |
Dj |
R= dk,j |
коррекция Oj=k, Dj=R |
2 |
{4,3,2} |
{2,3,1} |
1 |
2 |
{3, 7} |
3 |
≠0 |
3 |
5 |
нет |
7 |
=0 |
|
6 |
O7=2, D7=6 |
||||||
3 |
{4,3,7} |
{2,3,6} |
2 |
4 |
{3, 5} |
3 |
≠0 |
3 |
1 |
O3=k, D3=1 |
5 |
=0 |
|
2 |
O5=k, D5=2 |
||||||
4 |
{5,3,7} |
{2,1,6} |
1 |
3 |
{5, 6, 7} |
5 |
≠0 |
2 |
3 |
нет |
6 |
=0 |
|
4 |
O6=k, D6=4 |
||||||
7 |
≠0 |
6 |
2 |
O7=k, D7=2 |
||||||
5 |
{5,6,7} |
{2,4,2} |
2 |
5 |
{ 6} |
6 |
≠0 |
4 |
1 |
O6=k, D6=1 |
6 |
{6,7} |
{1,2} |
1 |
6 |
{7, 8} |
7 |
≠0 |
2 |
1 |
O7=k, D7=1 |
8 |
=0 |
|
4 |
O8=k, D8=4 |
||||||
7 |
{7,8} |
{1,4} |
1 |
7 |
{ 8} |
8 |
≠0 |
4 |
2 |
O8=k, D8=2 |
8 |
{8} |
{2} |
2 |
8 |
{} |
|
|
|
|
нет |
N<n, но искать min не по чему, т.к. O(j)=0 для всех невключенных вершин ребер между включенными и невключенными вершинами нет граф несвязен. Мы построили МОД одной компоненты связности: Dмод=2+1+1+2+2+1+1=10.