автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Расширенная задача о равномерном назначении

На правах рукописи

Чаплыгина Надежда Борисовна

Расширенная задача о равномерном назначении

специальность 05.13.18 -математическое моделирование, численные методы и комплексы программ

автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Ярославль - 2004

Работа выполнена в Ярославском государственном университете им.П.Г. Демидова

Научный руководитель

кандидат физико-математических наук, доцент Рублев Вадим Сергеевич

Официальные оппоненты:

доктор физико-математических наук, профессор Бережной Евгений Иванович, кандидат физико-математических наук, доцент Корнилов Петр Анатольевич

Ведущая организация Вычислительный центр РАН

Защита состоится ■ ..2...\. ЯПРМЛ8..... 2004 г. вА'7..час.

на заседании диссертационного совета К 212.002.04

при Ярославском государственном университете им. П.Г.Демидова

по адресу: 150000 гЛрославль, ул.Советская, д. 14

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г.Демидова

по адресу: гЛрославль, ул.Полушкина роща, д.1

Автореферат разослан 2.6.

Ученый секретарь диссертационного советах,... • ./Тлызин С.Д

Общая характеристика работы

Актуальность проблемы

Задаче о назначениях и различным ее модификациям посвящено множество научных исследований, поскольку она сама по себе имеет немалое число приложений в практической сфере и, кроме того, к ней сводятся многие задачи из дискретной математики, теории оптимизации. В результате исследований получен ряд алгоритмов для ее решения.

В настоящее время исследуются различные расширения, обобщения и модификации классической задачи о назначениях, например, квадратичная задача о назначениях, многокритериальная задача о назначениях, случайная задача о назначениях, задача о равномерном назначении и др., разрабатываются эффективные алгоритмы решения как обобщенных задач, так и сужения задач, полученных в результате дополнительных ограничений и условий. Задача о назначениии в различных ее вариантах, несмотря на существование эффективных общих методов решений, не потеряла своей актуальности, поскольку она представляет большой практический интерес. Возникающие в практической сфере различные модификации задачи заставляют искать более быстрые и эффективные алгоритмы, привязанные к дополнительным условиям задачи и учитывающие ее конкретную специфику.

Простейшая постановка задачи о назначениях состоит в следующем. Имеется п работников различных профессий &ь&2,...,&т К0Т0" рые должны выполнить п работ {2)Квалификация каждого работника позволяет ему выполнять некоторые из предложенных работ. Возможно ли произвести назначение работ для исполнения таким образом, чтобы весь план работ был выполнен при условии, что один работник не может выполнять более одной работы? Эта задача в литературе часто носит название задачи о свадьбах.

Если число претендентов отличается от числа работ, которые необходимо выполнить, то такую задачу принято называть "несбалансированной" задачей о назначениях. В таком случае число претендентов на выполнение работ, конечно, должно быть не меньше числа самих работ, иначе задача неразрешима.

Данная задача может быть сведена к задаче о максимальном потоке в сети или к задаче о нахождении наибольшего паросочетания; можно представить эту задачу как задачу линейного программирования. Соответственно, и разрешима она может быть различными методами: с

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

помощью алгоритмов нахождения максимального потока, венгерским методом нахождения наибольшего паросочетания, симплекс-методом и ДР.

Задача усложняется при добавлении некоторых оптимизационных условий. Говоря о классической постановке задачи о назначениях, имеют в виду оптимизационную задачу с критерием - стоимостью затрат назначения, которую необходимо минимизировать, либо с критерием - суммой доходов, которую желательно максимизировать.

Исследованием классической задачи о назначениях занимались такие математики, как Р.Басакер, Т.Саати, Т.Ху, Г.Вагнер, Н.Кристофидес, Х.Кун и др.

Развитие вычислительной техники позволяет решать все более сложные, требующие больших объемов вычислений, задачи. Это влияет и на развитие математических методов решения, на построение новых математических моделей для решения реальных прикладных задач, исследование которых показывает, что практическая задача редко характеризуется оптимизацией лишь одного критерия. Как правило, принимая решение в той или иной задаче управления, приходится иметь дата с несколькими критериями и оценивать решение не по одному параметру. Так последнее время большое внимание уделяется исследованию многокритериальных задач, которые характеризуются наличием нескольких целевых функций вместо одной в однокритериальных задачах. Сложность нахождения решения многокритериальных оптимизационных задач связана с тем, что целевые функции, выступающие в качестве критериев оптимизации, во многих случаях конфликтуют между собой. Таким образом, оптимизировать решение сразу по всем целевым функциям возможно далеко не всегда.

Для того, чтобы отбирать более предпочтительные решения, надо уметь их сравнивать. В лучшем случае можно было бы ввести отношение линейного порядка на множестве значений критериев. Отношение линейного порядка можно ввести с помощью метода, называемого сверткой критериев. Он состоит в конструировании скаляризующей функции ^ : Я" Я, где к - число критериев, каждый из которых имеет вещественные или целочисленные значения. И если у - вектор значений критериев, то оптимизация з(у(х)) на множестве допустимых решений х приводит к получению решения А;-критериальной задачи. В практических приложениях часто осуществить этот метод довольно сложно из-за сложности отношений между критериями, если критериев достаточное число.

Однако можно ввести отношение частичного порядка на том же

множестве значений критериев, которое может и не дать возможность определить среди всех допустимых решений элемент с максимальным (в смысле введенного частичного порядка) значением многомерного критерия, но может дать возможность определить элемент со значением критерия, над которым нет большего, т.е. недоминируемого значения.

Пусть у(х) = (у1(х),у2(х),...,ук(х))- А;-мерная критериальная фунь ция на множестве допустимых значений X со значениями в Введем следующее отношение частичного порядка на множестве критериальных значений У С Rk. _

Vi •< Уг, если у\ < у\ для г = 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.

