1-3 OPTIMIZACION CON RESTRICCIONES DE DESIGUALDAD

En los problemas de la vida real, la optimizacin debe considerar las limitaciones fsicas
que imponen restricciones a las variables de decisin. Estas limitaciones imponen un
conjunto de ecuaciones o restricciones de desigualdad de la forma:

g ( P) 0 1.3.1

Ejemplos de estas restricciones son los lmites inferiores y superiores de la potencia de

operacin de una unidad generadora, o el lmite superior de una lnea de transmisin de
alto voltaje en un sistema elctrico, o los voltajes mnimos y mximos de operacin en
una red elctrica, etc.

Pimin Pi Pimax 1.3.2

Es importante mencionar que un mtodo de solucin muy utilizado, es el iniciar la

solucin resolviendo el problema ignorando las restricciones de desigualdad, se
obtienen los resultados de la solucin ptima para analizar violaciones. Si no ocurren
estas violaciones ah termina el problema. Pero, si ocurren violaciones de una o ms de
las restricciones se procede a realizar modificaciones al algoritmo.

Se han descrito muchos mtodos de solucin para manipular las restricciones de

desigualdad, la mayora se han descrito como aproximacin de una funcin de
penalizacin, pero uno de los mtodos ms utilizados es el de las condiciones de Kuhn-
Tucker.

Condiciones de Kuhn Tucker

Considere el problema de minimizacin de una funcin de costo

F(C) 1.3.3
el cual est sujeto a satisfacer un conjunto de ecuaciones de restricciones de igualdad
h(C) =0 1.3.4
y restricciones de desigualdad
g(C)0 1.3.5

Las restricciones de igualdad pueden ser manipuladas fcilmente utilizando los

multiplicadores de Lagrange. Y podemos transformar las restricciones de desigualdad
en ecuaciones de de igualdad utilizando variables slack : vi Esto produce las
relaciones equivalentes en 1.3.5

gi (C) + vi2 = 0 1.3.6

esto garantiza que se cumplan las restricciones de desigualdad.

con esta transformacin la funcin de costo aumentada y representada en forma
vectorial es:

J (C ) F (C ) T h(C ) T g (C ) V 2 1.3.7
o en forma expandida:

J (C ) F (C ) i hi i ( g i vi2 ) 1.3.8
Las condiciones necesarias para optimalidad son obtenidas como resultado de aplicar la
tcnica variacional.

J
0 1.3.9
Pi

J
0 1.3.10
i

J
0 1.3.11
i

J
0 1.3.12
vi

Las primeras tres condiciones son conocidas, la ltima es:

J
2 i vi 0 1.3.13
vi

Sustituyendo vi de la ecuacin 1.3.6, se obtiene:

i gi 0 1.3.14

Estas expresiones se llaman Ecuaciones de Kuhn Tucker.

Ya sea que el multiplicador i o que gi sea cero. El caso sin violaciones corresponde a
i = 0 . Si ocurren violaciones gi se pone en su lmite gi = 0

Los requerimientos de 1.3.9 combinados con 1.3.8 se escriben

F h g
( ) j ( j ) j ( j ) 0
Pi Pi Pi

Por simplicidad, consideremos un problema de 2 dimensiones con 2 restricciones de

desigualdad y sin restricciones de igualdad. Si suponemos que el mnimo ocurre en un
punto P(0) en el interior de la regin, segn se muestra en la figura 1 En ese caso F / P i
= 0 Si el mnimo ocurre en el lmite, g 1 ( P) = 0 el gradiente J tiene que ser
ortogonal al lmite y tiene direccin hacia adentro segn se muestra en la figura 2.
E n este caso F 1g1 0
 g1(P) g1(P)

g2 (P)
P(0) g1 g2(P)

F
P(0)

figura 1 figura 2

En la figura 3 el mnimo est en el lmite de las dos restricciones, por lo que tenemos:

F 1g1 2 g 2 0

Ejemplo:
Considere dos plantas trmicas alimentando un sistema elctrico de potencia. Los costos
de combustibles asociados a cada una de las dos unidades son:

C1 = 4P1 + 0.01 P12

C2 = 2P2 + 0.03 P22

El objetivo es el de minimizar el costo total de operacin mientras se satisfacen las

restricciones de igualdad:

P1 + P2 = PD PD : Potencia Total Demandada

Utilizamos una funcin de costo aumentada con las restricciones utilizando un

multiplicador de Lagrange .

C 4 P1 2 P2 0.01P12 0.03P22 ( PD P1 P2 )
las condiciones necesarias para la optimizacin son:

4 + 0.02 P1 = 0
2 + 0.06 P2 = 0
P1 + P2 = PD

Eliminando P2 y obtenemos una ecuacin para P1

