Безусловная оптимизация управления

⇐ ПредыдущаяСтр 7 из 7

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

Пусть имеется зависимость

Найти такие значения a и g, при которых h_з = min. Дифференцируя в частных производных, получим

;

Так как , то ; .

Отсюда ; .

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

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

Максимум функции одной переменной определяется методом золотого сечения. Для этого в области [z , z ], на которой решается задача оптимизации, задается начальная точка z , а целевая функция рассматривается при фиксированных значениях всех факторов кроме одного, изменяющегося в пределах

z z z .

Устанавливают два значения этого фактора, равные

z = 0, 618 z + 0, 382 z ;

z = 0, 382 z + 0, 618 z .

Затем вычисляют соответствующие им значения целевой функции

R = F(z ) и R = F(z )

и сравнивают их между собой.

Если R > R , то z < z . Тогда оптимум фактора z должен лежать в пределах z z z , а z присваивается значение, равное

z = z ,

Если R < R , то z > z . Тогда оптимум фактора z должен лежать в пределах

z z z ,

а z присваивается значение, равное

z = z .

Сужение пределов осуществляется последовательно до тех пор, пока разность верхней и нижней границ не будет превышать точности вычислений.

Оптимум фактора z определяется как полусумма верхней и нижней границ

z = (z + z ) / 2.

Это значение принимают за начальное при определении оптимума следующего фактора z .

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

z₂ z_2b z_2o z_2a z₁_аz₁_о z_1bz₁ Рис 9. Покоординатный метод определения экстремума R R_x > R_y z_аz_оz_x z_y z_b z R R_x < R_y z_аz_x z_y z_о z_b z Рис. 10. Определение максимума методом золотого сечения

Нелинейное программирование

Задача определения экстремума нелинейной целевой функции

F ( z ) = extr, j = 1... n

при нелинейных ограничениях - равенствах

F (z ) - R = 0, i = 1... m

решается методом множителей Лагранжа.

Для решения этой задачи составляют вспомогательную функцию n переменных z и m неопределенных множителей (функцию Лагранжа)

Ф (z , ) = F ( z ) + [F ( z ) - R ]

и решают систему n + m уравнений:

Ф (z , ) / z = 0;

Ф (z , ) / = 0.

8.6. Линейное программирование

Сформулированную Л. В. Канторовичем задачу линейного программирования определения таких значений переменных z , которые в условиях заданных линейных ограничений на параметры R

a z [R ]

обеспечивают максимум линейной целевой функции

a z = max,

решают симплекс-методом, разработанным Дж. Данцигом.

Систему линейных ограничений-неравенств заменяют системой линейных ограничений-равенств путем введения дополнительных переменныхy . При этом свободный член целевой функции полагают равным нулю

a z + y = b ;

a z + y = 0.

Систему уравнений приводят к виду

y = b - [ a z ];

y = 0 - [ a z ].

Полученную систему уравнений представляют в виде таблицы, включающей в себя матрицу из коэффициентов и свободных членов ограничений и целевой функции:

	z	...	z	...	z
y	b	a	...	a	...	a
...	...	...	...	...	...	...
y	b	a	...	a	...	a
...	...	...	...	...	...	...
y	b	a	...	a	...	a
y	b	a		a		a

Если положить все основные переменные z , равными нулю,
то y = b . Это решение можно принять за базисное решение. Однако это решение еще не оптимально.

Для нахождения оптимального решения необходимо поменять местами основные переменные z с равным количеством дополнительных переменных y , т.е. перевести дополнительные переменные y в базис, равные нулю. Для этого поочередно в каждом столбце коэффициентов определяют разрешающий элементa , т.е. положительный элемент столбца, имеющий максимальное отношение к абсолютной величине свободного члена

a / |b | = max.

Разрешающий элемент заменяют на обратную величину

a = 1 / a .

Все остальные элементы разрешающей строки делят на разрешающий элемент

b = b / a ; a = a / a .

Все остальные элементы разрешающего столбца делят на разрешающий элемент и меняют знак на обратный

a = - a / a .

Из каждого из оставшихся элементов вычитают произведение элемента разрешающего столбца из той же строки и элемента из разрешающей строки из того же столбца, деленное на разрешающий элемент

