ESCUELA POLITÉCNICA NACIONAL

FACULTAD DE INGENIERÍA ELÉCTRICA

SISTEMAS DE ADMINISTRACIÓN
DE ENERGÍA ELÉCTRICA

Ing. Marco Valencia, [Link].

1
 ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA ELÉCTRICA

SISTEMAS DE ADMINISTRACIÓN DE
ENERGÍA ELÉCTRICA

III. Operación Económica del Sistema

Parte 1: Técnicas Matemáticas - Capítulo 2

2
Programación lineal – entera mixta

• Introducción

• Métodos de solución

• El método de ramificación
y acotamiento

3
Programación lineal – entera mixta

• Introducción

• Métodos de solución

• El método de ramificación
y acotamiento

4
 MODELOS DE PROGRAMACIÓN
LINEAL ENTERA - MIXTA

PROGRAMACIÓN LINEAL: Variables toman valores reales

En muchos problemas reales: Variables pueden ser:

ENTERAS
BINARIAS (0/1)

Problemas más complejos

por ausencia de continuidad
5
 EL PROBLEMA DE LA MOCHILA

• Un excursionista debe preparar su mochila

– Existe un conjunto de objetos de utilidad
– La capacidad de la mochila es limitada

• El problema consiste en escoger un subconjunto de

objetos de manera que:
– Se maximice la utilidad para el excursionista
– No se exceda la capacidad de la mochila

6
 EL PROBLEMA DE LA MOCHILA

DATOS: VARIABLES:

n: número de objetos
xj =
aj : peso de cada objeto j
1 si el objeto j se mete en la mochila
cj : utilidad de cada objeto j
0 caso contrario
b: la capacidad máxima de la
mochila (del excursionista)

7
 EL PROBLEMA DE LA MOCHILA

RESTRICCIONES: No exceder la capacidad máxima de la mochila

a x
j 1
j j b

FUNCIÓN OBJETIVO: Maximizar la utilidad del excursionista

n
max Z   c j x j
j 1

8
 EL PROBLEMA DE LA MOCHILA

EJEMPLO:
Un armador tiene un carguero con capacidad de hasta 700 toneladas.
El carguero puede transportar contenedores de diferentes pesos para
una determinada ruta.

Contenedor c1 c2 c3 c4 c5 c6 c7 c8 c9 c10
Peso 100 155 50 112 70 80 60 118 110 55

El analista de la empresa del armador debe determinar el conjunto de

contenedores que maximiza la carga transportada.

9
 EL PROBLEMA DE LA MOCHILA

EJEMPLO:

DATOS: VARIABLES:

n = 10 contenedores
xj =
aj = peso de cada contenedor j
1 si el contenedor j se carga
cj = la utilidad es el peso de
cada contenedor transportado 0 caso contrario
b = 700 toneladas

10
 EL PROBLEMA DE LA MOCHILA

EJEMPLO:
RESTRICCIONES: El peso de la carga transportada no debe
exceder la capacidad máxima del carguero

100x1 + 155x2 + 50x3 + 112x4 + 70x5 + 80x6 + 60x7 + 118x8 + 110x9 + 55x10 <= 700

FUNCIÓN OBJETIVO: Maximizar la carga transportada

Z = 100x1 + 155x2 + 50x3 + 112x4 + 70x5 + 80x6 + 60x7 + 118x8 + 110x9 + 55x10

11
 INTRODUCCIÓN

• Un problema de programación lineal entera (ILP) está

dado por
maximizar f(x) = cx
sujeto a Ax = b
x  0 entero
• Al problema de programación lineal (LP) que se obtiene
al eliminar las restricciones de integralidad se lo conoce
como el problema LP correspondiente o como una
relajación del ILP.

12
 INTRODUCCIÓN

En general, el problema
Si x0 es una solución
P1: max f(x), x  S1 óptima de P1 y x* es una
solución óptima de P2,
se dice la relajación del problema entonces f(x0)  f(x*)

P2: max f(x), x  S2

Si x0  S2, entonces x0 es
si S2  S1. una solución óptima de
P2

P2 se dice una restricción de P1

13
 INTRODUCCIÓN

• Un problema de programación lineal entera-mixta

(PPLEM) es un problema de programación lineal (LP) en
el que algunas de las variables son enteras.

• Si todas las variables enteras son binarias (0/1), el

problema se denomina problema de programación lineal
entera-mixta 0/1 (PPLEM 0/1).

14
 INTRODUCCIÓN
maximizar 3x + 4y
sujeto a 5x + 8y ≤ 24
x, y ≥ 0 y entero

Solución LP:
x=24/5, y=0; y z =14 2/5

Redondeo:
x=5, y=0 NO FACTIBLE

El punto óptimo es
x=3, y=1, y z =13

15
 INTRODUCCIÓN

