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

• Медведев, Сергей Николаевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Медведев, Сергей Николаевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ПОСТАНОВКИ ОБОБЩЁННЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ И ИХ КЛАССИФИКАЦИЯ

1.1 Многоиндексные обобщения задачи о назначениях

1.1.1 Классификация задач о назначениях

1.1.2 Постановки трёхиндексных задач о назначениях

1.1.3 Обзор научных результатов для аксиальной трёхиндексной задачи о назначениях

1.1.4 Обзор научных результатов для планарной трёхиндексной задачи о назначениях

1.2 Обзор задач о назначениях в условиях неопределённости

1.2.1 Типы данных

1.2.2 Переход к вероятностной постановке задачи

1.2.3 Основные понятия для работы с интервальными величинами

1.2.4 Понятие нечёткого числа

1.2.5 Обзор задач оптимизации в условиях неопределённости

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

Выводы по главе 1

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

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

2.2 Многокритериальная трёхиндексная задача о назначениях

2.3 Аксиальная трёхиндексная задача о назначениях

2.4 Планарная трёхиндексная задача о назначениях

Выводы по главе 2

ГЛАВА 3. ОБОБЩЁННЫЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ В УСЛОВИЯХ НЕОПРЕДЕЛЁННОСТИ

3.1 Постановка интервальной задачи о назначениях. Существование оптимального решения

3.2 Нахождение области устойчивости оптимального решения стандартной задачи о назначениях

3.3 Анализ решения интервальной задачи о назначениях

3.4 Нечёткая задача о назначениях с нечёткими коэффициентами

Выводы по главе 3

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

4.1 Описание программного обеспечения

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

4.2.1 Алгоритмы решения аксиальной трёхиндексной задачи о назначениях

4.2.2 Алгоритмы решения планарной трёхиндексной задачи о назначениях

Выводы по главе 4

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

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

ПРИЛОЖЕНИЯ

Приложение А

Приложение Б

Приложение В

Приложение Г

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

ВВЕДЕНИЕ

Актуальность темы исследования и степень разработанности проблемы.

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

Для трёхиндексных и других многоиндексных задач о назначениях, которые являются АТ'-трудными, существует проблема построения алгоритмов для нахождения приближённого (субоптимального) решения. Усовершенствованию алгоритмов посвящено множество работ, в которых прослеживаются несколько основных подходов: постановка и решение ЗОН на графах (Y. Crama, L. Kaufman, Э. X. Гимади, H. М. Коркишко), построение алгоритмов на основе метода ветвей и границ с различными вариантами ветвления и фиксации переменных (Е. Balas, R. Е. Burkard, M. Vlach, Э. X. Гимади, И. П. Вознюк), применение метода лагранжевой «релаксации» (D. Magos, P. Camerini, M. К. Кравцов, С. А. Дичковская), модификация известных алгоритмов решения двухиндексных задач (L. Kaufman, С. И. Сергеев). Практически не проводятся исследования, связанные с построением быстрых «жадных» алгоритмов и повышением их эффективности. Известные методы такого типа (R. M. Aiex, Л. Г. Раскин, И. О. Кириченко) дают слишком «грубое» решение. Существует необходимость в их улучшении для работы с задачами больших размерностей, возникающими на практике, что возможно осуществить за счёт построения итеративного алгоритма, учитывающего результаты предыдущих шагов.

Обобщённые ЗОН с интервальными и нечёткими данными возникают в результате формализации неопределённости, присущей многим практическим задачам. Для них не существует единого подхода в определении понятия оптимальности решения и условий его существования, поэтому различны и подходы к построению алгоритмов решения (R. Е. Steuer, F. Mraz, В. И. Левин, С. П. Шарый), что является стимулом к дальнейшему исследованию в этой области.

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

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

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

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

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

2. Разработка адаптивных методов для решения аксиальной и планарной трёхиндексных ЗОН.

3. Разработка модели многокритериальной трёхиндексной ЗОН и адаптивных методов ее решения.

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

5. Разработка программного обеспечения для решения трёхиндексных задач о назначениях и задач с неточными данными.

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

Результаты, выносимые на защиту, и их научная новизна:

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

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

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

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

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

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

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

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

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

Предложенные в диссертации подходы к решению различных ЗОН позволяют повысить обоснованность принимаемых решений в сложных системах различного назначения, в том числе, при оптимизации вычислительных и производственных процессов. Практические результаты диссертации в форме программного комплекса используются в деятельности ОГБУ «Агентство по инвестициям и стратегическим проектам» (акт№ 51/1-01-11-542).

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

Публикации. Основные результаты диссертации отражены в 13 опубликованных работах, в том числе, 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит: [60] -математическая модель многокритериальной трёхиндексной задачи о назначениях; [63] - утверждение, обосновывающее сведение полной нечёткой задачи о назначениях к задаче с нечёткими целевыми коэффициентами, алгоритм решения поставленной задачи на основе венгерского метода; [55] - «жадные» алгоритмы решения трёхиндексной задачи о назначениях; [58] - детальная разработка «жадного» и адаптивного алгоритмов, конкретизация и наполнение шагов решения поставленной задачи; [59, 60] - решение задачи по ¡1; [64] -переход от нечёткой к интервальной задаче о назначениях, алгоритм решения поставленной задачи с использованием адаптивного алгоритма; [65] - модуль

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

Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка используемых источников из 169 наименований и приложения; изложена на 147 страницах основного текста и включает 30 рисунков и 15 таблиц.

ГЛАВА 1. ПОСТАНОВКИ ОБОБЩЁННЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ И ИХ КЛАССИФИКАЦИЯ

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

Пусть задано конечное множество X = и конечное множество комбинаций его элементов

^ = {^15 ' ^лг) >

при этом под комбинацией 5 е О понимается упорядоченная или неупорядоченная т-выборка из п элементов множества X. Пусть /(.у) - функция,

заданная на множестве О. Требуется найти элемент /еб, доставляющий экстремум этой функции.

Широко известна проблема поиска экстремума функции /(я) на множестве перестановок. В этом случае

Я/ЕЯ..

где Бп - симметричная группа и N < п\.

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

1.1 Многоиндексные обобщения задачи о назначениях

Задача о назначениях (ЗОН) имеет множество разновидностей и модификаций, таких как стандартная (или классическая) задача о назначениях [13, 25], её многоиндексные аналоги [130, 148, 165], квадратичные и биквадратичные

и

постановки [106], обобщения задачи, связанные с использованием неполной и неточной исходной информации [69] и т.д.

Математическая модель стандартной ЗОН имеет вид

ЦХ) = ££с,Л->1тп (1.1)

