• Author / Uploaded
• Ada Quispe R

Citation preview

DPTO. ECONOMÍA GENERAL Y ESTADÍSTICA UNIDAD DOCENTE DE ESTADÍSTICA Y ECONOMETRÍA. UNIVERSIDAD DE HUELVA

TÉCNICAS DE DECISIÓN MULTICRITERIO 2003--2004 2003 LICENCIATURA EN CIENCIAS AMBIENTALES

TEMA 3: PROGRAMACIÓN MULTIOBJETIVO

Profesora: Concepción Cortés Rodríguez 1

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.1 Aspectos básicos 3.2. Ejemplo ilustrativo 3.3. La matriz de pagos en la programación multiobjetivo 3.4. Método de las Restricciones 3.5. Método de las Ponderaciones 3.6. Otras técnicas multiobjetivo: un breve comentario 3.7. Algunas observaciones sobre la programación multiobjetivo

2

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.1. Aspectos Básicos • Formulación de un problema multiobjetivo:

Eff f(x) = [f1(x), f2(x),..., fp(x)] s.a.

x∈ℑ ∈ℑ

Eff : búsqueda de soluciones eficientes o Pareto óptimas en el sentido “maximizar” (+ del atributo mejor) o “minimizar” (- del atributo mejor)

fi(x): expresión del atributo i-ésimo (i = 1, 2, ..., p) x= (x1, x2, ..., xn) : vector de variables de decisión ℑ: conjunto de restricciones que definen el conjunto de soluciones posibles o factibles (generalmente son lineales) Para resolver este problema utilizaremos técnicas generadoras de soluciones eficientes, 3

como el método de la restricción y el método de la ponderación.

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.2. Ejemplo Ilustrativo • Planificación de la producción de una papelera: Variables

Restricciones

Supongamos una empresa que está considerando la posibilidad de planificar la producción de una papelera de propiedad pública en la que existen dos posibles productos: pulpa de celulosa obtenida por medios mecánicos y pulpa de celulosa obtenida por medios químicos. Las capacidades máximas de producción se estiman en 300 y 200 toneladas/día para cada uno de los dos tipos de pasta de celulosa. Cada tonelada de pasta de celulosa producida demanda un jornal. La empresa dispone de una plantilla de 400 trabajadores, no deseando contratar mano de obra eventual. El margen bruto (ingresos menos costes variables) por tonelada de pasta de celulosa obtenida por medios mecánicos se estima en 1.000 u.m. y en 3.000 u.m. la obtenida por medios químicos. Los costes de la papelera se estiman en 300.000 u.m./día. La empresa desearía, al menos, cubrir los costes fijos.

Objetivos

Las preferencias de la empresa se concretan en la maximización del margen bruto (objetivo económico) y en la minimización del daño generado en el río en el que la papelera vierte sus residuos productivos (objetivo ambiental). Se estima que los residuos producidos por cada tonelada 4 de pasta de celulosa obtenida por medios mecánicos y por medios químicos generan unas demandas biológicas de oxígeno en las aguas del río de 1 y 2 unidades.

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.2. Ejemplo ilustrativo: Planificación de la producción de una papelera • Formulación del problema Variables de decisión: x1 a las toneladas diarias de pulpa de celulosa obtenida por medios mecánicos y x2 a las toneladas diarias de pulpa de celulosa obtenida por medios químicos

Atributos:

f1(x) = 1000x 1 + 3000x 2 f2(x) = x1 + 2x2

(margen bruto) (demanda biológica de O 2 )

Max f1(x) = 1000x 1 + 3000x2 Min f2(x) = x 1 + 2x2

(margen bruto) (demanda biológica de O 2 )

Funciones objetivo:

Restricciones: x1 + x 2 ≤ 400

(empleo)

1000x1 + 3000x 2 ≥ 300000

(margen bruto)

x1 ≤ 300

(capacidades de producción)

x2 ≤ 200 x1, x 2 ≥ 0

5

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.2. Ejemplo ilustrativo: Planificación de la producción de una papelera • Formulación matemática Buscamos las soluciones eficientes del siguiente problema con dos objetivos (bi-objetivo):

Eff f(x) = [f1(x), f2(x)] donde: f1(x) = 1000x 1 + 3000x2 f2(x) = x1 + 2x2

(margen bruto) (demanda biológica de O 2 )

sujeto a:

x∈ℑ

x1 + x 2 ≤ 400

(empleo)

1000x1 + 3000x 2 ≥ 300000