0.08 P1 + (2-0.06 PD ) = 0
como PD es informacin conocida, se encuentran las otras variables
PD = 50 P1 = 12.5 P2 = 37.5 = 4.25
PD = 100 P1 = 50 P2 = 50 =5
PD = 200 P1 = 125 P2 = 75 = 6.5
PD = 250 P1 = 162.5 P2 = 87.5 = 7.25

P1 y P2 son positivos, pero estos valores obtenidos podran violar restricciones de

operacin mnimas y mximas de las unidades generadoras.
Supongamos una restriccin de operacin en P1.
50 P1 150
imponemos como ejemplo, restricciones de mnimo y mximo en la planta ms barata

esta restriccin se puede convertir en dos restricciones:

50 P1 0 P1 150 0

De acuerdo a la teora Kuhn Tucker , la funcin de costo aumentada es

F ( P) F ( P) ( PD P1 P2 ) 1 (50 P1 ) 2 ( P1 150)

las condiciones necesarias son:

4 + 0.02 P1 - 1 + 2 = 0
2 + 0.06 P2 = 0
P1 + P2 -PD = 0
1 ( 50 P1 ) = 0
2 ( P1 150 ) = 0

Ahora tenemos 5 ecuaciones en lugar de tres,

Considere el caso en que PD = 50, en este caso se viola el lmite inferior y la solucin
ptima se obtiene utilizando P1 en el lmite inferior violado. Las condiciones de
optimalidad se dan con los requerimientos

P1 = 50 2 = 0
El lmite superior no es violado, la solucin es:
P 2 = 0 = 2 1 = 3

La solucin para el caso con PD = 250 viola el lmite mximo y los resultados ptimos
son:
P1 = 150 P2 = 100 1 = 0 2 = 1 = 8

Cuando la demanda es de 100 o 200, no se violan las restricciones de desigualdad por lo

que 1 = 2 = 0

Ejemplo
Considere el siguiente problema

min f(x) = x1
sujeto a :
g1 ( x) 16 ( x1 4) 2 ( x2 ) 2 0
 h1 ( x) ( x1 3) 2 ( x2 2) 2 13 0

La funcin de costo aumentada ser:

m p
f ( x ) i g i ( x ) j h j ( x * ) 0
* *

i 1 j 1

x1 16 ( x1 4) 2 x22
f ( x ) 1

Verificaremos si los puntos (0,0) y ( 3 + 13, 2) satisfacen las condiciones de Kuhn-

Tucker

1) Punto ( 0,0)
Problema 1
1- Maximizar U = x*y
sujeto a x + y 100
x 40
y x,y 0
Sol. El lagrangeano es L xy 1 (100 x y ) 2 (40 x)
y las condiciones de Kuhn Tucker son:

L
L / x y 1 2 0 x0 y x 0
x
L
L / y x 1 0 y0 y y 0
y
L
L / 1 100 x y 0 10 y 1 =0
1
L
L/2 = 40-x 0 20 y 2 =0
2

Para resolver, no tiene sentido el tratar con x = 0 o y = 0 , pues U = x*y =0

y la funcin objetivo (ganancias) es mnima
Supongamos que tanto x,y son diferentes de cero, L/x , L/y = 0
como no estamos en el lmite (restriccin) la pendiente es cero
esto significa que
y 1 2 = x 1
y 2 = x

L
supongamos que x # 40, (no en el lmite), entonces 2 =0, pues 2 =0
2
luego x = y = 50. Pero esto viola la restriccin x 40. Por lo que podramos suponer
que estamos en la restriccin (lmite) x = 40. As y = 60
y
L/x = L/y = 0 1 = 40 2 = 20

Problema 2
Resolver el siguiente problema de minimizacin

Minimizar C ( x1 4) ( x2 4)
2 2

sujeto a 2 x1 3x2 6
3 x1 2 x2 12
x1 , x2 0
Sol. El lagrangeano
L ( x1 4) 2 ( x2 4) 2 1 (6 2 x1 3x2 ) 2 (12 3 x1 2 x2 )

como es de minimizacin, las condiciones apropiadas dan:

L / x1 2( x1 4) 21 32 0 (1)
L / x2 2( x2 4) 31 22 0 (2)
L / 1 6 2 x1 3 x2 0 (3)
 L / 2 12 3 x1 2 x2 0 (4)

Para encontrar la solucin, por prueba y error

Supongamos 1 , 2 > 0 ( ambas restricciones en el lmite)
Con multiplicadores de Lagrange positivos,
L / 1 L / 2 0

de (3) y (4) 6 2 x1 3 x2 12 3 x1 2 x 2
x1 = 4 4/5 x2 = -1 1/5 lo cual viola la restricciones de no negatividad de x2

