Введение к работе
Актуальность темы исследования и степень разработанности проблемы. Многие практические проблемы сводятся к известной задаче о назначениях (ЗОН), которая относится к задачам дискретной оптимизации, и для её решения известно несколько алгоритмов (венгерский метод, методы ветвей и границ и динамического программирования). Однако её многочисленные модификации и обобщения, в том числе многоиндексные постановки и ЗОН с неполными и неточными исходными данными в алгоритмическом плане освоены далеко не полностью и требуют дальнейших исследований.
Для трёхиндексных и других многоиндексных задач о назначениях, которые являются TVP-трудными, существует проблема построения алгоритмов для нахождения приближённого (субоптимального) решения. Усовершенствованию алгоритмов посвящено множество работ, в которых прослеживаются несколько основных подходов: постановка и решение ЗОН на графах (Y. Сга-ma, L. Kaufman, Э. X. Гимади, Н. М. Коркишко), построение алгоритмов на основе метода ветвей и границ с различными вариантами ветвления и фиксации переменных (Е. Balas, R. Е. Burkard, М. Vlach, Э. X. Гимади, И. П. Воз-нюк), применение метода лагранжевой «релаксации» (D. Magos, P. Camerini, М. К. Кравцов, С. А. Дичковская), модификация известных алгоритмов решения двухиндексных задач (L. Kaufman, С. И. Сергеев). Практически не проводятся исследования, связанные с построением быстрых «жадных» алгоритмов и повышением их эффективности. Известные методы такого типа (R. М. Aiex, Л. Г. Раскин, И. О. Кириченко) дают слишком «грубое» решение. Существует необходимость в их улучшении для работы с задачами больших размерностей, возникающими на практике, что возможно осуществить за счёт построения итеративного алгоритма, учитывающего результаты предыдущих шагов.
Обобщённые ЗОН с интервальными и нечёткими данными возникают в результате формализации неопределённости, присущей многим практическим задачам. Для них не существует единого подхода в определении понятия оптимальности решения и условий его существования, поэтому различны и подходы к построению алгоритмов решения (R. Е. Steuer, F. Mraz, В. И. Левин, С. П. Шарый), что является стимулом к дальнейшему исследованию в этой области.
Таким образом, актуальность темы диссертационного исследования обусловлена необходимостью совершенствования методов для нахождения решения обобщённых и модифицированных ЗОН на основе «жадных» стратегий и приближённой исходной информации.
Диссертационная работа выполнена в рамках одного из основных научных направлений Воронежского государственного университета «Математическое моделирование, программное и информационное обеспечение, методы вычислительной и прикладной математики и их применение к фундаментальным исследованиям в естественных науках».
Цели и задачи исследования. Целью диссертации является исследование моделей обобщённых задач о назначениях и разработка методов их реше-
ния на основе усовершенствования «жадных» стратегий и развития подходов к определению оптимальности решения для задач с неточными данными. Для достижения цели в диссертации решаются следующие задачи:
-
Анализ методов решения обобщённых ЗОН (многоиндексных и с неточными данными) с целью выявления их особенностей, а так же исследование направлений их усовершенствования.
-
Разработка адаптивных методов для решения аксиальной и планарной трёхиндексных ЗОН.
-
Разработка модели многокритериальной трёхиндексной ЗОН и адаптивных методов ее решения.
-
Развитие подходов к определению оптимальности решения для ЗОН в условиях неопределённости и нахождению области его устойчивости.
-
Разработка программного обеспечения для решения трёхиндексных задач о назначениях и задач с неточными данными.
Методы исследования. В диссертационной работе использовались методы дискретной оптимизации, исследования операций, теории вероятностей, интервальная и нечёткая арифметики. При написании программного комплекса использовалась технология модульного программирования и объектно-ориентированный подход.
Результаты, выносимые на защиту, и их научная новизна:
-
модель многокритериальной задачи о назначениях, структура которой основана на разбиении переменных на группы, для каждой из которых определена целевая функция, и в постановке имеют место как ограничения стандартной задачи, так и дополнительные связующие ограничения;
-
утверждения, определяющие вид условия локального улучшения для каждой из трёхиндексных задач, позволяющие построить адаптивные аналоги «жадных» алгоритмов за счёт перехода к вероятностной постановке задачи и модификации процедуры поиска минимального элемента;
-
комплекс численных методов, включающий адаптивные алгоритмы для решения трёхиндексных задач о назначениях (аксиальной, планарной и многокритериальной), отличительными признаками которых являются альтернативные варианты задания полных групп событий и учёт оценок предыдущих шагов за счёт пересчёта вероятностей и углубления памяти алгоритма, что позволяет улучшить результат «жадных» алгоритмов, сохраняя их вычислительную сложность на каждом шаге;
-
совокупность утверждений, касающихся разрешимости интервальной задачи о назначениях и оценки устойчивости найденного решения: о существовании оптимального решения с учётом введённого определения оптимальности; о нахождении области устойчивости оптимального решения стандартной задачи о назначениях; о допустимых изменениях целевых коэффициентов интервальной задачи для получения оптимального решения;
-
утверждение о том, что в полной нечёткой задаче о назначениях оптимальное решение не может быть нечётким, поэтому целесообразно рассматривать задачу только с нечёткой целевой функцией, для решения которой раз-
работаны методы, основанные на решении для каждого уровня интервальных задач с последующим применением венгерского или адаптивного алгоритмов;
6) программный комплекс, включающий реализацию предложенных методов решения обобщённых задач о назначениях, структура которого отличается возможностью динамического выбора алгоритма в зависимости от типа исходных данных и структуры задачи.
Область исследования. Тематика работы соответствует следующим пунктам Паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»: п. 2. «Развитие качественных и приближенных аналитических методов исследования математических моделей»; п. 3. «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; п. 4. «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».
Практическая и теоретическая значимость диссертации и использование полученных результатов. Результаты диссертации, сформулированные в виде утверждений, расширяют теоретическую базу для многих прикладных задач, в которых ЗОН является базовой моделью, а также для решения других задач дискретной оптимизации (например, для задачи о минимальном покрытии и задачи коммивояжёра). Предложенный подход к определению понятия оптимальности, а также утверждения, определяющие область устойчивости решения ЗОН, позволяют существенно упростить исследование дискретных задач с интервальными данными.
Теоретические результаты диссертации используются в учебном процессе Воронежского государственного университета при чтении спецкурсов и выполнении курсовых и выпускных квалификационных работ.
Предложенные в диссертации подходы к решению различных ЗОН позволяют повысить обоснованность принимаемых решений в сложных системах различного назначения, в том числе, при оптимизации вычислительных и производственных процессов. Практические результаты диссертации в форме программного комплекса используются в деятельности ОГБУ «Агентство по инвестициям и стратегическим проектам» (акт № 51/1-01-11-542).
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Международная конференция «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2013); Международная конференция «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2012); VI Международная научно-техническая конференция «Аналитические и численные методы моделирования естественнонаучных и социальных проблем» (Пенза, 2011); Ежегодная международная конференция КРОМШ (Симферополь, 2010-2011); Международная школа-семинар «Системное моделирование социально-экономических процессов» (Воронеж, 2008), а также на ежегодных научных конференциях Воронежского государственного университета.
Публикации. Основные результаты диссертации отражены в 13 опубликованных работах, в том числе, 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит: [1, 2] - решение задачи по /л; [2] - математическая модель многокритериальной трёхиндексной ЗОН; [4] - утверждение о сведении полной нечёткой ЗОН к задаче с нечёткой целевой функцией, алгоритм решения на основе венгерского метода; [5] - «жадные» алгоритмы решения трёхиндексной ЗОН; [6] - детальная разработка «жадного» и адаптивного алгоритмов; [9] - переход от нечёткой к интервальной ЗОН, алгоритм решения нечёткой задачи с использованием адаптивного алгоритма; [10] - модуль программы, связанный с использованием приближённой информации при решении задач в условиях неопределённости; [11] - адаптивный алгоритм решения трёхиндексной ЗОН, исследование возможности корректировки целевых коэффициентов стандартной ЗОН при сохранении оптимального решения.
Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка используемых источников из 169 наименований и приложения; изложена на 147 страницах основного текста и включает 30 рисунков и 15 таблиц.
