Модели и алгоритмы решения многокритериальных задач о назначениях с дополнительными ограничениями тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Медведева, Ольга Александровна

• Медведева, Ольга Александровна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Медведева, Ольга Александровна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Удзавы

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЯ

Приложение А

Приложение Б

Приложение В

Приложение Г

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы решения многокритериальных задач о назначениях с дополнительными ограничениями»

ВВЕДЕНИЕ

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

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

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

Этот пример показывает, что существуют различные виды целевых функций. В случае минимизации стоимости обычно используется суммарная целевая функция. Если минимизируется время, часто используется минимаксная целевая функция, и хотя её запись не является линейной, задачу оптимизации с такой целевой функцией называют «линейной» в отличие от квадратичных задач.

Задача о назначениях с минимаксным критерием оптимальности (задача на «узкое место») [88, 90, 101] может быть записана в виде

Ь(Х) = шах с х -» шт

1,7=1 ,п 1 }

п _

=1> J=l>n>

1=1

п _

7=1

^ ={0,1}, /,у' = 1 ,п.

Представленные модели описывают так называемый закрытый вариант задачи о назначениях, при этом предполагается, что количество рабочих равно количеству работ. Однако известна и открытая форма задачи, в которой количество претендентов не равно числу вакантных работ [2].

Линейная задача о назначениях может быть рассмотрена как частный случай известной транспортной задачи Хичкока-Купманса [11, 67, 88], которая формулируется следующим образом:

Имеется т пунктов производства (А1>...,Ат) и п пунктов потребления

(Вх,...,Вп). Заданы объёмы производства а1 каждого пункта производства и

размеры спроса bJ каждого пункта потребления. Известны также транспортные

издержки с , связанные с перевозкой единицы продукции из пункта А1 в пункт

В). Требуется составить план перевозок, обеспечивающий при минимальных

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

Математическая модель задачи имеет вид

т п

,=1 7=1

п _

2Х=а«> 1=1 ,т,

7=1

т _

2Х J = l>n>

1=1

т п

,=1 7=1

х >0, I = \,т,] = \,п.

Частным случаем данной задачи, где все объёмы производства и размеры спроса равны единице

а1 = 1, / = 1 ,т, Ъ} =1,у=1,и,

является линейная задача о назначениях.

Такая постановка транспортной задачи предполагает, что любая пара пунктов производства и пунктов потребления связана коммуникацией. Однако во многих практических задачах это требование нарушается. В связи с этим существует транспортная задача с запретами, в которой переменные, отвечающие отсутствующим коммуникациям, заранее полагаются равными нулю [2, 11].

Алгоритмы решения линейной задачи о назначениях

В 1949 году Кантаровичем А. В. и Гавуриным М. К. был предложен первый точный метод решения транспортной задачи - метод потенциалов [11]. Он позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число шагов (итераций). Данный метод применим и для линейной задачи о назначениях.

Первый полиномиальный алгоритм для решения линейной задачи о назначениях был предложен в середине 1950-х г. Куном [108, 109], в его оригинальной формулировке он имеет 0(п4) временную сложность. В 1953, изучая книгу по теории графов Денеша Кёнига [107], он столкнулся с

эффективным алгоритмом для определения паросочетания максимальной мощности двудольного графа. Эта задача эквивалентна линейной задаче о назначениях с переменными из множества {0,1}. Сноска в книге Кёнига указала на статью Эгервари [94], где рассмотрен метод приведения общей задачи о назначениях к конечному числу задач с элементами из {0,1}. Комбинация приведения Эгервари и алгоритма поиска паросочетания максимальной мощности Кёнига привела к получению эффективного алгоритма решения линейной задачи о назначениях, который Кун назвал "венгерским методом" в честь этих двух венгерских математиков. Позже были разработаны модификации классического венгерского метода, имеющие временную сложность 0(п3) [93, 105].

В 1960 г. А. Лэндом и А. Дойгом был предложен метод ветвей и границ [51, 69, 111] для решения общей задачи целочисленного линейного программирования. Интерес к этому методу в частности связан с широкими возможностями его применения к различным задачам комбинаторной оптимизации, таким как задача коммивояжера [64, 112] или линейная задача о назначениях.

