Задача о рюкзаке ( о ранце ) - файл

приобрести
скачать (163.7 kb.)





7 Вопрос

Задачи дискретной оптимизации. Основные точные методы дискретной оптимизации: поиск с возвратом, динамическое программирование, метод ветвей и границ. Приближённые методы дискретной оптимизации: жадный алгоритм, метод локальных вариаций.
В задачах дискретной оптимизации контролируемые входные переменные хj принимают значения из некоторого дискретного (конечного или счетного) множества.

Рассмотрим несколько классических примеров задач дискретной оптимизации.



Задача о рюкзаке (о ранце). Имеются вещи одного из n типов, определенной ценности сj и веса wj, значения которых – натуральные числа. В рюкзак можно положить не более H кг груза. Выбрать вещи, суммарная ценность которых максимальна.

Данную задачу можно считать частным случаем следующей.



Задача целочисленного линейного программирования (ЦЧЛП), т.е. задача ЛП, в которой все переменные хj – целые числа.

В задаче о рюкзаке обозначим хj – количество вещей j-го вида. Тогда в терминах ЦЧЛП задача о рюкзаке может быть сформулирована так: найти максимум линейной функции при ограничениях хj  0, .





Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации