Maximizar a receita de vendedores preservando a satisfação dos consumidores apresenta alguns desafios computacionais. O problema da precificação livre de inveja surgiu como uma alternativa de modelagem que é APX-difícil em geral, mas alguns casos e/ou variações já foram provados ser resolvíveis de maneira exata em tempo polinomial. Este trabalho aborda os casos de emparelhamento perfeito livre de inveja, no qual o número de consumidores coincide com o número de itens à venda e cada consumidor pode comprar apenas um único item, e o de demanda unitária com substituibilidade métrica, no qual várias unidades de um mesmo item são vendidas em localidades diferentes e os consumidores destas localidades podem comprar apenas uma unidade do item, sendo que os custos de deslocamento de uma localidade à outra para a realização da compra formam um espaço métrico. Para o primeiro caso, foi projetado um algoritmo exato baseado em uma estratégia de programação dinâmica levando em consideração as utilidades dos consumido- res para calcular as precificações ótimas. Para o segundo caso, foi proposta uma estratégia algorítmica que realiza a busca das soluções ótimas através de uma redução para o primeiro caso e da simplificação dos cálculos dos caminhos mínimos para a determinação dos preços. Comparando-se os métodos propostos com os existentes na literatura, no primeiro caso houve um aumento de desempenho de, em média, 49% na busca de preços ótimos, e no segundo caso houve uma redução da complexidade computacional de tempo na busca das soluções ótimas de O(n^4) para O(n^3).
|
