Расширенная задача о равномерном назначении тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Чаплыгина, Надежда Борисовна

• Чаплыгина, Надежда Борисовна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Чаплыгина, Надежда Борисовна

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 представлены примеры, построенные программами, а в приложении - тексты этих программ, реализующих алгоритм нахождения решения Л-задачи как с учетом обязательных назначений, так и без него.Задача о равномерном назначении различающихся работ

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Чаплыгина, Надежда Борисовна

Заключение

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

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

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

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

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

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

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

А.

Список литературы диссертационного исследования кандидат физико-математических наук Чаплыгина, Надежда Борисовна, 2004 год

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.