Нелинейное программирование
Задача определения экстремума нелинейной целевой функции
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 y2 - 1,5 y3) ;
y = 1 - (0,5 y2 - 0,5 y3) ;
x = 2 - (0,25 y2 + 0,25 y3) ;
x = 2 - (-0,5 y2 + 0,5 y3) ;
y = -2 - (-0,25 y2 - 0,25 y3) .
Так как коэффициенты перед дополнительными переменными 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))) .
Каждая их этих прямых является границей "допустимой полуплоскости", все точки которой (z1 и z2) удовлетворяют ограничениям-неравенствам. Часть плоскости, принадлежащая одновременно всем "допустимым полуплоскостям", образует область "допустимых решений". Все точки этой области удовлетворяют всем без исключения ограничениям-неравенствам.
Далее строят "основную прямую", уравнение которой
ln z = - (a
/ a
) ln z
,
и определяют направление ее возрастания. “Основную прямую” перемещают в этом направлении параллельно самой себе до тех пор, пока она не будет иметь с "областью допустимых решений" только одну общую точку. Потенцируя координаты этой точки, получают оптимальные значения z и z
.
ln s PZ ln sO Ra ОДР qK ОП ln vO ln v Рис. 11. Графическое решение задачи линейного программирования |

Дата добавления: 2016-03-15; просмотров: 1079;