CAPÍTULO 8
Programação Linear Multiobjectivo
1. Introdução
Tomar decisões constitui uma tarefa básica da gestão. Decidir é escolher ou optar entre
alternativas viáveis. Muitas das situações de decisão da vida real consistem na resolução de
problemas com múltiplos critérios, geralmente conflituosos. No entanto, em situações em que a
pressão do tempo é grande, como sejam as situações de crise, resvala-se com facilidade para
“modelos” muito simples, em que apenas um dos critérios de decisão assume particular relevância,
levando a pôr de lado outros aspectos do problema e, consequentemente, reduz-se o problema (mais
vasto) a um problema de optimização (minimização ou maximização) do objectivo associado ao
critério “relevante”.
Contudo, cada vez mais a entidade que decide (o agente de decisão — AD), é forçado a
considerar uma grande variedade de critérios para avaliação das diferentes alternativas que se lhes
oferecem, até porque se torna difícil a modelação e formulação do problema à custa de apenas um
critério, devido à complexidade, heterogeneidade, natureza conflituosa e aos compromissos presentes
na situação de escolha.
Agora, as suas preocupações não se restringem apenas ao campo económico em sentido restrito; pelo
contrário, já abrangem outros campos, nomeadamente, político, social, meio ambiente, estético e
outros, em que a qualidade de vida da sociedade humana ganha foros de cidadania cada vez mais
fortes.
Em conclusão, o AD é confrontado com a necessidade de ponderar os conflitos entre os
critérios, com vista a encontrar uma decisão de compromisso satisfatória.
114
O problema multiobjectivo
O problema multicritério está relacionado com os métodos e procedimentos, pelos quais os
vários critérios podem ser formalmente associados no processo de análise. De uma forma geral, estes
problemas dividem-se em problemas multiatributo e multiobjectivo. Os primeiros, caracterizam-se
pela existência de uma quantidade discreta de alternativas explicitamente conhecidas. Os problemas
multiobjectivo, referem-se aos casos em que as alternativas são definidas implicitamente por um
conjunto de restrições matemáticas.
Um exemplo de um problema multiatributo é escolher o melhor local para a construção de uma
ponte, em que os critérios poderiam ser os seguintes : custo, impacto sobre o rio (ambiental e
utilização do rio), volume de tráfego, impacto sobre as margens, estética, custo da travessia, etc..
Um exemplo de um problema multiobjectivo é determinar o trajecto mais económico para
efectuar a entrega/recolha de produtos aos clientes duma determinada firma, em que os critérios
poderiam ser os seguintes : tempo, distância, atraso, tráfego, etc..
2. O problema multiobjectivo
O problema multiobjectivo abrange problemas de decisão com pelo menos 2 objectivos. De uma
forma geral, um problema multiobjectivo pode ser formulado da seguinte maneira :
Maximizar z1(x) = c1 x
Maximizar z2(x) = c2 x
...
Maximizar zp(x) = cp x
sujeito a
x ∈ X = { x ∈ ℜn : x ≥ 0, A x = b, b ∈ ℜm }
em que,
p é o número de funções objectivo (critérios),
n é o número de variáveis do problema (de decisão e folga),
m é o número de restrições do problema,
X é a região admissível no espaço das decisões (ou das variáveis),
x é o vector das variáveis do problema : x = (x1, x2, … , xn) é solução admissível,
ck (k = 1, ..., p) é o vector dos coeficientes da função objectivo zk,
A é a matriz dos coeficientes tecnológicos (m×n),
b é o vector dos termos independentes (recursos disponíveis ou requerimentos),
o que não implica perda de generalidade, pois mediante operações convenientes é sempre possível
transformar qualquer problema num de maximização.
Programação Linear Multiobjectivo
O problema multiobjectivo
115
A região admissível no espaço das funções objectivo (o conjunto de todas as imagens dos
pontos em X), pode ser definida da seguinte forma :
Z = { z ∈ ℜp : z = ( z1(x), z2(x), ..., zp(x) ), x ∈ X }.
Na resolução de problemas com apenas um objectivo, procura-se encontrar a solução óptima,
ou seja, a solução admissível que optimize a função objectivo, cujo valor é único mesmo que existam
soluções óptimas alternativas. Obviamente, em problemas com múltiplos objectivos esse conceito não
é aplicável, uma vez que uma solução admissível que optimize um dos objectivos não optimiza, em
geral, os restantes objectivos.
Na resolução de problemas multiobjectivo, pretende-se encontrar uma solução de compromisso
satisfatória para o AD, designada por solução final. Desta forma, a noção de solução óptima é
substituída pela noção de solução não dominada (também designada por eficiente, óptima de Pareto
ou não inferior).
Uma solução diz-se dominada por outra se na passagem da primeira para a segunda existir
“melhoria” de pelo menos uma das funções objectivo e as restantes permanecerem inalteradas. Por
outro lado, uma solução não dominada caracteriza-se por não existir uma outra solução admissível
que melhore, simultaneamente, todos os objectivos, isto é, a melhoria num objectivo é alcançada à
custa de piorar, pelo menos, um dos outros. Matematicamente, tem-se :
Definição 1. Sejam x = (x1, x2, … , xn) e y = (y1, y2, … , yn) duas soluções admissíveis de um
problema de PMO. A solução x domina a solução y se e só se
zk (x1, …, xn) ≥ zk (y1, …, yn)
para qualquer k, e,
zk (x1, …, xn) > zk (y1, …, yn)
para algum k, com (k = 1, 2, …, p)
Definição 2. Seja x = (x1, x2, … , xn) uma solução admissível de um problema de PMO. A
solução x diz-se não dominada se não existir qualquer outra solução admissível y = (y1,
y2, …, yn) que domine x.
Em síntese :
Problema
Função objectivo
com um único
Z : ℜn → ℜ
objectivo
função real de n variáveis reais
Com múltiplos
Z : ℜn → ℜp
objectivos
Sistema de p funções de n variáveis reais
Programação Linear Multiobjectivo
Conceito chave
óptimo
não dominância
116
Métodos de resolução de problemas multiobjectivo
Geralmente, o conceito de não dominância é utilizado para pontos no espaço dos objectivos, ao
passo que o conceito de eficiência é utilizado para a respectiva imagem no espaço das variáveis de
decisão. Uma solução de compromisso satisfatória para o problema multiobjectivo deverá ser não
dominada, cujos valores dos critérios são satisfatórios para o AD, de tal modo que seja aceitável como
solução final do processo de decisão. Desta forma, é apenas sobre o conjunto das soluções não
dominadas que deve recair a atenção do analista e do AD.
Entre quaisquer duas soluções não dominadas verifica-se que a uma melhoria em pelo menos
um dos objectivos se encontra sempre associado um sacrifício em pelo menos um dos outros
objectivos, isto é, verifica-se sempre uma compensação (“trade-off”) entre objectivos no conjunto das
soluções não dominadas. Neste conjunto escolhe-se apenas uma solução (não dominada), que se
designa por melhor solução de compromisso. Como proceder à sua escolha ? Só o diálogo analista-decisor
pode dar resposta satisfatória a esta questão.
3. Métodos de resolução de problemas multiobjectivo
No processo de tomada de decisão desempenha papel relevante o sistema de preferências do
decisor, podendo os diferentes métodos de PMO ser classificados com base na fase do processo em
que essa informação é incorporada. Assim, podem distinguir-se três grandes classes de métodos,
conforme a articulação de preferências é efectivada a priori, a posteriori ou progressivamente :
1. Métodos que incorporam as preferências reveladas pelo AD. Toda a informação de preferências é
indicada pelo AD antes da resolução do problema. Apesar de existir modelação multiobjectivo, o
problema é depois reduzido ao caso monocritério onde é optimizada uma função valor (ou
utilidade), que conduz à solução de compromisso óptima. A dificuldade reside na obtenção a
priori de informação das preferências do AD para construir uma função valor que agrega, numa
única dimensão, todos os critérios considerados no modelo.
2. Métodos de geração do conjunto das soluções não dominadas. São calculadas todas as soluções
não dominadas do problema (ou parte), as quais são parcial ou totalmente enumeradas e
apresentadas ao AD para avaliação. Estes métodos têm sido alvo de numerosas críticas devido ao
elevado esforço computacional necessário para o cálculo exaustivo das soluções eficientes.
3. Métodos interactivos. Através de interacções Homem-máquina existe uma progressiva
articulação das preferências do AD. Estes métodos alternam entre fases de cálculo e fases de
diálogo, sendo o AD chamado a expressar as suas preferências. A informação relativa às
preferências do AD é usada para reduzir o âmbito da pesquisa, de modo a conduzir o processo
de cálculo para a zona da região admissível onde se localizam as soluções que melhor
correspondem ao seu sistema de preferências.
Programação Linear Multiobjectivo
Representação gráfica
117
Os métodos multicritério interactivos constituem uma boa ilustração da tendência actual da
programação multicritério, uma evolução no sentido do apoio à decisão : ajudar o AD a encontrar
uma solução de compromisso satisfatória.
4. Programação Linear Multiobjectivo
Este tipo de problema é um caso particular, de grande interesse, do PMO, em que as p funções
objectivo e as m restrições são funções lineares. Desta forma, pode-se definir este problema da
seguinte forma :
Maximizar z1(x1, …, xn) = c 11 x 1 + K + c 1n x n
...
p
p
Maximizar zp(x1, …, xn) = c 1 x 1 + K + c n x n
sujeito a
ai1 x1 + ai2 x2 + . . . + ain xn ≤ bi
xj ≥ 0
(i = 1, 2, …, m)
(j = 1, 2, …, n)
O papel do analista é fornecer informação ao AD que permita a este aperceber-se do domínio
onde pode exercer a sua escolha quanto à alternativa a seguir — conjunto das soluções não dominadas,
KD ⊂ K. Essa informação pode ser apresentada ao decisor sob forma gráfica ou tabular, que tomandoa por base e tendo em conta as suas preferências procede à escolha da melhor solução de compromisso de
entre o conjunto das soluções não dominadas.
5. Representação gráfica
Considere-se o exemplo da empresa de mobiliário metálico de escritório que pretende
determinar o plano de produção mensal para os novos modelos de secretária e estante sugeridos pela
Direcção de Marketing.
A empresa estabeleceu então como objectivo (único) a maximização da margem bruta. Admitase que a empresa fabrica outros produtos mais lucrativos, mas que só podem ser vendidos
conjuntamente com os novos modelos de secretárias ou de estantes, e suponha-se que por cada
secretária produzida são economizados 20 minutos do tempo global da empresa para processamento
das encomendas e por cada estante produzida essa economia é de 30 minutos. Dado que neste
momento não se pode levar a cabo uma expansão da capacidade da empresa para o processamento
das encomendas, é natural que a empresa pretenda também maximizar as economias de tempo de
processamento decorrentes da produção destes novos modelos.
Programação Linear Multiobjectivo
118
Representação gráfica
Assim, o problema pode ser formalizado como problema de programação multiobjectivo da
seguinte forma :
Maximizar z1(x1, x2) = 6 x1 + 3 x2
Maximizar z2(x1, x2) = 20 x1 + 30 x2
sujeito a
2 x1 + 4 x2 ≤ 720
4 x1 + 4 x2 ≤ 880
x1
≤ 660
x1, x2 ≥ 0
O conjunto das soluções admissíveis, K, encontra-se representado na Figura 1. Na mesma figura
encontram-se representadas as rectas de nível das duas funções objectivo correspondentes às soluções
óptimas respectivas se cada um dos objectivos fosse tomado isoladamente :
zl = 6 x1 + 3 x2 atinge o óptimo ( z ∗1 = 1 140) no ponto extremo (160, 60)
z2 = 20 x1 + 30 x2 atinge o óptimo ( z∗2 = 5 800) no ponto extremo (80, 140)
Programação Linear Multiobjectivo