Метод условного градиента

Назначение сервиса. Онлайн-калькулятор используется для нахождения минимума функции двух переменных f(x1,x2) методом условного градиента для случая линейных ограничений ax1+bx2 ≤ c.
Количество ограничений, gi(x)
Правила ввода функций:
  1. Все переменные выражаются через x1,x2
  2. Все математические операции выражаются через общепринятые символы (+,-,*,/,^). Например, x12+x1x2, записываем как x1^2+x1*x2.
  3. При этом ограничения типа xi ≥ 0 не учитывайте.

Рассматривается ЗНП
, (1)
, (2)
, (3)
где f(x) - выпуклая функция.
Пусть - очередное приближение исходной задачи НП и . Тогда в окрестности точки ЦФ представима в виде

и линейная функция

является приближением разности с точностью до величины в некоторой окрестности точки .
Поставим вспомогательную задачу минимизации на множестве линейной функции , т. е.
(4)
при тех же ограничениях (2), (3).
Пусть - решение этой задачи. Следующее приближение к точке минимума исходной ЦФ на множестве найдем по формуле:
. (5)
В силу выпуклости следует, что .
Величина из (5) может вычисляться различными способами. Например,
,
где найдено из условия наискорейшего спуска по направлению
;
.
Другой способ вычисления значения . В начале выполнения итерации (5) полагают , после чего проверяют условие:
. (6)
Если это условие нарушается, то уменьшают в 2 раза (до тех пор, пока неравенство (6) не будет выполнено) и переходят к следующей итерации (5).
Критерий останова:
или .
Отметим, что в общем случае задача (4) является, вообще говоря, задачей нелинейного программирования ( - нелинейные функции). Укажем случаи, когда поиск решения не представляет затруднений.
Допустимое множество задано линейными ограничениями и условием неотрицательности переменных. Тогда (4) - ЗЛП и ее решение можно найти с помощью симплекс-метода.
Допустимое множество является n-мерным параллелепипедом. Тогда
(7)
Пусть ; .
В этом случае имеем:
.
Имеем ЗЛП. Пусть . Найдем начальную угловую точку. Имеем
; ; ; .
Составим таблицу.
Таблица 1


x1

x2

x3

x4

x5

x6


1

0

-1

0

0

0

a1

0

1

0

-1

0

0

a2

1

0

0

0

1

0

b1

0

1

0

0

0

1

b2

Таблица 2


x1

x2

x3

x4

x5

x6


1

0

-1

0

0

0

a1

0

1

0

-1

0

0

a2

0

0

1

0

1

0

b1a1

0

0

0

1

0

1

b2a2


Таким образом вычислим : .
Подставим в ЦФ это значение, получим: ,
где .
Если , то в точке достигнут минимум, т. е. , .
Если или , то решаем задачу дальше. Составляем симплекс-таблицу.

Таблица 3



x3

x4


x1

-1

0

a1

x2

0

-1

a2

x5

1

0

b1a1

x6

0

1

b2a2


g1

g2

- p0

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

Составляемфункцию Лагранжа L:
.

; ;
;
или
. Пример. Решить ЗНП с помощью метода условного градиента, завершая вычисления при .

,
; .

Решение. Возьмем .

Шаг 1. Найдем в точке :
.
Запишем вспомогательную задачу (4):


Это ЗЛП, ее можно решить симплекс-методом. Однако проще воспользоваться соотношениями (7), откуда следует:
.
Найдем первым способом. В данном случае
.
Из условия . Поэтому
.
Вычислим очередное приближение по формуле (5):
.
Т. к. , то требуемая точность не достигнута.
Результаты вычислений на следующих итерациях приведены в таблице.

Таблица 4







1

(0,8; 1,6)

1,789

(1; 0)

0,8

2

(0,892; 0,861)

0,745

(1; 2)

0,212

8

(0,957; 0,953)

0,1

Точность не достигнута

Окончательно имеем:
;
.
загрузка...