Tema 11.

Programación multiobjetivo

Tema 11. PROGRAMACION LINEAL MULTIOBJETIVO

11.1. Introducción a la programación multiobjetivo

11.2 Método de las ponderaciones
11.3 Método de las e-restricciones
11.4 Método simplex multiobjetivo

El problema clásico de la programación matemática lineal consiste en la búsqueda de un

óptimo de una función lineal de varias variables restringido por un conjunto de
ecuaciones y/o inecuaciones lineales. Un enfoque más reciente y realista, no sólo en
programación lineal sino también en optimización y otras áreas de la Investigación
Operativa y Estadística, consiste en la optimización simultánea de varias funciones
objetivo que en muchos casos pueden ser conflictivas, que no es deseable o posible
reducir a una única función objetivo y por tanto hay que tratarlas de una manera
conjunta. Este enfoque se denomina de programación multiobjetivo (o más general, de
decisión multicriterio).

1/9
 Tema 11. Programación multiobjetivo

11.1. Introducción a la programación multiobjetivo

Existen muchas aplicaciones en que el proceso de modelización matemática conduce a

un problema con varios objetivos que pueden ser total o parcialmente conflictivos, de
manera que la mejora en cualquiera de ellos puede empeorar el valor de otros.
La formulación general del problema de programación mutiobjetivo con n variables de
decisión x, m restricciones y p objetivos es: Determinar x1…..xn que

maximicen z=(z1 (x) ,...,zp (x))

sujeto a x ∈ F (región factible del espacio de soluciones)

Podemos suponer que el problema de optimización es de la forma de maxímización

(maximización de cada función objetivo), ya que los problemas en que aparecen
funciones objetivo de minimización, se pueden reducir a maximización multiplicándolas
por —1.

La optimalidad juega un papel importante en la resolución de problemas con un único

objetivo en los que se persigue determinar la solución óptima, que es una solución
factible (o más de una) que da el mejor valor al objetivo, siendo único tal valor. Sin
embargo, en el caso de objetivos múltiples no es aplicable este concepto de óptimo ya
que una solución que maximice un objetivo en general no maximizará los restantes
objetivos. Esta observación lleva a un nuevo concepto denominado solución o punto
eficiente y en vez de buscar una solución óptima buscaremos un conjunto de
soluciones eficientes.

De una manera informal, diremos que un punto factible x para un problema de

programación multiobjetivo es eficiente, si no existe otro punto factible x' que
mejore el valor de un objetivo sin causar una disminución en el valor de alguno
de los restantes objetivos. Para ilustrarlo, consideremos un problema con dos
objetivos z1y z2 y cuatro resultados A', B' C' y D’ que son cuatro puntos de la
región Z , transformados mediante z de los puntos A, B, C y D respectivamente, de una
región factible F.