,=i j=1

±XlJ=\,j=ü, (1.2) 1=1

5>„=i, *=!Я (1.3)

7=1

хц = {ОД}, ij = u (1.4)

Ограничения (1.1)-(1.4) задают множество допустимых решений Q. 1.1.1 Классификация задач о назначениях

Различные модификации ЗОН можно классифицировать по следующим основным признакам.

1. По виду целевой функции.

1.1. Линейные целевые функции, которые, в свою очередь, подразделяются на классическую (1.1) и минимаксную

L{X) - maxc х —> min.

1.2. Нелинейные целевые функции (квадратичные, кубические, биквадратичные). Квадратичная целевая функция, например, пред ставима в виде [131]

п п п п я п

l{X)=ZEXZaA v«+ ^ min-

,=1 J=l к=1 /=1 (=1 ;=1

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

2. По типу коэффициентов.

Можно выделить следующие обобщения задачи.

2.1. Детерминированная ЗОН, например, (1.1)-(1.4), в которой коэффициенты целевой функции являются числами.

2.2. Интервальная ЗОН, в которой коэффициенты целевой функции известны с точностью до интервалов возможных значений, то есть имеют вид

сц =[су, Су], i, j = l,n. Математическая модель интервальной ЗОН представима в виде

ЦХ) = ^сцхц->тт (1.5)

1=1 7=1

2X=w=Vn, (i.6)

í=I

п __

^хц =1, г' = 1,л, (1.7)

ху={0,1}, í,y = U, (1.8)

где Х(Х) - функция с интервальными коэффициентами су .

2.3. Нечёткая ЗОН, основанная на применении нечётких чисел. Для неё известно несколько постановок [134], например, когда переменные и целевые коэффициенты являются неотрицательными треугольными нечёткими числами

п п ,=1 7=1

(í.io)

i=i

¿jcv=í,í = l^, (1.11)

7=1

и называется полной нечёткой ЗОН. 3. По виду переменных.

3.1. Двухиндексные ЗОН, в которых переменные задаются в виде плоских матриц, например, (1.1)-(1.4).

3.2. Трёхиндексные ЗОН, в которых переменные задаются в виде кубических матриц (куба). Наиболее известными являются аксиальная (1.13)-(1.17)

п п п

l=i j=i k=i

±±xl=l = (1.14)

y=l *=1

¿1X=1J = M, (1.15)

1=1 k=1

22X=1,* = 1,H, (1.16)

<=1 7=1

*J={0,1}, /,у, £ = 1Я (1.17)

и планарная (1.18)-(1.22) задачи

п п п

1=1 7=1 к=1

5X=i, ¿*=1Я (1.19)

i=i

¿<=1, = (1-20)

7=1

¿^=1, i,j = l,n, (1.21)

*=1

<={0,1}, i,j,k = ü. (1.22)

3.3. Многоиндексные ЗОН, различные постановки которых представлены в [148, 150, 153-155]. 4. По типу переменных.

4.1. Вероятностная постановка задачи, в которой переменные являются случайными величинами {X}: X е Q с реализациями из множества П

М(ЦХ))-> min .

Данная постановка используется при построении адаптивных алгоритмов (см. главу 2).

4.2. Полная нечёткая ЗОН (1.9)-(1.11), в которой и целевые коэффициенты, и переменные являются нечёткими числами. В главе 3 будет показано, что такая задача не имеет смысла и сводится к задаче только с нечёткими целевыми коэффициентами.

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

1.1.2 Постановки трёхиндексных задач о назначениях

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

Хорошо изученной является двухиндексная задача о назначениях [25]: построены эффективные алгоритмы для нахождения её точного решения [68, 25], а также известны многие свойства, касающиеся существования целочисленного оптимального решения релаксации задачи [112], математического ожидания оптимального значения целевой функции на случайных входах [127], и других аспектов.

Естественным обобщением этой задачи является многоиндексная задача о назначениях, впервые предложенная в 1968 году [148] Пиеррискалой. В течение долгого времени рассматривались только трёхиндесные ЗОН, однако в последние годы начались исследования задач более чем с 3 индексами, главным образом, в контексте многоцелевого слежения [150, 153-155] и проблем зависимости данных [12, 19, 29, 33, 123, 149, 151, 152, 167].

Для задач с тремя индексами существуют две основные модели: аксиальная (или осевая) трёхиндексная задача о назначениях

1=1 ]=\ к=1 п п _

7=1 ¿=1 п п _

1=1 к=1

п п _

,=1 7=1

л:* ={0,1}, г,),к = ~п. и планарная (или плоская) трёхиидексная задача о назначениях

1 7=1 к=1 д _

=1, к = 1,п,

1=1

я _

7=1

п _

XX =1, г,у = 1 ,п,

ы 1

< = {0,1}, =

Данные названия были введены Шеллом [165] в 1955 году для транспортных задач.

Трёхиндексная аксиальная задача о назначениях состоит в таком выборе п элементов кубической матрицы (с*), /',/', к = \,п, порядка п (по одному в каждом сечении), чтобы сумма выбранных элементов была минимальна. (Под сечением понимается плоская матрица из п2 элементов при фиксированном значении одного из индексов к).

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

выбрано ровно п элементов и при этом сумма выбранных элементов была минимальна.

1.1.3 Обзор научных результатов для аксиальной трёхиндексной задачи о назначениях

Аксиальная ЗОН во многих отношениях напоминает классическую задачу о назначениях, однако в отличие от неё, является ТУР-трудной [130].

Исследования аксиальной трёхиндексной задачи о назначениях обобщённо представлено на рис. 1.1.

Рисунок 1.1- Исследование аксиальной ЗОН

Опишем подробнее каждый из блоков, представленных на рис. 1.1. 1) Известные методы решения.