Muy útil para modelar restricciones “lógicas”:

Considérese el problema de la mochila…

max 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6

sujeto a 5x1+ 7x2+ 4x3+ 3x4+ 4x5+ 6x6 ≤ 14
xj ε {0,1}

16
 INTRODUCCIÓN

• Se seleccionan solo 3 elementos:

x1+ x2+ x3+ x4+ x5+ x6=3

• Si se selecciona el elemento 2, también el elemento 1.

x1  x2

17
 INTRODUCCIÓN

• Si se selecciona el elemento 1, el elemento 3 no se

selecciona.
x1 + x3  1

• Se debe seleccionar el elemento 4 o el elemento 5, pero

no ambos.
x4 + x5 = 1

18
 INTRODUCCIÓN

• Las variables binarias permiten modelar relaciones

complejas y no linealidades:

• Conjuntos alternativos de restricciones

• Restricciones condicionales
• Funciones discontinuas
• Funciones lineales a tramos y no convexas

19
 FUNCIONES DISCONTINUAS

El problema del cargo fijo: d + c x si x > 0

f(x) =
0 si x = 0
f(x)

f(x) puede representarse como:

c g(x,y) = c x + d y
x0
d Si x > 0 entonces
y=1 y = 0, 1
x(1–y)=0

x La última restricción puede reem-

plazarse por la restricción lineal
x  xsup y
20
Programación lineal – entera mixta

• Introducción

• Métodos de solución

• El método de ramificación
y acotamiento

21
 MÉTODOS DE SOLUCIÓN

• Existe una clase de problemas de programación entera

para los cuales la relajación LP correspondiente siempre
tiene una solución entera.
Si la solución óptima del LP
es entera, entonces es una
solución óptima para el ILP

• Pero, en general, el problema LP correspondiente no

tiene una solución óptima entera.

22
 MÉTODOS DE SOLUCIÓN

• Existen dos enfoques fundamentales para resolver

problemas de programación entera:

• Enumeración
• Planos cortantes

23
 MÉTODOS DE SOLUCIÓN

EJEMPLO

Maximizar 2x1 + x2
Sujeto a x1 + x2  5
- x1 + x2  0
6x1 + 2x2  21
x1, x2  0, enteros

24
 MÉTODOS DE SOLUCIÓN

EJEMPLO Maximizar 2x1 + x2

Sujeto a x1 + x2  5
- x1 + x2  0
6x1 + 2x2  21
x1, x2  0, enteros

Región factible LP

Solución factible ILP

25
 MÉTODOS DE SOLUCIÓN

EJEMPLO

ENUMERACIÓN:

Existen 8 soluciones
factibles.
La solución óptima
es x1 = 3, x2 = 1

26
 MÉTODOS DE SOLUCIÓN

EJEMPLO
PLANOS CORTANTES:
Plano
cortante 2 Generar una secuencia de
restricciones que eliminen
parte de la región factible
del LP correspondiente,
dejando intacta la región
factible del ILP

Cuando se han logrado

Plano suficientes cortes, el LP tiene
cortante 1 la misma solución que el ILP

27
 MÉTODOS DE SOLUCIÓN

EJEMPLO
PLANOS CORTANTES:
Plano
cortante 2 Se define S+, la envolvente
convexa de S, como la
combinación lineal convexa
de los elementos de S

S  S+  T
donde T es la región factible
Plano del problema LP
cortante 1 correspondiente

28
 MÉTODOS DE SOLUCIÓN

• Enumeración completa
Hace una lista de todas las soluciones y elige la mejor.
• Branch & Bound
Busca implícitamente todas las soluciones, pero elimina
selectivamente la gran mayoría, antes incluso de buscarlas.
• Enumeración implícita
Branch & Bound aplicado a variables binarias.

• Técnicas de planos de corte

Usa la PL para resolver programas enteros añadiendo
restricciones para eliminar las soluciones fraccionarias.

29
Programación lineal – entera mixta

• Introducción

• Métodos de solución

• El método de ramificación
y acotamiento

30
 TÉCNICAS DE ENUMERACIÓN

• Las técnicas de enumeración consideran

sistemáticamente todos los posibles valores de las
variables de decisión.

– Si existen n variables binarias, hay 2n soluciones diferentes.

31
 TÉCNICAS DE ENUMERACIÓN

ÁRBOL DE ENUMERACIÓN
Problema
original

x1 = 0 x1 = 1

x2 = 0 x2 = 1 x2 = 0 x2 = 1

x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1

3 variables binarias = 8 posibles soluciones

32
 TÉCNICAS DE ENUMERACIÓN

Supongamos que pudiésemos evaluar mil millones de

soluciones por segundo.

Los tiempos requeridos para enumerar todas las

