Введение к работе
Актуальность работы. В традиционном динамическом программировании (ДП) оптимальность понимается в смысле экстремального значения выбранного скалярного критерия. Многие практически важные задачи не удается свести к однокритериальной постановке, поэтому в последнее время вопросу обобщения метода ДП на многокритериальный, нечёткий и иные случаи уделяется большое внимание. Этой теме посвящены работы Д. И. Батищева, С. П. Вовк, В. А. Емеличева, С. С. Мазуренко, А. Г. Ченцова, В. А. Перепелицы, В. И. Струченкова и др. Однако наиболее общей трактовкой понятия оптимальности является понятие выбора, а самым универсальным и удобным для анализа языком его описания признана функция выбора (ФВ). Использование такого подхода к совершенствованию методов ДП позволит значительно расширить круг решаемых задач.
Диссертационная работа выполнена в соответствии с планом госбюджетных научно-исследовательских работ ВГУИТ по теме «Математическое и компьютерное моделирование в задачах проектирования и оптимизации функционирования информационных технологических систем» (ГК № 01.2006.06298), а также в рамках гранта ФЦП «Научные и научно-педагогические кадры инновационной России на 2 009-2013 гг.» на тему «Разработка открытых информационных систем перерабатывающих производств» (ГК № П947).
Целью исследований является разработка новой методики моделирования выбора на множестве альтернатив, необозримом для лица, принимающего решения (ЛПР), в многоэтапных задачах, допускающих использование различных вариантов обобщения схемы динамического программирования.
Поставленная цель достигается посредством решения следующих задач:
-
Синтез математических моделей обобщения схемы динамического программирования посредством её описания в терминах функций выбора и сведения к задачам выбора оптимальных путей в графах различного типа.
-
Разработка на основе указанных моделей численных методов, позволяющих решать задачи оптимизации управления многоэтапными процессами, не решаемые традиционными способами.
-
Проверка адекватности разработанных моделей и эффективности предлагаемых методов.
-
Создание программных модулей, реализующих данные модели и методы.
Методы исследования. Выполненные исследования базируются на использовании аппарата теории графов, динамического программирования, теории бинарных отношений, теории выбора и принятия решений. Общей методологической основой является системный подход.
Научная новизна работы состоит в следующем.
-
-
Созданы математические модели обобщения схемы динамического программирования, отличающиеся использованием языка функций выбора для описания процесса поэтапной оптимизации на графах. Доказана адекватность предложенных моделей.
-
На основе данных моделей раработан класс алгоритмов поиска оптимальных путей на графах, использующих в качестве механизма выбора блокировку по бинарному отношению, не содержащему числовых критериев. Установлены достаточные условиея корректности применения этих методов.
-
В рамках указанного класса разработан новый численный метод, позволяющий решать задачи поэтапного выбора в условиях применения качественых шкал. Также разработан численный метод сужения множества недоминируемых альтернатив (МНА) при наличии эквивалентных решений. Проведено теоретическое обоснование обоих предложенных методов.
-
Создан программный комплекс, реализующий предложенные модели и методы, и использованный для проведения вычислительных экспериментов, подтверждающих эффективность указанных численных методов.
Практическая значимость работы состоит в построении комплекса инструментальных средств на основе новых моделей, численных схем и алгоритмов выбора на необозримом множестве альтернатив с использованием различных обобщений метода динамического программирования.
Достоверность и полнота результатов исследований подтверждена их практической реализацией при оптимизации загрузки оборудования и персонала ООО Ринг Авто (акт внедрения от «01» декабря 2012 года).
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на I Международной научно- практической интернет-конференции "Моделирование энергоинформационных процессов", Воронеж 2012; в рамках программы У.М.Н.И.К. на Региональной конференции "Инновационные технологии и материалы", Воронеж 2011; на III Международной научной конференции «Современные проблемы прикладной математики и математического моделирования», Воронеж 2009.
Публикации. По теме диссертации опубликовано 8 печатных работ, из них 4 - в изданиях, рекомендуемых ВАК РФ, и получено одно свидетельство о регистрации программы для ЭВМ.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 113 наименований. Основной текст изложен на 110 страницах без списка литературы. Работа содержит 14 таблиц, 17 рисунков. Приложения на двух страницах.
Личный вклад автора. Личный вклад автора заключается в постановке задач и их решении. Так, в работе [1] им разработана модель выбора, а так же доказана её корректность. В работах [2,4] автором поставлены задачи и предложены варианты их решения. После выбора одного из предложенных вариантов соавтором, автором доказаны необходимые теоремы и интерпретированы результаты. В работе [3] автором самостоятельно соединены в единый подход модели поэтапного принятия решений и механизм функций выбора. Полностью разработана и отлажена программа для ЭВМ [5]. В работах [6,8] автором сформулированы условия применения обобщенных методов, в [7] - предложена иерархическая структура задач ДП.
Похожие диссертации на Математическое моделирование функций выбора в обобщенном динамическом программировании
-
