TOPSIS – Algoritmo de tomada de decisão

Ao longo de nossas vidas somos obrigados a tomar uma série de decisões, algumas fáceis e outras extremamente difíceis. Seja fácil ou difícil, para se fazer uma escolha, normalmente, temos alternativas a serem escolhidas de acordo com um conjunto de critérios pré definidos. Um exemplo simples pode ser escolher um carro para comprar. A maioria das pessoas leva em consideração o preço, potência do motor, reputação da montadora, conforto, etc. Esses, nada mais são que nossos critérios para escolher um carro e baseado neles, avaliamos nossas alternativas, que poderiam ser um Hb20, um Pálio ou um Corola, dependendo, é claro, de quais os critérios são os mais importantes para cada pessoa. Agora imagine uma decisão mais complexa de ser tomada, como por exemplo, onde investir uma certa quantidade de dinheiro. Já imaginou um algoritmo que possa te auxiliar nessa decisão?

Problemas de tomada de decisão multi-critério (do inglês, multi-criteria decision making, abreviado por MCDM) são caracterizados por uma matriz de decisão, que é composta de alternativas e critérios ponderados de acordo com o tomador de decisão em questão. Métodos para solucionar problemas MCDM como têm sido amplamente utilizados para selecionar a melhor alternativa entre um número finito de alternativas. Como exemplo de métodos, podemos citar PROMETHEE [1], TODIM [2] e o TOPSIS [3], que será o tema deste post.

O algoritmo TOPSIS (do inglês, Technique for Order Preference by Similarity to Ideal Solution) foi desenvolvido por Hwang & Yoon [3] e é uma técnica de avaliação de performances de alternativas através da similaridade da mesma com uma solução ideal. De acordo com essa técnica a melhor alternativa é aquela mais próxima da solução ideal e mais distante da solução não ideal. O TOPSIS é muito utilizado para solucionar problemas de tomada de decisão da vida real, como nosso exemplo da escolha do carro. Além disso, existem variações do algoritmo que utilizam lógica fuzzy e lógica fuzzy intuicionista [4] [5], mas isso são assuntos para um próximo post.

A seguir serão definidos os conceitos básicos e o algoritmo de tomada de decisão TOPSIS.

Tomada de decisão de multi-critério

Vamos considerar uma matriz D, no qual consiste de alternativas e critérios, descrita por:

matD

no qual A_{1}, A_{2} \cdots A_{m} são as alternativas viáveis, C_{1}, C_{2} \cdots C_{m} são os critérios, x_{ij} indica o rating, o desempenho, da alternativa A_{1} com respeito ao critério C_{j}. Cada critério possui um determinado peso, definido pelo tomador de decisão em questão (pode ser eu, você, um amigo…), representado pelo vetor W = (w_{1}, w_2, \cdots , w_n), sendo w_j um peso para o critério C_j satisfazendo \sum_{j=1}^n w_j = 1.

Em geral os critérios são classificados em dois tipos (e isso é muito importante). Critérios de custo, quanto, menor o rating dele melhor, e critérios de benefício, quanto maior o rating melhor. Voltando ao nosso exemplo da compra do carro, o preço é um critério de custo, ou seja, quanto menor o preço, mais desejável é o carro. Por outro lado, o conforto é um critério de benefício, ou seja, quanto maior, melhor.

A matriz D, depois de preenchida, necessita ser normalizada em uma matriz R = [r_{ij}]_{mxn}, isso permite a comparação entre todos os critérios (imagine, o preço dos carros estão em um intervalo menor do que uma nota de 0 a 10 dada para o conforto, por exemplo). Para normalizar basta fazer:

  r_{ij} = \frac{x_{ij}}{\sqrt{\sum_{i=1}^m x^2_{ij}}}

Por fim, após a normalização dos ratings, os valores da matriz R deve ser ponderados pelo vetor W, gerando uma nova matriz P = [p_{ij}]_{mxn}, oriunda da seguinte multiplicação de:

  p_{ij} = w_j . r_{ij}

O algoritmo TOPSIS

O algoritmo do TOPSIS será descritos no passo a passo a seguir.

Passo 1: Identificar a solução ideal positiva A^+, para critérios de benefício, e a solução ideal negativa A^-, para critérios de custo, como mostrado a seguir:

  A^{+} = (p^{+}_{1}, p^{+}_{2}, \cdots , p^{+}_{n}) \\  A^{-} = (p^{-}_{1}, p^{-}_{2}, \cdots , p^{-}_{n})

