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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

127
Выводы
1.
Определение экстремальных точек на графе (минисуммных и
минимаксных) согласно рассмотренной методике выполняется в два этапа:
-
построение полного множества кратчайших маршрутов
(предварительный этап);
-
размещение
R
точек
(
)
Rrx
r
,1= на графе, удовлетворяющих
заданным требованиям, методом перемещений.
2.
Решения минисуммной и минимаксной задач совпадают по мере
увеличения числа точек
R
, покрывающих граф. При n
R
=
покрывающие
точки находятся в вершинах графа, а значения целевых функций равны
нулю.
3.
Решение минисуммной задачи соответствует вершинам графа.
4.
Решение минимаксной задачи, как правило, лежит на ребрах
графа (граф неориентированный, смешанный) или в вершинах (граф
ориентированный).
ЗАКЛЮЧЕНИЕ
Любая сложная практическая задача, математическую модель которой
не удается представить в форме, доступной для решения и анализа
известными методами, требует поиска и разработки новых подходов и
методов решения. Поиск таких подходов и методов, как правило,
начинается с
неформального анализа задачи, сопутствующих ей
условий, частных случаев, отражающих отдельные её стороны, изучение
которых раскрывает проблему в целом и позволяет наметить наиболее
перспективные пути дальнейших исследований.
Задача коммивояжера, весьма простая в своей концептуальной
постановке, является довольно сложной для формализации и ещё более
сложной для решения, особенно в том случае, когда речь идёт о
задаче
большого размера )500( >
n . На первый план при этом выступают
неформальные (эвристические) методы, основанные, как правило, на
использовании некоторых специфических особенностей задачи или её
физических аналогов.
Особенностью комбинаторных задач, к которым относится и задача
коммивояжера, является невозможность применения хорошо
разработанного
классического аппарата бесконечно малых. Это в
основном и обусловливает сложность их решения. Поиск специальных
приёмов и методов для их преодоления, применительно к задаче

Страницы