Читать курсовая по информационному обеспечению, программированию: "Клиент-серверное приложение для системного проектирования программного обеспечения" Страница 3

(Назад) (Cкачать работу)

- потребление j-го ресурса i-ым предметом;

- величина j-го ресурсного ограничения;

m - количество ограничений.

Решения многомерной задачи рюкзака сводится к нахождению вектора оптимизации X. Он позволяет достичь максимальной стоимости предметов, помешенных в рюкзак, при выполнении всех ограничений, наложенных на используемые ресурсы.

Метод ветвей и границ (branch and bound) - общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. В основе метода лежит идея последовательного разбиения множества допустимых решений и анализу - содержит ли данное подмножество оптимальное решение или нет.

Решение задачи загрузки рюкзака методом ветвей и границ предполагает наличие вспомогательной модели, позволяющей прогнозировать получение определенных значений целевой функции в процессе ветвления. Вспомогательная (непрерывная) задача загрузки рюкзака (НЗЗР) использует допущение о непрерывности значений управляемых переменных. Модель НЗЗР (в отличие от ЗЗР) имеет простое решение. Алгоритм решения НЗЗР требует, чтобы индексы в последовательности были отсортированы по убыванию стоимости единицы объема предметов, помещаемых в рюкзак Решение вспомогательной задачи о рюкзаке очевидно: необходимо брать груз, начиная с первого, до тех пор, пока не заполним весь рюкзак объема b. Если первые k грузов полностью поместим в рюкзак, а (k+1)-й груз частично, то оптимальное решение σn вспомогательной задачи о рюкзаке будет следующим: гдеСтоимость решения вспомогательной задачи может служить граничной (верхней) оценкой значений F(σn') модели ЗЗР, поскольку

Другими словами, если грузы "сыпучи", стоимость грузов в рюкзаке окажется не меньшей, чем в случае дискретных грузов. .2.2 Алгоритм решения многомерной задачи загрузки рюкзака

Решение многомерной задачи загрузки рюкзака должно удовлетворять m ограничениям. Схема ветвей и границ применяется для вычисления «обещаний» C(x) на каждом фрагменте решения σk.

Если как и в одномерной задаче загрузки рюкзака отказаться от дискретности xi, то есть считать, что грузы сыпучи (0≤ xi ≤1), то перейдем к формулировке вспомогательной задачи как задачи линейного программирования. Для упрощения задачи отбросим m-1 ограничений и сведем задачу к одномерной задачи загрузки рюкзака. В каждой вершине дерева перебора будет решаться m вспомогательных задач, получаю m обещаний C(x). Берется наименьшее из этих обещаний.

.3.1 Контрольный пример 1

Рассмотрим пример решения многомерной задачи загрузки рюкзака. Параметры первого примера приведены в табл. 1. Задача сформулирована следующим образом: при условиях Σa1i xi≤b1, Σa2i xi≤b2,Таблица 1. Параметры первого примера

Похожие работы