В начале 1970-х г. разработан алгоритм поиска кратчайшего пути на приведенных матрицах затрат [13, 93]. Первые симплексные алгоритмы для решения задачи о назначениях, предложенные в середине 1970-х г. [59, 80], хорошо работали на практике, но теоретически были экспоненциальными из-за сильной вырожденности линейной задачи о назначениях. Позже, в 1993 г. был предложен полиномиальный прямой симплексный алгоритм [76, 88]. В 2012 г. в [65] был разработан итеративный алгоритм решения, основанный на декомпозиции исходной задачи на ряд двумерных оптимизационных задач с последовательно модифицируемыми целевыми функциями.

В 1991 г. Д. Бертсекас [81, 82] предложил двойственный алгоритм, имеющий псевдо-полиномиальную временную сложность, но на практике показавший высокую среднюю эффективность (аукционный алгоритм). Самые

известные двойственные симплексные алгоритмы для задачи о назначениях -называемые сигнатурные методы - предложены в середине 1980-х г. [79].

так

Квадратичная задача о назначениях

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

Впервые квадратичная задача о назначениях была сформулирована как задача о распределении заводов по локациям [58, 114]. Пусть необходимо распределить п заводов между п локациями. Заданы три входные матрицы размера п х п: А-(а1к), В = (Ь^), С = (су), где а1к - поток физических

продуктов между заводами г и к, - расстояние между локациями у и /, и с(у -

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

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

п п п п п п

цх)+ тш

,=1 у =1 к=1 /=1 1=1 у=1

п _

7=1

п _

=1>

1=1

хуе{0,1}, 1,у' = 1, л.

Для линейных задач о назначениях существуют эффективные полиномиальные методы решения, позволяющие решать задачи больших размерностей. Однако для квадратичных задач о назначениях таких методов нет, так как они относятся к классу ТУР-полных [16, 62, 97]. Это означает, что оптимальное решение может быть найдено только полным перебором всех

возможных решений при Р ЫР. Кроме того, они принадлежат ядру Л(Р-полных задач в том смысле, что невозможно найти даже приближенное решение в пределах некоторого постоянного множителя от оптимального значения в полиномиальное время, если Р =£ МР. Самые большие квадратичные задачи о назначениях, для которых было определено оптимальное решение, имеют размер около п ~ 30 [60, 61]. Разработано много эвристических алгоритмов, которые приводят к более или менее хорошему субоптимальному решению, например, схема «табу-поиска» [98, 99], метод отжига [66, 85], генетические алгоритмы [26, 95, 103], итеративный локальный поиск [15, 75], метод муравьиной колонии [72, 89] и т.п.

Известна постановка квадратичной задачи о назначениях в терминах графов (сетей). Структура связей между размещаемыми объектами при этом представлена с помощью реберновзвешенного графа без петель и кратных ребер. Вершины соответствуют размещаемым объектам, а ребра указывают на наличие связей между ними. Веса ребер отражают удельные стоимости связей. Позиции, в которые производится размещение, являются узлами сети. Критерий -минимальная суммарная стоимость связей между объектами. В данном случае интерес представляет построение полиномиальных алгоритмов для специальных видов графов и сетей. В [46] предложен эффективный алгоритм локальной оптимизации в случае, когда граф и сеть состоят из двух долей. Если граф и сеть представляют собой изоморфные деревья, то квадратичная задача о назначениях разрешима за полиномиальное время алгоритмом динамического программирования [88]. Полиномиальные алгоритмы решения квадратичной задачи о назначениях на невзвешенной цепи для специальных невзвешенных графов приведены в [24]. В [22, 23] предложен ряд полиномиальных алгоритмов решения квадратичной задачи о назначениях для специальных видов графов и сетей. В частности, рассматривается размещение цепи и цикла на древовидной взвешенной сети.

Иногда рассматриваются кубические и биквадратные (четвертые степени) целевые функции по множеству назначений. Это приводит к кубическим и биквадратным задачам о назначениях [86, 87].

Генетические методы решения

В последнее время большое распространение получили генетические методы, неоднократно положительно зарекомендовавшие себя при решении NP-полных задач [1, 4]. В теории моделирования эволюции структура и качество поколения потомков во многом зависит от того, между какими особями происходит скрещивание. Здесь существуют разные подходы, такие как введение в генетический алгоритм макроэволюции, то есть развития нескольких субпопуляций [6], использование эффекта самоорганизации при работе генетического консилиума [55], различных видов селекции [5, 26] и т.д. Кроме того, генетические алгоритмы в результате предоставляют не одно, а целое множество приближённых решений [100], и по этому множеству можно организовать поиск по дополнительным критериям, не учтённым в исходной постановке.

Трёхиндексные задачи о назначениях

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

Математическая модель аксиальной трёхиндексной задачи о назначениях [57, 88] имеет вид:

п п п

L{X) = min

/=1 j~\ к=\

п п _

II**=1. г"=1'п'

7=1 к=1

п п _

IIxijk=l J = l>n>

i=1 к=]

