Математические основы теории систем. Методы оптимизации

4. Преобразуем ограничения-неравенства в ограниченияравенства путем введения искусственных переменных:

При переходе от одной симплекс-таблицы к другой необходимо проверять выполнение ограничений-равенств. В данном случае λ1 и λ2 нельзя переводить из свободных в базисные.

Решение заканчивается, когда w3 = w4 = 0 и в правом нижнем углу таблицы – 0.

Ответ: х1 = 0,8, х2 = 1,2.

101

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

Пусть X i – приближение к экстремуму на i-м шаге. В точке X i находим градиент. Затем целевая функция заменяется новой функцией, коэффициентами которой являются координаты вектора градиента в точке X i . Эта функция является линейной. Решив новую задачу линейного программирования, получаем точку Z i . Затем делается шаг в направлении отрезка Z i − X i . В результате находится новая точка X i+1 .

Постановка задачи

1.f(x1, x2,…xn) → min(max).

2.gi(x1, x2,…xn) ≤ 0, i = 1, m.

3.X 0 = (x10, x20,…xn0) – начальнаяточкаприближениякэкстремуму.

4.ε – точность нахождения экстремума.

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

Алгоритм рассматривается для i-го шага приближения к экстремуму.

Решение:

Z 0 = (0;4) .

Далее находим выражение для подсчета координат новой точки приближения к экстремуму:

x11 = x10 + α1(z10 – x10) = 0 + α1 0 =0, x21 = x20 + α1(z20 – x20) = 0 + α1 4 = 4α1.

Для нахождения величины шага подставим x11 и x21 в функцию f: f(α1) = 16α1 – 32α12 ,

следовательно, требуется выполнить еще хотя бы один шаг.

Задания для самостоятельной работы

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

Дано: ε = 0,05, xo = (0; 0).

1. f(x) = x12 + 2x22 – 16x1 – 20 x2 → min, 2. f(x) = x12+x22–18x1–20x2→min,

105

Суть метода.

Вводится искусственная целевая функция F = f(x1, x2,…xn) +

+H(x1, x2,…xn).

Н– штрафная функция, определенная следующим образом (для

определенности ищется минимум целевой функции):

Н= 0 внутри области допустимых решений,

Н> 0 вне области допустимых решений.

Вследствие такого задания Н безусловный экстремум функции F совпадет с условным экстремумом функции f.

X 2

X 3

X 0 X 1

Рис. 3.8. Графическая иллюстрация метода штрафных функций

В точках X 0 и X 1 Н = 0. В точке X 2 Н > 0, следовательно, значение F резко увеличится. Но поскольку функцию F требуется минимизировать, то следующая итерация возвращает текущую точку в область допустимых решений.

Выбор штрафной функции.

Безусловный экстремум функции F находится любым известным методом.

107

Решение:

F= f (x1, x2 ) + α g(x1, x2 ) =

=− x12 − x22 + α(18 − (x1 − 7)2 − (x2 − 7)2 ) → max.

(Шаг выбран произвольным, но в данной задаче он больше нуля, так как интегральная функция H = α·g должна уменьшать ЦФ за областью допустимых решений).

Для простоты шаг в направлении градиента возьмем постоянным

λ = 0,1.

X 0 = (6, 7), проверим выполнение ограничения для этой точки: g(6, 7) > 0, следовательно, α = 0,

и так далее, пока не будет достигнута заданная точность (точность определяется как в задачах на безусловный экстремум).

108

4. ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ

Вариационное исчисление – это математическая дисциплина, занимающаяся поиском экстремума функционалов [5].

Функционал – выражение, зависящее от функции (например, определенный интеграл).

Пример

Даны две точки на плоскости. Требуется соединить их такой кривой, чтобы круглое материальное тело (шар), двигаясь по этой кривой под действием силы тяжести без трения, доходило от одной точки до другой за минимальное время.

Составим математическое описание задачи.

Изменение кинетической энергии теларавноработесилытяжести:

Ищем некоторую функцию у(х). Этой функции будет поставлено в соответствие некоторое число – значение t для этой функции.

Задача – найти такую функцию у(х), при которой функционал (значение t) достигает минимума.

4.1. Формула Эйлера–Лагранжа

Дана следующая задача:

x0

начальные условия: y(x0) = y0, y(x1) = y1.

109