03 Mco Goal Programming

Optimización Multicriterio Programación por Metas Goal Programming (GP) Ultima modificación: Enero 20, 2008

Andrés L. Medaglia, Ph.D. Departamento de Ingeniería Industrial Universidad de los Andes http://wwwprof.uniandes.edu.co/~amedagli [email protected] g @ Fuentes: Steuer (1989)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

Introducción ƒ Charnes y Cooper (1955, 1961) ƒ La idea fundamental de programación por metas ( (goal l programming) i ) es lla d de obtener bt un nivel i ld de aspiración para cada criterio. ƒ G GP es de ut utilidad dad cua cuando do se co conocen oce metas etas explícitas o umbrales para los criterios. ƒ Usualmente una solución que satisface todas las metas no es factible. factible ƒ Se intenta encontrar una solución factible que satisfaga las metas de la mejor forma posible. Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

2

Tipos de metas goal{zi = ci x}(zi ≥ ti )

ƒ Mayor o igual (≥) U

ti

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

zi

3

Tipos de metas ƒ Menor o igual (≥)

goal{zi = ci x}(zi ≤ ti )

U

ti

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

zi

4

Tipos de metas ƒ Igualdad (=)

goal{zi = ci x}(zi = ti )

U

ti Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

zi

5

Tipos de metas

[ ])

goal{zi = c i x}(zi = til , tiu

ƒ Rango U

til Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

tiu

zi

6

Ejemplo 1 goal{z1 = c1x}(z1 ≥ t1 ) goal{z2 = c 2x} (z2 ∈ t2l , t2u ) sa s.a., x2 t1 x∈S x2

[

]

conjunto utópico

t2u

c

2

= [12 ,1]

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

S

t2l

1

x c1 = [1, 12 ]

x1 7

Ejemplo 1 x2

x

conjunto utópico z2

t1

t2u

2

z 2 = [2 12 ,5]

t2l t2u

c = [ ,1] 2

1 2

S

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

Z

t2l

1

x c1 = [1, 12 ]

z1 = [4 12 ,3]

x1

z1 t1 8

Objetivo de GP

El objetivo de GP es encontrar una solución factible en S cuyo vector de criterios “mejor” j se aproxime p al conjunto j utópico (en el espacio de criterios).

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

9

Ejemplo 2 goal{z1 = c x}(z1 = t1 ) goal{z2 = c 2x}(z2 = t2 ) goal{z3 = c 3x}(z3 = t3 ) s.a., x∈S 1

x2 t1 1

c

c2

S

c ƒ Conjunto utópico ƒ ¿en espacio de las decisiones? ƒ ¿en espacio de los criterios? Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

t2

3

t3 10

x1

Modelo Arquimediano de GP ƒ El objetivo es encontrar soluciones en S cuyos vectores de criterio estén lo más cercano posible, con base en una na métrica ponderada L1, al conj conjunto nto utópico en el espacio de criterios.

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

11

Ejemplo 3 goal{z1 = c1x}(z1 ≥ t1 )

goal{z2 = c 2x}(z2 = t2 )

[ ])