Supongamos que en la tabla aparecen sus coordenadas (z1 z2). Observamos que A es
eficiente ya que para cualquier otro punto en Z distinto de A', si mejora el valor de z1
(=6) empeora el valor de z2 (= 14). Análogamente, B y C también son eficientes. No lo
es D, ya que para su transformado D', existen puntos en Z que mejoran alguna de sus
coordenadas sin empeorar la otra, como por ejemplo B'. También diremos que el punto
B (B') domina al punto D' o que D(D’) esta dominado por B (B').

Solución Z1 Z2

A’ 6 14

B’ 8 12

C’ 9 6

D’ 7 8

2/9
 Tema 11. Programación multiobjetivo

De esta definición vemos, que cuando uno se mueve de una solución eficiente a otra
solución eficiente y una función objetivo mejora, una o más de las restantes empeoran.

El conjunto eficiente generalmente está formado por muchas soluciones, alguna de las
cuales hay que seleccionar como decisión final. La solución eficiente elegida por el
decisor como más preferida se denomina solución de mejor compromiso.

Son muchos los métodos existentes para tratar de ayudar al decisor a alcanzar la citada
solución y una descripción de aquellos más importantes (teorías del valor y utilidad,
métodos interactivos, satisfacientes, etc)

Aquí nos limitaremos esencialmente a métodos para generar el conjunto eficiente y

entre ellos vemos primero los de las ponderaciones y E—restricciones, que tienen un
amplio ámbito de aplicación ya que son válidos para problemas lineales y no lineales y
convenientemente interpretados permiten determinar la solución de mejor compromiso.

Después estudiaremos un método simplex multiobjetivo, que también permite generar

el conjunto eficiente y que es una extensión del algoritmo del simplex del capítulo 4 al
caso de objetivos múltiples, por lo que únicamente es válido en el caso lineal.

11.2 Método de las ponderaciones

La ponderación de objetivos para la determinación de soluciones eficientes, es

posiblemente la primera técnica multiobjetivo considerada. El método se deduce
directamente de las condiciones necesarias de Kuhn-Tucker para soluciones eficientes y
fue propuesto por Zadeh en 1963, para con una adecuada variación paramétrica de
los pesos, generar el conjunto eficiente.

PLANTEAMIENTO DEL MÉTODO

Matemáticamente el método de las ponderaciones se formula mediante el problema,

p
con λk peso asociado al objetivo Zk.
Max z(x) = ∑ λk zk (x) Denominamos a este problema
K=1
Sujeto a: P(λ) donde λ=(λ1,...,λp).
x∈ F

El problema multiobjetivo ha quedado transformado en un problema de optimización

con un único objetivo. El peso λk para el objetivo zk se interpreta como la importancia o
peso relativo del k-ésimo objetivo en relación con el resto de los objetivos.
De esta forma, si los pesos λ1,...,λp expresan las preferencias del decisor y este
es capaz de asignarlos de una manera coherente, la solución óptima de P(λ) es
la solución de mejor compromiso para él.

3/9
 Tema 11. Programación multiobjetivo

Este método es válido para problemas lineales y no lineales, aunque nosotros nos
restringiremos aquí al primer caso. Es interesante notar, que la solución óptima del
problema P(λ) es eficiente si los pesos λk son positivos.
Si se tomaran pesos negativos, ello es equivalente a transformar el problema P(λ)
en uno de minimización, para el que se tendría un conjunto eficiente distinto.

El método de las ponderaciones se puede utilizar para generar el conjunto eficiente,

aunque no resulta muy adecuado para obtener la representación completa del citado
conjunto. Para llevarlo a cabo, hay que considerar de forma sistemática una serie de
conjuntos de pesos positivos. Usualmente se empieza por la optimización individual de
cada objetivo que equivale a tomar los pesos (1,0,...,0). (0,1,0,...,0),...,(O...,0,1), para
después introducir una variación sistemática de estos con una tasa de aumento prefijada
que hay que estimar como adecuada.

En el caso de los puntos obtenidos con algún peso nulo, no podemos asegurar que sean
eficientes y en tal caso habría que comprobarlo(un método para ello se considera en el
apartado siguiente). Cada problema de ponderación es un programa lineal cuya
resolución conduce, con la salvedad anterior, a una solución eficiente.

Conceptualmente la generación del conjunto eficiente mediante el método de las

ponderaciones parece bastante simple. En la práctica sin embargo, puede tener ciertos
inconvenientes: distintos conjuntos de pesos pueden generar el mismo punto, el tamaño
de paso de un conjunto de pesos a otro puede no permitir generar todos los puntos
extremos y por tanto se obtendría únicamente una aproximación del conjunto eficiente
al considerar, por ejemplo, bordes que unen puntos extremos no adyacentes, etc. En
definitiva, se podría esperar en muchos casos la obtención de una aproximación más que
una representación exacta del conjunto eficiente.

11.3. Método de las e-restricciones.

Este método consiste en optimizar una función objetivo z1(x) que se supone más
importante que las otras, para las que se introducen números reales εk (k≠ l) que
corresponden a cotas inferiores. De esta forma el problema multiobjetivo se reduce a
un problema con un único objetivo.

Max zl (x)
Sujeto a
X∈F
Zk (x) ≥ εk con k= 1,….l-1, l+1 …p

Que denominaremos problema P(ε).

La elección de la función objetivo zl y las cotas εk representan preferencias subjetivas

del decisor de manera que si no existiera una solución para P(ε), habría que relajar al
menos una de las cotas.

La solución del problema P(ε) denomimada x* será eficiente si es una solución única.

4/9
 Tema 11. Programación multiobjetivo

11.4. Método simplex-multiobjetivo

Los métodos anteriores transforman el problema multiobjetivo en un problema con un

único objetivo Existen sin embargo otros métodos, que trabajan directamente con todos
los objetivos para determinar soluciones eficientes y que básicamente se desarrollan en
tres etapas.

1. En la primera, se determina una solución inicial básica factible. Esta

generalmente se lleva a cabo, como en el caso uniobjetivo, introduciendo
variables de holgura y/o artificiales obteniendo así un punto extremo inicial
factible.
2. En la segunda, se determina un punto extremo eficiente, cuya existencia está
garantizada. Si la región factible del problema es no vacía y todas las funciones
objetivo acotadas en ella, entonces existe al menos un punto extremo eficiente.
3. Finalmente la tercera etapa, consiste en determinar todos los puntos eficientes lo
que se lleva a cabo partiendo de la solución eficiente de la etapa anterior y
generando a partir de ella los restantes puntos extremos eficientes.

Los métodos para llevar a cabo las diferentes etapas son varios. Consideraremos
únicamente el método debido a Zeleny (1974),denominado método del simplex
multiobjetivo que lleva a cabo de forma integrada las tres etapas y que es una extensión
natural del algoritmo del simplex del capítulo 4, ya que utiliza la misma transformación
de pivote para moverse de un punto extremo eficiente a otro adyacente.

Consideremos el problema al que se le han añadido m variables de holgura para ponerlo

en forma estándar.

max z = (z1(x)…., zp(x))

sujeto a
Ax=b
x≥0

donde z1(x)= c1T x………zp(x)= cpt x y x = (x1,….xn, xn+1….xn+m)

A las variables de holgura se les asigna coeficientes cero en las p funciones objetivo.
Como en el caso de un objetivo podemos construir una tabla del simplex multiobjetivo
similar a la tabla del simplex aunque con algunas diferencias que vemos a continuación.

5/9
 Tema 11. Programación multiobjetivo

Esta tabla del simplex multiobjetivo tiene más filas en la parte superior e inferior que la
del simplex del capítulo 4. Las de la parte superior, en número p corresponden a los
coeficientes, de las funciones objetivo, incluidos los de las variables de holgura. Las de
la parte inferior son p filas indicadores formadas con los costes reducidos (w) o
indicadores de cada variable respecto de cada función objetivo. Se les denomina
rk=zjk-cjk al coste reducido o indicador de la columna j (variable x) para la función
objetivo k-ésima. Así, para cada variable xj hay un vector de dimensión p de indicadores
rj= (rj1……rjp) y la introducción de una variable no básica en la base, con valor θ cambia
los valores de los p objetivos mediante la relación.

Zk= zk-θ rjk k=1,...,p

que es la misma expresión y con la misma interpretación que se tenía en el caso de un

objetivo. La información que proporcionan los costes reducidos rjk se puede utilizar,
como veremos en los teoremas que siguen, para determinar la eficiencia de una
solución básica y las adyacentes a ella.

1º) Dado un punto extremo de la región factible, si un punto extremo adyacente

incrementa al menos el valor de un objetivo manteniendo el resto con el mismo valor,
entonces este domina al anterior. Se tiene.

Teorema. Sea B una base con XB = B -1 b solución básica factible. Si existe una
columna aj no básica tal que:
r¡k ≤ O para todo k = 1,..., p, y
rjt< 0 para al menos un t ∈ {1,.., p}
entonces XB no es eficiente.

Notemos que si introducimos la columna aj en la base, tendremos una nueva base B' con
XB´, solución básica factible adyacente a XB y donde Zk (xB´) = Zk (xB) -θ rjk

Pero si θ > 0 entonces Zk(xB´) ≥ zk(xB) Para todo k

Este resultado establece que, si se puede introducir en la base una variable a nivel
positivo de manera que se incremente al menos el valor de un objetivo manteniendo el
resto en el mismo nivel, entonces la actual solución no es eficiente.

El siguiente resultado permite conocer las condiciones bajo las cuales la introducción de
una variable no básica en la base lleva a una solución dominada.
-1
Teorema . Sea B una base con XB = B b solución básica factible. Si existe una columna
aj no básica tal que

rjk ≥ 0 para todo k=1,...,p, y

rjt >0 para al menos un t ∈ {1,..., p}

entonces la introducción de aj en la base, llevará a una nueva solución dominada

6/9
 Tema 11. Programación multiobjetivo

por XB. Por tanto si se introduce una variable no básica en la base que disminuya al
menos el valor de un objetivo manteniendo el resto en el mismo valor, entonces la
nueva solución está dominada por la actual.

Finalmente, damos un resultado que relaciona la actual solución con otras dos
soluciones adyacentes.

Teorema. Sea B una base con XB = B –1 b solución básica factible. Si existen dos
columnas aj y as, no básicas, con aj ≠ as, tales que:

θj rjk ≤ θ s rsk para todo K= 1,…p y

θj rjt ≤ θ s rst para al menos un t∈ (1…p)

con θj, valor de xj si aj se introduce en la base y análogamente θs, entonces la solución

básica factible obtenida si se introduce as en la base está dominada por la solución
básica factible obtenida si se introduce aj en la base.

Sea XB la actual solución básica factible. Si se introduce aj en la base, sea XB´la

correspondiente solución básica factible y XB´´ si se introduce as.
Se tienen las relaciones:
Zk(x B´) = zk (xB) - θj rjk
Zk (x B´´ ) = zk (xB)- θs rsk

Y por tanto podemos escribir

Zk(xB´) ≥ zk(xB´´ ) para todo k
Zt (xB´) > zt (XB´´) para al menos un t ∈ (1…p)

Luego xB´´y está dominada por XB´.

Notemos que estos tres teoremas están relacionados con la posible dominación de la
actual solución respecto a las soluciones adyacentes pero no afirman nada sobre la
eficiencia de la solución. La única situación en que la tabla del simplex multiobjetivo
permite establecer en forma directa la eficiencia de una solución, es cuando esta es
un máximo único para una de las funciones objetivo, lo que se detecta en la tabla
cuando los indicadores de todas las variables no básicas para ese objetivo son
estrictamente positivos (como en el método del simplex con un objetivo). De igual
manera sabemos, que si los indicadores de las variables no básicas para un objetivo son
algunos positivos y otros nulos, la actual solución es un máximo pero no único para ese
objetivo, de forma que la existencia de soluciones óptimas alternativas puede indicar
que tal solución no sea eficiente.

Para determinar la eficiencia de una solución básica factible x, se resuelve el

subproblema de eficiencia.
Max E = ∑ k=1p dk
Sujeto a
X∈F

Zk(x) – dk = zk ( x*), k= 1…p

Dk ≥ 0 k = 1…p

7/9
 Tema 11. Programación multiobjetivo

Las restricciones Zk(x) – dk = zk ( x*) están justificadas por el hecho de que

si x* no es eficiente, debe existir un punto x ∈ Fcon zk(x)>zk(x* ) para todo k y
zt(x) > zt(x*) para al menos un t. Considerando las variables de holgura dk, es claro que
si al resolver el problema es E=0, la solución básica factible x* para el problema
multiobjetivo original es eficiente. Sin embargo, si E> O, es posible que existan puntos x
con al menos una función objetivo con mayor valor que para x*, y por tanto esta no será
eficiente.

A continuación vemos el algoritmo del simplex multiobjetivo en su forma más

sencilla, ya que Zeleny y otros autores han propuesto algunos refinamientos que no
consideramos aquí.

Paso 0. Construir la tabla inicial considerando una fila indicador para cada uno de los p
objetivos.

Paso l. Determinar una base inicial Bh factible. SÍ existe Bh, ir al paso 2. En otro caso,
parar. (Si no es posible una base, el problema es infactible y el algoritmo termina)

[Link] h=1,f=0, (f: contador de soluciones eficientes)(h: contador de soluciones)

Paso 3. Determinar xh (solución básica factible asociada a Bh).

Paso 4. Si existe al menos un k tal que rjk≥ O para todo aj, entonces xh maximiza zk e ir
al paso 5. En otro caso, ir al paso 6.

Paso 5. Si rjk> O para todo aj∉ Bh, x h maximiza de forma única zk , xh es eficiente e ir al
paso 8. En otro caso (xh no es único), determinar las soluciones óptimas alternativas
(introduciendo en la base las columnas con valor cero en la fila k) para ver cuales son
eficientes e ir también al puso 8.

Paso 6. Si rjk ≤ 0 para algún aj ∉ Bh para todo k, ir al paso 15. En otro caso, resolver el
subproblema de eficiencia para xh e ir al paso 7.

Paso 7. Si es xh es eficiente, ir al paso 8 . En otro caso, ir al paso 9.

Paso 8. Guardar la solución eficiente xh y hacer f=f+1

Paso 9. Si para un aj es θj rj ≤ θs rs para todo as de fuera de la base, ir al paso 15. En

otro caso, ir al paso 10.

Paso 10. Si xh es eficiente, ir al paso 12. En otro caso, ir al paso 11.

Paso 11. Si es f= O, ir al paso 12. En otro caso ir al paso 14.

Paso 12. Si existe alguna columna no básica que tenga algún indicador positivo y alguno
negativo (rj con elementos positivos y negativos), ir al paso 13. En otro caso ir al paso
14.

8/9
 Tema 11. Programación multiobjetivo

Paso 13. Guardar tales columnas no básicas (que van a producir bases no consideradas
anteriormente).

Paso 14. Si existe alguna base almacenada, no explorada anteriormente, ir al paso 15.
En otro caso, parar.

Paso 15. Si introduciendo aj en la base se obtiene una nueva base no explorada

anteriormente, ir al paso 16. En otro caso, ir al paso 14.

Paso 16. Introducir aj en la base, hacer h = h +1 y volver al paso 3.

En el paso 4, se comprueba si la solución xh maximiza algún objetivo (∃ k tal que rjk≥0),y

si es así, en et paso 5 se busca la unicidad (rjk >0 ∀ aj ∉ Bh) para ese k). Si xh es única,
es eficiente y vamos al paso 8. Si no es única, puede no ser eficiente y hay que
determinar las soluciones óptimas alternativas comprobando cuales de ellas lo son, para
ir nuevamente con aquellas que lo sean al paso 8.