3Бондаренко В.А., Клоеден П.Е., Краснов М.В. О лексикографической оптимизации в многокритериальных дискретных задачах. Автоматика и телемеханика. 2, 2000.

ной в работах Рублева B.C. и Кропанова В.А. 4, задача о равномерном назначении расширена дополнительной возможностью выбора каждым рабочим определенных работ в любой день, что заметно усложняет ее решение.

Кроме описанной задачи в настоящей работе приводятся исследования и решения бикритериальных задач о назначениях с двумя критериями: критерием равномерности и критерием стоимости; рассматривается лексикографическая оптимизация, которая в задаче с двумя критериями имеет два варианта. Решения задач в обоих случаях будут иметь равные значения критериев оптимизации, если множества решений двух соответствующих однокритериальных задач имеют непустое пересечение, т.е. существует оптимальное решение сразу по обоим критериям.

Задача о равномерном назначении рассматривается с критерием -квадратичным отклонением, хотя в качестве критерия оптимизации можно было взять и другие функционалы. Какой критерий позволит получить наиболее приемлемое решение задачи, какими свойствами он должен обладать? Во многих оптимизационных задачах выбор критерия производится из общих соображений, интуитивно. В данной диссертационной работе проводится исследование свойств функционалов, используемых в качестве критериев равномерности.

Изучение вопросов, связанных с необходимыми свойствами критериев и решений задачи, к которым приводит оптимизация этих критериев, позволило доказать утверждение о том, что выбор одного из критериев - критерия среднеквадратичного отклонения - является наиболее выгодным в условиях рассматриваемой задачи, так как его оптимизация позволяет получить решения, которые оптимизируют и любой другой, возможный, критерий.

Задачи, в которых нет нужды выбора критерия среди множества возможных, представляют определенный интерес. Какие свойства оптимизационной задачи позволяют ей иметь приоритетный критерий оптимизации? Попытки ответить на этот вопрос привели к построению задачи не дискретного характера, обладающей описанным свойством и имеющей областью допустимых решений область, аналогичную области допустимых решений в рассматриваемой задаче о назначениях. И в этой построенной задаче замечательным свойством приоритетности обладает тот же функционал квадратичного отклонения.

4Кропанов В. А., Рублев В. С, Задача о равномерном назначении работ и ее обобщения //Моделир. и анализ информ. систем. Ярославль, 2000. Т.7, 2.

Методы исследования

В диссертационной работе были использованы идеи характеристического свойства оптимального решения оптимизационной задачи о равномерном назначении Рублева B.C.

Использовался алгоритм Форда-Фалкерсона нахождения максимального потока в сети5.

Использовалось свойство оптимального решения задачи о назначениях о том, что в дополнительной сети не может быть контуров отрицательной стоимости, приводимое во многих работах, в которых рассматривается задача о назначениях, например, в работах Т.Ху6, Р.Басакера и Т.Саати.

Использовались теоремы о реберных разбиениях графа на циклы и

7

цепи .

Доказательство приведенных в диссертационной работе теорем и построение алгоритмов получены аналитическими методами.

Цели работы

1) В диссертационной работе формулируются и иссследуются свойства оптимальных решений следующих обобщений задач о назначениях:

♦ задача о равномерном назначении;

♦ задача о равномерном назначении с учетом обязательных назначений;

♦ задача о назначении, приближенном к желательному вектору числа назначений;

♦ задача о равномерном назначении среди назначений минимальной стоимости;

♦ задача о назначении минимальной стоимости среди равномерных назначений.

2) Для всех приведенных задач необходимо найти и обосновать эффективные алгоритмы построения оптимальных решений.

3) Целями главы 5 являются

5Форд Л.Р., Фалкерсон Д.Р., Потоки в сетях. М.: Мир, 1963.

6Ху Т., Целочисленное программирование и потоки в сетях. М.: Мир, 1974.

7Басакер Р., Т.Саати Т. Конечные графы и сети. М.: Наука, 1974.

♦ исследования свойств критериев равномерности, которые могут быть использованы в задаче о равномерном назначении;

♦ обоснование выбора среднеквадратичного отклонения как наиболее предпочтительного критерия оптимизации;

♦ исследования примеров оптимизационных задач, которые могут иметь определенный приоритетный критерий.

Научная новизна работы

1) Поставлена задача о равномерном назначении, как системы задач о назначении с критерием оптимизации - средне квадратичным отклонением. Разработан эффективный алгоритм ее решения, состоящий из последовательности решений вспомогательных А/-задач, также сформулированных в работе. Каждое решение А/-задачи является исходным потоком для следующей А/-задачи. Для решения А/-задач может быть использован алгоритм нахождения максимального потока в сети.

2) Сформулирована и доказана теорема о свойстве оптимального решения в задаче нахождения равномерного потока минимальной стоимости. Построен и обоснован алгоритм ее решения.

3) Сформулирована и доказана теорема о свойстве оптимального решения в задаче нахождения решения минимальной стоимости среди равномерных. Построен и обоснован алгоритм ее решения.

4) Исследованы свойства критериев равномерности. Обоснован выбор критерия оптимизации в задаче о равномерном назначении. Построена оптимизационная задача не дискретного характера, обладающая аналогичным свойством - имеющая приоритетный критерий оптимизации, представленный среднеквадратичным отклонением.

Практическая ценность работы

Задача о назначениях имеет немалое число приложений в практической сфере и, кроме того, к ней сводятся многие задачи из дискретной математики, теории оптимизации: задача о максимальном потоке, задача о наибольшем паросочетании, транспортная задача и др. Возникающие в практической сфере различные модификации задачи за-

ставляют искать более быстрые и эффективные алгоритмы, привязанные к дополнительным условиям задачи и учитывающие ее конкретную специфику. Несмотря на существование эффективных общих методов решений, задача о назначениях не потеряла своей актуальности.

В результате исследований в данной диссертационной работе получен ряд теорем о свойствах оптимальных решений определенных модификаций задач о назначениях, которые могут иметь практическое значение, для каждой задачи получены алгоритмы нахождения решений.

