Обобщённые модели задачи о назначениях и адаптивные алгоритмы их решения

• Автор: Медведев, Сергей Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Воронеж
• Количество страниц: 172 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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

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

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

1Л .2 Постановки трёхиндексных задач о назначениях

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

назначениях

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

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

1.2.1 Типы данных
1.2.2 Переход к вероятностной постановке задачи
1.2.3 Основные понятия для работы с интервальными величинами
1.2.4 Понятие нечёткого числа
1.2.5 Обзор задач оптимизации в условиях неопределённости
1.3 Цель и задачи исследования
Выводы по главе
ГЛАВА 2. АДАПТИВНЫЕ АЛГОРИТМЫ РЕШЕНИЯ ТРЁХИНДЕКСНЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ
2.1 Построение адаптивного алгоритма решения для стандартной задачи о назначениях
2.2 Многокритериальная трёхиндексная задача о назначениях
2.3 Аксиальная трёхиндексная задача о назначениях
2.4 Планарная трёхиндексная задача о назначениях
Выводы по главе
ГЛАВА 3. ОБОБЩЁННЫЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ В УСЛОВИЯХ
НЕОПРЕДЕЛЁННОСТИ
ЗЛ Постановка интервальной задачи о назначениях. Существование оптимального решения
3.2 Нахождение области устойчивости оптимального решения стандартной задачи о назначениях
3.3 Анализ решения интервальной задачи о назначениях
3.4 Нечёткая задача о назначениях с нечёткими коэффициентами
Выводы по главе
ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РЕШЕНИЯ ПОСТАВЛЕННЫХ ЗАДАЧ. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ
4.1 Описание программного обеспечения
4.2 Вычислительный эксперимент
4.2.1 Алгоритмы решения аксиальной трёхиндексной задачи о назначениях
4.2.2 Алгоритмы решения планарной трёхиндексной задачи о назначениях
Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЯ
Приложение А
Приложение Б
Приложение В
Приложение Г

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

В работах [40-42, 50] предложен подход к оптимизации систем с интервально заданными параметрами, основанный на принципах сравнения интервалов, вытекающих из общих принципов интервальной математики [3] (см. рис. 1.5). В результате оказалось возможным эффективное решение многих задач оптимизации в новой, интервальной постановке [16, 39, 41, 42, 44, 47]. Однако предложенный подход имел ограничение, связанное с невозможностью сравнения интервалов, один из которых накрывает другой.
В [49] обоснован более общий подход к оптимизации систем с интервальными параметрами. В нем, кроме общих принципов интервальной математики, позволяющих переносить любые операции над числами (в частности, операция взятия максимума и минимума) на интервалы, использовано также понятие меры близости двух интервалов (см. рис. 1.5). Это позволило обоснованно сравнивать любые интервалы, находящиеся в произвольных отношениях между собой (в том числе, накрывающие друг друга), и выбирать максимальный и минимальный из них.
Надо заметить, что предложенный метод сравнения интервальных чисел и соответствующий подход к оптимизации систем с интервальными параметрами имеют определенные ограничения, вытекающие из менее полного, чем в [40-42], учета неопределенности значений указанных параметров. Например, если интервалы, определяющие области значений параметров системы, расширяются симметрично относительно их центра, то такое очевидное увеличение неопределенности системы, учитываемое в [40-42], не учитывается в подходе [49].