Probemos x1> 0 x2 > 0 lo que implica L / x1 L / x2 0

y para (1) y (2) 2( x1 4) 21 32 0 y 2( x2 4) 31 22 0

de estas dos obtenemos 4 x1 6 x2 51 8 0

suponiendo 1 = 0 x1- (3/2)x2 = -2

Si suponemos que 2 # 0 entonces L/2 = 0

entonces 3x1+2x2 = 12

Obtenemos 1 = 0 2 = 16/13 ( 3/13) > 0

Como no se viola ninguna restriccin y las variables no son negativas

LOCALIZACION DE MAXIMOS Y MINIMOS (CONDICION NECESARIA)

Se denominan puntos estacionarios, aquellos que pueden ser mximo, mnimo, o de

inflexin. El problema se reduce a localizar los puntos en los cuales las derivadas
parciales son cero o donde son discontinuas.

Condiciones necesarias para una variable independiente

Podemos desarrollar un criterio de seleccin para establecer si un punto estacionario es
un mnimo local o un mximo local a partir de la serie de Taylor alrededor de un punto
estacionario x0
la expansin de Taylor es:
1 2
y ( x ) y ( x0 ) y 1 ( x0 )( x x0 ) y ( x x0 ) 2 ter min osordenalt o
2

Seleccionemos x suficientemente cerca de x 0 por lo que los trminos de orden alto se

hacen despreciables respecto a los de orden 2. Luego, la primera derivada y1 es cero

y(x) = y(x0) + y2 (x0) (x x0)

Podemos determinar si x0 es un mnimo o un mximo local examinando el valor de la
segunda derivada y2(x0) debido a que x x 0 siempre ser positiva. Si la segunda
derivada es positiva, luego el trmino y 2(x0)(x-x0)2 siempre produce un incremento al
valor de y(x), por lo que y(x0) es un mnimo.
Resumiendo:
Si la segunda derivada y2(x0) > 0 luego y(x0) es un mnimo
y2(x0) < 0 luego y(x0) es un mximo
y2(x0) = 0 no se puede decir nada
Si la segunda derivada es cero, se deben examinar los trminos de ms alto orden, en
general, la serie de Taylor
1
y ( x) y ( x0 ) ( ) y n ( x0 )( x x0 ) n
n!
Si n es par, luego ( x x0)n siempre es positivo y el resultado esta definido por la
ensima derivada

y(n) (x0) > 0 luego y(x0) es un mnimo

y(n) (x0) < 0 luego y(x0) es un mximo

Si n es impar (x-x0) cambia de signo conforme x se mueve de x < x0 a valores x > x0

luego hay un punto de inflexin.

Ejemplo a
Localizar los puntos extremos de la siguiente funcin y(x)
y( x) x 4 / 4 x 2 / 2
y 1 ( x) x 3 x x( x 2 1) x( x 1)( x 1) 0
Los puntos estacionarios son: x = 0 x = 1 x = -1

y2(0) = -1 es mximo y2(1) = 2 es mnimo y2(-1) = 2 es mnimo

Ejemplo b
y(x) = x5
y1(x) = 5x4 el punto estacionario es 0
y2(x) = 20x3 y2(0) = 0
y3(x) = 60x2 y3(0) = 0 no se puede decir nada
y4(x) = 120x y4(0) = 0
y5(x) = 120 y5(0) = 120 n=5 es impar y el punto estacionario es un punto de
inflexin.

Criterio para mnimo o mximo local para una funcin de 2 variables

El criterio para un mximo o mnimo local de un punto estacionario x 0(x10,x20) de una

funcin de dos variables, utilizando la expansin de la serie de Taylor es

