Programação Multiobjetivo

A complexidade dos problemas operacionais observados em empresas do setor florestal são de difícil representação matemática e, por isso, geralmente são executados de maneira empírica. Um dos fatores que mais dificulta sua representação é sua característica multiobjetivo pela interação de padrões difusos aos quais a função objetivo do problema pode seguir.

Otimização multiobjetivo é um problema de busca na qual um vetor de variáveis de decisão é considerado para satisfazer as restrições e otimiza o vetor de sua função, sendo o objetivo de cada vetor a função objetivo do problema. Uma série de trabalhos foram realizados ao longo dos anos aplicando ao setor florestal o conceito de otimização multiobjetivo (CAMBERO e SOWLATI 2016).

A utilização de modelos de otimização considerando múltiplas funções objetivo é, em geral, baseada no fato de que, nos problemas reais, existem múltiplas óticas para avaliar o mérito das soluções admissíveis. No mundo real, geralmente deseja-se contemplar múltiplos objetivos, e estes objetivos nem sempre são convergentes. O termo otimização multiobjetivo é sinônimo de termos comuns na otimização, como vetor de otimização, otimização multicritério ou otimização multiperformance.

$max Z_1 = f_1(x) = c_1x = \sum_{j=1}^{n} c_{1j}x_j$

$max Z_2 = f_2(x) = c_2x = \sum_{j=1}^{n} c_{2j}x_j$

(…)

$max Z_k = f_k(x) = c_kx = \sum_{j=1}^{n} c_{kj}x_j$

S.a.

$\sum_{j=1}^{n} a_{ij}x_j = b_i$ em que $i = 1,...,m$

$x_{ij} \geq 0$ em que $j = 1,...,n$

O espaço de soluções num problema multiobjetivo é mapeado no espaço dos objetivos e não mais no espaço das variáveis de decisão como nos casos de problemas mono-objetivos. Num problema de único objetivo, a busca pela solução ótima é puramente técnica, cabendo ao algoritmo descobri-la. Já num problema multiobjetivo, é necessário definir uma estrutura de preferência. Existem diferentes abordagens para resolver um problema multi-objetivo via programação linear:

  • Otimização por metas.
  • Método de minimização dos desvios percentuais.
  • Método da soma pesada das funções objetivo.
  • Métodos interativos para modelos multiobjetivo.
2wr2f76.png

Vídeo explicativo de Programação Multiobjetivo

Otimização por Metas

A solução de problemas multiobjetivos baseada na otimização por metas pode ser melhor compreendida através de exemplo. Acompanhe o problema abaixo:

Um fazendeiro está interessado em desenvolver um projeto agroflorestal beneficiando-se de uma nova linha de crédito. Um hectare da primeira alternativa suporta 2 animais, produz 200 $m^3$ de madeira e custam R$ 6.000. Um hectare da segunda alternativa produz 60 $m^3$ de madeira, suporta 4 animais e custa R$ 7.500.

O proprietário conseguiu um financiamento de R$ 750.000 para implantar os projetos e firmou dois contratos futuros: o fornecimento de 40.000 m³ de madeira e de 150 animais. Qual deve ser o objetivo do proprietário?

  • Uso todo o financiamento (maximizar investimento)?
  • Produzir a maior quantidade de madeira (maximizar volume)?
  • Produzir a maior quantidade de animais (maximizar cabeças)?

Primeiramente, deve-se modelar matematicamente as possíveis metas:

Orçamento: $6.000 A1 + 7.500 A2 = 750.000$
Pecuária: $2 A1 + 4 A2 \geq 150$
Madeira: $200 A1 + 60 A2 \geq 40.000$

Conhecendo cada meta, define-se matematicamente os possíveis desvios em relação a cada uma delas. Considerando a meta de orçamento, caso a implementação do projeto fique abaixo de 750.000, inclui-se uma variável que indica o quanto falta para atingir a meta ($d_{orc}^{-}$):

$6.000 A1 + 7.500 A2 + d_{orc}^{-}= 750.000$

Caso a implementação do projeto fique acima de 750.000, inclui-se uma variável que indique o quanto se passou da meta ($d_{orc}^{+}$):

$60.000 A1 + 80.000 A2 - d_{orc}^{+}= 750.000$

Considerando agora e meta pecuária, caso a implementação dos projetos fique acima de 15, atende-se a meta. Caso a implementação dos projetos fique abaixo de 15, inclui-se uma variável que indique o que falta para atingir meta ($d_{pec}^{-}$):

$2 A1 + 4 A2 + d_{pec}^{-}= 150$

Finalmente, considerando a meta de madeira, caso a implementação dos projetos fique acima de 4.000, atende-se a meta de pelo menos. Caso a implementação dos projetos fique abaixo de 4.000, deve-se incluir uma variável que indique o quanto falta para atingir a meta ($d_{mad}^{-}$):

$200 A1 + 60 A2 + d_{mad}^{-} >= 40.000$

É razoável pensar que o ideal seja chegar o mais próximo possível das metas. Assim a função objetivo pode ser definida como a minimização dos desvios em relação a meta, seja o desvio para mais, seja o desvio para menos:

$MinZ = d_{orc}^{-} + d_{orc}^{+} + d_{pec}^{-} + d_{mad}^{-}$

S.a.

$6.000 A1 + 7.500 A2 + d_{orc}^{-} - d_{orc}^{+} = 750.000$

$2 A1 + 4 A2 + d_{pec}^{-}= 150$

$200 A1 + 60 A2 + d_{mad}^{-} >= 40.000$