soluciones son
n = 30 1 segundo
n = número de variables
n = 40 17 minutos binarias del problema
n = 50 11.6 días
n = 60 31 años

33
 TÉCNICAS DE ENUMERACIÓN

Supongamos que pudiésemos evaluar mil millones de

soluciones por segundo y de forma instantánea eliminar el
99.9999999% de todas las soluciones por no merecer
consideración.

Los tiempos requeridos para enumerar todas las soluciones son

n = 70 1 segundo
n = 80 17 minutos n = número de variables
binarias del problema
n = 90 11.6 días
n = 100 31 años

34
 LA IDEA DE LA RAMIFICACIÓN Y
ACOTAMIENTO

BRANCH AND BOUND: (Ramificación y acotamiento (RA))

Buscar en el árbol de enumeración, pero en cada nodo
1. Resolver el problema PL asociado
2. Eliminar el subárbol (podarlo) si:
1. La solución es entera (no hay necesidad de ir más allá)
2. La mejor solución en el subárbol no puede ser tan buena como
la mejor solución disponible
3. No existe solución factible

35
 LA IDEA DE LA RAMIFICACIÓN Y
ACOTAMIENTO

BRANCH AND BOUND:

• Establece una cota inferior y una cota superior del valor
óptimo de la función objetivo.
• El mecanismo de ramificación aumenta progresivamente el
valor de la cota inferior y disminuye también progresivamente
el valor de la cota superior.
• La diferencia entre estas cotas es una medida de la
proximidad de la solución actual a la óptima, si ésta existe.

36
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO

Minimizar - x1 - x2
Sujeto a - x1 0
2x1 - 2x2  1
2x2  9
x1, x2  0, enteros

Inicializamos:
Cota inferior =- 
Cota superior = + 
37
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO Minimizar - x1 - x2
Sujeto a - x1 0
2x1 - 2x2  1
2x2  9
x1, x2  0

P0 (5, 4.5), Z=-9.5

Cota inferior
Ramificamos = -9.5
sobre x2

38
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO Minimizar - x1 - x2
Sujeto a - x1 0
2x1 - 2x2  1
2x2  9
x2  4

P0 (5, 4.5), Z=-9.5

x2  4 x2  5

(4.5, 4), Z=-8.5 P1 P2

Ramificamos Cota inferior

sobre x1 = -8.5
39
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO
Minimizar - x1 - x2
EJEMPLO Sujeto a - x1 0
2x1 - 2x2  1
2x2  9
x2  5
Problema
no factible

P0 (5, 4.5), Z=-9.5

x2  4 x2  5

(4.5, 4), Z=-8.5 P1 P2 NoFactible

x1  4 x1  5

P3 P4
La rama se poda
por infactibilidad
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO
Minimizar - x1 - x2
EJEMPLO Sujeto a - x1 0
2x1 - 2x2  1
2x2  9
Solución entera:
Se almacena como x2  4
candidato. x1 4
Se actualiza cota
superior = -8
P0 (5, 4.5), Z=-9.5

x2  4 x2  5

(4.5, 4), Z=-8.5 P1 P2 NoFactible

x1  4 x1  5

(4, 4), Z=-8 P3 P4 La rama se poda

por integralidad
41
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO
Minimizar - x1 - x2
EJEMPLO Sujeto a - x1 0
2x1 - 2x2  1
2x2  9
x2  4
Problema x1 5
no factible

P0 (5, 4.5), Z=-9.5

x2  4 x2  5

(4.5, 4), Z=-8.5 P1 P2 NoFactible

x1  4 x1  5

La rama se poda
(4, 4), Z=-8 P3 P4
por infactibilidad
42
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO

P0 (5, 4.5), Z=-9.5

La lista ha
x2  4 x2  5 quedado vacía.
(4.5, 4), Z=-8.5 P1 P2 NoFactible El candidato a
minimizador es la
x1  4 x1  5
solución óptima
(4, 4), Z=-8 P3 P4 NoFactible

43
 ALGORITMO DE RAMIFICACIÓN Y
ACOTAMIENTO
PASO 1: INICIACIÓN

Se establece una cota superior (∞) y una cota inferior (−∞) de la

solución óptima.
Se resuelve el PPLEM inicial relajando las restricciones de
integralidad.
•Si el problema relajado es infactible, el original también lo es
y no hay solución.
•Si la solución obtenida satisface las condiciones de
integralidad, es óptima.
•En cualquier otro caso, se actualiza el valor de la cota inferior
con el valor de la función objetivo del problema relajado.
44
 ALGORITMO DE RAMIFICACIÓN Y
ACOTAMIENTO
PASO 2: RAMIFICACIÓN

Empleando la variable xk que ha de ser entera y no lo es (xk = a.b),

