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

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

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 .