Для решения аксиальной трёхиндексной ЗОН Гансом и Кауфманом [126] был предложен прямо-двойственный алгоритм, который является аналогом венгерского метода решения классической ЗОН. На первом этапе на основе скорректированной матрицы строится гиперграф с вершинами ¿, у, к, и тройка (г, у,

к) определяет в нём ребро, если Су = 0. Ставится задача отыскания максимального

паросочетания гиперграфа, которая является ТУР-трудной. Аналогично классическому методу вместо данной задачи можно рассмотреть проблему

отыскания минимального вершинного покрытия гиперграфа. Однако для аксиальной трёхиндексной ЗОН теорема Кёнига [79] не выполняется: минимальное число вершин в минимальном покрытии может быть строго больше, чем мощность любого (максимального) паросочетания. Дальнейшая работа алгоритма [126], основанного на методе ветвей и границ, сводится к поиску соответствующих паросочетания и вершинного покрытия мощности п.

Большинство алгоритмов ветвления (методы ветвей и границ) разбивают задачу на две подзадачи посредством фиксации одной из переменных, и приравнивании её к 0 или 1 соответственно. Таким образом, размерность задачи уменьшается. В [97] рассмотрена стратегия ветвления, при которой в каждом узле фиксируется несколько переменных. Бёркард и Рудольф [107] представили различные схемы метода ветвей и границ для аксиальной задачи. Например, в [98] была рассмотрена стратегия ветвления, основывающаяся на описании многогранника назначений.

Как было сказано выше, получение оптимального результата аксиальной трёхиндексной ЗОН есть задача ./VP-трудная, поэтому было разработано большое количество приближённых методов решения. Первый эвристический алгоритм был предложен в 1967 году [149]. В дальнейших исследованиях предлагались различные варианты изменений точных методов решения задач дискретной оптимизации, применённых к аксиальной ЗОН. В 2005 году был разработан «жадный» алгоритм с перекомпановкой [93], который показал хорошие результаты на основе компьютерных вычислений. Хуанг и Лим [127] предложили гибридный генетический алгоритм решения аксиальной ЗОН. В [119] представлен метод, названный авторами «редукционным». В разное время было разработано несколько эвристических алгоритмов для задач с декомпозицией целевых коэффициентов [102, 111, 116].

2) Частные случаи постановки задачи.

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

[66], то аксиальная трёхиндексная ЗОН полиномиально разрешима и решение {(1, 1, 1), (2, 2, 2), ... , (п, п, п)} является оптимальным [108].

В работе [113] исследуется специальная постановка аксиальной трёхиндексной задачи о назначениях на графах. Полагается, что для рёбер выполняется неравенство треугольника, и строятся две различные модели, в одной из которых минимизируется сумма длин всех сторон треугольника, в другой - сумма двух меньших. Обе задачи являются тУР-трудными, однако для них оказалось возможным построить алгоритмы, которые дают значения не хуже, чем 3/2 и 4/3 от оптимального значения соответственно.

Отдельно выделяют аксиальную задачу о назначениях на одноциклических подстановках, для которой доказано условие разрешимости и разработаны «быстрые» приближённые алгоритмы решения [10-12, 26, 123].

В [110] исследована задача, в которой целевые коэффициенты пред ставимы в виде произведения трёх неотрицательных вещественных чисел. Доказано, что в случае минимизации функции цели задача является М3-трудной, однако при максимизации она разрешается за полиномиальное время. Данное утверждение показывает, что в отличие от классической ЗОН, в задачах на максимум и на минимум есть существенное различие. В [117] предложена постановка, которая обобщает предложенный подход, в ней разложение коэффициентов происходит на два числа.

3) Многогранник ограничений.

Отдельные исследования посвящены так называемому многограннику ограничений аксиальной трёхиндексной ЗОН [20], то есть выпуклой оболочке всех допустимых решений. Эйлер [119] рассматривал роль нечётных циклов для некоторых классов граней этого многогранника. В работе [99] проведены детальные исследования, и доказано, что его размерность равна пг - Зп + 2, а также предложен 0(п4) алгоритм разделения граней. В [100, 125, 156] проведено дальнейшее их изучение. Результатом стала работа [157], содержащая в себе подробный обзор структуры многогранника, описание классов граней, и 0(п3)

алгоритм разделения для них. С использованием рассмотренного аппарата разработан «многогранный» алгоритм решения трёхиндексной аксиальной ЗОН [125].

Другой подход к изучению многогранника ограничений предложен в работах [20, 28, 30, 32, 34, 35], в которых исследовались различные классы вершин. Причём, стоит заметить, что авторы рассматривают как трёх-, так и многоиндексные аксиальные ЗОН.

1.1.4 Обзор научных результатов для планарной трёхиндексной задачи о назначениях

Планарная трёхиндексная задача о назначениях не так тщательно изучена как аксиальная, и её гораздо труднее решить. Она также является iVP-трудной [130]. Если представить себе геометрическую интерпретацию задачи в виде куба, то каждая плоскость, полученная фиксацией одного из индексов i, j, к, должна являться допустимым назначением в классической ЗОН. Ввиду такого представления допустимые решения планарной задачи тесно связаны с понятием латинского квадрата [73, 82, 118]. Ив задаче размерности п их количество равно

(л')2"

количеству латинских квадратов того же порядка (более -——), а, следовательно,

п"

возрастает очень быстро [101, 140].

Направления исследования планарной трёхиндексной задачи о назначениях представлены на рис. 1.2.

1) Известные методы решения.

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

Рисунок 1.2 - Исследование планарной ЗОН Другая процедура ветвления была рассмотрена в работе [138], в которой также были приведены вычислительные результаты. Считается, что это единственная статья, сообщающая о вычислительном опыте с алгоритмом, решающим планарную задачу точно. Авторы используют так называемый метод «релаксации», ослабляя одну из групп ограничений для получения верхней оценки. Далее производится процедура, основывающаяся на связи задачи с латинским квадратом, в котором ячейки, выбранные по определённому правилу, меняются таким образом, чтобы получить улучшенное решение.

Позднее в работе [139] был предложен алгоритм поиска с запретами, основанный на работе со структурой окрестности латинского квадрата. Движение в окрестности латинского квадрата полностью определяется изменением значения одной его ячейки. Оно влечёт за собой соответственные изменения в других ячейках, в количестве от 3 до 2л-1. Размерность окрестности, соответственно,

