Многокритериальные задачи ранцевого типа : разработка и сравнительный анализ алгоритмов

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

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

1.1. Классическая задача о ранце и алгоритмы поиска точного решения.

1.2. Многомерная задача о ранце.

1.3. Алгоритмы синтеза Наретооптимальных решений для многокритериальной задачи о ранце на основе принципа динамического программирования
1.4. Синтез полной совокупности эффективных оценок многокритериальной задачи о ранце методом ветвей и границ.
ГЛАВА 2. СИНТЕЗ ПРЕДСТАВИТЕЛЬНЫХ СОВОКУПНОСТЕЙ ЭФФЕКТИВНЫХ ОЦЕНОК ДЛЯ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ О РАНЦЕ .
2.1. Концепция оператора, сгроящего представительную совокупность. Понятие консервативного оператора
2.2. Алгоритм синтеза совокупностей эффективных оценок, удовлетворяющих пороговым ограничениям

2.3. Синтез разреженных совокупностей эффективных оценок

2.4. Алгоритмы построения совокупностей эффективных оценок получаемых применениями типовых схем компромисса при варьируемых параметрах этих схем
2.4.1. Метод последовательных уступок.
2.4.2. Линейная свертка критериев.
2.4.3. Метод главного критерия
2.4.4. Метод идеальной точки
2.5. Результаты вычислительных экспериментов
ГЛАВА 3. ПОДХОДЫ К УСКОРЕНИЮ СЧЕТА ПРИ ПОИСКЕ РЕШЕНИЙ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ О РАНЦЕ.
3.1. эффективные оценки. Синтез совокупностей эффективных оценок методом ветвей и границ
3.2. Применение эволюционногенетических алгоритмов для получения эвристических решений
3.3. Комбинированные алгоритмы решения задач о ранце
3.4. Некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов
ГЛАВА 4. НЕКОТОРЫЕ МОДИФИКАЦИИ ЗАДАЧИ О РАНЦЕ И МЕТОДЫ ИХ РЕШЕНИЯ
4.1. Задача о ранце с аддитивным и точечным критериями
4.1.1. Математическая постановка задачи и алгоритмы ее точного решения
4.1.2. Эволюционногенетический алгоритм решения задачи.
4.2. Задачи с несколькими ранцами.
4.2.1. Математические постановки задач с несколькими ранцами и алгорит
мы их точного решения.
4.3.2. Эволюционногенетические алгоритмы решения задач
ГЛАВА 5. ОБ ОДНОЙ ЗАДАЧЕ ВЫБОРА ОГРАНИЧЕННОГО ПРЕДСТАВИТЕЛЬНОГО ПОДМНОЖЕСТВА ОБЪЕКТОВ
5.1. Математическая модель задачи и ее интерпретация. Алгоритм поиска точного решения
5.2. Эвристические алгоритмы поиска решения
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Все разделы сопровождаются результатами вычислительных экспериментов. Программноаппаратным средствам и условиям проведения вычислительных экспериментов посвящено приложение к диссертационной работе. Основные результаты, полученные в ходе работы над диссертацией, изложены в одиннадцати публикациях , , , 4, в том числе восемь из них в центральной печати , , , четыре в материалах и тезисах докладов на международных , , 4 и российских конференциях . ГЛАВА 1. КЛАССИЧЕСКАЯ ЗАДАЧА О РАНЦЕ В ОДНОКРИТЕРИАЛЬНОЙ И МНОГОКРИТЕРИАЛЬНОЙ ПОСТАНОВКАХ. АЛГОРИТМЫ РЕШЕНИЯ. Первая глава посвящена классической задаче о ранце, ее многомерной и многокритериальной модификациям. Детально исследуются алгоритмы поиска точного решения и вопросы вычислительной сложности их реализации. В разделе 1. В разделе 1. В разделе 1. В разделе 1. Вопросы вычислительной сложности рассматриваются по мере описания алгоритмов. Математическая постановка классической задачи о ранце , 0 следующая
тах 1. ХЬ 1. Для задачи 1. Имеется совокупность предметов Г1,. У у 1,н. Предметы считаются недробимыми, т. Необходимо максимизировать суммарную стоимость помещенных в ранец предметов, при условии, что суммарный вес предметов в ранце не может превосходить значение заданной константы Ь. В решении, определяемом вектором X ,х2,. П кладется в ранец тогда и только тогда, когда X1. Считается, что суммарный вес всех предметов
не превосходит величину Ъ, т. Ь. Задачу 1. Существует два стандартных подхода к решению классической задачи о ранце принцип динамического программирования 5, , , и схема ветвей и границ , , 6, 1. В основу метода динамического программирования положен принцип оптимальности, сформулированный Р. Беллманом . Этот принцип устанавливает, что часть оптимальной траектории от любого ее состояния д до конца траектории, сама является оптимальной траекторией с началом в состоянии д. Практически метод динамического программирования как правило реализуется с помощью некоторой системы рекуррентных соотношений. Реализация схемы ветвей и границ заключается в построении дерева вариантов решений, при этом считаются определенными процедуры вычисления верхних и нижних оценок в вершинах дерева, а также процедуры ветвления и отсева бесперспективных направлений. Сначала изложим метод ветвей и границ. Дерево вариантов для задачи 2 это дерево, каждое ребро которого фиксирует значение какойлибо переменной любой путь от начальной вершины корня к конечной вершине дерева листу полностью определяет соответствующее допустимое решение. Конструируя полное дерево вариантов, мы графически изображаем все множество допустимых решений. Реализация метода ветвей и границ сводится к построению некоторого фрагмента дерева вариантов с анализом получаемых в процессе построения вершин чем меньший фрагмент придется построить аля решения задачи 2, тем более эффективным окажется применение метода ветвей и границ. Для каждой вершины V дерева вариантов однозначно определен путь, который ведет из корня в V. Этот путь фиксирует значения ряда переменных, число составляющих его ребер именуется рангом вершины V. Примем для ранга обозначение гУ. Вершине У соответствует частная задача 2У, отличие которой от исходной задачи 2 состоит лишь в том, что значения некоторых переменных уже определены путем из корня в данную вершину. При анализе каждой получаемой вершины У определяем для нее две оценки, верхнюю примем для нее обозначение РУ и нижшою примем для нес обозначение НУ. Верхняя оценка РУ характеризует оптимальное решение в задаче 2У как некоторую надежду. Нижняя оценка порождается определенным допустимым решением задачи 2У. Метод ветвей и границ основывается на трех составляющих способе получения верхней и нижней оценок в вершинах правиле выбора вершины, в которой будет выполняться очередное ветвление способе ветвления. Способ ветвления определяет переменную, различные значения которой фиксируются ребрами, исходящими из вершины. Поскольку переменные задачи 2 булевозначны, то при выполнении ветвления в вершине V из нес проводится два новых ребра, получаем две новые вершины.