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

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

Медведева Ольга Александровна

МОДЕЛИ И АЛГОРИТМЫ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ С ДОПОЛНИТЕЛЬНЫМИ ОГРАНИЧЕНИЯМИ

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

АВТОРЕФЕРАТ

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

21 НОЯ 2013

Воронеж-2013

005538631

Работа выполнена в ФГБОУ ВПО «Воронежский государственный университет»

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

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

Леденёва Татьяна Михайловна, доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет», заведующий кафедрой вычислительной математики и прикладных информационных технологий

Бугаев Юрий Владимирович, доктор физико-математических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет инженерных технологий», профессор кафедры информационных технологий моделирования и управления

Ведущая организация:

Белецкая Светлана Юрьевна, доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный технический университет», профессор кафедры систем автоматизированного проектирования и информационных систем

ФГБОУ ВПО «Липецкий государственный технический университет»

Защита состоится «12» декабря 2013 г. в 13.00 на заседании диссертационного совета Д.212.037.01 при ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский пр., д. 14.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «11» ноября 2013 г.

Ученый секретарь диссертационного совета

Барабанов В.Ф.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задача о назначениях (ЗОН), её линейные, квадратичные и многоиндексные разновидности привлекают внимание исследователей ввиду своей обширной применимости в различных областях научной и практической деятельности. К ним сводятся задачи, связанные с оптимальным распределением элементов на микросхемах, задачи планирования работы вычислительных, производственных, технологических систем, оптимизации перевозок, а также задачи составления расписаний. Содержательная постановка данной задачи формулируется следующим образом: пусть имеется п работ и п претендентов для выполнения этих работ. Назначение претендента / на работу j связано с затратами с:] (i, j = 1, и). Требуется определить назначение, дающее минимальные суммарные затраты, при этом каждого претендента можно назначить только на одну работу, и каждая работа может быть занята только одним кандидатом. С комбинаторной точки зрения допустимое решение этой задачи представляет собой перестановку к = (щ,...,яп) чисел 1, ..., и, а