п(п-1) п\п-1) ^

заключена в пределах от- до —---. Структура окрестности имеет два

2 4

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

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

Другой вариант метода «релаксации», с применением функции Лагранжа, описывается в работе [112]. Было показано [138], что такой алгоритм решает задачи размерности п = 9 менее чем за 4 минуты процессорного времени.

Кравцов М. К. и Крачковский А. П. [31] предприняли попытку разработки полиномиального асимптотически точного алгоритма решения планарной ЗОН. Однако Гимади Э. X., Филатов М. Ю., Вознюк И. П., показали, что приведённые в статье обоснования основаны на ошибочном утверждении [7]. Так же Гимади Э. X. и Глазков Ю. В. исследовали модификацию планарной трёхиндексной ЗОН -т-планарную трёхиндексную ЗОН, в которой матрица затрат имеет размерность п х п х т, и предложили полиномиальный алгоритм её решения, который асимптотически оптимален, если т есть 0(1пя), и целевые коэффициенты являются независимыми одинаково распределенными случайными величинами [9]. В дальнейшем была доказана асимптотическая оптимальность этого алгоритма для специальных типов случайных величин [167]. В работах [16, 17] приведены результаты обширной серии вычислительных экспериментов по исследованию четырех полиномиальных алгоритмов нахождения асимптотически оптимального решения планарной трёхиндексной ЗОН.

Список литературы диссертационного исследования кандидат наук Медведев, Сергей Николаевич, 2013 год

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

1. Авдийский В. И. Неопределённость, изменчивость и противоречивость в задачах анализа рисков поведения экономических систем / В. И. Авдийский, В. М. Безденежных // Эффективное антикризисное управление, 2011. -№ 3. - С. 46-61.

2. Азарнова Т. В. Методы оптимизации: Учеб. Пособие / Т. В. Азарнова, И. Л. Каширина, Г. Д. Чернышова. - Воронеж: Изд-во ВГУ, 2003. - 86с.

3. Алефельд Г. Введение в интервальные вычисления / Г. Алефельд, Ю. Херцбергер. - М: Мир, 1987. - 360 с.

4. Аттетков А. В. Методы оптимизации / А. В. Аттетков, С. В. Галкин, В. С. Зарубин. - М.: Изд-во МГТУ им. Баумана, 2001. - 480 с.

5. Ватолин А. А. О задачах линейного программирования с интервальными коэффициентами // Журнал вычислительной математики и математической физики, 1984.-Т. 24.-№ 11.-С. 1629-1637.

6. Вентцель Е. С. Теория вероятностей: Учеб. для вузов. - 6-е изд. стер. - М.: Высш. шк., 1999. - 576 с.

7. Вознюк И. П. Асимптотически точный алгоритм для решения задачи размещения с ограниченными объёмами производства / И. П. Вознюк, Э. X. Гимади, М. Ю. Филатов // Дискретный анализ и исследование операций. Серия 2, 2001. - Вып. 8. - № 2. - С. 3-16.

8. Вощинин А. П. Оптимизация в условиях неопределенности / А. П. Вощинин, Г. Р. Сотиров. - М. : Изд-во Моск. энергет. ин-та, 1989. - 224 с.

9. Гимади Э. X. Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях / Э. X. Гимади, Ю. В. Глазков // Дискретный анализ и исследование операций. Серия 2, 2006. - Вып. 13. -№ 1. - С. 10-26.

10. Гимади Э. X. Об одном алгоритме решения трёхиндексной аксиальной задачи о назначениях на одноциклических подстановках / Гимади Э. X.,

Коркишко Н. М. // Дискретный анализ и исследование операций, Серия 1, 2003. - Вып. 10. - № 2. - С. 56-65.

11. Гимади Э. X. Аксиальные трёхиндексные задачи о назначениях и коммивояжёра: быстрые приближённые алгоритмы и их вероятностный анализ / Э. X. Гимади, А. И. Сердюков // Изв. Вузов. Математика, 1999. -№12.-С. 19-25.

12. Гимади Э. X. О разрешимости многоиндексной аксиальной задачи о назначениях на одноциклических подстановках / Э. X. Гимади, Н. М. Кайран, А. И. Сердюков // Изв. Вузов. Математика, 2000. - №12. - С. 21-26.

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

14. Гребенник И. В. Ранжирование альтернативных решений на основе интервальной информации о важности их характеристик / И. В. Гребенник, К. Э. Петров, Л. В. Колесник // Вестник Херсонского государственного технического университета, 2005. - № 1(21). - С.42-47.

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

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

17. Дичковская С. А. Исследование полиномиальных алгоритмов решения трёхиндексной планарной проблемы выбора / С. А. Дичковская, М. К. Кравцов // Журнал вычислительной математики и математической физики, 2006. - Вып. 46. - № 2. - С. 222-228.

18. Добронец Б. С. Интервальная математика. - Красноярск: Краснояр. гос. ун~ т., 2004.-216 с.

19. Емеличев В. А. Многогранники, графы, оптимизация / В. А. Емеличев, М. М. Ковалев, М. М. Кравцов. - М: Наука, 1981. - 346 с.

20. Емеличев В. А. О многогранниках многоиндексной транспортной задачи / В. А. Емеличев, А. М. Кононенко. - ДАН БССР, 1972. - Вып. 16. - №6. - С. 45-49.

21. Захаров А. В. Синтез систем управления при интервальной неопределённости параметров их математических моделей / А. В. Захаров, Ю. И. Шокин // Доклады Академии Наук, 1988. - Том 299. - №2. - С. 292295.

22. Иванов В. В. О трехиндексной задаче назначения / В. В. Иванов // Экономика и математические методы, 1974. - Вып. 10. - № 2. - С. 336-339.

23. Каплинский А. И. Построение рандомизированных алгоритмов оптимизации // Проблемы случайного поиска, 1980. - Вып. 8. - С. 63-91.

24. Колесник Л. В. Метод ращонального щдбору та розстановки кадр1в // Проблеми шформацшних технологи, 2009. - №1. - С. 42-47.

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

26. Коркишко Н. М. Трёхиндексная аксиальная задача о назначениях на одноциклических подстановках на максимум / Н. М. Коркишко // Новосибирск, 2003. - (Препринт. / Рос. акад. наук. Сиб. отд-ние. Ин-т математики им. С. Л. Соболева; Сер. 113). - С. 62-67.