se generan mediante ramificación dos problemas:
•El primer problema es el PPLEM inicial relajado al que se la
añade la restricción xk ≤ a;
•El segundo problema es el PPLEM inicial relajado al que se
le añade la restricción xk ≥ a + 1.
Estos problemas se colocan ordenadamente en una lista de
problemas a procesar que son resueltos secuencialmente o en
paralelo.
Esta técnica de ramificación
cubre completamente el
espacio de soluciones 45
 ALGORITMO DE RAMIFICACIÓN Y
ACOTAMIENTO
PASO 3: SOLUCIÓN

Se resuelve el problema siguiente en la lista de

problemas a procesar.

46
 ALGORITMO DE RAMIFICACIÓN Y
ACOTAMIENTO
PASO 4: ACTUALIZACIÓN DE COTAS

•Si la solución del problema actual satisface las condiciones de

integralidad y el valor óptimo de su función objetivo es menor que la
cota superior actual, la cota superior se actualiza al valor óptimo de
la función objetivo del problema resuelto. La solución actual se
almacena como el mejor candidato a minimizador del problema
original.
•Si la solución obtenida no satisface las restricciones de
integralidad y el valor de la función objetivo está entre las cotas
inferior y superior, se actualiza el valor de la cota inferior al valor de
la función objetivo del problema resuelto y se procede a ramificar.
Los problemas generados en el proceso de ramificación se añaden
a la lista de problemas que han de resolverse.
47
 ALGORITMO DE RAMIFICACIÓN Y
ACOTAMIENTO
PASO 5: PODA

•Si la solución del problema actual cumple las restricciones de

integralidad, no hay lugar a ramificaciones adicionales relacionadas
con esa solución. La rama se poda por razones de integralidad.
•Si la solución no satisface las condiciones de integralidad y
además el valor de la función objetivo del problema resuelto es
mayor que la cota superior, no es posible obtener soluciones
mediante ramificaciones adicionales de esa rama. La rama se poda
por cotas.
•Si el problema es infactible, no hay lugar a ramificaciones
adicionales empleando esa rama. La rama se poda por
infactibilidad.
48
 ALGORITMO DE RAMIFICACIÓN Y
ACOTAMIENTO
PASO 6: OPTIMALIDAD

•Si la lista de problemas a procesar no está vacía, se continúa con

el paso 3.
•Si la lista está vacía, el procedimiento concluye.
•Si existe un candidato a minimizador, este candidato es el
minimizador;
•Si no existe, el problema es infactible.

El algoritmo de ramificación y
acotamiento devuelve la solución
óptima o notifica la infactibilidad
bien en el paso 1 o en el paso 6
49
 ESTRATEGIAS DE RAMIFICACIÓN
Y PROCESAMIENTO

• Cualquier variable que deba ser entera pero que no lo

sea en la solución actual, es una variable candidata para
ramificación.

• Cuál escoger es una cuestión no trivial cuya respuesta

ha de basarse en la estructura del problema.

50
 ESTRATEGIAS DE RAMIFICACIÓN
Y PROCESAMIENTO

• Los problemas almacenados para ser procesados

pueden tratarse mediante estrategias en anchura o en
profundidad.

• El conocimiento técnico del problema permite establecer

el uso de una u otra estrategia, o una estrategia mixta.

51
 ESTRATEGIAS DE RAMIFICACIÓN
Y PROCESAMIENTO
BÚSQUEDA EN PROFUNDIDAD

P0
• Origina rápidamente problemas
fuertemente restringidos, que
P1 P6 producen buenas cotas superiores
e inferiores.

P2 P3
• Da lugar a problemas infactibles y
por tanto a una deseable
P4 P5 eliminación de ramas.

52
 ESTRATEGIAS DE RAMIFICACIÓN
Y PROCESAMIENTO
BÚSQUEDA EN ANCHURA

P0
• Permite tratar problemas muy
similares, de lo que pueden
P1 P2 desprenderse ventajas
computacionales.

P3 P4
• Las técnicas de procesado paralelo
son aplicables a cualquiera de las
P5 P6 dos estrategias.

53
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO

Minimizar 3x1 + 2x2

Sujeto a x1 – 2x2 + x3 = 5/2
2x1 + x2 + x4 = 3/2
x1, x2, x3, x4  0
x2, x3 enteros

54
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO
Inicializamos:
EJEMPLO Cota inferior =- 
Cota superior = + 

P0 P0 (0,0,2.5,1.5), Z=0
Minimizar 3x1 + 2x2
Sujeto a x1 – 2x2 + x3 = 5/2 Nueva cota
Ramificamos inferior = 0
2x1 + x2 + x4 = 3/2 en x3
x1, x2, x3, x4  0

55
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO Cota inferior =0

Cota superior = + 

