где М — большое число (например, если ожидаемое оптимальное значение целевой функции порядка единиц, то можно принять М=
1000).
Если xj находится в области допустимых решений, то выполняются все ограничения и, значит, gi(xj)=0. При этом штрафная функция (4.9) равняется нулю, и новая целевая функция (4.8) оказывается равной заданной.
Если xj, не находится в области допустимых решений, то не выполняются ограничения, т. е. gi(xj) 0. Значит, gi2 (x j ) 0 , а
большое число М приводит к тому, что в новой целевой функции (4.8) штрафная функция (4.9) оказывается существенно больше заданной целевой функции f (xj). Поэтому в ходе минимизации благодаря большому градиенту в первую очередь уменьшается штрафная функция (gi(xj)), пока она не станет равной нулю (т. е. пока значения xj не войдут в область допустимых решений или пока не будет найдено допустимое решение), а далее начинается процесс минимизации заданной целевой функции.
Пример 1. Решить задачу условной оптимизации вида:
F x2 min; |
|
|
2 |
|
|
x2 2 x1 2 |
1; |
|
x1 3 2 x2 |
0,5 2 |
|
4; |
||
0 x1 4;0 x2 3. |
|
|
|
||
Решение. Первое ограничение представляет собой параболу с координатами вершины A(2;1), второе — часть плоскости, находящуюся вне окружности радиусом R = 2, центр которой имеет координаты O(3; 0,5). Без наложения второго ограничения минимум находился бы в вершине параболы в точке А и имел бы значение F1=1. Наложение дополнительного условия ухудшило результат. Минимум переместился в точку B с координатой x1=1,4. При этом F2*= x2= 1,8, т. е. его значение ухудшилось.
Решение этой задачи методом штрафных функций предусматривает следующий алгоритм.
1. Записывается условие задачи в виде системы (4.7):
16
F x2 min; |
|
|
2 |
|
|
x2 2 x1 2 |
1 0; |
|
x1 3 2 x2 |
0,5 2 y1 |
|
4 0; |
||
0 x1 4;0 x2 3; y1 0. |
|
|
|
||
Чтобы удовлетворить форме выражения (4.7), во втором ограничении сделан переход от неравенства к уравнению и введена неотрицательная переменная y1 0.
2.Составляется новая целевая функция, включающая штрафную функцию с числом М= 1000. Тогда получим:
F x2 |
1000 x2 2 x1 |
2 2 |
1 |
|
|
y1 |
x1 3 2 |
x2 0,5 2 |
4 |
|
|
min; |
|||||
0 x1 4;0 x2 |
3; y1 |
0. |
|
|
|
|
|
||||
|
|
|
|
|
|
3. Далее проводится решение полученной системы.
Для решения задач вида (4.7) существует классический метод оптимизации Лагранжа – метод разрешающих множителей. При этом предполагается, что функции f и gi (i=1,2,..,m) непрерывны вместе со своими первыми частными производными.
Суть метода Лагранжа состоит в построении функции вида
L(x1,x2, )=f(x1,x2)+ g(x1,x2) от трех переменных x1, x2, , называемой функцией Лагранжа, и в сведении задачи на условный экстремум в случае двух независимых переменных к задаче на абсолютный экстремум функции L(x1,x2, ) трех независимых переменных x1, х2, .
Функция Лагранжа L(x1,x2, ) представляет собой сумму целевой функции (4.10) и функции ограничения (4.11), умноженной на новую независимую переменную , называемую множителем Лагранжа, входящую обязательно в первой степени:
f (x1 , x2 ) min(max), |
(4.10) |
при условии
17
g(x1 , x2 ) 0. |
(4.11) |
Необходимое условие локального условного экстремума функции (4.10) при наличии ограничения (4.11) в аналитической форме имеет следующий вид: пусть (x10 , x20 ) - точка условного локального экстремума функции (4.10) при наличии ограничения (4.11) и пусть
gradg (x0 |
, x0 ) 0 . |
Тогда существует единственное число 0, такое, |
|||||||
1 |
2 |
|
|
|
|
|
|
|
|
что (трехмерная) |
точка (x0 , x0 , 0 ) |
удовлетворяет следующей |
|||||||
|
|
|
|
1 |
2 |
|
|
|
|
системе трех уравнений с тремя неизвестными x1, х2, . |
|||||||||
|
L(x1 , x2 , ) / x1 0; |
|
|
|
|
||||
|
L(x1 , x2 , ) / x2 |
0; |
|
|
|
(4.12) |
|||
|
|
|
|
||||||
|
L(x , x |
2 |
, ) / g(x , x |
2 |
) 0. |
|
|||
|
|
1 |
|
1 |
|
|
|
||
Иначе говоря, если двумерная точка |
(x0 |
, x0 ) есть точка ло- |
|||||||
|
|
|
|
|
|
|
|
1 |
2 |
кального экстремума функции (6.10) при наличии ограничения (6.12), то трехмерная точка (x10 , x20 , 0 ) - критическая точка функции Лагранжа. Отсюда следует, что для нахождения точек (условного) локального экстремума функции (4.10) при наличии ограничения (4.11) прежде всего, следует найти критические точки функции Лагранжа, т. е. найти все решения системы уравнений (4.12). Далее критические точки функции Лагранжа следует укоротить, удалив из них последние координаты 0. Затем каждую укороченную критическую точку необходимо проанализировать, является ли она в действительности точкой (условного) локального экстремума функции (4.10) при наличии ограничения (4.11) или не является. При этом используют геометрические соображения [2].
В некоторых новых задачах на условный экстремум, появляющихся в экономике, обычно укороченная критическая точка функции Лагранжа действительно является точкой условного локального (и глобального) экстремума функции (6.10) [2].
18
Пример 2. Найти экстремум функции y x12 x22 при условии, что x1+x2 1=0, т. е. решить задачу на условный экстремум методом Лагранжа.
|
Решение. Функция Лагранжа |
|
|
|
|
|||||||
L x , x |
, x2 |
x2 x x |
2 |
1 , откуда следует, что |
|
|||||||
1 |
2 |
1 |
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
L(x1 , x2 |
, ) / x1 2x1 0; |
|
|
||||||
|
|
|
L(x1 |
, x2 |
, ) / x2 2x2 0; |
|
(4.13) |
|||||
|
|
|
|
|||||||||
|
|
|
L(x , x |
2 |
, ) / x x |
2 |
1 0. |
|
||||
|
|
|
1 |
|
|
|
1 |
|
|
|
||
Система уравнений (4.13) имеет единственное решение, т. е. дает единственную критическую точку функции Лагранжа (1/2, 1/2, - 1). Укороченная критическая точка (x10 , x20 ) =(1/2; 1/2) есть точка условного локального (также и глобального) минимума заданной функции при ее заданном ограничении, что нетрудно проверить.
5. Целочисленное программирование
Задачи оптимизации, решением которых должны быть целые числа, называют задачами целочисленного (дискретного)
программирования. В том случае, если ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования, если же хотя бы одна зависимость является нелинейной, задачу называют
целочисленной задачей нелинейного программирования.
Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано с физической неделимостью многих элементов расчёта. В ряде случаев такие задачи решаются обычными методами, например, симплексметодом, с последующим округлением до целых чисел. Такой метод оправдан, когда отдельная единица составляет очень малую часть всего объёма (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач, среди которых можно выделить два
19
направления: методы отсечения (отсекающих плоскостей) и комбинаторные методы.
Метод отсекающих плоскостей (известный как метод Гомори) состоит в построении дополнительных ограничений и применении двойственного симплекс-метода. Представление о
комбинаторных методах даёт |
широко используемый на практике |
||||
метод ветвей и границ. |
|
|
|
|
|
С помощью метода ветвей и границ решаются задачи |
|||||
целочисленного |
программирования, |
в |
которых как |
целевая |
|
функция, так |
и функции |
в системе |
ограничений |
являются |
|
линейными. В общем виде любая из этих задач может быть записана следующим образом: найти максимум функции
|
|
|
n |
|
|
|
||
|
F c j x j |
max, |
(5.1) |
|||||
|
|
|
j 1 |
|
|
|
||
при условиях: |
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
(5.2) |
aij x j |
bi (i 1, m), x j |
0, |
|
|||||
j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x j 0( j 1, n). |
|
|
(5.3) |
|||||
Как и при решении задачи методом Гомори, находится оптимальный план задачи без учёта целочисленности переменных с помощью симплекс-метода. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то найдено искомое оптимальное решение задачи. Если среди компонента плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи, причём для всякого последующего плана X – F(X0) F(X). Так как у плана X0 имеются дробные числа, то пусть, например, это будет компонента xi0. Тогда в оптимальном целочисленном плане её значение будет, по крайней мере, либо меньше, либо равно ближайшему меньшему целому числу Ki0, либо больше, либо равно
20