Доказано важное свойство средне квадратичного отклонения как наиболее оптимального критерия в задаче о равномерном назначении, что позволяет не рассматривать данную задачу с другими альтернативными критериями.

Алгоритмы решения задачи о равномерном назначениия реализованы программами на языке С + + , тексты которых приведены в приложении.

Апробация работы

Основные результаты работы докладывались и обсуждались на научных конференциях:

1) "Проблемы теоретической кибернетики", XIII Международная конференция (Казань), Москва, 2002;

2) "Дискретные модели в теории управляющих систем", V Международная конференция, Ратмино, 2003;

3) "Современные проблемы функционального анализа и дифференциальных уравнений", Научная конференция, Воронеж, 2003;

4) Всероссийская научная конференция, посвященная 200-летию Ярославского государственного университета им. П.Г.Демидова, Ярославль, 2003.

5) Восьмой международный семинар "Дискретная математика и ее приложения", Москва, МГУ, 2004.

Публикации и вклад автора

Материалы диссертации опубликованы в 8 печатных работах: 4 статьях и 4 тезисах докладов.

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, содержащего 37 наименований. Диссертация содержит 11 иллюстрирующих рисунков. В приложении приведена программная реализация алгоритмов поиска равномерного назначения. Общий объем диссертации составляет 104 страницы.

Краткое содержание работы Введение

Обосновывается актуальность темы диссертационной работы, сформулированы цели работы, указана научная новизна и практическая значимость результатов работы, приведены структура и содержание диссертации.

Задача о равномерном назначении различающихся работ

Решению оптимизационной задачи о равномерном назначении с одним из возможных критериев оптимизации: среднеквадратичным отклонением числа работ от среднего - посвящена эта глава.

В течение планируемого периода из т дней п работников различных профессий должны выполнить определенный объем работ. В каждый к-п день к 6 1,т они должны произвести в к определенных и различных между собой работ. Будем обозначать работников через ¿>1, &2,..., Ьп, а работы к-го дня обозначим через (£ € 1,т).

Общее чисто работ равно 5 = При этом каждый работник

может в любой день выполнить не более одной работы. Возможности выполнения работ работниками на период заданы трехмерной булевой матрицей Я — € 17п,к 6 1 ,т,] € 1,5*), при этом матрица

А — {азадает обязательные назначения

Предполагается, что эти возможности позволяют произвести назначения работ или найти матрицу X— {х^}, согласованную с матрицами А и Я ( для всех г,У,¿выполняется 0 < а*- < х< < 1) так, чтобы все работы были выполнены.

Пусть X = (а?!,..-,х„) - итоговый вектор числа работ каждого

работника (обозначим тем же символом, что и матрицу), где

ж' = ЕЕ4- (1)

Необходимо равномерно распределить работы между работниками: найти допустимое решение X, минимизирующее функционал

где « = ^ - среднее число работ. Эту задачу назовем А-задачей.

Если т = 1, то получаем обычную задачу о назначениях. Если работы любого определенного дня не различаются между собой, то получим задачу о равномерном назначении.

Доказывается характеристическое свойство оптимального решения, которое позволяет построить эффективный алгоритм решения задачи равномерного назначения с различающимися работами. Для доказательства свойства оптимального решения определяются вспомогательные оптимизационные задачи с дополнительным условием-ограничением на число работ для каждого работника и условием оптимизации - максимизировать общее число назначенных работ.

Алгоритм поиска равномерного назначения состоит в последовательности решений вспомогательных задач, построенных из исходной.

В задаче находится решение, наиболее близкое к вектору из средних значений числа работ. Этот вектор выступает в качестве желательного. Рассматривается естественное обобщение задачи на случай произвольного желательного вектора Н = h) с суммой элементов 8, что дает возможность гибкого управления назначением.

Для построенного алгоритма нахождения решения проводится анализ сложности. Обосновывается вывод о том, что сложность алгоритма составляет 0((птп)%пз2) операций.

Равномерное назначение минимальной стоимости

При решении A-задачи оптимальное по равномерности назначение может быть не единственным. Если для каждого возможного назначения рабочему Ь, работы определена числовая характеристика с* — стоимость этого назначения, то задача приобретает два критерия

оптимизации. Рассмотрим лексикографическую оптимизацию полученной бикритериальной задачи. Среди равномерных назначений, т.е. решений А—задачи, естественно считать более предпочтительными те, которые имеют минимальную общую стоимость, и в следующей главе построено такое назначение.

Симметричная задача предполагает альтернативный порядок критериев: найти самое равномерное назначение среди назначений минимальной стоимости. В этой главе и рассматривается эта задача. Решение оптимизируется сначала по стоимости, затем по критерию равномерности. Необходимо среди всех назначений минимальной СТОИМОСТИ найти наиболее равномерное, т.е. минимизирующее функционал /(X) = — Графически условие задачи можно представить

в виде сети ЫЛ, которая имеет следующий вид:

В построенной по условиям задачи сети ЫЛ на дугах вида (Ьо,Ь>) пропускная способность не ограничивается, а на остальных дугах она

равна 1. Стоимости дуг вида представлены в матрице С, осталь-

ные дуги имеют нулевую стоимость. Требуется найти поток X величины ^ (т.е. максимальный), согласованный с матрицей А обязательных назначений, минимизирующий функционал

и наиболее равномерно распределенный согласно критерию

Если X - допустимое решение минимальной стоимости, то в дополняющей поток X сети ИЛ(Х) нет контуров отрицательной стоимости. Наличие любого контура в дополняющей сети означает возможность переназначения работ по данному контуру. Если контур имеет поло-жигельную стоимость, то такое переназначение приведет к увеличению стоимости потока. Если контур проходит через вершины именно в таком направлении и порядке, и к тому же выполняется неравенство

х, < х, - 1, (2)

