- •Курсовая работа
- •Содержание
- •Введение. Общее описание задачи о ранце. Простейшая математическая модель.
- •Однокритериальная задача. Алгоритм решения
- •Постановка кзр
- •Алгоритм решения кзр методом динамического программирования
- •Алгоритм решения кзр методом ветвей и границ
- •Решение поставленной задачи с помощью метода ветвей и границ
- •Решение поставленной задачи с с помощью метода реккурентных соотношений
- •Решение задач многокритериальной оптимизации
- •Подход к решению многокритериальных задач, использующий схемы компромисса
- •Метод последовательных уступок по значению ведущего критерия (для 2х критериев)
- •Метод главного критерия
- •Принцип гарантированного результата
- •Метод идеальной точки
- •Принцип равенства
- •Принцип справедливой абсолютной уступки
- •Принцип относительной справедливой уступки
- •Подход к решению многокритериальных задач, основанный на концепции эффективной оценки и Парето-оптимального решения
- •Концепция Парета
- •Роль лпр в решении задач многокритериальной оптимизации
- •Многокритериальная многомерная задача о ранце
- •Постановка многокритериальной задачи
- •Заключение
- •Список литературы
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ
КАФЕДРА ‘ПРИКЛАДНАЯ МАТЕМАТИКА’
Курсовая работа
По дисциплине “Теория систем”
на тему “Многокритериальные задачи принятия решений в системах управления на примере задач ранцевого типа”
Выполнила: студентка группы ИТ-2
3 курс, специальность 230401
Эберг Галина Анатольевна
Руководитель:
Коган Дмитрий Израилевич
Оценка курсовой работы__________
М осква 2012
Содержание
Введение …………………………………………………………….....3
Общее описание задачи о ранце; простейшая математическая модель……………………………………………………………….…..3
Однокритериальная задача. Алгоритм решения………………….....5
Постановка КЗР…………………………………………………......…5
Алгоритм решения КЗР методом динамического программирования....................................................................................5
Алгоритм решения КЗР методом ветвей и границ…………………..7
Решение поставленной задачи с помощью метода ветвей и границ………………………………………………………………...…9
Решение поставленной задачи с помощью метода реккурентных соотношений…………………………………………………..….……11
Решение задач многокритериальной оптимизации…………...……12
Подход к решению многокритериальных задач, использующий схемы компромисса………………………………………………….………..12
Схемы компромисса…………………………………………………..13
Подход к решению многокритериальных задач, основанный на концепции эффективной оценки и Парето-оптимального решения..19
Концепция Парета……………………………………………………...20
Роль ЛПР в решении задач многокритериальной оптимизации….....21
Многокритериальная многомерная задача о ранце ………………….21
Постановка многокритериальной задачи…………………………..…24
Заключение……………………………………………………………...26
Список литературы……………………………………………………..27
Введение. Общее описание задачи о ранце. Простейшая математическая модель.
Задача о ранце – одна из задач оптимизации. Название это получила от максимальной задачи укладки как можно большего возможного числа вещей в рюкзак при условии, что общий объём или вес всех предметов ограничен.
Подобные задачи часто возникают в экономике, прикладной математике. Задача о ранце и различные её модификации широко применяются на практике для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.
В общем виде, задачу можно записать как: из множества предметов со свойствами «стоимость» и «вес», требуется отобрать некоторое число предметов так, чтобы получить максимальную общую стоимость при одновременном соблюдении ограничения на общий вес.
Эта задача широко используется на практике :
- загрузка транспорта - перевозка лифтом максимального количества людей - задача об оформлении подписки - оптимальное заполнение вагонов
- производственная задача с заявками на производство определенного вида продукции с показателями трудоемкости и стоимости
-задача загрузки уникального оборудования
-задача формирования инвестиционного портфеля
-задача изготовления комплекта деталей в системе двух параллельных станков
Нахождение оптимальной загрузки транспорта помогает сокращать расходы, получать большую прибыль.
Существует несколько модификаций задачи ранцевого типа:
Задача о ранце с условием дробимости для части предметов (ЗРДП)
Задача о нескольких ранцах
Задача о ранце с ограниченным количеством предметов каждого наименования
Многомерная задача о ранце
Возьмем в качестве примера систему управления по загрузке грузовых кораблей товаром в порту. Надо определить оптимальную загрузку корабля, с учетом веса груза, его стоимости и максимальной вместимости корабля.
Это возможно сделать в рамках модели однокритериальной задачи оптимизации. А именно – мы можем найти решение, используя классическую задачу о ранце.