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

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

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

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

Одним из приемов, которые часто используются на практике, является "пожирающие" (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).

2.3. Решение задачи на контрольном примере

Имеется четыре продукта питания (хлеб П₁, сливки П₂, колбаса П₃, сливочное масло П₄). Известна стоимость и пищевая ценность одного килограмма каждого продукта (табл. 3.4.). Из заданного набора продуктов необходимо составить пищевой рацион, который должен содержать:

- белков не менее 0,063 кг (b ₁=0,063);

-углеводов не менее 0,100 кг (b ₂=0,1);

- жиров не менее 0,180 кг (b ₃=0,18).

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

Таблица 3.4

	Стоимость Cj (руб).	Пищевая ценность на 1 кг продукта aji
Белки (кг)	Углеводы (кг)	Жиры (кг)
П1		0,08	0,42	0,02
П2		0,03	0,05	0,10
П3		0,16		0,38
П4		0,01	0,02	0,72

Запишем условия задачи контрольного примера:

0.08₁х₁+0.03х₂+0.16х₃+0.01х₄≥0.63; (3.6)

0.42х₁+0.05х₂+0х₃+0.02х₄≥0.1; (3.7)

0.02х₁+0.1х₃+0.38х₃+0.72х₄≥0.18; (3.8)

x_i ≥ 0, i = 1, 2, 3, 4; (3.9)

С=50x₁+40x₂+170x₃+120x₄ ® min. (3.10)

Необходимо найти такие неотрицательные значения переменных х₁, х₂, х₃, х₄, удовлетворяющие линейным неравенствам (3.6-3.9), при которых линейная функция этих переменных (3.10) обращалась в минимум.

Найдем стоимость каждого продукта питания с содержанием килограмма каждого питательного вещества (табл. 3.5).

Таблица 3.5

	Стоимость (руб.)	Условная стоимость на 1 кг продукта hji
Белки (руб.)	Углеводы (руб.)	Жиры (руб.)
П1
П2		1333,3
П3			-	437.4
П4
	Необходимое количество питательного вещества в рационе	0.063	0.1	0.18

Выберем минимальное значение из таблицы 3.5 равное 119, соответствующее продукту П₁.

Количество продукта П₁, необходимого для удовлетворения рациона по углеводам равно:

.

Стоимость продукта П₁ дляудовлетворения рациона по углеводам равны:

C^*₁=c₁×x^*₁ = 50×0,238=11,9 руб.

В найденном количестве продукта П₁ будет содержаться белков:

x^*₁ × a₁₁ = 0.238 ´ 008 = 0.019 кг,

и останется удовлетворить потребность белков в количестве b^*₁:

b^*₁=b₁-x^*₁ × a₁₁ = 0,063 - 0.238 ´ 008 = 0,044 кг.

В найденном количестве продукта П₁ будет содержаться жиров:

x*₁ × a₁₃ = 0.238 ´0.02=0.00476 кг

и останется удовлетворить потребность жиров в количестве b^*₃:

b^*₃= b^*₃=b₃-x^*₁×a₁₃ =0,18- 0.238 ´0.02=0.175.

Получим таблицу 3.6 с измененными значениями потребностей в количестве белков и жиров.

Таблица 3.6

	Стоимость (руб.)	Условная стоимость на 1 кг продукта
Белки (руб.)	Углеводы (руб.)	Жиры (руб.)
П1
П2		1333,3
П3				437.4
П4
	Необходимое количество питательного вещества в рационе	0.044		0.175

Выберем минимальное значение из таблицы 3.6 равное 166, соответствующее продукту П₄.

Количество продукта П₄, необходимого для удовлетворения рациона по жирам равно:

Затраты на удовлетворение рациона по жирам продуктом П₄ равны:

C₄ = с ₄× x ₄ = 120×0,234=29,16 руб.

В найденном количестве продукта П₄ будет содержаться белков:

x ₄× a ₄₁ = 0.243 ´ 0.01 = 0.0243 кг.

и останется удовлетворить потребность белков в количестве b^**₁ :

b ^**₁ = b^* ₁ - x ₄× a ₄₁

b^{* *}₁ = b^* ₁ - x ₄× a ₄₁₌ 0,044 - 0.243 ´ 0.01 = 0,0197 = 0,02 кг.

Получим таблицу 3.7 с корректировкой количества необходимых белков.

Таблица 3.7

	Стоимость (руб.)	Условная стоимость на 1 кг продукта
Белки (руб.)	Углеводы (руб.)	Жиры (руб.)
П1
П2		1333,3
П3
П4
	Необходимое количество питательного вещества в рационе	0.02

Выберем минимальное значение из таблицы 3.7 равное 625, соответствующее продукту П₁.

Дополнительное количество продукта П₁, необходимого для удовлетворения рациона по белкам равно:

Дополнительные затраты на удовлетворение рациона по белкам продуктом П₁ равны:

С^**₁=с₁×х^**₁ =50×0,25=12,5 руб.

Находим стоимость рациона:

С=С^*₁+С₄+С^**₁ = 11.9+ 29.1+ 12.5 = 53.5 руб.

Количество продуктов необходимо приобрести в следующих количествах:

П₁(хлеб): x₁ = x^*₁ + x^**₁ = 0.238+ 0.25 = 0.488 кг;

П₄(масло): x₄ = 0.243 кг.

3. Проектирование информационного обеспечения

Задача проектирования информационного обеспечения ИС формулируется следующим образом: определить потоки, содержание, носители, форму и структуру представления информации, необходимой и достаточной для управления объектом в рассматриваемой предметной области.