Однокритериальная задача. Алгоритм решения

Нам известны два метода решения задач о ранце - принцип динамического программирования (реккурентные соотношения) и метод ветвей и границ.

Постановка кзр

Считается, что у анс имеется ранец с максимальной грузоподъемностью W и предметы П₁, П₂,…., П_n каждому предмету соответствует неотрицательная характеристика c_i (стоимость ) v_i(вес), 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)

С₁, если V₁≤P

В(1,р)=

0, если V₁>P

Запишем общее реккурентное соотношение, которое позволит заполнить по заполненной к^ой строке (к+1)^ю строку.

B(k,p), если V_k+1>P

B(k +1,p)=

Max( B(k,p), С_k+1+B(k,p-V_k+1))

С помощью этих соотношений можно решить любую классическую задачу о ранце

Плюсы этого алгоритма:

• Получаем точное решение.

• Имеем оптимальные загрузки рюкзака для всех его весов от 1 до MaxW

Алгоритм решения кзр методом ветвей и границ

КЗР формулируется как задача булева линейного программирования (1)-(3). Решение методом ветвей и границ мы начинаем с определения оценок в корне ДВ. Расширим множество допустимых значений до , (7)

Получится задача о ранце с дробимыми предметами. Для решения ЗРДП используется алгоритм Дацинга:

1. Для каждого предмета П_j, J= , вычисляется показатель :

2. Предметы упорядочиваются по убыванию показателя

3. В полученном порядке предметы последовательно и полностью помещаются в ранец до тех пор, пока соблюдается ограничение по весу

4. Первый предмет, который нельзя поместить в ранец целиком , делим на две части так, чтобы помещаемая в ранец часть предмета имела вес , удовлетворяющий условию максимальной загрузки ранца.

5. Все предметы, следующие за дробимым предметом в полученном порядке в ранец не кладутся.

Найденное алгоритмом оптимальное значение критерия ЗРДП (округленная в меньшую сторону до целого числа) – верхняя оценка для критерия КЗР. Для отыскания нижней оценки значения критерия КЗР используем ЭАД( эвристический алгоритм Дацинга). Который использует пункты 1-3 алгоритма Дацинга после чего случае успеха(очередной предмет поместился в ранец), так и в случае неуспеха (предмет вне ранца) переходим к рассмотрению следующего предмета.

Если найденные верхняя и нижняя оценка в корне задачи совпадают, то решение задачи закончено. В противном случае(когда значение одной из переменных х* дробно) в корне следует выполнить ветвление.

Мы будем рассматривать дихотомическое ветвление, когда в каждой вершине проводятся две ветви – отображение двух возможных вариантов выбора значений переменной х* :

При х*=0 получаем левую дочернюю вершину, при х*=1 получаем правую. Эти условия надписываем над ребрами. Для получения оценок в дочерних вершинах применяем описанные выше алгоритмы Дацинга. В случае дальнейших ветвлений , будем их выполнять по тому же принципу, что и первые. Вершину в которой будем выполнять ветвление, назначаем, руководствуясь оптимистичной стратегией выбора.

Минус данного алгоритма:

• В худшем случае работает как полный перебор.

Плюс данного алгоритма:

• Возможно значительное сокращение времени работы.