Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Недостатки метода ДП




Достоинства метода динамического программирования.

1. На каждом этапе решается задача поиска экстремума лишь по части переменных, следовательно, размерность этих задач по сравнению с исходной значительно ниже. Это позволяет упростить поиск оптимальных значений искомых переменных.

2. Метод ДП дает возможность решать задачи, которые не могут быть решены другими методами.

3. Алгоритм метода ДП легко реализуется на ЭВМ.

1. Отсутствие универсального алгоритма, который был бы пригоден для решения всех задач рассматриваемого класса. Алгоритмы ДП объединены лишь общей идеей, и в каждом конкретном случае должны формироваться применительно к специфике прикладной задачи.

2. При большой размерности исходной задачи эти алгоритмы требуют значительных ресурсов ЭВМ.


Задача о загрузке рюкзака (задача о ранце).

Постановка задачи. Пусть имеются N видов грузов с номерами .

Единица груза j-го вида имеет все aj. Если груз j-го вида берется в количестве xj, то его ценность в общем случае составляет F(xj). Имеется «рюкзак», грузоподъемность которого равна B. Требуется загрузить рюкзак имеющимися грузами таким образом, чтобы вес его был не больше заданного B, а ценность «рюкзака» была максимальной.

Составим Мат. Модель задачи.

Пусть xj – количество груза j-го вида, помещаемого в рюкзак. Тогда можно записать:

(1)

(2)

(3)

Здесь х j могут быть и целыми числами. В общем случае это задача нелинейного программирования с сепарабельной целевой функцией, следовательно, она м.б. решена методом ДП.

Для этого погрузку «рюкзака» можно интерпретировать как N-этапный процесс принятия решений: на 1-м этапе принимается решение о том, сколько нужно взять груза 1-го вида, на 2-ом этапе – сколько груза 2-го вида и т.д. Такая интерпретация наталкивает на возможность применения для решения задачи (1) – (3) метода динамического программирования. Для этого приведем задачу (1) – (3) к виду (4) – (7) из предыдущей лекции.

Для этого введем обозначения: – вес рюкзака перед погрузкой груза j-го вида груза или вес рюкзака после погрузки грузов видов 1, 2, …, j – 1.Очевидно, что

y1 = 0. (4)




Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 1665; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.