1 APLICACIÓN DE LA PROGRAMACIÓN LINEAL A LA RESOLUCIÓN DE PROBLEMAS COMPLEJOS – EL MÉTODO SIMUSNolberto Munier

2 Objetivo de este seminarioDemostrar la factibilidad de la Programación Lineal (PL) para la resolución de problemas complejos, y presentación del método Simus (Sequential Interactive Model for Urban Systems), como un método alternativo para la resolución de problemas de decisión, aunque se basa en una metodología diferente a los modelos que habéis visto (Promethee y AHP/ANP). El método Simus está apoyado en la PL y está diseñado para aumentar el empleo de esta herramienta en la solución de problemas multiobjetivos y con restricciones cualitativas, ya que la PL normalmente no puede resolver este tipo de problemas, que son por otro lado los más comunes en la realidad. La PL es una técnica matemática desarrollada por el ruso Leonid Kantórovich durante la Segunda Guerra Mundial para optimizar el empleo de los recursos del país. El algoritmo de resolución de problemas lineales ha sido desarrollado por el norteamericano Georges Dantzig y recibió el nombre de ‘Simplex’. Este algoritmo se encuentra como componente de Excel y es el que se empleará en esta presentación, aunque hay muchos programas computacionales para resolver este problema, y naturalmente todos deben alcanzar resultados similares. En consecuencia ustedes lo tienen en sus ordenadores bajo el nombre de ‘Solver’, si usan la plataforma Microsoft. La PL se apoya en el algebra lineal y trabaja con matrices para resolver las incógnitas de un sistema de ecuaciones lineales. Existe también la Programación No Lineal que opera con un algoritmo diferente.

3 Resolución de problemas de decisión mediante programación linealPlanteo de un problema de toma de decisiones Se construye la matriz de decisión con alternativas en columnas ( j ), y restricciones o criterios en filas ( i ) (o viceversa). En la intersección de una fila con una columna se coloca un valor numérico ( aij ) que indica en cuánto contribuye cada alternativa a lo requerido por una restricción o criterio determinado. Este enfoque es diferente al que habéis visto para AHP y Promethee, y sigue el formato de un sistema de ecuaciones en donde las incógnitas (xj) están en columnas en tanto que las ecuaciones forman las filas. Por otro lado, se debe establecer una acción que indique para cada criterio qué es lo que se desea que ese criterio cumpla. Así, en un criterio relacionado con costes, habrá interés en minimizarlos, en tanto que en un criterio relacionado con beneficios en maximizarlos. Los criterios pueden ser cuantitativos (Kg, €, m2, mg/m3 , etc.), o responder a expresiones cualitativas tales como (bueno, malo, de acuerdo, satisfactorio, etc.). Estas expresiones verbales deben expresarse en valores numéricos empleando determinadas escalas, por ejemplo entre 1 (oposición completa) a 10 (acuerdo completo). Si no se conocen estos valores (aij) puede emplearse el modelo AHP para generarlos.

4 Matriz normal de decisión

5 Matriz de decisión en programación lineal

6 Esta matriz representa un sistema de inecuaciones del siguiente tipo:Conversión de la matriz de decisión en una formulación algebraica de inecuaciones Esta matriz representa un sistema de inecuaciones del siguiente tipo: a a a a ≤ b1 [La contaminación ambiental debe ser menor que este valor máximo permitido (por razones medioambientales)] a a a a ≥ b2 [La producción eléctrica debe ser mayor que este valor mínimo admisible (debido a economías de escala)] a a a a ≥ b3 [La TIR debe ser mayor que este valor mínimo estimado (considerando el rendimiento otras inversiones potenciales)] a a a a = b4 [La inversión debe ser igual a la cantidad de fondos (de acuerdo a los montos disponibles)]

7 Expresión matricial del sistema de inecuaciones

8 Matriz de decisión para un caso de energía renovable

9 Conversión de la matriz de decisión en una formulación algebraicaEl cuadro anterior puede ponerse en forma de ecuaciones, tal como: A) Índice de eficiencia: ES FV ≤ [Es obvio que la eficiencia debe ser menor que 1] B) Índice financiero: ES FV ≥ [Este índice debe ser mayor que 0,84] C) Índice de uso de la tierra: ES FV ≤ [Se ha fijado que debe ser menor que 0,94] D) Índice de generación total: ES FV ≥ [Se ha fijado que debe ser mayor que 0,80]

10 Representación gráfica del problema

11 Dual del problema anteriorEl problema resuelto se denomina ‘Problema directo’. Si en lugar de considerar alternativas en columnas las ponemos en filas y los criterios en columnas, y resolvemos el sistema, estaríamos entonces en un espacio de cuatro dimensiones (criterios A, B, C y D), y que no podemos resolver en forma gráfica. Este problema de denomina ‘Problema dual’ y su resultado tiene una significación distinta al problema directo. En efecto, en el problema directo la solución indica la participación de cada alternativa en la obtención del objetivo, o sea la importancia de cada alternativa, lo cual permite su ordenamiento. La solución del problema dual en cambio suministra los valores marginales de los criterios, es decir indica en cuánto se modifica el funcional cuando el umbral de un criterio se varia en una unidad, lo cual también puede interpretarse como una medida de la importancia de cada criterio. Sin embargo, el valor del funcional es el mismo para ambos problemas.