1
y ( x1 , x2 ) y ( x10 , x20 ) y x1 ( x1 x10 ) y x 2 ( x2 x20 ) [ y x1 x1 ( x1 x10 ) 2 2 y x1 x 2 ( x1 x10 )( x2 x20 )
2
y x 2 x 2 ( x2 x20 ) 2 ter min oaltoorden
x1 , x2 : son las derivadas parciales con respecto a esas variables

De nuevo, se selecciona y(x1,x2) lo suficientemente cerca de y(x10,x20) para que los

trminos de orden alto se hagan despreciables respecto al de segundo orden. La primera
derivada es cero en el punto estacionario por lo que

1 y y x1 x 2 ( x1 x10 )
y ( x1 , x2 ) y ( x10 , x20 ) [( x1 x10 )( x2 x20 )] x1 x1
2 y x 2 x1 y x 2 x 2 ( x2 x20 )

En notacin vectorial
 1
y ( x ) y (x 0 ) [( x x 0 ) T H0 (x x 0 )]
2
donde H0 es la matriz Hessiana y es la matriz de segundas derivadas evaluadas en el
punto estacionario x0
y(x0) puede ser un mnimo o un mximo dependiendo de si el siguiente trmino de la
expresin ( forma cuadrtica) es positiva o negativa.

y(x0) es mnimo si yx1x1 > 0 y H>0

y(x0) es mximo si yx1x1 < 0 y H<0

Ejemplo
El costo de operacin C($/ao) = 1000 P + 4* 109 /PR + 2.5* 105 R
P,R son variables

C
Las derivadas parciales 1000 4 * 10 9 / RP 2 0
P
C
2.5 * 10 5 4 * 10 9 / PR 2
R
Resolviendo simultneamente P = 1000 R = 4 y el costo C = 3*106 $ por ao
C(P,R) es mnimo si

2C 2C
2C P 2 PR 0
2C 2C
0 y
P 2

RP R 2
evaluando en el punto estacionario P = 1000

2C 2 10 3 / 4
20 3x10 / 16 0
6
y 3
P 2
6
10 / 4 10 / 8

Ejemplo
Hallar los puntos estacionarios del siguiente problema restringido utilizando el mtodo
de Lagrange
Optimizar y(x) = x1 x2
sujeto a F(x) = x12 + x22 -1 = 0
El lagrangiano, o funcin aumentada es L(x1,x2, ) = x1 + x2+ ( x12 + x22 -1)
las derivadas parciales

L/x1 = x2 + 2x1=0 L/x2 = x1 + 2x2=0 L/x = x12 + x22-1=0

Resolviendo simultneamente hallamos los siguientes puntos estacionarios

mximo x1 = ()2 x2 = ()2 =

x1 = -()2 x2 = -()2 = -
mnimo x1 = ()2 x2 = -()2 =
x1 = -()2 x2 = ()2 =

Ejemplo
Localizar los puntos estacionarios
y = x4/2 x2/2

Solucin dy/dt = 2x3-x = 0 x( 2x2-1) = 0 x=0 x =

dy 2
6x 2 1 para x = 0 x = x x= -
dx 2

dy 2 dy 2 dy 2
1 (mximo) 2 (mnimo) 2 (mmimo)
dx 2 dx 2 dx 2

Ejemplo Localizar puntos estacionarios

y = x7
Solucin
y1 (x) = 7x6 = 0 ( x=0 es el punto estacionario)
y2 (x) = 42x5 y2(0)=0 no se dice nada
y3 (x) = 210x4
y4 (x) = 840x3
y5 (x) = 2520x2
y6 (x) = 5040x1
y7 (x) = 5040 La derivada diferente de cero es par y es un punto de inflexin

Ejemplo Localizar puntos estacionarios

y = x12 + x1 x2 + x22

y/x1 = 2x1 + x2 = 0 y/x2 = x1 + 2x2 = 0

Resolviendo simultneamente los puntos estacionarios x1 = x2 = 0

y 2 dy 2
2 1
x1
2
dx1x 2

y 2 dy 2
2 1
x2
2
dx1x 2
2 1 y 2
1 3 >0 2 >0
2 x1
2

El signo es positivo y el punto x1 = x2 = 0 es un mnimo

Ejemplo Resolver por Multiplicadores de Lagrange y clasificar los puntos

estacionarios
 minimizar y 2 x1 4 x1 x2 4 x2 x1 3 x2
2 2

sujeto a 10 x1 + 5x2 3

Solucin
Convertir el problema con restricciones de desigualdad en uno con restricciones de
igualdad utilizando variable de holgura x3 positiva x32

10 x1 5 x2 x3 3
2

El lagrangeano
L 2 x1 4 x1 x2 4 x2 x1 3x2 (10 x1 5 x2 x3 3)
2 2 2

L
4 x1 4 x2 1 10 0
x1
L
4 x1 8 x2 3 5 0
x2
L
2 x 3 0
x3
L
10 x1 5 x2 x3 3 0
2

x
dos posibilidades
= 0 o x3=0 Si : x3=0 (igualdad) Si : =0 (desigualdad)

Para = 0 x3 = 0
1) 4x1 4x2 = -1 1) 4x1 4x2 + 10 = -1
2) -4x1 +8x2 = 3 2) -4x1 +8x2 + 5 = 3
x32 = 3- 10x1 5x2 3) 10 x1 + 5x2 = 3

Resolviendo simultneamente
x1 = x32 = -2 No satisface la restriccin x2 = 53/130
Este es el punto estacionario para el no restringido resolviendo para da

2y/x12 = 4 2y/x22 = 8 = 8/325 > 0 es mnimo

4 4
2y/x1x2 = -4 4 = 48 mnimo
8
x1 = 5/ 52 x2= 53/130 = 8/325 mnimo