то переназначение работ согласно данному контуру приведет к решению с меньшим значением функционала /, т.е. более равномерному. Такие контуры будем называть улучшающими равномерность или просто улучшающими. Если улучшающий контур имеет нулевую стоимость, то переназначение работ по нему не изменит стоимости потока.

Утверждается, что если два решения максимальной вачичины и минимальной стоимости не имеют улучшающих контуров нулевой стоимости в дополняющих их сетях соответственно, то их итоговые векторы (1) равны между собой с точностью до перестановки; и как следствие этого: если решение величины 8 минимальной стоимости не имеет улучшающих контуров нулевой стоимости, то оно является оптимальным по равномерности среди решений минимальной стоимости, т.е. решением поставленной задачи.

С учетом этого можно предложить алгоритм нахождения наиболее равномерного назначения минимальной стоимости:

1) построить максимальный поток;

2) пока есть контуры отрицательной стоимости, добавляя 1 единицу потока по такому контуру, уменьшать стоимость потока; если отрицательных контуров нет, то получен поток минимальной стоимости;

3) пока есть улучшающий контур нулевой стоимости, количество назначений начальной рабочей вершины которого, увеличенное на 1,

меньше количества назначений конечной рабочей вершины контура, т.е. выполнено условие (2), произвести переназначение по данному контуру; при этом стоимость потока не изменяется, а значение функционала / уменьшается на положительное целое число.

Поскольку / (X) > О, то алгоритм закончит свою работу, полученный при этом поток будет соответствовать наиболее равномерному решению задачи А среди максимальных потоков минимальной стоимости.

Анализ сложности алгоритма показывает, что для его реализации требуется 0((пт)3$2) операций.

Минимальная стоимость равномерного назначения

Рассматривается симметричная относительно лексикографического порядка оптимизации критериев задача, о которой говорилось в начале предыдущей главы. При ее решении приоритет отдается равномерности назначения, а не стоимости. При тех же исходных данных, что и в задаче предыдущей главы, требуется среди всех равномерных назначений, т.е. минимизирующих функционал / найти решение минимальной стоимости.

Требуется найти поток X,

1) удовлетворяющий неравенству X < Я (поэлементное выполнение неравенства);

2) равный по величине 5 (т.е. максимальный);

3) наиболее равномерно распределенный согласно критерию

4) и среди потоков, удовлетворяющих условиям 1)-3), минимизирующий функционал стоимости

Пусть X - равномерный максимальный поток в сети ЫЛ. Рассмотрим дополняющую его сеть ЫЛ(Х). Контуры этой сети могут проходить через вершину Ьо или не содержать ее . В первом случае будем считать началом контура вершину Ъ, во втором случае - любую вершину Л , через которую он проходит. Тогда если контур начинается с дуги а заканчивается дугой (Ь*, и к тому же Т} — ц = 1,

т.е. х^ = Хг + 1, то переназначение по нему увеличити уменьшит х^, что не изменит равномерность распределения, так как после переназначения элементы х^ и просто поменяются значениями. Это может быть лишь в случае контура, содержащего вершину Ьо. Если же контур не содержит вершину то переназначение по нему не изменит итоговые характеристики Х{, т.е. также не изменит равномерности потока.

Такие контуры будем называть контурами, сохраняющими равномерность.

Доказывается теорема:

Если поток X является равномерным потоком максимальной величины в сети ИЛ и в дополняющей его сети ИЛ^ не существует контуров отрицательной стоимости, сохраняющих равномерность, то X является потоком минимальной стоимости среди равномерных.

На основе этой теоремы можно предложить алгоритм решения поставленной задачи:

1) получить равномерный поток в сети ИЛ ;

2) пока в дополняющей сети есть отрицательный контур, не изменяющий равномерность, добавлять по нему единицу потока, т.е. производить переназначение по данному контуру, уменьшая стоимость потока.

Поскольку имеем дело с конечной сетью, то уменьшение стоимости потока будет производиться на величину, ограниченную снизу некоторым положительным числом. Поэтому алгоритм закончит свою работу за конечное число шагов.

Рассмотрим вопрос: обладает ли решение X задачи из предыдущей главы ( минимальной стоимости среди наиболее раномерных назначений) минимальной стоимостью на всем множестве допустимых решений? В общем случае это решение может не являться решением минимальной стоимости.

Пусть S - множество всех назначений минимальной стоимости, а Н - множество всех равномерных назначений. Тогда, если пересечение этих множеств не пусто, т.е. 5 П Л Ф 0, то алгоритм нахождения равномерного назначения с минимальной стоимостью, очевидно, будет строить решения именно из пересечения Я П Я. Если же в сети ИЛ(К), в которой не будет отрицательных контуров, сохраняющих равномерность, все-таки останутся отрицательные контуры, то можно сделать вывод о том, что оптимизировать решение сразу по двум критериям невозможно. В этом случае пересечение множеств

Для построения решения, обладающего наилучшей равномерностью и минимальной стоимостью, если оно существует, можно использовать и алгоритм из предыдущего раздела, который строит наиболее равномерное назначение из всех назначений минимальной стоимости. В сети ИЛ^, где X - решение, построенное данным алгоритмом, не должно быть улучшающих контуров с нулевой стоимостью. Если улучшающие равномерность контуры все же останутся, то задача не обладает решением, оптимальным сразу по двум критериям. В противном случае, получим именно такое решение, т.е. решение из пересечения множеств

5 Л Л.

Таким образом, если у задами существует решение X, оптимальное сразу по двум рассматриваемым критериям: равномерности и стоимости, то в сети ЫЛ(Х) не найдется ни контуров отрицательной стоимости, ни улучшающих равномерность контуров. Чтобы построить такое решение, можно воспользоваться любым из двух алгоритмов, приведенных в данном и предыдущем разделах.

О выборе наилучшего критерия равномерности