27. Кофман А. Введение в теорию нечетких множеств [пер. с франц.] - М.: Радио и связь, 1982. - 432 с.

28. Кравцов В. М. Оценки снизу числа нецелочисленных вершин многогранника трёхиндексной аксиальной задачи о назначениях / В. М. Кравцов // Вестн. Белорус, гос. ун-та. Сер 1, 2002. - №3. - С. 87-90.

29. Кравцов В. М. Характеризация типов максимально нецелочисленных вершин релаксационного многогранника четырёхиндексной аксиальной задачи о назначениях / В. М. Кравцов, М. К. Кравцов // Журнал вычислительной математики и математической физики, 2013. - Вып. 53. -№5.-С. 825.

30. Кравцов М. К. О нецелочисленных вершинах многогранника трёхиндексной аксиальной задачи о назначениях / М. К. Кравцов, В. М. Кравцов, Е. В. Лукшин // Дискрет, мат., 2001. - Вып. 13. - № 2. - С. 120-143.

31. Кравцов М. К. О полиномиальном алгоритме нахождения асимптотически оптимального решения трехиндексной планарной проблемы выбора / М. К. Кравцов, А. П. Крачковский // Ж. вычисл. матем. и матем. физ., 2001. - Вып. 41. -№2. -рр. 342-345.

32. Кравцов М. К. О типах (Зи-2)-нецелочисленных вершин многогранника трёхиндексной аксиальной задачи выбора / М. К. Кравцов, В. М. Кравцов, Е. В. Лукшин // Изв. вузов. Математика, 2002. - №12. - С. 84-90.

33. Кравцов М. К. О типах максимально нецелочисленных вершин релаксационного многогранника четырёхиндексной аксиальной задачи о назначениях / М. К. Кравцов, В. М. Кравцов // Известия высших учебных заведений. Математика, 2012. -№ 3. - С. 9-16.

34. Кравцов М. К. О числе г-нецелочисленных вершин многогранника трёхиндексной аксиальной задачи выбора / М. К. Кравцов, В. М. Кравцов, Е. В. Лукшин // Изв. вузов. Математика, 2000. - №12. - С. 89-92.

35. Кравцов М. К. О числе нецелочисленных вершин многогранника трёхиндексной аксиальной задачи о назначениях / М. К. Кравцов, В. М. Кравцов, Е. В. Лукшин // Весщ HAH Беларуси сер. ф1з.-мат. Навук, 2000. -№4. - С. 56-65.

36. Кудрявцев Л. Д. Математический анализ: Учеб. пособие для вузов. - М.: Высш. шк., 1970. - 704 с.

37. Кузьмин Е. А. Неопределенность в экономике: понятия и положения / Е. А. Кузьмин // Вопросы управления, 2012. - № 2. - С. 80-92.

38. Кузьмин Е. А. Неопределенность и определенность в управлении организационно-экономическими системами / Е. А. Кузьмин. -Екатеринбург : Институт экономики УрО РАН, 2012.- 184 с.

39. Левин В. И. Антагонистические игры с интервальными параметрами // Кибернетика и системный анализ, 1999. - № 3. - С. 149-160.

40. Левин В. И. Булево линейное программирование с интервальными коэффициентами // Автоматика и телемеханика, 1994. - № 7. - С. 17-22.

41. Левин В. И. Дискретная оптимизация в условиях интервальной неопределенности // Автоматика и телемеханика, 1992. - № 7. - С. 97-107.

42. Левин В. И. Интервальное дискретное программирование // Кибернетика и системный анализ, 1994. - № 6. - С. 91-103.

43. Левин В. И. Интервальные методы оптимизации систем в условиях неопределенности. - Пенза: Изд-во Пенз. технол. ин-та, 1999. - С. 45-51.

44. Левин В. И. Интервальный подход к оптимизации в условиях неопределенности // Информационные технологии, 1999. - № 1. - С. 7-12.

45. Левин В. И. Моделирование задач оптимизации в условиях интервальной неопределённости // Известия Пензенского государственного педагогического университета им. В.Г. Белинского, 2011. - № 26. - С. 589595.

46. Левин В. И. Нелинейная оптимизация в условиях интервальной неопределенности // Кибернетика и системный анализ, 1999. - № 2. - С. 138-147.

47. Левин В. И. Оптимизация расписаний в системах с неопределенными временами обработки. I, II // Автоматика и телемеханика, 1995. - №2, 3. -С. 99-110, 106-116.

48. Левин В. И. Решение интервальной задачи квадратичного программирования методом детерминизации / В. И. Левин, Е. А. Немкова // Вестник Тамбовского государственного технического университета, 2012. -Вып. 18. -№ 1.-С. 203-211.

49. Левин В. И. Сравнение интервалов и оптимизация в условиях неопределённости // Вестник Тамбовского университета. Серия: Естественные и технические науки, 2002. - Вып. 7. - № 3. - С. 383-389.

50. Левин В. И. Сравнение интервальных величин // Вестник Тамбовского университета. Серия: Естественные и технические науки, 2000. - Т. 5. - № 1.-С. 99-101.

51. Львович Я. Е. Конструирование адаптивных схем перебора для решения дискретных задач оптимизации / Я. Е. Львович, А. И. Каплинский, Г. Д. Чернышова, О. И. Черных // В сб.: Актуальные проблемы фундаментальных наук. - М.: Изд-во МГТУ, 1991. - С. 44-46.

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

53. Медведев С. Н. Адаптивные алгоритмы решения трёхиндексных задач о назначениях / С. Н. Медведев // Современные методы прикладной математики, теории управления и компьютерных технологий: сб. трудов VI Междунар. конф., Воронеж, 10-16 сентября 2013г. - Воронеж : Воронеж, гос. ун-т., 2013.-С. 153-156.

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

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

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

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

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

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

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

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

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

62. Медведев С. И. Нахождение области устойчивости интервальной задачи о назначениях / С. Н. Медведев // Вестник Воронеж, гос. тех. ун-та. -Воронеж : Воронеж, гос. тех. ун-т., 2011. - Том 7, № 10. - С. 51-54.