Si en el paso 4, xh no es máximo para ninguno de los objetivos, entonces en el paso 6 se

buscan columnas no básicas (aj ∉ Bh ) con todos sus indicadores no positivos (rjk ≤0). Si
existe alguno, entonces xh no es eficiente y vamos al paso 15, para introducir tal
columna (s) en la base obteniendo una nueva solución no considerada anteriormente,
hacer h = h +1 y volver al paso 3.

Si en el paso 6, la contestación es negativa, se determina la eficiencia de la solución

mediante el subproblema de eficiencia. Si xh es eficiente (paso 7), vamos al paso 8 y el
Índice f, que es el contador de soluciones eficientes, se incrementa en una unidad. Por
el contrario, si se determina que xh no es eficiente, vamos al paso 9. En este, se
determina una columna no básica no dominada y vamos al paso 15 para introducirla en
la base y explorar una nueva solución no considerada. Si no existe tal columna básica y
xh es eficiente (paso 10), en el paso 12 se determinan aquellas columnas no básicas que
tengan algún indicador positivo y negativo y se guardan en el paso 13 para explorar
posteriormente las correspondientes bases (pasos 14 y 15). Por el contrario si xh no es
eficiente ( paso 10) y no se ha encontrado alguna solución eficiente hasta el momento
(f=0) vamos al paso 12.

De esta forma el algoritmo continua hasta que quedan exploradas todas las bases que
puedan llevar a soluciones eficientes ya que se pasará de punto eficiente a otro punto
eficiente al estas todo el conjunto eficiente conectado.

9/9