Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 88 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

90
74,7, при этом соответствующий ему цикл включает все множество n
элементов ( ∅=)3;3(
2
G , графа 8). Условия (4.33) выполнены и цикл
)5;3(
2
μ
выбывает из дальнейших расчетов (знак минус в графе 7 строки
14). Полученный вариант (строка 12)
не доминируется ближайшим к нему
вариантом (строка 7), а поэтому он и должен быть использован как
начальный для очередного шага процесса. Однако поскольку все элементы
уже включены в цикл (
∅
=
3
G
), то процесс заканчивается. Полученное
решение записано в нижней строке табл. 37. Решение оптимально и
совпадает с решениями, полученными другими методами ((5.8), табл. 36).
Проверка условий доминирования (4.33) требует значительно меньше
усилий, чем необходимо для описания их применения в данном примере.
Кроме того, уменьшая число шагов процесса, применение принципа
доминирования пропорционально этому уменьшает и объем
вычислений,
требуемый для получения решения. Условия (4.33) основаны на
неформальном подходе, поэтому возникает вопрос о том, как повлияет
вводимое правило на конечный результат и сокращение объема
вычислений. Некоторые объяснения может дать рассматриваемый
тестовый пример.
Если отказаться от применения принципа доминирования и на втором
шаге процесса в качестве исходного цикла для очередного шага
(3
=
t
)
процесса взять вариант, соответствующий минимальному значению
удельных энергозатрат (табл. 37, строка 13), то процесс продолжится. Для
этого случая в табл. 38 приведены результаты дальнейших расчетов.
Текущие пробные циклы (табл. 38, графа 4) улучшены на основе проверки
второго необходимого условия оптимальности для повторяющихся
элементов. Элементы, которые согласно этому условию должны быть
удалены для улучшения решения, отмечены справа точками. Значения
энергозатрат (4.1) и удельных энергозатрат (4.17) вычислены для
улучшенных вариантов (табл. 38, графы 5 и 7).
Примечание. На шаге 3
=
t
также можно было бы
воспользоваться условиями доминирования (4.33) и получить
оптимальное решение (строка 21).
Выбирая цикл с минимальными удельными энергозатратами
86)5;4(
3
=
ε
, выполняем последний шаг процесса, в результате которого
получаем все то же решение. Однако следует отметить, что если на втором
шаге оптимальное решение было получено с использованием условий
доминирования (табл. 37, строка 12), то без использования условий
доминирования такое же решение было получено только на шаге 4
=
t
и
после улучшения его на основе проверки второго необходимого условия

Страницы