b = b - b a / a ; a = a - a a / a .

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

Оптимальное значение каждого фактора z определяют путем потенцирования свободного члена в той же строке. Если в строке целевой функции есть положительный элемент, то соответствующую дополнительную переменную из базиса переводят в свободную, а свободную в базис.

Пример.

Задача: Требуется определить максимум функции

F = x + x

при выполнении следующих ограничений:

x + 2 x 6;

2 x + x 3;

x - 2 x - 1.

Решение. Приводим ограничения-неравенства к одному виду

x +2 x 6;

2 x + x 3;

- x + 2 x £ 1.

Заменяем ограничения-неравенства уравнениями, вводя дополнительные переменные y, и полагаем свободный член в целевой функции равным нулю

x + 2 x + y = 6;

2 x + x + y = 3;

- x + 2 x + y = 1;

x + x + y = 0.

Выражаем значения дополнительных переменных y через основные x

y = 6 - (x + 2 x );

y = 3 - (2 x + x );

y = 1 - (- x + 2 x );

y = 0 - (x + x ).

Находим разрешающий элемент в первом столбце коэффициентов и меняем местами основную переменную x и дополнительную переменную y

2 x = 3 - ( y + x )

или

x = 1, 5 - 0, 5 y - 0, 5 x .

Подставляем это значение в остальные уравнения

y = 6 - (1, 5 - 0, 5 y - 0, 5 x + 2 x );

x = 1, 5 - (0, 5 y + 0, 5 x );

y = 1 - (-1, 5 + 0, 5 y + 0, 5 x + 2 x );

y = 0 - (1, 5 - 0, 5 y - 0, 5 x + x ).

Тогда система уравнений примет вид

y = 4, 5 - (-0, 5 y + 1, 5 x );

x = 1, 5 - (0, 5 y + 0, 5 x );

y = 2, 5 - (0, 5 y + 2, 5 x );

y = -1, 5 - (-0, 5 y + 0, 5 x ).

Теперь находим разрешающий элемент во втором столбце и меняем местами основную переменную x с дополнительной переменной y

2, 5 x = 2, 5 - (0, 5 y + y )

или

x = 1 - 0, 2 y - 0, 4 y .

Подставляем это значение в остальные уравнения.

y = 4, 5 - (-0, 5 y + 1, 5 - 0, 3 y - 0, 6 y );

x = 1, 5 - ( 0, 5 y + 0, 5 - 0, 1 y - 0, 2 y );

x = 1, 0 - (0, 2 y + 0, 4 y );

y = -1, 5 - (-0, 5 y + 0, 5 - 0, 1 y - 0, 2 y ).

Тогда система уравнений примет вид

y = 3 - (-0, 8 y - 0, 6 y );

x = 1 - (0, 4 y - 0, 2 y );

x = 1 - (0, 2 y + 0, 4 y );

y = -2 - (-0, 6 y - 0, 2 y ).

Так как коэффициенты перед дополнительными переменными y и y в строке целевой функции имеют отрицательные значения, то оптимальное решение имеется

x = 1; x = 1.

Пример.

Задача: Требуется определить максимум функции F = x при условии выполнения следующих ограничений:

x + 4 x £ 16;

x - 2 x ³ - 2;

x + 2 x £ 6;

x £ 3.

Решение. Приводим ограничения-неравенства к одному виду

x + 4 x £ 16;

- x + 2 x £ 2;

x + 2 x £ 6;

x £ 3.

Заменяем ограничения-неравенства уравнениями, вводя дополнительные переменные y и полагая свободный член в целевой функции, равным нулю.

x + 4 x + y = 16;

- x + 2 x + y = 2;

x + 2 x + y = 6;

x + y = 3;

x + y = 0.

Выражаем значения дополнительных переменных y через основные x

y = 16 - (x + 4 x );

y = 2 - (-x + 2 x );

y = 6 - (x + 2 x );

y = 3 - (x );

y = 0 – ( x ).

Находим разрешающий элемент в первом столбце коэффициентов и меняем местами основную переменную x с дополнительной переменной y

x = 3 - y .

Подставляем это значение в остальные уравнения

y = 16 - ( 3 - y + 4 x );