P1 P0 (0,0,2.5,1.5), Z=0
Minimizar 3x1 + 2x2 x3  2 x3  3
Sujeto a x1 – 2x2 + x3 = 5/2
P1 P2
2x1 + x2 + x4 = 3/2
x3 2 (0.5,0,2,0.5), Z=1.5

x1, x2, x3, x4  0

Solución entera. Se
guarda como mejor
candidato. Se actualiza la
cota superior
56
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO Cota inferior =0

Cota superior = 1.5

P2 P0 (0,0,2.5,1.5), Z=0
Minimizar 3x1 + 2x2 x3  2 x3  3
Sujeto a x1 – 2x2 + x3 = 5/2
P1 P2 (0,0.25,3,1.25), Z=0.5
2x1 + x2 + x4 = 3/2
x3 3 (0.5,0,2,0.5), Z=1.5

x1, x2, x3, x4  0 Ramificamos en x2.

Nueva cota inferior = 0.5

57
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO Cota inferior =0.5

Cota superior = 1.5

P3 P0 (0,0,2.5,1.5), Z=0
Minimizar 3x1 + 2x2 x3  2 x3  3
Sujeto a x1 – 2x2 + x3 = 5/2
P1 P2 (0,0.25,3,1.25), Z=0.5
2x1 + x2 + x4 = 3/2
(0.5,0,2,0.5), Z=1.5 x2  0 x2  1
x3 3
x2 0 P3 P4

x1, x2, x3, x4  0

Problema no factible.
Se poda
58
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO Cota inferior =0.5

Cota superior = 1.5

P4 P0 (0,0,2.5,1.5), Z=0
Minimizar 3x1 + 2x2 x3  2 x3  3
Sujeto a x1 – 2x2 + x3 = 5/2
P1 P2 (0,0.25,3,1.25), Z=0.5
2x1 + x2 + x4 = 3/2
(0.5,0,2,0.5), Z=1.5 x2  0 x2  1
x3 3
x2 1 (no factible) P3 P4

x1, x2, x3, x4  0 (0,1,4.5,0.5), Z=2

Función objetivo
mayor a cota superior.
Se poda 59
 EL MÉTODO DE RAMIFICACIÓN Y
ACOTAMIENTO

EJEMPLO
P0 (0,0,2.5,1.5), Z=0
x3  2 x3  3

(0.5,0,2,0.5), Z=1.5 P1 P2 (0,0.25,3,1.25), Z=0.5

x2  0 x2  1

(no factible) P3 P4 (0,1,4.5,0.5), Z=2

La lista está vacía. La

solución óptima es la
del problema P1

60
 Programación no lineal

• Introducción

• Condiciones necesarias
de optimalidad

D f(x) • Suficiencia y convexidad

S

Fo
• Teoría de la dualidad

61
 Programación no lineal

• Introducción

• Condiciones necesarias
de optimalidad

D f(x) • Suficiencia y convexidad

S

Fo
• Teoría de la dualidad

62
 MODELOS DE PROGRAMACIÓN
NO LINEAL

PROGRAMACIÓN LINEAL: Problemas muy comunes

Cubren un amplio rango de
aplicaciones

En muchos problemas reales: La función objetivo y/o

las restricciones son no
lineales

Problemas de programación
no lineal (PPNL)
EL PROBLEMA DEL PAQUETE
POSTAL

• Caja de dimensiones x, y, z.

• La oficina de correos exige que la

altura más el perímetro de la base
no exceda cierta cantidad
preestablecida.

• Se desea maximizar el volumen del

paquete.
EL PROBLEMA DEL PAQUETE
POSTAL

DATOS:

b: Longitud total que no debe

ser excedida (cm)

VARIABLES:

x: ancho de la caja (cm)

y: largo de la caja (cm)
z: altura de la caja (cm)
EL PROBLEMA DEL PAQUETE
POSTAL

RESTRICCIONES:

2x  2 y  z  b
x, y , z  0

FUNCIÓN OBJETIVO:

max V  xyz
EL PROBLEMA DE LA TIENDA DE
CAMPAÑA

• Encontrar las dimensiones

óptimas de una carpa, de manera
que se minimice la superficie
total, observando un volumen y
una altura total predefinidos.
• Carpa con base cuadrada de
lado 2a.
• La altura de las paredes es b
• El techo tiene la forma de una
piramide de altura h.
EL PROBLEMA DE LA TIENDA DE
CAMPAÑA

DATOS:

V: Volumen de la carpa
H: Altura total deseada

VARIABLES:

a: mitad de un lado de la base

cuadrada
b: altura de las paredes
h: altura del techo piramidal
EL PROBLEMA DE LA TIENDA DE
CAMPAÑA

RESTRICCIONES:

4a 2 b  h / 3  V
bh  H
a, b, h  0
FUNCIÓN OBJETIVO:


