Введение к работе
Актуальность темы. Задача о назначениях (ЗОН), её линейные, квадратичные и многоиндексные разновидности привлекают внимание исследователей ввиду своей обширной применимости в различных областях научной и практической деятельности. К ним сводятся задачи, связанные с оптимальным распределением элементов на микросхемах, задачи планирования работы вычислительных, производственных, технологических систем, оптимизации перевозок, а также задачи составления расписаний. Содержательная постановка данной задачи формулируется следующим образом: пусть имеется п работ и п претендентов для выполнения этих работ. Назначение претендента / на работу у связано с затратами с (/, j = 1, п). Требуется определить назначение, дающее минимальные суммарные затраты, при этом каждого претендента можно назначить только на одну работу, и каждая работа может быть занята только одним кандидатом. С комбинаторной точки зрения допустимое решение этой задачи представляет собой перестановку ж = (ж1,...,жп)чисел 1, ..., п, а
соответствия вида /—>тг. (/= 1,п)описывают произведённые назначения (/, тг.)(/-й претендент назначен на работу с номером тт.). Тогда задача сводится к определению
такой перестановки ж', которая минимизирует линейную целевую функцию У"| сіж .
;=1
Данная задача, называемая линейной закрытой ЗОН, относится к задачам дискретной оптимизации и является частным случаем транспортной задачи. Для неё существуют точные методы решения, такие как венгерский алгоритм, метод потенциалов, метод ветвей и границ. Однако дополнительные требования, обусловленные практическими задачами, приводят к различным модификациям математической модели: изменению стандартных, добавлению новых ограничений, а также появлению многокритериальности. Для модифицированных моделей, по-прежнему являющихся задачами дискретной оптимизации, известные методы зачастую не применимы, что требует разработки специальных подходов к нахождению решения - точного или приближённого. Основные исследования ЗОН связаны с изучением различных целевых функций при стандартных ограничениях (R.Burkard, М. R.Garey, D. S.Johnson, О.Gross, R. М.Кагр, Э. Х.Гимади) или с применением линейной свёртки критериев (И. В.Сергиенко, В. А. Емеличев, В. А.Перепелица, P. Aneja).
Актуальность диссертационной работы обусловлена необходимостью разработки моделей для задачи о назначениях с дополнительными требованиями, которые отражаются в многокритериальности и появлении специфических ограничений, а также методов для нахождения точных и приближённых решений формируемых дискретных оптимизационных задач, основанных как на модификации известных алгоритмов, так и на оригинальных подходах, базирующихся на теории двойственности и учитывающих иные стратегии агрегирования.
Диссертационная работа выполнена в рамках одного из основных научных направлений Воронежского государственного университета «Математическое моделирование, численные методы и комплексы программ».
Цели и задачи исследования. Целью диссертационной работы является разработка комплекса моделей и методов для решения задачи о назначениях с дополнительными требованиями, которые выражаются в многокритериальности и появлении специфических ограничений.
Для достижения цели в работе решаются следующие основные задачи:
-
Анализ алгоритмов решения классической ЗОН и исследование направления их усовершенствования.
-
Разработка математических моделей для ЗОН с дополнительными условиями, связанными с изменением стандартных, добавлением новых ограничений, а также с появлением многокритериальности.
-
Разработка алгоритмов решения поставленных задач, учитывающих структурные особенности моделей, и оценка их сложности.
-
Разработка программного комплекса для проведения вычислительного эксперимента и рекомендаций по использованию разработанных методов в зависимости от типов задач и их размерности.
Методы исследования основаны на дискретной оптимизации и, в частности, теории двойственности, на исследовании операций и теории принятия решений. При написании программного комплекса использовалась технология модульного программирования и объектно-ориентированный подход.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
комплекс оптимизационных моделей для задачи о назначениях, учитывающий дополнительные требования (предпочтения, запреты, конфликты) к матрице назначений и наличие нескольких критериев, отличительной особенностью которого является существование в структуре каждой из моделей как ограничений, формализующих дополнительные требования, так и ограничений стандартной задачи о назначениях, что позволяет использовать в ходе решения венгерский алгоритм;
аналитическое доказательство существование решения задачи о назначениях с запретами, обосновывающее модификацию матрицы затрат, что позволяет получить точное решение на основе венгерского алгоритма;
аналитические доказательства совместности системы ограничений многокритериальных задач о назначениях, основанные на оценке нижней границы количества претендентов в задаче и позволяющие оценить ее разрешимость;
комплекс численных методов для решения задач о назначениях с дополнительными требованиями, отличающийся использованием в качестве базовой процедуры венгерского метода или двойственного алгоритма Удзавы и позволяющий получить оптимальное или субоптимальное решение в зависимости от размерности задачи, параметров, а также требований по времени;
комплекс численных методов для решения многокритериальных задач о назначениях, основанных на переходе к одноцелевой задаче о назначениях с последующим применением алгоритма Удзавы, отличающихся способами построения функции Лагранжа и применением на каждой итерации венгерского алгоритма или независимой минимизации по столбцам в зависимости от альтернативных вариантов множества ограничений, и обеспечивающих получение субоптимального решения;
утверждение об эквивалентном преобразовании нелинейной оптимизационной модели для задачи о назначениях с возможностью обучения к линейной, позволяющее применить алгоритм Удзавы для нахождения субоптимального решения;
совокупность утверждений о полиномиальной сложности разработанных методов, гарантирующих получение оптимального или субоптимального решений за конечное число итераций и обеспечивающих сравнительный анализ методов;
структура программного комплекса, включающая инвариантную составляющую, в которой реализованы базовые методы, и проблемно-ориентированную со-
ставляющую для решения задач о назначениях с дополнительными ограничениями и несколькими критериями оптимальности, отличительной особенностью которого является возможность формирования информационной среды задачи и динамического выбора метода для ее решения.
Тематика работы соответствует следующим пунктам Паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»: п. 2. Развитие качественных и приближенных аналитических методов исследования математических моделей; п. 3. Разработка, обоснование и тестирование эффективных вьшислительных методов с применением современных компьютерных технологий; п. 5. Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вьшислительного эксперимента.
Практическая значимость работы. Предложенные в диссертации математические модели, в которых учтены различные ограничения и возможность введения дополнительных критериев оптимальности, качественным образом расширяют множество известных моделей ЗОН и могут быть использованы как в теоретических исследованиях, где задача о назначениях является базовой моделью, так и при решении прикладных задач. Разработанные методы, базирующиеся на двойственном алгоритме Удзавы, составили алгоритмическую основу для программного комплекса, позволяющего сформировать информационную среду и найти точное и/или приближенное решение для модифицированных ЗОН. Разработанные модели, методы, а также рекомендации, полученные на основе вьшислительного эксперимента, могут оказаться полезными в задачах оптимизации вьшислительных процессов, планировании муль-тиресурсных систем, при составлении расписаний.
Реализация и внедрение результатов работы. Результаты диссертационной работы используются в АУ ВО «Институт регионального развития» (г. Воронеж) для решения задач подбора кадров и управления персоналом, а так же в учебном процессе ФГБОУ ВПО «Воронежский государственный университет» при чтении спецкурсов и выполнении выпускных квалификационных работ.
Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на следующих международных и всероссийских конференциях: Международная школа-семинар «Системное моделирование социально-экономических процессов» (Воронеж, 2008, Вологда, 2009); Ежегодная Международная конференция КРОМШ (Симферополь, 2010-2011); Международная научно-техническая конференция «Аналитические и численные методы моделирования естественнонаучных и социальных проблем» (Пенза, 2011); Всероссийская молодежная научная школа«Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 2012); Международная конференция «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2012); Международной конференции «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2013).
Публикации. Основные результаты диссертации опубликованы в 12 научных работах, в том числе 3 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежат: [1] - математическая модель двукритериальной ЗОН с возможностью обучения и детальная разработка двойственного метода её решения; [2] - детальная разработка и наполнение шагов двойственного метода решения многокритериальной трёхиндексной ЗОН; [4] - введение запретов в математическую модель трёхиндексной ЗОН; [5] - математическая мо-
дель ЗОН с возможностью обучения претендентов и метод её решения; [6] - математические модели задач и конкретизация их решения на основе венгерского алгоритма, теорема о величине «штрафа» в задаче с запретами; [9] - введение нормировки целевых коэффициентов и строк матрицы вероятностей; [10] - модуль программы, связанный с учётом дополнительных условий; [11] - подходы к моделированию ЗОН с дополнительными условиями и их решению с использованием венгерского алгоритма и двойственного алгоритма Удзавы.
Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка используемых источников из 117 наименований, и приложений. Основная часть работы изложена на 137 страницах и включает 17 рисунков и 7 таблиц.
