Методы покоординатного спуска

Сущность метода.

Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной.

Алгоритм метода.

Первый цикл:

1 шаг. x₁ = var, х₂ = х₂⁰, х₃ = х₃⁰, х_n = х_n⁰.

Ищем экстремум функции f(х₁). Положим, экстремум функции в точке х₁¹.

2 шаг. x₁ = х₁¹, x₂ = var, х₃ = х₃⁰, х_n = х_n⁰.

Экстремум f(х₂) равен х₂¹.

n шаг. x₁ = х₁¹, x₂ = х₂¹, x₃ = х₃¹,x_n = var.

В результате выполнения n шагов найдена новая точка приближения к экстремуму .

Далее проверяем критерий окончания счета:

если – решение найдено, в противном случае выполняем еще один цикл.

____________________Вопрос 34____________________

Метод покоординатного спуска с постоянным шагом

Схема алгоритма покоординатного спуска с постоянным шагом

Шаг 1.

При к = 0 вводятся исходные данные х₀, ε₁, α .

Шаг 2.

Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки х_kn по формуле:

Шаг 3.

Если ||x_(k+1)n–x_kn||₁, то поиск минимума заканчивается, причем:

Иначе к=к+1 и переходим к шагу 2.

Если же шаг выбирается из условия минимума функции:

то мы получаем аналог метода наискорейшего спуска, называемый обычно методом Гаусса – Зейделя.

____________________Вопрос 35____________________

Метод покоординатного спуска с дроблением шага

____________________Вопрос 36____________________

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

Схема метода Гаусса – Зейделя

Шаг 1.

При к=0 вводятся исходные данные х₀,₁.

Шаг 2.

Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки х_kn по формулам:

где _kn+j-1 является решением задачи одномерной минимизации функции:

Шаг 3.

Если ||x_(k+1)n–x_kn||₁, то поиск минимума заканчивается, причем:

Иначе к = к + 1 и переходим к шагу 2.

____________________Вопрос 37____________________

Постановка задач линейного программирования

Математически задача линейного программирования (ЗЛП) заключается в нахождении наибольшего или наименьшего значения линейной функции многих переменных при линейных ограничениях типа равенств и неравенств, когда на переменные есть или нет ограничений на знак.

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

(1)

(2) ,

(3) ,, (1.1)

(4) ,.

Здесь — целевая функция, линейная относительно своих аргументов, — число переменных,— число ограничений задачи. Условия (2), (3) задают линейные ограничения на ресурсы в виде неравенств и равенств, условия (4) определяют ограничения на знак переменных.

Целевая функция , где выражает критерий оптимизации, отражающий основную цель преследуемую субъектом управления — повышение эффективности использования ресурсов. В производственной сфере показателями эффективности являются обычно выручка или прибыль, что приводит к задачам максимизации. Именно (1.1) представляет собой формулировку задачи максимизации целевой функции.

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

____________________Вопрос 38____________________