min S  4 2ab  a a 2  h 2 
 INTRODUCCIÓN

• Un problema de programación no lineal (PPNL) se puede formular

como:

minimizar Z = f(x1, . . . ,xn)

sujeto a h1(x1, . . . , xn) = 0
...
hl(x1, . . . , xn) = 0
g1(x1, . . . , xn) ≤ 0
...
gm(x1, . . . , xn) ≤ 0

70
 INTRODUCCIÓN

De forma compacta:

minimizar Z = f(x) Variables de decisión

sujeto a h (x) = 0 Función objetivo

g (x) ≤ 0

Restricciones de
igualdad
Al menos una
de las
funciones es no
lineal Restricciones de
desigualdad

71
 INTRODUCCIÓN

Caso más simple: Minimizar una función de una variable en R

Pierre de Fermat trató este

minimizar Z = f(x) problema en el siglo XVII
mediante el estudio de la
sujeto a xR posición de las rectas
tangentes.

72
 INTRODUCCIÓN

El mínimo se alcanza en un
punto del conjunto de puntos …no siempre los mínimos
donde la recta tangente es satisfacen esta condición
horizontal. Pero…

73
 INTRODUCCIÓN

En un problema general, la función no

necesariamente posee recta tangente
(hiperplano tangente).

Para poseer recta tangente la

función debe ser diferenciable.

74
 INTRODUCCIÓN

EJEMPLO
3

1 f no es
diferenciable
0
en x = -2
-1

-2

-3
-5 -4 -3 -2 -1 0 1 2 3 4 5

El mínimo se
alcanza en x=-2 75
 INTRODUCCIÓN

Se estudiarán únicamente problemas en los que todas las

funciones involucradas sean diferenciables (optimización no
lineal diferenciable).
Se han desarrollado generalizaciones del concepto de
diferenciabilidad para poder abordar problemas más
generales de optimización. Las teorías más consistentes se
basan en los llamados subgradientes, que dan lugar al
concepto de subdiferencial, y los gradientes generalizados
de Clarke.

76
 INTRODUCCIÓN

Pero, el hecho de que los candidatos a mínimos de la función se puedan

caracterizar no es suficiente para determinarlos explícitamente.

Infinito número de puntos

donde la recta tangente es
horizontal (f’(x) = 0).

Además, existe dificultad

en resolver de forma
cerrada (analíticamente)
la ecuación f’(x) = 0.

77
 INTRODUCCIÓN

La existencia de un infinito número de candidatos además

de no poder generarlos explícitamente, hace imposible
saber, de una forma cierta, si un candidato dado es un
mínimo absoluto.

La función objetivo se
optimiza en un
En programación no entorno, no en toda la
lineal se presentan región factible.
mínimos locales

78
 INTRODUCCIÓN

En las funciones convexas, un óptimo local es también

óptimo global.

Para que una función sea

convexa, su grafo, en cualquier
intervalo, debe quedar por
debajo del segmento que une
las imágenes de los extremos.

79
 INTRODUCCIÓN

Un problema general de programación no lineal puede que

no posea solución óptima, esencialmente debido a una de
las razones siguientes:

1. La función no está acotada en la región factible S.

Por ejemplo, la función de variable real f(x) = x, donde
xR decrece sin límite a −∞ cuando x tiende a −∞. En
este caso se escribirá
Infimo xS f(x) = −∞
80
 INTRODUCCIÓN

2. La función está acotada en S, pero ésta no alcanza la

mayor de las cotas inferiores en S.

Este valor se denota por ínfimo xS f(x).

Por ejemplo, la función f(x) = e−x está acotada en S = R y

la mayor de las cotas inferiores es 0 pero no es alcanzada
por f(x).

81
 INTRODUCCIÓN

TEOREMA (WEIERSTRASS)

Sea S un conjunto cerrado, acotado y no vacío de Rn y

f : S → R una función continua.
El problema
minimizar Z = f(x)
sujeto a xS
posee al menos una solución óptima.

82
 INTRODUCCIÓN

COROLARIO (EXISTENCIA DE SOLUCIONES ÓPTIMAS.)

Sea S un conjunto cerrado no vacío (posiblemente no

acotado) de Rn y f : S → R una función continua.
Si lim x→∞,xS f(x) = +∞
el problema
minimizar Z = f(x)
sujeto a xS
admite solución óptima.
83
 Programación no lineal

• Introducción

• Condiciones necesarias
de optimalidad

D f(x) • Suficiencia y convexidad

S

Fo
• Teoría de la dualidad

84
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

DEFINICIÓN (MÍNIMO GLOBAL).

Una función f(x) tiene un mínimo global en el conjunto de

puntos S (respectivamente, un mínimo global estricto) en el
punto x*, si y sólo si f(x*) ≤ f(x) [respectivamente, f(x*) < f(x)]
para todo x en S.

DEFINICIÓN (MÍNIMO LOCAL).

Una función f(x) tiene un mínimo local sobre el conjunto S en el

punto x’, si y sólo si existe un número positivo ε cumpliendo
f(x’) ≤ f(x) para todo x en S tal que 0 < ||x’ − x|| < ε.

85
CONDICIONES NECESARIAS DE
OPTIMALIDAD

Todo mínimo global

también es un
mínimo local

Mínimos locales

Mínimos globales

86
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

DEFINICIÓN (DIFERENCIABILIDAD).

Se dice que f : Rn → R es diferenciable en x si las derivadas

parciales ∂f/∂xi, i = 1, . . . , n, existen, y

donde el gradiente de f en x es el vector definido por

El gradiente es ortogonal a
las superficies de nivel y es
la dirección de máximo
ascenso de la función f en x

87
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

CONDICIONES DE KARUSH–KUHN–TUCKER

En los problemas diferenciables de optimización no restringida la

condición necesaria para que una solución sea un mínimo local es
que se anule el gradiente.

Esta propiedad no es cierta

para problemas diferenciables
restringidos.

88
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

DEFINICIÓN (CONDICIONES DE KARUSH–KUHN–TUCKER (CKKT)).

El vector x  Rn satisface las CKKT para el PPNL si existe un

par de vectores λ  Rl y µ  Rm tales que

Condiciones de
factibilidad primal

Multiplicadores Condición de
complementariedad
de Kuhn - Tucker

Condición de
factibilidad dual
89
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

f decrece

Curvas
de nivel

D f(x)

Fo

S: Región factible

D: Cono de direcciones factibles

Fo  D = 
90
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

CONDICIONES DE KARUSH–KUHN–TUCKER

Para una restricción

de igualdad

91
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

CONDICIONES DE KARUSH–KUHN–TUCKER

Para una restricción

de desigualdad

92
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

NOTA (CASOS ESPECIALES).

Si en un determinado PPNL un cierto tipo de restricción (igualdad o

desigualdad) no está presente, estas restricciones y sus respectivos
multiplicadores tampoco lo estarán en las correspondientes CKKT.

Problema no restringido:

Problema con solo restricciones de igualdad: Método clásico de

los multiplicadores

93
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

EJEMPLO: minimizar

Sujeto a 4  xy  0
B
x0

La CKKT son:  2x   y   1  0 
   1    2      A
2y  x  0   0
1 ( 4  xy )  0 C

2 x  0 D

1 , 2  0 E

94
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

EJEMPLO:
Caso 1. µ1 = 0; µ2 = 0. En este caso, de A se obtiene x = y = 0, que no
satisface B. Por tanto, el punto (0, 0) no es un punto de KKT.
Caso 2. µ1  0; µ2 = 0. En este caso, de A se deriva x2 = y2, es decir, x = ±y,
que junto a C conducen a y = ±2. La expresión A junto a B y a E implica que x
e y deben ser positivas, concluyendo que (2, 2) es un punto de KKT.
Caso 3. µ1 = 0; µ2  0. En este caso, A conduce a y = 0, y por tanto no se
satisface B.
Caso 4. µ1  0; µ2  0. En este caso, D conduce a x = 0, y entonces no se
cumple B.
El único punto de KKT, (2, 2),
es la solución óptima
95
En (2, 2):

 2x   4
f ( x )      
 2 y   4

  y    2
g1 ( x )      
  x    2

Como 2 = 0, la restricción
x  0 no está activa
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

DEFINICIÓN (RESTRICCIÓN ACTIVA)

Dado x  Rn, y dado j  {1, . . . , m}, la restricción de desigualdad

gj(x) ≤ 0 se dice que es activa en el punto x si gj(x) = 0; se denomina
no activa si gj(x) < 0. Se denota el conjunto de los índices de las
restricciones activas por I(x):

97
 CONDICIONES NECESARIAS DE
OPTIMALIDAD

LEMA:

Las condiciones de KKT son condiciones necesarias para los

óptimos locales de la mayoría de los PPNL.

98
 Programación no lineal

• Introducción

• Condiciones necesarias
de optimalidad

D f(x) • Suficiencia y convexidad

S

Fo
• Teoría de la dualidad

99
CONDICIONES DE OPTIMALIDAD:
SUFICIENCIA Y CONVEXIDAD

La diferenciabilidad es un concepto local (en un

entorno del punto) que solo permite caracterizar
los mínimos locales.

La propiedad de convexidad de las

funciones permite garantizar que
todo óptimo local del PPNL también
es un óptimo global.

100
 CONDICIONES DE OPTIMALIDAD:
SUFICIENCIA Y CONVEXIDAD

DEFINICIÓN (FUNCIÓN CONVEXA)