y = 2 - (-3 + y + 2 x );

y = 6 - ( 3 - y + 2 x );

x = 3 - ( y );

y = 0 - ( x ).

Тогда система уравнений примет вид

y = 13 - (-y + 4 x );

y = 5 - ( y + 2 x );

y = 3 - (-y + 2 x );

x = 3 - ( y );

y = 0 - ( x ).

Теперь находим разрешающий элемент во втором столбце и меняем местами основную переменную x и дополнительную y

2 x = 3 - (- y + y )

или

x = 1, 5 + 0, 5 y - 0, 5 y .

Подставляем это значение в остальные уравнения

y = 13 - ( - y + 6 + 2 y - 2 y );

y = 5 - ( y + 3 + y - y );

x = 1, 5 - (-0, 5y + 0, 5y );

x = 3 - ( y );

y = 0 - ( 1, 5 + 0, 5y - 0, 5y ).

Тогда система уравнений примет вид

y = 7 - ( y - 2 y );

y = 2 - ( 2 y - y );

x = 1, 5 - (-0, 5 y + 0, 5 y );

x = 3 - ( y );

y = -1, 5 - ( 0, 5 y - 0, 5 y ).

Так как в строке целевой функции коэффициент перед дополнительной переменной y положительный, то решение x = 3 и x = 1, 5 не оптимально.

Поэтому в столбце коэффициентов перед y находим разрешающий элемент и относительно его меняем местами дополнительные переменные y и y

2 y = 2 - ( y - y )

или

y = 1 - 0, 5 y + 0, 5 y .

Подставляем это значение в остальные уравнения

y = 7 - ( 1 - 0, 5 y + 0, 5 y - 2 y );

y = 1 - ( 0, 5 y - 0, 5 y );

x = 1, 5 - (-0, 5 + 0, 25 y - 0, 25 y + 0, 5 y );

x = 3 - ( 1 - 0, 5 y + 0, 5 y );

y = -1, 5 - (0, 5 - 0, 25 y + 0, 25 y - 0, 5 y ).

Тогда система уравнений примет вид

y = 6 - (-0, 5 y₂ - 1, 5 y₃);

y = 1 - (0, 5 y₂ - 0, 5 y₃);

x = 2 - (0, 25 y₂ + 0, 25 y₃);

x = 2 - (-0, 5 y₂ + 0, 5 y₃);

y = -2 - (-0, 25 y₂ - 0, 25 y₃).

Так как коэффициенты перед дополнительными переменными y и y в строке целевой функции отрицательные, то оптимальное решение найдено. Это x = 2; x = 2.

8.7. Стохастическое программирование

Сравнение задачи стохастического программирования с задачей линейного программирования для детерминированных величин показывает, что детерминированный эквивалент задачи стохастического программирования отличается от задачи линейного программирования уменьшением допустимых значений параметров процесса ln [R ] на некоторую величину (1/ ) ln ln (1/(1- F(R ))). Эта величина определяется требуемой вероятностью работоспособного состояния F(R ) и показателем распределения случайного параметра . Она является платой за принятие решения об управлении в условиях неопределенности.

Возможно, эта плата окажется неиспользованной, но для достижения цели она необходима.

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

ln z = b / a - (a / a ) ln z ,

где b = ln R - ln c - (1 / ) lnln (1 / (1-F (R))).

Каждая их этих прямых является границей " допустимой полуплоскости", все точки которой (z₁ и z₂) удовлетворяют ограничениям-неравенствам. Часть плоскости, принадлежащая одновременно всем " допустимым полуплоскостям", образует область " допустимых решений". Все точки этой области удовлетворяют всем без исключения ограничениям-неравенствам.

Далее строят " основную прямую", уравнение которой

ln z = - (a / a ) ln z ,

и определяют направление ее возрастания. “Основную прямую” перемещают в этом направлении параллельно самой себе до тех пор, пока она не будет иметь с " областью допустимых решений" только одну общую точку. Потенцируя координаты этой точки, получают оптимальные значения z и z .

ln s P_Z ln s_O Ra ОДР q_K ОП ln v_O ln v Рис. 11. Графическое решение задачи линейного программирования

⇐ Предыдущая 1 2 3 4 5 67