Рассматривается задача сравнения критериев равномерности в А-задаче. Определяются свойства, необходимые для критерия оптимизации:

1) свойства нормы разности между решением X и вектором средних значений числа работ на каждого рабочего £ — (;[>•••>%)>

2) симметричность относительно перестановки координат.

Доказывается теорема о том, что решение, полученное оптимизацией среднеквадратичного отклонения или равносильного ему функционала /, оптимизирует любой альтернативный критерий, обладающий установленными выше свойствами. Построена задача не дискретного характера, обладающая описанным выше свойством, имеющая областью допустимых решений область, аналогичную области допустимых решений в рассматриваемой задаче о назначениях.

Заключение

В данной работе исследованы следующие задачи:

♦ задача о равномерном назначении с усложненной структурой плана работ и анализ сложности решения,

♦ ее модификации: с возможностью определения обязательных назначений и возможностью определения желательного вектора числа назначений,

♦ бикритериальные задачи о назначениях с лексикографической опт мизацией, дающей два варианта задач в зависимости от приоритета критериев: критерия равномерности и стоимости.

Для каждой задачи предложены варианты ее решения с помощью алгоритмов, опирающихся на доказанные в работе теоремы о свойствах соответствующих оптимальных решений.

Кроме этого исследован вопрос о свойствах критериев равномерности и доказано важное свойство задами о равномерном назначении, которое позволяет не рассматривать в качестве критериев равномерности альтернативные функционалы, поскольку оптимизация по введенному критерию - квадратичному отклонению - является оптимизацией и по любому другому допустимому в задаче критерию.

Также построена задача не дискретного характера, обладающая этим же свойством.

Таким образом, цели, поставленные перед данным исследованием достигнуты.

Приложение

Приводятся тексты программ на языке С + + , реализующие алгоритмы равномерного назначения.

Список публикаций по теме диссертации

[1] Рублев В. С, Чаплыгина Н.Б. Расширение задачи о назначениях //Моделирование и анализ информационных систем. Ярославль, 2002. Т.9, №2. С. 3-11.

[2] Рублев B.C., Чаплыгина Н.Б. Расширение задачи о назначени-ях//Тез. докл. XIII Межд. конф. Проблемы теор. кибернетики (Казань). Москва, 2002. С. 156.

[3] Чаплыгина Н.Б. Оптимальный критерий равномерного назначе-ния//Тез. докл. XIII Межд. конф. Проблемы теор. кибернетики (Казань). Москва, 2002. С Л 87.

[4] Чаплыгина Н.Б. Расширенная задача о равномерном назначении минимальной стоимости //Моделирование и анализ информационных систем. Ярославль, 2003. Т.11, №2, С. 20-30.

[5] Чаплыгина Н.Б. Задача о назначении минимальной стоимости среди равномерных назначений//Вопросы теории групп и гомологической алгебры. Ярославль, ЯрГУ, 2003. С. 238-245.

[6] Чаплыгина Н.Б. Задача о равномерном назначении минимальной стоимости //Труды V Межд. конф. Дискр. модели в теории управл. систем. Ратмино, 2003. С. 90-91.

[7] Рублев B.C., Чаплыгина Н.Б. Критерий среднеквадратичного отклонения - наилучший для области определенного вида в // Тез. конф. Совр. проблемы функ. анализа и диф. ур. Воронеж, 2003. С. 199.

[8] Чаплыгина Н.Б. Сравнение критериев равномерности в задаче о назначениях// Математика: Материалы Всеросс. науч. конф., по-свящ. 200-летию ЯрГУ им.П.Г.Демидова. Ярославль, 2003. С. 144151.

jä -6 97 4

1. Введение

2. Задача о равномерном назначении различающихся работ

2.1. Постановка задачи.

2.2. Постановка Лкзадачи.

2.3. Характеристическое свойство оптимального решения А - задачи.

2.4. Алгоритм решения Л-задачи.

2.5. Учет желательного числа назначений (НА-задача).

2.6. Анализ сложности алгоритма нахождения равномерного назначения

3. Равномерное назначение минимальной стоимости

3.1. Постановка задачи.

3.2. Улучшающие контуры.

3.3. Частичная сеть, порожденная потоками, и дополняющая их сеть

3.4. Построение равномерного потока минимальной стоимости.

3.5. Решение задачи с ненулевой матрицей обязательных назначений

3.6. Еще один алгоритм решения задачи равномерного назначения

3.7. Анализ сложности алгоритма нахождения равномерного назначения минимальной стоимости

4. Минимальная стоимость равномерного назначения

4.1. Постановка задачи.

4.2. Свойство оптимального решения.

4.3. Алгоритм нахождения оптимального решения

4.4. Оптимальность решения по двум критериям

5. О выборе наилучшего критерия равномерности

5.1. Постановка задачи.

5.2. Свойства критерия равномерности.

5.3. Оптимальный критерий равномерности

5.4. Свойства задачи, влияющие на оптимальность критерия /