(margen bruto)

x1 ≤ 300

(capacidades de producción)

x2 ≤ 200 x1, x 2 ≥ 0 6

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.2. Ejemplo ilustrativo: Planificación de la producción de una papelera • Representación de las soluciones o posibles (región factible) en el espacio de las variables

Puntos extremos: A= (0, 100) B= (0, 200) C= (200, 200) D= (300, 100) E= (300, 0)

Soluciones Eficientes: Los segmentos AB y BC

7

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.2. Ejemplo ilustrativo: Planificación de la producción de una papelera • Representación de las soluciones o posibles (región factible) en el espacio de los objetivos

Puntos extremos: A´= (300.000, 200) B´= (600.000, 400) C´= (800.000, 600) D´= (600.000, 500) E´= (300.000, 300)

Soluciones Eficientes: Los segmentos A´B´ y B´C´

8

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.3. Matriz de pagos (pay-off matrix) Ejemplo: Planificación de la producción de una papelera MATRIZ DE PAGOS

Margen Bruto Demanda Biológica de O2

Margen Bruto

Demanda biológica de O2

800.000 300.000

600 200

• Es una matriz cuadrada, cuya dimensión 2x2 coincide con el número de objetivos. • Se calcula optimizando cada objetivo separadamente y calculándose seguidamente los valores alcanzados por los demás objetivos en cada solución óptima. Utilidad: Permite cuantificar el nivel de conflicto existente entre los objetivos en cada solución 9 óptima.

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.3. Matriz de pagos (pay-off matrix)

PRIMERA FILA DE LA MATRIZ DE PAGOS Max f1(x) = 1000x 1 + 3000x2

margen bruto

sujeto a: x1 + x 2 ≤ 400

(empleo)

1000x1 + 3000x 2 ≥ 300000

(margen bruto)

x1 ≤ 300

(capacidades de producción)

x2 ≤ 200 x1, x 2 ≥ 0 f2(x) = x 1 + 2x 2

demanda biológica de O 2

Solución: (x 1, x 2) = (200, 200)

(f1, f2) = (800.000, 600)

10

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.3. Matriz de pagos (pay-off matrix) SEGUNDA FILA DE LA MATRIZ DE PAGOS Min f2(x) = x1 + 2x 2

demanda biológica de O 2

sujeto a: x1 + x 2 ≤ 400

(empleo)

1000x1 + 3000x 2 ≥ 300000

(margen bruto)

x1 ≤ 300

(capacidades de producción)

x2 ≤ 200 x1, x 2 ≥ 0 f1(x) =1000 x 1 + 3000x2

margen bruto

Solución: (x 1, x 2) = (0, 100)

(f1, f2) = (300.000, 200)

11

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.3. Matriz de pagos (pay-off matrix) • PUNTO IDEAL: La solución en la que todos los objetivos alcanzan su valor óptimo. Coincide con los elementos de la diagonal principal de la matriz de pagos. En la mayoría de los contextos decisionales reales el punto ideal es inalcanzable. (f1, f2) = (800.000, 200)

• PUNTO ANTI-IDEAL: Es el peor elemento de cada columna de la matriz de pagos. Coincide con el mínimo (máximo) de la columna si el objetivo correspondiente se maximiza (minimiza). (f1, f2) = (300.000, 600)

12

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.4. Método de las Restricciones Fue Propuesto por Marglin en 1967. Consiste en optimizar uno de los objetivos, mientras que el resto de los objetivos se incorporan al modelo en forma de restricciones paramétricas.

Formulación: Función objetivo

P(Li):

Opt fk(x) Objetivo fi a maximizar

sujeto a: Restricciones fijas

x∈ℑ

Restricciones paramétricas

fi (x) ≥ Li

i = 1,2, ..., k−1, k+1, ..., p

{Valor anti-ideal del objetivo i} ≤ Li ≤ {Valor ideal del objetivo i} • Genera puntos eficientes extremos e interiores sólo cuando las restricciones paramétricas fi (x) = Li. • Si no se da la igualdad y además existen óptimos alternativos, entonces la solución del problema P(Li) puede no ser eficiente. • Cuando algunas de las cotas Li son altas, los problemas P(Li) pueden ser infactibles. • Este método requiere rp-1 pasadas de computador con r= nº de valores que se dé a los parámetros Li. 13 • Uno de los softwares disponibles que resultan más útiles para este método es el LINGO.

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.5. Método de las Ponderaciones Fue propuesto por Zadeh en 1963. Se optimiza una función objetivo en la que se han agregado y ponderado todos los objetivos.