Suponha que seja 5 vezes mais importante atender à meta de orçamento do que as demais. É possível incorporar esta exigência na formulação do problema incluindo um peso aos desvios de orçamento:

$MinZ = 5(d_{orc}^{-} + d_{orc}^{+}) + d_{ani}^{-} + d_{mad}^{-}$

S.a.

$6.000 A1 + 7.500 A2 + d_{orc}^{-} - d_{orc}^{+} = 750.000$

$2 A1 + 4 A2 + d_{pec}^{-}= 150$

$200 A1 + 60 A2 + d_{mad}^{-} >= 40.000$

Outro ponto que pode estar chamando a atenção de um atento leitor, é que os desvios relacionados ao orçamento são da ordem de mil de reais e os desvios relacionados à pecuária estão expressos em animais por mês. Como consequência, a função objetivo não poderá ter uma única unidade. Este é um ponto bastante criticado da programação por metas. Uma alternativa é normalizar as restrições trazendo os desvios para a dimensão unitária:

$MinZ = d_{orc}^{-} + d_{orc}^{+} + d_{ani}^{-} + d_{ani}^{+} + d_{mad}^{-}$

S.a.

$\frac{6.000}{750.000} A1 + \frac{7.500}{750.000} A2 + d_{orc}^{-} - d_{orc}^{+}= \frac{750.000}{750.000}$

$\frac{2}{150} A1 + \frac{4}{150} A2 + d_{pec}^{-}= \frac{150}{150}$

$\frac{200}{40.000} A1 + \frac{60}{40.000} A2 + d_{mad}^{-} >= \frac{40.000}{40.000}$

Antes da normalização, R$ 1 na meta de R$ 750.000 tinha o mesmo peso de 1 animal na meta de 150 animais. Depois da normalização, os desvios da meta de orçamento tem o efeito proporcional aos desvios na meta de pecuária.

Método de Minimização dos Desvios Percentuais

Considere o problema multiobjetivo abaixo:

$max Z_1 = x_1 + 1,5 x_2$

$max Z_2 = 5 x_1 + 2 x_2$

S.a.

$2 x_1 + 2 x_2 \leq 160$

$x_1 + 2 x_2 \leq 120$

$4 x_1 + x_2 \leq 280$

Sendo $Z^{*}_{1}$ a solução ótima considerando apenas a $$FO_1$$ e $$Z^{*}_{2}$$ a solução ótima considerando apenas a $FO_2$, a FO multi-objetivo será:

$min Z = \{\frac{Z^{*}_{1} - Z_1}{Z^{*}_{1}}\}+\{\frac{Z^{*}_{2} - Z_2}{Z^{*}_{2}}\}$

Assim, a novo modelo matemático será:

$min Z = \{\frac{100 - (x_1 + 1,5 x_2)}{100}\} + \{\frac{350 - (5 x_1 + 2 x_2)}{350}\}$

S.a.

$2 x_1 + 2 x_2 \leq 160$

$x_1 + 2 x_2 \leq 120$

$4 x_1 + x_2 \leq 280$

Método da Soma Pesada

$max Z_\lambda = \lambda_1 f_1(x) + \lambda_2 f_2(x) +...+\lambda_k f_k(x) = \sum_{k=1}^{K} \lambda_k c_k x$

S.a. $x \in X$

$\Lambda^0 = \{\lambda \in \Re^K: \lambda_k \leq 0, k=1,2,....,K, \sum_{k=1}^{K} \lambda_k = 1 \}$

$\Lambda = \{\lambda \in \Re^K: \lambda_k \leq 0, k=1,2,....,K, \sum_{k=1}^{K} \lambda_k = 1 \}$

No espaço de soluções de um problema baseado na soma pesada, existem regiões de indiferença associadas às soluções básicas eficientes que otimizam individualmente cada função objetivo. Deseja-se portanto, buscar não uma solução ótima individual, mas uma solução eficiente, para todas as funções objetivo.

Métodos Interativos

O processo de apoio à decisão para a otimização multiobjetivo baseado em métodos iterativos é constituído por ciclos de: cálculo de soluções, avaliação das soluções e possível alteração da estrutura de preferências face à nova informação disponível. Deseja-se a “convergência” para uma solução final que estabeleça um compromisso aceitável entre as funções objetivo.

A solução ideal $z^*$ (ou ponto utopia) é o ponto cujas componentes são o ótimo de cada função objetivo na região admissível, quando otimizadas separadamente. Isto leva a uma solução $x' \in X$ é eficiente se e somente se não existir uma outra solução $x \in X$ tal que $f_k(x) \geq f_k(x')$ para todas as k-ésimas funções objetivos, sendo a desigualdade estrita para pelo menos um $k$, $f_k(x) > f_k(x')$. Qualquer outra solução é pior que a solução corrente para qualquer uma das funções objetivo.

Solução não dominada: não existe outra solução admissível que melhore simultaneamente todas as FO - a melhoria numa FO é alcançada à custa da degradação do valor de pelo menos uma das outras. Isto leva a uma solução $x' \in X$ é fracamente eficiente se e só se não existir uma outra solução $x \in X$ tal que $f_k(x) > f_k(x')$. $X_{FE}$ representa o conjunto das soluções fracamente eficientes. Existe outra solução que é igual à solução, mas nunca pior, para pelo menos uma das funções objetivo.

**Playlist: Videoaulas Complementares:

Introdução à Otimização Multiobjetivo**

** Revisão PL e Multiobjetivo**

Otimização Multiobjetivo em Problema de Rota de Compras

Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License