Задаче о назначениях и различным ее модификациям посвящено множество научных исследований, поскольку она сама по себе имеет немалое число приложений в практической сфере и, кроме того, к ней сводятся многие задачи из дискретной математики, теории оптимизации. В результате исследований получен ряд алгоритмов для ее решения.В настоящее время исследуются различные расширения, обобщения и модификации классической задачи о назначениях, например, квадратичная задача о назначениях, многокритериальная задача о назначениях, случайная задача о назначениях, задача о равномерном назначении и др., разрабатываются эффективные алгоритмы решения как обобщенных задач, так и сужения задач, полученных в результате дополнительных ограничений и условий.Задача о назначениии в различных ее вариантах, несмотря на существование эффективных общих методов решений, не потеряла своей актуальности, поскольку она представляет большой практический интерес. Возникающие в практической сфере различные модификации задачи заставляют искать более быстрые и эффективные алгоритмы, привязанные к дополнительным условиям задачи и учитывающие ее конкретную специфику.Простейшая постановка задачи о назначениях состоит в следующем. Имеется п работников различных профессий 6i, 62, . . . , bn, которые должны выполнить п работ ti,t2,..., tn. Квалификация каждого работника позволяет ему выполнять некоторые из предложенных работ. Возможно ли произвести назначение работ для исполнения таким образом, чтобы весь план работ был выполнен при условии, что один работник не может выполнять более одной работы? Эта задача в литературе часто носит название задачи о свадьбах (см. [2], [4] и др.).Если число претендентов отличается от числа работ, которые необходимо выполнить, то такую задачу принято называть "несбалансированной" задачей о назначениях. В таком случае число претендентов на выполнение работ, конечно, должно быть не меньше числа самих работ, иначе задача неразрешима.Данная задача может быть сведена к задаче о максимальном потоке в сети или к задаче о нахождении наибольшего паросочетания; можно представить эту задачу как задачу линейного программирования. Соответственно, и разрешима она может быть различными методами: с помощью алгоритмов нахождения максимального потока, венгерским методом нахождения наибольшего паросочетания, симплекс-методом и др. Решение этой задачи можно найти в работах Р.Басакера, Т.Саати [1], Т.Ху [10], Г.Вагнера [3] и др.Задача усложняется при добавлении некоторых оптимизационных условий. Говоря о классической постановке задачи о назначениях, имеют в виду оптимизационную задачу с критерием - стоимостью затрат назначения, которую необходимо минимизировать, либо с критерием - суммой доходов, которую желательно максимизировать. Исследование и различные алгоритмы решения задачи представлены, например, в работах Н.Кристофидеса [7], Х.Куна [36], названных выше авторов и многих других.Развитие вычислительной техники позволяет решать все более сложные, требуюш;ие больших объемов вычислений, задачи. Это влияет и на развитие математических методов решения, на построение новых математических моделей для решения реальных прикладных задач, исследование которых показывает, что практическая задача редко характеризуется оптимизацией лишь одного критерия. Как правило, принимая решение в той или иной задаче управления, приходится иметь дело с несколькими критериями и оценивать решение не по одному параметру. Так последнее время большое внимание уделяется исследованию многокритериальных задач, которые характеризуются наличием нескольких целевых функций вместо одной в однокритериальных задачах. Сложность нахождения решения многокритериальных оптимизационных задач связана с тем, что целевые функции, выступающие в качестве критериев оптимизации, во многих случаях конфликтуют между собой. Таким образом, оптимизировать решение сразу по всем целевым функциям возможно далеко не всегда.Для того, чтобы отбирать более предпочтительные решения, надо уметь их сравнивать. В лучшем случае можно было бы ввести отношение линейного порядка на множестве значений критериев.Отношение линейного порядка можно ввести с помощью метода, называемого сверткой критериев. Он состоит в конструировании скаляризующей функции s : R^ —^ R, где к - число критериев, каждый из которых имеет вещественные или целочисленные значения. И если у - вектор значений критериев, то оптимизация s{y{x)) на множестве допустимых решений х приводит к получению решения А;-критериальной задачи. В практических приложениях часто осзоцествить этот метод довольно сложно из-за сложности отношений между критериями, если критериев достаточное число. Однако можно ввести отношение частичного порядка на том же множестве значений критериев, которое, возможно, и не даст возможность определить среди всех допустимых решений элемент с максимальным (в смысле введенного частичного порядка) значением многомерного критерия, но может позволить определить элемент со значением критерия, над которым нет большего, т.е. недоминируемым значением.Тогда у недоминируется на Z, если не существует такого у Е Z, что у ^ у и у ^ у. Согласно введенного отношения частичного порядка -< можно поставить задачу найти решение х, для которого значение критерия является недоминируемым. Такое решение называется эффективным или оптимальным по Парето. Нахождение эффективных решений имеет большое значение, так как только эти решения являются претендентами на оптимальность, если оптимальное решение вообще существует на множестве допустимых решений.В зависимости от вводимого отношения порядка на множестве значений критериев можно получить различные оптимальные решения. В случае, когда критерии оптимизации можно упорядочить по предпочтению, можно ввести лексикографический порядок на множестве критериальных векторов, что может позволить многокритериальную задачу свести к последовательности однокритериальных задач.Решению и исследованию многокритериальных оптимизационных задач посвящен довольно широкий ряд работ И.И.Меламеда и И.Х.Сигала [12]-[17]. В этих работах кроме полученных общих теоретических результатов: методов нахождения оптимальных по Парето решений, метода линейной свертки критериев и др. - представлены и данные обширных вычислительных экспериментов по решению двух- и трехкритериальных задач с критериями типа MINSUM и MINMAX. В том числе представлены результаты работы алгоритма нахождения решения бикритериальной задачи о назначениях и приведена статистическая обработка полученных экспериментальных данных, исследованы зависимости числа значений вектора критериев на решениях задачи от объема задачи, от вида входных данных задачи, распределение критериальных значений по виду линейной свертки критериев.Общие теоретические положения теории принятия решений при многокритериальной оптимизации можно найти в работах Р.Штойера [19], Р.Л.Кини и Х.Райфы [20]. Лексикографической многокритериальной оптимизации и сложности алгоритмов решения оптимизационных задач со многими критериями посвящены исследования Бондаренко В.А., Клоедена П.Е., Краснова М.В. [22], [23].В настоящей работе рассматривается расширение задачи о назначениях, связанное с усложнением структуры плана работ, рассчитанного на период в несколько дней, в связи с чем любой работник может выполнять несколько работ плана при условии, что ежедневно любой работник не может выполнять более одной работы. Таким образом, необходимо разрешить систему задач о назначениях на каждый день плана, ^ причем в качестве исполнителей в "ежедневных" задачах о назначениях берется одно и то же множество. Поэтому задачи не могут решаться независимо друг от ^ Здесь имеются в виду задачи без учета стоимости назначения, так что можно было бы говорить о "ежедневных" задачах поиска максимальных паросочетаний. Но название задачи "о назначениях" отражает практический ее смысл. друга, т.е. решение полученной системы задач не может быть сведено к решению нескольких задач назначений на каждый день. В итоге каждый г-тый работник получает xi определенных назначений. Оптимизационный характер данная задача приобретает при введения критерия оптимизации, но в отличие от классической постановки критерием в рассматриваемой задаче является функционал равномерности, представленный в работе В.С.Рублева [26].Минимизация функционала равномерности должна привести к решению, в котором распределение работ между исполнителями осуш;ествляется наиболее равномерно.Если в классической постановке критерием выступает линейный функционал, что позволяет применять для решения этой задачи соответствующие методы, например, методы решения задач линейного программирования, то в задаче, исследуемой в данной работе, критерий может являться нелинейным.Один из-вариантов задачи о равномерном назначении рассматривается с работах В.С.Рублева и В.А.Кропанова [24]-[26]. Постановка решаемых в них задач также включает план работ, рассчитанный на несколько дней. Но в данной задаче исполнитель может выражать отношение сразу ко всем работам одного дня, не имея возможности выбора между ними, т.е. работы одного дня не различаются между собой для любого определенного работника.В настояш;ей диссертационной работе постановка задачи о равномерном назначении расширена дополнительной возможностью выбора каждым рабочим определенных работ в любой день, что заметно усложняет задачу.Решению оптимизационной задачи о равномерном назначении с одним из возможных критериев оптимизации: среднеквадратичным отклонением числа работ от среднего - посвящена глава 2 настоящей работы. Здесь приводится постановка задачи оптимизации критерия равномерности, доказывается характеристическое свойство оптимальных решений, для чего вводится дополнительная модификация задачи, полученная из исходной добавлением ограничения на максимальное число работ для каждого рабочего. В той же главе описывается алгоритм решения поставленной задачи, который использует характеристическое свойство оптимального решения. В доказательстве характеристического свойства оптимального решения использованы идеи научного руководителя В.С.Рублева [25]. Кроме исходной задачи о равномерном назначении в этой же главе приводятся два ее расширения. Одно из них допускает возможность предопределять некоторые назначения работ определенным исполнителям матрицей обязательных назначений. Другое - допускает возможность оптимизации равномерности решения не относительно среднего, а относительно желательного числа работ, что позволяет управлять назначением работ в последовательности задач равномерного назначения, расширяя возможности практического применения алгоритма. Если, например, в силу определенных обстоятельств в полученном оптимальном решении определенный рабочий получает число назначений, значительно отклоняющееся от среднего, то в решении следуюш;ей задачи эту "несправедливость" можно уменьшить с помощью задания числа желательных назначений. Для обоих расширений задач получены алгоритмы их решения, обоснование которых аналогично приведенным в [25].В задаче о равномерном назначении используется критерий квадратичное отклонение, хотя в качестве критерия оптимизации можно было взять и другие функционалы. Какой критерий позволит получить наиболее приемлемое решение задачи, какими свойствами он должен обладать - эти вопросы исследуются в 5 главе настоящей работы. Кроме этого доказывается утверждение о том, что выбор одного из критериев - критерия среднеквадратичного отклонения - является наиболее выгодным в условиях рассматриваемой задачи, так как его оптимизация позволяет получить решения, которые оптимизируют и все другие, возможные, критерии. Задачи, в которых нет необходимости выбора критерия среди множества возможных, представляют определенный интерес. Какие свойства оптимизационной задачи позволяют ей иметь приоритетный критерий оптимизации? Попытки ответить на этот вопрос привели к построению задачи не дискретного характера, обладающей описанным выше свойством и имеющей областью допустимых решений область, аналогичную области допустимых решений в рассматриваемой задаче о назначениях.В 3 и 4 главах исследуются бикритериальные задачи о назначениях с критериями: равномерности и стоимости. Рассматривается лексикографическая оптимизация, которая в задаче с двумя критериями имеет два варианта. Обе задачи - обобщения соответствующих задач, рассмотренных В.А.Кропановым и В.С.Рублевым [24][25]. Решения задач в обоих случаях будет иметь равные значения критериев оптимизации, если множества решений двух соответствующих однокритериальных задач имеют непустое пересечение, т.е. существует оптимальное решение сразу по обоим критериям.В 3 главе ставится задача из всех решений минимальной стоимости найти наиболее равномерное. Приводится доказательство теоремы о свойстве оптимального решения (в дополняющей сети нет контуров нулевой стоимости, улучшающих равномерность) и на основе этого строится алгоритм решения задачи.В 4 главе критерии оптимизации рассматриваются в другом лексикографическом порядке, что приводит и к другому оптимальному решению задачи. Здесь также доказывается теорема об оптимальном решении (в дополняющей сети нет контуров, сохраняющих равномерность и имеющих отрицательную стоимость) и приводится алгоритм его нахождения.Алгоритм нахождения равномерного решения, полученный в главе 2, реализован программами на языке С+-Н. В п.2.4 представлены примеры, построенные программами, а в приложении - тексты этих программ, реализующих алгоритм нахождения решения Л-задачи как с учетом обязательных назначений, так и без него.Задача о равномерном назначении различающихся работ

