Введение к работе
Актуальность темы. Моделирование и проектирование современных технических систем невозможно представить без применения вычислительной техники. При ^создании автоматизированных систем и их проектировании, прежде всего, возникает проблема выбора формальной модели представления систем. От модельного через алгоритмическое к программному обеспечению - таков путь современного моделирования и проектирования систем.
Необходимость в исследовании многокритериальных задач возникает в результате того, что при математическом моделировании достаточно сложных систем и объектов постановка скалярной (однокритериальной) задачи оптимизации не удовлетворяет потребностям лица, принимающего решение (ЛПР) , в связи с тем,., что построение обобщенных функций полезности (интегральной эффективности) является проблемой весьма сложной, а иногда неразрешимой. В то же время потребности практики разработки и эксплуатации сложных систем (в том числе биологических и социально-экономических) требует согласования значительного числа разнородных требований и целей. Следует отметить, что для лица, принимающего решение, существенно больший интерес представляет множество конкурирующих альтернатив (парето-оптимальных решений) по сравнению с. одним решением, оптимальным по какому-либо критерию или свертке критериев. Иными .словами, возникает проблема нахождения множества альтернатив.
Рассматривая задачу оптимального проектирования оросительных систем и систем магистральных водопроводов
для сельскохозяйственного водоснабжения, нельзя не учитывать то, что эту задачу необходимо формулировать в многокритериальной постановке, которая требует нахождения не одного оптимального решения, а множества альтернатив, например, паретовского множества. К настоящему времени проблема нахождения множества альтернатив исследована очень слабо, в том числе и для векторной (т.е. многокритериальной) задачи об остовных деревьях, которая возникает при проектировании закрытых оросительных систем. Исследованию этой задачи, а также построению достаточно эффективных алгоритмов ее решения посвящена настоящая диссертационная работа.
Для хотя бы частичного разрешения проблемы вычислительной сложности предлагается использовать математический аппарат предфрактальных графов. Таким образом, в настоящей работе также уделено внимание относительно малоизвестному математическому объекту, называемому термином «фрактальные графы». Появление фрактальных (предфрактальных) графов является логически закономерным следствием стремления возможно более адекватно моделировать реальные геофизические, экономические, социальные явления и объекты с помощью математического аппарата теории графов. В настоящей работе предлагается использовать предфрактальныи граф в том определении, которое впервые было сформулировано В.А. Перепелицей.
Цель работы. Основной целью работы является: исследование сложности задачи об остовных деревьях, которая возникает при проектировании закрытых оросительных систем, в многокритериальной постановке;
вычисление максимальной мощности паретовского множества векторной задачи об остовных деревьях; доказательство свойства полноты задачи об остовных деревьях для случая, когда ее векторная целевая функция содержит наряду с весовыми и топологические критерии; выделение полиномиально разрешимых классов векторных задач и построение статистически эффективного алгоритма; исследование топологических и метрических свойств фрактальных и предфрактальных графов; построение и обоснование декомпозиционного статистически эффективного алгоритма.
Методы исследований. В диссертационной работе использованы понятия и методы теории графов, теории вероятностей, комбинаторики и математического программирования.
Научная новизна. Предлагается решить задачу проектирования закрытой оросительной системы для сельскохозяйственного водоснабжения, используя теоретико-графовые модели и алгоритмы решения задачи об остовных деревьях в многокритериальной постановке. Дана оценка вычислительной сложности рассамтриваемой задачи. Рассмотрены 2-критериальные задачи об остовных деревьях, у ВЦФ которых первый критерий представляет собой весовой критерий вида MINSUM и MINMAX, а второй критерий является топологическим; построен статистически эффективный алгоритм, использующий принцип декомпозиции. Предлагается использовать в определении допустимого решения понятие предфрактального дерева. Получены верхние и нижние оценки радиуса и диаметра предфрактальных графов;
формулы вычисления максимальной степени остовного предфрактального дерева на предфрактальном и фрактальном графе.
Практическая ценность. При разработке
математического обеспечения системы автоматизированного проектирования закрытых оросительных систем возникают многокритериальные задачи об остовных деревьях для решения которых применимы предлагаемые теоретико-графовые модели и малотрудоемкие алгоритмы решения соответствующих задач об остовных деревьях. Практическая ценность полученных результатов заключается в том, что приемлемые проектные решения в условиях многокритериальное получаются при резком сокращении объемов вычислений. При этом, в отличии от традиционных оптимизационных моделей, предлагаемые подходы позволяют учитывать в системном единстве все показатели качества, что является принципиально важным с точки зрения практического применения. Идеи доказательства статистической эффективности предложенных в диссертации алгоритмов могут быть также применены в дальнейших исследованиях для построения и обоснования новых методов дискретной многокритериальной оптимизации.
Достоверность полученных результатов. Представленные в диссертационной работе теоремы и леммы имеют строгое математическое обоснование.
Апробация работы. Основные результаты диссертации докладывались на Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 1996г.); на
Международном коллоквиуме по применению математики в архитектуре и строительстве (Веймар, 1997г.); на Международном конгрессе математиков (Берлин, 1998г.); на научных конференциях «Гагаринские чтения» (Москва, 1997г., 2000г.); на Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 1996, 1997, 1998, 2000гг.); на научно-практических конференциях КЧГТИ (Черкесск, 1995, 1997гг.) и научных семинарах кафедры прикладной математики и информатики КЧГТИ, г. Черкесск.
Публикации. По теме диссертации опубликовано 15 работ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы, содержащего 37 наименований. Содержание изложено на 123 страницах.