Введение к работе
Актуальность проблемы
Задаче о назначениях и различным ее модификациям посвящено множество научных исследований, поскольку она сама по себе имеет немалое число приложений в практической сфере и, кроме того, к ней сводятся многие задачи из дискретной математики, теории оптимизации. В результате исследований получен ряд алгоритмов для ее решения.
В настоящее время исследуются различные расширения, обобщения и модификации классической задачи о назначениях, например, квадратичная задача о назначениях, многокритериальная задача о назначениях, случайная задача о назначениях, задача о равномерном назначении и др., разрабатываются эффективные алгоритмы решения как обобщенных задач, так и сужения задач, полученных в результате дополнительных ограничений и условий. Задача о назначениии в различных ее вариантах, несмотря на существование эффективных общих методов решений, не потеряла своей актуальности, поскольку она представляет большой практический интерес. Возникающие в практической сфере различные модификации задачи заставляют искать более быстрые и эффективные алгоритмы, привязанные к дополнительным условиям задачи и учитывающие ее конкретную специфику.
Простейшая постановка задачи о назначениях состоит в следующем. Имеется п работников различных профессий &ь&2, ->&»» і которые должны выполнить п работ t\,t2,...,
Если число претендентов отличается от числа работ, которые необходимо выполнить, то такую задачу принято называть "несбалансированной" задачей о назначениях. В таком случае число претендентов на выполнение работ, конечно, должно быть не меньше числа самих работ, иначе задача неразрешима.
Данная задача может быть сведена к задаче о максимальном потоке в сети или к задаче о нахождении наибольшего паросочетания; можно представить эту задачу как задачу линейного программирования. Соответственно, и разрешима она может быть различными методами: с
ЗЩГЛ
Cfletei ОЭ МО
помощью алгоритмов нахождения максимального потока, венгерским методом нахождения наибольшего паросочетания, симплекс-методом и
ДР.
Задача усложняется при добавлении некоторых оптимизационных условий. Говоря о классической постановке задачи о назначениях, имеют в виду оптимизационную задачу с критерием - стоимостью затрат назначения, которую необходимо минимизировать, либо с критерием - суммой доходов, которую желательно максимизировать.
Исследованием классической задачи о назначениях занимались такие математики, как Р.Басакер, Т.Саати, Т.Ху, Г.Вагнер, Н.Кристофидес, Х.Кун и др.
Развитие вычислительной техники позволяет решать все более сложные, требующие больших объемов вычислений, задачи. Это влияет и на развитие математических методов решения, на построение новых математических моделей для решения реальных прикладных задач, исследование которых показывает, что практическая задача редко характеризуется оптимизацией лишь одного критерия. Как правило, принимая решение в той или иной задаче управления, приходится иметь дата с несколькими критериями и оценивать решение не по одному параметру. Так последнее время большое внимание уделяется исследованию многокритериальных задач, которые характеризуются наличием нескольких целевых функций вместо одной в однокритериальных задачах. Сложность нахождения решения многокритериальных оптимизационных задач связана с тем, что целевые функции, выступающие в качестве критериев оптимизации, во многих случаях конфликтуют между собой. Таким образом, оптимизировать решение сразу по всем целевым функциям возможно далеко не всегда.
Для того, чтобы отбирать более предпочтительные решения, надо уметь их сравнивать. В лучшем случае можно было бы ввести отношение линейного порядка на множестве значений критериев. Отношение линейного порядка можно ввести с помощью метода, называемого сверткой критериев. Он состоит в конструировании скаляризующей функции s : if -* R, где к - число критериев, каждый из которых имеет вещественные или целочисленные значения. И если у - вектор значений критериев, то оптимизация s(y(x)) на множестве допустимых решений х приводит к получению решения А;-критериальной задачи. В практических приложениях часто осуществить этот метод довольно сложно из-за сложности отношений между критериями, если критериев достаточное число.
Однако можно ввести отношение частичного порядка на том же
множестве значений критериев, которое может и не дать возможность определить среди всех допустимых решений элемент с максимальным (в смысле введенного частичного порядка) значением многомерного критерия, но может дать возможность определить элемент со значением критерия, над которым нет большего, т.е. недоминируемого значения.
Пустьу(х) = (у1(х),у2(х),...,у*(х)) - А;-мерная критериальная фунь
ция на множестве допустимых значений X со значениями в it. Введем
следующее отношение частичного порядка на множестве критериаль
ных значений Y С Rk.
Уі -< У2, если у\ < у\ для і = 1, к.
Тогда у - недоминируется на Z, если не существует такого у є Z, что у -< у и у ф у. Согласно введенного отношения частичного порядка -< можно поставить задачу найти решение х, для которого значение критерия является не доминируемым. Такое решение называется эффективным или оптимальным по Парето. Нахождение эффективных решений имеет большое значение, так как только эти решения являются претендентами на оптимальность, если оптимальное решение вообще существует на множестве допустимых решений.
В зависимости от вводимого отношения порядка на множестве значений критериев можно получить различные оптимальные решения. В случае, когда критерии оптимизации можно упорядочить по предпочтению, можно ввести лексикографический порядок на множестве критериальных векторов, что может позволить многокритериальную задачу свести к последовательности однокритериальных задач.
Решению и исследованию многокритериальных оптимизационных задач посвящен довольно широкий ряд работ И.И.Меламеда и И.Х.Сигала1. В этих работах кроме полученных общих теоретических результатов: методов нахождения оптимальных по Парето решений, метода линейной свертки критериев и др. - представлены и данные обширных вычислительных экспериментов по решению двух- и трех-критериальных задач с критериями вида MINSUM и MINMAX.
1 Меламед И.И., Сигал И.Х. Вычислительное исследование трехкритериальных задач о деревьях и назначениях. Ж. вычислит, матем. и матем. физики, 1998, Т.38. 10. С.1780-1787.
Меламед И.И., Сигал И.Х. Задачи комбинаторной оптимизации с двумя и тремя критериями. ДАН, 1999, Т.Збб. 2. С.170-173.
Меламед И.И., Сигал И.Х. Бикритериальные задачи дискретного программирования с MINSUM-MINSUM критериями. М.: ВЦ РАН, 2000.
Меламед И.И., Сигал И.Х. Распределение эффективных решений в некоторых оикритериальных задачах дискретного программирования. М.: ВЦ РАН, 2001.
Общие теоретические положения теории принятия решений при многокритериальной оптимизации можно найти, например, в работах Р.Штойера, Р.Л.Кини и Х.Райфы 2.
Лексикографической многокритериальной оптимизации и сложности алгоритмов решения оптимизационных задач со многими критериями посвящены, например, исследования Бондаренко В.А., Клоедена П.Е., Краснова М.В.3
В настоящей работе рассматривается расширение задачи о назначениях, связанное с усложнением структуры плана работ, рассчитанного на период в несколько дней, в связи с чем любой работник может выполнять несколько работ плана при условии, что ежедневно любой работник не может выполнять более одной работы. Таким образом, необходимо разрешить систему задач о назначениях на каждый день плана, причем в качестве исполнителей в "ежедневных" задачах о назначениях берется одно и то же множество. Поэтому задачи не могут решаться независимо друг от друга, т.е. решение полученной системы задач не может быть сведено к решению нескольких задач назначений на каждый день. В итоге каждый г-й работник получает х,- определенных назначений.
Оптимизационный характер данная задача приобретает при введения критерия оптимизации, но в отличие от классической постановки критерием в рассматриваемой задаче является функционал равномерности, минимизация которого должна привести к наиболее равномерному распределению работ между исполнителями.
Если в классической постановке критерием выступает линейный функционал, что позволяет применять для решения этой задачи соответствующие методы, например, методы решения задач линейного программирования, то в задаче, исследуемой в данной работе, критерий может являться нелинейным.
В настоящей диссертационной работе поставлена задача о равномерном назначении и ее обобщения: введена возможность обязательных назначений и вектор желаемого числа работ для каждого исполнителя; получены алгоритмы их решений. В отличие от задачи, приведен-
2Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. М.: Радио и связь, 1992.
Кипи Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981.
'Бондаренко ВА, Клоеден П.Е., Краснов М.В. О лексикографической оптимизации в многокритериальных дискретных задачах. Автоматика и телемеханика. 2, 2000.
ной в работах Рублева B.C. и Кропанова ВА 4, задача о равномерном назначении расширена дополнительной возможностью выбора каждым рабочим определенных работ в любой день, что заметно усложняет ее решение.
Кроме описанной задачи в настоящей работе приводятся исследования и решения бикритериальных задач о назначениях с двумя критериями: критерием равномерности и критерием стоимости; рассматривается лексикографическая оптимизация, которая в задаче с двумя критериями имеет два варианта. Решения задач в обоих случаях будут иметь равные значения критериев оптимизации, если множества решений двух соответствующих однокритериальных задач имеют непустое пересечение, т.е. существует оптимальное решение сразу по обоим критериям.
Задача о равномерном назначении рассматривается с критерием -квадратичным отклонением, хотя в качестве критерия оптимизации можно было взять и другие функционалы. Какой критерий позволит получить наиболее приемлемое решение задачи, какими свойствами он должен обладать? Во многих оптимизационных задачах выбор критерия производится из общих соображений, интуитивно. В данной диссертационной работе проводится исследование свойств функционалов, используемых в качестве критериев равномерности.
Изучение вопросов, связанных с необходимыми свойствами критериев и решений задачи, к которым приводит оптимизация этих критериев, позволило доказать утверждение о том, что выбор одного из критериев - критерия среднеквадратичного отклонения - является наиболее выгодным в условиях рассматриваемой задачи, так как его оптимизация позволяет получить решения, которые оптимизируют и любой другой, возможный, критерий.
Задачи, в которых нет нужды выбора критерия среди множества возможных, представляют определенный интерес. Какие свойства оптимизационной задачи позволяют ей иметь приоритетный критерий оптимизации? Попытки ответить на этот вопрос привели к построению задачи не дискретного характера, обладающей описанным свойством и имеющей областью допустимых решений область, аналогичную области допустимых решений в рассматриваемой задаче о назначениях. И в этой построенной задаче замечательным свойством приоритетности обладает тот же функционал квадратичного отклонения.
4Кропанов В. А., Рублев В. С, Задача о равномерном назначении работ и ее обобщения //Моделир. и анализ информ. систем. Ярославль, 2000. 1.1, 2.
Методы исследования
В диссертационной работе были использованы идеи характеристического свойства оптимального решения оптимизационной задачи о равномерном назначении Рублева B.C.
Использовался алгоритм Форда-Фалкерсона нахождения максимального потока в сети5.
Использовалось свойство оптимального решения задачи о назначениях о том, что в дополнительной сети не может быть контуров отрицательной стоимости, приводимое во многих работах, в которых рассматривается задача о назначениях, например, в работах Т.Ху6, Р.Басакераи Т.Саати.
Использовались теоремы о реберных разбиениях графа на циклы и цепи7.
Доказательство приведенных в диссертационной работе теорем и построение алгоритмов получены аналитическими методами.
Цели работы
1) В диссертационной работе формулируются и иссследуются свой
ства оптимальных решений следующих обобщений задач о назна
чениях:
задача о равномерном назначении;
задача о равномерном назначении с учетом обязательных назначений;
задача о назначении, приближенном к желательному вектору числа назначений;
задача о равномерном назначении среди назначений минимальной стоимости;
задача о назначении минимальной стоимости среди равномерных назначений.
-
Для всех приведенных задач необходимо найти и обосновать эффективные алгоритмы построения оптимальных решений.
-
Целями главы 5 являются
5Форд Л.Р., Фалкерсон Д.Р., Потоки в сетях. М.: Мир, 1963.
6Ху Т., Целочисленное программирование и потоки в сетях. М.: Мир, 1974.
'Басакер Р., Т.Саати Т. Конечные графы и сети. М.: Наука, 1974.
исследования свойств критериев равномерности, которые мо
гут быть использованы в задаче о равномерном назначении;
обоснование выбора среднеквадратичного отклонения как
наиболее предпочтительного критерия оптимизации;
исследования примеров оптимизационных задач, которые мо
гут иметь определенный приоритетный критерий.
Научная новизна работы
-
Поставлена задача о равномерном назначении, как системы задач о назначении с критерием оптимизации - средне квадратичным отклонением. Разработан эффективный алгоритм ее решения, состоящий из последовательности решений вспомогательных ^/-задач, также сформулированных в работе. Каждое решение ^/-задачи является исходным потоком для следующей ^/-задачи. Для решения JZ-задач может быть использован алгоритм нахождения максимального потока в сети.
-
Сформулирована и доказана теорема о свойстве оптимального решения в задаче нахождения равномерного потока минимальной стоимости. Построен и обоснован алгоритм ее решения.
-
Сформулирована и доказана теорема о свойстве оптимального решения в задаче нахождения решения минимальной стоимости среди равномерных. Построен и обоснован алгоритм ее решения.
-
Исследованы свойства критериев равномерности. Обоснован выбор критерия оптимизации в задаче о равномерном назначении. Построена оптимизационная задача не дискретного характера, обладающая аналогичным свойством - имеющая приоритетный критерий оптимизации, представленный среднеквадратичным отклонением.
Практическая ценность работы
Задача о назначениях имеет немалое число приложений в практической сфере и, кроме того, к ней сводятся многие задачи из дискретной математики, теории оптимизации: задача о максимальном потоке, задача о наибольшем паросочетании, транспортная задача и др. Возникающие в практической сфере различные модификации задачи за-
ставляют искать более быстрые и эффективные алгоритмы, привязанные к дополнительным условиям задачи и учитывающие ее конкретную специфику. Несмотря на существование эффективных общих методов решений, задача о назначениях не потеряла своей актуальности.
В результате исследований в данной диссертационной работе получен ряд теорем о свойствах оптимальных решений определенных модификаций задач о назначениях, которые могут иметь практическое значение, для каждой задачи получены алгоритмы нахождения решений.
Доказано важное свойство средне квадратичного отклонения как наиболее оптимального критерия в задаче о равномерном назначении, что позволяет не рассматривать данную задачу с другими альтернативными критериями.
Алгоритмы решения задачи о равномерном назначениия реализованы программами на языке С + +, тексты которых приведены в приложении.
Апробация работы
Основные результаты работы докладывались и обсуждались на научных конференциях:
-
"Проблемы теоретической кибернетики", XIII Международная конференция (Казань), Москва, 2002;
-
"Дискретные модели в теории управляющих систем", V Международная конференция, Ратмино, 2003;
-
"Современные проблемы функционального анализа и дифференциальных уравнений", Научная конференция, Воронеж, 2003;
-
Всероссийская научная конференция, посвященная 200-летию Ярославского государственного университета им. П.ГДемидова, Ярославль, 2003.
-
Восьмой международный семинар "Дискретная математика и ее приложения", Москва, МГУ, 2004.
Публикации и вклад автора
Материалы диссертации опубликованы в 8 печатных работах: 4 статьях и 4 тезисах докладов.
Структура и объем диссертации
