3.2 Метод Гаусса-Зайделя

Метод Гаусса-Зайделя (метод покоординатного спуска) заключается в последовательном поиске оптимума R(x)поочередно по каждой переменной [1].

Для той же самой задачи найти минимум функции методом Гаусса – Зайделя выполнив 4-8 шагов.

Дана функция R(x₁, x₂) = (x₁)² + 2·(x₂ – 1.3)² (4)

Требуется найти минимум функции.

Начальная точка: x₁ = -0.5; x₂ = 0.

Интервал поиска: x_1нач = -3, х_1кон = 2, х_2нач = -3, х_2кон = 2.

Параметры поиска: коэффициент шага h = 0,1, погрешность Е = 0,01

Из начальной точки x₁ = -0.5; x₂ = 0 вычисляем критерий.

x₁ := -0.5

x₂ := 0

R(x₁, x₂) = (x₁)² + 2·(x₂ – 1.3)² = 3.63

Ищем минимум критерия оптимальности по переменной x₁. Используем прием последовательного сканирования, т.е. «шагаем» до первого лучшего значения критерия применяя алгоритм x₁ⁱ⁺¹ = x₁ⁱ ±h. Нижний индекс – номер переменной, верхний – номер шага. Знак «+» или «-» выбирается в зависимости от направления изменения критерия: нужно взять такой знак, при котором критерий уменьшается. Выбираем знак «+».

Наилучшей в этом направлении оказывается точка с координатами:

x₁ := 0

x₂ := 0

R(x₁, x₂) = (x₁)² + 2·(x₂ – 1.3)² = 3.38

полученная после шести шагов.

Из этой точки ищем минимум критерия по переменной x₂ тем же методом.

Наилучшей в этом направлении оказывается точка с координатами:

x₁ := 0

x₂ := 0.6

R(x₁, x₂) = (x₁)² + 2·(x₂ – 1.3)² = 0.98

Полученная после 6 шагов.

На этом первый цикл заканчивается и начинается следующий, заключающийся опять в поиске minR по переменной x₁ и x₂.

После 4 шагов получаем координаты:

x₁ := 0.4

x₂ := 1

R(x₁, x₂) = (x₁)² + 2·(x₂ – 1.3)² = 0.34

Отобразим координаты на графике (рисунок 4)

Рисунок 4 – траектории полученные методом Гаусса – Зайделя

4 Решение транспортной задачи методом Фогеля.

По теории известно что решение транспортной задачи методом Фогеля [1, c. 99], позволяет найти приближенное значение оптимального плана. Проверим это на практике.

Определим колонки штрафов.

Таблица 2 – определение колонок штрафов.

	1	2	3	4	Запасы	Штраф
1	9	3	6	5	35	6-3=3
2	4	10	11	8	70	8-4=4
3	2	2	3	9	65	3-2=1
4	3	4	9	12	30	4-3=1
Потребности	40	85	25	50
Штраф	3-2=1	3-2=1	6-3=3	8-5=3

Выделяем клетку с максимальным штрафом. Находим в ряду минимальную цену, добавляем максимальное значение потребностей. Исправляем значение штрафа.

Таблица 3 – исправление значения штрафа.

	1	2	3	4	Запасы	Штраф
1	9	3	6	5	35	6-3=3
2	4(40)	10	11	8	70-40=30	(8-4=4) 10-8=2
3	2	2	3	9	65	3-2=1
4	3	4	9	12	30	4-3=1
Потребности	0	85	25	50
Штраф	3-2=1	3-2=1	6-3=3	8-5=3

Таблица 4 – повторение шага.

	1	2	3	4	Запасы	Штраф
1	9	3(35)	6	5	0	6-5=1
2	4(40)	10	11	8	70-40=30	(8-4=4) 10-8=2
3	2	2	3	9	65	3-2=1
4	3	4	9	12	30	4-3=1
Потребности	0	85-35=50	25	50
Штраф	3-2=1	3-2=1	6-3=3	8-5=3

Строку 1 больше не используем. Продолжаем поиск.

Таблица 5 – продолжение шага.

	1	2	3	4	Запасы	Штраф
1	9	3(35)	6	5	0	6-5=1
2	4(40)	10	11	8	70-40=30	(8-4=4) 10-8=2
3	2	2	3(25)	9	65-25=40	3-2=1
4	3	4	9	12	30	4-3=1
Потребности	0	85-35=50	0	50
Штраф	3-2=1	3-2=1	6-3=3	9-8=1

Столбец 3 больше не используем. Продолжаем поиск.

Таблица 6 – повторение шага, продолжение поиска.

	1	2	3	4	Запасы	Штраф
1	9	3(35)	6	5	0	6-5=1
2	4(40)	10	11	8(30)	0	(8-4=4) 10-8=2
3	2	2	3(25)	9	65-25=40	3-2=1
4	3	4	9	12	30	4-3=1
Потребности	0	85-35=50	0	50-30=20
Штраф	3-2=1	3-2=1	6-3=3	9-8=1

Строку 2 больше не используем. Продолжаем поиск.

Таблица 7 – повторение пред. шага, продолжение поиска.

	1	2	3	4	Запасы	Штраф
1	9	3(35)	6	5	0	6-5=1
2	4(40)	10	11	8(30)	0	(8-4=4) 10-8=2
3	2	2(40)	3(25)	9	40-40=0	3-2=1
4	3	4	9	12	30	4-3=1
Потребности	0	50-40=10	0	50-30=20
Штраф	3-2=1	3-2=1	6-3=3	9-8=1

Строку 3 больше не используем. Продолжаем поиск.

Таблица 8 – повторение пред. шага, продолжение поиска.

	1	2	3	4	Запасы	Штраф
1	9	3(35)	6	5	0	6-5=1
2	4(40)	10	11	8(30)	0	(8-4=4) 10-8=2
3	2	2(40)	3(25)	9	0	3-2=1
4	3	4(10)	9	12	30-10=20	4-3=1
Потребности	0	10-10=0	0	50-30=20
Штраф	3-2=1	3-2=1	6-3=3	9-8=1

Столбец № 2 больше не используем. Продолжаем поиск.

Таблица 9 – повторение пред. шага, продолжение поиска.

	1	2	3	4	Запасы	Штраф
1	9	3(35)	6	5	0	6-5=1
2	4(40)	10	11	8(30)	0	(8-4=4) 10-8=2
3	2	2(40)	3(25)	9	0	3-2=1
4	3	4(10)	9	12(20)	20-20=0	4-3=1
Потребности	0	0	0	20-20=0
Штраф	3-2=1	3-2=1	6-3=3	9-8=1

Оптимальный план найден.

Рассчитываем стоимость затрат (5).

Z= 3(35)+4(40)+8(30)+2(40)+3(25)+4(10)+12(20)= 940 (5).

Вывод: при решении данной задачи распределительным методом сумма минимальных затрат равна 820. Это подтверждает метод Фогеля позволяет сразу найти не лучший, но максимально приближенный к лучшему опорный план.

5 Планирование многофакторного эксперимента