Разработка метода решения задачи

Этап 1. Происходит вычисление для каждого мероприятия коэффициента эффективности , мероприятия упорядочиваются в порядке убывания величины . В дальнейшем, для исключения иерархии индексов полагается, что они перенумерованы в порядке убывания коэффициента . Формируется множество  - множество всех решений исходной задачи в виде . Очевидно, что существуют следующие варианты решений:

Общее количество вариантов равно . Среди этих вариантов должны быть исключены решения, которые не удовлетворяют ограничениям на суммарный объем. Нижняя оценка  представляется в следующем виде:

.

Для нахождения компонент  и  необходимо определить такой номер l в нумерации мероприятий, для которого выполняется следующее неравенство:

, .

Таким образом, l – номер мероприятия, включение которого приводит к нарушению ограничения на суммарный объем мероприятий. Тогда:  - значение суммарного эффекта от мероприятий, которые могут быть размещены в рюкзаке без нарушения ограничения на суммарный объем мероприятий:

;

 - прогноз дополнительного эффекта за счет включения в состав рюкзака, в дальнейшем, предмета с максимальной эффективностью. Таким мероприятием является l –й мероприятие:

,

Где - представляет собой значение незаполненного объема ранца.

Очевидно, что

.

Этап 2. На этом этапе исходное множество  делится на два непересекающихся подмножества  и . Перед выполнением процедуры деления определяются переменная, которая должна быть включена в оптимальное решение. Эта переменная находится из условия:

, ,

Где  - множество переменных, которые могут быть включены в решение.

Очевидно, что при делении множества  множество  включает индексы, относящиеся ко всем мероприятиям, т.е.  - множество решений, которое предполагает обязательное включение первого мероприятия,  - множество решений, для которых первое мероприятие не включается в оптимальный набор мероприятий (рис.3.3.2.1)

Рис. 3.3.2.1 Ветвление исходного множества в задаче о ранце

Этап 3. Находятся характеристики множества . Производится расчет верхней оценки подмножества . Для этого определяется множество  и множество . Для множества  находится  из следующих условий:

; .

Верхняя оценка  для подмножества  включает три компоненты:

.

Тогда: , , ,    ,

.

Этап 4. Находится верхняя оценка для подмножества , которое содержит все те решения, в которых в состав мероприятий не включается мероприятие с номером . Соотношения для вычисления верхней оценки  аналогичны.

Предельное значение  находится из следующих условий:

;                  .

Верхняя оценка  для подмножества :

;         , ,    ,

.

Этап 5. В качестве перспективного подмножества выбирается подмножество, имеющее максимальную верхнюю оценку, и производится переход к выполнению следующей итерации. При выполнении этой итерации вновь определяется перспективная переменная:

.

Множество   - множество индексов переменных, которые конкурируют между собой для включения в оптимальное решение. Тогда возможны два варианта деления (рис. 3.3.2.2, 3.3.2.3).

Рис. 3.3.2.2 Ветвление для первого варианта.

Рис. 3.3.2.3. Ветвление для второго варианта.

После определения элементов множества  для каждого из подмножеств находится граничное значение . Соотношения для подмножества :

;              .

Если , то формулы будут выглядеть следующим образом:

;                  .

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