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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

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

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

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

y₁ = 0. (4)

Дата добавления: 2014-01-11