ВУЗ:
Составители:
Рубрика:
69
Улучшить решение на основе двух известных необходимых условий
оптимальности невозможно: первое условие выполнено по построению,
второе условие не выполнено только для тройки
1,4,3, однако замена ее
на оптимальный участок
1;3 приведет к увеличению энергозатрат (из-за
смещения активного элемента 4
=
j
с третьей позиции на седьмую).
Энергозатраты, соответствующие полученному решению, согласно (4.1)
равны (
транзитные элементы, выделенные жирным шрифтом в (4.26),
игнорируются):
)(
1
μ
Э = 6·7 + 5·10 + 2·18 + 4·20 + 1·28 =236.
По сравнению с (4.25) энергозатраты увеличились, а следовательно,
метод наращивания цикла по убыванию веса не является общим, и от него
следует отказаться, несмотря на то, что он весьма эффективен в
вычислительном плане.
В связи с рассмотренным специально подобранным примером,
позволившим отказаться от ложной гипотезы, возникает вопрос: не явится
ли этот пример
непосильным и для модифицированного метода
расширения цикла? Используя те же табл. 25, 26, найдем решение
упомянутым методом.
На первом шаге (1
=
t
) поочередно в нулевой интервал 1;1
включается каждый из элементов множества
1
G . Порядок расчетов и
запись промежуточной информации (табл. 27) ведутся так же, как и в
табл. 21. Например, элемент
1
2 G∈=
γ
включается в интервал 1;1
посредством двух кратчайших маршрутов, взятых из табл. 26, что и
записано в графе 4 первой строки табл. 27.
1; ,5,4,1 1, ,5,4,1∪=22 2 .
На втором шаге получено оптимальное решение (табл. 27, строка 8),
при этом даже не потребовалось заполнять графу 7, поскольку при
равенстве количеств активных элементов (1)(:
2
=∀
γγ
r
n – графа 6)
упорядоченность по
)(
2
γε
r
совпадет с упорядоченностью по
),(
2
1
γ
rЭ
, что
следует из (4.17).
Страницы
- « первая
- ‹ предыдущая
- …
- 65
- 66
- 67
- 68
- 69
- …
- следующая ›
- последняя »
