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

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

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

1.1. Классическая задача о ранце, ее приложения и модификации.

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

1.4. Схемы синтеза полных совокупностей эффективных оценок в ММЗР

1.4.1 Табличный алгоритм.

1.4.2 Графовый алгоритм

1.4.3 Алгоритм последовательной генерации списков

1.5. Вычислительная сложность МЗРТ и алгоритмов их решения

ГЛАВА 2. АДАПТАЦИЯ СТАНДАРТНОЙ СХЕМЫ СИНТЕЗА ЭФФЕКТИВНЫХ ОЦЕНОК ДЛЯ МОДИФИЦИРОВАННЫХ ЗАДАЧ РАНЦЕВОГО ТИПА
2.1. ММЗР с различными типами критериев.
2.1.1. ММЗР с аддитивными и максиминными критериями
2.1.2. Многокритериальные задачи ранцевого типа с аддитивными и диапазонными критериями.
2.1.3. Многокритериальные задачи ранцевого типа с аддитивными и точечными критериями
2.2. ММЗР с групповой струкгурой
2.3. ММЗР с дробимыми и недробимыми предметами.
ГЛАВА 3. АЛГОРИТМЫ СИНТЕЗА ПРЕДСТАВИТЕЛЬНЫХ СОВОКУПНОСТЕЙ ЭФФЕКТИВНЫХ ОЦЕНОК
3.1. Операторы, строящие представительные совокупности. Понятие консервативного оператора
3.2 Алгоритм синтеза совокупностей, удовлетворяющих пороговым ограничениям
3.3. Адаптация технологии синтеза эффекгивных оценок для применения типовых схем компромисса при решений ММЗР
3.3.1. Синтез эффекгивных оценок, получаемых сверткой векгорного критерия при варьируемых весовых коэффициентах
3.3.2. Синтез подмножеств эффективных оценок, соответствующих последовательным уступкам по значению ведущего критерия.
3.3.3. Построение представительных совокупностей эффективных оценок при выделенном главном кригерии
3.3.4. Синтез подмножеств эффективных оценок, ближайших к варьируемой идеальной точке
ГЛАВА 4. СХЕМЫ УСКОРЕННОГО СЧЕТА И ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ В ПРОЦЕССАХ РЕШЕНИЯ МЗРТ.
4.1. Метод комбинированной разметки при решении ММЗР.
4.2. Метод декомпозиции в процессе синтеза совокупностей эффективных оценок в ММЗР .
4.3. Применение эвристических алгоритмов в ходе реализации типовых схем компромисса при решении МЗРТ.
4.3.1. Жадные алгоритмы.
4.3.2. Процедуры округления в процессах решения МЗРТ
4.3.3. Эвристические процедуры, связанные с понятием ядра.
4.4. Эвристические процедуры решения ММЗР
4.4.1. Эвристические алгоритмы, приближающие полную совокупность эффективных оценок
4.4.1.1. Двухэтапный эвристический алгоритм.
4.4.1.2. Эвристический алгоритм, основанный на укрупнении предметов
4.4.1.3. Декомпозиционнопороговый эвристический алгоритм.
4.4.2. Эвристический алгоритм, приближающий фрагмент полной совокупности эффективных оценок
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Предложен комбинированный подход к решению МЗРТ, предусматривающий синтез совокупностей эффективных оценок, удовлетворяющих условиям заданных схем компромисса при варьируемых параметрах этих схем. При этом рассматриваются пять схем компромисса с варьируемыми параметрами линейная свертка критериев, метод последовательных уступок, метод главного критерия, принцип гарантированного результата, метод идеальной точки. В рамках предложенного подхода появляется возможность адекватно учесть имеющуюся у ЛПР дополнительную информацию о специфике предметной области, требованиях или предпочтениях заказчика и т. МЗРТ, и, следовательно, повысить размерность задач, которые могут решаться в реально приемлемом времени. К таким приемам относится, в частности декомпозиционк ный подход. Раздел 4. ММЗР. Приводятся несколько новых эвристических алгоритмов, позволяющих, как показывают вычислительные эксперименты, получать достаточно качественные решения ММЗР большой размерности за практически приемлемое время. В приложении описана разработанная диалоговая программная система, в которой реализованы изложенные в основном тексте алгоритмы решения многокритериальных задач ранцевого типа. Приводятся результаты вычислительных экспериментов по решению с помощью данной программной системы сгенерированных классов тестовых задач. Апробация результатов. Результаты диссертации докладывались и обсуждались на VII Нижегородской сессии молодых ученых Саров, г. XIV Международной школесеминаре Синтез и сложность управляющих систем Н. Новгород, г. Нижегородском семинаре по дискретной математике г. ВМК ННГУ. Публикации. Основные результаты, полученные в ходе выполнения диссертационной работы, опубликованы в , , . ГЛАВА 1. В разделах 1. В разделе 1. В разделе 1. Раздел 1. Большая часть главы 1 носит обзорный характер, однако в ней содержатся и самостоятельные результаты впервые введенные диапазонные и точечные критерии, алгоритм последовательной генерации списков для многокритериальных задач, результаты по вычислительной сложности задач и алгоритмов. Классическая задача о ранце КЗР одна из типовых, имеющих важное теоретическое и прикладное значение задач дискретной оптимизации. Начиная с работы эта задача является предметом активных исследований. Своим названием задача 1. Имеется совокупность, состоящая из п предметов П,. Ь . В 1. П , взаимно однозначно соответствует булева переменная ху, принимающая значение 1, если предмет П кладется в ранец и 0 в противном случае. Большое внимание к КЗР обусловлено тем, что в рамках этой модели описываются многие реальные прикладные задачи, особенно связанные с планированием и управлением производственными и фанспортными процессами, а также распределением денежных средств. Приведем следующие сводящиеся к КЗР задачи. Требуется набрать производственную программу таким образом, чтобы в пределах заданного фонда рабочего времени получить максимальный доход от выполнения заказов. Легко видеть, что стандартная КЗР 1. Ь заданный фонд рабочего времени, критерий 1. В прикладных интерпретациях КЗР неравенсгво 1. Заметим, что для сведения общей задачи объемного планирования к КЗР пришлось допустить некоторые упрощения например, не учитывать разделение общего фонда рабочего времени по группам используемого оборудования. В то же время приводимая далее задача загрузки уникального оборудования укладывается в модель 1. Имеется совокупность заказов для выполнения которых требуется задействовать уникальное оборудование имеющийся на предприятии в единичном экземпляре сложный и дорогостоящий станок 5 с длительным циклом выполнения каждого заказа. Время выполнения заказа на станке 5 а. Имеется инвестор, располагающий денежной суммой Ь, которую он готов вложить в некоторые из предлагаемых ему п проектов. Для уго проекта известна сумма а, которую требуется вложить и минимальная гарантируемая инвестору величина дохода су от реализации данного проекта эти цифры должны быть указаны разработчиком проекта в бизнесплане, который предоставляется на рассмофение инвестору.