п п

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

Известно, что аксиальная трёхиндексная задача о назначениях является А(Р-полной и никакой полиномиальный алгоритм не может достигнуть постоянного показателя эффективности, если Р Ф ЫР [106].

Для данной задачи существует алгоритм решения [57, 102], аналог венгерского метода для линейных задач о назначениях. Также известны эвристические алгоритмы [10, 57, 74, 104], многие из которых являются модификациями точных методов, примененных как приближенные.

Другая разновидность трёхиндексной задачи о назначениях - планарная задача [57, 88]. Решение данной задачи представляет собой куб, в каждой горизонтальной или вертикальной плоскости которого стоят матрицы назначений. Соответствующая целочисленная задача линейного программирования имеет вид

п п п

С»кХук тШ

,=1 7=1 к=1

п

п

п

Данная задача также является //Р-полной [96].

^ Для планарной трёхиндексной задачи о назначениях известно не так много алгоритмов решения, в частности существует несколько методов ветвления, основанных на связи задачи с понятием латинского квадрата [113, 116].

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

Двухуровневые задачи о назначениях

В последние годы внимание исследователей привлекают двухуровневые задачи математического программирования, в частности двухуровневая задача о назначениях [12, 31]. Суть её в том, что работодатель (верхний уровень) способен предложить любую совокупность из п видов работ, которые выполняются т исполнителями (нижний уровень). Задача нижнего уровня заключается в поиске такого назначения, которое максимизирует суммарный доход исполнителей. Задача верхнего уровня состоит в минимизации затрат заказчика с учётом реакции исполнителей.

Список литературы диссертационного исследования кандидат наук Медведева, Ольга Александровна, 2013 год

СПИСОК ИСПОЛЬЗОВАННЫХ источников

1. Алгулиев Р. М. Генетический подход к оптимальному назначению заданий в распределенной системе / Р. М. Алгулиев, Р. М. Алыгулиев // Искусственный интеллект, 2004. - Вып. 4. - С. 79-88.

2. . Афанасьев М. Ю. Исследование операций в экономике: модели, задачи,

решения. Учеб. пособие / М. Ю. Афанасьев, Б. П. Суворов. - М.: ИНФРА-М, 2003.-444 с.

3. Баева Н. Б. Основы теории и вычислительные схемы векторной оптимизации: Учебное пособие / Н.Б. Баева, Ю.В. Бондаренко. - Воронеж: Воронеж, гос. ун-т, 2003.-87 с.

4. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. - Ниж. Новгород: Нижегород. гос. ун-т, 1995. - 62 с.

5. Батищев Д. И. Применение генетических алгоритмов к решению задач дискретной оптимизации / Д. И. Батищев, Е. А. Неймарк, Н. В. Старостин. -Нижний Новгород: НГУ им! Лобачевского, 2007. - 88 с.

6. Белявский П. Г. Эволюционный подход к решению задачи о назначениях / П. Г. Белявский, Ю. О. Чернышев, Басова А. В. // Современные наукоёмкие технологии. - М.: Издательство РАЕ, 2006. - №5. - С. 34-35.

7. Вагнер Г. Основы исследования операций / Г. Вагнер [пер. с англ. Б. Т. Вавилова]. -М.: Мир, 1972 .-Т. 1.-335 с.

8. Васильев Ф. П. Методы оптимизации / Ф. П. Васильев. - М.: МЦНМО, 2011. -Т. 1.-620 с.

9. Волконский В. А. О множестве эффективных точек в линейных многокритериальных задачах / В. А. Волконский, Г. К. Еганян, А. Б. Поманский // Сиб. матем. журн., 1983. - Т. 24. - №2. - С. 9-17.

10. Гимади Э. X. Аксиальные трёхиндексные задачи о назначении и коммивояжера: быстрые приближённые алгоритмы и их вероятностный анализ / Э. X. Гимади, А. И. Сердюков // Известия высших учебных

заведений. Математика. - Казань: Казанский (Приволжский) фед. ун-т, 1999. -№12 (451).-С. 19-25.

11. Голыитейн Е. Г. Задачи линейного программирования транспортного типа / Е. Г. Гольштейн, Д. Б. Юдин. - М.: Наука, 1969. - 382 с.

12. Горбачевская Л. Е. Двухуровневая экстремальная задача выбора номенклатуры изделий / Л. Е. Горбачевская, Дементьев В. Т., Шамардин Ю.

B. - Новосибирск, 1997. - 26 с. - (Препринт / РАН. Сиб. отд-ние. Ин-т математики; №41)

13. Грешилов А. А. Прикладные задачи математического программирования: учебное пособие для ВУЗов. / А. А. Грешилов. - М.: Логос, 2006. - 286 с.

14. Грэхем Р. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник [Пер. с англ. В. В. Походзея]. - М.: Мир, 1998. - 704 с.

15. Гуляницький Л. Ф. Об одном подходе к использованию вероятностного моделирования в схеме генетического алгоритма / Л. Ф. Гуляницький, О. Я. Турчин // Тр. Межд. конф. по индуктивному моделированию, Львов, 20-25 мая 2002 г. - Львов: ГНИИ информационной инфраструктуры, 2002. - Т. 2. -

C. 275-281.

16. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри , Д. Джонсон [Пер. с англ.]. -М.: Мир, 1982.

17. Дементьев В. Т. Двухуровневая задача о назначениях при обобщенном условии Монжа / В. Т. Дементьев, Ю. В. Шамардин // Дискретный анализ и исследование операций. Серия 2, 2003. - Т. 10. - № 2. - С. 19-28.

18. Дичковская С. А. Исследование полиномиальных алгоритмов решения многокритериальной трехиндексной планарной задачи о назначениях / С. А. Дичковская, М. К. Кравцов // Журнал вычислительной математики и математической физики, 2007. - Т. 47. -№ 6. - С. 1077-1086.

19. Емеличев В. А. Полные задачи многокритериальной дискретной оптимизации / В. А. Емеличев, В. А. Перепелица. - Сообщения АН ГС СР, 1988.-Т. 131.-№3.-С. 501-504.

20. Емеличев В. А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах / В. А. Емеличев, В. А. Перепелица // ЖВМ и МФ, 1989. - Т. 29. - №2. - С. 171-183.

21. Емеличев В. А. Сложность дискретных многокритериальных задач / В. А. Емеличев, В. А. Перепелица // Дискретная математика, 1994. - Т. 6. - Вып. 1. -С. 3-33.

22. Забудский Г. Г. Полиномиальные алгоритмы решения квадратичной задачи о назначениях на сетях / Г. Г. Забудский, А. Ю. Лагздин // Журнал вычислительной математики и математической физики, 2010. - Т. 50. - №11. - С. 2052-2059.

23. Забудский Г. Г. Динамическое программирование для решения квадратичной задачи о назначениях на дереве / Г. Г. Забудский, А. Ю. Лагздин // Автоматика и телемеханика, 2012. - № 2. - С. 141-155.

24. Иорданский М.А. Задачи размещения графов / М. А. Иорданский // Комбинаторно-алгебраические методы в прикладной математике, Межвуз. сб. - Горький: ГГУ им. Лобачевского, 1982. - С. 26-65.

25. Кахичко А. А. О построении совершенных паросочетаний графа / А. А. Кахичко // Методы решения нелинейных задач и обработка данных. -Днепропетровск: ЛГУ, 1986. - С. 41-44.

26. Каширина И. Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида / И. Л. Каширина // Вестник ВГУ. Серия физика, математика. - Воронеж: ВГУ, 2003. - №1. - С. 128-131.

27. Каширина И. Л. Генетический алгоритм решения многокритериальной задачи о назначениях / И. Л. Каширина, Б. А. Семенов // Информационные технологии. - М.: Новые технологии, 2007. - Вып. 5. - С. 62-68.

28. Корбут А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкелыптейн [под ред. Д.Б. Юдина]. -М.: Наука, 1969. - 368 с.

29. Кофман А. Методы и модели исследования операций: Целочисленное программирование / А. Кофман, А. Анри-Лабордер [пер. с фр. Б. Т. Вавилова]. - М.: Мир, 1977. - 432 с.

30. Красс М. С. Основы математики и её приложения в экономическом образовании / М. С. Красс, Чупринов Б. П. - 2-е изд., испр. - М.: Дело, 2001. -688 с.

31. Ларин Р. М. Двухуровневая задача о назначениях / Р. М. Ларин, А. В. Пяткин // Дискретный анализ и исследование операций. Серия 2- Новосибирск: Институт математики им С.Л.Соболева СО РАН, 2001. -Том 8. - №2. - С. 4251.

32. Ларичев О. И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах / О. И. Ларичев. - М. : Логос, 2000. - 296 с.

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

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

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

36. Малюгина О. А. Использование задачи о назначениях при решении проблемы формирования штатов / О. А. Малюгина, Г. Д. Чернышова // Вестн. факультета прикладной математики, информатики и механики. -Воронеж: Воронеж, гос. ун-т., 2010. -Вып. 8 - С. 141-148.

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

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

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

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

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

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

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

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

конф., Воронеж, 10-16 сентября 2013г. - Воронеж : Воронеж, гос. ун-т., 2013,-С. 158-160.

%

45. Меламед И. И. Методы оптимизации в транспортном процессе / И. И. Меламед // ВИНИТИ, Сер. Организация управления транспортом, 1991. -Вып. 10.-С. 1-164.

46. Метельский Н. Н. Методы локальной оптимизации для задачи размещения двудольных графов / Н. Н. Метельский // Журнал вычислительной математики и математической физики, 1984. - Т. 24. -№9. - С. 1428-1432.

47. Мину М. Математическое программирование. Теория и практика / М. Мину [Пер. с фр. А.И. Штерна]. - М.: Наука, 1990. - 488 с.

48. Никонов О. Я. Математические методы решения многокритериальной задачи о назначениях / О. Я. Никонов, О. А. Подоляка, А. Н. Подоляка, Е. В. Скакалина // Вестник ХНАДУ. - Харьков: ХНАДУ, 2011. - Вып. 55. - С. 103112.

49. Ногин В. Д. Границы применимости распространенных методов скаляризации при решении задач многокритериального выбора / В. Д. Ногин // Методы возмущений в гомологической алгебре и динамика систем. Межвуз. сб. научн. тр. - Саранск: Изд-во Мордовского ун-та, 2004. - С. 5968.

50. Озерной В. М. Методология решения дискретных многокритериальных задач / В. М. Озерной, М. Г. Гафт // Многокритериальные задачи принятия решений. -М.: Машиностроение, 1978. - С. 14-47.

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

52. Перепелица В. А. Многокритериальные задачи теории графов. Алгоритмический подход / В. А. Перепелица. - Киев: УМК ВО, 1989.

53. Подиновский В. В. Парето-оптимальные решения многокритериальных задач / В. В. Подиновский, В. Д. Ногин. - М.: Наука, 2007. - 225 с.

54. Поляк Б. Т. Введение в оптимизацию / Б. Т. Поляк. - М.: Наука, 1983. - 384 с.

55. Протасов В. И. Решение сложных проблем методом генетического консилиума / В. И. Протасов, Н. И. Витиска, Е. В. Шустов // Тезисы докладов междунар. конф. "Интеллектуальные многопроцессорные системы (ИМС-2001)", 1-6 октября. - Геленджик, 2001. - С. 53-55.

56. Пяткин А. В. Д/Р-полнота двухуровневой задачи о назначениях / А. В. Пяткин. - Новосибирск, 2000. - 11 с. (Препринт / РАН. Сиб. отд-ние. Ин-т математики; №71).

57. Раскин Л. Г. Многоиндексные задачи линейного программирования / Раскин Л. Г., И. О. Кириченко. - М.: Радио и связь, 1982. - 240 с.

58. Рыбников К. К. Введение в дискретную математику и теорию решения экстремальных задач на конечных множествах: Уч. Пособие / К. К. Рыбников. - М.: Гелиос АРВ, 2010. - 320 с.

59. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы / Т. Саати. - М.: Мир, 1973.

60. Сергеев С. И. Квадратичная задача назначения I. Новые нижние границы в схеме парного назначения / С. И. Сергеев // Автоматика и телемеханика. -М.: Наука, 1999. - Вып. 8. - С. 127-147.

61. Сергеев С. И. Квадратичная задача назначения И. Улучшенный алгоритм Гилмора-Лоулера / С. И. Сергеев // Автоматика и телемеханика. - М.: Наука, 1999.-Вып. 9.-С. 137-143.

62. Сергеев С. И. Квадратичная задача о назначениях / С. И. Сергеев // Авиационная и ракетная техника. - 1999. - №8. - С. 127-147.

63. Сергиенко И. В. К проблеме нахождения множеств альтернатив в дискретных многокритериальных задачах / И. В. Сергиенко, В. А. Перепелица // Кибернетика, 1987. - №5. - С. 85-93.

64. Сигал И. X. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. Уч. пособие / И. X. Сигал, А. П. Иванова. - М.: ФИЗМАТЛИТ, 2003. - 240 с.

65. Тизик А. П. Итеративный алгоритм для задачи о назначении / А. П. Тизик, Д. И. Кузовлев, Ю. П. Тресков // Технические науки: теория и практика:

материалы междунар. науч. конф. (г. Чита, апрель 2012 г.). - Чита: Издательство Молодой ученый, 2012. - С. 41-43.

66. Тихонов А. С. О быстрых вариантах алгоритма отжига (simulated annealing) / А. С. Тихонов // Стохастическая оптимизация в информатике. - Санкт-Петербург: Издательство СПбГУ, 2009. - Вып. 5. - С. 65-90.

67. Триус Е. Б. Задачи математического программирования транспортного типа / Е. Б. Триус. - М.: Советское радио, 1967. - 206с.

68. Харари Ф. Теория графов / Ф. Харари. -М.: Мир, 1973.— 301 с.

69. Чернышова Г. Д. Дискретная оптимизация: Методическое пособие к курсу "Модели и методы дискретной оптимизации" / Г. Д. Чернышова, И. JI. Каширина. - Воронеж: Воронеж, гос. ун-т., 2003. - 26 с.

70. Чернышова Г. Д. Элементы теории двойственности. Учебно-методическое пособие для вузов / Г. Д. Чернышова, И. Н. Булгакова. - Воронеж : Воронеж, гос. ун-т., 2008. - 32 с.

71. Шварц Д. Т. Интерактивные методы решения задачи многокритериальной оптимизации. Обзор / Д. Т. Шварц // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 4. DOI: http ://dx.doi.org/l 0.7463/0413.0547747

72. Штовба С.Д. Муравьиные алгоритмы / С.Д. Штовба // Exponenta Pro. Математика в приложениях. - М.: Радиотехника, 2003. - №4. - С. 70-75.

73. Штойер Р. Многокритериальная оптимизация: теория, вычисления, приложения / Ральф Штойер [пер. с англ. Е. М. Столяровой]. - М.: Радио и связь, 1992.-504 с.

74. Aiex R. М. GRASP with path relinking for three-index assignment / R. M. Aiex, M. G. C. Resende, P. M. Pardalos, G. Toraldo // INFORMS J. Comput., 2005. -Vol. 17.-pp. 224-247.

75. Ahuja R. K. A survey of very large-scale neighborhood search techniques / R. K. Ahuja, O. Ergun, J. B. Orlin, A. P. Punnen // Discr. Appl. Math., 2002. - Vol. 123. -pp. 75-102.

76. Akgul M. A genuinely polynomial primal simplex algorithm for the assignment problem / M. Akgul // Discr. Appl. Math., 1993. - Vol. 45. - pp. 93-115.

77. Aneja P. Bicriterial transportation problem / P. Aneja, K. R. Nair // Manag. Sci., 1979.-Vol. 25. -№l.-pp. 73-78.

78. Arrow K. J. Studies in linear and non-linear programming / Kenneth J. Arrow, Leonid Nurwicz, Hirofumi Uzawa. - Stanford University Press: Stanford, California, 1958.-326 c.

79. Balinski M. L. Signature methods for the assignment problem / M. L. Balinski // Oper. Res., 1985. - Vol. 33. - pp. 527-536.

80. Barr R. S. The alternating basis algorithm for assignment problems / R. S. Barr, F. Clover, D. Klingman// Math. Programming, 1977. - Vol. 13. - pp. 1-13.

81. Bertsekas D. P. An auction algorithm for shortest paths / D. P. Bertsekas // SIAM Journal on Optimization, 1991. - Vol. 1. - pp. 425-447.

82. Bertsekas D. P. Linear Network Optimization: Algorithms and Codes / D. P. Bertsekas. - The MIT Press, Cambridge, MA, 1991.

83. Brucker P. Discrete parameter optimization problem and essential efficient points / P. Brucker//Operat. Res., 1972. - Vol. 16. - №5. - pp. 189-197.

84. Burkard R. E. Efficiency and optimality in minisum, minimax 0-1 programming problems. / R. E. Burkard, J. Krarup, P. M. Pruzan // Oper. Res. Soc., 1982. - Vol. 33,-№2.-pp. 137-151.

85. Burkard R.E. A thermodynamically motivated simulation procedure for combinatorial optimization problems / R. E. Burkard, F. Rendl // European J. Oper. Res., 1984. - Vol. 17. - pp. 169-174.

86. Burkard R. E. On the biquadratic assignment problem / R. E. Burkard, E. Cela, B. Klinz // Quadratic Assignment and Related Problems, DIM ACS Series, 1994. -Vol. 16.-pp. 117-146.

87. Burkard R. E. Heuristics for biquadratic assignment problems and their computational comparison / R. E. Burkard, E. Cela // European J. Oper. Res., 1995.-Vol. 83.-pp. 283-300.

88. Burkard R. Assignment problems / Rainer Burkard, Mauro Dell'Amico, Silvano Martello. - Society for industrial and Applied mathematics, Philadelphia, 2009. -382 p.

89. Colorni A. The ant system: Optimization by a colony of cooperating agents / A. Colorni, M. Dorigo, V. Maniezzo // IEEE Trans. Syst. Man Cybernetics, 1996. -Vol. 26.-pp. 29-41.

90. Derigs U. An augmenting path method for solving linear bottleneck assignment problems / U. Derigs, U. Zimmermann // Computing, 1978. - Vol. 19. - pp. 285295.

91. Derigs U. Monge sequences and a simple assignment algorithm / U. Derigs, O. Goecke, R. Schrader // Discrete Appl. Math., 1986. - Vol. 15. - № 2. - pp. 241248.

92. Easterfield T. E. A combinatorial algorithm / T. E. Easterfield // J. London Math. Soc., 1946. - Vol. 21. - pp. 219-226.

93. Edmonds J. Theoretical improvements in algorithmic efficiency for network flow problems / J. Edmonds, R. M. Karp // J. ACM, 1972. - Vol. 19. - pp. 248-264.

94. Egervary J. Matrixok kombinatorius tulajdonsagairol [On combinatorial properties of matrices] / J. Egrvary // Matematikai es Fizikai Lapok (in Hungarian), 1931. -Vol. 38.-pp. 16-28.

95. Fleurent C. Genetic hybrids for the quadratic assignment problem / C. Fleurent, J. A. Ferland // Quadratic Assignment and Related Problems, DIMACS Series, 1994.-Vol. 16.-pp. 173-187.

96. Frieze A. M. Complexity of a 3-dimensional assignment problem / A.M. Frieze // European J. Oper.Res., 1983.-Vol. 13.-pp. 161-164.

97. Garey M. R. Computers and Intractability: A Guide to the Theory of NP-Completeness / M. R. Garey, D. S. Johnson. - W. H. Freeman and Company, New York, NY, 1979.

98. Glover F. Tabu search - Part I / F. Glover // ORSA J. Comput., 1989. - Vol. 1. -pp. 190-206.

99. Glover F. Tabu search - Part II / F. Glover // ORSA J. Comput., 1990. - Vol. 2. -pp. 4-32.

100. Goldberg D. E. A practical schema theorem for general algorithm design and tuning / K. A. Sastry, D. E. Goldberg. - 2001.

101. Gross O. The bottleneck assignment problem // Technical Report P-1630, The Rand Corporation. - Santa Monica, California, 1959.

102. Hansen P. A primal-dual algorithm for the three-dimensional assignment problem / P. Hansen, L. Kaufman // Cahiers du CERO, 1973. - Vol. 15. - pp. 327-336.

103. Holland J. H. Adaptation in Natural and Artificial Systems / J. H. Holland. -University of Michigan Press, Ann Arbor, MI, 1975.

104. Huang G. A hybrid genetic algorithm for the three-index assignment problem / G. Huang, A. Lim // European J. Oper. Res., 2006. - Vol. 172. - pp. 249-257.

105. Jonker R. Improving the Hungarian assignment algorithm / R. Jonker and A.T.Volgenant // Oper. Res. Lett., 1986. - Vol. 5. - pp. 171-175.

106. Karp R. M. Reducibility among combinatorial problems / R. M. Karp // Complexity of Computer Computations, 1972. - pp. 85-103.

107. Konig D. Theorie der Endlichen und Unendlichen Graphen. Akademische Verlagsgesellschaft / D. Konig. - Leipzig, 1936.

108. Kuhn H. W. The hungarian method for the assignment problem / H. W. Kuhn // Naval Research Logistics Quarterly, 1955. - Vol. 2. - pp. 83-97.

109. Kuhn H. W. Variants of the Hungarian method for assignment problems / H. W. Kuhn // Naval Research Logistics Quarterly, 1956. - Vol. 3. - pp. 253-258.

110. Kung H. T. On finding the maxima of set of vectors. / H. T. Kung, F. Luccio, F. P. Preparata // Assoc. Comput. Mach., 1975. - Vol. 22. - №4. - pp. 469-476.

111. Land A. H. An autmatic method of solving discrete programming problems / A. H. Land, A. G. Doig // Econometrica, 1960. - Vol. 28. - pp. 497-520.

112. Little J. D. C. An algorithm for the traveling salesman problem / J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel // Operations Research, 1963. - Vol. 11. - pp. 972-989.

113. Magos D. An algorithm for the planar three-index assignment problem / D. Magos, P. Miliotis // European J. Oper. Res., 1994. - Vol. 77. - pp. 141-153.

114. Misevicius A. A tabu search algorithm for the quadratic assignment problem / A. Misevicius // Computational optimization and applications, 2005. - Vol. 30. - pp. 95-111.

115. Perepelitza V. A. On finding Pareto set for the discrete multiobjective problem / V. A. Perepelitza // Hth IFIP Conference on System Modelling and Optimization (Leipzig, July 3-7). - Leipzig, 1989. - pp. 13-14.

116. Vlach M. Branch-and-bound method for the three-index assignment problem / M. Vlach // Ekonomicko-Matematicky Obzor, 1967. - Vol. 3. - pp. 181-191.

117. Zeleny M. Linear Multiobjective Programming / M. Zeleny. - Springer, Berlin, 1974.