Formulación: Función objetivo

P(W): Opt w1f1(x) + w2f2(x) + ... + wpfp(x)

Restricciones fijas

sujeto a:

x∈ ℑ W= (w1, w2, ..., wp) ≥ 0

+: objetivos a maximizar -: objetivos a minimizar

• Los pesos W elegidos no guardan ninguna relación con las preferencias del decisor. • Se aconseja comenzar resolviendo los problemas con pesos (1,0,0,...,0), (0,1,0,...,0), ..., (0,0,...,1). • Genera puntos extremos eficientes sólo cuando todos los wi > 0. • Si alguno de los pesos es cero y además existen óptimos alternativos, entonces la solución generada por el problema P(W) puede ser no eficiente. • Uno de los softwares disponibles que resultan más útiles para este método es el LINGO.

14

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.5. Método de las Ponderaciones Observaciones: • Este método, al igual que el método de las restricciones, no conduce siempre a una representación completa del conjunto eficiente, garantizando solamente una aproximación del mismo. • Por un lado, combinaciones distintas de los pesos wi pueden llevar a un mismo punto extremo, con lo que el esfuerzo informático realizado no aporta nueva información. Una cota superior del número de puntos factibles extremos en un problema lineal con n variables (incluyendo las de holgura) y m restricciones es:

n  n!   =  m  m!(n − m)!

• Alguno de los problemas P(W) puede resultar infactible. • Si la solución del problema P(W) es única entonces es una solución eficiente. • Este método requiere la realización de rp-1 pasadas de computador con r= nº pesos W ensayados. • El método de las ponderaciones se puede usar conjuntamente con el método de las restricciones obteniéndose el llamado método híbrido de las ponderaciones y restricciones.

15

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.6. Otras técnicas multiobjetivo: un breve comentario Método NISE: Inicialmente fue propuesto por Cohon en 1979. • Permite una rápida y buena aproximación del conjunto eficiente con dos objetivos. • Genera puntos eficientes basándose en el método de las ponderaciones y es válido para cualquier número de variables y de restricciones. • La elección de los pesos wi no es arbitraria. • La evaluación de la eficiencia de segmentos que unen puntos eficientes adyacentes extremos se hace con la elección de los pesos w1 y w2 de la función objetivo de forma que: w1 / w2 = pendiente de la recta que une los puntos extremos eficientes de la iteración anterior, comenzando con los puntos de la matriz de pagos • En 1985, Balachandran y Gero extendieron el método NISE al caso de tres objetivos. 16

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.6. Otras técnicas multiobjetivo: un breve comentario Simplex Multicriterio: Fue propuesto por Philip (1972) y Zeleny (1973). Es válido sólo para problemas multiobjetivos lineales. • Es el único método multiobjetivo que genera todos los puntos extremos eficientes. Se basa en el algoritmo del simplex, desplazándose de un punto extremo a otro punto extremo adyacente. Proporciona pues, una representación exacta del conjunto eficiente. • Su principal inconveniente es la enorme complejidad de los cálculos que se necesitan para su implementación. • Los softwares disponibles basados en este método resultan útiles sólo para problemas con un tamaño moderado. • ADBASE (diseñado en EE.UU. por el profesor Steuer, 1983): admite hasta 50 variables, 50 restricciones y un máximo de 3 objetivos. • MLP (desarrollado por Zeleny en 1973 y comercializado por una empresa holandesa de ordenadores): en teoría para 50 variables, 50 restricciones y un máximo de 8 objetivos. En la 17 práctica, para problemas de tamaño mucho más reducido.

TEMA 3. PROGRAMACIÓN MULTIOBJETIVO

3.7. Algunas observaciones sobre la programación multiobjetivo Debilidades del Método de las Restricciones y de las Ponderaciones • Pueden dejar pasar por alto alguno de los puntos eficientes. Solución En el método de las restricciones: Aumentar el número de valores que le demos a Li. En el método de las ponderaciones: Reducir la escala de los pesos.

Debilidades de los Métodos Multiobjetivo • En general, generan un número de puntos extremos eficientes muy elevado. Solución 1.- Trabajar con intervalos de pesos en lugar de pesos fijos (Steuer, 1976) 2.- Recurrir a técnicas de “poda” y “filtrado” (Steuer y Harris, 1980): Se descartan soluciones eficientes 18 que sean muy parecidas a otras soluciones eficientes previamente calculadas.