Оптимальное размещение участка слежения в графе решения летчика
Дипломная работа - Транспорт, логистика
Другие дипломы по предмету Транспорт, логистика
7 2 2 3 3 4 1
Второй уровень
7 7 3 5 Оценка = 51
7 10 5 Оценка = 53
7 14 1 Оценка = 61
7 15 Оценка = 59
Третий уровень
7 7 7 1 Оценка = 55
7 7 8 Оценка = 53
Четвертого уровня не будет
2 7 2 3 4 1
Второй уровень
2 7 9 1 Оценка = 52
2 7 10 Оценка = 50
Третьего уровня не будет
2 2 7 3 3 4 1
Второй уровень
2 2 7 6 5 Оценка = 53
2 2 7 10 1 Оценка = 61
2 2 7 11 Оценка = 59
Третьего уровня не будет
2 2 3 7 3 4 1
Второй уровень
2 2 3 7 7 1 Оценка = 59
2 2 3 7 8 Оценка = 57
Третьего уровня не будет
2 2 3 2 8 4 1
Второго уровня не будет
2 2 3 2 2 6 4 1
Второго уровня не будет
2 2 3 2 2 3 7 1
Второго уровня не будет
Скользящее сечение по уровням справа-налево
1 2 2 3 2 2 3 8
Второй уровень
3 7 8 Оценка = 49
10 8 Оценка = 51
12 8 Оценка = 55
14 8 Оценка = 59
8 Оценка = 57
Третий уровень
7 7 8 Оценка = 53
7 8 Оценка = 51
Четвертого уровня не будет
2 2 3 2 2 3 7 1
Второй уровень3 5 7 7 1 Оценка = 51
10 7 1 Оценка = 53
12 7 1 Оценка = 57
14 7 1 Оценка = 61
7 1 Оценка = 59
Третий уровень
7 7 7 1 Оценка = 55
7 7 1 Оценка = 53
Четвертого уровня не будет
2 2 3 2 2 6 4 1
Второй уровень
7 6 4 1 Оценка = 49
9 6 4 1 Оценка = 53
11 6 4 1 Оценка = 57
6 4 1 Оценка = 55
Третьего уровня не будет
2 2 3 7 3 4 1
Второй уровень
7 7 3 4 1 Оценка = 55
7 3 4 1 Оценка = 53
Третьего уровня не будет
2 2 7 3 3 4 1
Второго уровня не будет
2 7 2 3 3 4 1
Второго уровня не будет
7 2 2 3 3 4 1
Второго уровня не будет
Опт п/последовательности по всем уровням скользящего сечения: 8 7 3 5, 5 3 7 8, 5 7 6 4 1 с оценкой = 49
.4 Доказательство необходимости почленного укрупнения и скользящего сечения
(I, ): заданная последовательность состоит из членов первого участка, а их сумма больше х1 (процедура скользящего сечения с продвижением суммы членов, минимально превосходящих х1. Процедура слева-направо и справа-налево).
Пример 1:
Рисунок 2.7
Исходя из примера, видно, что почленное укрупнение помогает не потерять важные для нахождения оптимальной порожденной последовательности решения.
Конкретно:
Рисунок 2.8
При заданных коэффициентах a1, a2, b1 оценка порожденной последовательности с неукрупненными членами на втором участке меньше оценки порожденной последовательности с укрупненными членами.
Пример 2:
Рисунок 2.9
Исходя из примера, видно, что почленное укрупнение помогает не потерять важные для нахождения оптимальной порожденной последовательности решения.
Конкретно:
Рисунок 2.10
При заданных коэффициентах a1, a2, оценка порожденной последовательности с укрупненными членами меньше оценки порожденной последовательности с неукрупненными членами.
2.5 Процедура по сокращению прямого перебора
Класс ().
Таким образом получим:
(1)
Найдем разность полученных оценок и
Предпочтительная опт п/последовательность определяется знаками и величинами и
Рисунок 2.11
Рисунок 2.12
Рисунок 2.13
Рисунок 2.14
Рисунок 2.15
Рисунок 2.16
Рисунок 2.17
Рисунок 2.18
Рисунок 2.19
Таким образом, можно сделать вывод:
Если:
)y(A)-y(b)>0, то целесообразен перенос на II участок
2)y(A)-y(b)<0, то перенос нецелесообразен
3)y(A)-y(b)=0, то результат от переноса не изменится
Рисунок 2.20
Рисунок 2.21
Рисунок 2.22
Рисунок 2.23
Рисунок 2.24
Рисунок 2.25
Рисунок 2.26
Рисунок 2.27
Рисунок 2.28
Рисунок 2.29
Рисунок 2.30
Рисунок 2.31
Рисунок 2.32
Рисунок 2.33
Анализируя результаты тестовых примеров, можно сделать вывод:
1)a1>a2, b>a2, то целесообразен перенос на II участок
2)a2>a1, b?a2 то перенос нецелесообразен
3)При росте b (b>a2) есть критическая точка, после которой целесообразно переносить на II участок
)при а2=b, то результат от переноса не изменится
Рассматриваются з/последовательности {I, x1<?} и {I,II} с оценочной функцией, имеющей только два линейных участка. Ее параметры a1, a2, b1, x1.
Заданная последовательность {I, x1<?}
Укрупним выделенные члены, обеспечив минимальное число укрупненных членов, каждый из которых (не превосходит ) Пусть k1 - число укрупненных членов.
Тогда:
a2(?1-x1)+a1x1+b1
a1?1+k1b1
Найдем разность:
?1=(a2-a1)( ?1-x1)-(k1-1)b1
При ?1<0 выделенные члены з/последовательности нужно переносить на II участок.
При ?1>0 выделенные члены з/последовательности нужно оставлять на I участке.
Примеры:
Проверим общий случай b минимально, вариации с а1 и а2
Рисунок 2.34
Рисунок 2.35
Увеличиваем b, вариации с а1 и а2
Рисунок 2.36
Рисунок 2.37
Рисунок 2.38
Рисунок 2.39
Увеличим а1 и будем увеличивать b, чтобы увидеть зависимость
Рисунок 2.40
Рисунок 2.41
Рисунок 2.42
Рисунок 2.43
Рисунок 2.44
Рисунок 2.45
Рисунок 2.46
Делаем вывод, что при a1>a2 и b>a2, получаем целесо