Пример 4. Требуется решить систему методом сплошного перебора:

Требуется решить систему методом сплошного перебора:

Решение

Так как d1, d2, d3 могут принимать значения 0 или 1 в любом сочетании, рассмотрим все возможные сочетания (табл. 3.5) в следующей последовательности.

1. Заполнить все возможные сочетания допустимых значений d₁, d₂, d₃.

2. Определить и записать значения левых частей ограничений (1)–(4) и целевой функции.

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

4. Из оставшихся вариантов принимается тот, в котором целевая функция максимальна. В примере max L = 8 в шестом варианте (оптимальном), в котором d₁⁰ = d₃⁰ = 1; d₂⁰ = 0.

Таблица 3.5

Перечень вариантов

№ варианта	d1	d2	d3	(1)	(2)	(3)	(4)	L
				–2				–2
Требование				£ 2	£ 4	£ 3	£ 6	max

Из этого примера видно, что в данном случае всего вариантов будет 2³ = 8 и для каждого варианта надо вычислить четыре ограничения и целевую функцию, то есть выполнить N = 8 (4 + 1) = 40 вычислительных операций. Значит в общем случае N = 2 ⁿ (m + 1), где n – число переменных, m – число ограничений. Следовательно, при увеличении размерности задачи число вычислений резко возрастает (табл. 3.6).

Таблица 3.6

Зависимость числа вычислений от размерности

n	m

Для сокращения трудоемкости полного перебора применяют различные методы.

Метод фильтрующего ограничения предполагает следующую последовательность действий.

1. Принимают некоторые значения d₁, d₂, d₃, например: 1, 0, 0.

2. Определяют значение целевой функции при таком наборе переменных L = 3d₁–2d₂ + 5d₃ = 3^. 1 – 2^. 0 + 5^. 0 = 3.

3. Далее устанавливают новые значения переменных и целевой функции; причем, если полученная целевая функция меньше 3, то этот вариант не рассматривают. Для исключения возможного рассмотрения такого варианта вводят дополнительное ограничение 3d₁ – 2d_{2 +} 5d₃ ³ 3, которое называют фильтром (Ф).

4. Составляют таблицу (табл. 3.7), в которой для каждого варианта проверяют выполнение всех ограничений, включая Ф.

Таблица 3.7

Перечень вариантов

№ варианта	d1	d2	d3	Ф = F	(1)	(2)	(3)	(4)
				– –2	– – – –1	– – –	– – – – –	– – – – –
Требование				³ 3	£ 2	£ 4	£ 3	£ 6

Если вычисление прекращается, и величины не определены, то в клетках таблицы ставится прочерк.

Введение фильтрующего ограничения Ф привело к сокращению числа вычисляемых величин (24 вместо 40, то есть 60%).

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

Например, из таблицы видно, что в пятом варианте Ф = 5. Поэтому для дальнейших вычислений в качестве фильтрующего ограничения принимаем 3d₁ – 2d_{2 +} 5d₃ ³ 5 (Ф₁). Однако для следующего варианта целевой функции будет еще больше и равна Ф = 8 и в качестве фильтрующего ограничения принимается 3d₁ – 2d_{2 +} 5d₃ ³ 8 (Ф₂). Для седьмого и восьмого вариантов целевой функции не удовлетворяет требованиям фильтра Ф₂ и значения ограничений не вычисляем. Значит трехкратный фильтр (Ф, Ф₁, Ф₂) позволил сократить вычисления еще на 4, то есть надо выполнить 20 вычислений вместо 40 (50%). Более значительное сокращение трудоемкости достигается методом Беллмана с фильтром, где наибольший Ф получают сразу.