63. Медведев С. Н. О нечёткой задаче о назначениях / С. Н. Медведев, Т. М. Леденёва // Вестник Белгородского государственного технического университета им. В. Г. Шухова. - Белгород: БГТУ, 2012. - С. 154-157.

64. Медведев С. Н. Применение адаптивного алгоритма для решения нечёткой задачи о назначениях / О. А. Медведева, С. Н. Медведев // Аналитические и численные методы моделирования естественнонаучных и социальных

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

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

66. Монж Г. Приложение анализа к геометрии / Г. Монж [пер. с франц.] - М., 1936.-708 с.

67. Орловский С. А. Проблемы принятия решений при нечеткой исходной информации. - М.: Радио и связь, 1981. - 286 с.

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

69. Пегат А. Нечеткое моделирование и управление [пер. с англ.] - М.: БИНОМ. Лаборатория знаний, 2009. - 798 с.

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

71. Ротштейн А. П. Влияние методов деффазификации на скорость настройки нечеткой модели / А. П. Ротштейн, С. Д. Штовба // Кибернетика и системный анализ, 2002. - №1. - С. 169-176.

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

73. Сачков В. Н. Комбинаторные методы дискретной математики. - М., 1977. -320 с.

74. Сергеев С. И. Новые нижние границы для трипланарной задачи назначения. Использование классической модели / С. И. Сергеев // Автомат, и телемех., 2008.-№ 12.-С. 53-75.

75. Сергеев С. И. Трипланарная задача назначения и задача разделения. Новые нижние границы / С. И. Сергеев // Автомат, и телемех., 2006. - № 2. - С. 8089.

76. Тимохин С. Г. О задачах линейного программирования в условиях неточных данных / С. Г. Тимохин, А. В. Шапкин // Экономика и математические методы, 1981. - Вып. 17. - № 5. - С. 955-963.

77. Фидлер М. Задачи линейной оптимизации с неточными данными / М. Фидлер, Й. Недома, Я. Рамик, И. Рон, К. Циммерман. - М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Институт исследований, 2008. -288с.

78. Фишберн П. Теория полезности для принятия решений [пер. с англ.] / П. Фишберн. - М.: Наука, 1978. - 352 с.

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

80. Хлебалин Н. А. Аналитический метод синтеза регуляторов в условиях неопределённости параметров объекта // Аналитические методы синтеза регуляторов. - Саратов: Саратов, политехи, ин-т, 1981. - С. 107-123.

81. Хлебалин Н. А. Синтез интервальных регуляторов в задаче модального управления // Аналитические методы синтеза регуляторов. - Саратов: Саратов, политехи, ин-т, 1988. - С. 26-30.

82. Холл М. Комбинаторика / М. Холл [пер. с англ.]. - М., 1970. - 424 с.

83. Хуцишвили Н. Г. Алгоритм решения трёхиндексной транспортной задачи -Тр. Ин-та. приклад, мат., 1969. - №1. -С. 42-47.

84. Хуцишвили Н. Г. Об одной задаче размещения. - Сообщ. АН ГССР, 1971. -№1. - С. 67-72.

85. Хуцишвили Н. Г. Решение трёхиндексной транспортной задачи методом транспортных сетей / Н. Г. Хуцишвили, Н. М. Шарашенидзе. - Сообщ. АН ГССР, 1968. - Вып. 49. -№1. - С. 32-38.

86. Чернышова Г. Д. Вероятностная модификация «жадных» алгоритмов комбинаторной оптимизации // Высокие технологии в технике и медицине. -Воронеж, 1994. - С. 51-56.

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

88. Шарая И. А. Ограниченно ли допустимое множество решений интервальной линейной системы? // Вычислительные технологии, 2005. - Том 9. - № 3. -С. 108-112.

89. Шарая И. А. Переход к ограниченному допустимому множеству решений // Всероссийское (с международным участием) совещание по интервальному анализу и его приложениям ИНТЕРВАЛ-06, 1-4 июля 2006 г., Петергоф, расшир. тез. докл. - Санкт-Петербург: ВВМ, 2006. - С. 135-139.

90. Шарая И. А. Строение допустимого множества решений интервальной линейной системы // Вычислительные технологии, 2005. - Том 10. - № 5. -С. 103-119.

91. Шарый С. П. Интервальные алгебраические задачи и их численное решение: дис. д-ра физ.-мат. наук : 01.01.07 : защищена 25.08.2000 : утв. 12.01.2001 / Шарый Сергей Петрович. - Новосибирск, 2000. - 266 с.

92. Шарый С. П. Решение интервальной линейной задачи о допусках // Автоматика и телемеханика, 2004. - №10. - С. 147-162.

93. 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.

94. Anuradha D. A New method for finding an optimal solution to solid assignment problems / D. Anuradha, P. Pandian // International Journal of Engineering Research and Applications, 2012. - Vol. 2, Issue 3. - pp. 1614-1618.

95. Appa G. A new class of facets for the Latin square polytope / G. Appa, D. Magos, I. Mourtos // Discr. Appl. Math., 2006. - Vol. 154. - pp. 900-911.

96. Arbib C. A three-dimensional matching model for perishable production scheduling / C. Arbib, D. Pacciarelli, S. Smriglio // Discrete Appl. Math., 1999. -Vol. 92.-pp. 1-15.

97. Balas E. An algorithm for the three-index assignment problem / E. Balas, M. J. Saltzman // Oper. Res., 1991.-Vol. 39.-№ l.-pp. 150-161.

98. Balas E. Facets of the three-index assignment polytope / E. Balas, M. J. Saltzman // Discrete Appl. Math., 1989. - Vol. 23. - №3. - pp. 201-229.

99. Balas E. Facets of the three-index assignment polytope / E. Balas, M. J. Saltzman // Discrete Applied Mathematics, 1989. - Vol. 23. - pp. 201-229.

100. Balas E. Linear-time separation algorithms for the three-index assignment polytope / E. Balas, L. Qi // Discrete Applied Mathematics, 1993. - Vol. 43. - pp. 1-12.

101. Bammel S. E. The number of 9 x 9 Latin squares / S. E. Bammel, J. Rothstein // Discrete Mathematics, 1975. - Vol. 11. - pp. 93-95.

