Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

3.5.1. Многообразие целевых функций

Накопленный к настоящему времени опыт математического моделирования свидетельствует о существовании достаточно широкого класса задач дискретной оптимизации с допустимыми решениями в виде остовных деревьев некоторых графов. В этом классе качество допустимых решений оценивается различными целевыми функциями или, в другой терминологии, критериями. Множество этих критериев принято делить на две части – критерии весового вида и критерии комбинаторные. Пусть для данного -вершинного графа  множество допустимых решений (МДР)  состоит из остовных деревьев , , удовлетворяющим определенным условиям. Если ребрам  приписаны веса , то наиболее известными являются весовые критерии вида MINSUM (MAXSUM)

 (3.9)

и вида MINMAX (MAXMIN)

  ().(3.10)

Наиболее известными комбинаторными критериями являются: минимизируемая степень остовного дерева

 (3.11)

и максимизируемый диаметр остовного дерева

 (3.12)

Перечень критериев (3.9)-(3.12) можно продолжить, однако более важно отметить, что указанное многокритериальное многообразие в контексте практических целей моделирования приводит к многокритериальным задачам об остовном дереве.