Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
3.5.1. Многообразие целевых функций
Накопленный к настоящему времени опыт математического моделирования свидетельствует о существовании достаточно широкого класса задач дискретной оптимизации с допустимыми решениями в виде остовных деревьев некоторых графов. В этом классе качество допустимых решений оценивается различными целевыми функциями или, в другой терминологии, критериями. Множество этих критериев принято делить на две части – критерии весового вида и критерии комбинаторные. Пусть для данного 
-вершинного графа 
множество допустимых решений (МДР) 
состоит из остовных деревьев 
, 
, удовлетворяющим определенным условиям. Если ребрам 
приписаны веса 
, то наиболее известными являются весовые критерии вида MINSUM (MAXSUM)
(3.9)
и вида MINMAX (MAXMIN)
(
).(3.10)
Наиболее известными комбинаторными критериями являются: минимизируемая степень остовного дерева
(3.11)
и максимизируемый диаметр остовного дерева
(3.12)
Перечень критериев (3.9)-(3.12) можно продолжить, однако более важно отметить, что указанное многокритериальное многообразие в контексте практических целей моделирования приводит к многокритериальным задачам об остовном дереве.