102. Bandelt H. J. Approximation algorithms for multidimensional assignment problems with decomposable cost coefficients / H. J. Bandelt, Y. Crama, F. C. R. Spieksma // Discr. Appl. Math., 1994. - Vol. 49. - pp. 25-50.

103. Beamont O. Linear tolerance problem and linear programming techniques / O. Beamont, B. Philippe // Reliable Computing. - 2001. - Vol. 7. - № 6. - pp. 433447.

104. Beeck H. Linear programming with inexact data. - Technical report TUM-ISU-7830, Technical university of Munich, Munich, 1978.

105. Billard L. Symbolic data analysis: conceptual statistics and data mining / L. Billard, E. Diday. - Wiley, Chichester, 2006. - 321 p.

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

107. Burkard R. E. Computational investigations on 3-dimensional axial assignment problems / R. E. Burkard, R. Rudolf // Belgian J. of Operations Research, 1993. -Vol. 32.-pp. 85-98.

108. Burkard R. E. Perspectives of Monge properties in optimization / R. E. Burkard, B. Klinz, R. Rudolf// Discr. Appl. Math., 1996. - Vol. 70. - pp. 95-161.

109. Burkard R. E. Some remarks on 3-dimensional assignment problems / R. E. Burkard, K. Frohlich // Methods of Operations Research, 1980. - Vol. 36. - pp. 31-36.

110. Burkard R. E. Three-dimensional axial assignments problems with decomposable cost coefficients / R. E. Burkard, R. Rudolf, G. J. Woeginger // Discr. Appl. Math., 1996.-Vol. 65.-pp. 123-139.

111. Burkard R. E. Three-dimensional axial assignments problems with decomposable cost coefficients / R. E. Burkard, R. Rudolf, G. J. Woeginger // Discr. Appl. Math., 1996.-Vol. 65.-pp. 123-139.

112. Camerini P. On improving relaxation methods by modified gradient techniques / P. Camerini, L. Fratta, F. Maffioli // Mathematical Programming Study, 1975. -Vol. 3. - pp. 26-34.

113. Crama Y. Approximation algorithms for three-dimensional assignment problems with triangle inequalities / Y. Crama, F.C.R. Spieksma // European J. Oper. Res., 1992. - Vol. 60. - pp. 273-279.

114. De P. K. An Algorithm to Solve Multi-Objective Assignment Problem Using Interactive Fuzzy Goal Programming Approach / P. K. De, Bharti Yadav // Int. J. Contemp. Math. Sciences, 2011. - Vol. 6. -№ 34. - pp. 1651-1662.

115. Dehghan M. Computational methods for solving fully fuzzy linear systems / M. Dehghan, B. Hashemi, M. Ghatee // Applied Mathematics and Computation, 2006. - Tom 179.-№ 1. - C. 328-343.

116. Dell'Amico M. Efficient algorithms and codes for the k-cardinality assignment problem / M. Dell'Amico, A. Lodi, S. Martello // Discr. Appl. Math., 2001. -Vol. 110.-pp. 25-40.

117. Dell'Amico M. Solution of the cumulative assignment problem with a well-structured tabu search method / M. Dell'Amico, A. Lodi, F. Maffioli // J. Heuristics, 1999. - Vol. 5. - pp. 123-143.

118. Denes J. Latin Squares and their Applications / J. Denes, A. D. Keedwell. -Budapest, 1974.-235 p.

119. Euler R. Odd cycles and a class of facets of the axial 3-index assignment polytope / R. Euler // Applicationes mathematicae (Zastowania Matematyki), 1987. - Vol. 19.-pp. 375-386.

120. Euler R. On Latin squares and the facial structure of related polytopes / R. Euler, R. E. Burkard, R. Grammes //Discr. Math., 1986. - Vol. 62. - pp. 155-181.

121. Euler R. Time-tables, polyhedra and the greedy algorithm / R. Euler, H. Le Verge // Discr. Appl. Math., 1996. - Vol. 65. - pp. 207-221.

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

123. Gimadi E. Kh. Multi-index assignment problem: an asymptotically optimal approach / E. Kh. Gimadi, N. M. Kairan // IEEE Symposium on ETFA, 2001. -pp. 707-709.

124. Glazkov Y. On asymptotically optimal algorithm for one modification of planar 3-dimensional assignment problem / Y. Glazkov // Operations Research Proceedings, 2006.-pp. 175-179.

125. Gwan G. On facets of the three-index assignment polytope / G. Gwan, L. Qi // Australasian J. Combinatorics, 1992. - Vol. 6. - pp. 67-87.

126. Hansen P. A primal-dual algorithm for the three-dimensional assignment problem / P. Hansen, L. Kaufman // Cahiers du GERO, 1973. - Vol. 15. -№3. - pp. 327336.

127. 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.

128. Jansson C. A Self-Validating Method for Solving Linear Programming Problems with Interval Input Data / C. Jansson // Computing Supplementum, 1988. - Vol. 6.-pp. 33-45.

129. Jansson C. Rigorous Lower and Upper Bounds in Linear Programming / C. Jansson // SIAM J. Optim., 2004. - Vol. 14. - № 3. - pp. 914-935.

130. Karp R. M. Reducibility among combinatorial problems, in Complexity of Computer Computations / R. M. Karp // Plenum Press, New York, 1972. - pp. 85-103.

131. Konickova J. Optimalizacni ünoly s nepresnymi daty // PhD thesis. - Charles University, Prague, 1996.

132. Konig D. Uber Graphen und ihre Anwendungen / D. Konig // Mathematische Annalen, 1916. - Vol. 77. - pp. 453-465.

133. Krawczyk R. Fehlerabschätzung bei linearer Optimierung / R. Krawczyk // Interval mathematics. - Springer Verlag, Berlin, 1975. - Vol. 29. - pp. 215-222.

134. Kumar A. Method for solving fully fuzzy assignment problems using triangular fuzzy numbers / Amit Kumar, Anila Gupta, Amarpreet Kaur // International Journal of Computer and Information Engineering. - 2009. - № 3. - pp. 231-234.

135. Libura M. Integer programming problems with inexact objective function // Control and Cybernetics, 1980. - Vol. 9. - № 4. - pp. 189-202.

136. Lin C. J. A labelling algorithm for the fuzzy assignment problem / C. J. Lin, U. P. Wen // Fuzzy Sets Syst., 2004. - Vol. 142. - pp. 373-391.

