1 ¿Optimización por Simualción u Optimización para la Simulación? Universidad Central de Venezuela Escuela de Ingeniería Eléctrica Dr. Ebert Brea Profesor Asociado E-mail: [email protected]
2 Contenido La optimización y la Simulación El algoritmo de Nelder-Mead bajo Restricciones Lineales Método de Particiones Jerarquizadas Optimizando la Simulación Conclusiones n n n n n
3 La optimización y la Simulación Hoy en día la simulación de Sistemas de Eventos Discretos ha constituido ser una poderosa herramienta de análisis de sistemas, como soporte para la toma de decisiones Sin embargo, actualmente está siendo empleada en la optimización de las operaciones de sistemas.
4 La optimización y la Simulación Enfoque Newtoniano: Análisis Infinitesimal de Perturbación Función de Registro Enfoque de Búsqueda Directa Método de Nelder-Mead Patrón de Búsqueda
5 1. El método de N-M bajo Restricciones Sujeto a donde
6 1.1 Definiciones Básicas Símplex completo Diremos que un símplex en el espacio Euclidiano de dimensión d es completo, si la matriz de aristas es de rango completo. Es decir, S nv[q] =[x 1 :x 2 : :x nv-1 :x nv ] E j[q] =[x 1 -x j :x 2 -x j : :x nv-1 -x j :x nv -x j ]
7 Grado de Colapso Decimos que un símplex de d+1 vértices en el espacio Euclidiano de dimensión d ha colapsado en grado r, si los d+1 vértices pertenencen simultaneamente a r fronteras dadas por las restriciones lineales. Restrición activa Una restricción se dicer se activa, si todos los vértices del símplex pertenencen a la frontera de al restrición. 1.2 Definiciones Básicas
8 1.3 Basic definitions Menor Símplex Decimos que un símplex de grado de colapso r está suficientemente definido sobre r fronteras lineales, si su número de vértices v es igual a d+1-r.
9 1.4 Operaciones del NMLR x1x1 x2x2 Reflexión Restringida x ref
10 x1x1 x2x2 Expansión Restringida x ref x exp 1.5 Operaciones del NMLR
11 x1x1 x2x2 Contracción Interna x con 1.6 Operaciones del NMLR
12 x1x1 x2x2 Reducción 1.7 Operaciones del NMLR
13 2.1 Idea básica del algoritmo del NMLR
14
15
16
17
18
19 x min 2.1 Idea básica del algoritmo del NMLR
20 a) Función de Rosenbrock Sujeto a 3.1 Ejemplo numérico
21 SM: Metodo de Subrahmanyam 3.1 Ejemplo numérico
22 b) Función cuadrática Sujeto a 3.2 Ejemplo numérico
23 x inicial =[400, -400, 400, 400] t x min =[50, -15, 22.5, 22.5] t 3.2 Ejemplo numérico
24
25 c) Función de Rosenbrock Sujeto a donde 3.3 Ejemplo numérico
26 x inicial =[20, 20, 20, 20] t x min =[6, 36, 6, 36] t 3.3 Ejemplo numérico
27
28 4. El problema de Optimización Sujeto a donde
29 4.1 Optimización ordinal Sujeto a donde
30 4.2 Optimización via Particiones Jerarquizadas Partición Muestreo Ordenamiento y selección del mejor n n n Más particiones, retroceso o parada n
31 El Método de PJ: Partición 1 (0) 2 (0) 3 (0) 4 (0) 5 (0) (1) := 2 (0) (0) := 1 (1) 3 (1) 2 (1) 4 (1) \ (1) 2 (0)
32 1 (0) 2 (0) 3 (0) 4 (0) 5 (0) (0) = D 1 (0) D 2 (0) D 3 (0) D 4 (0) D 5 (0) (0) = El Método de PJ: Muestreo
33 El método de PJ: Ejemplo, k=0 1 (0) 2 (0) 3 (0) 4 (0) 5 (0) 12 3 4 57 6 9 11 12 13 14 15 16 17 18 8 10 (0) :=
34 2 (1) 1 (1) \ (1) 12 3 4 57 6 9 11 12 13 14 15 16 17 18 8 10 (1) := 2 (0) El método de PJ: Ejemplo, k=1
35 2 (2) 1 (2) \ (2) 12 3 4 57 6 9 11 12 13 14 15 16 17 18 8 10 (2) := 1 (1) El método de PJ: Ejemplo, k=2
36 5. El problema de Optimización Sujeto a donde
37 5.1 Optimización ordinal Sujeto a donde
38 5.2 Optimizando la Simulación Sujeto a donde
39 5.2 Optimizando la Simulación
40 Teorema 1 (Chen-Lin-Yücesan-Chick) Dado un número total de replicas a muestras de simulaciones T a ser adjudicados a k puntos de diseños Ei y cuyo índice de desempeño es medido por con respectivamente. Entonces cuando se tiene 5.2 Optimizando la Simulación
41
42 Inicio Paso 0: Paso 1: Paso 2: Paso 3: Fin 5.2 Optimizando la Simulación
43 n La optimización y la simulación hoy en día representan campos complementarios para la búsqueda de soluciones en sistemas complejos. 6 Conclusiones