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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

93
Оптимизация по критерию энергозатрат во всех случаях (строки 5 – 8)
обеспечила оптимальное решение, что, однако, не является гарантией того,
оптимальности решения для любых вариантов исходной
информации
с и а.
В вычислительном плане наиболее удобными можно считать методы
последовательного наращивания цикла, для использования которых
требуется иметь матрицу кратчайших маршрутов. Впрочем, такая матрица
необходима и для решения задачи другими методами, кроме
немодифицированного метода расширения цикла.
Выводы
1. Все четыре метода минимизации длины пути коммивояжера
(табл. 39, строки 1 – 4) обеспечивают решения, близкие к оптимальному.
Модифицированный метод расширения цикла дал точное решение.
Проверка необходимых условий оптимальности позволила вдвое снизить
погрешность решений (стрóки 1 и 3).
2. Рассмотренные методы минимизации энергозатрат (строки 5 – 8)
после улучшения решений на основе проверки необходимых условий
оптимальности обеспечили получение
оптимальных решений.
3. Решение, оптимальное по критерию длины цикла (табл. 39,
строка 2), при незначительном увеличении пути коммивояжера (
%5,2<
,
строка 5) вдвое увеличивает его энергозатраты.
4. Методом последовательного наращивания цикла (табл. 39, строка 5)
получено решение тестового примера, заимствованного из [17]. Длина
пути более чем на 4 % меньше, чем в [17]. Уменьшение длины пути
получено за счёт ослабления ограничения об
однократности посещения
каждого пункта (в пункте 4=
j
коммивояжер побывал дважды). Отказ от
указанного жесткого ограничения неизбежен, если матрица расстояний
с
не является полной )1( <
ϕ
. О возможности получения решения при 1
<
ϕ
в
[17] информация отсутствует.
6. ПРОПУСКНАЯ СПОСОБНОСТЬ СЕТИ
6.1. Построение маршрута с максимальной пропускной способностью
методом улучшения оценок
Исходной информацией в задаче о пропускной способности является
граф ),(
M
A
G
= с An = вершинами и Mm
=
дугами. Для постановки и
решения задачи используется задание графа в виде
взвешенной матрицы
пропускных способностей
ji
с
,
=с , где
ji
c
,
– вес дуги ),(
j
i . Если в

Страницы