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

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

Шаг 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____________________

Способы перехода от одной формы задачи лп к другой

Существует несколько форм записи задач линейного программирования. Рассмотрим их.

1. Общая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции

(4.1)

при ограничениях

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

Здесь (и везде далее) заданные числа

2. Каноническая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции (4.1) при ограничениях

На все неизвестные наложены условия неотрицательности:

(4.2)

3. Симметричная форма записи задачи линейного программирования. Здесь принято выделять две стандартные задачи − задачу максимизации и задачу минимизации.

3.1. Стандартная задача максимизации: необходимо найти максимальное значение целевой функции (4.1) при ограничениях

и условиях неотрицательности (4.2).

3.2. Стандартная задача минимизации: необходимо найти минимальное значение целевой функции (4.1) при ограничениях

и условиях неотрицательности (4.2).

____________________Вопрос 39____________________