Следовательно, эта задача является двухкритериальной.
На первом этапе решения необходимо найти множество подмножеств грузов с максимальной мощностью числа ценных вещей помещаемых в рюкзак, с учётом ограничения для ранца по весу W, а затем выявить максимальную суммарную ценность грузов в результате перебора конечного числа этих подмножеств с целью получить глобальное оптимальное решение.
На втором этапе решения нужно определить локальный оптимум решения задачи о ранце, уменьшая мощность подмножеств грузов.
В настоящее время не найдено эффективного метода точного решения задачи о ранце.
Постановка задачи о ранце
Пусть для задачи о ранце имеется n грузов. Для каждого i-го груза определён вес и ценность p,. Дана грузоподъёмность W.
Необходимо выбрать подмножество грузов максимальной мощностью, так чтобы их общий вес не превышал W, а суммарная их ценность была бы максимальной.
Метод решения задачи о ранце
Принимаем в качестве числа угадывания (N
) определённое числа грузов и объединений грузов различной мощности.
Предварительно необходимо выбрать подмножества грузов с максимальной мощностью М, так чтобы их общий вес не превышал W, путём выбора М грузов с минимальным их весом, и запомнить это число.
Первоначально осуществляется объединение и упорядочение по весу подмножества грузов по два. В дальнейшем проводиться поэтапное объединение грузов в конечные подмножества грузов, с увеличением мощности подмножества с упорядочением этих подмножеств по возрастанию веса, до получения множества грузов мощностью М по различным правилам.
Конечные подмножества проверяются по суммарному весу, которые не должны превышать W. Осуществляется итерационное угадывание количества этих подмножеств с различной мощностью, с последующей проверкой возможности выбрать подмножество грузов мощностью М, так чтобы их общий вес не превышал W.
После выявления множества подмножества грузов мощностью М с суммарным весом грузов меньше или равно W., с помощью данного метода, находится среди этого конечного множества искомый результат решения задачи о ранце в виде подмножество грузов, суммарная ценность которого была бы максимальной.
В результате поиска, согласно данного метода путём увеличения значения N
, после получении первого подмножества с мощностью М суммарным весом грузов больше W, процесс поиска заканчивается. Затем осуществляется выбор локального оптимума решения задачи о ранце с мощностью меньше М, путём уменьшения значения М и выбора N
.
Индикатором нахождения оптимального решения является само появление первого подмножества с суммарным весом грузов больше или равно W.
Для данного метода существует зависимость, согласно закономерности, присущей задачам комбинаторной оптимизации, которая является объективной.
В общем виде её можно представить в виде положительного градиента со сдвигом относительно начала координат.
Рис. 4.10. Выявленная зависимость между К
и N
.
Где Кw – количество подмножеств мощностью М с суммарным весом грузов больше или равно W, N
– шкала количества подмножеств грузов мощностью М, а N
– количество угаданных подмножеств грузов.
Метод включает:
1) выбор множества грузов с максимальной мощностью М, так чтобы их общий вес не превышал W, путём выбора грузов М с минимальным весом;
2) упорядочение множества грузов по возрастанию веса;
3) объединения грузов в подмножества грузов по два с последующим упорядочением и выбором этих подмножеств грузов с их наилучшими суммарными весами и соответствующей суммарной ценой согласно N
;
4) поэтапное объединение подмножества грузов меньшей мощностью грузов в подмножества грузов большей мощностью с последующим упорядочением до получения подмножеств грузов с числом грузов (М+1)/2 для М нечетных и с числом грузов М/2 +1 для М чётных и выбором, в дальнейшем, множества грузов подмножеств грузов большей мощности с их наилучшими суммарными весами и соответствующей суммарной ценой согласно N
.;
5) итерационный поиск подмножества грузов с числом грузов М с суммарным весом грузов больше или равно W;
6) выбор из множества подмножеств с максимальной мощностью М, подмножества, с суммарным весом грузов меньше или равно W, суммарная ценность грузов в котором была бы максимальной, путём перебора конечного числа этих подмножеств, т.е. получение искомого результата;
7) выбор локального оптимума решения задачи о ранце путём уменьшения значения М и выбора N
.
Алгоритм решения задачи о ранце
Шаг 1) Выбор подмножества грузов с максимальной мощностью М, так чтобы их общий вес не превосходил W, путём выбора М грузов с минимальным весом и запоминание его значения т.е. запоминание этого числа.
Шаг 2) Производится сортировка и запоминание грузов в соответствии с их весом, а также запоминается ценность этих грузов.
Шаг 3) Выбирается значение N
, и запоминается…
Шаг 4) Выбирается множество грузов с мощностью согласно N
с соответствующими им наилучшими весами и ценами.
Шаг 5) Производится объединения грузов в подмножества грузов по два. Осуществляется запоминание этих подмножеств грузов, с учётом их весов и цен.
Шаг 6) Производится сортировка и запоминание подмножеств грузов по два с соответствующими им наилучшими весами и соответствующей суммарной ценой.
Шаг 7) Выбирается множество подмножеств грузов по два с мощностью согласно N
с соответствующими им наилучшими суммарными весами и соответствующей суммарной ценой.
Шаг 8) Производится объединения грузов по два в подмножества грузов по три и запоминание этих подмножеств, с их суммарным весом и соответствующей суммарной ценой показанное на рис.10. Осуществляется проверка суммарного веса подмножеств грузов по три. Подмножества грузов по три с суммарным весом больше W не рассматриваются.
Рис. 4.11. Объединение грузов по три.