M
M
Mtodos de optimizacin
Begoa Vitoriano
www.mat.ucm.es/~bvitoria
Andrs Ramos
http://www.iit.upcomillas.es/~aramos
Facultad CC. Matemticas, Universidad Complutense, Pza. Ciencias 3, 28040 Madrid http://www.mat.ucm.es
NDICE
I. OPTIMIZACIN LINEAL ................................................................ 1
19/02/2010 i
II. OPTIMIZACIN LINEAL ENTERA MIXTA ...................................113
IV.1. ESTOCASTICIDAD..............................................................................................195
IV.2. OPTIMIZACIN LINEAL BIETAPA Y MULTIETAPA ...............................................207
IV.3. OPTIMIZACIN LINEAL ESTOCSTICA BIETAPA .................................................209
ii 19/02/2010
IV.4. OPTIMIZACIN LINEAL ESTOCSTICA MULTIETAPA .......................................... 210
IV.5. REFERENCIAS ................................................................................................... 212
V. PROGRAMACIN DINMICA .................................................... 217
19/02/2010 iii
MTODOS DE OPTIMIZACIN
I. Optimizacin lineal
I.1. Introduccin
min z = c j x j
xj
j
a x
j
ij j = bi (1.1)
xj 0
19/02/2010 1
OPTIMIZACIN LINEAL
Aditividad
Cada ecuacin en un problema LP es la suma de las contribuciones individuales de
las respectivas actividades.
Divisibilidad
Cualquier variable puede tomar cualquier valor, no necesariamente entero, que
satisfaga las restricciones incluyendo las de no negatividad.
Certidumbre
Los parmetros (constantes) de un problema LP se suponen conocidos con
certidumbre (pueden ser estimaciones, pero stas se tratan como valores conocidos).
x2
3x 1 + 2x 2 18
2x 2 12
(0,6)
(2,6)
x1 4
max z = 3x 1 + 5x 2
Rectas de
x1 4
(4,3) isofuncin
2x 2 12
3x 1 +2x 2 18
x 1, x2 0 3x 1 + 5x 2
(4,0) x1
(0,0)
La regin factible est encerrada por las tres rectas que constituyen las restricciones
ms los dos ejes, que son las rectas correspondientes a la no negatividad de las
variables. La solucin ptima se halla grficamente desplazando paralela a s misma la
recta de isofuncin objetivo en el sentido de maximizacin (direccin del gradiente de
2 19/02/2010
MTODOS DE OPTIMIZACIN
la funcin objetivo, c ) hasta que se alcanza el ltimo punto de la regin factible. sta
corresponde al punto (x 1, x 2 ) = (2, 6) con un valor de la funcin objetivo z = 36 .
Hay una serie de conceptos geomtricos que hay que definir antes de analizar la
geometra de un problema de programacin lineal.
Un hiperplano est definido por el conjunto de puntos x j que cumplen una ecuacin
axj ij j bi .
19/02/2010 3
OPTIMIZACIN LINEAL
El contorno de una regin factible contiene las soluciones factibles que estn en uno
o ms hiperplanos. Arista es el segmento obtenido por solucin de n 1 hiperplanos,
siendo sus extremos soluciones factibles vrtices.
puede expresar como combinacin lineal convexa de los vrtices del mismo.
Sin embargo, este resultado no es de una aplicacin inmediata ya que, por un lado,
el nmero total de vrtices o puntos extremos posibles del politopo (no todos ellos son
n n!
necesariamente factibles) puede ser muy grande (es de C n ,m = m = y
m !(n m )!
4 19/02/2010
MTODOS DE OPTIMIZACIN
crece exponencialmente con el tamao del problema) y, por otro lado, hay que calcular
cules son los puntos extremos, que si bien estn caracterizados y existe el
procedimiento para hacerlo puede ser largo y costoso. Adems en el caso de que no
haya ningn punto factible, no sera detectado hasta la prueba de todos los puntos
candidatos a ser extremos (C n ,m puntos) y, en el caso de que la solucin sea no acotada,
Por lo tanto, se impone la bsqueda del ptimo de una forma dirigida, es decir, con
ciertos criterios que favorezcan esta bsqueda y que adems permitan la deteccin de
situaciones como las descritas en el apartado anterior. Estos criterios se plasman en un
mtodo o algoritmo de tipo algebraico que se describe en la siguiente seccin.
19/02/2010 5
OPTIMIZACIN LINEAL
x2
3x 1 + 2x 2 18
2x 2 12
(0,6)
(2,6)
x1 4
Rectas de
isofuncin
(4,3) objetivo
3x 1 + 5x 2
(4,0) x1
(0,0)
min z = cT x
Ax = b (1.2)
x 0
n mn
donde x es el vector de las variables del problema, A es la matriz de
n
restricciones del problema o matriz del lado izquierdo (left hand side LHS), c es
el vector de los coeficientes de las variables en la funcin objetivo o vector de costes,
m
b es el vector del lado derecho (right hand side RHS) o vector de cotas de las
restricciones, siendo b 0 , y la variable z es el valor de la funcin objetivo.
Por consiguiente,
1
Por convencin en la formulacin los vectores son columna, su transposicin se representa por un
superndice T , las variables se ubican a la izquierda de las ecuaciones y los coeficientes de las variables
preceden a stas.
6 19/02/2010
MTODOS DE OPTIMIZACIN
min z = 3x 1 5x 2
x1 +x 3 =4
2x 2 +x 4 = 12
3x 1 +2x 2 +x 5 = 18
x 1, x 2, x 3, x 4, x5 0
3 x1
1 1 4
5 x 2
siendo A = 2 1 , b = 12 , c = y x = x 3 .
x 4
3 2 1 18
x 5
Funcin objetivo
19/02/2010 7
OPTIMIZACIN LINEAL
Restricciones
a x
j
ij j bi aij x j + ui = bi
j
a x
j
ij j bi aij x j vi = bi
j
Variables
0 yj .
Solucin factible
8 19/02/2010
MTODOS DE OPTIMIZACIN
Solucin infactible
Una base de la matriz de restricciones o matriz del problema es una matriz cuadrada
no singular (es decir, tiene inversa) de rango mximo en A , r (A) = m . Las
variables asociadas a las columnas que forman la base se denominan variables
bsicas y el resto variables secundarias (o no bsicas).
Solucin bsica factible es aqulla con m variables bsicas que pueden tomar valor
diferente de 0 y (n m ) variables no bsicas que toman valor 0, est asociada a una
base de la matriz. Los valores de las variables bsicas, si la base es B , se calculan
por resolucin de un sistema de m m ecuaciones, es decir, se obtienen calculando
B 1b .
Toda solucin bsica factible est asociada a un nico punto extremo o vrtice y
todo punto extremo est asociado a alguna solucin bsica factible. Sin embargo,
puede existir un punto extremo que corresponda a dos bases diferentes en presencia
de degeneracin.
Dos soluciones factibles vrtices son adyacentes si la lnea que los conecta es una
arista, es decir, si todas excepto una de sus variables son iguales. Cada solucin
factible vrtice tiene n soluciones factibles vrtices adyacentes. Moverse de una
solucin bsica factible a otra adyacente es cambiar de una variable no bsica a
bsica y al contrario para otra variable.
19/02/2010 9
OPTIMIZACIN LINEAL
Solucin ptima
Aquella solucin bsica factible (vrtice) con mejor valor de la funcin objetivo.
Pueden existir mltiples soluciones ptimas. Esta situacin, que por inspeccin del
problema de dos dimensiones parecera infrecuente, es una situacin habitual en la
realidad por razn de que el criterio de optimalidad se comprueba numricamente,
es decir, cuando la tasa de mejora de la funcin objetivo est por debajo de cierta
tolerancia muy pequea pero no cero.
Si admite una solucin factible, admite al menos una solucin bsica factible.
Si admite una solucin ptima finita, admite al menos una solucin bsica ptima.
El comportamiento del mtodo simplex en el peor caso es muy pobre. Sin embargo,
en la prctica recorre un nmero muy inferior al nmero total de vrtices posibles. Para
el problema anterior el mtodo simplex recorre 3 vrtices (incluyendo el inicial) de un
5
nmero total posible (factibles e infactibles) de C 5,2 = = 10 .
2
10 19/02/2010
MTODOS DE OPTIMIZACIN
z = cTB x B + cTN x N = cTB B 1b cTB B 1Nx N + cTN x N = cTB B 1b + cTN cTB B 1N x N (1.4)
x B = b = B 1b (1.5)
Definamos
wT cTB B 1 (1.7)
Y B 1N (1.8)
19/02/2010 11
OPTIMIZACIN LINEAL
particular sera
z = cTB x B + cj x j = z + (c j z j )x j
j I N j I N
1 1
3
cB = , cN = , B = 1 = B 1 y N = 2 .
5
1 3 2
12 19/02/2010
MTODOS DE OPTIMIZACIN
4
Los valores que toman dichas variables sern xB = b = B b = 12 y xN = ,
1
18
4 1
x
xB = B b B NxN = 12 2 1
1 1
x2
18 3 2
y el de la funcin objetivo
x
z = cBT B 1b + cTN cBT B 1 N xN = 0 + [ 3 5] 1
x2
Para determinar hasta dnde se puede incrementar dicha variable sin violar ninguna
restriccin de no negatividad de las variables bsicas se observan las ecuaciones de las
variables bsicas
19/02/2010 13
OPTIMIZACIN LINEAL
( xB )i = bi yit xt (1.12)
hasta alcanzar el valor 0 para xt = bi / yit , bi > 0 por ser el valor de la variable bsica.
valores fueran yit 0 el problema sera no acotado, puesto que la variable bsica
entrante se puede incrementar indefinidamente sin que una variable bsica alcance el
valor 0. La direccin de no acotamiento para dicha variable no bsica xt es un vector
La variable xt puede aumentar su valor hasta xt mientras todas las variables bsicas
sigan siendo no negativas. As el mximo valor que puede tomar y en el que adems una
variable bsica se hace 0 y puede salir de la base es
b
xt = min i : yit > 0 (1.13)
it
1 i m y
2
Si existe ms de una relacin que alcance el valor mnimo al mismo tiempo usualmente se toma
aqul con mayor coeficiente en la columna pivote.
14 19/02/2010
MTODOS DE OPTIMIZACIN
z = z + c t xt (1.14)
xB = b y t xt (1.15)
contrario, se selecciona 3 como variable bsica entrante xt una variable con coste
3
La variable bsica entrante seleccionada es la de coste reducido negativo de mayor valor absoluto.
Sin embargo, esta opcin no considera el clculo de la relacin mnima (es decir, el incremento que se le
va a dar a dicha variable) luego la mejora en la funcin objetivo puede ser pequea. Tampoco tiene en
cuenta el efecto del escalado de las variables en el problema. En general, no existe manera prctica de
predecir qu eleccin de variable bsica entrante puede dar lugar al menor nmero de iteraciones.
19/02/2010 15
OPTIMIZACIN LINEAL
bs b
= min i : yit > 0
yst 1i m yit
yt = y2 = B a2 = 2
1
b2 y22 = 12 2 = 6 y b3 y32 = 18 2 = 9
x3
x
xB = x2 y xN = 1
x5 x4
1 1 1
Entonces B = 2 , B 1 = 1/ 2 y N = 1 . Los costes de la
2 1 1 1 3
variables bsicas son cBT = [ 5 ] y los de las no bsicas cTN = [ 3 ] .
16 19/02/2010
MTODOS DE OPTIMIZACIN
1
1 4 4
xB = b = B b = 1/ 2 12 = 6
1 1 18 6
y el valor de la funcin objetivo ser z = cBT B 1b = 30 .
Los coeficientes
1
wT = cBT B 1 = [ 5 ] 1/ 2 = [ 5 / 2 ]
1 1
1
c = c w N = [ 3 ] [ 5 / 2 ] 1 = [ 3 5 / 2] .
T
N
T
N
T
Elegimos x1 como la variable bsica entrante por ser la nica con un coste reducido
negativo. Calculamos los elementos de la columna pivote
1 1
1
yt = y1 = B a1 1
= 1/ 2 =
1 1 3 3
b1 y11 = 4 1 = 4 y b3 y31 = 6 3 = 2
x3
x
xB = x2 y xN = 5
x4
x1
19/02/2010 17
OPTIMIZACIN LINEAL
1/ 3
1 1
1
1 1/ 3
Entonces B = 2 , B = 1/ 2 y N = 1 . Los costes de la
2 3 1/ 3 1/ 3 1
variables bsicas son cBT = [ 5 3] y los de las no bsicas cTN = [ ] .
1
1 1/ 3 1/ 3 4 2
xB = b = B b = 1/ 2 12 = 6
1/ 3 1/ 3 18 2
y el valor de la funcin objetivo ser z = cBT B 1b = 36 .
Los coeficientes
1/ 3
1 1/ 3
wT = cBT B 1 = [ 5 3] 1/ 2 = [ 3 / 2 1]
1/ 3 1/ 3
y los costes reducidos
c = c w N = [ ] [ 3 / 2 1] 1 = [1 3 / 2]
T
N
T
N
T
Como todos los costes reducidos son positivos no se puede mejorar la funcin
objetivo, es decir, se ha alcanzado la solucin ptima.
18 19/02/2010
MTODOS DE OPTIMIZACIN
En tal caso, una solucin ser ptima si todos los costes reducidos son menores o
iguales que 0 y, en caso de que no sea as, la variable bsica entrante es la que tenga
coste reducido estrictamente positivo de mayor valor.
En algunos problemas no existe un nico ptimo, sino que puede haber varios. Esta
condicin es fcilmente detectable pues para que existan mltiples ptimos al finalizar
el algoritmo del simplex debe haber al menos una variable no bsica cuyo coste
reducido sea igual a 0, de modo que si la variable aumenta su valor la funcin objetivo
no se ve afectada, con lo que puede ser introducida en la base.
Sin embargo, no es una condicin suficiente que el coste reducido sea 0, hay que
asegurar tambin que cuando esta variable entra en la base lo hace con valor distinto de
0, pues en otro caso, si sustituye a una variable con valor 0, se produce un cambio de
base pero no de punto.
Una vez identificadas todas las soluciones bsicas factibles (puntos extremos)
ptimas, sern soluciones ptimas todas las combinaciones lineales convexas de stas.
Por ejemplo, si existen dos soluciones bsicas ptimas, todo el segmento que une los
puntos correspondientes son soluciones ptimas del problema.
19/02/2010 19
OPTIMIZACIN LINEAL
Las cotas superiores no se deben tratar como restricciones, esto tiene ventajas
computacionales. En el mtodo simplex las cotas superiores no se deben sobrepasar
cuando la variable bsica entrante se incrementa hasta alcanzar un nuevo vrtice.
no bsica.
4
La eliminacin gaussiana actualiza la tabla para que en ella aparezca un 1 en el elemento pivote y 0
en el resto de la columna. Para aplicarla seguir los siguientes pasos:
1. Dividir la fila pivote por el elemento pivote yst
2. Restar a las dems filas de la tabla la nueva fila pivote multiplicada por el elemento que se desea pase
a ser cero, es decir, el elemento correspondiente de la columna pivote.
Adems, se han de hacer 0 los coeficientes de la funcin objetivo correspondientes a las variables
bsicas.
20 19/02/2010
MTODOS DE OPTIMIZACIN
z 1 cTN cBT 0
xB 0 N B b
Tabla 2.1 Tabla (A) del simplex en la primera iteracin.
siendo cBT y cTN son los coeficientes de las variables bsicas y no bsicas actuales en la
funcin objetivo, B las columnas bajo las variables bsicas actuales de la matriz
original A y N las columnas de las variables no bsicas actuales de la matriz original
A . Su forma de interpretarla es la siguiente
z + cTN xN + cBT xB = 0
0 z + NxN + BxB = b
xB 0 B 1 N I B 1b
Tabla 2.2 Tabla (A) del simplex en una iteracin cualquiera.
z = cBT B 1b
xB = B 1b
19/02/2010 21
OPTIMIZACIN LINEAL
Si en la solucin inicial la base fuera una matriz identidad y los costes de las
variables bsicas fueran 0, la tabla original inicial sera la siguiente (por notacin se
designa con un apstrofo a lo que es inicial)
Cotas
Variables bsicas z xN xB
z 1 cNT 0 0
xB 0 N I b
Tabla 2.3 Tabla (B) del simplex en la primera iteracin partiendo de una matriz identidad.
xB 0 B 1 N B 1 B 1b
Tabla 2.4 Tabla (B) del simplex en una iteracin cualquiera.
Bajo las columnas de las variables bsicas originales inicialmente estaba la matriz
identidad I y ahora est la matriz inversa de la base B 1 . Luego esta matriz contiene
las manipulaciones hechas a las restricciones hasta una iteracin cualquiera. cNT son los
coeficientes de las variables no bsicas iniciales y cBT son los coeficientes de las
variables bsicas de cada iteracin.
Observando las tablas 2.1 y 2.2 se puede decir que el mtodo simplex persigue
hallar la particin adecuada entre variables bsicas y no bsicas que cumplen la
condicin de optimalidad cTN = cTN cBT B 1 N 0 . Observando las tablas 2.3 y 2.4
consistira en hallar los valores que cumplen la condicin de optimalidad del problema,
es decir, coeficientes de la funcin objetivo no negativos en el caso de minimizacin
cTN = cNT cBT B 1 N 0 y wT = cBT B 1 0 .
Veamos con un ejemplo las iteraciones del mtodo simplex en forma tabular. La
tabla inicial del problema anterior es:
22 19/02/2010
MTODOS DE OPTIMIZACIN
Variables bsicas
z x1 x2 x3 x4 x5 Cotas Relacin
z 1 3 5 0
x3 1 1 4
x4 2 1 12 12/2=6
x5 3 2 1 18 18/2=9
Se toma x2 como variable bsica entrante por tener el coste reducido negativo de
mayor valor absoluto. Luego su columna es la columna pivote.
Se toma x4 como variable bsica saliente por tener la menor relacin. Luego su fila
es la fila pivote.
z 1 3 5/2 30
x3 1 1 4 4/1=4
x2 1 1/2 6
x5 3 1 1 6 6/3=2
Se toma x1 como variable bsica entrante por tener el nico coste reducido negativo.
Luego su columna es la columna pivote.
Se toma x5 como variable bsica saliente por tener la menor relacin. Luego su fila
es la fila pivote.
19/02/2010 23
OPTIMIZACIN LINEAL
z 1 3/2 1 36
x3 1 1/3 1/3 2
x2 1 1/2 6
x1 1 1/3 1/3 2
min cT x
Ax = b ( P)
x0
Sin embargo, no siempre es fcil proporcionar una solucin bsica factible inicial.
Como se ha visto, la forma sencilla para hacerlo es partiendo de una matriz identidad en
los coeficientes de las variables bsicas iniciales.
a x
j
ij j bi aij x j + ui = bi
j
a x
j
ij j bi aij x j vi + wi = bi
j
24 19/02/2010
MTODOS DE OPTIMIZACIN
a x
j
ij j = bi aij x j + wi = bi
j
Con las variables de holgura y artificiales se parte de una matriz identidad para las
variables bsicas y el problema de optimizacin lineal a resolver es
min cT x
Ax + Ixa = b ( P(a))
x, xa 0
Obsrvese que en las hiptesis del mtodo simplex se ha supuesto que la matriz era
de rango mximo, sin embargo, esta hiptesis no se ha comprobado nunca. La razn es
que al partir de una matriz identidad de rango mximo la hiptesis necesariamente se
verifica. Sin embargo, si no se parte de una matriz identidad habra que comprobar que
se cumple esta condicin. Obsrvese tambin que aunque el problema original no la
cumpliera, al aadir las variables artificiales s lo har.
Para lograr anular las variables artificiales se emplean habitualmente dos mtodos:
el mtodo de la M mayscula
el mtodo de las dos fases
En el mtodo de las dos fases, la fase I del mtodo simplex tiene como funcin
objetivo la suma de las variables artificiales. Si esta fase I acaba con valor de la funcin
objetivo igual a cero entonces el problema original es factible y se dispone de una
19/02/2010 25
OPTIMIZACIN LINEAL
solucin bsica factible siendo no bsicas las variables artificiales. La fase II restablece
la funcin objetivo original y aplica de nuevo el mtodo simplex hasta alcanzar la
solucin ptima a partir de la solucin bsica factible del final de la fase I.
min z = xa
a
Ax + Ixa = b
x, xa 0
Sin embargo, todava es posible distinguir dos casos en esta situacin, antes de pasar
a la fase II:
26 19/02/2010
MTODOS DE OPTIMIZACIN
Fase II: Eliminar las variables artificiales del problema 5 y retomar la funcin
objetivo original, recalculando los costes reducidos para la solucin bsica factible
obtenida en la fase I.
min z = x4 + x6
0.3 x1 +0.1x2 + x3 = 2.7
0.5 x1 +0.5 x2 + x4 =6
0.6 x1 +0.4 x2 x5 + x6 =6
x1 , x2 , x3 , x4 , x5 , x6 0
5
En muchos casos no se eliminan estas variables, sino que se mantienen aunque no se cuente con
1
ellas para entrar en la base, ya que aportan informacin al final ( B , ...).
19/02/2010 27
OPTIMIZACIN LINEAL
Si esta fase acaba con la funcin objetivo con valor 0 significa que se ha encontrado
una solucin bsica factible inicial del problema original y se puede seguir con la fase
II. En caso contrario el problema es infactible.
x4 0.5 0.5 1 6
x6 0.6 0.4 1 1 6
x4 0.5 0.5 1 6 12
x6 0.6 0.4 1 1 6 10
x6 0.2 1 2 1 0.6 3
28 19/02/2010
MTODOS DE OPTIMIZACIN
x2 1 5 10 5 3
x3 1 1 0.6 1 0.3
x2 1 5 6 5 6
x3 1 1 0.6 1 0.3
x2 1 5 6 5 6
19/02/2010 29
OPTIMIZACIN LINEAL
1.4 0.5
z 1 0.5 5.4
x1 1 5 4 5 6
x2 1 5 6 5 6 1.2
A partir de ahora se ignoran los coeficientes de las variables artificiales para elegir
la variable bsica entrante para evitar que stas tomen valor positivo. Por tanto, se elige
x5 como variable bsica entrante y entonces x3 es la variable bsica saliente. Se hacen
0 los elementos de la columna pivote excepto el elemento pivote que se hace 1.
x5 1 1 0.6 1 0.3
x2 1 5 3 4.5
objetivo es z = 5.25 .
30 19/02/2010
MTODOS DE OPTIMIZACIN
xB Valores
wT = cBT B 1 z = cBT B 1b
B 1 b = B 1b
Tabla 2.5 Tabla (B) del simplex revisado en una iteracin cualquiera.
bs b
saliente ( = min i : yit > 0 ). El pivotamiento se hace sobre la tabla actual,
yst 1i m yit
suponiendo que existe una columna adicional (realmente no es aadida) que es la
columna pivote.
19/02/2010 31
OPTIMIZACIN LINEAL
Byt = at entonces
B = BF (1.16)
siendo
1
F = yt
1
B 1 = EB 1 (1.17)
donde
1 y1t yst
E = siendo = 1 yst .
1 ymt yst
32 19/02/2010
MTODOS DE OPTIMIZACIN
Bk1 = Ek 1 Ek 2 E2 E1 (1.18)
1 1
1 = 1 2 , E1 = 1 2 y B2 = E1 B1 = E1 = 1 2
1 1
1 1 1 1 1
el tercero, s = 3 . Luego
1 3 1 1 3 1 1 3 1 3
2 = , E2 = 1 1
y B3 = E2 E1 = 1 2
13 1 3 1 3 1 3
wT = cBT B 1 .
19/02/2010 33
OPTIMIZACIN LINEAL
1 1 a1 a1 1
Ea = s as = 0 + as s (1.21)
m
1 am am
m
1 1
1
cT E = ( c1 c2 cs cm )
s (1.22)
m 1
= ( c1 c2 cs 1 cT cs +1 cm )
34 19/02/2010
MTODOS DE OPTIMIZACIN
En cada iteracin del mtodo simplex se realiza el clculo de los costes reducidos de
las variables no bsicas, del valor de las variables bsicas y de la columna pivote en
funcin de la inversa de la base B 1
wT = cBT B 1
b = B 1b (1.23)
1
yt = B at
wT B = cBT
Bb = b (1.24)
Byt = at
B = LU (1.25)
19/02/2010 35
OPTIMIZACIN LINEAL
Bb = b
(1.26)
LUb = b
Lb1 = b (1.27)
y despus se resuelve este otro sistema triangular hacia atrs para calcular b
Ub = b1 (1.28)
En cada iteracin del mtodo simplex se actualiza la matriz base B mediante una
matriz elemental F
B = BF (1.29)
siendo
1
F = yt
1
B = LU (1.30)
36 19/02/2010
MTODOS DE OPTIMIZACIN
B = RT R (1.31)
Hasta ahora se supona que se calculaban los costes reducidos de todas las variables
no bsicas y se seleccionaba como variable bsica entrante a aqulla con coste reducido
de menor valor negativo. Existen otras estrategias de clculo de costes reducidos y de
seleccin de la variable bsica entrante (denominadas pricing strategies en ingls).
La primera gran divisin es calcular los costes reducidos de todas las variables no
bsicas (full pricing) o slo de algunas (partial pricing). En el primer caso, se hace
mayor esfuerzo computacional en cada iteracin y, en principio, menor nmero de
iteraciones del simplex. En el segundo, lo contrario.
19/02/2010 37
OPTIMIZACIN LINEAL
I.5. Dualidad
min z = cT x
Ax = b (P ) (1.32)
x 0
Supngase que se quiere calcular una cota inferior de la funcin objetivo de este
problema antes de resolverlo. Una forma de hacerlo sera operar con las filas de la
matriz, multiplicndolas por algn valor yT Ax = yTb y sumndolas entre ellas de
AT y c
38 19/02/2010
MTODOS DE OPTIMIZACIN
y tal que el resultado obtenido en el lado derecho al operar sea mximo. Este nuevo
problema planteado a raz del anterior se denomina problema dual (D )
max y 0 = bT y
(D ) (1.33)
AT y c
m
siendo y el vector de variables del problema dual o variable duales.
min 5x 1 3x 2 x 3 + 4x 4
x 1 2x 2 + 3x 3 + x 4 = 7
12x 1 9x 2 4x 3 4x 4 3
8x 1 5x 2 + 7x 3 + 9x 4 6
x 1 0, x 2 , x 3 libres, x 4 0
reagrupando trminos
cada uno de estos coeficientes de x 1 , x 2 , x 3 y x 4 debe tener una relacin con el del
problema original. Como x 1 0 para que la funcin objetivo del nuevo problema sea
menor su coeficiente ha de ser menor y1 + 12y2 + 8y 3 5 . Como x 4 0 su
coeficiente ha de ser mayor y1 4y2 + 9y 3 4 . Como x 2 es libre la relacin entre sus
coeficientes depender del valor que tome. Si x2 0 entonces
2y1 9y2 5y 3 3 . Si x 2 0 , 2y1 9y2 5y 3 3 . La nica forma de que
se puedan cumplir ambas a la vez es 2y1 9y2 5y 3 = 3 . Anlogamente para x 3 ,
3y1 4y2 + 7y 3 = 1 . Luego las restricciones que deben cumplir los pesos para que la
combinacin lineal sea cota inferior son
19/02/2010 39
OPTIMIZACIN LINEAL
y1 + 12y2 + 8y 3 5
2y1 9y2 5y 3 = 3
3y1 4y2 + 7y 3 = 1
y1 4y2 + 9y 3 4
Luego el problema, denominado dual, que obtiene la mayor cota inferior del
problema primal original es
40 19/02/2010
MTODOS DE OPTIMIZACIN
Primal (m n ) Dual (n m )
max z = cT x min y 0 = bT y
x y
Ax b AT y c
x 0 y0
n m
max z = c j x j min y 0 = biyi
xj yi
j =1 i =1
n m
a x ij j bi i = 1, , m a y
i =1
ij i c j j = 1, , n
j =1
x j 0 j = 1, , n yi 0 i = 1, , m
Primal Dual
max z = 3x 1 + 5x 2 min y 0 = 4y1 + 12y2 + 18y 3
x1 4 y1 +3y 3 3
2x 2 12 2y2 +2y 3 5
3x 1 +2x 2 18 y1, y2 , y3 0
x 1, x2 0
x 1 y
max z = 3 5 x 1
2 min y 0 = 4 12 18 y2
1 y 3
x 4
1
2 x 12
2 1 3 y1 3
3 2 18
2 2 y2 5
y
x 1 0 3
x 2 0 y 0
1
y 0
2
y 3 0
A continuacin se muestra la tabla completa (vista de izquierda a derecha o
viceversa segn sea el problema primal) que permite la transformacin de un problema
primal cualesquiera en su dual y viceversa.
19/02/2010 41
OPTIMIZACIN LINEAL
min max
Variable Restriccin
0
0
no restringida =
Restriccin Variable
0
0
= no restringida
Tabla 2.6 Tabla de conversin entre primal y dual.
A cada restriccin (variable) del primal le corresponde una variable (restriccin) del
dual. El tipo de restriccin (variable) del primal afecta al tipo de variable (restriccin)
del dual.
Como caso ejemplo general para observar la conversin entre primal y dual se
presenta el siguiente problema.
Existe un conjunto de propiedades bsicas de dualidad que ligan las soluciones del
primal y dual.
Propiedad de la simetra
Para cualquier problema primal y su dual, todas las relaciones entre ellos son
simtricas porque el dual de su dual es el primal.
42 19/02/2010
MTODOS DE OPTIMIZACIN
Si x es una solucin factible del primal e y es una solucin factible del dual, se
verifica que cT x bT y .
Si x es una solucin ptima del primal e y es una solucin ptima del dual, se
verifica que cT x = bT y .
En cada iteracin del mtodo simplex se encuentra una solucin bsica (vrtice)
factible del primal y una solucin bsica complementaria infactible del dual tal que
cT x = bT y o z = y 0 . Si x no es ptima para el primal y no es factible para el dual.
19/02/2010 43
OPTIMIZACIN LINEAL
Adems, esta solucin dual puede ser fcilmente identificada en la forma tabular del
simplex, corresponde a los coeficientes de las variables bsicas iniciales (variables de
holgura y artificiales) en la funcin objetivo. Para las variables de holgura, la solucin
dual complementaria puede ser vista en los costes reducidos de estas variables,
simplemente cambiando el signo. Si la variable fuera de exceso es todava ms directo,
ya que no habra que cambiar el signo. Slo en el caso de las restricciones donde no se
hayan introducido variables de holgura o exceso, es decir, restricciones de igualdad (o si
se hubieran eliminado las variables artificiales tras la fase I) no es posible ver el valor
de las variables duales asociadas a esas restricciones.
Variables bsicas
z x N x B Cotas
z 1 variables duales de variables duales cTB B 1b
exceso y de holgura originales
xB 0 B 1N B 1 B 1b
Propiedad de la complementariedad de holguras
Si una solucin ptima del primal tiene una variable de holgura o exceso > 0 en una
restriccin (es decir, es variable bsica > 0), la variable dual asociada a esa restriccin
tiene valor 0 y, de la misma forma, si una variable original del primal (no las de
holgura, exceso o artificiales) en el ptimo tiene valor > 0, su correspondiente
restriccin del dual no tiene holgura (es decir, su variable asociada del dual es 0). Por el
contrario, si una variable de holgura o exceso del primal es 0 en el ptimo, la variable
dual asociada a dicha restriccin puede tener un valor distinto de 0 (positivo o negativo
segn corresponda al tipo de restriccin y de funcin objetivo maximizacin o
minimizacin) en el ptimo del problema dual.
min z = cT x
Ax = b (P )
x 0
44 19/02/2010
MTODOS DE OPTIMIZACIN
max y 0 = bT y
(D )
AT y c
max y 0 = bT y
AT y + s = c
s0
x js j = 0 j = 1, , n (1.34)
primal y dual sean simultneamente diferentes de 0. Por otra parte, permite que ambos
sean 0.
Sean dos puntos factibles del problema primal y dual, es decir, que cumplen
Ax = b x 0
(1.35)
AT y + s = c s 0
Para las respectivas soluciones ptimas del problema primal y dual este intervalo de
dualidad es 0 segn la propiedad de la complementariedad de holguras.
Teorema de dualidad
19/02/2010 45
OPTIMIZACIN LINEAL
Otra forma de expresar estas mismas relaciones entre primal y dual es el lema de
Farkas. Sea el problema en su forma estndar
min cT x
Ax = b (1.37)
x 0
max z = 3x 1 + 5x 2
x1 4
2x 2 12 (P )
3x 1 +2x 2 18
x 1, x2 0
46 19/02/2010
MTODOS DE OPTIMIZACIN
min z = 3x 1 5x 2
x1 +x 3 =4
2x 2 +x 4 = 12
3x 1 +2x 2 +x 5 = 18
x 1, x 2, x 3, x 4, x5 0
Variables bsicas x1 x2 x3 x4 x5
z Cotas
z 1 3 5 0
x3 1 1 4
x4 2 1 12
x5 3 2 1 18
El problema dual en forma estndar, aunque sin aadir variables artificiales porque
no lo queremos resolver por el mtodo simplex tal como se ha explicado, y la tabla
inicial correspondiente son
Los valores de las variables del problema dual (variables duales) corresponden a los
coeficientes de las variables del problema primal en la funcin objetivo. Las variables
19/02/2010 47
OPTIMIZACIN LINEAL
originales del problema dual en las columnas correspondientes a las variables bsicas
iniciales del problema primal y las variables de exceso del problema dual en las
columnas de las variables no bsicas iniciales del primal. En cualquier iteracin,
excepto la ltima, del mtodo simplex aplicado al problema primal algn coste reducido
de las variables no bsicas toma valor negativo luego existe una variable dual negativa,
luego el problema dual para esa solucin bsica es infactible.
z 1 3/2 1 36
x3 1 1/3 1/3 2
x2 1 1/2 6
x1 1 1/3 1/3 2
ptima porque los costes reducidos de las variables no bsicas cTN = 3 / 2 1 son no
negativos. Las variables duales de este problema de minimizacin son
(y1, y2, y 3 ) = (0, 3 / 2, 1) , los costes reducidos de las variables bsicas originales
cambiados de signo. Las variables duales del problema original de maximizacin son
las opuestas (y1, y2 , y 3 ) = (0, 3 / 2,1) .
48 19/02/2010
MTODOS DE OPTIMIZACIN
max cT x = min bT y
o lo que es lo mismo,
n m
max c j x j = min biyi
j =1 i =1
Hay que tener precaucin con esta interpretacin pues todo tiene un lmite, es decir,
esto ser cierto mientras no cambie el valor de las variables duales, lo que se puede
19/02/2010 49
OPTIMIZACIN LINEAL
asegurar mientras la base actual sea ptima (ya que como hemos visto las variables
duales tienen la expresin yT = cTB B 1 , luego no dependen de b ). De ah que una
interpretacin completa de una solucin requiera tambin el anlisis de los lmites en
que puede darse esta interpretacin. El clculo de estos lmites corresponden a lo que se
denomina anlisis de sensibilidad que se presenta en la siguiente seccin.
+1 c1 : P1
P1 P1 : 1
+2 c2 : P2
P2 P2 : 2
+3 c3 : P3
P3 P3 : 3
0 1, 2 , 3 0
P1, P2 , P3 0
set i grupos de generacin / g1 * g3 /
parameter
cv(i) coste variable / g1 30, g2 50, g3 70 /
ptmx(i) potencia mxima / g1 200, g2 200, g3 100 /
equations
fo coste variable total
demanda cobertura de la demanda
prodmax(i) limitacin de la potencia producida ;
50 19/02/2010
MTODOS DE OPTIMIZACIN
S O L V E S U M M A R Y
GAMS/Cplex May 15, 2003 WIN.CP.CP 21.0 023.025.041.VIS For Cplex 8.1
Cplex 8.1.0, GAMS Link 23
g1 . 200.0000 +INF .
g2 . 100.0000 +INF .
g3 . . +INF 20.0000
parameter
cv(i) coste variable / g1 30, g2 50, g3 70 /
ptmx(i) potencia mxima / g1 200, g2 200, g3 100 /
equations
fo remuneracin total
prgrupo(i) limitacin del pago al grupo ;
19/02/2010 51
OPTIMIZACIN LINEAL
S O L V E S U M M A R Y
GAMS/Cplex May 15, 2003 WIN.CP.CP 21.0 023.025.041.VIS For Cplex 8.1
Cplex 8.1.0, GAMS Link 23
fo remuneracin total
LA precio marginal
g1 -INF -20.0000 . .
g2 -INF . . 100.0000
g3 -INF . . 100.0000
52 19/02/2010
MTODOS DE OPTIMIZACIN
Observando la tabla 2.8, tabla del simplex en cualquier iteracin, se advierte que las
columnas de la tabla bajo las variables bsicas iniciales x B no dependen de los
19/02/2010 53
OPTIMIZACIN LINEAL
2) preparacin para adecuarla a una iteracin del simplex (funcin objetivo con
coeficientes nulos en variables bsicas y matriz identidad en las columnas de
dichas variables)
5) nueva iteracin del mtodo simplex o del mtodo simplex dual (ste se ve en
un siguiente apartado)
max z = 3x 1 + 5x 2
x1 4
2x 2 12
3x 1 +2x 2 18
x 1, x2 0
positive variables x1, x2
54 19/02/2010
MTODOS DE OPTIMIZACIN
variable z
fo .. z =e= 3 * x1 + 5 * x2 ;
r1 .. x1 =l= 4 ;
r2 .. 2 * x2 =l= 12 ;
r3 .. 3 * x1 + 2 * x2 =l= 18 ;
caso.optfile= 1
S O L V E S U M M A R Y
GAMS/Cplex May 15, 2003 WIN.CP.CP 21.0 023.025.041.VIS For Cplex 8.1
Cplex 8.1.0, GAMS Link 23
19/02/2010 55
OPTIMIZACIN LINEAL
Observando la tabla 2.8 se ve que los cambios en las cotas de las restricciones slo
afectan al valor de la funcin objetivo y a los valores de las variables bsicas. Como
stos se pueden hacer negativos se puede perder factibilidad. En este caso, se aplica el
mtodo simplex dual que se ver ms adelante.
1 1/ 3 1/ 3
1
=
en la iteracin final era B 1/ 2 y las variables duales
1/ 3 1/ 3
yT = cTB B 1 = 3 / 2 1 .
56 19/02/2010
MTODOS DE OPTIMIZACIN
1 1/ 3 1/ 3 4 6
x B = b = B 1b
= 1/ 2
24 = 12 , que resulta ser infactible por tomar
1/ 3 1/ 3 18 2
un valor negativo.
z = z + z = z + yT b = 36 + 3 / 2 1 12 = 36 18 = 54
2 1 1/ 3 1/ 3 2 4 6
1
x B = x B + x B = x B + B b = 6 + 1/ 2 12 = 6 + 6 = 12
2 1/ 3 1/ 3 2 4 2
Es interesante determinar tambin el intervalo de valores para los que la solucin
bsica ptima se mantiene factible cambiando nicamente el valor de bi en el problema.
19/02/2010 57
OPTIMIZACIN LINEAL
58 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 59
OPTIMIZACIN LINEAL
Este mtodo, por lo tanto, se mueve por fuera de la regin factible, movindose por
vrtices exteriores (infactibles) con mejor valor de la funcin objetivo que el ptimo que
luego se alcanza y entra en la regin factible slo al alcanzar el ptimo.
1) Inicializacin
Se parte de una solucin bsica que cumpla el criterio de optimalidad (dual factible),
es decir, cuyos costes reducidos sean todos mayores o iguales que 0.
Si la solucin es factible (todas las variables bsicas tienen valor 0), la solucin
es ptima. En caso contrario, iterar.
2) Iteracin
Se suele elegir dentro de las negativas la mayor en valor absoluto, aunque esto
no garantiza una convergencia ms rpida.
60 19/02/2010
MTODOS DE OPTIMIZACIN
cj z j
min : y < 0
1 j n
sj
ysj
min 4x 1 + x 2
3x 1 + x 2 3
4x 1 + 3x 2 6
x 1 + 2x 2 4
x 1, x 2 0
Como las restricciones son de tipo habra que introducir muchas variables
artificiales y emplear el mtodo de las dos fases para solucionarlo. En su lugar, se
transforman las restricciones en tipo y se aplica el mtodo simplex dual.
min 4x 1 + x 2
3x 1 x 2 3
4x 1 3x 2 6
x 1 2x 2 4
x 1, x 2 0
19/02/2010 61
OPTIMIZACIN LINEAL
min 4x 1 + x 2
3x 1 x 2 + x 3 = 3
4x 1 3x 2 + x 4 = 6
x 1 2x 2 + x 5 = 4
x 1, x 2 , x 3 , x 4 , x 5 0
Variables Bsicas z x 1 x 2 x 3 x 4 x 5 Valores
Relacin 1 1/3
z 1 4 1
x3 3 1 1 3
x4 4 3 1 6
x5 1 2 1 4
Obsrvese cmo la tabla tiene las caractersticas necesarias para utilizar el simplex
dual: coeficientes de la funcin objetivo mayores o iguales que 0 (factibilidad del dual,
optimalidad del primal) y alguna cota de las restricciones negativa (no optimalidad del
dual, infactibilidad del primal).
Se elige x 4 como variable bsica saliente por tener el mayor coeficiente negativo en
la funcin objetivo del dual (mayor valor negativo de cota). sta define la fila pivote. Se
calcula la relacin entre los coeficientes de la funcin objetivo y los estrictamente
negativos de la fila pivote. Se elige como variable bsica entrante x 2 , aqulla con menor
relacin en valor absoluto, ser la primera que alcance valor 0 al incrementar x 4 . Se
realizan ahora las transformaciones sobre la tabla para prepararla para la eliminacin
gaussiana.
Variables Bsicas z x 1 x 2 x 3 x 4 x 5 Valores
Relacin 8/5 1
z 1 8/3 1/3 2
x3 5/3 1 1/3 1
x2 4/3 1 1/3 2
x5 5/3 2/3 1
Se elige x 3 como variable bsica saliente y x 4 como variable bsica entrante y se
hacen las transformaciones pertinentes.
Variables Bsicas x1 x 2 x 3 x 4 x 5 Valores
z 1 1 1 3
x4 5 3 1 3
x2 3 1 1 3
x5 5 2 1 2
62 19/02/2010
MTODOS DE OPTIMIZACIN
Veamos el problema dual del problema original y la tabla inicial del simplex para
este problema
19/02/2010 63
OPTIMIZACIN LINEAL
64 19/02/2010
MTODOS DE OPTIMIZACIN
4) Incrementar hasta anular las cotas de las restricciones (la solucin se hara
infactible). sta es la nueva variable bsica saliente en el simplex dual.
Obsrvese en este caso, que los diferentes valores del parmetro determinan
diferentes regiones factibles, as el espacio paramtrico es dividido en intervalos de
modo que en cada uno de ellos hay una base que es ptima (unas restricciones activas
que determinan el punto extremo ptimo). En este caso, el proceso de anlisis acaba con
un intervalo donde para cualquier valor del parmetro hay una base que es ptima o con
un intervalo del parmetro donde el problema resulta no factible.
19/02/2010 65
OPTIMIZACIN LINEAL
Los mtodos de punto interior requieren pocas iteraciones para resolver un problema
lineal. Sin embargo, estas iteraciones son muy costosas. Esencialmente cada iteracin
conlleva la resolucin de un sistema de ecuaciones lineales, como se ver ms adelante.
min z = cT x
Ax = b (P ) (1.38)
x 0
max y 0 = bT y
(D ) (1.39)
AT y c
mn m n n m
siendo A ,b ,c ,x ey .
max y 0 = bT y
AT y + s = c (D ) (1.40)
s0
m
siendo s .
66 19/02/2010
MTODOS DE OPTIMIZACIN
Sea x una solucin factible del problema primal (P ) y (y , s ) una solucin factible
del problema dual (D ) , no necesariamente bsicas. Sern ptimos en sus respectivos
problemas si cumplen la propiedad de la complementariedad de holguras
x js j = 0 j = 1, , n (1.41)
Ax = b
x 0
AT y + s = c (PD) (1.42)
s0
x js j = j
puntos estrictamente factibles. Este mismo avance se puede ver como una reduccin del
intervalo de dualidad (duality gap) hasta alcanzar el valor cero en la solucin ptima
cT x bT y = x T s = n (1.43)
6
Se define una solucin como estrictamente factible en el poliedro Ax = b , x 0 a aqulla que
verifica Ax = b y x > 0.
19/02/2010 67
OPTIMIZACIN LINEAL
A (x k + x k ) = b Ax k = 0
(1.44)
AT (y k + y k ) + s k + s k = c AT y k + s k = 0
x kj +1s kj +1 = (x kj + x kj )(s kj + s kj ) = k +1
(1.45)
s kj x kj + x kj s kj + x kj s kj = k +1 x kj s kj
s kj x kj + x kj s kj = k +1 x kj s kj (1.46)
( )
T
S = diag(s ) y e = 1 1 . Luego x = Xe , s = Se y, por consiguiente,
XSe = e (1.47)
De forma completa, una iteracin cualquiera del mtodo primal-dual resuelve este
sistema de (m + 2n ) ecuaciones lineales
S x + X s = e XSe
Ax = 0 (1.48)
AT y + s = 0
68 19/02/2010
MTODOS DE OPTIMIZACIN
S x XAT y = e XSe
(1.49)
Ax = 0
s = AT y
(1.52)
x = S 1v() D s
19/02/2010 69
OPTIMIZACIN LINEAL
de la holgura. Para garantizar la estricta factibilidad hay que limitar los movimientos de
las variables de forma que stas permanezcan dentro de sus cotas
x (P , ) = x + P x
y(D , ) = y + D y (1.53)
s(D , ) = s + D s
donde P = min x j x j
x j <0
( )y D (
= min s j s j
s j <0
) son las longitudes del paso que
aseguran x > 0 y s > 0 . Obsrvese que el parmetro D es nico para y k y s k . Una
estrategia habitual es tomar una longitud de paso nica = min(P , D )
x j + x j 0
y j + y j 0 (1.54)
s j + s j 0
(x k , s k ) C k (1.55)
70 19/02/2010
MTODOS DE OPTIMIZACIN
A (x k + x k ) = b Ax k = b Ax k rP
(1.56)
AT (y k + y k ) + s k + s k = c AT y k + s k = c (AT y k + s k ) rD
o bien
S x + X s = e XSe v()
Ax = b Ax rP (1.57)
AT y + s = c AT y s rD
S x + X s = e XSe X Se v()
Ax = b Ax rP (1.59)
AT y + s = c AT y s rD
19/02/2010 71
OPTIMIZACIN LINEAL
Los mtodos de punto interior no producen soluciones bsicas ptimas. Por ello
cuando llegan al ptimo se suele realizar un proceso de permutacin (crossover) para
determinar la solucin bsica ptima.
min z = x 1 + x 2 min z = x 1 + x 2
2x 1 + x 2 2 2x 1 + x 2 + x 3 = 2
x 1 + 2x 2 6 x 1 + 2x 2 + x 4 = 6
x 1 + 2x 2 10 o expresado en forma estndar x 1 + 2x 2 + x 5 = 10
x 1 + 2x 2 5 x 1 2x 2 + x 6 = 5
x1 x 2 4 x1 x 2 + x 7 = 4
x 1, x 2 0 x 1, x 2 , x 3 , x 4 , x 5 , x 6 , x 7 0
72 19/02/2010
MTODOS DE OPTIMIZACIN
2x 1 + x 2 + x 3 = 2
x 1 + 2x 2 + x 4 = 6
x 1 + 2x 2 + x 5 = 10
x 1 2x 2 + x 6 = 5
x1 x 2 + x 7 = 4
2y1 y2 + y 3 y 4 + y5 + s1 = 1
y1 + 2y2 + 2y 3 2y 4 y5 + s2 = 1
y1 + s 3 = 0
y2 + s 4 = 0
y 3 + s5 = 0
y 4 + s6 = 0
y5 + s7 = 0
x 1s1 = 0
x 2s2 = 0
x 3s 3 = 0
x 4y 4 = 0
x 5s5 = 0
x 6s6 = 0
x 7s7 = 0
x 1, x 2 , x 3 , x 4 , x 5 , x 6 , x 7 0
s1, s2 , s 3 , s 4 , s5 , s6 , s7 0
max z = 3x 1 + 5x 2 min 3x 1 5x 2
x1 4 x1 +x 3 =4
2x 2 12 o bien 2x 2 +x 4 = 12
3x 1 +2x 2 18 3x 1 +2x 2 +x 5 = 18
x 1, x 2 0 x 1, x 2 , x 3 , x 4 , x 5 0
19/02/2010 73
OPTIMIZACIN LINEAL
I.10. Referencias
Bazaraa, M.S. and Jarvis, J.J. (1998) Programacin Lineal y Flujo en Redes. Limusa.
Gill, P.E., Murray, W. and Wright, M.H. (1991) Numerical Linear Algebra and
Optimization. Addison Wesley.
Nash. S.G. and Sofer. A. (1996) Linear and Nonlinear Programming. McGraw-Hill.
Ros Insa, S., Ros Insa, D., Mateos, A. y Martn, J. (1997) Programacin lineal y
aplicaciones. Ejercicios resueltos Ed. Ra-Ma.
74 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 1
min x 1 + x 2 3x 3
3x 1 x 3 = 5
x2 x 3 = 1
x 1, x 2 , x 3 0
Se pide:
3
4) Comprobar que la base B = est asociada a una solucin no acotada.
1
PROBLEMA 2
19/02/2010 75
OPTIMIZACIN LINEAL
max 3x + 2y
4x + y 16
x + 4y 16
5x + 6y 30
x, y 0
max 3y + 8z
y + 2z = 4
z 3
y, z 0
max 3x + 2y
5x + y 0
y x 0
4.
min 3x + 5y 4z + 6t
x + 2z t = 6
y + 4z + t = 9
2z 2t = 3
x , y, z, t 0
5.
min x 1 + 2x 2 3x 3
x1 + x 2 + x 3 = 6
x 1 + x 2 + 2x 3 = 4
2x 2 + 3x 3 = 10
x3 2
x 1, x 2 , x 3 0
76 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 3
1.
min 3x 1 + 2x 2 x 3
x1 + x 2 x 3 5
x 1 x 2 + 7x 3 4
x 1, x 2 0
x 3 libre
2.
max 3x 1 + 4x 2
x1 x 2 7
x1 + x 2 3
x 1, x 2 libres
3.
max x 1 + x 2 + x 3
x1 x 2 5
x1 + x 3 = 8
x 1, x 2 0
PROBLEMA 4
min x 1 + x 2 + x 3 + x 4
2x 1 x 2 + x 3 = 4
(i)
x 1 + 2x 3 x 4 = 3
x 1, x 2 , x 3 0
19/02/2010 77
OPTIMIZACIN LINEAL
max x 1 + 2x 2 + 3x 3
x 1 x 2 + 2x 3 5
(ii)
x1 x 3 = 3
x 1, x 2 , x 3 0
Se pide:
PROBLEMA 5
min x 1 + x 2 + x 3 + x 4
2x 1 x 2 + x 3 = 4
x 1 + 2x 3 x 4 = 3
x 1, x 2 , x 3 0
4 3
3) Idem al cambiar el vector b = por b =
3 1
1
4) Aadir x 5 con coste c5 = 3 y a 5 =
1
PROBLEMA 6
Dado el problema
78 19/02/2010
MTODOS DE OPTIMIZACIN
donde
c1 3 3
c = 2 + 2 [0, ]
2
c
3 1 1
PROBLEMA 7
min 3x 1 + 2x 2 + 4x 3
3x 1 + 2x 2 x 3 5
x1 + x 3 = 3
x 1, x 2 , x 3 0
Se pide:
1) La solucin ptima.
PROBLEMA 8
19/02/2010 79
OPTIMIZACIN LINEAL
PROBLEMA 9
max 2x 1 x 2 17x 3
5x 1 2x 2 + 31x 3 1
3x 1 x 2 + 19x 3 0
x 1, x 2 , x 3 0
Se pide:
PROBLEMA 10
max 2x 1 + x 2 + 0.5x 3
2x 1 + x 2 + 2x 3 2
x1 x 2 x 3 1
x 1, x 2 , x 3 0
80 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 11
max 4x + 2y
x +y 5
2x + y 7
x 3
x, y 0
x y s1 s2 s 3
z 0 0 0 2 0 14
s1 0 0 1 1 1 1
y 0 1 0 1 2 1
x 1 0 0 0 1 3
Se pide:
1) Resolverlo grficamente.
b1 = 4 .
19/02/2010 81
OPTIMIZACIN LINEAL
PROBLEMA 12
max z = 2x 1 + 2x 2
x1 + x 2 3
x 1 + 2x 2 4
x 1, x 2 0
Se pide:
1) Resolverlo grficamente.
5) Obtener los precios duales de los dos recursos. Cul es su significado? cul
es el sentido de su signo?
PROBLEMA 13
En una fbrica se producen dos tipos de artculos. La semana siguiente se estima que
han de producirse al menos 50 artculos en total. Para producirlos se usan dos tipos de
materia prima, cuyo coste unitario es de 100 y 200 , respectivamente. El problema que
82 19/02/2010
MTODOS DE OPTIMIZACIN
se plantea para maximizar los beneficios de la empresa y su tabla ptima son los
siguientes:
x y s1 s2 s3
z 0 0 0 200 0 16000
x 1 0 2 1 0 20
y 0 1 1 1 0 30
s3 0 0 1 0 1 10
PROBLEMA 14
19/02/2010 83
OPTIMIZACIN LINEAL
max 2x + y
x +y 2
x + 4y 16
3x + y 15
x, y 0
PROBLEMA 15
En una fbrica se producen dos productos, P1 y P2, cuyos beneficios unitarios son
20 y 70, respectivamente. En la produccin se utilizan dos materias primas, disponiendo
de 30 y 60 unidades cada una. La demanda total es de al menos 20 productos y ha de ser
satisfecha. El planteamiento del problema es:
2) Dar los valores e interpretacin de las variables originales, las de holgura, las
artificiales (si existen), las duales, de los costes reducidos y de la funcin
objetivo, si la tabla ptima fuera
x y s1 s2 s3
z 0 0 25 0 5 650
y 0 1 1/2 0 1/2 5
s2 0 0 1 1 1 10
x 1 0 1/2 0 3/2 15
84 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 16
min 3x 1 + 5x 2 + 7x 3
x 1 + x 2 + x 3 300
x 1 200
x 2 200
x 3 100
x 1, x 2 , x 3 0
Se pide:
PROBLEMA 17
19/02/2010 85
OPTIMIZACIN LINEAL
min 4x 1 + x 2
3x 1 + x 2 3
4x 1 + 3x 2 6
x 1 + 2x 2 4
x 1, x 2 0
Se pide:
PROBLEMA 18
min x + y + z
x +y 1
2x + z = 3
PROBLEMA 19
n
donde x , c1, c2 , , cp y d1, d2 , , d p
min f (x )
Ax = b
x =0
PROBLEMA 20
86 19/02/2010
MTODOS DE OPTIMIZACIN
que tras agrupar trminos en cada restriccin, aadir dos variables de holgura ( s2 y s 3
en la segunda y tercera restriccin, respectivamente) y resolver (aadiendo una variable
artificial en la primera restriccin, a1 ), proporciona la siguiente tabla ptima
x1 x2 x3 x4 x5 s2 s3 a1 Cotas
s2 0 0 0 0 0 1 1 0.1 9
19/02/2010 87
OPTIMIZACIN LINEAL
PROBLEMA 21
Tren 10 15 18
10
Camin 20 6
88 19/02/2010
MTODOS DE OPTIMIZACIN
del que se adjunta la ltima tabla del mtodo simplex de la que se deduce la solucin
ptima:
x1 x2 x3 x4 x5 Cotas
2) Por otro lado existe la posibilidad de adquirir 200 tornillos con un precio
unitario incrementado sobre el precio normal de adquisicin 0.05 . Merece
la pena adquirirlos? Se adquiriran los 200 tornillos si el citado incremento
fuera tan slo de 0.02 ? Por qu?
19/02/2010 89
OPTIMIZACIN LINEAL
3) Parece que una de las razones por las que los juguetes han perdido atractivo
es que son un poco pobres de ornamentacin. Cabe la posibilidad de
aadirles algunas ventanillas como adornos: los trenes necesitan 7 ventanillas
por unidad y los camiones 4. El artesano puede adquirir para la prxima
semana un mximo de 2100 ventanillas. Cmo afecta esta incidencia a la
produccin ptima de juguetes?
PROBLEMA 22
El ingeniero del ICAI Antn Pirulero Artesano, conocido por APA entre sus
compaeros de promocin, se dedica al ejercicio libre de la profesin, orientndose a
actividades comerciales. En la lnea que le ha hecho famoso como empresario-riesgo, se
dispone a participar en la feria agro-alimentaria de Vladivostock presentando una
coleccin de tres tipos de piruletas de su invencin. Estas piruletas son: A: piruletas de
naranja, B: piruletas de limn, C: piruletas de ans. Las piruletas tienen una base comn
de azcar y miel, en las cantidades que se indican en la siguiente tabla. Con la venta de
las piruletas tiene previsto cubrir en parte los gastos de participacin en la feria. Por
razones de limitacin en el peso autorizado, a la feria slo puede llevar 220 kg de azcar
y 90 kg de miel y quiere vender al menos 20000 piruletas.
90 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 91
OPTIMIZACIN LINEAL
PROBLEMA 23
PROBLEMA 24
Dado el problema
max 4x + y
s.a. 2x + y 9
4x 3y 8
x, y 0
Se pide:
92 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 25
Una empresa produce una determinada bebida a partir de dos ingredientes bsicos.
El proceso de elaboracin de la bebida puede llevarse a cabo de dos formas distintas.
Para producir un litro de la bebida, de la forma 1 requerir 1 litro del primer ingrediente
y 2 del segundo, mientras que de la forma 2 requerir 2 litros del primer ingrediente y 1
del segundo. El proveedor habitual le puede suministrar hasta 900 litros de cada
ingrediente a un coste de 3 por litro el primero de ellos, y de 5 por litro el segundo.
La empresa plantea el siguiente problema para determinar cmo debe ser su produccin
de la prxima semana para satisfacer una demanda de 500 litros de la bebida con el
menor coste posible:
x y s1 s 2 s 3
z 0 0 15 2 0 5700
y 0 1 1 1 0 400
s3 0 0 3 1 1 300
x 1 0 2 1 0 100
Se pide responder a las siguientes cuestiones, independientemente unas de otras, y
razonando y calculando a partir de la tabla ptima:
1) Qu precio mnimo debera pedir para cubrir costes por cada litro ms que
se le solicite de la bebida? Si la demanda se mantiene pero puede acceder a
otro proveedor distinto del habitual aunque ms caro para que le suministre
los ingredientes, qu precio mximo debera pagar por cada litro de los dos
ingredientes?
19/02/2010 93
OPTIMIZACIN LINEAL
2) Cunto podra variar el coste del ingrediente 1 sin que cambie la solucin
actual?
PROBLEMA 26
X Y Z
N1 0.5 0.6 0.5
N2 0.4 0.2 0.5
Un kilo de X produce un beneficio de 5.9 , uno de Y 4 y uno de Z 7 . Un
contrato con un cliente obliga a fabricar al menos 300 kilos de X .
max G = 5.9X + 4Y + 7Z
0.5X + 0.6Y + 0.5Z 1050
0.4X + 0.2Y + 0.5Z 650
X 300
G X Y Z H1 H2 E3 Cotas
G 1 0 0 0 3 11 0 10300
Y 0 0 1 0 2.5 2.5 0.25 925
Z 0 0 0 1 1 3 0.7 690
X 0 1 0 0 0 0 1 300
1) Hay ms soluciones al problema? Si as fuera, cul es la estructura general
de todas ellas?
94 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 27
Un trapero se dedica a recoger tres tipos de artculos, X1, X2 y X3, que transporta en
un vehculo que puede acarrear hasta 300 kg de peso y un volumen mximo de 480
unidades de volumen. Las caractersticas de peso, volumen y beneficio generado por
cada unidad de esos artculos vienen dadas en la tabla siguiente.
maxW = 7X1 + 6X 2 + 4X 3
2X1 + X 2 + 3X 3 300
3X1 + 2X 2 + X 3 480
Xi 0
X1 X2 X3 H1 H2 Cotas
W 2.2 0 0 0.4 2.8 1464
X2 1.4 1 0 0.2 0.6 228
X3 0.2 0 1 0.4 0.2 24
19/02/2010 95
OPTIMIZACIN LINEAL
4) El trapero muestra inters por un cuarto artculo X4 que pesa 2.5 kg, ocupa 2
unidades de volumen y proporciona un beneficio unitario de 5 . Le interesa
recoger unidades de este artculo?
1/ 3 1/ 3
, y 3 = B 1a 3 =
B 1 = 1 es un vector con todos sus componentes <
1
0 y el coste reducido de x 3 es menor que 0, c3 = 5 / 3 .
4) (x , y, z , t ) = (12 / 5, 0,21/10, 3 / 5)
96 19/02/2010
MTODOS DE OPTIMIZACIN
5) (x 1, x 2 , x 3 ) = (2,2,2)
1)
2)
3)
ii.c) Obvias.
19/02/2010 97
OPTIMIZACIN LINEAL
2) (x 1, x 2 , x 3 , x 4 ) = (7 / 3,2 / 3, 0, -2 / 3)
3) (x 1, x 2 , x 3 , x 4 ) = (3 / 2, 0, 0,1/ 2)
4) Solucin no acotada.
0 1 (x 1, x 2 , x 3 ) = (0, 9 / 2, 4) z = -13 + 13
1 (x 1, x 2 , x 3 ) = (6, 0,1) z = 17 - 17
1) (x 1, x 2 , x 3 ) = (2, 0,1)
2) 04 (x 1, x 2 , x 3 ) = (2 + 5 / 4, 0,1 - 1/ 4) 4
(x 1, x 2 , x 3 ) = (3 + , 0, 0)
1) x = (0, 0.5, 0)
2) x = (0, 0.5, 0)
3) x = (0, 0, 0)
98 19/02/2010
MTODOS DE OPTIMIZACIN
1) x1 = 1 , x 2 = 0 , x 3 = 0
2) w1 = 1 , w 2 = 0
min 5w1 + 7w 2 + 3w 3
w1 + 2w 2 + w 3 4
2)
w1 + w 2 2
w 1, w 2 , w 3 0
3) (w1, w2 , w 3 ) = (0,2, 0)
6) (x , y ) = (3, 0)
4) w1 = 2 , w 2 = 0
5) (x 1, x 2 ) = (0,2)
19/02/2010 99
OPTIMIZACIN LINEAL
d) (w1, w 2 , w 3 ) = (0,200, 0)
f) (x , y ) = (50,10) , z = 14000
1) (x , y ) = (4, 3) , z = 11
2) (x , y ) = (4, 0) , z = 8
Se puede concluir que son los porcentajes de la Al1 (37.5) y de la Al5 (62.5) sea
cul sea la cantidad a producir.
1 0.375 0.375
1
4) B 0.4 0.7 = 0 , 30 (30 0 25) 0 = 3.125
0.6 0.4 0.625 0.625
100 19/02/2010
MTODOS DE OPTIMIZACIN
x1 x2 x3 x4 x 5 s2 s3 s4 Cotas
cj z j 0 14.0625 37.5 25.9375 0 0 6.25 0 2531.25
x5 0 0.1875 0.5 0.8125 1 0 1.25 0 56.25
s2 0 0 0 0 0 1 1 0 9
x1 1 0.8125 0.5 0.1875 0 0 1.25 0 33.75
s4 1 0 0 0 0 0 0 1 30
Reorganizando (a la ltima restar la penltima solamente):
x1 x2 x3 x4 x 5 s2 s3 s4 Cotas
cj z j 0 14.0625 37.5 25.9375 0 0 6.25 0 2531.25
x5 0 0.1875 0.5 0.8125 1 0 1.25 0 56.25
s2 0 0 0 0 0 1 1 0 9
x1 1 0.8125 0.5 0.1875 0 0 1.25 0 33.75
s4 0 0.8125 0.5 0.1875 0 0 1.25 1 3.75
Aplicando el dual entra la tercera de holgura y sale la cuarta
x1 x2 x3 x4 x 5 s2 s 3 s4 Cotas
cj z j 0 10 35 25 0 0 0 5 2550
x5 0 1 1 1 1 0 0 1 60
s2 0 0.65 0.4 0.15 0 1 0 0.8 6
x1 1 0 0 0 0 0 0 1 30
s4 0 0.65 0.4 0.15 0 0 1 0.8 3
1)
x1 x 2 x3 x4 x 5 Cotas
cj z j 0 0 0.115 0.01 0 860
x5 0 0 0.45 1.5 1 900
x2 0 1 0.075 0.05 0 300
x1 1 0 0.05 0.1 0 200
Cambia la solucin actual:
19/02/2010 101
OPTIMIZACIN LINEAL
x1 x2 x3 x 4 x 5 Cotas
c j z j 0.1 0 0.11 0 0 880
x5 15 0 0.3 0 1 3900
x2 0.5 1 0.05 0 0 400
x4 10 0 0.5 1 0 2000
x1 x 2 x3 x4 x 5 x 6 Cotas
cj z j 0 0 0.025 0.09 0 0 740
x5 0 0 0.45 1.5 1 0 900
x2 0 1 0.075 0.05 0 0 300
x1 1 0 0.05 0.1 0 0 200
x6 0 0 0.05 0.5 0 1 500
Resultando la siguiente tabla ptima:
x1 x 2 x3 x4 x5 x6 Cotas
cj z j 0 0 0.034 0 0 0.18 650
x5 0 0 0.3 0 1 3 2400
x2 0 1 0.07 0 0 0.1 350
x1 1 0 0.04 0 0 0.2 100
x4 0 0 0.1 1 0 2 1000
102 19/02/2010
MTODOS DE OPTIMIZACIN
8
5. El coste reducido sera: 1.1 (0.025 0.09 0) 12 = 0.18 . No interesa.
3
2)
19/02/2010 103
OPTIMIZACIN LINEAL
A 10000
15000
B = 0 + (1 ) 10000 [0,1]
C 5000 0
3) Ninguna de las soluciones cumple la nueva restriccin, as que hay que aadir
B 12000 , es decir, B Exceso4 = 12000 . Sera:
Reorganizando:
Exceso 4
A B C Holgura 1 Holgura 2 Exceso 3
cj z j 0 0 0 0 0.03 0.03 0 2100
Holgura 1 0 2 0 1 1 6 0 10000
C 0 0.5 1 0 0.5 2 0 5000
A 1 0.5 0 0 0.5 3 0 15000
Exceso 4 0 1 0 0 0 0 1 12000
Exceso 4
A B C Holgura 1 Holgura 2 Exceso 3
cj z j 0 0 0 0 0.03 0.03 0 2100
Holgura 1 0 2 0 1 1 6 2 34000
C 0 0 1 0 0.5 2 0.5 1000
A 1 0 0 0 0.5 3 0.5 9000
B 0 1 0 0 0 0 1 12000
Dual no acotado, primal no factible.
104 19/02/2010
MTODOS DE OPTIMIZACIN
Reorganizando
4)
cj = c j z j = c j cTB B 1a j = c j yT a j =
= 0.22 (0 0.15 0.09)(2 2 1)T = Interesa.
= 0.22 (0 0.03 0.03)(12 8 1)T = 0.01
1 1 6 12 2
B a j = 0
1
0.5 2 8 = 2
0 0.5 3 1 1
19/02/2010 105
OPTIMIZACIN LINEAL
2 1
b) B 1 =
3 1
x1 x 2 x 3 x 4 x 5
0 0 1 1 3 81
x1 1 0 2 2 1 6
x2 0 1 1 3 1 3
Aadir x 1 2x 2 1 6 2 3 = 0 < 1 x 1 2x 2 x 6 = 1
0 0 1 1 3 0 81
x 1 1 0 2 2 1 0 6
x 2 0 1 1 3 1 0 3
x 6 1 2 0 0 0 1 1
106 19/02/2010
MTODOS DE OPTIMIZACIN
Organizando:
0 0 1 1 3 0 81
x 1 1 0 2 2 1 0 6
x 2 0 1 1 3 1 0 3
x 6 0 0 4 8 3 1 1
Dual:
a)
X Y S1 S2 X Y S1 S2 X Y S1 S2
Z 4 1 0 0 0 Z 0 4 0 1 8 Z 0 0 8/5 1/5 16
S1 2 1 1 0 9 S1 0 5/2 1 1/2 5 Y 0 1 2/5 1/5 2
S2 4 3 0 1 8 X 1 3/4 0 1/4 2 X 1 0 3/10 1/10 7/2
cx > 4 / 3
0 (2 / 5 + cx 3 /10) < 0
b) cx > 2
0 (1/ 5 + cx 1/10) < 0 cx > 2
min 9w + 8t
2w + 4t 4
c) Dual: Valor variables duales en el ptimo: w = 8 / 5 t = 1/ 5
w 3t 1
w, t 0
2 1 18 + 2inc1 8
9 + inc1 10 + 2inc1 0
5
B b = 5
1
= 5
0 inc1 5
3 1 8 27 + 3inc1 + 8 35 + 3inc1 0
10 10 10
18 8 inc2
2 / 5 1/ 5
9 5 10 inc2 0 inc2 35
1
B b = =
0
3 /10 1/10 8 + inc2 27 + 8 + inc2 35 + inc2 0 inc2 10
10
19/02/2010 107
OPTIMIZACIN LINEAL
x y S1 S2 S3 x y S1 S2 S3 x y S1 S2 S3
Z 0 0 8/5 1/5 0 16 Z 0 0 8/5 1/5 0 16 Z 0 0 1 0 2 15
Y 0 1 2/5 1/5 0 2 Y 0 1 2/5 1/5 0 2 Y 0 1 1 0 2 3
X 1 0 3/10 1/10 0 7/2 X 1 0 3/10 1/10 0 7/2 X 1 0 0 0 10 3
S3 1 0 0 0 1 3 S3 0 0 3/10 1/10 1 1/2 S2 0 0 3 1 10 5
Solucin nodo: (3,4) Z=15, entera podar y Z = 15 . No podar otros, seguir nodo 0
x y S1 S2 S3 x y S1 S2 S3
Z 0 0 8/5 1/5 0 16 Z 0 0 8/5 1/5 0 16
Y 0 1 2/5 1/5 0 2 Y 0 1 2/5 1/5 0 2
X 1 0 3/10 1/10 0 7/2 X 1 0 3/10 1/10 0 7/2
S3 1 0 0 0 1 4 S3 0 0 3/10 1/10 1 1/2
No factible, podar. Todos los nodos explorados, la solucin ptima es (3,3), Z=15.
max G = 5.9X + 4Y + 7Z
0.5X + 0.6Y + 0.5Z 1050
0.4X + 0.2Y + 0.5Z 650
X 300
G X Y Z H1 H2 E3 Cotas
G 1 0 0 0 3 11 0 10300
Y 0 0 1 0 2.5 2.5 0.25 925
Z 0 0 0 1 1 3 0.7 690
X 0 1 0 0 0 0 1 300
1) S, nueva tabla:
G X Y Z H1 H2 E3 Cotas
G 1 0 0 0 3 11 0 10300
108 19/02/2010
MTODOS DE OPTIMIZACIN
X Y Z H1 H2 E3 E4 Cotas X Y Z H1 H2 E3 E4 Cotas
G 0 0 0 3 11 0 0 10300 0 0 0 3 11 0 0 10300
Y 0 1 0 2.5 2.5 0.25 0 925 0 1 0 2.5 2.5 0.25 0 925
Z 0 0 1 1 3 0.7 0 690 0 0 1 1 3 0.7 0 690
X 1 0 0 0 0 1 0 300 1 0 0 0 0 1 0 300
E4 0 1 0 0 0 0 1 1000 0 0 0 2.5 2.5 0.25 1 75
X Y Z H1 H2 E3 E4 Cotas
G 0 0 0 14 0 1.1 4.4 9970
Y 0 1 0 0 0 0 1 1000
Z 0 0 1 2 0 1 1.2 600
X 1 0 0 0 0 1 0 300
H2 0 0 0 1 1 0.1 0.4 30
4) Interesa:
19/02/2010 109
OPTIMIZACIN LINEAL
No hay ms soluciones, cualquiera en que una variable no bsica pase a tener valor
positivo tendr un valor estrictamente menor de la funcin objetivo que el actual, ya que
todos los costes reducidos son distintos de 0.
X1 X2 X3 H1 H2 H3 Cotas
W 2.2 0 0 0.4 2.8 0 1464
X2 1.4 1 0 0.2 0.6 0 228
X3 0.2 0 1 0.4 0.2 0 24
H3 1 1 1 0 0 1 200
X1 X2 X3 H1 H2 H3 Cotas
W 2.2 0 0 0.4 2.8 0 1464
X2 1.4 1 0 0.2 0.6 0 228
X3 0.2 0 1 0.4 0.2 0 24
H3 0.6 0 0 0.2 0.4 1 52
X1 X2 X3 H1 H2 H3 Cotas
W 1 0 0 0 2 2 1360
X2 2 1 0 0 1 1 280
X3 1 0 1 0 1 2 80
H1 3 0 0 1 2 5 260
110 19/02/2010
MTODOS DE OPTIMIZACIN
X1 X2 X3 H1 H2 H3 Cotas
W 0 0 1 0 1 4 1280
X2 0 1 2 0 1 3 120
X1 1 0 1 0 1 2 80
H1 0 0 3 1 1 1 20
2.5
( )
Calculamos su coste reducido: c4 z 4 = 5 0.4 2.8 = 5 6.6 = 1.6 . No le
2
interesa
19/02/2010 111
MTODOS DE OPTIMIZACIN
max x 2
Heurstico
x 1 + x 2 0.5
x 1 + x 2 3.5 ptimo IP
x 1, x 2 0 xi Z x1
7
Se entiende por problema relajado el problema original pero sin las condiciones de integralidad de
las variables.
19/02/2010 113
OPTIMIZACIN LINEAL ENTERA MIXTA
x2
max x 1 + 5x 2 ptimoLP
ptimo IP
x 1 + 10x 2 20
Heurstico
x1 2
x 1, x 2 0 xi Z
x1
114 19/02/2010
MTODOS DE OPTIMIZACIN
Eliminar es podar la rama (o nodo) del rbol si la cota indica que no puede contener
la solucin ptima.
a x
j =1
ij j bi i = 1, , m
xj 0 j = 1, , n
xj Z j = 1, , I I n
19/02/2010 115
OPTIMIZACIN LINEAL ENTERA MIXTA
RAMIFICACIN
Seleccionar uno de los nodos (por ejemplo, el creado ms recientemente 8) entre los
no explorados (subproblemas restantes).
Seleccionar una variable entera que tenga valor no entero en la solucin ptima del
subproblema relajado. Un criterio de seleccin es elegir la primera en el orden
natural 9. Si xj es el valor ptimo en el problema relajado, entonces se ramifica en
dos ramas, donde cada una incorpora una de estas restricciones respectivamente
x j xj
, siendo xj parte entera de xj .
x x + 1
j j
La ramificacin aade una restriccin, luego el problema ser resuelto por anlisis
de sensibilidad mediante el mtodo simplex dual. El problema primal de la nueva
rama resulta infactible, cada rama elimina la solucin ptima del subproblema
ascendiente. El problema dual es factible pero no ptimo.
ACOTAMIENTO
8
Ms adelante se vern otros criterios ms elaborados.
9
Este criterio tambin puede ser ms elaborado.
116 19/02/2010
MTODOS DE OPTIMIZACIN
PODA
Se intentan podar nodos y, por tanto, eliminar ramas que saldran de ellos, con los
siguientes criterios de poda para un problema de maximizacin:
- z > z , es decir, es mejor que la mejor solucin entera encontrada hasta este
momento z , con lo que sta ser la nueva solucin entera, actualizando z = z .
3) Criterio de optimalidad
19/02/2010 117
OPTIMIZACIN LINEAL ENTERA MIXTA
max z = 4x 1 2x 2 + 7x 3 x 4
x1 +5x 3 10
x1 +x 2 x 3 1
6x 1 5x 2 0
x 1 +2x 3 2x 4 3
xj 0 j = 1, , 4
xj Z j = 1, , 3
Se ramifica con la primera variable que debiera ser entera y no lo es, x 1 . Cada rama
corresponde a aadir las restricciones x 1 1 (nodo 1) y x 1 2 (nodo 2),
respectivamente. Se resuelve el nodo 1 y se obtiene z = 14.2 y
(x 1, x 2 , x 3 , x 4 ) = (1,1.2,1.8, 0) . Luego cualquier solucin ptima descendiente de este
nodo cumplir z 14.2 . El nodo 2 resulta infactible luego esa rama queda podada.
Partiendo del nodo 1 se ramifica con la primera variable que debiera ser entera y no
lo es, x 2 , de manera que el nodo 3 tiene las restricciones originales ms x 1 1 y
x 2 1 y en el nodo 4 se aaden x 1 1 y x 2 2 . Resolviendo el nodo 3 se obtiene
Se selecciona ramificar el nodo 3 por tener la mayor funcin objetivo (ser el nodo
ms prometedor, aunque tambin este criterio puede ser modificado) y se ramifica con
la variable x 1 . En el nodo 5 se habrn aadido las restricciones x 1 1 , x 2 1 y
x 1 0 y su resultado es z = 13.5 y (x 1, x 2 , x 3, x 4 ) = (0, 0,2, 0.5) . Resulta la primera
solucin entera factible del problema MIP, con valor de la funcin objetivo z = 13.5 .
Una vez obtenida una solucin entera se intentan podar las ramas no exploradas y se
observa que el nodo 4 puede ser descartado porque su funcin objetivo es menor (en
maximizacin) que la solucin entera actual.
118 19/02/2010
MTODOS DE OPTIMIZACIN
z=14.25
(1.25,1.5,1.75,0)
x1 1 x1 2
1
2
z=14.2
INFACTIBLE
x2 1 (1,1.2,1.8,0) x2 2
3 4
z=14.16 z=12.16
x1 0 (0.83,1,1.83,0) x1 1 (0.83,2,1.83,0)
5
6
z=13.5
INFACTIBLE
(0,0,2,0.5)
z = 13.5
19/02/2010 119
OPTIMIZACIN LINEAL ENTERA MIXTA
Tambin se puede modificar (relajar) el criterio de parada del mtodo para evitar
explorar exhaustivamente el rbol. Es fundamental en la solucin de problemas reales
ya que puede marcar la diferencia entre acabar un problema, con una solucin
cuasiptima dentro de una cierta tolerancia conocida, o no solucionar el problema. Para
ello se aade en el criterio de poda una cierta tolerancia relativa o absoluta que descarta
una solucin no entera slo ligeramente mejor que la solucin entera actual, es decir,
poco prometedora. El criterio para maximizacin descarta las ramas con funcin
objetivo z que cumplen siendo el error de tolerancia relativo (por ejemplo 103 ) o
z z z + siendo el error de tolerancia absoluto, ambas constantes conocidas.
120 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 121
OPTIMIZACIN LINEAL ENTERA MIXTA
1) Elegir un nodo (en el inicio es el nodo raz que es el problema original relajado).
122 19/02/2010
MTODOS DE OPTIMIZACIN
problemas de gran tamao. Entre ellos cabe destacar: el preproceso automtico, tanto
para problemas continuos como enteros. Como se ha visto en la resolucin, una buena
formulacin de un problema puede ser de vital importancia a la hora de resolverlo. Una
medida de la bondad de una formulacin en programacin entera que se suele utilizar es
la diferencia entre el ptimo del problema relajado y el ptimo entero (habitualmente se
utiliza el trmino anglosajn gap). Un valor pequeo de esta diferencia, suele implicar
un tiempo de resolucin reducido, que a la postre es lo que se desea.
La idea bsica es detectar la redundancia por medio de las cotas de las variables. En
el proceso tambin se pueden fijar algunas variables a sus cotas y detectar infactibilidad.
19/02/2010 123
OPTIMIZACIN LINEAL ENTERA MIXTA
Por ejemplo, para restricciones de se igualan a su cota superior las variables con
coeficientes positivos y a la inferior las dems. Las siguientes restricciones son
redundantes para variables con valores entre 0 y 1
3x1 + 2 x2 6
3x1 2 x2 3
3x1 2 x2 3
Reforzamiento de cotas
Reduccin eucldea
Asignacin de variables
Consiste en identificar variables que pueden fijarse a una de sus cotas ya que los
dems valores no pueden dar una solucin factible y ptima.
Si un valor de una variable no puede satisfacer una restriccin, aun cuando las
dems variables tomen sus valores ms favorables para intentar cumplirla, la variable
debe fijarse al valor opuesto.
124 19/02/2010
MTODOS DE OPTIMIZACIN
La idea bsica es que si una variable slo va en contra de la funcin objetivo y de las
restricciones puede ser fijada a su cota inferior. Si es justo al revs, puede ser fijada a su
cota superior.
3 x1 2
3 x1 + x2 2 x1 = 1
5 x1 + x2 2 x3 2
x1 + x2 2 x3 1 x3 = 0
3x1 + x2 3 x3 2 x1 = 1, x3 = 0
3x1 2 x2 1 x1 = 0, x2 = 1
3x1 + x2 2 x3 2 x1 = 1
x1 + x4 + x5 1 x4 = 0, x5 = 0
x5 + x6 0 x6 = 0
19/02/2010 125
OPTIMIZACIN LINEAL ENTERA MIXTA
Estas tcnicas son especficas para problemas enteros y, en particular, con variables
binarias. Dos formulaciones de un problema entero se dicen 0-1 equivalentes si tienen
las mismas soluciones enteras. Dadas dos formulaciones equivalentes de un problema
entero, se dice que una es ms fuerte que la otra, si la regin factible de su relajacin
lineal est estrictamente contenida en la regin factible de la otra. En la formulacin
ms fuerte el intervalo de integralidad (integrality gap), es decir, la diferencia entre la
funcin objetivo de la solucin entera y la del problema relajado linealmente es menor.
La formulacin ms fuerte ideal es aqulla cuyo intervalo de integralidad es nulo, es
decir, cuya solucin entera se puede obtener resolviendo un problema lineal. Sin
embargo, formulaciones fuertes pueden requerir un nmero exponencial de
restricciones.
El objetivo es reducir la regin factible del problema lineal sin eliminar soluciones
factibles del problema BIP, variando los coeficientes de las restricciones.
126 19/02/2010
MTODOS DE OPTIMIZACIN
a j = aj y el de la cota b = b
6) Ir a 1.
Con esta nueva restriccin se puede ver que el conjunto de puntos enteros factibles
no ha cambiado, pero s la regin factible del problema relajado.
x2
x1
x1 + x 2 = 1 2x 1 + 3x 2 = 4
19/02/2010 127
OPTIMIZACIN LINEAL ENTERA MIXTA
1) Considerar cualquier restriccin con variables binarias de tipo con todos los
coeficientes no negativos (restriccin mochila).
planos de corte x1 + x2 + x4 2 , y x 1 + x 3 1 .
128 19/02/2010
MTODOS DE OPTIMIZACIN
Otro tipo de planos de corte que se estudiaron fueron planos de corte en problemas
de flujo con coste fijo, que ahora son utilizados en programacin entera mixta.
En general, los cuatro tipos ms utilizados (no especficos) son cortes GUB, cliques,
cubrimientos (covers) y flujos (flow covers). Adems se estn retomando los planos de
corte de Gomory. Todos estos planos pueden ser utilizados en el preproceso, o en los
nodos del rbol de enumeracin cuando se desarrolla la tcnica de ramificacin y corte.
II.6. Referencias
Nemhauser, G.L., Wolsey, L.A. (1988) Integer and Combinatorial Optimization. John
Wiley and Sons.
PROBLEMA 1
19/02/2010 129
OPTIMIZACIN LINEAL ENTERA MIXTA
1.
max 3x 1 + 2x 2
2x 1 + 2x 2 9
3x 1 + 3x 2 18
x 1, x 2 0 enteras
2.
max 2x 1 + 3x 2
5x 1 + 7x 2 35
4x 1 + 9x 2 36
x 1, x 2 0 enteras
3.
max x 1 + x 2
2x 1 + 5x 2 16
6x 1 + 5x 2 27
x 1, x 2 0 enteras
4.
min 5x 1 + 4x 2
3x 1 + 2x 2 5
2x 1 + 3x 2 7
x 1, x 2 0, x 2
5.
max 5x 1 + 7x 2
2x 1 + x 2 13
5x 1 + 9x 2 41
x 1, x 2 0, x 2
130 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 2
max x 1 + 2x 2 + 5x 3
x 1 + 10x 2 3x 3 15
2.
2x 1 + x 2 + x 3 10
x 1, x 2x 3 0
PROBLEMA 3
max 3x 1 + 2x 2 + 2x 3 + 2x 4
3x 1 + x 2 + 2x 3 + x 4 5
x 1 + 2x 2 + 2x 3 + x 4 3
x 1, x 2 , x 3 , x 4 {0,1}
2) Obtener para cada desigualdad los cubrimientos minimales y los planos de corte
obtenidos con ellos. Reforzar los cortes obtenidos.
PROBLEMA 4
19/02/2010 131
OPTIMIZACIN LINEAL ENTERA MIXTA
(0,1,0.75,0.2)
z=17
X1=0
X1=1 X2=0
(1,0.25,0.25,0.25)
z=15 (1,1,0,0.75)
z=19
X3=0
X2=1
(1,1,0.25,0)
z=16
X3=1
No factible
PROBLEMA 5
132 19/02/2010
MTODOS DE OPTIMIZACIN
1) No factible
4) z * = 10.5 , x * = (0.5,2)
1) z * = 40 , x * = (1,1,1, 0, 0)
2) z * = 50 , x * = (0, 0,10) , * = 1
1) x 1 = 1 , x 2 = 5 , objetivo 5
3) x1 + x 2 + x 3 2 , x1 + x 3 + x 4 2
5) x 2 + x 3 1 , x1 + x 2 + x 4 2 , x1 + x 3 + x 4 2
6) x1 + x 2 + x 4 2
19/02/2010 133
OPTIMIZACIN LINEAL ENTERA MIXTA
z=19: se poda ya que aunque no es entera, es peor que la mejor encontrada hasta el
momento (minimizacin)
La mejor solucin por el momento es z=18, pero podra llegar a ser 17 explorando el
nodo que an queda activo.
134 19/02/2010
MTODOS DE OPTIMIZACIN
min f (x )
x
(1.60)
gi (x ) bi i = 1, , m
n n n
donde x , f (x ) : y gi (x ) : . Ntese que, en este caso, la no
negatividad de las variables no forma parte de la formulacin general. Aunque la
funcin objetivo puede ser de maximizacin o minimizacin, en lo que sigue, cuando se
hable de un problema de programacin no lineal se supondr, sin prdida de
generalidad, que es un problema de minimizacin.
19/02/2010 135
OPTIMIZACIN NO LINEAL
Optimizacin no restringida
min f (x ) (1.61)
x
Para este tipo de problemas en la siguiente seccin se vern cules son las
condiciones que ha de cumplir un punto para que sea ptimo y algunos algoritmos de
bsqueda para encontrar tal punto, diferenciando entre problemas de una variable
(unidimensionales) o de ms variables (multidimensionales) y entre algoritmos que usan
diferenciacin y otros que no.
Son problemas donde todas las restricciones son lineales, aunque la funcin objetivo
no lo es
min f (x )
x (1.62)
Ax = b
En este caso, el problema se simplifica bastante y existe una extensin del algoritmo
simplex para resolverlo adems de algunos casos particulares, como el del problema
cuadrtico, con algoritmos particulares muy eficientes.
Programacin cuadrtica
Son problemas donde las restricciones son lineales, pero la funcin objetivo es
cuadrtica, es decir, que incluye algn trmino con el cuadrado de alguna variable o con
el producto de dos variables
1 T
min f (x ) = x Qx bT x
x 2 (1.63)
Ax = b
136 19/02/2010
MTODOS DE OPTIMIZACIN
Se han desarrollado muchos algoritmos para este tipo de problemas, algunos con la
hiptesis adicional de que f (x ) sea convexa (cncava para el caso de maximizacin).
Programacin convexa
La programacin convexa engloba una amplia clase de problemas, entre los que se
encuentran los casos anteriores cuando las funciones son convexas. Sus hiptesis son:
f (x ) es convexa (cncava si es maximizacin) y gi (x ) es convexa, i = 1, , m .
En tal caso, adems, se puede asegurar que todo ptimo local es tambin global.
Programacin separable
Una funcin separable es una funcin en la que cada trmino incluye una sola
variable, por lo que la funcin se puede separar en una suma de funciones de las
variables individuales
n
f (x ) = fj (x j ) (1.64)
j =1
Programacin no convexa
19/02/2010 137
OPTIMIZACIN NO LINEAL
Programacin geomtrica
donde
a a a
Pj (x ) = x 1 j 1 x 2 j 2 ...x n jn , j = 1,..., n (1.66)
Programacin fraccional
f1(x )
f (x ) = (1.67)
f2 (x )
138 19/02/2010
MTODOS DE OPTIMIZACIN
1 T 2
f (x * + p) = f (x * ) + f (x * )T p + p f ( )p (1.68)
2
n
donde x n
, p es un vector diferente de 0, es un punto entre x y x * , f (x )
2 f
hessiana, tal que hij = (x * ) . sta es una matriz simtrica por tener f segundas
x i x j
derivadas continuas.
1 T
f (x ) = x Qx bT x
2
n n nn
donde x ,b yQ .
f (x ) = Qx b
y el hessiano
2 f (x ) = Q
Si tenemos la funcin
1 2 1
f (x 1, x 2 ) = x 1 + 2x 1x 2 + x 22 x 2 + 9 ,
2 2
el gradiente es
19/02/2010 139
OPTIMIZACIN NO LINEAL
f
x 1 x 1 + 2x 2
f (x 1, x 2 ) = =
f 2x 1 + x 2 1
x 2
y el hessiano
2 f 2 f
x 12 x 1x 2 1 2
f (x 1, x 2 ) = 2
2
=
f 2 f 2 1
x 2x 1 x 22
0.1 1 1 2
0.1
( )
f (1.1, 0.9) = 9 + 1 0 + 0.1 0.1
0.1 2
( )
0.1 = 8.93
2 1
min f (x ) (1.69)
x
En primer lugar se ven las condiciones necesarias y suficientes para que un punto
sea mnimo local y para que lo sea global, bajo ciertas hiptesis. A continuacin se ven
diferentes algoritmos iterativos de clculo de dicho mnimo.
140 19/02/2010
MTODOS DE OPTIMIZACIN
n
Sea f : diferenciable en x * ; si x * es un mnimo local 10 entonces
f (x * ) = 0 (1.70)
Sin embargo, cualquier punto que satisfaga esta condicin es un punto estacionario,
no necesariamente un mnimo.
x 1 + 2x 2
Ejemplo: f (x 1, x 2 ) = = 0 luego (x 1, x 2 ) = (2 3, 1 3)
2x 1 + x 2 1
n
Sea f : dos veces diferenciable en x * ; si x * es un mnimo local entonces
f (x * ) = 0 y H f (x * ) es semidefinida positiva.
[0,1]
f (u + (1 ) v ) f (u ) + (1 ) f (v )
10
Mnimo local es un punto x * n
que satisface la condicin f (x * ) f (x ) para todo x tal que
x x * < siendo un nmero positivo (tpicamente pequeo) cuyo valor puede depender de x * . Si
19/02/2010 141
OPTIMIZACIN NO LINEAL
f (u + (1 ) v ) f (u ) + (1 ) f (v )
Una funcin convexa (cncava) en [a, b ] tiene un valor mnimo (mximo) en dicho
intervalo.
Si una matriz tiene autovalores tanto positivos como negativos se dice que es
indefinida.
2 1
Ejemplo: 2 f (x 1, x 2 ) = es una matriz semidefinida positiva ya que sus
1 2
2 1
determinantes son positivos 2 = 2 0 y = 3 0 . Sin embargo, la matriz
1 2
1 2
hessiana del ejemplo anterior, 2 f (x 1, x 2 ) = , no lo es ya que el determinante de
2 1
n
Sea f : dos veces diferenciable en x * ; si f (x * ) = 0 y H f (x * ) es
142 19/02/2010
MTODOS DE OPTIMIZACIN
n
Sea f : convexa y diferenciable en x * (si es dos veces diferenciable el
Sea el problema
min f (x )
x
(1.71)
x [a, b ]
19/02/2010 143
OPTIMIZACIN NO LINEAL
k = ak + (1 )I k
k = ak + I k
Mtodo de Newton
144 19/02/2010
MTODOS DE OPTIMIZACIN
1
q(x k +1 ) = f (x k ) + f (x k )(x k +1 x k ) + f (x k )(x k +1 x k )2 (1.72)
2
f (x k )
q (x k +1 ) = 0 x k +1 = x k (1.73)
f (x k )
Sea el problema
min f (x ) (1.74)
x
n
siendo f una funcin convexa y x .
Tambin ahora, la clasificacin de los algoritmos iterativos se hace igual que antes
por algoritmos sin diferenciabilidad y algoritmos que utilizan diferenciacin. Existen
varios mtodos que no requieren diferenciabilidad: mtodo de Rosenbrock o de las
coordenadas cclicas, mtodo de Hooke y Jeeves (con paso continuo o paso discreto),
mtodo de Nelder y Mead, etc. De los cuales se presenta el primero. Existen varios
mtodos que requieren diferenciabilidad para minimizar funciones de varias variables.
Se pueden clasificar en:
- Aquellos que slo utilizan derivadas primeras: mtodo del mximo descenso y
mtodo del gradiente conjugado
19/02/2010 145
OPTIMIZACIN NO LINEAL
Los mtodos que utilizan derivadas son procedimientos iterativos con un mecanismo
de actualizacin del punto del tipo
x k +1 = x k + k pk (1.75)
min F () f (x k + k pk ) (1.76)
k >0
Por ejemplo, se define k como una secuencia 1, , , 1/8, etc. Se van utilizando
los valores de la secuencia empezando por 1. Si para = 1 se satisface la condicin
anterior, si no se utiliza el valor siguiente.
146 19/02/2010
MTODOS DE OPTIMIZACIN
pT f (x k )
>0
p f (x k )
p m f (x k )
pk = f ( xk ) (1.77)
19/02/2010 147
OPTIMIZACIN NO LINEAL
Se puede interpretar como un caso particular del mtodo de Newton (que se ver a
continuacin) cuando el hessiano se sustituye por la matriz identidad.
1 T
min f ( x) = x Qx bT x
x 2
1 1
donde Q = 5 y b = 1
25 1
f ( xk )T pk
k = (1.78)
pkT 2 f ( xk ) pk
148 19/02/2010
MTODOS DE OPTIMIZACIN
0 1
Supongamos un punto inicial x0 = 0 . Para ese punto f ( x0 ) = 0 , f ( x0 ) = 1 y si
0 1
se utiliza la norma 2 del gradiente como medida de la convergencia
0.097
La nueva estimacin de la solucin es x1 = x0 + 0 p0 = 0.097 . Para este punto
0.097
0.903
f ( x1 ) = 0.145 , f ( x1 ) = 0.516 y su norma 2 f ( x1 ) = 1.76 . El valor de
1.419
1 = 0.059 .
0.150
La nueva estimacin de la solucin es x2 = 0.127 . Para este punto
0.013
0.850
f ( x2 ) = 0.237 , f ( x2 ) = 0.364 y su norma 2 f ( x2 ) = 1.14 .
0.673
La convergencia del mtodo del mximo descenso para una funcin cuadrtica con
bsqueda unidimensional exacta es lineal. La relacin de mejora entre dos iteraciones
consecutivas se puede acotar superiormente de esta manera
2
f ( xk +1 ) f ( x* ) cond(Q) 1
(1.79)
f ( xk ) f ( x* ) cond(Q) + 1
19/02/2010 149
OPTIMIZACIN NO LINEAL
Mtodo de Newton
1
q( xk +1 ) = f ( xk ) + f ( xk )T ( xk +1 xk ) + ( xk +1 xk )T 2 f ( xk )( xk +1 xk ) (1.80)
2
1
q( xk +1 ) = 0 xk +1 = xk 2 f ( xk ) f ( xk ) (1.81)
2 f ( xk ) pk = f ( xk ) (1.82)
150 19/02/2010
MTODOS DE OPTIMIZACIN
Mtodo de cuasi-Newton
Bk pk = f ( xk ) (1.83)
xk +1 = xk + k pk (1.84)
sk = xk +1 xk
(1.85)
yk = f ( xk +1 ) f ( xk )
19/02/2010 151
OPTIMIZACIN NO LINEAL
2 f ( xk +1 )( xk +1 xk ) f ( xk +1 ) f ( xk )
Bk +1 ( xk +1 xk ) f ( xk +1 ) f ( xk ) (1.86)
Bk +1sk = yk
Bk +1 = Bk + actualizacin (1.87)
( B s )( Bk sk )
T
yk ykT
Bk +1 = Bk k k + (1.88)
skT Bk sk ykT sk
( B s )( Bk sk )
T
yk ykT
Bk +1 = Bk k k + T + ( skT Bk sk )uk ukT (1.89)
skT Bk sk y k sk
yk Bs
donde uk = T
Tk k
yk sk sk Bk sk
debe cumplir ykT sk > 0 condicin que se debe garantizar controlando la bsqueda
unidimensional.
152 19/02/2010
MTODOS DE OPTIMIZACIN
directamente la solucin ptima del problema entre los puntos que son soluciones del
sistema de ecuaciones que se plantea y, a continuacin, algoritmos de bsqueda como
alternativa al procedimiento anterior.
min f ( x)
x (1.90)
Ax = b
mn
donde x n
, A y b m
.
L( x, ) = f ( x) + T ( Ax b) (1.91)
donde m
se denominan multiplicadores o multiplicadores de Lagrange. El
mnimo del lagrangiano es el mnimo del problema ( P) puesto que en el ptimo
Ax = b .
x L( x, ) = f ( x) + AT
(1.92)
L( x, ) = Ax b
L ( x * , * ) = 0 (1.93)
f ( x* ) = AT * (1.94)
19/02/2010 153
OPTIMIZACIN NO LINEAL
min f ( x)
x
gi ( x) 0 i = 1,..., m
(1.95)
h j ( x) = 0 j = 1,..., l
x X
donde m
, l
son los multiplicadores de Lagrange. Esta funcin es siempre
una cota inferior de f ( x) para valores factibles de x y valores conocidos de 0 (no
negativos) y (libre). Por consiguiente, interesa obtener la mayor cota inferior
max L( x, , ) y el problema original ( P) ser
0
min max L( x, , )
0 (1.97)
x
x X
154 19/02/2010
MTODOS DE OPTIMIZACIN
Estas condiciones estn basadas en unas previas, denominadas de Fritz John pero
menos tiles para resolver problemas. Fueron enunciadas por Karush en su tesis de
mster y publicadas en ruso, pero el hecho de que fueran presentadas en este idioma
dificult su expansin y, unos aos despus, Kuhn y Tucker (Kuhn, 1951) las
enunciaron y demostraron de nuevo (sin conocer el estudio previo en ruso), por lo que
durante mucho tiempo se conocieron como las condiciones de Kuhn-Tucker, hasta que
posteriormente se incluy a la primera persona que realmente las public.
Sea el problema ( P)
min f ( x)
x
gi ( x) 0 i = 1,..., m (1.98)
x X
f ( x* ) + i gi ( x* ) = 0
iI (1.99)
i 0 i I
19/02/2010 155
OPTIMIZACIN NO LINEAL
m
f ( x* ) + i gi ( x* ) = 0
i =1
i gi ( x ) = 0 i = 1,..., m
*
(1.100)
i 0 i = 1,..., m
Veamos un ejemplo
min f ( x, y ) = 9 y ( x 5) 2
x, y
x2 + y 0
x y 0
x 1 0
2( x 5) 2 x1 2 + 3 = 0
9 + 1 2 = 0
1 ( x 2 + y ) = 0
2 ( x y ) = 0
3 ( x 1) = 0
1 , 2 , 3 0
adems se deben considerar todas las restricciones del problema puesto que el punto ha
de ser factible.
2 x + 10 9 + 3 = 0
3 ( x 1) = 0
Ahora se tiene:
o Si 3 = 0 , entonces x = 1 2 e y = 1 2 . Entonces A = (1 2, 1 2) y
A = ( 0,9, 0 ) .
156 19/02/2010
MTODOS DE OPTIMIZACIN
posibilidades
o x = 0 , que implica y = 0 y al resolver se tiene C = (0, 0) y
C = (1,10, 0)
o x = 1 , que implica y = 1 y al resolver se tiene D = (1, 1) y
D = ( 3, 6, 0 )
As, el punto D no es un punto que cumpla las condiciones de KKT (los
multiplicadores no son mayores o iguales que 0). Los otros tres puntos las cumplen,
pero grficamente se puede observar que B y C son mnimos locales (ambos con valor
25 de la funcin objetivo), A no es nada y no existe mnimo global. De hecho, la
funcin no est acotada.
Si se hubiera deseado tambin buscar los mximos locales, basta buscar puntos con
las mismas condiciones pero en que todos los multiplicadores sean menores o iguales
que 0 y se habra obtenido el punto E = (1,1) con E = (9, 0, 26) que es un mximo
local.
f ( x* ) + i gi ( x* ) = 0
iI (1.101)
i 0 i I
19/02/2010 157
OPTIMIZACIN NO LINEAL
Sea el problema ( P)
min f ( x)
x
gi ( x) 0 i = 1,..., m
(1.102)
h j ( x) = 0 j = 1,..., l
x X
l
f ( x* ) + i g i ( x* ) + j h j ( x* ) = 0
iI j =1 (1.103)
i 0 i I
m l
f ( x* ) + i gi ( x* ) + j h j ( x* ) = 0
i =1 j =1
i gi ( x ) = 0 i = 1,..., m
*
(1.104)
i 0 i = 1,..., m
158 19/02/2010
MTODOS DE OPTIMIZACIN
que
l
f ( x* ) + i gi ( x* ) + j h j ( x* ) = 0
iI j =1 (1.105)
i 0 i I
x=x+p (1.106)
n r
Si Z es una matriz (siendo r n m ) del espacio nulo de A (espacio definido
por el conjunto de vectores ortogonales a las filas de A , representa el conjunto de
direcciones factibles de las restricciones) la regin factible tambin se puede expresar
como
x = x + Zv (1.107)
donde v r
.
19/02/2010 159
OPTIMIZACIN NO LINEAL
(v ) = Z T f ( x ) (1.109)
El hessiano reducido de f en x es
2 (v) = Z T 2 f ( x) Z (1.110)
p
Ap = ( B N ) B = BpB + NpN = 0
pN
p B 1 N
p= B = pN
pN I
B 1 N
Z = (1.111)
I
B 1b B 1 N
x = x + p = x + ZpN = + pN
0 I
mn mm m n m n n m
donde A , B , N , Z
2) Factorizacin QR
AT = QR
Q = ( Q1 Q2 )
AQ = RT
AQ1 = R1T
AQ2 = 0
mn n n m n n n m n n m n m
donde A , Z , Q , Q1 , Q2 , R y
mm
R1 (es una submatriz triangular superior de R )
160 19/02/2010
MTODOS DE OPTIMIZACIN
Z = Q2 (1.112)
Z T f ( x * ) = 0 (1.113)
p T 2 f ( x* ) p 0 (1.114)
Z T f ( x * ) = 0 (1.115)
Veamos un ejemplo
2 x1 2 2
f ( x) = 2 x2 , f ( x) = 2
2
2 x + 4 2
3
2.5 1 2
Sea el punto x = 1.5 y la matriz de transformacin Z = 1 . Entonces el
*
1 1
nuevo punto y el valor de la funcin a minimizar queda
19/02/2010 161
OPTIMIZACIN NO LINEAL
v1 , v2
+ ( 1.5 + v1 ) ( 1 + v2 ) + 4 ( 1 + v2 )
2 2
3
1 1
Z f ( x ) =
T *
3 =
2 1 6
2 1 2 1 2
1 1 2 2 4 4
Z f ( x )Z =
T 2 *
2 1 = 1 =
2 1 4 2 4 6
2 1 1
min f ( x)
x (1.116)
Ax b
mn
donde x n
, A y b m
.
f ( x* ) = AT *
(1.117)
*T ( Ax* b) = 0
o equivalentemente
162 19/02/2010
MTODOS DE OPTIMIZACIN
Z T f ( x* ) = 0
(1.118)
*T ( Ax* b) = 0
Las condiciones suficientes para que sea un mnimo local estricto son
Z T f ( x* ) = 0
(1.119)
*T ( Ax* b) = 0
Sea el problema ( P)
min f ( x)
x
(1.120)
gi ( x) = 0 i = 1, , m
donde x n
y gi : n
. El lagrangiano de este problema es
L ( x, ) = f ( x ) + T g ( x ) (1.121)
Z ( x* )T f ( x* ) = 0 (1.122)
Las condiciones suficientes de primer y segundo orden para mnimo local estricto
Z ( x* )T f ( x* ) = 0 (1.123)
19/02/2010 163
OPTIMIZACIN NO LINEAL
Sea el problema ( P)
min f ( x)
x
(1.124)
gi ( x) 0 i = 1, , m
donde x n
y gi : n
. El lagrangiano de este problema es
L ( x, ) = f ( x ) + T g ( x ) (1.125)
x L ( x* , * ) = 0
(1.126)
*T g ( x* ) = 0
o equivalentemente
Z ( x* )T f ( x* ) = 0
(1.127)
*T g ( x* ) = 0
Z ( x* )T f ( x* ) = 0
(1.128)
*T g ( x* ) = 0
164 19/02/2010
MTODOS DE OPTIMIZACIN
Veamos un ejemplo
min f ( x) = x1
( x1 + 1) 2 + x22 1
x12 + x22 2
1 21 ( x1 + 1) + 22 x1
x L ( x, ) =
21 x2 + 22 x2
2(1 + 2 )
2xx L( x, ) =
2(1 + 2 )
0
a) Probar si x = es ptimo.
0
1 21 0
x L ( x, ) = =
0 0
Luego 1 = 0.5
0
Si se toma Z = como la matriz base del espacio nulo del jacobiano de las
1
restricciones activas (slo la primera) g ( x* )T = ( 2 0 )
1
Z + ( x* )T 2xx L( x* , * ) Z + ( x* ) = ( 1) = 1
1 1
19/02/2010 165
OPTIMIZACIN NO LINEAL
0
luego x = no es ptimo.
0
1
b) Probar si x = es ptimo.
1
1 22 0
x L ( x, ) = =
21 22 0
Luego 1 = 2 = 0.5
La matriz base del espacio nulo del jacobiano de las restricciones activas es vaca.
Luego la condicin suficiente de segundo orden se satisface, luego el punto es un
mnimo local estricto.
0
c) Probar si x = es ptimo.
2
1 + 22 0 0
x L( x, ) = =
22 2 0
166 19/02/2010
MTODOS DE OPTIMIZACIN
- Mtodos factibles
Minimizan una funcin relacionada con el lagrangiano que tiene el mismo mnimo.
Sustituyen un problema NLP por una sucesin de problemas de optimizacin no
restringida, cuyas soluciones convergen a la misma solucin. En la funcin objetivo
se incluyen unas penalizaciones que miden las violaciones de las restricciones y
adems unos parmetros que determinan la importancia de cada restriccin. Dentro
de estos mtodos existen dos variantes, una que se mueve por fuera de la regin
factible (penalizacin exterior) y otra que se mueve por dentro de la regin factible
(penalizacin interior). El mtodo de penalizacin (exterior) penaliza la violacin de
las restricciones. Se mueve por puntos infactibles. Se aplica para restricciones de
igualdad y desigualdad. El mtodo barrera (interior) evita que se alcance el
contorno de las restricciones. Se mueve por puntos estrictamente factibles. No es
vlido para restricciones de igualdad. El mtodo del lagrangiano aumentado aade
una penalizacin cuadrtica al lagrangiano de una funcin.
min f ( x)
x (1.129)
Ax = b
19/02/2010 167
OPTIMIZACIN NO LINEAL
mn
donde x n
, A y b m
.
nm
donde v .
xk +1 = xk + pk (1.131)
pk = Zvk (1.132)
vk = Z T f ( xk ) (1.133)
pk = Zvk = ZZ T f ( xk ) (1.134)
Z T 2 f ( xk ) Z vk = Z T f ( xk ) (1.135)
168 19/02/2010
MTODOS DE OPTIMIZACIN
Bk vk = Z T f ( xk ) (1.136)
sk = Z T ( xk +1 xk ) (1.137)
yk = Z T ( f ( xk +1 ) f ( xk ) ) (1.138)
min f ( x)
x
(1.139)
gi ( x) = 0 i = 1, , m
donde x n
y gi : n
. El lagrangiano de este problema es
L ( x, ) = f ( x ) + T g ( x ) (1.140)
xk +1 xk pk
= + (1.141)
k +1 k k
p
2 L( xk , k ) k = L( xk , k ) (1.142)
k
19/02/2010 169
OPTIMIZACIN NO LINEAL
2xx L( xk , k ) g ( xk ) pk x L( xk , k )
= (1.143)
( ) 0 k g ( xk )
T
g xk
1 T 2
min pk xx L( xk , k ) pk + pkT [ x L( xk , k ) ]
pk 2 (1.144)
[g ( xk )] pk + g ( xk ) = 0
T
La funcin objetivo cuadrtica resulta ser una aproximacin en serie de Taylor del
x
lagrangiano en el punto k y las restricciones resultan una aproximacin lineal de las
k
restricciones originales g ( xk + p ) .
Sea el problema ( P)
min f (x )
x
gi (x ) 0 i = 1,..., m (1.145)
h j (x ) = 0 j = 1,..., l
m l
P (x ) = (gi (x )) + (h j (x )) (1.146)
i =1 j =1
170 19/02/2010
MTODOS DE OPTIMIZACIN
(y ) = 0 y 0 (y ) = 0 y = 0
de modo que y .
(y ) > 0 y > 0 (y ) > 0 y 0
1 l 1
q
(y ) = y o (x ) = h j (x )2 = h(x )T h(x )
2 j =1 2
min (x , k ) = {f (x ) + k P (x )} (1.147)
x
min f (x )
x
(1.148)
h j (x ) = 0 j = 1,..., l
19/02/2010 171
OPTIMIZACIN NO LINEAL
Sea el problema (P )
min f (x )
x
(1.151)
gi (x ) 0 i = 1,..., m
(y ) 0 y < 0
donde . Lo ms habitual es definir (y ) = 1 y o
limy 0 (y ) =
172 19/02/2010
MTODOS DE OPTIMIZACIN
min f (x )
x
(1.156)
gi (x ) = 0 i = 1, , m
1
min A(x , , ) = f (x ) + T g(x ) + g(x )T g(x ) (1.158)
x ,, 2
19/02/2010 173
OPTIMIZACIN NO LINEAL
1
min A(x , k , k ) = f (x ) + kT g(x ) + k g(x )T g(x ) (1.159)
x 2
k +1 = k
(1.160)
k +1 = k + k g(x k +1 )
Mtodo
Ax = b Z T 2 f (x k )Z vk = Z T f (x k )
Cuasi-Newton reducido min f (x ) min (v ) = f (x + Zv )
x v
Ax = b Bk vk = Z T f (x k )
174 19/02/2010
MTODOS DE OPTIMIZACIN
gi (x ) 0 m l
P (x ) = (gi (x )) + (h j (x ))
h j (x ) = 0 i =1 j =1
III.5. Referencias
Bazaraa, M.S., Sherali, H.D. and Shetty, C.M. (1993) Nonlinear Programming. Theory
and Algorithms. John Wiley and Sons.
Gill, P.E., Murray, W. and Wright, M.H. (1981) Practical Optimization. Academic
Press.
Kuhn, H.W. and Tucker, A.W. (1951) Nonlinear Programming Econometrica (19) pp.
50-51.
Nash. S.G. and Sofer. A. (1996) Linear and Nonlinear Programming. McGraw-Hill.
19/02/2010 175
OPTIMIZACIN NO LINEAL
PROBLEMA 1
PROBLEMA 2
PROBLEMA 3
Los costes de produccin por unidad de producto son 0.2 y 0.3 y la capacidad de
produccin disponible en cada uno es 25 y 50, respectivamente. Adems, existe un
lmite en la capacidad total de produccin de la empresa representado por la ecuacin
QA + 2QB 50 .
176 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 4
min 3x + y z 2
3) x +y +z 0
x + 2y + z 2 = 0
min x
4) x +y +z = 0
x 2 + y 2 + z 2 = 2 >0
2
Es x = ( , , ) mnimo global del problema, siendo los multiplicadores
6 6 6
1
(v1, v2 ) = (1/ 3, )?
6
PROBLEMA 5
19/02/2010 177
OPTIMIZACIN NO LINEAL
y2 x 1
x 2
3) Alguno de los puntos anteriores es mnimo global del problema? Por qu?
PROBLEMA 6
Se considera el problema
max x 2 + y 2
(x 4)2 + (y 4)2 12
x +y 5
PROBLEMA 7
min 2(x 12 + x 22 1) x 1
x 12 + x 22 1 = 0
1
min x TQx
2
Ax = b
178 19/02/2010
MTODOS DE OPTIMIZACIN
13 6 3 0
13 23 9 3 2 1 2 1 3 0
Q = A = b = partiendo de x =
6 9 12 1 1 1 3 1 2 0
3 3 1 1 0
1 1
min x 12 + x 22
2 2
x1 + x 2 1
1 1
min x 13 + x 23
3 3
x1 + x 2 1
1 1
min x 13 + x 23
3 3
2 2
x1 + x 2 1
min x 12 + x 22
x1 + x 2 = 1
min x 12 + x 22
x 12 x 22
+ =1
25 9
min x 1 + x 2
Resolver por el mtodo de penalizacin interior (barrera): x 1 0
x1 0
PROBLEMA 8
Calcular analticamente
3 4
min x 2 2xy + y 2 + xz + 3z 2 4zw + 2w 2 x z
2 3
19/02/2010 179
OPTIMIZACIN NO LINEAL
PROBLEMA 9
Una furgoneta que tiene 4 m 3 de capacidad tiene que transportar 600 kg de tres
productos, A, B y C. Cada kilo de A ocupa 0.08 m 3 , cada kilo de B ocupa 0.06 m 3 y
uno de C 0.07 m 3 .
9x + 10
cA (x ) = , x 50 (la cantidad mnima a llevar es de 50 kg),
x
12
cB (x ) =
1 + 0.1x
PROBLEMA 10
180 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 11
min 4x + 3y
x +y 5
3x + 2y 12
x, y 0
1) Resolverlo grficamente
3) Comprobar que los puntos que las cumplen son ptimos globales.
PROBLEMA 12
Se quiere obtener una rentabilidad esperada superior al 24%, pero de forma que se
minimice la varianza de dicha rentabilidad. Cmo se han de invertir los 9000 ? Probar
que, efectivamente, esa inversin es la mejor posible.
PROBLEMA 13
19/02/2010 181
OPTIMIZACIN NO LINEAL
x 2 2xy + 2y 2 + 2yz + 2z 2 9
y el semiespacio
x + y + 4z 8
W = x 2 + y 2 + 2yz + 4z 2 x + 5y
Comprobar que el potencial mnimo se alcanza en el punto (1, 1,2) . Para ello,
probar que dicho punto satisface las condiciones necesarias de KKT y las condiciones
suficientes de mnimo global.
El mximo (global por las condiciones suficientes de KKT) se alcanza en los valores
(p1, p2 ) = (110, 40) (multiplicadores u1 = 0 , u2 = 60 ), beneficio = 50 .
182 19/02/2010
MTODOS DE OPTIMIZACIN
min x 2 + (y 3)2
x + y 2 + 1 0
x 2 0
Condiciones KKT:
2x u1 + u2 = 0
2(y 3) + 2yu1 = 0
u1(x + y 2 + 1) = 0
u2 (x 2) = 0
u1, u2 0
19/02/2010 183
OPTIMIZACIN NO LINEAL
Se dan ambas restricciones con igualdad, luego ambos multiplicadores pueden ser
2(1 3)
distintos de cero. De la segunda ecuacin se tiene u1 = =2 y
21
sustituyendo en la primera sera u2 = u1 2x = 2 2 2 = 2 , luego no es
candidato a mnimo.
2 0 0 0
H f = y H g =
0 2
0 2 1
que est dentro del crculo de centro (4,4) y radio 12 y pertenece al semiespacio
x +y 5.
2) KKT:
2x + 2(x 4)u1 u2 = 0
2y + 2(y 4)u1 u2 = 0
u1((x 4)2 + (y 4)2 12) = 0
u2 (x y + 5) = 0
u1, u2 0
2(4 + 6) + 2 6u1 = 0 4 6 6
u1 = < 0.
2(4 + 6) + 2 6u1 = 0 6
184 19/02/2010
MTODOS DE OPTIMIZACIN
No puede asegurarse que sea ptimo global por las KKT (la funcin objetivo es
convexa no cncava). Para asegurarlo haba que ver todos los puntos KKT que salen
y si es el nico se puede asegurar pues la funcin est acotada (salvo para puntos en
los que los gradientes de las restricciones activas sean linealmente dependientes que
podran no salir al resolver el sistema de ecuaciones de KKT). Es el nico que sale al
resolver.
3x 2y + z 1 = 0 x + z 1 = 0
2x + 2y = 0 x =y
x + 6z 4w 4 / 3 = 0 x + 2z 4 / 3 = 0
4z + 4w = 0 z =w
(x , y, z , w ) = (2 / 3,2 / 3,1/ 3,1/ 3) f .ob = 0.5555
Se ramifica en x 0 y x 1 .
3x 2y + z 1 + u1 = 0 x + z 1 + u1 = 0
2x + 2y = 0 x =y
x + 6z 4w 4 / 3 = 0 Multiplicador mayor o igual que 0, x + 2z 4 / 3 = 0
4z + 4w = 0 z =w
u1x = 0 u1x = 0
- u1 0 x = 0 z = 2 / 3 u1 = 1/ 3
19/02/2010 185
OPTIMIZACIN NO LINEAL
3x 2 y + z 1 u1 = 0 x + z 1 u1 = 0
2 x + 2 y = 0 x = y
x + 6 z 4w 4 / 3 = 0 Multiplicador mayor o igual que 0, x + 2z 4 / 3 = 0
4 z + 4 w = 0 z = w
u1 ( x 1) = 0 u1(x 1) = 0
u1 0 x = 1 z = 1/ 6 u1 = 1/ 6
-
Nodo 3: Ramificado con z 0 . Al aplicar las condiciones KKT el sistema es casi igual
al del nodo 2, excepto la tercera restriccin que es la derivada respecto a z, y la holgura:
3x 2 y + z 1 u1 = 0 x + z 1 u1 = 0
2 x + 2 y = 0 x = y
x + 6 z 4 w 4 / 3 + u2 = 0 x + 2z 4 / 3 + u2 = 0
Multiplicador mayor o igual que 0,
4 z + 4 w = 0 z=w
u1 ( x 1) = 0 u1(x 1) = 0
u2 z = 0 u 2z = 0
u2 0 z = 0
-
u1 = 0 x = 1 u2 = 1/ 3 :
(x , y, z , w ) = (1,1, 0, 0) (u1, u2 ) = (0,1/ 3) f .ob = 0.5
u1 0 x = 1 u1 = 0, u2 = 1/ 3 misma solucin que la anterior
186 19/02/2010
MTODOS DE OPTIMIZACIN
3x 2 y + z 1 u1 = 0 x + z 1 u1 = 0
2 x + 2 y = 0 x = y
x + 6 z 4 w 4 / 3 u2 = 0 x + 2z 4 / 3 u2 = 0
Multiplicador mayor o igual que 0,
4 z + 4 w = 0 z=w
u1 ( x 1) = 0 u1(x 1) = 0
u2 ( z 1) = 0 u2 (z 1) = 0
u2 0 z = 1
-
u1 = 0 x = 0 No factible.
u1 0 x = 1 u1 = 1, u2 = 5 / 3
(x , y, z , w ) = (1,1,1,1) (u1, u2 ) = (1, 5 / 3) f .ob = 0.166666
Nodo podado por ser entera; y cota peor que la ya obtenida hasta el momento.
19/02/2010 187
OPTIMIZACIN NO LINEAL
0
(2/3,2/3,1/3,1/3)
f.o= -0.5555
x 0 x 1
1 2
(0,0,2/3,2/3) (1,1,1/6,1/6)
f.o= -0.4444 f.o= -0.52777
Podado,
peor cota z 0 z 1
3 4
(1,1,0,0) (1,1,1,1)
f.o= -0.5 f.o=0.1666
Podado, Podado,
entera. Entera.
M ejor so lucin Solucin peor
hasta m o m ento
9x + 10 12 12y
min x+ y + 10z
min 9x + 10 + + 10z
x 1 + 0.1y
1 + 0.1y
s.a. x + y + z = 600
s.a. x + y + z = 600
0.08x + 0.06y + 0.07z 4 0.08x + 0.06y + 0.07z 4
x 50 x 50
y0
y0
z 0
z 0
9 + v + 0.08u2 u 3 = 0
12
2 + v + u2 u 4 = 0
(1 + 0.1y )
10 + v + 0.07u2 u5 = 0
188 19/02/2010
MTODOS DE OPTIMIZACIN
0
0 0
2 orden: H f = 0 2.4 /(1 + 0.1y )3 0 semidefinida negativa, luego cncava,
0
0 0
luego no se dan las condiciones suficientes KKT. El problema es acotado, luego si slo
saliera un punto que verifique las necesarias sera el mnimo global, pero, si salen ms
habra que comparar entre ellos cul es el de menor valor.
x x
max (100 1 )x 1 + (60 2 )x 2 30(x 1 50) 40(x 1 + x 2 120)
6 6
s.a. x 1 50 50 x 1 0
Modelo:
x 1 + x 2 120 120 x 1 x 2 0
x2 0 x2 0
KKT(necesarias):
100 x 1 30 40 1 2 = 0
60 2 x 40 = 0
6
2 2 3
1(50 x 1 ) = 0 2 (120 x 1 x 2 ) = 0 3 (x 1 ) = 0 i 0
KKT (suficientes): las restricciones son convexas (por ser lineales) y la funcin
2 / 6 0
definida negativa, luego es cncava
objetivo es cncava? H f (x ) =
0 2 / 6
para todo x . As pues las condiciones KKT son necesarias y suficientes para encontrar
el ptimo global de este problema.
Punto (90,60): para este punto (que es factible ya que cumple todas las
restricciones), ninguna restriccin es activa, luego i = 0 . La primera ecuacin KKT
sera entonces 100180/63040=0 que se cumple, y la segunda sera 60120/640=0
que se cumple. Luego, cumple las condiciones KKT, luego es mximo global del
problema.
19/02/2010 189
OPTIMIZACIN NO LINEAL
4 1 + 32 3 = 0
min 4x + 3y 3 + 2
4 = 0
1 2
x y + 5 0
(x + y 5) = 0
1) 3x + 2y 12 0 LP KKT 1
2 (3x + 2y 12) = 0
x 0
3x = 0
y 0
y = 0 i 0
4
Resolver sistema:
- 3 = 0
4 = 0 4 1 + 32 = 0 y 3 1 + 22 = 0 2 = 1 NO
4 0 y = 0 No factible
3 0 x =0
-
4 = 0
1 = 0 2 = 3 / 2 NO
1 0 x +y 5 = 0 y=5 2 = 0 1 = 3 3 = 1
Punto (0, 5) Multiplicadores (3, 0,1, 0)
4 0 y = 0 No factible
3) Dual
190 19/02/2010
MTODOS DE OPTIMIZACIN
S1 1 3 1 0 4 S1 0 1 1 1 1
S2 1 2 0 1 3 W1 1 2 0 1 3
4) Fcil ver que las condiciones KKT corresponden al mismo sistema, y a las
condiciones de holgura complementaria del ptimo del dual.
minW = x 2 + y 2 + 2yz + 4z 2 x + 5y
x 2 2xy + 2y 2 + 2yz + 2z 2 9
x + y + 4z 8
minW = x 2 + y 2 + 2yz + 4z 2 x + 5y
x 2 2xy + 2y 2 + 2yz + 2z 2 9 0
x y 4z + 8 0
El lagrangiano ser
L(x , y, z , 1, 2 ) = x 2 + y 2 + 2yz + 4z 2 x + 5y +
+1(x 2 2xy + 2y 2 + 2yz + 2z 2 9) + 2 (x y 4z + 8)
19/02/2010 191
OPTIMIZACIN NO LINEAL
2x 1 + 1(2x 2y ) + 2 (1) = 0
2y + 2z + 5 + 1(2x + 4y + 2z ) + 2 (1) = 0
2y + 8z + 1(2y + 4z ) + 2 (4) = 0
1(x 2 2xy + 2y 2 + 2yz + 2z 2 9) = 0
2 (x y 4z + 8) = 0
1, 2 0
adems el punto debe ser factible, es decir, debe cumplir las ecuaciones
x 2 2xy + 2y 2 + 2yz + 2z 2 9
x + y + 4z 8
Para dicho punto las restricciones son activas luego los multiplicadores de Lagrange
pueden ser mayores que 0 de acuerdo con las ecuaciones de la complementariedad de
holguras. Sustituyendo el punto (1, 1,2) en las condiciones KKT nos queda
1 + 41 2 = 0
7 21 2 = 0
14 + 61 42 = 0
2L 2L 2L
x 2 x y x z
2
L 2L 2L
2L(x , y, z ) =
y x y 2 y z
2L 2L 2L
z x z y z 2
2L 2L 2L 2L 2L
siendo = 2 + 21 , = 21 , = 0, = 2 + 41 , = 2 + 21 ,
x 2 x y x z y 2 y z
2L
= 8 + 41 . Luego el hessiano es
z 2
192 19/02/2010
MTODOS DE OPTIMIZACIN
2 + 2 21 0 4 2 0
1
2
L(x , y, z ) = 21 2 + 41 2 + 21 = 2 6 4
0 2 + 21 8 + 41 0 4 12
1 =1
que es una matriz definida positiva ya que los determinantes en orden creciente son
4 2 0
4 2
todos estrictamente positivos 4 = 4 , = 20 y 2 6 4 = 176 . Los
2 6
0 4 12
2 0 0
f (x , y, z ) = 0 2 2
2
0 2 8
que es una matriz definida positiva ya que los determinantes en orden creciente son
2 0 0
2 0
todos estrictamente positivos 2 = 2 , = 4 y 0 2 2 = 24 . Los autovalores
0 2
0 2 8
2 2 0
g1(x , y, z ) = 2 4 2
2
0
2 4
que es una matriz definida positiva ya que los determinantes en orden creciente son
2 2 0
2 2
todos estrictamente positivos 2 = 2, =4 y 2 4 2 = 8 . Los
2 4
0 2 4
19/02/2010 193
OPTIMIZACIN NO LINEAL
0 0 0
g 2 (x , y, z ) = 0 0 0
2
0 0 0
194 19/02/2010
MTODOS DE OPTIMIZACIN
IV.1. Estocasticidad
11
La restriccin a problemas lineales es por razones prcticas: primero, son los ms frecuentemente
utilizados, y segundo, aqullos con mtodos de solucin ms eficientes y avanzados. Las tcnicas que se
presentan admiten tambin funciones no lineales si regin factible y funcin objetivo son convexas
19/02/2010 195
OPTIMIZACIN ESTOCSTICA
12
El recurso se denomina completo cuando para cualquier decisin de la primera etapa
(independientemente de su factibilidad) existen decisiones factibles para la segunda etapa. Se denomina
relativamente completo si se cumple slo para decisiones factibles de la primera etapa y parcial o simple
cuando no siempre las decisiones de la segunda etapa son factibles para las decisiones de la primera
etapa.
13
Se denomina bietapa porque tiene dos etapas, una asociada a las decisiones anteriores a la
realizacin de la incertidumbre y otra a las decisiones correctoras una vez realizada la incertidumbre.
196 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 197
OPTIMIZACIN ESTOCSTICA
SETS
I generadores / gen-1 * gen-4 /
J periodos / per-1 * per-3 /
S escenarios de demanda / s-1 * s-3 /
PARAMETERS
F(i) coste fijo de inversin []
/ gen-1 10
gen-2 7
gen-3 16
gen-4 6 /
SCALARS
POTMIN potencia mnima a instalar [MW] / 12 /
PRSPTO lmite presupuestario [] / 120 /
VARIABLES
X(i) potencia a instalar [MW]
Y(j,i) potencia en operacin [MW]
YS(s,j,i) potencia en operacin estocstica [MW]
COSTE coste total
POSITIVE VARIABLES X, Y, YS
EQUATIONS
COST coste total []
COSTS coste total estocstico []
PRESUP limitacin presupuestaria []
INSMIN potencia mnima instalada [MW]
BALPOT potencia en operacin menor que instalada [MW]
198 19/02/2010
MTODOS DE OPTIMIZACIN
LOOP (s,
DEM(j) = DEMS(s,j) ;
SOLVE DETERM MINIMIZING COSTE USING LP ;
) ;
* problema estocstico
19/02/2010 199
OPTIMIZACIN ESTOCSTICA
o Una es solucionar el problema para cada posible escenario. sta se denomina espera
y observa (wait and see o scenario analysis o what-if analysis), corresponde a tomar
las decisiones una vez que se ha resuelto la incertidumbre. A partir de las soluciones
se observan sistemticamente semejanzas y diferencias entre ellas y mediante
criterios subjetivos tomar decisiones flexibles, es decir, aqullas cuyos componentes
forman parte de las decisiones ptimas bajo numerosos escenarios. Evidentemente
este procedimiento no garantiza la obtencin de la solucin ptima. De hecho la
solucin ptima estocstica no tiene por qu ser ptima para ningn escenario. Con
este criterio el generador 2 en el problema de expansin previo no aparecera puesto
que no aparece en la solucin para ninguno de los escenarios ni para el de demanda
media. Sin embargo, s aparece en la solucin ptima del problema estocstico.
o Otra es la solucin del problema estocstico para el valor medio de los parmetros
aleatorios convirtindolo, por tanto, en un problema determinista.
Los diferentes estados que pueden tomar los parmetros aleatorios a lo largo del
tiempo se representan mediante un rbol de probabilidad o de escenarios (figura 4.1.).
Se define un escenario como cualquier camino (trayectoria) que va desde la raz del
rbol hasta las hojas de manera que los escenarios que comparten una misma
200 19/02/2010
MTODOS DE OPTIMIZACIN
informacin hasta una cierta etapa tambin comparten esa parte del rbol. El rbol de
probabilidad es la forma natural y explcita de representar la no anticipatividad de las
decisiones. En el caso ejemplo previo, el rbol es simplemente una raz y tres hojas. Las
decisiones de la primera etapa se comparten (son las mismas para cualquiera de los
escenarios) y por eso la raz es nica. Las decisiones de la segunda etapa son mltiples
(dependen de cada escenario) y por eso tiene tres hojas. La determinacin del rbol de
probabilidad debe considerar las dependencias temporales y/o espaciales que pudieran
existir entre los parmetros aleatorios. Si el proceso aleatorio es markoviano la
dependencia temporal slo alcanzar un periodo. En un caso general se puede extender
ms all.
Y1
Y2
X
Y3
19/02/2010 201
OPTIMIZACIN ESTOCSTICA
X1 Y1
Y2
X2
X3 Y3
BALPOTS
Restricciones segundo escenario
BALDEMS
BALPOTS
Restricciones tercer escenario
BALDEMS
202 19/02/2010
MTODOS DE OPTIMIZACIN
las decisiones de la primera etapa. Este valor siempre ser menor o igual, si se est
minimizando, que la funcin objetivo del problema estocstico.
Para cada escenario, la solucin del problema estocstico es siempre peor o igual
que la solucin con informacin perfecta (280, 349.33 y 439.33 respectivamente). Se
denomina arrepentimiento a la diferencia entre ambas (280262=18, 349.33
346.67=2.66, 439.33437.33=2) y valor esperado de la informacin perfecta (EVPI) a
su esperanza.
Cuando esta diferencia en algn escenario pueda ser elevada (de consecuencias
catastrficas) o existe gran no linealidad en la funcin objetivo para los diferentes
escenarios la optimizacin estocstica se puede formular como minimizacin del
mximo arrepentimiento (o criterio minimax). ste es un criterio conservador de
proteccin frente el riesgo que determina planes robustos (es decir, estables frente a
perturbaciones en los datos).
19/02/2010 203
OPTIMIZACIN ESTOCSTICA
SETS
S escenarios de temperatura / nr, fr, mf /
O opciones de gestin / cyv, cya, ayv /
PARAMETERS
CVS(s) coste del gas en cada escenario []
/ nr 5.0
fr 6.0
mf 7.5 /
SCALARS
CALM coste de almacenamiento [ por ao] / 1 /
VARIABLES
X(o) cantidad que gestiona el primer ao
Y(o) cantidad que gestiona el segundo ao
YS(s,o) cantidad que gestiona el segundo ao estocstico
COSTE coste total
POSITIVE VARIABLES X, Y, YS
EQUATIONS
COST coste total
COSTS coste total estocstico
BALDEM1 balance de demanda del primer ao
BALDEM2 balance de demanda del segundo ao
BALDEMS2 balance de demanda del segundo ao
GSTDEP gestin del depsito ;
LOOP (s,
CV = CVS(s) ;
DEM = DEMS(s) ;
204 19/02/2010
MTODOS DE OPTIMIZACIN
* problema estocstico
Para este ejemplo tambin se observa que las soluciones en cada escenario son
claramente diferentes a las del escenario medio y a las decisiones del problema
estocstico.
19/02/2010 205
OPTIMIZACIN ESTOCSTICA
(Dantzig, 1963), (Dantzig, 1961). Por otra parte, como otra extensin de la
programacin lineal para grandes sistemas con estructuras especiales en la matriz de
coeficientes de las restricciones aparecieron las tcnicas de descomposicin (Benders,
1962), (Dantzig, 1963), (Dantzig, 1960), (Van Slyke, 1969), denominadas de
optimizacin matemtica a gran escala.
o descomposicin
La conjuncin de varias de estas tcnicas fue propuesta por Dantzig (Dantzig, 1987),
(Dantzig, 1990) y ha dado resultados espectaculares por los tamaos de los problemas
de planificacin resueltos (Dantzig, 1991a), (Dantzig, 1991c), (Entriken, 1990),
(Infanger, 1991), (Infanger, 1994), (Stanford, 1989).
14
Las tcnicas de descomposicin son de uso matemtico general y tienen sentido
independientemente de la tecnologa del ordenador/es utilizados en su resolucin. Sin embargo, dada su
naturaleza resulta muy conveniente la utilizacin de clculo en paralelo (un ordenador con mltiples
CPUs dbil o fuertemente acopladas) o clculo distribuido (mltiples ordenadores trabajando en
colaboracin) para reducir los tiempos de clculo de manera sustancial.
206 19/02/2010
MTODOS DE OPTIMIZACIN
min(c1T x 1 + cT2 x 2 )
x1 ,x 2
A1x 1 = b1
(1.161)
B1x 1 +A2x 2 = b2
x 1, x2 0
19/02/2010 207
OPTIMIZACIN ESTOCSTICA
A1
B1 A2
Los dos ejemplos del captulo anterior corresponden a problemas lineales bietapa,
deben proporcionar decisiones antes de resolver la incertidumbre, siendo la segunda
etapa estocstica. Un problema de planificacin esttica (para un momento fijo en el
tiempo) se formula frecuentemente como minimizacin de una funcin objetivo suma
de costes totales de inversin y explotacin sujeta a restricciones propias de inversin y
de explotacin. Las decisiones de inversin corresponden a la primera etapa y las de
explotacin a la segunda.
Bp1x p1 + Ap x p = bp p = 1, , P (1.162)
xp 0
B0 0
donde las matrices Ap y Bp y los vectores bp y cp son conocidos por ser optimizacin
208 19/02/2010
MTODOS DE OPTIMIZACIN
A1
B1 A2
B2 A3
BP 1 AP
Figura 4.5 Estructura de la matriz de coeficientes de las restricciones en problemas lineales multietapa.
El tamao del problema crece linealmente con el nmero de etapas. Aunque para
problemas pequeos o medianos se pueden utilizar tcnicas convencionales de
programacin lineal, esto resulta inviable para problemas de gran tamao. Por ello, para
su resolucin se emplean tcnicas de descomposicin que aprovechan su especial
estructura.
A1x 1 = b1
(1.163)
B1 x 1 +A2 x 2 = b2
x 1, x 2 0
15
El superndice indica la dependencia de las matrices y vectores con respecto al valor de .
19/02/2010 209
OPTIMIZACIN ESTOCSTICA
A1
B11 A21
B12 A22
B13 A23
min
,x1 ,x 2
siendo f el valor ptimo de la funcin objetivo para cada escenario (i.e., la funcin
objetivo para la decisin ptima sabiendo que va a ocurrir un determinado escenario
).
210 19/02/2010
MTODOS DE OPTIMIZACIN
p
p pT
min
p p p c xp p
xp
p =1 p p
p p 1
B x
p 1 p 1 + Ap p x p p = bp p p = 1, , P (1.165)
p
x p 0
B01 0
de los valores tomados en la etapa anterior. Cuando se van a tomar las decisiones al
comienzo de la etapa p los valores de cp p , Bpp 1 , Ap p , bp p son conocidos y se conocen
las distribuciones condicionadas de los vectores para las etapas futuras p + 1, , P . Los
diferentes valores de los parmetros en las sucesivas etapas forman una estructura en
rbol.
P P
p =1
m p p restricciones y p =1
n p p variables, siendo Ap p una matriz m p n p .
A1
B11 A21
B12 A22
B21 A31
B22 A32
B23 A33
B24 A34
Figura 4.15 Estructura de la matriz de coeficientes de las restricciones en problemas lineales multietapa.
19/02/2010 211
OPTIMIZACIN ESTOCSTICA
IV.5. Referencias
Dantzig, G.B. and Glynn, P.W. Parallel Processors for Planning Under Uncertainty
Annals of Operations Research. Vol 22, pp 1-21. 1990.
Dantzig, G.B., Ho, J.K. and Infanger, G. Solving Stochastic Linear Programs on a
Hypercube Multicomputer Systems Optimization Laboratory. Department of
Operations Research. Stanford University. SOL 91-10. August 1991.
212 19/02/2010
MTODOS DE OPTIMIZACIN
Dantzig, G.B. and Infanger, G. Multi-Stage Stochastic Linear Programs for Portfolio
Optimization Systems Optimization Laboratory. Department of Operations
Research. Stanford University. SOL 91-11. September 1991.
Gassmann, H.I. MSLiP: A Computer Code for the Multistage Stochastic Linear
Programming Problem Mathematical Programming. Vol 47, pp 407-423. August
1990.
Gassmann, H.I. and Ireland, A.M. On the Formulation of Stochastic Linear Programs
using Algebraic Modelling Languages Annals of Operations Research. Vol 64, pp
83-112. 1996.
19/02/2010 213
OPTIMIZACIN ESTOCSTICA
Jacobs, J, Freeman, G., Grygier, J., Morton, D. P., Schultz, G., Staschus, K. and
Stedinger, J. SOCRATES: A System for Scheduling Hydroelectric Generation
under Uncertainty Annals of Operations Research. Vol 59, pp 99-133. 1995.
Kall, P. and Wallace, S.W. (1995) Stochastic Programming. John Wiley and Sons.
Murtagh, B.A. and Saunders, M.A. MINOS 5.1 User's Guide Systems Optimization
Laboratory. Department of Operations Research. Stanford University. SOL 83-
20R. December 1983. Revised January 1987.
214 19/02/2010
MTODOS DE OPTIMIZACIN
Prez Arriaga, J.I., Ramos, A. y Latorre, G. Volumen 1: Gua de usuario del programa
de planificacin esttica de la red de transporte a largo plazo. PERLA. Volumen 2:
Casos ejemplo Instituto de Investigacin Tecnolgica. Julio 1991.
Ramos, A. Integrated Model for Capacity Planning for Manufacturing Systems March
1992.
Rockafellar, R.T. and Wets, R.J.B. Scenarios and Policy Aggregation in Optimization
Under Uncertainty Mathematics in Operations Research. Vol 16, pp 119-147.
Van Slyke, R.M. and Wets, R.J.-B. L-Shaped Linear Programs with Application to
Optimal Control and Stochastic Programming SIAM Journal on Applied
Mathematics. Vol 17, No 4, pp 638-663. July 1969.
19/02/2010 215
MTODOS DE OPTIMIZACIN
V. Programacin dinmica
V.1. Introduccin
Hay una gran variedad de situaciones de muy diversa naturaleza que se pueden
modelar como procesos de decisin secuenciales de tipo polietpico, para los cuales el
mtodo conocido como programacin dinmica (dynamic programming DP) se muestra
como una herramienta eficaz en la mayora de los casos.
16
Estas etapas muchas veces se hallan asociadas a tiempo, de ah el nombre de programacin
dinmica, pero esto no es necesario.
19/02/2010 217
PROGRAMACIN DINMICA
Variables de Variables de
estado de etapa Decisiones estado de etapa
k k +1
xk uk x k +1
La programacin dinmica es una tcnica de divide y vencers. Resuelve el
problema de optimizacin del conjunto de todas las etapas mediante un procedimiento
recursivo que se resuelve de manera iterativa, incorporando cada vez una etapa, es
decir, partes cada vez mayores del problema original. El procedimiento puede hacerse
hacia delante (forward DP) o hacia atrs (backward DP). La recursin hacia atrs
define la poltica ptima en la etapa k conocida la poltica ptima en cualquier estado
de la etapa k + 1 , produciendo un modelo del tipo, por ejemplo,
218 19/02/2010
MTODOS DE OPTIMIZACIN
adems, no slo la decisin ptima sino otras soluciones cuasiptimas con los valores
correspondientes de la funcin objetivo.
x k +1 = k (x k , uk ) (1.167)
gk ,ik (x k , uk ) = 0
x k X k , uk U k
En lo que sigue supondremos que los posibles cambios slo pueden tener lugar en
instantes discretos del tiempo, no forzosamente equidistantes. Al intervalo de tiempo
transcurrido entre la adopcin de dos decisiones consecutivas es lo que hemos llamado
fase o etapa. En la prctica la dificultad radica en los aspectos siguientes:
o la identificacin de las fases o etapas, junto con las variables de estado y las de
decisin
19/02/2010 219
PROGRAMACIN DINMICA
Una vez conocida la solucin ptima global, cualquier solucin parcial que
involucre slo una parte de las etapas es tambin una solucin ptima. Todo
subconjunto de una solucin ptima es a su vez una solucin ptima para un problema
parcial.
220 19/02/2010
MTODOS DE OPTIMIZACIN
Andorra
Barcelona
Lrida
Zaragoza
Castelln
Madrid Valencia
Vamos a considerar un problema clsico soportado por una red valorada (es decir,
una red a cada uno de cuyos arcos le ha sido asignado uno o ms valores, que pueden
ser una distancia, un tiempo o un coste) y sin circuitos.
Supongamos que se quiere construir una carretera entre las ciudades de Aburgo y
Teburgo, que constar de seis tramos y pasar por una serie de ciudades. Los costes de
las distintas variantes que el trazado de la carretera puede tener vienen reflejados en la
figura 1 y en ellos se han tenido en cuenta los trabajos y construcciones de carcter
tcnico que la obra lleva implcitos, as como los gastos de expropiaciones,
indemnizaciones, etc.
19/02/2010 221
PROGRAMACIN DINMICA
Geburgo
7
1
Beburgo 6 Kaburgo
2 Hacheburgo 9
Eburgo 6 11
8 5 4
1 Peburgo
5
Ceburgo 8 2 6
6 Eleburgo
Iburgo 3
7 9
Aburgo
6 4 Teburgo
5 6 5
5 Efeburgo 6
6 Ereburgo
Deburgo 4 5
5
8 Emeburgo
Jotaburgo
Figura 1
222 19/02/2010
MTODOS DE OPTIMIZACIN
7
B 1
6 K
2 H 9
E 6 11
8 5 4
1 P
C 5
8 2 6
6 L
A 7 I 3
9 T
6 4
5 6 5
5 F 6 R
4 6 5
D 5
8 M
J
Tramo I Tramo II Tramo III Tramo IV Tramo V Tramo VI
Figura 2
Nivel Ciudades
0 A
1 B, C, D
2 E, F
3 G, H, I, J
4 K, L, M
5 P, R
6 T
Tabla 1
Designaremos por vi (x i1, x i ) al coste del tramo i-simo, el cual depender de los
1) El coste mnimo del tramo 1 para cada una de las ciudades B, C y D que lo
configuran es
g1 (B ) = 8, g1 (C ) = 6, g1 (D ) = 5
2) Calculamos ahora el coste mnimo conjunto de construccin de tramos 1 y 2. Las
ciudades en las que puede acabar el conjunto de los dos primeros tramos son E y
F. Tendremos
19/02/2010 223
PROGRAMACIN DINMICA
224 19/02/2010
MTODOS DE OPTIMIZACIN
ACEG: coste 8, ADFH: coste 13, ACEI: coste 14, ACEJ: coste 13
TPKG: coste 8, TPLH: coste 16, TPMI: coste 15, TPLJ: coste 13
A continuacin vamos a presentar este mismo problema desde otro ngulo. Se trata
de un viajante de comercio que desea ir de la ciudad A a la J por el camino ms corto.
Vamos a resolver el problema mediante programacin dinmica hacia atrs. Notar que
el avance a travs de la red est dividido en etapas, necesarias para que se pueda utilizar
la programacin dinmica. Por consiguiente, no es un problema general de distancia
mnima en una red (para ese caso tambin es posible aplicar el principio de optimalidad
y ecuaciones para implantar la solucin, pero la definicin de las etapas y estados no es
tan evidente).
19/02/2010 225
PROGRAMACIN DINMICA
B 7 E
1
4
2 6 4 H
3 3
6
A 4 C 2 F J
4 3
4
3 I
4 3
1 3
D 5 G
Estados x 4
Estados x 3 H I Distancia acumulada f3* Decisin ptima u 3*
E 4 8 4 H
F 9 7 7 I
G 6 7 6 H
Para la etapa k = 2
Estados x 3
Estados x 2 E F G Distancia acumulada f2* Decisin ptima u2*
B 11 11 12 11 E, F
C 7 9 10 7 E
D 8 8 11 8 E, F
Finalmente en la etapa k = 1
Estados x 2
Estado x 1 B C D Distancia acumulada f1* Decisin ptima u1*
A 13 11 11 11 C, D
226 19/02/2010
MTODOS DE OPTIMIZACIN
A partir de la tabla final se deduce que las rutas ptimas son: ACEHJ, ADEHJ y
ADFIJ con distancia total de 11. Obsrvese que si en cada ciudad se hubiera tomado la
decisin miope, es decir, ir a la ciudad ms prxima, la distancia total recorrida sera de
13, que no coincide con la ptima.
Estado x 1
Estados x 2 A Distancia acumulada f2* Decisin ptima u2*
B 2 2 A
C 4 4 A
D 3 3 A
Para k = 3
Estados x 2
Estados x 3 B C D Distancia acumulada f3* Decisin ptima u 3*
E 9 7 7 7 C, D
F 6 6 4 4 D
G 8 8 8 8 B, C, D
Para k = 4
Estados x 3
Estados x 4 E F G Distancia acumulada f4* Decisin ptima u 4*
H 8 10 11 8 E
I 11 7 11 7 F
Finalmente para la etapa k = 5
Estados x 4
Estados x 5 H I Distancia acumulada f5* Decisin ptima u5*
J 11 11 11 H, I
Las rutas ptimas son: JHECA, JHEDA y JIFDA con distancia ptima de 11.
19/02/2010 227
PROGRAMACIN DINMICA
Se trata de minimizar los costes totales (fijos y variables) de expansin del equipo
generador para un alcance de varios aos. Las decisiones son la potencia a instalar de
cada tipo de generacin en cada ao del alcance del modelo. Habitualmente se tienen en
cuenta estas restricciones en la expansin: potencia instalada inicial conocida, mxima
(mnima) potencia instalable, inversin mxima (mnima), nmero mximo (mnimo) de
generadores instalables en cada ao. Adems tambin se consideran estas restricciones
de operacin: el balance generacin demanda en cada ao. Los estados se definen como
el nmero total de generadores instalados al comienzo de cada ao.
Est 2004
Est 2003 8000 Cst fut Inst pt
7000 15+40=55 55 1000
8000 0 0 0
Para la etapa n = 2003
228 19/02/2010
MTODOS DE OPTIMIZACIN
Est 2003
Est 2002 7000 8000 Cst fut Inst pt
6000 15+45+55=115 15+90=105 105 2000
7000 55 15+45=60 55 0
8000 0 0 0
Para la etapa n = 2002
Est 2002
Est 2001 6000 7000 8000 Cst fut Inst pt
4000 15+130+105=250 15+195+55=265 250 2000
5000 15+65+105=185 15+130+55=200 15+195=210 185 1000
6000 105 15+65+55=135 15+130=145 105 0
7000 55 15+65=80 55 0
8000 0 0 0
Para la etapa n = 2001
Est 2001
Est 2000 4000 5000 6000 7000 8000 Cst fut Inst pt
2000 15+120+250=385 15+180+185=380 380 3000
3000 15+60+250=325 15+120+185=320 15+180+105=300 300 3000
4000 250 15+60+185=260 15+120+105=240 15+180+55=250 240 2000
5000 185 15+60+105=180 15+120+55=190 15+180=195 180 1000
6000 105 15+60+55=130 15+120=135 105 0
Est 1999
Est 1998 1000 2000 3000 Cst fut Inst pt
0 15+50+420=485 15+100+360=475 15+150+285=450 450 3000
La potencia ptima a instalar en cada ao a partir de 1999 es: 3000, 3000, 0, 0, 2000
y 0 MW con un coste total de 450 .
19/02/2010 229
PROGRAMACIN DINMICA
Los ejemplos anteriores son tambin ilustracin de un caso general, que podemos
denominar de funciones separables en fases, y el proceso de optimizacin empleado se
230 19/02/2010
MTODOS DE OPTIMIZACIN
dice que es de tipo secuencial. Estas denominaciones son vlidas no slo para aquellas
funciones para las que
G (x 0 , x 1, , x n ) = v1 (x 0 , x 1 ) + v2 (x 1, x 2 ) + + vn (x n 1, x n ) (1.169)
G (x 0 , x 1, , x n ) = v1 (x 0 , x 1 ) v2 (x 1, x 2 )vn (x n 1, x n ) (1.170)
F (x 1, x 2 , , x n ) = f1 (x 1 ) + f2 (x 2 ) + + fn (x n ) (1.171)
x1 + x 2 + + xn = K ; xi 0 (1.172)
o Los ingresos procedentes de distintas actividades pueden ser medidos con una
misma unidad.
19/02/2010 231
PROGRAMACIN DINMICA
R1 (C 0 , x 0 ) = g (x 0 ) + h (C 0 x 0 ), x 0 [ 0,C 0 ] (1.173)
C 1 = cx 0 + b(C 0 x 0 )
C 1 = x 1 + (C 1 x 1 ), 0 < x 1 < C 1
g (x 1 ) + h (C 1 x 1 )
R2 (C 0 , x 0 , x 1 ) = g (x 0 ) + h (C 0 x 0 ) + g (x 1 ) + h (C 1 x 1 )
0 x 0 C 0 ; 0 x1 C 1
RN (C 0 , x 0 , x 1, , x N 1 ) = g (x 0 ) + h (C 0 x 0 ) + g (x 1 ) + h (C 1 x 1 ) +
+ g (x N 1 ) + h (C N 1 x N 1 )
232 19/02/2010
MTODOS DE OPTIMIZACIN
x 1 = cx 0 + b (C 0 x 0 ), 0 x 0 C 0
x 2 = cx 1 + b (C 1 x 1 ), 0 x 2 C 1
x N 1 = cx N 2 + b (C N 2 x N 2 ), 0 x N 2 C N 2 , 0 x N 1 C N 1
C0 = max RN (C 0 , x 0 , , x N 1 ), N = 2, 3,
{x 0 ,x1 ,....,x N 1 }
con
f1 (C 0 ) = max R1 (C 0 , x 0 ) = max g (x 0 ) + h (C 0 x 0 )
0x 0 C 0 0x 0 C 0
f1 (C 0 ) . Considerando el proceso bietpico, vemos que el retorno total ser la suma del
elegido en la etapa inicial, la cantidad restante C 1 debe ser usada de la mejor manera
posible en la segunda etapa, si deseamos obtener una asignacin ptima. Si lo hacemos
as, en la segunda etapa conseguiremos un retorno ptimo
f1 (cx 0 + b (C 0 x 0 ))
si x 1 es elegido de forma ptima. Como resultado el retorno total para el conjunto de las
dos primeras etapas, resultante de la asignacin inicial x 0 , viene dado por
19/02/2010 233
PROGRAMACIN DINMICA
R2 (C 0 , x 0 , x 1 ) = g (x 0 ) + h (C 0 x 0 ) + f1 (ax 0 + b (C 0 x 0 ))
ptima que debemos hacer al comienzo de la k-sima etapa cuando inicialmente se parte
con una cantidad C 0 . As, la solucin de un problema especfico, dados C 0 y N , es de
la forma
x 0* = x N (C 0 )
x 1* = x N 1 (ax 0* + b (C 0 x 0* ))
x 2* = x N 2 (ax 1* + b (C 1 x 1* ))
x N* 1 = x 1 (ax N* 2 + b (C N 2 x N* 2 ))
siendo (x 0*, x 1*, , x N* 1 ) un conjunto de asignaciones, que puede no ser nico, que
Las ventajas del mtodo son evidentes: hemos reducido un simple problema N-
dimensional a una secuencia de N problemas unidimensionales.
234 19/02/2010
MTODOS DE OPTIMIZACIN
f (C 0 ) = max g (x ) + h (C 0 x ) + f (ax + b (C 0 x ))
0x C 0
cuya solucin f (C 0 ) es el retorno total del proceso, con una funcin de asignacin
x1 + x 2 + + x N = C
xi 0
g N (C ) = max F (x 1, x 2 , , x N ), N = 1,2,
{xi }
fN (C ) = max [ ]
0x C
g N (C ) = max ( fN (x ) + g N 1 (C x )), N = 2, 3,
0x C
con g1 (C ) = f1 (C ) .
Teorema 1:
Supongamos que
19/02/2010 235
PROGRAMACIN DINMICA
Bajo estas hiptesis hay una solucin nica de [8] que es continua y que se anula
para x = 0 .
Definicin 1:
[0,1]
f (u + (1 ) v ) f (u ) + (1 ) f (v )
f (u + (1 ) v ) f (u ) + (1 ) f (v )
Teorema 2:
Teorema 3:
Teorema 4:
g (0) h (0)
> , h (0) > g (0), a < b
1 a 1 b
236 19/02/2010
MTODOS DE OPTIMIZACIN
g (x ) h (C 0 x ) + (a b ) f (ax + b (C 0 x )) = 0
Inversin 0 1 2 3 4 5 6 7 8 9
Zona 1 0 0.5 0.6 0.8 1.1 1.3 1.4 1.46 1.50 1.52
Zona II 0 0.4 0.48 0.6 0.78 0.91 1 1.05 1.08 1.1
Zona III 0 0.6 0.71 0.9 1.08 1.26 1 1.48 1.55 1.6
Zona IV 0 0.3 0.45 0.7 0.85 0.95 1.02 I 1.07 1.1 1 1.13
Tabla 2.1
F (x 1, x 2 , x 3 , x 4 ) = f1 (x 1 ) + f2 (x 2 ) + f3 (x 3 ) + f4 (x 4 )
x 1 + x 2 + x 3 + x 4 = 9 ; x i 0, x i
19/02/2010 237
PROGRAMACIN DINMICA
g 0 (y 0 ) = 0 , y 0 = 0
g 0 (y 0 ) = 1 , y 0 = 1
g 4 (9) = max g 3 (y 3 ) + f4 (9 y 3 )
0y3 9
y1 , y 2 0 1 2 3 4 5 6 7 8 9
0 0.5 0.6 0.8 1.1 1.3 1.4 1.46 1.50 1.52
f2 (y2 y1 ) = f2 (x 2 ) 0 0.4 0.48 0.6 0.78 0.91 1 1.05 1.08 1.1
Subpolticas
ptimas para 0,0 1,0 1,1 2,1 3,1 4,1 5,1 6,1 5,3 5,4
las zonas I y II
Tabla 2.2
para obtener las subpolticas ptimas para el conjunto de las dos primeras zonas, en la
que, por ejemplo, g2 (3) se ha obtenido de la forma siguiente
238 19/02/2010
MTODOS DE OPTIMIZACIN
g 2 (3) = max [ f1 (0) + f2 (3), f1 (1) + f2 (2), f1 (2) + f2 (1), f1 (3) + f2 (0)] =
= max[0 + 0.6, 0.5 + 0.48, 0.6 + 0.4, 0.8 + 0] = 1
frmula [12]. Esta tabla y la frmula [13] nos permitirn obtener la tabla 2.4 y
determinar la poltica ptima.
x 3 , y2 0 1 2 3 4 5 6 7 8 9
( )
g 2 y2 0 0.5 0.9 1 1.2 1.5 1.7 1.8 1.9 2.08
( ) (
f3 x 3 = f3 y 3 y2 ) 0 0.6 0.71 0.9 1.08 1.26 1.4 1.48 1.55 1.6
( )
g 3 y3 0 0.06 1.1 1.5 1.61 1.8 2.1 2.8 2.41 2.6
Subpoltica
ptima para 0,0 1,0 1,1 2,1 3,1 4,1 5,1 6,1 5,3 5,4
zonas I y II
Subpolticas 3,1,1
ptimas para 0,0,0 0,0,1 1,0,1 1,1,1 1,1,2 4,1,1 5,1,1 5,1,2 5,1,3
zonas I a III 1,1,3
Tabla 2.3
x 4 , y3 0 1 2 3 4 5 6 7 8 9
( )
g 3 y3 0 0.6 1.1 1.5 1.61 1.8 2.1 2.3 2.41 2.6
( ) = f4 (9 y 3 )
f4 x 4 0 0.3 0.45 0.7 0.85 0.95 1.02 1.07 1.1 1 1.13
Subpolticas 3,1,1
ptimas para 0,0,0 0,0,1 1,0,1 1,1,1 1,2,2 4,1,1 5,1,1 5,1,2 5,1,3
Zonas I, II y III 1,1,3
Polticas
ptimas 0,0,0,0 0,0,1,0 1,0,1,0 1,1,1,0 1,1,1,1 1,1,1,2 1,1,1,3 4,1,1,1 5,1,1,1 4,1,1,3
Tabla 2.4
19/02/2010 239
PROGRAMACIN DINMICA
La poltica ptima es, por tanto, la (4,1,1,3), pudiendo verificarse que todas las
subpolticas son ptimas. As, por ejemplo, la tabla 2.2 nos muestra que la mejor
manera de distribuir 5 millones entre las zonas I y II es 4 y 1 respectivamente, mientras
que el anlisis combinado de las tablas 2.2 y 2.4 nos permitira establecer que la manera
ptima de distribuir 4 millones entre las zonas III y IV es asignar 1 milln a III y 3 a IV
con un beneficio de 1.3 millones.
Debe hacerse resaltar la gran eficiencia del mtodo. Una descripcin de todas las
polticas hubiera precisado el anlisis de 220 posibilidades, mientras que si el nmero
de millones a invertir hubiera sufrido un incremento slo de 3 millones, el nmero de
posibilidades hubiera llegado a 455.
Al comienzo vimos un ejemplo en el que sobre una red valorada, en la que cada arco
tena asociado el coste de la construccin del correspondiente tramo de carretera,
tratbamos de obtener el trazado de una carretera entre dos ciudades con coste mnimo.
En el caso siguiente se analiza una red del tipo conocido como red Manhattan, que
adopta una estructura rectangular. En el ejemplo considerado se trata de encontrar el
camino de duracin mnima entre los puntos O y B de una ciudad, separados por siete
manzanas de casas, conocindose el tiempo, en minutos, que se tarda en atravesar cada
una de las manzanas que constituyen las diversas rutas que unen O y B. Se trata de
obtener el camino que lleva de O hasta B con la condicin de que las direcciones de
avance son de izquierda a derecha o de abajo hacia arriba. A tal efecto, consideraremos
un origen de coordenadas en el punto O y asociaremos a cada encrucijada posible un par
240 19/02/2010
MTODOS DE OPTIMIZACIN
En lo que sigue designaremos por t(i, j ) al mnimo tiempo que se tarda en alcanzar
el vrtice (i, j ) desde O. Adems llamamos i = 0 al tiempo que se tarda en llegar al
vrtice (i, j ) desde el vrtice inferior (i, j 1) y D(i, j ) al tiempo que se invierte en
el trayecto entre los vrtices (i 1, j ) e (i, j ) . El proceso de bsqueda del camino al que
corresponde el tiempo mnimo de viaje entre el punto O (0, 0) y el punto B (m, n ) lo
dividiremos en m + n etapas o fases, para una red Manhattan general de dimensin
m n . La variable de estado x k asociada a la fase k tomar como argumentos todos
los vrtices (i, j ) tales que i + j = k .
min [t (i 1, j ) + D (i, j ), t (i, j 1) + A (i, j )], j 0, i 0
t (i, j ) =
t (i 1, j ) + D (i, j ), si j = 0
i + j =k
t (i, j 1) + A (i, j ), si i = 0
Para cada fase, y para cada vrtice de la misma tal que i = 0 , j = 0 , la decisin a
tomar es si debe ser alcanzado desde el vrtice (i 1, j ) , que representaremos por una
Derecha, o desde el vrtice (i, j 1) , que representaremos por una Arriba. Para los
vrtices en los que i = 0 o j = 0 la decisin viene forzada: A o D, respectivamente.
(0,4) 5 (1,4) 4 (2,4) 3 (3,4)
2 3 4 6
(0,3) 2 (1,3) 3 (2,3) 2 (3,3)
3 5 4 1
(0,2) 1 (1,2) 3 (2,2) 6 (3,2)
4 3 6 5
(0,1) 2 (1,1) 4 (2,1) 4 (3,1)
3 1 3 5
(0,0) 2 (1,0) 3 (2,0) 4 (3,0)
Figura 3
19/02/2010 241
PROGRAMACIN DINMICA
242 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 243
PROGRAMACIN DINMICA
Dada la intervencin del azar, el valor de una estrategia se suele medir utilizando
algn tipo de promedio sobre los valores aleatorios que puede tomar la magnitud que se
quiere maximizar, en este caso la cantidad total de oro extrada. Suele ser habitual tomar
como medida de valoracin el valor esperado.
cuando A tiene x ; B tiene y y se ha empleado una estrategia ptima que dura como
mucho N etapas o extracciones.
f1 (x , y ) = max (pArAx , pB rB y )
f (B, x , y ) = pB (rB y + fN 1 (x , (1 rB ) y ))
244 19/02/2010
MTODOS DE OPTIMIZACIN
Al igual que nos ocurri en los modelos de asignacin podemos plantearnos que
sucedera si el nmero de etapas crece indefinidamente. En este caso, el retorno total
f (x , y ) , suponiendo que exista, satisface la ecuacin funcional
Como antes tambin se hace necesario establecer las condiciones para la existencia
y unicidad de las soluciones de esta ecuacin.
x k +1 = Ak x k + Bk uk (1.174)
19/02/2010 245
PROGRAMACIN DINMICA
J N* = x TNQN x N (1.176)
J N 1
= (RN 1 + BNT 1QN BN 1 ) uN 1 + BNT 1QN AN 1x N 1 = 0
uN 1
246 19/02/2010
MTODOS DE OPTIMIZACIN
1
uN* 1 = (RN 1 + BNT 1QN BN 1 ) BNT 1QN AN 1x N 1
es decir, J N* 1 = x TN 1K N 1x N 1 , con
uk* = Lk x k
1
Lk = (Rk + BkT K k +1Bk ) BkT K k +1Ak
K N = QN
Esta solucin del problema resulta especialmente atractiva porque cada estado x k es
realimentado como control uk mediante una ganancia lineal Lk .
uk xk
x k +1 = Ak x k + Bk uk
Lk
19/02/2010 247
PROGRAMACIN DINMICA
K = AT K KB (R + BT KB ) BT K A + Q
1
u * = Lx (1.181)
PROBLEMA 1
PROBLEMA 2
248 19/02/2010
MTODOS DE OPTIMIZACIN
El ingeniero responsable de una central elctrica tiene que decidir cada da, a la vista
de la demanda prevista para ese da, cules de los dos generadores de 600 y 1000 MW
de que dispone deben ser puestos en funcionamiento y en qu momento. La demanda
requerida vara a lo largo de cuatro periodos en los que el da se considera dividido a
estos efectos, de acuerdo con la siguiente tabla:
19/02/2010 249
PROGRAMACIN DINMICA
PROBLEMA 4
Tras realizar un estudio de mercado, la empresa estima que habr una demanda de
3000 helados en julio, 2000 helados en agosto y 1000 helados en septiembre. Los
pedidos de helados deben hacerse en cajas de 1000 unidades. Con el fin de simplificar
el clculo de costes, se considerar que cada helado almacenado al final de mes
supondr un coste de 10 . Los gastos de produccin dependen del nmero de cajas de
1000 unidades producidas mensualmente segn se muestra en la tabla.
Se supone que los helados tienen una caducidad de 6 meses, por lo que los helados
que no se vendan un mes servirn para el mes siguiente. La empresa parte de un
inventario de cero unidades y no desea ningn inventario al final del verano. Se pide:
1) Determine cul debe ser la produccin de la empresa durante los meses de junio,
julio y agosto.
PROBLEMA 5
250 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 6
Una compaa area tiene una flota de 15 aeronaves: 5 de cada uno de tres tipos A,
B y C, cuyas respectivas capacidades para el transporte de viajeros son de 80, 70 y 55
personas. Una agencia de viajes le solicita presupuesto para trasladar a 372 personas. La
compaa analiza sus costes, que dependen del nmero de aviones de cada tipo que
19/02/2010 251
PROGRAMACIN DINMICA
quiera utilizar para transportar a esas personas, datos que se dan en la siguiente tabla en
miles de euros
Tipo 1 2 3 4 5
A 11 20 30 40 50
B 9 17 24 34 45
C 8 15 21 26 31
Adems la compaa area incurre en un coste fijo adicional de 6 k por cada tipo
de aviones que utilice.
PROBLEMA 7
Aos funcionando
Ao adquisicin 1 2 3
1-ene-2005 4000 5400 9800
1-ene-2006 4300 6200 8700
1-ene-2007 4800 7100
1-ene-2008 4900
Adems se considera un coste de mantenimiento anual de 200 el primer ao de
uso, 300 en segundo y 500 el tercero.
252 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 8
Asignaturas
Das dedicados CS ITF MM
0 0 0 0
1 4 5 5
2 5 6 7
3 6 7 9
4 8 8 9
5 10 9 10
Desarrollar un modelo de programacin dinmica que optimice la distribucin de
tiempo en orden a obtener una puntuacin global media mxima, dando la solucin
ptima.
19/02/2010 253
PROGRAMACIN DINMICA
Las etapas son las temporadas. Los estados en cada etapa son las seis combinaciones
posibles de orden de emisin de los tres programas. Los denominamos (1,2, 3)k ,
(1, 3,2)k , (2,1, 3)k , (2, 3,1)k , (3,1,2)k , (3,2,1)k , para una etapa k cualesquiera.
(1,2, 3)0
(1,2, 3)1 2.5+3.6+3.8=9.9 (1,2, 3)0
(2,1, 3)1 2.25+2.7+3.80.250.25=8.25 (1,2, 3)0
(2, 3,1)1 2.25+4.2+3.50.250.250.25=9.2 (1,2, 3)0
254 19/02/2010
MTODOS DE OPTIMIZACIN
Luego la solucin ptima es emitir los programas en el siguiente orden (1,2, 3)1 ,
(1,2, 3)2 , (1,2, 3)3 , (1,2, 3)4 (1, 3,2)4 con un total de 38.3 millones de espectadores.
19/02/2010 255
PROGRAMACIN DINMICA
B 0 1 2 3 4 5
0 0 (0) 17 (70) 23 (140) 30 (210) 40 (280) 51 (350)
80 17 (80) 34 (150) 40 (220) 47 (290) 57 (360) 68 (430)
160 26 (160) 43 (230) 49 (300) 56 (370) 66 (440) Sobra
240 36 (240) 53 (310) 59 (380) Sobra Sobra Sobra
320 46 (320) 63 (390) Sobra Sobra Sobra Sobra
400 56 (400) Sobra Sobra Sobra Sobra Sobra
C 0 1 2 3 4 5
0 Falta Falta Falta Falta Falta Falta Falta
70 Falta Falta Falta Falta Falta Falta Falta
80 Falta Falta Falta Falta Falta Falta Falta
140 Falta Falta Falta Falta Falta 31+6+23 60
150 Falta Falta Falta Falta Falta 31+6+34 71
160 Falta Falta Falta Falta 26+6+26 Sobra 58
210 Falta Falta Falta 21+6+30 Sobra Sobra 57
220 Falta Falta Falta 21+6+40 Sobra Sobra 67
230 Falta Falta Falta 21+6+43 Sobra Sobra 70
240 Falta Falta Falta 21+6+36 Sobra Sobra 63
280 Falta Falta 15+6+40 Sobra Sobra Sobra 61
290 Falta Falta 15+6+47 68
300 Falta Falta 15+6+49 70
310 Falta Falta 15+6+53 74
320 Falta 8+6+46 60
350 Falta 8+6+51 65
360 Falta 8+6+57 71
370 Falta 8+6+56 70
380 59 59
390 63 63
400 56 56
430 68 68
440 66 66
Mnimo: 56
Mnimo: 56 k con 0 de tipo C, 0 de tipo B y 5 de tipo A.
Las etapas son los aos, de 2006 a 2009. Los estados de cada etapa son el ao de
antigedad del coche. Las decisiones al principio de cada etapa son comprar o no coche.
A2005
2006
A 4000+200=4200 A2005 4200
C2006A2005 200 A2005 200
256 19/02/2010
MTODOS DE OPTIMIZACIN
A2006 C2006A2005
A2007 4300+200+4200=8700 5400+300+200=5900 5900 C2006A2005
C2007A2006 200+4200=4400 4400 A2006
C2007A2005 300+200=500 500 C2006A2005
19/02/2010 257
PROGRAMACIN DINMICA
CS
Decisiones 0 1 2 3 4 5 pt f.pt.
Estados
0 15 18 17 16 13 10 1 18
Solucin: dedicar a CS 1 da, a ITF 1 da y a MM 3 das. Notas: 4, 5 y 9. Nota media
6.
0 Nota total Decisin
acumulada ptima
0MM 0 0 0MM
1MM 5 5 1MM
2MM 7 7 2MM
3MM 9 9 3MM
4MM 9 9 4MM
5MM 10 10 5MM
258 19/02/2010
MTODOS DE OPTIMIZACIN
Dentro de este contexto surge la decisin multicriterio, en la que si bien dada una
decisin sus consecuencias estn perfectamente determinadas, lo que no est definido
tan claramente es qu es lo mejor, existiendo varios objetivos en conflicto.
19/02/2010 259
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
260 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 261
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Un ejemplo grfico para dos atributos que se desea que tomen el mayor valor
posible podra ser el siguiente:
z2
Espacio de objetivos
Alternativas dominadas
z1
Sin embargo, en la mayora de las situaciones, el fin ltimo es dar una nica
solucin, no un conjunto de posibles soluciones. Se denomina solucin de mejor
compromiso a la solucin del conjunto eficiente que es seleccionada por el decisor.
Coste Calidad
Coste m11 m12
Calidad m21 m22
donde m11 es el mnimo coste que se puede lograr con las condiciones impuestas en el
siguiente fila sera al revs, es decir, m22 sera la mxima calidad que se puede lograr de
262 19/02/2010
MTODOS DE OPTIMIZACIN
la mezcla, y m21 sera el coste de esa mezcla. A la diagonal de esta matriz se le conoce
como punto ideal ya que tiene los mejores valores posibles para cada uno de los
atributos, y si existe realmente conflicto entre criterios, ser un punto inalcanzable.
500 C
D
Coste
300
E B
200
A
Coste Calidad
Coste 200 20
Calidad 500 100
y el punto ideal sera (200,100), inalcanzable a la vista del espacio de objetivos.
Por otra parte, las tasas de intercambio (trade-offs o costes de oportunidad) entre los
atributos representan lo que se est dispuesto a empeorar un atributo por mejorar en una
unidad otro objetivo. Seran las pendientes de los segmentos que forman el conjunto
eficiente. As, en el segmento AB la tasa de intercambio entre el coste y la calidad ser
300 200
TA ' B ' = = 1.66 , es decir, en ese segmento cada unidad ms de calidad cuesta
80 20
1.66 unidades monetarias. Anlogamente, para el segmento BC la tasa ser
500 300
TB 'C ' = = 10 . Es decir, cada unidad ms de calidad cuesta 10 unidades
100 80
monetarias.
Problemas sencillos como ste pueden ser resueltos con Excel, utilizando el
complemento que viene por defecto, Solver.
19/02/2010 263
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
X 20
X + Y 100
X + Y 50
X ,Y 0
Por otra parte, los dos atributos planteados y su direccin de optimizacin, seran:
Calidad: max X
Coste: min 200 X + 100Y
90
80
70
60
50
40
30
20
10
0
0 20 40 60 80 100 120
C ompone nt e X
264 19/02/2010
MTODOS DE OPTIMIZACIN
Las soluciones obtenidas optimizando cada criterio por separado forman la matriz
de pagos del problema:
Calidad Coste
Coste 20 7000
25000
Coste (200X+100Y)
20000
15000
10000
5000
0
0 20 40 60 80 100 120
Calidad (X)
Obsrvese que para obtener las tasas de intercambio ha sido necesario tener la
Frontera de Pareto. Y por otra parte, para obtener la frontera de Pareto, hemos obtenido
todo el espacio de objetivos, a partir de las imgenes de los vrtices del espacio de
soluciones. Sin embargo, este procedimiento es altamente costoso, y nada trivial. Por lo
tanto, lo primero que se va a estudiar es cmo obtener la frontera de Pareto directamente
19/02/2010 265
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Dado que de forma natural surge que la decisin que debera tomarse en un
problema con criterios mltiples debera encontrarse en la frontera de Pareto, es lgico
querer conocer esta frontera, que incluso permite determinar las tasas de intercambio.
As dentro de los mtodos de anlisis existe la denominada optimizacin multiobjetivo,
que son un conjunto de mtodos para generar el conjunto eficiente en su totalidad.
Las tcnicas generadoras del conjunto eficiente, son tcnicas de carcter mecnico,
en las que no se incluyen las preferencias del decisor. El fin para el que estn diseadas
es la obtencin de todo el conjunto eficiente, en general, tras aplicar mtodos de
programacin paramtrica, aunque no llegaremos a ese nivel de profundidad.
Este mtodo consiste en multiplicar cada objetivo por un peso o factor no negativo y
agregarlos en una nica funcin. Variando los pesos se puede obtener todo el conjunto
eficiente, obteniendo las distintas soluciones mediante programacin paramtrica. Sin
266 19/02/2010
MTODOS DE OPTIMIZACIN
embargo, en este curso nos conformaremos con resolver los distintos problemas
planteados para los valores de los parmetros mediante Solver.
p
max i zi ( x)
i =1
xF P ( )
0
Uno de los resultados en que se fundamenta este mtodo dice que si i > 0 i ,
En cualquier caso, hay que tener en cuenta que para aplicar este mtodo (y no slo
ste) es conveniente haber normalizado previamente los criterios (para que no influya la
diferencia de unidades de los criterios).
En primer lugar, hay que tener en cuenta que para agregar los objetivos ambos tienen
que ir en el mismo sentido, es decir, no podemos tener uno de maximizacin (Calidad) y
otro de minimizacin (Coste). Para ello basta con cambiar de signo la expresin de uno
para que ya estn ambos en el mismo sentido. Por ejemplo, poniendo un menos en el
Coste, ya ser un criterio de maximizacin.
Por lo tanto, el modelo que hay que resolver para distintos valores de lambda es:
Para ello utilizamos un archivo de Excel, con una celda para el valor de lambda que
iremos introduciendo, y una celda para el objetivo agregado. Este modelo lo
19/02/2010 267
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Obsrvese que la solucin es siempre la misma excepto para la ltima fila de la tabla.
El problema es que la programacin lineal siempre da un vrtice de la regin factible
como solucin, por lo que sta se va a ir repitiendo hasta el coste pierda fuerza en el
objetivo agregado. Por otra parte, dado que las unidades son muy distintas entre uno y
otro criterio resulta muy difcil llegar a compensar el coste con la calidad. Para evitar
este problema, puesto que con estos pocos valores de lambda y tal diferencia de
unidades es difcil creer que sa sea la frontera de Pareto (las combinaciones lineales de
ambas soluciones), se puede normalizar cada uno de los criterios en la funcin
agregada. Hay muchas formas de normalizar pero en decisin multicriterio, y dado que
ya se tiene la matriz de pagos, una forma es restar al ideal el criterio y dividir por la
diferencia entre el ideal y el anti-ideal, entendido como el peor valor en la matriz de
pagos para ese criterio. En nuestro ejemplo, la matriz de pagos es:
Calidad Coste
Coste 20 7000
268 19/02/2010
MTODOS DE OPTIMIZACIN
Obsrvese adems que ahora ambos criterios son de minimizacin puesto que
queremos aproximarnos en ambos casos al ideal de cada criterio.
Puede observarse que se han obtenido tres puntos distintos, cuyos valores de los
criterios son: (20,7000), (50,10000) y (100,20000), cuya unin da lugar a toda la
frontera de Pareto segn el siguiente grfico:
19/02/2010 269
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Fronte ra de Pare to
25000
20000
15000
10000
5000
0
0 20 40 60 80 100 120
Calidad
max zl ( x)
xF Pl ( )
zk ( x ) k k = 1,..., l 1, l + 1,..., p
eficiente.
Por lo tanto, de estos dos resultados se infiere que variando el lado derecho siempre
obtenemos soluciones eficientes, y que hacindolo variar adecuadamente debemos
obtener todas las soluciones eficientes. Sin embargo, su aplicacin prctica suele ser
relativamente compleja.
270 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 271
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Fronte ra de Pare to
25000
20000
15000
Coste
10000
5000
0
0 20 40 60 80 100 120
Calidad
Se define el punto o alternativa ideal, como un punto del espacio de objetivos que
recoge los valores ptimos de los objetivos individualmente tratados y se denota por
272 19/02/2010
MTODOS DE OPTIMIZACIN
z * = ( z1* ,..., zi* ,..., z *p ) , siendo zi* = max zi ( x) (en caso de maximizar el objetivo, en otro
xF
1/
p
zi zi ( x )
*
min L = wi *
xF
i =1 zi z*i
donde el conjunto de los pesos wi suponen una ponderacin preferencial de los criterios
19/02/2010 273
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
conjunto compromiso coincide con este segmento. En nuestro caso, trabajaremos con el
caso lineal y Tchebychev.
En primer lugar, de la matriz de pagos obtenemos los puntos ancla que nos dan el
siguiente ideal z*= (100,7000), y el anti-ideal z* = (20,20000).
100 X 100 X
Calidad : d1 ( X , Y ) = =
100 20 80
7000 (200 X + 100Y ) 200 X + 100Y 7000
Coste : d 2 ( X , Y ) = =
7000 20000 13000
Ahora tenemos que dar la ponderacin subjetiva de los criterios. sta es la parte ms
complicada, ya que a veces es difcil decir cunto ms importante es un criterio respecto
al otro. Por otra parte, se suelen dar pesos cuya suma sea 1, por normalizar. De
momento, supongamos que consideramos que la calidad es 3 veces ms importante que
el coste, en cuyo caso el peso de la calidad sera 0,75, y el del coste 0,25.
274 19/02/2010
MTODOS DE OPTIMIZACIN
min D
s.a. X 20
X + Y 100
X + Y 50
100 X
0, 75 D
80
200 X + 100Y 7000
0, 25 D
13000
X ,Y 0
19/02/2010 275
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Sin embargo, dado que son niveles de aspiracin, una restriccin meta, en general,
no puede ser incluida como una restriccin rgida en el problema, ya que soluciones que
no logren ese nivel de aspiracin tambin son soluciones admisibles. As, una
restriccin meta se formula utilizando variables de desviacin: zi ( x) + ni pi = zi . De
estas variables, una de ellas es una variable no deseada: si la meta es al menos un
valor, la variable no deseada ser ni , y si es del tipo a lo sumo, la variable de
desviacin no deseada ser pi . En ocasiones, hay metas de ser igual a cierto nivel de
aspiracin, en cuyo caso ambas variables son no deseadas, pero no es habitual.
Este procedimiento se puede aplicar tambin a las restricciones del problema para
relajarlas, admitiendo soluciones cercanas a la regin factible (el mismo concepto se
ha aplicado en lgica difusa para resolver problemas de programacin lineal).
276 19/02/2010
MTODOS DE OPTIMIZACIN
Sin embargo, casi nunca se utiliza en su versin bsica. Algunas variantes de este
mtodo se han desarrollado con gran xito y se exponen a continuacin.
p
min ( i ni + i pi )
i =1
zi ( x) + ni pi = z i = 1,..., p
xF
ni 0, pi 0 i = 1,..., p
La idea bsica es ponderar las variables de desviacin, ya que pueden tener diferente
relevancia las metas o diferentes unidades si no han sido previamente normalizados los
criterios.
En primer lugar, hemos de dar un nivel de aspiracin para la calidad y uno para el
coste. Por ejemplo, supongamos que queremos una calidad del 75% y un coste de
10000. Y supongamos que no damos preferencias subjetivas ms all de las marcadas
por los propios niveles de aspiracin. En ese caso el modelo sera:
19/02/2010 277
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
n1 p2
min +
75 10000
s.a. X 20
X + Y 100
X + Y 50
X + n1 p1 = 75
200 X + 100Y + n2 p2 = 10000
X , Y , n1 , n2 , p1 , p2 0
En este caso se busca una solucin equilibrada, de modo que ninguna de las metas
se desve en exceso de su nivel de aspiracin. Para ello se minimiza la mxima distancia
a este nivel, es decir, el problema se planteara en estos trminos
min D
i ni + i pi D i = 1,..., p
zi ( x) + ni pi = z i = 1,..., p
xF
ni 0, pi 0 i = 1,..., p
Para el ejemplo que estamos viendo y con los mismos datos de la seccin anterior, el
modelo sera:
278 19/02/2010
MTODOS DE OPTIMIZACIN
min D
s.a. X 20
X + Y 100
X + Y 50
X + n1 p1 = 75
200 X + 100Y + n2 p2 = 10000
n1 / 75 D
p2 /10000 D
X , Y , n1 , n2 , p1 , p2 0
las dos primeras, despus la tercera, y por ltimo las 3 ltimas, el problema se
representa como
Para resolver el problema, se resolvera primero con las dos primeras metas.
Obtenidos los valores de las variables de desviacin no deseadas para stas, se fijan y se
resuelve el problema para la tercera meta (segundo nivel de prioridad). Una vez
resuelto, se fija el valor de la variable no deseada tambin para esta meta, y se resuelve
el tercer nivel incluyendo las tres ltimas metas.
19/02/2010 279
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
anteriores. Es til cuando hay muchas metas y claramente diferenciadas (por ejemplo
metas econmicas, metas de clientes, etc.) teniendo una prioridad clara unas sobre otras.
Es cierto, que, por ejemplo, en las metas lexicogrficas si se fijan unos niveles muy
pesimistas en los primeros niveles (fciles de alcanzar) y muy optimistas en los
ltimos (difciles de alcanzar), al resolverlo para los primeros niveles se obtendr un
valor 0 de las desviaciones, y puede llegar un momento en que para una meta no
haya ptimos alternativos y, por lo tanto, fijar el valor de su desviacin es ya dar
una solucin haciendo redundantes las metas de prioridades ms bajas; de este
modo, sera equivalente a fijar las metas de los niveles anteriores en su nivel de
aspiracin y optimizar la meta para la que no hay ptimos alternativos. Sin embargo,
esta equivalencia se da por un mal planteamiento de los niveles de aspiracin. La
equivalencia puede darse tambin en metas ponderadas, por ejemplo, si se plantean
unos niveles de aspiracin muy pesimistas para las metas, excepto para una en que
resulte muy optimista, prcticamente inalcanzable. En tal caso, es cierto que el
280 19/02/2010
MTODOS DE OPTIMIZACIN
problema puede ser equivalente a optimizar ese atributo incluyendo las dems metas
como restricciones. En cualquier caso, estos problemas se derivan de la formulacin
del modelo y no a debilidades lgicas de la metodologa.
19/02/2010 281
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
mejora computacional (los mtodos de resolucin suelen aadir una variable en las
desigualdades como primera medida).
Las metas con dos lados no deseados son menos habituales que las de un solo lado,
ya que es raro que un decisor desee el logro exacto de una meta ms que superar, o
no hacerlo, un determinado nivel. Incluir entre las no deseadas una desviacin que
no lo es, puede llevar a obtener soluciones subptimas. Es claro, que hay que tener
un especial cuidado en identificar cules son las variables de desviacin no
deseadas.
282 19/02/2010
MTODOS DE OPTIMIZACIN
La programacin por metas no est pensada para obtener soluciones eficientes sino
para obtener soluciones satisfacientes. En este sentido, es posible que la solucin de
un modelo de programacin por metas no sea eficiente. Para ello, lo que tiene que
pasar es que haya ptimos alternativos del problema de metas ponderadas o del
ltimo nivel de metas lexicogrficos (esta condicin es necesaria aunque no es
suficiente). Para algunos autores es un gran inconveniente, pero no ha de olvidarse
que el objetivo de la programacin por metas, como ya se ha dicho, no es obtener
soluciones eficientes sino satisfacientes. Para comprobar si una solucin obtenida
mediante programacin por metas es eficiente, se fijan los valores de las variables
de desviacin no deseadas obtenidos, y se maximizan las variables opuestas; si la
solucin no cambia, es que la solucin es eficiente, mientras que si vara, la nueva
solucin ser una solucin eficiente con los mismos valores de las variables no
deseadas. Existe un test propuesto por Hannan (1980) que permite a partir de una
solucin obtenida por metas, obtener todas las soluciones eficientes que tienen el
mismo valor de las variables de desviacin no deseadas. Este test consiste en aplicar
la tcnicas multiobjetivo a un problema que sea el original pero incluyendo los
valores de las variables de desviacin (tanto las deseadas como las no deseadas)
obtenidas previamente mediante programacin por metas. As si una meta es que x1
19/02/2010 283
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Z1
f2
Z2
Z
f1
284 19/02/2010
MTODOS DE OPTIMIZACIN
Hay algunas formas ms sencillas de obtener los pesos, como es pedirle al decisor
que clasifique los criterios por orden de importancia, de modo que si hay n criterios, al
19/02/2010 285
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Para evitarlo Saaty propone otro mtodo que consiste en comparar los criterios por
parejas, de modo que se asigne un 1 si ambos son de la misma importancia, un 3 si hay
una moderada importancia de un criterio respecto a otro, un 7 si hay una demostrada
importancia y un 9 si hay extrema importancia. Con ello se forma una matriz cuadrada
aij que valora la importancia del criterio i respecto al j. Si la importancia de un criterio
respecto a otro es aij , a la inversa ser 1/ aij . Obtenida esta matriz, se busca un vector
Wi
de pesos para los criterios que sea solucin del sistema = aij , o lo que es lo mismo
Wj
Wi = aijW j . Lamentablemente, ese sistema no suele tener solucin dadas las normales
inconsistencias del decisor y hay que buscar los que ms se aproximen, por ejemplo,
con la programacin por metas vista en la seccin anterior (planteando las restricciones
meta Wi aijW j + nij pij = 0 y penalizando ambas variables de desviacin).
Supngase que se quiere elegir el trazado de una autopista, supngase que el centro
decisor ha emitido sus juicios de valor obteniendo la siguiente matriz de comparaciones.
286 19/02/2010
MTODOS DE OPTIMIZACIN
A partir de esta matriz se buscan los pesos preferenciales de los criterios resolviendo
el siguiente problema donde se han introducido las variables de desviacin para
resolverlo (ver la seccin VI.3.2):
3
min (ni + pi )
i =1
desviaciones n12 = n13 = n21 = n31 = n32 = p12 = p13 = p21 = p23 = 0, n23 = 0.06, p32 = 0.02 .
Esta misma estrategia puede utilizarse para comparar alternativas (numricas o no) y
asignarles un valor numrico de preferencias.
VI.4. Referencias
Benayoun, R., Roy, B., Sussman, B. Electre: Une Mthode pour Guider le Choix en
Prsence de Vue Multiples. Sema (Metra International), Direction Scientifique.
Note de travail, 49.
Charnes, A., Cooper, W.W (1961) Management Models and Industrial Applications of
Linear Programming. John Wiley and Sons.
DeGroot, M.H. (1970) Optimal Statistical Decisions, McGraw Hill, New York
19/02/2010 287
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Keeney, R.L. and Raiffa, H. (1976) Decisions with Multiple Objectives: Preferences
and Value Trade-Offs. John Wiley and Sons.
Yu, P.L. (1973) A Class of Solutions for Group Decision Problems. Management
Science, 19, 936-946.
Yu, P.L. (1985) Multiple criteria decision making: Concepts, techniques and
extensions. Plenum, New York.
288 19/02/2010
MTODOS DE OPTIMIZACIN
PROBLEMA 1
Las posibilidades de utilizacin de cada una de las opciones estn determinadas por
el potencial existente, o por condicionantes de otro tipo, que se detallan a continuacin:
o el potencial de la energa elica ha sido evaluado en unos 2.000 MW, que, para
una utilizacin media de 2.500 h, producira un mximo de 5.000 GWh.
Toda la demanda debe ser satisfecha con estas opciones, sin tener en cuenta otras
como fuel-oil, energa solar La tabla 1 muestra los costes de generacin y emisiones
de CO2 de las opciones consideradas, referidos al kWh generado 1GWh= 106kWh
19/02/2010 289
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
PROBLEMA 2
A y B preceden a C y D I precede a J
D y C preceden a E y F J precede a K y a L
E precede a I K y M preceden a N y O
F precede a G L precede a M
G precede a H N y O preceden a Q
H precede a L y a P
290 19/02/2010
MTODOS DE OPTIMIZACIN
Supngase ahora que los tiempos sealados en la tabla son fijos, pero que podran
acelerarse las ejecuciones de las actividades hasta un mximo de dos das, excepto L y
Q que slo admiten un mximo de un da. Los costes de acelerar un da el tiempo de
ejecucin de una actividad son los siguientes:
A, C, B y G 6000 K, O, H 12000
D, F, E 8000
I, J, L, Q 10000 M, N, P 5000
Analizar el problema, obteniendo la matriz de pagos, la frontera de Pareto, la mejor
solucin compromiso suponiendo igualdad de preferencias, y la solucin por metas,
planteando como niveles de aspiracin 60 das de tiempo, y un coste de 50000.
Nota: El siguiente modelo sirve para representar las precedencias y las reducciones de
tiempo en la duracin de las tareas, y obtener el tiempo del proyecto y el coste.
X C + X H + X B + X E + X G + X N = 150000
X H 31755
X B 40000
X E 5000
X G 12845
X N 53000
X i 0 i
19/02/2010 291
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
5,85 X C + 8, 24 X N + 5 X G + 9 X E + 12 X B + 6 X H
Coste :
150000
1015 X C + 401X G
Emisiones :
150000
Matriz de pagos
Coste Emisiones
Coste 5,777 962,421
Emisiones 8,398 84,413
Por el procedimiento de ponderaciones la tabla para obtener la frontera de Pareto es:
Frontera de Pareto
1000
Emisiones (g/kWh)
800
600
400
200
0
5 6 7 8 9
Coste (c/kWh)
292 19/02/2010
MTODOS DE OPTIMIZACIN
Tabla resultados
e Coste Emisiones C N G E B H
0 8,3984 84,4123 7400 53000 12845 5000 40000 31755
0,1 7,8664 172,2132 20375,5 53000 12845 5000 27024,5 31755
0,2 7,3344 260,0141 333501 53000 12845 5000 14049 31755
0,3 6,8024 347,8149 46326,5 53000 12845 5000 1073,5 31755
0,4 6,5434 435,6158 59302 46098 12845 0 0 31755
0,5 6,3367 523,4167 72277,5 33122,5 12845 0 0 31755
0,6 6,1299 611,2176 85253 20147 12845 0 0 31755
0,7 5,9232 699,0185 98228,5 7171,5 12845 0 0 31755
0,8 5,8031 786,8193 111204 0 12845 0 0 25951
0,9 5,7902 874,6202 124179,5 0 12845 0 0 12975,5
1 5,7772 962,4211 137155 0 12845 0 0 0
y el grfico obtenido:
Frontera de Pareto
1000
Emisiones (g/kWh)
800
600
400
200
0
5 5,5 6 6,5 7 7,5 8 8,5 9
Coste (c/kWh)
Para buscar la mejor solucin compromiso, primero lo hacemos con la mtrica L1,
normalizando la distancia al ideal de los criterios, y agregado de forma lineal en un
objetivo en que multiplicamos por 0,5 cada una de esas distancias (dado que dice que se
considere igualdad de preferencias). Con ello, obtenemos la solucin:
C N G E B H
52400 53000 12845 0 0 31755
con los siguientes valores de ambos criterios:
Coste 6,65343333
Emisiones 388,9123
19/02/2010 293
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Por ltimo, aplicamos la programacin por metas con un 125% respecto al ideal
para ambos criterios, lo que supone un nivel de aspiracin para el coste de 7,22 c/kWh
y para las emisiones de 106 g/kWh. Suponemos preferencias iguales como en el caso
compromiso. Por otra parte, podemos hacerlo mediante metas ponderadas o
Tchebychev. Se tiene la solucin por metas ponderadas:
C N G E B H
10590,3005 53000 12845 5000 36809,6995 31755
cuyo coste y emisiones son:
Coste 8,26763101
Emisiones 106
siendo las desviaciones
n p
Desviaciones coste 0 1,04763102
Desviaciones emisiones 0 0
Como puede observarse, se cumple la meta de emisiones, y para esa meta se obtiene el
coste correspondiente.
C N G E B H
12677,6333 53000 12845 5000 34722,3667 31755
con coste y emisiones
Coste 8,18205037
Emisiones 120,124285
y desviaciones
n p
Desviaciones coste 0 0,96205037
Desviaciones emisiones 0 14,1242852
que suponen para ambos criterios un incumplimiento respecto al nivel de aspiracin de
un 13%.
294 19/02/2010
MTODOS DE OPTIMIZACIN
19/02/2010 295
PROGRAMACIN MATEMTICA EN DECISIN MULTICRITERIO
Frontera de Pareto
120
100
80
Coste
60
40
20
0
55 57 59 61 63 65 67 69
Tie m po
Tabla resultados
Lambda Tiempo Coste
0 70 0
0,1 67,7333 11,6
0,2 65,8 23,2
0,3 63,9 34,8
0,4 62,45 46,4
0,5 61,3846 58
0,6 60,4923 69,6
0,7 59,74 81,2
0,8 59,16 92,8
0,9 58,58 104,4
1 58 116
Frontera de Pareto
120
100
80
Coste
60
40
20
0
55 57 59 61 63 65 67 69
Tiempo
296 19/02/2010
MTODOS DE OPTIMIZACIN
Tiempo 62 0,33333
Coste (miles de euros) 50 0,43103
aplicando las siguientes reducciones: A, D, G, P 2 das
Tiempo 62
Coste (miles de euros) 50
que cumple la meta del coste pero no la del tiempo, con reducciones: A, D, G, P 2 das.
Tiempo 61,8795
Coste (miles de euros) 51,5663
que incumple ambas metas, en un 3,1% respecto a su nivel de aspiracin, con las
reducciones: A, D, G, P 2 das y F y M 0,1205 das.
19/02/2010 297