goal{z3 = c 3x}(z3 ∈ t3l , t3u s.a., x∈S

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

c1x + d1− ≥ t1 c 2x + d 2− − d 2+ = t2 c 3x + d 3− ≥ t3l c 3x − d 3+ ≤ t3u

12

Ejemplo 3 (cont.) min w1− ⋅ d1− + w2− ⋅ d 2− + w2+ ⋅ d 2+ + w3− ⋅ d 3− + w3+ ⋅ d 3+ s.a., c1x + d1− c 2x

+ d 2−

c 3x c 3x

− d 2+ + d 3− − d 3+

≥ = ≥ ≤

t1 t2 t3l t3u

d1− , d 2− , d 2+ , d 3− , d 3+ ≥ 0 x∈S Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

13

Modelo Arquimediano de GP ƒ Los w´s son pesos positivos en la función objetivo. ƒ Cada meta genera una restricción, excepto las metas de rangos que generan dos dos. ƒ Sólo las desviaciones indeseables deben ser incorporadas en la formulación. ƒ Las L restricciones ti i d de meta t son bl blandas d ((soft) ft) y “aumentan” “ t ” ell espacio original (mayor dimensión). ƒ La función objetivo Arquimediana es una suma ponderada de las desviaciones indeseables. ƒ El programa lineal resultante puede ser resuelto con métodos/software convencional de PL. Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

14

Diferentes grados en las penalizaciones

[ ]

zi ∈ til , tiu

wi+

wi− til

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

tiu

zi

15

Diferentes grados en las penalizaciones

[ ]

wi−,3

zi ∈ til , tiu

wi+, 2 wi−, 2 wi−,1

wi+,1 til

tiu

zi

ƒ ¿Cómo incorporar estos grados en las penalizaciones en el modelo? Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

16

Modelo Lexicográfico de GP ƒ Las metas se organizan de acuerdo a prioridades prioridades. ƒ Las metas de la más alta prioridad son consideradas infinitamente más importantes p q que las metas de segunda prioridad; las de segunda prioridad son infinitamente más importantes que las metas de tercera prioridad; ... goal{z1 = c1x} P1 (z1 ≤ t1 ) goal{z2 = c 2 x} P2 (z2 ≥ t2 )

goal{z3 = c 3x} P3 (z3 = t3 ) s.a.,, x∈S Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

Pj >>> Pj +1

17

Ejemplo 4 goal{z1 = c1x} P1 (z1 ≤ t1 )

goal{z2 = c 2 x} P2 (z2 ≥ t2 )

goal{z3 = c 3x} P3 (z3 = t3 ) s.a., x∈S

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

c1x − d1+ ≤ t1 c 2x + d 2− ≥ t2 c 3x + d 3− − d 3+ = t3

18

Ejemplo 4 (cont.) min{P1 (d1+ ) + P2 (d 2− ) + P3 (d 3− + d 3+ )} ó lex min{d1+ , d 2− , d 3− + d 3+ }

s.a.,

c1x − d1+ c 2x c 3x

+ d 2− + d 3−

− d 3+

≤

t1

≥

t2

=

t3

d1+ , d 2− , d 3− , d 3+ ≥ 0 x∈S Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

19

Ejemplo 4 (cont.) ƒ Esquema Esq ema de sol solución: ción ƒ Primera etapa:

s.a.,

min d1+

x , (d

c1x − d1+ ≤ t1

*

+ 1

d ≥0 x∈S no FIN Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

)

+ * 1

¿óptimos alternos?

si 2a etapa 20

Ejemplo 4 (cont.) ƒ Segunda S d etapa: t

s.a.,

min d 2−

c x ≤ t1 + (d c 2x + d 2− ≥ t2 d 2− ≥ 0 x∈S 1

)

+ * 1

x , (d *

no FIN Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

)

− * 2

¿óptimos alternos?

si 3a etapa

21

Ejemplo 4 (cont.) ƒ Tercera T etapa: t

min d 3− + d 3+ s.a., 1 + * c x ≤ t1 + (d1 ) * c 2x ≥ t2 − (d 2− ) c 3x + d 3− − d 3+ = t3 d 3− , d 3+ ≥ 0 x∈S

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

x , (d *

) , (d )

− * 3

+ * 3

FIN

22

Observaciones al modelo lexicográfico ƒ Las etapas no se pueden resolver simultaneamente simultaneamente, sino secuencialmente. ƒ Proceso dinámico de solución ((varios PLs en cadena) ƒ Las metas de baja prioridad pueden no llegar a influir el proceso de solución. ƒ No existe compromiso entre los criterios. ƒ Alternativa: relajaciones

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

23

Ejemplo 5 goal{z1 = c x} P1 (z1 ≥ t1 ) goal{z2 = c 2 x} P2 (z2 ≥ t2 ) s.a., x∈S 1

t2

x2

t1

c1

S

x1

c2 Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

24

Ejemplo 5 (cont.) ƒ Primera Pi etapa: t

min d1−

s.a., c1x + d1− ≥ t1 d1− ≥ 0 x∈S

t2

x2

(x )

t1

1 *

c1

S

x1

c2

ƒ ¿Cómo buscar un mejor compromiso entre los criterios? Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

25

Ejemplo 5 (cont.) ƒ Segunda S d etapa t ((con relajación): l j ió )

t2

x2

min d

− 2

s.a., 1 − * c x ≥ t1 − (d1 ) − Δ1 c 2x + d 2− ≥ t2 d 2− ≥ 0 x∈S

(x )

1 *

(x )

2 *

Δ1

c1

t1

S

x1

c2 Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

26

Simplex lexicográfico goal{z1 = x2 } P1 (z1 ≥ 5)

goal{z2 = − x1 − x2 } P2 (z2 ≥ 4 ) goal{z3 = x3 } P3 (z3 ≥ 3) sa s.a., x2 ≤ 2 x3 ≤ 3 x1 , x2 , x3 ≥ 0

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

27

Simplex lexicográfico (cont.)

{

lex min d1− , d 2− , d 3− sa s.a., − x1

} + d1−

x2 − x2

+ d 2− x3

x2 x3

+ d 3−

≥ ≥ ≥ ≤ ≤

5 4 3 2 3

x1 , x2 , x3 , d1− , d 2− , d 3− ≥ 0 Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

28

Simplex lexicográfico (cont.)

s.a.,

x , d, s ≥ 0

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

29

Simplex lexicográfico (cont.)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

30

Simplex lexicográfico (cont.)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

31

Simplex lexicográfico (cont.)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

32

Simplex lexicográfico (cont.)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

33

Simplex lexicográfico (cont.)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

34

Simplex lexicográfico (cont.)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

35

Simplex lexicográfico (cont.)

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

36

Minimización de la máxima desviación goal{z1 = c1x} P1 (z1 = t1 ) goal{z2 = c 2 x} P2 (z2 ≥ t2 ) goal{z3 = c 3x} P2 (z3 ≥ t3 ) goal{z4 = c 4x} P2 (z4 ≥ t4 ) s.a., x∈S

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

P2

mín. máx. desviación

37

Minimización de la máxima desviación goal{z1 = c1x} P1 (z1 = t1 )

goal{z2 = c 2 x} P2 (z2 ≥ t2 ) goal{z3 = c 3x} P2 (z3 ≥ t3 ) goal{z4 = c 4x} P2 (z4 ≥ t4 ) 0

d 4−

d 2− d 2− ≤ d d 3− ≤ d d 4− ≤ d

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

c1x − d1+ + d1− = t1 c 2x + d 2− ≥ t2 c 3x + d 3− ≥ t3

c 4x + d 4− ≥ t4 d 3−

d

min d

38

Minimización de la máxima desviación lex min{d1− + d1+ , d } s.a.,1 c x − d1+ + d1− c 2x c 3x c 4x

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

= + d 2− ≥ + d 3− ≥ + d 4− ≥ ≤ d 2− d 3− ≤ d 4− ≤ d1+ , d1− , d 2− , d 3− , d 4− , d ≥ 0 x∈S

t1 t2 t3 t4 d d d

39

Referencias ƒ ƒ ƒ

Charnes, A Charnes A., W W. W W. Cooper and Ferguson Ferguson, R R. (1955) (1955). Optimal estimation of executive compensation by linear programming. Management Science 1, pp. 138–151. Charnes, A. and Cooper, W. W. (1961). Management models and industrial applications of linear programming. New York: Wiley. St Steuer, R R. (1989) (1989). M Multiple lti l criteria it i optimization: ti i ti th theory, computation t ti and d application. li ti Malabar (FL, USA): Krieger.

Andrés L. Medaglia Departamento de Ingeniería Industrial Centro de Optimización y Probabilidad Aplicada http://copa.uniandes.edu.co/

40