 |
Алгоритм решения КЗР методом динамического программирования
|
|
|
|
КУРСОВАЯ РАБОТА
По дисциплине “Теория систем”
на тему “ Многокритериальные задачи принятия решений в системах управления на примере задач ранцевого типа ”
Выполнила: студентка группы ИТ-2
3 курс, специальность 230401
Эберг Галина Анатольевна
Руководитель:
Коган Дмитрий Израилевич
Оценка курсовой работы__________
Москва 2012
Содержание
· Введение …………………………………………………………….....3
· Общее описание задачи о ранце; простейшая математическая модель……………………………………………………………….…..3
· Однокритериальная задача. Алгоритм решения………………….....5
· Постановка КЗР…………………………………………………......…5
· Алгоритм решения КЗР методом динамического программирования....................................................................................5
· Алгоритм решения КЗР методом ветвей и границ…………………..7
· Решение поставленной задачи с помощью метода ветвей и границ………………………………………………………………...…9
· Решение поставленной задачи с помощью метода реккурентных соотношений…………………………………………………..….……11
· Решение задач многокритериальной оптимизации…………...……12
· Подход к решению многокритериальных задач, использующий схемы компромисса………………………………………………….………..12
· Схемы компромисса…………………………………………………..13
· Подход к решению многокритериальных задач, основанный на концепции эффективной оценки и Парето-оптимального решения..19
· Концепция Парета……………………………………………………...20
· Роль ЛПР в решении задач многокритериальной оптимизации….....21
· Многокритериальная многомерная задача о ранце ………………….21
· Постановка многокритериальной задачи…………………………..…24
· Заключение……………………………………………………………...26
|
|
|
· Список литературы……………………………………………………..27
Введение.
Общее описание задачи о ранце. Простейшая математическая модель.
Задача о ранце – одна из задач оптимизации. Название это получила от максимальной задачи укладки как можно большего возможного числа вещей в рюкзак при условии, что общий объём или вес всех предметов ограничен.
Подобные задачи часто возникают в экономике, прикладной математике. Задача о ранце и различные её модификации широко применяются на практике для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.
В общем виде, задачу можно записать как: из множества предметов со свойствами «стоимость» и «вес», требуется отобрать некоторое число предметов так, чтобы получить максимальную общую стоимость при одновременном соблюдении ограничения на общий вес.
Эта задача широко используется на практике:
- загрузка транспорта
- перевозка лифтом максимального количества людей
- задача об оформлении подписки
- оптимальное заполнение вагонов
- производственная задача с заявками на производство определенного вида продукции с показателями трудоемкости и стоимости
-задача загрузки уникального оборудования
-задача формирования инвестиционного портфеля
-задача изготовления комплекта деталей в системе двух параллельных станков
Нахождение оптимальной загрузки транспорта помогает сокращать расходы, получать большую прибыль.
Существует несколько модификаций задачи ранцевого типа:
1. Задача о ранце с условием дробимости для части предметов (ЗРДП)
2. Задача о нескольких ранцах
3. Задача о ранце с ограниченным количеством предметов каждого наименования
4. Многомерная задача о ранце
Возьмем в качестве примера систему управления по загрузке грузовых кораблей товаром в порту. Надо определить оптимальную загрузку корабля, с учетом веса груза, его стоимости и максимальной вместимости корабля.
|
|
|
Это возможно сделать в рамках модели однокритериальной задачи оптимизации. А именно – мы можем найти решение, используя классическую задачу о ранце.
Однокритериальная задача. Алгоритм решения
Нам известны два метода решения задач о ранце - принцип динамического программирования (реккурентные соотношения) и метод ветвей и границ.
Постановка КЗР
Считается, что у анс имеется ранец с максимальной грузоподъемностью W и предметы П1, П2,…., Пn каждому предмету соответствует неотрицательная характеристика ci (стоимость) vi(вес), i= 
. Каждый предмет можно положить в ранец только целиком. Требуется отобрать из неограниченного множества предметов со свойствами «стоимость» и «вес», некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
(1)
(2)
, 
(3)
(1)-(3) - математическая запись КЗР относится к числу задач булева линейного программирования
Алгоритм решения КЗР методом динамического программирования
Записываемую задачу (1)-(3) условно обозначим задачей Z. По ее начальным данным введем в рассмотрение целый ряд частных задач Z(k,p) – считается, что имеются только первые к предметов, а р – разрешенный вес ранца.
К=1,2,…,n; P=1,2,…,n. Тогда задача Z(k,p) приобретает вид (4)-(6):
(4)
(5)
, 
(6)
Введем В(к,р) - оптимальное значение критерия в частной задаче Z(k,p). Через В обозначим оптимальное значение критерия в задаче Z.
Z=Z(n,w) –> В=В(n,w) в ранец можно класть все предметы и вес ранца равен W, что есть исходная задача Z.
| К \ Р | p1 | ……… | pW |
| k1 | В(k1,p1) | ……... | В(k1,pw) |
| ……. | …….. | …..…. | ….…. |
| kn | В(kn,p1) | ….….. | В(kn,pw) |
С1, если V1≤P
В(1,р)=
0, если V1>P
Запишем общее реккурентное соотношение, которое позволит заполнить по заполненной кой строке (к+1)ю строку.
B(k,p), если Vk+1>P
B(k +1,p)=
Max(B(k,p), Сk+1+B(k,p-Vk+1))
С помощью этих соотношений можно решить любую классическую задачу о ранце
Плюсы этого алгоритма:
· Получаем точное решение.
· Имеем оптимальные загрузки рюкзака для всех его весов от 1 до MaxW
|
|
|
