- •Оглавление
- •Исходные данные
- •Задание №1. Графоаналитическое решение озлп
- •Задание № 2. Задача о коммивояжере. Метод ветвей и границ
- •Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования р. Беллмана
- •Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера
- •Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона
Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Расстояния между пунктами заданы матрицей:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
С = |
1 |
∞ |
3 |
4 |
5 |
1 |
6 |
2 |
1 |
∞ |
5 |
1 |
3 |
2 |
|
3 |
4 |
2 |
∞ |
3 |
6 |
1 |
|
4 |
3 |
4 |
1 |
∞ |
5 |
7 |
|
5 |
5 |
1 |
6 |
2 |
∞ |
3 |
|
6 |
1 |
6 |
3 |
1 |
4 |
∞ |
Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы C по строкам:
hν= min(i) hνi
|
|
1 |
2 |
3 |
4 |
5 |
6 |
hν |
С’ = |
1 |
∞ |
3 |
4 |
5 |
1 |
6 |
1 |
2 |
1 |
∞ |
5 |
1 |
3 |
2 |
1 |
|
3 |
4 |
2 |
∞ |
3 |
6 |
1 |
1 |
|
4 |
3 |
4 |
1 |
∞ |
5 |
7 |
1 |
|
5 |
5 |
1 |
6 |
2 |
∞ |
3 |
1 |
|
6 |
1 |
6 |
3 |
1 |
4 |
∞ |
1 |
Произведем приведение матрицы C по столбцам:
gi = min(υ) gνi
|
|
1 |
2 |
3 |
4 |
5 |
6 |
С’ = |
1 |
∞ |
2 |
3 |
4 |
0 |
5 |
2 |
0 |
∞ |
4 |
0 |
2 |
1 |
|
3 |
3 |
1 |
∞ |
2 |
5 |
0 |
|
4 |
2 |
3 |
0 |
∞ |
4 |
6 |
|
5 |
4 |
0 |
5 |
1 |
∞ |
2 |
|
6 |
0 |
5 |
2 |
0 |
3 |
∞ |
|
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
В итоге получаем полностью приведенную (редуцированную) матрицу:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
hν |
С0 = |
1 |
∞ |
2 |
3 |
4 |
0 |
5 |
1 |
2 |
0 |
∞ |
4 |
0 |
2 |
1 |
1 |
|
3 |
3 |
1 |
∞ |
2 |
5 |
0 |
1 |
|
4 |
2 |
3 |
0 |
∞ |
4 |
6 |
1 |
|
5 |
4 |
0 |
5 |
1 |
∞ |
2 |
1 |
|
6 |
0 |
5 |
2 |
0 |
3 |
∞ |
1 |
|
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
|
Величины hν и gi называются константами приведения.
Нижняя граница цикла: d0=6 ().
Шаг №1.
Определяем ребро ветвления и разобьем все множество допустимых значений Q0 относительно этого ребра на два непересекающихся подмножества () и (), т.е. , где
В приведенной матрице исследуем все нулевые переходы.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
αν |
C0 = |
1 |
∞ |
2 |
3 |
4 |
0(4) |
5 |
2 |
2 |
0(0) |
∞ |
4 |
0(0) |
2 |
1 |
0 |
|
3 |
3 |
1 |
∞ |
2 |
5 |
0(2) |
1 |
|
4 |
2 |
3 |
0(4) |
∞ |
4 |
6 |
2 |
|
5 |
4 |
0(2) |
5 |
1 |
∞ |
2 |
1 |
|
6 |
0(0) |
5 |
2 |
0(0) |
3 |
∞ |
0 |
|
|
βi |
0 |
1 |
2 |
0 |
2 |
1 |
|
Наибольшая сумма констант приведения равна
υ15= α1 + β5 =2+2=4, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
1 |
2 |
3 |
4 |
6 |
hν |
|
2 |
0 |
∞ |
4 |
0 |
1 |
0 |
|
3 |
3 |
1 |
∞ |
2 |
0 |
0 |
C1= |
4 |
2 |
3 |
0 |
∞ |
6 |
0 |
|
5 |
∞ |
0 |
5 |
1 |
2 |
0 |
|
6 |
0 |
5 |
2 |
0 |
∞ |
0 |
|
gi |
0 |
0 |
0 |
0 |
0 |
|
d1=0
Шаг №2.
Определяем ребро ветвления и разобьем все множество допустимых значений Q1 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
|
|
1 |
2 |
3 |
4 |
6 |
αν |
|
2 |
0(0) |
∞ |
4 |
0(0) |
1 |
0 |
|
3 |
3 |
1 |
∞ |
2 |
0(2) |
1 |
C1= |
4 |
2 |
3 |
0(4) |
∞ |
6 |
2 |
|
5 |
∞ |
0(2) |
5 |
1 |
2 |
1 |
|
6 |
0(0) |
5 |
2 |
0(0) |
∞ |
0 |
|
βi |
0 |
1 |
2 |
0 |
1 |
|
Наибольшая сумма констант приведения равна
υ43=2+2=4, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
1 |
2 |
4 |
6 |
hν |
C2 = |
2 |
0 |
∞ |
0 |
1 |
0 |
3 |
3 |
1 |
∞ |
0 |
0 |
|
5 |
∞ |
0 |
1 |
2 |
0 |
|
6 |
0 |
5 |
0 |
∞ |
0 |
|
|
gi |
0 |
0 |
0 |
0 |
|
d2=0
Шаг №3.
Определяем ребро ветвления и разобьем все множество допустимых значений Q2 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
|
|
1 |
2 |
5 |
6 |
αν |
C2 = |
2 |
0(0) |
∞ |
0(0) |
1 |
0 |
3 |
3 |
1 |
∞ |
0(2) |
1 |
|
5 |
∞ |
0(2) |
1 |
2 |
1 |
|
6 |
0(0) |
5 |
0(0) |
∞ |
0 |
|
|
βi |
0 |
1 |
0 |
1 |
|
Наибольшая сумма констант приведения равна
υ36=1+1=2, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
1 |
2 |
4 |
hν |
|
2 |
0 |
∞ |
0 |
0 |
C3 = |
5 |
∞ |
0 |
1 |
0 |
|
6 |
0 |
5 |
0 |
0 |
|
gi |
0 |
0 |
0 |
|
d3=0
Шаг №4.
Определяем ребро ветвления и разобьем все множество допустимых значений Q3 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
|
|
1 |
2 |
4 |
αν |
|
2 |
0(0) |
∞ |
0(1) |
2 |
C3 = |
5 |
∞ |
0(6) |
1 |
1 |
|
6 |
0(5) |
5 |
∞ |
5 |
|
βi |
0 |
5 |
1 |
|
Наибольшая сумма констант приведения равна
υ52=1+5=6, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
1 |
4 |
hν |
C4 = |
2 |
0 |
0 |
0 |
6 |
0 |
∞ |
0 |
|
|
gi |
0 |
0 |
|
d4=0
В соответствии с этой матрицей включаем в маршрут и .
Ответ: l* =C15+C52+C24+C43+C36+C61=1+1+1+1+1+1=6.
Дерево решения имеет следующий вид: