Задача определения экстремума нелинейной целевой функции
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 .
|