Заключение

В данной работе исследованы следующие задачи:

• задача о равномерном назначении с усложненной структурой плана работ,

• ее модификации: с возможностью определения обязательных назначений и возможностью определения желательного вектора числа назначений,

• бикритериальные задачи о назначениях с лексикографической оптимизацией, дающей два варианта задач в зависимости от приоритета критериев: критерия равномерности и стоимости.

Для каждой задачи предложены варианты ее решения с помощью алгоритмов, опирающихся на доказанные в работе теоремы о свойствах соответствующих оптимальных решений.

Исследован вопрос о свойствах критериев равномерности и доказано важное свойство задачи о равномерном назначении, которое позволяет не рассматривать в качестве критериев равномерности альтернативные функционалы, поскольку оптимизация по введенному критерию - квадратичному отклонению - является оптимизацией и по любому другому допустимому в задаче критерию.

Построена задача не дискретного характера, обладающая этим же свойством. Таким образом, цели, поставленные перед данным исследованием достигнуты.

А.

1. Басакер Р., Т.Саати Т. Конечные графы и сети. М.: Наука, 1974.

2. Берж К. Теория графов и ее применение. М.: Ин.лит., 1962.

3. Вагнер Г. Основы исследования операций. М.: Мир, 1972.

4. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.« U

5. Иенсен П., Барнес Д. Потоковое программирование. М : Радио и связь, 1984.

6. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы. Построение и анализ. М.: МЦНМО, 2001.

7. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир,1978.

8. Пападимитриу X., Стайглиц К., Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

9. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

10. Ху Т., Целочисленное программирование и потоки в сетях. М.: Мир, 1974.

11. Форд Л.Р., Фалкерсон Д.Р., Потоки в сетях. М.: Мир, 1963.

12. Меламед И.И., Сигал И.Х. Исследование линейной свертки критериев в многокритериальном дискретном программировании. Ж. вычислит, матем. и матем. физики, 1995, Т.35. №8. С.1260-1270.

13. Меламед И.И. Теория линейной параметризации критериев в многокритериальной оптимизации. ДАН, 1996, Т.348. №4. С.446-448.

14. Меламед И.И., Сигал И.Х. Вычислительное исследование трех-критериальных задач о деревьях и назначениях. Ж. вычислит, матем. и матем. физики, 1998, Т.38. №10. С.1780-1787.

15. Меламед И.И., Сигал И.Х. Задачи комбинаторной оптимизации с двумя и тремя критериями. ДАН, 1999, Т.366. №2. С.170-173.

16. Меламед И.И., Сигал И.Х. Бикритериальные задачи дискретного программирования с MINSUM-MINSUM критериями. М.: ВЦ РАН, 2000.

17. Меламед И.И., Сигал И.Х. Распределение эффективных решений в некоторых бикритериальных задачах дискретного программирования. М.: ВЦ РАН, 2001.

18. Сигал И.X.,Иванова А.П., Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы. М.: Физматлит, 2002.

19. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. М.: Радио и связь, 1992.

20. Кини P.JL, Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981.

21. Стрекаловский A.C., Васильев И.Л. Об одном подходе к решению квадратичной задачи о назначениях. Тез. докл. конф.

22. Математическое программирование и приложения. Екатеринбург, 1999.

23. Бондаренко В.А., Клоеден П.Е., Краснов М.В. О лексикографической оптимизации в многокритериальных дискретных задачах./ / Автоматика и телемеханика. №2, 2000.

24. Бондаренко В.А., Краснов М.В. Сложность многокритериальных задач на графах. // Математика в Ярославском университете. Ярославль, ЯрГУ, 2001.

25. Кропанов В. А., Рублев В. С., Равномерное назначение работ минимальной стоимости //Дискретная математика, 2001. Т.13, №4. С. 144-156.

26. Кропанов В. А., Рублев В. С., Задача о равномерном назначении работ и ее обобщения //Моделирование и анализ информационных систем. Ярославль, 2000. Т.7, №2. С. 3-12.

27. Рублев B.C. Задача о равномерном распределении работ //Ярославский госуниверситет. Ярославль, 1986.-Деп. ВИНИТИ ДО611-В87 26.01.87

28. Рублев В. С., Чаплыгина Н.Б. Расширение задачи о назначениях //Моделирование и анализ информационных систем. Ярославль, 2002. Т.9, №2. С. 3-11.

29. Рублев B.C., Чаплыгина Н.Б. Расширение задачи о назначениях. //Тез. докл. XIII Межд. конф. Проблемы теор. кибернен-тики, Москва, 2002, С. 156.

30. Чаплыгина Н.Б. Оптимальный критерий равномерного назначения. //Тез. докл. XIII Межд. конф. Проблемы теор. кибер-нентики, Москва, 2002, С. 187.

31. Чаплыгина Н.Б. Расширенная задача о равномерном назначении минимальной стоимости //Моделирование и анализ информационных систем. Ярославль, 2003. Т.11, №2, С. 20-30.

32. Чаплыгина Н.Б. Задача о назначении минимальной стоимости среди равномерных назначений. //Вопросы теории групп и гомологической алгебры, Ярославль, ЯрГУ, 2003.

33. Чаплыгина Н.Б. Задача о равномерном назначении минимальной стоимости. //Труды V Межд. конф. Дискр. модели в теории управл. систем, Ратмино, 2003, С. 90-91.

34. Рублев B.C., Чаплыгина Н.Б. Критерий среднеквадратичного отклонения наилучший для области определенного вида в Rn. Тез. конф. Совр. проблемы функ. анализа и диф. ур. Воронеж, 2003, С. 199.

35. Чаплыгина Н.Б. Сравнение критериев равномерности в задаче о назначениях. Математика: Материалы Всеросс. науч. конф., посвящ. 200-летию ЯрГУ им.П.Г.Демидова, Ярославль, 2003. С. 144-151.

36. Hopcroft J.Е., Кагр R.M. An n5/2 algorithm for maximum match-ings in bipartite graphs. SIAM Journal on Computing, 2(4), 1973.

37. Kuhn H.W. The Hungarian method for the assigment problem. Nav.Res. Log. Quart., 2, 1955.

38. Abreu N., Netto P., Querido Т., Gouvea E. Classes of quadratic assignment problem instances: isomorphism and difficulty measure using a statistical approach.// Discrete applied mathematics, 124, 2002.

39. Angel E., Zissimopoulos V. On the hardness of the quadratic assignment problem with metaheuristics.// Journal of heuristics, 8, 2002.