3.2.2. Эвристические методы принятия решений

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

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

На практике чаще всего используют эвристические методы решения задачи, так как точные методы невозможно применить из-за «проклятия размерности».

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

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

, (1)

при условии:

, (2)

где x {0, 1}, j = 1, 2, …, n, c_j > 0, a_j > 0, b_j > 0. Не умаляя общности, можно предположить, что переменные занумерованы так, что c₁/a₁ ≥ c₂/a₂ ≥ ≥ c_n/a_n. Будем пытаться максимизировать f(x) за счет самых больших значений c_j/a_j, полагая последовательно x₁, x₂, и т. д. равными единице до тех пор, пока не нарушится ограничение (2).

Рассмотрим алгоритм решения задачи о выборе рациона питания:

С=c₁x₁+c₂x₂+c₃x₃+c₄x₄  min;

x_i ≥ 0, i = 1,2,3,4;

а₁₁х₁+а₂₁х₂+а₃₁х₃+а₄₁х₄≥b₁;

а₁₂х₁+а₂₂х₂+а₃₂х₃+а₄₂х₄≥b₂:

а₁₃х₁+а₂₃х₃+а₃₃х₃+а₄₃х₄≥b_3.

Воспользуемся пожирающим алгоритмом (можно также найти точное решение задачи, используя симплекс метод):

1. Найдем список коэффициентов:

H={ h_11, h_12, h_13, h_21, h_{22 ,}h₂₃, …, h₄₁, h₄₂, h₄₃,} ,

где h₁₁=c₁/a_11, h₁₂=c₁/a₁₂, h₁₃=c₁/a_13,.

h₂₁=c₂/a₂₁, h₂₂=c₂/a_22, h₂₃= c₂/a₂₃ …,

h₄₁= c₄/a₄₁, h₄₂=c₂/a₄₂, , h₄₃= c₄/a₄₃,

H={c_j/a_ji i=1,4; j=1,3}.

2. Присвоим s (номер витка цикла) значение равное единице

3. Найдем минимальное значение h*_ij, h*_ij  H и исключим из списка H все значения h_kj (k=1,4).

4. Назначим максимально возможное значение x*_i (s):

x*(s)_i = b_j/a_ij.

5. Удалим из дальнейшего рассмотрения ограничение:

а_1jх₁+а_2jх₂+а_3jх₃+а_4jх₄≥b_j:

6. Используя найденное значение x*_i (s) изменим ограничения задачи:

а_1jх₁+а_2jх₂+а_3jх₃+а_4jх₄≥b_j - a_ij  x*_i(s).

7. Если список H не пустой, то увеличим s на единицу и перейдем к пункту 2. В противном случае завершим решение и найдем значение целевой функции и искомых переменных:

, i=1,4; ,

где S – множество номеров витков цикла алгоритма (шаги 2-6).