Алгоритм решения задачи.
h1 = LiO
1 n(m)
(h(m) - число дуг контура ц).
k-й шаг.
Определяем контур |mk положительной длины, при длинах дуг lij- hk-1. LkЕсли Lk = L(mk) < 0, то h = hk-1. Если L(mk) > 0, то определяем1
hk =—Lk, nk
где nk = n(mk), и переходим к следующему шагу.
За конечное число шагов будет получена величина h такая, что в графе отсутствуют контуры положительной длины при длинах дуг 1ij - h. Соответствующие потенциалы вершин {1i} и величина h определяют оптимальное решение задачи (1.2.11), а значит (1.2.10) и (1.2.7). Определив 5i, мы можем найти уi и, следовательно, получить полное описание операции.
Пример 1.2. Возьмем t11 = 2, t21 = 3, t12 = 1, t22 = 2. Имеем
Х,о X
12 22
1 21 2
q21 = max
X,, X
11 21
= max | —;— I = —. 2 3 0 3
В данном случае задачу можно решить не переходя к логарифмам, определяя вместо длины контура его усиление.
Усиление контура(1,2,1) равно 4/3 > 1. Следовательно, e = у^, w1 = 1, w2 = л/3 . Имеем
= 1
Q1 = 1, Q2 =
max| QL;Q2|- mini Q1 ; Q
X, , X
X, , X
11 12
51 =
0,09
11 12
max| | + min| Q1 • Q2
X, , X
X, , X
11 12
11 12
max| -QL;Q2 j-mini Q1 • Q2
Хо, X
Хо, X
21 22
52 =
< 0,06 .
21 22
^ Q1 Q21
^ Q1 • Q21
max
+ min
V 21 22 0
VT 21 22 0
Соответственно получаем
Q1 Q2
0,92
VT
0,94
max
V 11 12 0
(
Q1 Q2
y1 =(1 -51 )•
max
y2
3
V 21 L22
= (1 -52 )•
Еще по теме Алгоритм решения задачи.:
- Алгоритм решения задач
- Постановка задачи и алгоритм решения
- Алгоритм решения ситуационных задач по экспертизе временной нетрудоспособности
- ГЛАВА 2.Модели и алгоритмы решения задачи распределения производственных ресурсов промышленного предприятия
- Метод ветвей и границ относительно бинарных деревьев. Примеры задач, основные этапы, алгоритм нахождения оптимального решения
- 42. проблемная ситуация и задача этапы решения задач способы решения задач.
- 4.8.1. Алгоритм принятия управленческого решения (интерпретация А. Чернявского)
- 6.3. Алгоритм выработки, принятия и реализации управленческих решений
- Блок 2. Технология решения психологических задач Занятие 3 Технологии решения психологических задач.
- 4.4 Алгоритм получения навигационного решения при синтезированной ковариационной матрице
- 3.4 Аналитическое исследование эффективности алгоритма на модельной задаче
- Применение алгоритмов обработки изображений в задачах распознаваниия образов и тепловизионного мониторинга оборудования
- Решение двойственных задач
- 12.2. Аналитический метод решения задач параметрического программирования
- Порядок проведения исследований по решению поставлених задач
- Решение вспомогательных задач.
- 7.3. Графическое решение задачи линейного программирования
- 4.4 Указания к решению задач РГКР № 2