соответствия вида i ->7г, (/ = 1,и) описывают произведённые назначения (г, кг) (г'-й претендент назначен на работу с номером л1). Тогда задача сводится к определению

такой перестановки ж', которая минимизирует линейную целевую функцию ^ ст .

Данная задача, называемая линейной закрытой ЗОН, относится к задачам дискретной оптимизации и является частным случаем транспортной задачи. Для неё существуют точные методы решения, такие как венгерский алгоритм, метод потенциалов, метод ветвей и границ. Однако дополнительные требования, обусловленные практическими задачами, приводят к различным модификациям математической модели: изменению стандартных и/или добавлению новых ограничений, а также появлению многокритериальное™. Для модифицированных моделей, по-прежнему являющихся задачами дискретной оптимизации, известные методы зачастую не применимы, что требует разработки специальных подходов к нахождению решения - точного или приближённого. Основные исследования ЗОН связаны с изучением различных целевых функций при стандартных ограничениях (R. Burkard, М. R. Garey, D. S. Johnson, О. Gross, R. М. Кагр, Э. X. Гимади) или с применением линейной свёртки критериев (И. В. Сергиенко, В. А. Емеличев, В. А. Перепелица, Р. Aneja).

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

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

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

Для достижения цели в работе решаются следующие основные задачи:

1. Анализ алгоритмов решения классической ЗОН и исследование направления их усовершенствования.

2. Разработка математических моделей для ЗОН с дополнительными условиями, связанными с изменением стандартных, добавлением новых ограничений, а также с появлением многокритериальности.

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

4. Разработка программного комплекса для проведения вычислительного эксперимента и рекомендаций по использованию разработанных методов в зависимости от типов задач и их размерности.

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

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

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

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

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

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

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

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

• структура программного комплекса, включающая инвариантную составляющую, в которой реализованы базовые методы, и проблемно-ориентированную со-

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

Тематика работы соответствует следующим пунктам Паспорта специальности 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 наименований, и приложений. Основная часть работы изложена на 138 страницах и включает 17 рисунков и 7 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Во второй главе предложены модели для ЗОН с дополнительными условиями и численные методы для нахождения оптимального и/или субоптимального решений, основанные на двух основных стратегиях: сведению к классической ЗОН или переходе к двойственной задаче. Математическая модель для классической открытой ЗОН взята за основу при построении других моделей и при т>п имеет вид:

¿х„.=1, у = (2)

1=1

¿>,<1, 1 = йп, (3)

7=1 ___

^={0,1}, / = 1,т, 7 = 1,«, (4)

где - затраты, связанные с назначением г'-го претендента на у'-е место. Матрица X = х„ называется матрицей назначений.

В диссертации предложены оптимизационные модели для следующих задач.

1. Задача о назначениях с запретами.

Предположение: задано множество наборов индексов

1пс! = {(/,у): назначение (г, у) запрещено}.

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

Модификация модели (1)-(4) заключается в замене ограничений (2)-(3) на следующие ограничения:

|>Л =1, у=й, (5)

/=1

¡ = (6)

7=1

где 5 = ^ - матрица запретов, которая формируется на основе множества Ы,

в которой для г = \,п, у = 1 ,т

{1, если /-й претендент умеет выполнятьу - ю работу, О, иначе.

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

Утверждение 1. Если М >п-тахсу и Л" = {х*} - оптимальное решение закрытой задачи о назначениях с матрицей затрат { с } ,где

^ у ) п X п

- (с/,, если/-Й претендент умеет выполнять у-ю работу, т.е. (/,у')б5, '' 1М, иначе, т.е. если (г,у) г 5, то имеет место следующая альтернатива:

1. (х^ = 0), и тогда ненулевые компоненты X'составляют решение

задачи о назначениях с запретами;

2. 3 (к,1)ё 5 (л? = 1), при этом система (5)-(6) несовместна.

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

2. Задача о назначениях с предпочтениями.

Предположение: для каждого индекса /(/ = 1,/и) существует перестановка Д -(/>,,...,/>„), которая отражает предпочтения на множестве индексов у.

Интерпретация: для каждого претендента известна система предпочтений на множестве работ.

Данная задача отличается от классической наличием двух критериев оптимальности, первый из которых отвечает за суммарную стоимость назначений, а второй учитывает предпочтения претендентов, при этом к модели (1)-(4) добавляется целевая функция вида

= (7)

¡-1 у.1

где Ъу - номер у'-й работы в списке предпочтения /'-го претендента, т.е. чем меньше коэффициент Ъу, тем предпочтительнейу'-я работа для /-го претендента.

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

,=1 >1

корректируется матрица затрат сц 1 = 1,т, ) = \,п, а затем применяется вен-

герский алгоритм для получения оптимального решения.

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

__от и г V г ГГ

r( Y) = V Y V и___fi.

MV / / . / i j max г min r max _

' ' / ' j max г mm г max _ г min

i=l y.i M М

__л h г т mm

L т = У"У iJ ''___=2_

2 V / / . / . , max _ r min r max _ т min '

i-i 1=1 2 2 2

где i,""" и ¿2mm - значения целевых функций при решении однокритериальных задач на минимум, a L,1"™ и - на максимум соответственно.

Затем осуществляется переход к задаче с целевой функцией вида

min j max^XXZ^X)) }, (9)

которую можно переписать в эквивалентной форме

ft = max(i1(A'),Z,2(A')) —> min

Ц(Х)-М<0, Т2(Х)-М< О, . x^eS, i = \,m,j = \,п, fi> О,

где S есть множество переменных {д^}, удовлетворяющих ограничениям (2)-(4). Функция Лагранжа для задачи 2 после преобразования принимает вид

m и

vb„

1 V

г max _ г min г max _ г mm

h 2

___(10)

r max t mm v '

¿1гаах-А'

y=i j=\

+/i(l-(u + v)), m,v> 0, xeS, fi> 0.

С помощью функции Лагранжа задача (1)-(5) и двойственная к ней могут быть записаны соответственно в виде

minmax<3>(.x,//,i/,v) и maxmm<P(x,fi,u,v).

xeS и .väO v ' »,v>0 xeS v

ft> 0 //>0

Двойственная задача тахю(и,у), где oj(u,v) = ттФ(x,u,u,v) - двойственная

u,v> О v ' v ' jceS 4

/i>0

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

ЛГ+1

N

Усо(и"У\

(И)

где через Уа» обозначено соответствующее значение субградиента двойственной функции со (•), а - шаги перемещения, выбранные в соответствии с правилом

расходящегося ряда.

Для вычисления значения Усо при фиксированных значениях двойственных переменных и и V (что делается на каждой итерации) показано, что необходимо минимизировать функцию Лагранжа по переменным х и ¡л. Из вида функции Лагранжа (10) следует, что на каждой итерации необходимо решать следующие подзадачи:

ЕХ

г шах г пип 2 2 J

► тш,

хб5

• П11П

(12) (13)

л , т

м -Ч

где (12) является ЗОН с изменяемой в процессе работы алгоритма матрицей затрат, а (13) - линейная задача по ц, решение которой может быть найдено по формуле

0, если и" + Vм < 1, ц" = любое, например, //л = цы~\ если и" + у" = 1, шах(4(хЛ,),4(хЛ,))> если и" + у" > 1. Схема метода решения задачи 2 представлена на рис. 1. В диссертации доказано следующее

Утверждение 2. Вычислительная сложность предложенного метода равна 0(//я3), где /-количество итераций.

Начальные данные и" >0, у°>0, N=0, Е>0, а\/

Матрица назначении Г

Пересчёт двойственных переменных и, V по субградиентной процедуре

Л*- оптимальное решение

да

нет А^- приближённое

решение

Рис. 1 - Алгоритм решения ЗОН с предпочтениями Таким образом, получена оптимизационная модель с целевыми функциями (1), (7) и ограничениями (2)-(4), формализующая задачу о назначениях с предпочте-

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

3. Задача о назначениях с конфликтами.

Предположение: существует множество групп пар индексов

Рк = {(/,/'): одновременное назначение запрещено}, к = \,К.

Интерпретация: наличие в коллективе конфликтных групп.

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

X к = ЦС, (14)

(/.У >е/1

где - группы пар индексов (/, _/), для которых индекс I соответствует пре-

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

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

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

™ » ( \ к

Ф(Х>У) = И11ХУ С!/+ Е Уь хеБ>

где 5- множество переменных {х^}, удовлетворяющих условиям (2)-(4) ЗОН.

В результате на каждой итерации при фиксированных значениях двойственных переменных ук, к = 1,К, необходимо решить ЗОН вида

ЕЕ*

V * Ни%Рк " 1

В.качестве критерия останова используются неравенства (14). Для данного метода также имеет место Утверждение 2 о вычислительной сложности.

Таким образом, получена оптимизационная модель с целевой функцией (1) и ограничениями (2)-(4), (14), формализующая задачу о назначениях с запретами на одновременный выбор из каждой группы более одного элемента, а также точный и приближённый численные методы решения в зависимости от количества конфликтных ограничений.

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

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

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

W = TL4XÖ min. 1ЛУ) = ¿¿Ф', "» min (15)

i=l 7=1 1=1 J=1

=], у с {у : ¿,„>1}, ¿.Vr<l, i = (16)

¡=i ы j,i

w w m

ZV» =1, у 6 {; e P: = 0, > 1 }, v.. ^ ' = (17>

1=1 /=1 i=l jeP

i^r _ ___

={0,1}, / = l,m,7 = 1,n,yt ={0,1}, i = l,m, j e P, (19)

где 5 = {■y,y}ntxn _ матрица запретов на назначения, D = {d^ ^ - матрица согласия

претендентов на обучение, С1 = {<4}т ^ и С2 = {cj} - матрицы затрат, связанных

с назначением на работу и с обучением соответственно, Р - множество работ, которым предприятие имеет возможность обучать претендентов.

В модели использованы стандартные переменные xtj и переменные

_ (1, если 1-й претендент направлен на обучение j - й работе, У'> ~ (0, иначе.

В диссертации доказано следующее утверждение об оценке нижней границы количества претендентов.

Утверждение 3. Задача (15)-(19) совместна при условии, что т>п + \р\.

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

Численный метод для аддитивного критерия является приближённым и основан на использовании венгерского алгоритма с последующей корректировкой. На первом этапе данного метода решается ЗОН с запретами для переменной х с матрицей затрат С1. На втором этапе анализируются полученные результаты, на основе которых корректируется матрица затрат С2 и решается задача относительно у. На третьем этапе определяется решение на основе вычисления суммарных затрат. При необходимости последовательность решаемых задач может быть изменена.

В диссертации доказано следующее

Утверждение 4. Вычислительная сложность предложенного метода равна О(т').

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

Имеет место следующее

Утверждение 5. Нелинейное ограничение (18) эквивалентно заменяется линейным ограничением вида

«'=£«• (20)

j=l j^P

Ограничение (20) убирается в лагранжиан для применения алгоритма Удзавы.

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

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

->min... ->min (21)

Ы j=1 ¿=1 j=l т ___

£4=1, k = \.K,j = \,nk, (22)

■=i

]>Х<1, i = üi, k = lK, (23)

¿f>><l, / = 1^, (24)

*=i j-1 _

^ ={0,1}, / = йЯ k = lK, j = üh, (25)

где m - количество претендентов, К - число предприятий и i\,...,nk- количество работ на каждом предприятии соответственно, Ск = {с*} , к = \,К - матрицы затрат, связанных с назначением /-го претендента на у'-е место на к-м предприятии.

В диссертации доказано следующее утверждение для оценки нижней границы количества претендентов.

К

Утверждение 6. Задача (21)-(25) совместна при условии, что т >

к= 1

Заметим, что ограничения (23) являются следствием (24), однако для удобства дальнейшей алгоритмизации они не убираются из модели. (22) и (23) являются стандартными ограничениями ЗОН по каждому фиксированному предприятию, а (24) означает, что один и тот же претендент не может быть одновременно назначен на работу на нескольких предприятиях.

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

В связи с тем, что каждое предприятие заинтересовано минимизировать свои затраты, то на основе принципа гарантированного результата в задаче (21)-(25) целесообразно перейти к целевой функции

min {max (L, (X,), ¿2 (JQ,..„ (Хх))}.

Задача (21)-(25) переписывается в эквивалентной форме р —> min

±±xl<\, / = ПЯ

*=1 >=1

xJ.eS, 1 = 1,т, к = \,К, ] = \,пк, !1> О,

а функция Лагранжа после преобразований имеет вид для и, и> > 0, х е 5, // > О

Ф(х,//,«,*>) = ¿¿(«,4 + и>,Ц + ... + + н-,)л£ 1 -Е"» I-

1=1 ;=1 1=1 V 1=1 )

Возможно несколько альтернативных вариантов структуры множества 5 .

1. Если в качестве $ выбирается множество | х' |, удовлетворяющих ограничениям (22), (23) и (25) задачи, то на каждой н'герации при фиксированных значениях двойственных переменных ик, к = \,К, и и;, 1 = 1,т, будут решаться венгерским методом ЗОН вида

к = йК. (26)

,.1

2. Если в множество 5 выбрать ограничения (22) и (25), убрав из рассмотрения ограничение (23) в силу его избыточности, то на каждой итерации будет решаться задача

1 = 1 ] = \ * = 1

2>®'=Ь (28)

1=1 ___

дг* = {0,1}, «=Гй, у=й, к = \^К, (29)

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

Кроме описанных выше задач, вид которых зависит от выбора множества 5, на каждой итерации решается задача

В силу определения переменной /< справедливы ограничения О < // < тах(Ь1(Х^),...,Ьк(Хк")), тогда задача (30) по // решается следующим образом:

0, если ^м» < 1,

к

любое, например,=//"', если У, — 1,

»-1

гтих^Х,"),...,^ (*/)), если £^>1.

1=1

Схема метода для решения задачи (21)-(25) представлена на рис. 2. В диссертации доказаны следующие утверждения.

Утверждение 7. Вычислительная сложность метода с использованием венгерского алгоритма равна 0(1Кт3), где I - количество итераций.

Утверждение 8. Вычислительная сложность метода с независимой минимиза-

к

цией по столбцам равна 0(1тп), где I- количество итераций и и = ^Г /¡,.

1=1

Рис. 2 - Схема метода для решения многокритериальной ЗОН Таким образом, предложены методы решения многокритериальной ЗОН, основанные на разных способах построения функции Лагранжа (рис. 2).

В четвёртой главе описывается структура программного комплекса «Задача о назначениях с дополнительными требованиями», реализованного в среде BorlandDelphi 7.0 и предназначенного для решения предложенными методами ЗОН с дополнительными требованиями. На рис. 3 изображена структура данного комплекса.

Проблемно-ориентированная часть

| Задача с запретами | | Задача с предпочтениями | Задача с конфликтами

Задача с возможностью обучения Многокритериальная задача

Вывод и интерпретация ответа

Инвариантная часть

Формирование информационной среды Библиотека методов

Инициализация алгоритмов и методов

Задание размерности задачи

Методы решения предложенных задач

Задание входных матриц, требуемых для задачи * *

Алгоритм венгерского метода

Выбор метода решения Одномерная минимизация

Задание пользовательских данных метода —» Алгоритм метода Удзавы *

Рис. 3 - Структура программного комплекса 12

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

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

К основным выводам вычислительного эксперимента относятся следующие.

1. Для решения многокритериальных ЗОН с числом строк каждой матрицы т< 30 целесообразно применять метод с использованием венгерского алгоритма на ка>вдо^те|тци1^(£те^4) для получения точного^ешеншг__

X

:ф О

э 2

а> TI

П

й гг

X 3

t м

■ 2x10x5 3x30x10

■ 4x32x8

От 100 до 500 От 500 до 1000 Более 1000 Количество итераций

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

2. Для задач большей размерности целесообразно использовать метод с независимой минимизацией по столбцам с дополнительным остановом по времени работы (рис. 5). В случае получения недопустимой точки, в диссертации предлагается метод корректировки. _____

I 5

ш •—•

Ф CQ

1 О

о CQ

Р I

О я

5 О

с;

2x200x100

4x200x50

3x150x50 Размерность задачи

■ Методе использованием венгерского алгоритма (первая итерация) ш Метод с использованием венгерского алгоритма (последняя итерация) Метод с независимой минимизацией (первая итерация) Метод с независимой минимизацией (последняя итерация)

Рис. 5 - Зависимость количества невыполненных ограничений-остановов от выбранного метода решения при останове по времени 1 минута

3. Сходимость субградиентного метода, используемого в предложенных методах для пересчёта двойственных переменных, существенным образом зависит от способа выбора на каждой итерации шагов перемещения а" и/?" . Вычислительный эксперимент показал, что для задач размерности т < 20 необходимо использовать следующие величины шагов:

, та хс*

в*=-!—. В" =

N + 1

ЛГ + 1

Для задач большей размерности целесообразней использовать

тахс*

N+1

¡,1,к

ТУн 1-

N < тах с

¡,],к '

N

(31)

(32)

ЛГ +1

иначе,

где Л' - номер итерации.

4. Предложенные в диссертации методы являются полиномиальными, что подтверждается утверждениями о вычислительной сложности и показано на рис. 6.

Размерность задачи

—метод с использованием венгерского алгоритма

&»методс использованием независимой минимизации

А полный перебор допустимых решений

Рис. 6 - Зависимость времени, необходимого для получения оптимального решения от размерности задачи

В заключении излагаются основные результаты диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

Публикации по теме исследования

Публикации в изданиях, рекомендованных ВАК РФ

1. Малюгина О. А. Использование двойственных методов для решения одной многокритериальной задачи о назначениях / О. А. Малюгина, С. Н. Медведев, Г. Д. Чернышева // Вестн. Воронеж, гос. ун-та. Серия: Системный анализ и информационные технологии. - Воронеж: Воронеж, гос. ун-т., 2010. - № 1. - С. 31-34.

2. Медведева О. А. Использование двойственных методов для решения трёх-индексной задачи о назначениях / О. А. Медведева, С. Н. Медведев, Г. Д. Чернышева // Вестн. Воронеж, гос. ун-та. Серия: Системный анализ и информационные технологии. - Воронеж: Воронеж, гос. ун-т., 2011. - № 2. - С. 32-35.

3. Медведева О. А. Задача о назначениях с возможностью обучения / О. А. Медведева // Вестн. Санкт-Петербургского университета. Серия: Прикладная математика, информатика, процессы управления. - Санкт-Петербург: Изд-во Санкт-Петербургского университета, 2013. - Серия 10, Выпуск 1. - С. 85-94.

Статьи и материалы конференций

4. Малюгина О. А. Задача комплектования штатов / О. А. Малюгина, С. Н. Медведев, Г. Д. Чернышева // Системное моделирование социально-экономических процессов: Тр. 31-й Междунар. шк.-сем., Воронеж, 1-5 октября 2008г. - Воронеж: Воронеж, гос. ун-т., 2008. -Ч. П1. - С. 265-272.

5. Малюгина О. А. Комплектование штатов при наличии обучения / О. А. Малюгина, С. Н. Медведев, Г. Д. Чернышова // Системное моделирование социально-экономических процессов: Тр. 32-ой Междунар. шк.-сем., Вологда, 5-10 октября 2009г. - Воронеж: Воронеж, гос. ун-т., 2009. - Ч. II. - С. 425-427.

6. Малюгина О. А. Использование задачи о назначениях при решении проблемы формирования штатов / О. А. Малюгина, Г. Д. Чернышова // Вестн. факультета

15

прикладной математики, информатики и механики. - Воронеж: Воронеж, гос. ун-т., 2010.-Вып. 8.-С. 141-148.

7. Малюгина О. А. Алгоритмизация задач, возникающих при комплектовании штатов / О. А. Малюгина // КРОМШ-2010: Тез. док. 21-ой ежегодн. Междунар. конф. - Симферополь: Изд-во КНЦ НАНУ, 2010. - С. 29.

8. Малюгина О. А. Многокритериальная трёхиндексная задача о назначениях / Г. Д. Чернышева, О. А. Малюгина, С. Н. Медведев // КРОМШ-2011: Тез. док. 22-ой ежегодн. Междунар. конф. - Симферополь: Изд-во КНЦ НАНУ, 2011. - С. 55. http://www.kromsh.info/files/abstracts/abstracts-2011 .р<1Г

9. Медведева О. А. Применение адаптивного алгоритма для решения нечёткой задачи о назначениях / О. А. Медведева, С. Н. Медведев // Аналитические и численные методы моделирования естественнонаучных и социальных проблем: Сб. ст. VI Междунар. науч.-техн. конф., Пенза, 25-29 октября 2011г. - Пенза: АННОО «Приволжский Дом знаний», 2011. - С. 78-81.

10. Медведева О. А. Программный комплекс для решения различных модификаций задачи о назначениях / О. А. Медведева, С. Н. Медведев // Матер. Всерос. мо-лодеж. науч. шк., Воронеж, 29-30 июня 2012г. - Воронеж: ООО ИПЦ «Научная книга», 2012.-С. 191-192.

11. Медведева О. А. Задача комплектования штатов / О. А. Медведева, С. Н. Медведев // Актуальные проблемы прикладной математики, информатики и механики: Сб. тр. Междунар. конф., Воронеж, 26-28 ноября 2012 г.: в 2 ч. - Воронеж: ИПЦ Воронеж, гос. ун-та, 2012. - Ч. 2. - С. 203-208.

12. Медведева О. А. Задача о назначениях с дополнительными условиями / О. А. Медведева // Современные методы прикладной математики, теории управления и компьютерных технологий: сборник трудов VI Междунар. конф., Воронеж, 10-16 сентября 2013 г. - Воронеж: Воронеж, гос. ун-т., 2013. - С. 158-160.

Свидетельства о государственной регистрации программ для ЭВМ

13. Медведева О. А. Программный комплекс для решения различных модификаций задачи о назначениях / О. А. Медведева, С. Н. Медведев // Свидетельство о гос. регистрации программы для ЭВМ №2012618203, РФ, 2012.

14. Медведева О. А. Программный комплекс для решения многокритериальной трёхиндексной задачи о назначениях / О. А. Медведева, С. Н. Медведев // Свидетельство о гос. регистрации программы для ЭВМ №2012617580, РФ, 2012.

Подписана в печать 06.И.13. Формат60*84 7,6. Усл. иеч. л. L Тираж 100 экз. Заказ 1118.

Отпечатано с готового оригинал-макета в типографии Издательско-гю л и графического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

04201451564

Медведева Ольга Александровна

МОДЕЛИ И АЛГОРИТМЫ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ С ДОПОЛНИТЕЛЬНЫМИ ОГРАНИЧЕНИЯМИ

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

ДИССЕРТАЦИЯ

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

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

доктор технических наук, профессор

Леденёва Татьяна Михайловна

Воронеж - 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ........................................................................................4

ГЛАВА 1. АНАЛИЗ РАЗНОВИДНОСТЕЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ.........10

1.1 Обзор моделей и алгоритмов решения существующих разновидностей задачи о назначениях..............................................................................10

1.2 Постановка классической задачи о назначениях и венгерский метод её решения.....................................................................................22

1.3 Открытая (несбалансированная) задача о назначениях...........................29

1.4 Двойственный алгоритм Удзавы......................................................31

1.5 Цели и задачи исследования............................................................41

Выводы по первой главе.......................................................................43

ГЛАВА 2. ЗАДАЧИ О НАЗНАЧЕНИЯХ С ДОПОЛНИТЕЛЬНЫМИ УСЛОВИЯМИ..................................................................................45

2.1 Задача о назначениях с запретами.....................................................45

2.2 Задача о назначениях с предпочтениями............................................53

2.3 Задача о назначениях с запретами и предпочтениями.............................63

2.4 Задача о назначениях с конфликтами.................................................69

Выводы по второй главе......................................................................75

ГЛАВА 3. МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ..............77

3.1 Двухкритериальная задача о назначениях с возможностью обучения претендентов...............................................................................78

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

3.1.2 Алгоритм, основанный на применении двойственного алгоритма Удзавы....................................................................................88

3.2 Многокритериальная задача о назначениях с несколькими предприятиями.............................................................................98

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

„ 3.2.2 Алгоритмы, основанные на применении двойственного алгоритма

Удзавы..................................................................................102

Выводы по третьей главе.....................................................................116

ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РЕШЕНИЯ ПОСТАВЛЕННЫХ ЗАДАЧ..................................................................118

4.1 Описание программного комплекса..................................................118

4.2 Вычислительный эксперимент.........................................................124

Выводы по четвёртой главе...................................................................135

ЗАКЛЮЧЕНИЕ.................................................................................137

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ......................................139

ПРИЛОЖЕНИЯ.................................................................................151

Приложение А...................................................................................152

Приложение Б...................................................................................153

Приложение В...................................................................................154

Приложение Г...................................................................................158

ВВЕДЕНИЕ

Актуальность темы. Задача о назначениях, её линейные, квадратичные и многоиндексные разновидности привлекают внимание исследователей ввиду своей обширной применимости в различных областях научной и практической деятельности. К ним сводятся задачи, связанные с оптимальным распределением элементов на микросхемах, задачи планирования работы вычислительных, производственных, технологических систем, оптимизации перевозок, а также задачи составления расписаний. Содержательная постановка данной задачи формулируется следующим образом: пусть имеется п работ и п претендентов для выполнения этих работ. Назначение претендента / на работу у связано с затратами с0 (7, у = \,п). Требуется определить назначение, дающее минимальные суммарные

затраты, при этом каждого претендента можно назначить только на одну работу, и каждая работа может быть занята только одним кандидатом. С комбинаторной точки зрения допустимое решение этой задачи представляет собой перестановку ж = (7г1,...,7гп) чисел I, ..., п, а соответствия вида / —> тг( (/ = 1,п) описывают произведённые назначения (/, тс1) (7-й претендент назначен на работу с номером 7г(). Тогда задача сводится к определению такой перестановки п, которая

п

минимизирует линейную целевую функцию ^ст. Данная задача, называемая

*=1

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

задачи о назначениях связаны с изучением различных целевых функций при стандартных ограничениях (R. Burkard, М. R. Garey, D. S. Johnson, О. Gross, R. М. Кагр, Э. X. Гимади) или с применением линейной свёртки критериев (И. В. Сергиенко, В. А. Емеличев, В. А. Перепелица, Р. Aneja).

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

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

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

Для достижения цели в работе решаются следующие основные задачи:

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

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

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

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

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

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

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

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

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

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

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

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

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

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

Тематика работы соответствует следующим пунктам Паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»: п. 2. Развитие качественных и приближенных аналитических методов исследования математических моделей; п. 3. Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий; п. 5. Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента.

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

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

Реализация и внедрение результатов работы. Результаты диссертационной работы используются в АУ ВО «Институт регионального развития» (г. Воронеж) для решения задач подбора кадров и управления персоналом, а так же в учебном процессе ФГБОУ ВПО «Воронежский государственный университет» при чтении спецкурсов и выполнении выпускных квалификационных работ.

Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на следующих международных и всероссийских конференциях: Международная школа-семинар «Системное моделирование социально-экономических процессов» (Воронеж, 2008, Вологда, 2009); Ежегодная Международная конференция КРОМШ (Симферополь, 20102011); Международная научно-техническая конференция «Аналитические и численные методы моделирования естественнонаучных и социальных проблем» (Пенза, 2011); Всероссийская молодежная научная школа «Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 2012); Международная конференция «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2012); Международной конференции «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2013).

Публикации. Основные результаты диссертации опубликованы в 12 научных работах, в том числе 3 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежат: [35] -модель двухкритериальной задачи о назначениях с возможностью обучения претендентов и детальная разработка двойственного алгоритма её решения; [39] -детальная разработка и наполнение шагов двойственного алгоритма решения многокритериальной трёхиндексной задачи о назначениях; [33] - введение запретов в математическую модель трёхиндексной задачи о назначениях; [34] -математическая модель задачи о назначениях с возможностью обучения претендентов и алгоритм её решения; [36] - модели задач и конкретизация их решения на основе венгерского метода, теорема о величине «штрафа» в задаче с запретами; [40] - введение нормировки целевых коэффициентов и строк матрицы вероятностей; [41] - модуль программы, связанный с учётом дополнительных условий в задаче о назначениях; обзорный доклад по результатам исследования [42] - подходы к моделированию задач о назначениях с дополнительными условиями и их решению с использованием венгерского метода и двойственного алгоритма Удзавы.

Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка используемых источников из 117 наименований, и приложений. Основная часть работы изложена на 138 страницах и включает 17 рисунков и 7 таблиц.

ГЛАВА 1. АНАЛИЗ РАЗНОВИДНОСТЕЙ ЗАДАЧИ О

НАЗНАЧЕНИЯХ

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

1.1 Обзор моделей и алгоритмов решения существующих разновидностей задачи о назначениях

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

Линейная задача о назначениях

Наибольшее распространение и известность получила линейная задача о назначениях [7], которая может быть сформулирована следующим образом: пусть заданы п2 коэффициентов с , г,у=1 ,п. Требуется найти перестановку ср такую, что

п

где Бп - множество всех перестановок чисел {1, ... , «}.

Можно представить данную задачу как задачу целочисленного линейного программирования с суммарной целевой функцией [28, 29].

п п

,=1 7=1

и _

=1' j = l>n>

1=1

п _

7=1

Ху = {ОД}, /,у' = 1,л.

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