12 Análisis de sensibilidadLa existencia del dual tiene una gran importancia para realizar ‘análisis de sensibilidad’, algo que es fundamental en selección de proyectos debido a la imprecisiones que siempre existen, ya sea por falta de datos fidedignos, o en la fijación de pesos para los criterios que emplean otros modelos - aunque no la PL - o sencillamente porque hay factores externos al proyecto con los cuales nada podemos hacer, pero que tienen una gran importancia en la selección. Un ejemplo es la evolución de los precios de venta, confiabilidad en el abastecimiento, factores meteorológicos, etc. Este análisis de sensibilidad nos puede indicar, para una solución hallada, entre qué limites pueden variar ciertos parámetros para que la solución siga siendo válida, y en cuánto debe aumentar el beneficio o disminuir el coste de una alternativa para que ésta figure en la solución.

13 Planteo para la resolución por Solver

14 Instalar Solver Colocar los datos de la matriz de decisión en Excel. A continuación trasladar los datos al Solver. Si Solver no esta instalado proceder en este orden: Ir a ‘Opciones de Solver’ Ir a ‘Complementos’ Oprimir ‘Ir’ Tildar la casilla que dice ‘Solver’ Volver a Excel Ir a ‘Datos’ ‘? Solver’ aparecerá en la parte superior derecha de Excel. Oprimir ahí y se verá el cuadro ‘Parámetros de Solver’ y que se muestra a continuación:

15 Operación con Solver

16 Opciones de Solver

17 Valores del dual

18 Desventajas del modelo de programación linealEste modelo tiene una gran desventaja que consiste en que sólo admite una función objetivo, cuando en realidad en los casos reales existen varias. Por ejemplo, se quiere maximizar el beneficio (objetivo 1), pero al mismo tiempo, reducir los costos (objetivo 2), llevar a un mínimo la contaminación ambiental (objetivo 3), y maximizar el empleo de los recursos (objetivo 4), y es obvio que algunos de estos objetivos pueden estar mutuamente opuestos. Se han hecho muchos esfuerzos para solucionar este problema por diversos investigadores tales como Charnes y Cooper, y otros, que desarrollaron métodos como la Programación por metas, el Simplex multicriterio y el método de las ε-restricciones. Estos métodos pueden trabajar con varios objetivos aunque en número limitado y en problemas relativamente sencillos, por lo que su aplicación no se ha extendido.

19 Métodos heurísticos para resolver problemas de decisiónExisten sin embargo métodos heurísticos que sí pueden trabajar con varios objetivos en forma eficiente, pero que están limitados a problemas relativamente poco complejos, con pocas alternativas y restricciones, y que no encuentran un óptimo, pero sí una solución satisfaciente que en muchos casos es para el decisor más importante que hallar el óptimo. Estos modelos son: AHP/ANP, Electre, Promethee, Topsis y varios otros. Por este motivo y para aprovechar las ventajas de la PL se desarrolló el método Simus que puede tratar problemas con cualquier número de objetivos y con restricciones de tipo cualitativo, otro de los aspectos que la PL no puede resolver.

20 El método Simus Como ejemplo del método Simus consideremos un caso con 3 alternativas (A,B;C), 3 objetivos, y 10 criterios. Para resolver se procede de esta manera: Construir la matriz de decisión con las 3 alternativas y que se añaden a los criterios como ‘metas’. Se muestra a continuación la matriz de decisión de partida. Seleccionar un criterio como objetivo, que se extrae de la matriz de decisión y que se usa como función objetivo # 1 como se muestra. Alternatives A B C Función objetivo Acción Umbrales Meta ≥ Meta ≤ Meta ≤ Criterio ≤ Criterio ≤ Criterio ≥ Criterio ≥

21 El modelo Simus – Extracción de primer objetivo objetivo

22 Modelo Simus- Construcción de la Matriz de Resultados Eficientes (MRE)

23 Restablecimiento de la función objetivo a la matriz de resultados eficientes

24 Modelo Simus – Extracción del segundo objetivo

25 Guía número 1

26 Guía número 2 Tiene por misión determinar el nivel de participación de cada alternativa con respecto a la cantidad de metas. Se han encontrado valores para las alternativas correspondientes a cada meta, cuando esta se usa como función objetivo. Podría suceder que una alternativa obtiene una suma muy alta superando a las otras, simplemente porque tiene valores muy altos en una o dos metas, mientras que otras alternativas obtienen valores suma bajos aunque participen en mas metas pero con valores más pequeños. Es obvio que una alternativa que tiene valores en muchas metas es mas valioso que otro que tiene pocos valores dado que ello demuestra que se elije dicha alternativa para escenarios diferentes.

27 Modelo Simus - Ejemplo de usoPropósito: Elegir una ruta entre tres localidades

28 Normalización

29 Matriz de resultados eficientes

30 Conclusión La programación lineal y su variación, el método Simus, es un modelo que se agrega la batería de modelos existentes y que al igual que estos, modela las preferencias del decisor y los datos cuantitativos de un problema. Se considera sin embargo que presenta las siguientes ventajas: Ausencia, aunque no total, de valores subjetivos como apreciaciones personales, pesos de los criterios, umbrales de aceptación y rechazo, etc. Capacidad para resolver problemas complejos con cualquier cantidad de alternativas y de criterios. Permitir representar más fielmente las características de un problema real, tal como limitación de recursos, incertidumbre, restricciones y condiciones existentes entre alternativas.