onde:

   p_{j}^+ = \left\{\begin{matrix}  max_i (p_{ij}), \textrm{se o criterio e de beneficio}  \\  min_i (p_{ij}), \textrm{se o criterio e de custo}   \end{matrix}\right.   \\   \\   p_{j}^- = \left\{\begin{matrix}  min_i (p_{ij}), \textrm{se o criterio e de beneficio}  \\   max_i (p_{ij}), \textrm{se o criterio e de custo}   \end{matrix}\right.

 

Em outras palavras, as equações acima escolhem os melhores desempenhos em cada critério, seja ele de custo (e nesse caso o melhor desempenho é o menor valor) ou de benefício (no qual o melhor desempenho é o maior valor), e monta os vetores A^+A^-, que nada mais são do que o desempenho para uma alternativa perfeita, ou seja, ter ratings altos para os critérios de benefícios e baixo para os de custo.

Uma outra maneira de obter os vetores ideais, é ao invés de escolher os valores máximos ou mínimos da matriz P, simplesmente é atribuído 1 ou 0 para criar a alternativa perfeita. Neste caso, no vetor ideal positivo A^+, os critérios de benefícios recebem valor 1 e de custo 0. Já no vetor ideal negativo A^-, a lógica inverte. Os critérios de benefícios recebem 0 e os de custo 1. Como alertei anteriormente,o conceito de custo e benefício é essencial para o TOPSIS funcionar corretamene.

 Passo 2: Calcular, para cada alternativa A_i a distancia euclidiana de cada rating para o vetor de soluções positivas A^+ e para o vetor de soluções ideias negativo A^-.

   d_{i}^{+} = \sqrt{\sum_{j=1}^{n} (d_{ij}^{+})^2}   \\   \\   d_{i}^{-} = \sqrt{\sum_{j=1}^{n} (d_{ij}^{-})^2}

onde d_{i}^{+} = p_{j}^{+} - p_{ij} e d_{i}^{-} = p_{j}^{-} - p_{ij}.

 

Passo 3: Calculado o as distâncias do passo anterior, o próximo passo é determinar a proximidade relativa \xi . A ideia é escolher como melhor alternativa aquela mais próxima da solução ideal positiva e mais distante da solução ideal negativa. Para isso, fazemos:

   \xi_i = \frac{d_{i}^{-}}{d_{i}^{+} + d_{i}^{-}}

 

Passo 4: o último passo é fazer o ranking das alternativas baseada nos vetor \xi . As melhores alternativas são aquelas com os maiores valores de \xi_i e devem ser escolhidas pois estão mais próximas da ideal.

Exemplo no MATLAB

Ao final deste post deixo linkado um código em MATLAB de um exemplo fictício baseado no nosso exemplo dos carros. Suponhamos que temos as 3 alternativas listadas na introdução: Pálio, HB20 e o Corola. Eles serão avaliados em 4 critérios: consumo (C), conforto (B), preço (C) e reputação da marca (B). Os pesos, que eu definir e cada tomador de decisão defini o seus próprios pesos, de cada critério, ou seja, o quão importante o critério é para mim, serão: consumo 30%, conforto 5%, preço 60% e reputação da marca 5%. A avaliação de cada carro, segundo os critérios é mostrado na matriz abaixo (cada alternativa e critério estão na mesma sequência). O consumo esta em litros a cada 100km, o conforto de 0 a 10, o preço em reais e a reputação de 0 a 10. Obviamente os valores são fictícios!

   D = \begin{pmatrix}  15 & 6 & 25000 & 7\\  12 & 7 & 35000 & 7 \\  10 & 9 & 55000 & 8  \end{pmatrix}

 

Nessa matriz é executado o TOPSIS (perceba que é importante a normalização, pois os valores estão em intervalos bem diferentes) e o resultado do raking final é mostrado na figura abaixo.

rankingOs valores na lateral são os obtidos por \xi_i . Observe, que segundo os ratings e seus respectivos pesos, que eu atribuí, o melhor carro para mim é um Pálio (e realmente eu tenho um pálio rs). Se os valores dos pesos forem alterados o ranking pode sofrer alterações. Experimente fazer isso!

Download código TOPSIS em MATLAB.

Download código TOPSIS em Python.

Referências

[1] R.E. Bellman, L.A. Zadeh, Decision-making in a fuzzy environment, Management Science 17 (1970) 141-164.

[2] C.L. Hwang & K.P. Yoon, Multiple Attributes Decision Making Methods and Applications, Springer-
Verlag, Berlin, 1981.

[3] L.F.A.M. Gomes, L.A.D. Rangel, An application of the TODIM method to the multicriteria rental evaluation of residential properties, European Journal of Operational Research 193 (2009) 204-211.

[4] Krohling, Renato A., and Vinicius C. Campanharo. “Fuzzy TOPSIS for group decision making: A case study for accidents with oil spill in the sea.” Expert Systems with Applications 38.4 (2011): 4190-4197.

[5] Krohling, Renato A., André GC Pacheco, and André LT Siviero. “IF-TODIM: An intuitionistic fuzzy TODIM to multi-criteria decision making.” Knowledge-Based Systems 53 (2013): 142-146.

Gostou? Então compartilhe!