Sea f : S → R, donde S es un conjunto no vacío de Rn. La función f se

dice que es convexa en S si para cualquier par de puntos x1 y x2, y
cualquier escalar λ que cumpla 0 ≤ λ ≤ 1, se tiene
f (λ x1 + (1 − λ) x2) ≤ λ f(x1) + (1 − λ) f(x2)
Si la desigualdad se satisface estrictamente, se dice que f es
estrictamente convexa.
Similarmente, una función f es cóncava si se cumple la relación con
la desigualdad inversa, esto es, si la función (−f) es convexa.

101
CONDICIONES DE OPTIMALIDAD:
SUFICIENCIA Y CONVEXIDAD

CONVEXA
CÓNCAVA

NI CÓNCAVA
NI CONVEXA

102
 CONDICIONES DE OPTIMALIDAD:
SUFICIENCIA Y CONVEXIDAD

TEOREMA (ÓPTIMO GLOBAL Y LOCAL)

Considérese la función convexa f : S → R, donde S es un

conjunto convexo no vacío de Rn.
Todo óptimo local de f en S también es un óptimo global
de f en S.
Además, si f es estrictamente convexa y posee un mínimo en
S, éste es único.

103
 CONDICIONES DE OPTIMALIDAD:
SUFICIENCIA Y CONVEXIDAD

CONDICIONES SUFICIENTES DE KARUSH–KUHN–TUCKER

Considérese el PPNL consistente en la minimización de

Z = f(x)
sujeto a h(x) = 0
g(x) ≤ 0
Supóngase que existe una terna de vectores (x, µ, ) que cumple
las CKKT. Sea K+ = {k| k > 0} y K− = {k| k < 0}. Supóngase que
f(x), gi(x) para todo i  I(x) y hk(x) para todo k  K+ son funciones
convexas en Rn, y hk(x) para todo k  K- son funciones cóncavas en
Rn. Entonces x es un mínimo global.

104
 Programación no lineal

• Introducción

• Condiciones necesarias
de optimalidad

D f(x) • Suficiencia y convexidad

S

Fo
• Teoría de la dualidad

105
 TEORÍA DE LA DUALIDAD

Considérese el PPNL: minimizar Z = f(x)

sujeto a h(x) = 0 P
g(x) ≤ 0

Se define la función dual:

θ(λ,µ) = Infx {f(x) + λTh(x) + µT g(x)}

y el problema dual: maximizar ZD = θ(λ,µ)

D
sujeto a µ≥0

106
 TEORÍA DE LA DUALIDAD

Empleando la función lagrangeana

Se puede reescribir (D) como

Si se supone que las funciones f, h, y g son de tal forma que el

ínfimo de la función lagrangiana siempre se alcanza en algún
punto x, el operador “´ınfimo” puede ser reemplazado por el
operador “mínimo”.
Entonces, el problema se denomina problema dual max–min.

107
 TEORÍA DE LA DUALIDAD

Bajo hipótesis de convexidad de las funciones f y g, de que h es una

función afín y que µ es no negativo, el lagrangiano es convexo en x.

El gradiente se debe anular en los mínimos globales:

108
 TEORÍA DE LA DUALIDAD

TEOREMA (DUALIDAD DÉBIL)

Cualquier solución factible x del problema primal (P) y cualquier

solución del problema dual (D), cumplen
f(x) ≥ θ(λ,µ)

D De la definición de θ, para cualquier solución x y para cualquier solución µ

≥ 0 y λ  Rl, se tiene:

109
 TEORÍA DE LA DUALIDAD

COROLARIO (OPTIMALIDAD DUAL Y PRIMAL)

1. Se cumple lo siguiente:

2. Si f(x*) = θ(λ*,µ*) para alguna solución factible x* del problema

primal (P) y para alguna solución factible (λ*,µ*) del problema dual
(D), entonces x* y (λ*,µ*) son, respectivamente, soluciones del
problema primal y dual.
3. Si sup { θ(λ,µ) : µ0 } = +∞, entonces el problema primal no tiene
soluciones factibles.
4. Si inf { f(x) : h(x) = 0, g(x) ≤ 0}= -∞, entonces θ(λ,µ) = -∞ para cada
λ  Rl y µ  0.

110
 TEORÍA DE LA DUALIDAD

TEOREMA DE DUALIDAD PARA PROBLEMAS CONVEXOS

Considérese el problema convexo (P). Si x* resuelve el problema

primal, su vector asociado de multiplicadores (λ*,µ*) resuelve el
problema dual, y µ*g(x*) = 0. Recíprocamente, si (λ*,µ*) resuelve
el problema dual, y existe una solución, x*, del problema
lagrangiano asociado a este vector de multiplicadores que cumple
µ*g(x*) = 0, entonces x* es una solución del problema primal.

111