137. Machost B. Numerische Behandlung des Simplexverfahrens mit intervallanalytischen Methoden / B. Machost. - Berichte der GMD 30, GMD, Bonn, 1970.

138. Magos D. An algorithm for the planar three-index assignment problem / D. Magos, P. Miliotis // European Journal of Operational Research, 1994. - Vol. 77. -pp. 141-153.

139. Magos D. Tabu search for the planar three-index assignment problem / D. Magos // Journal of Global Optimization, 1996. - Vol. 8. - pp. 35-48.

140. McKay B. D. On the number of Latin Squares / B. D. McKay, I. M. Wanless // Ann. Combin., 2005. - Vol. 9. - pp. 335-344.

141. Mraz F. Interval linear programming problem. - Albert-Ludwigs-Universitat, Freiburg, 1987.

142. Mraz F. It uloha linearniho programovani s intervalovymi koeficienty. - West Bohemian University, Habilitationsschrift, 1993.

143. Mraz F. On supremum of the solution faction in linear programs with interval coefficients, Research Report, KAM Series 93-236. - Faculty of Mathematics and Physics, Chrles University, Prague, 1993.

144. Mraz F. Solution function of an interval linear programming problem, Report 9003. - The Technical University of Denmark, Lyngby, 1990.

145. Mraz F. The exact lower bound of optimal values in interval LP / F. Mraz // In Scientific Computing and Validated Numerics, Mathematical Research. -Akademie Verlag, Berlin, 1996. - Vol. 90. - pp. 214-220.

146. Nagarajan R. Computing Improved Fuzzy Optimal Hungarian Assignment Problems with Fuzzy Costs under Robust Ranking Techniques / R. Nagarajan, A. Solairaju // International Journal of Computer Applications, 2010. - Vol. 6. - № 4.-pp. 6-13.

147. Neumaier A. Safe bounds in linear and mixed-integer programming / A. Neumaier, O. Shcherbina // Mathematical Programming, Ser. A, 2004. - Vol. 99. -pp. 283-296.

148. Pierskalla W. P. The multidimensional assignment problem / W. P. Pierskalla // Operational Research, 1968.-Vol. 16.-pp. 422-431.

149. Pierskalla W. P. The tri-substitution method for the three-dimensional assignment problem / W. P. Pierskalla // Canadian Operational Research Society J., 1967. -Vol. 5.-pp. 71-81.

150. Poore A. B. A Lagrangian relaxation algorithm for multidimensional assignment problems arising from multitarget tracking / A. B. Poore, N. Rijavec // SIAM J. Optim., 1993. - Vol. 3. - pp. 545-563.

151. Poore A. B. A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems / A. B. Poore, A. J. Robertson // Computational Opt. Appl., 1997. - Vol. 8. - pp. 129-150.

152. Poore A. B. Data association problems posed as multidimensional assignment problems: Problem formulation / A. B. Poore, N. Rijavec, M. Liggins, V. Vannicola // Signal and Data Processing of Small Targets, 1993. - SPIE, Bellingham,WA. - pp. 552-561.

153. Poore A. B. Multidimensional assignment and multitarget tracking / A. B. Poore // In Partitioning Data Sets, 1995. - Vol. 19. - pp. 169-196.

154. Poore A. B. Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking / A. B. Poore // Computational Opt. Appl., 1994. - Vol.3. - pp. 27-57.

155. Poore A. B. Multidimensional assignment problems arising in multitarget and multisensory tracking / A. B. Poore, P. M. Pardalos, L. S. Pitsoulis // Nonlinear Assignment Problems. Algorithms and Applications, 2000. - Kluwer Academic Publishers, Dordrecht, the Netherlands, - pp. 13-38.

156. Qi L. Anew facet class and a polyhedral method for the threeindex assignment problem / L. Qi, E. Balas, G. Gwan // Advances in Optimization and Approximaton, 1994. - Kluwer Academic, Dordrecht, the Netherlands. - pp. 256-274.

157. Qi L. Polyhedral methods for solving three index assignment problems / L. Qi, D. Sun // Nonlinear Assignment Problem: Algorithms and Application, Combinatorial Optimization Series, 2000. - Kluwer Academic Publishers, Dordrecht, The Netherlands. - pp. 91-107.

158. Ramik J. A new algorithm for solving multi-objective fuzzy linear programming problems / J. Ramik, H. Rommelfanger // Foundatuions of Computing and Decision Sciences, 1996. - Vol. 3. - pp. 145-157.

159. Rohn J. Duallity in interval linear programming / In Interval Mathematics. -Academic Press, New York, 1980. - pp. 521-529.

160. Rohn J. Linear programming with inexact data is NP-hard // Zeitschrift fur Angewandte Mathematik und Mechanik, 1998. - Vol. 3. - №78. - pp. 1051-1052.

161. Rohn J. NP-hardness result for some linear and quadratic problems, Technical report 619. - Institute of Computer Science, Academy of science of the Czech Republic, Prague, January, 1995.

162. Rohn J. On sensitivity of the optimal value of a linear program / J. Rohn // Ekonomicko-matematicky obzor, 1989. - Vol. 25. - pp. 105-107.

163. Rohn J. Strong solvability of interval linear programming problems / J. Rohn // Computing, 1981. - Vol. 26. -pp.79-82.

164. Rump S. M. Solving Algebraic Problems with High Accuracy // A New Approach to Scientific Computation. - Academic Press, New York, 1983. - pp. 51-120.

165. Schell E. Distribution of a product by several properties / E. Schell // Proceedings of the Second Symposium in Linear Programming, 1955. - National Bureau of Standards and U.S. Air Force, Washington D.C. - pp. 615-642.

166. Smagina Ye. M. A new approach to the model regulator synthesis for interval plant with scalar input // Reliable Computing, 1997. - Vol. 3. - pp. 401-410.

167. Spieksma F. C. R. Multi index assignment problems: complexity, approximation, applications // Nonlinear assignment problems, algorithms and applications. -Dordrecht: Kluwer Acad. Publ., 2000. - pp. 1-12.

168. Steuer R. E. Algorithms for linear programming problems with interval objective function coefficients // Mathematics of Operations Research, 1981. - Vol. 6. -pp. 222-248.

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