Introdução à programação linear multiobjetivo

Abstract

A programação linear multiobjetivo é um caso particular de programação multiobjetivo, onde se otimiza simultaneamente múltiplas funções lineares sujeitas a um conjunto de restrições também lineares. Este tipo de problemas, tipicamente, não admite uma única solução mas um conjunto de soluções incomparáveis. Este conjunto de soluções representa o melhor resultado possível entre os objetivos conflituantes, visto que não é possível melhorar um critério sem piorar algum dos outros. Neste trabalho iremos introduzir as principais definições de otimização multiobjetivo, analisar as principais ideias da programação linear multiobjetivo, sumarizar os resultados mais importantes de programação linear e mostrar como usar os programas lineares paramétricos para resolver programas lineares com múltiplos objetivos, utilizando exemplos em $\mathbb{R}^2$ que ilustrem esses resultados. Provaremos alguns resultados importantes, como por exemplo o principal teorema de programação linear multiobjetivo que afirma que todas as soluções eficientes são também propriamente eficiente. Estudaremos também dois métodos para resolver programas lineares biobjetivo, o método da soma ponderada e o método simplex, ambos implementados em \textit{Matlab}. Faremos ainda uma breve generalização do método simplex para o caso de programação linear multiobjetivo. Concluímos este trabalho com um breve estudo computacional comparativo dos dois métodos que permite concluir que o método simplex é mais rápido que o método da soma ponderada nos exemplos testados.

Multiobjective linear programming it is a particular case of multiobjective programming, where multiples linear functions, subjected to a set of linear constraints, are optimized simultaneously. This type of problems do not admit, in general, unique solution, but a set of solutions of incomparable solutions. This set of solutions represents the best result possible among the conflicting objectives in the sense that it is not possible to improve one criterion without worsening any of the others. In this work, we will introduce the main definitions of multiobjective optimization, analyze the main ideas of multiobjective linear programming, summarize the main results of linear programming and show how parametric linear programming can be used to solve linear programs with several objectives, using examples in $\mathbb{R}^2$ that illustrate the results. We will also proof some important results, for example, the main theorem of multiobjective linear programming, which states that all efficient solutions are properly efficient. We will also study two methods to solve biobjective linear programs, the weighted sum method and the simplex method, both implemented in \textit{Matlab}. We will also make a brief generalization of the simplex method for multiobjective linear programming. We concluded this work with a brief comparative computational study of the both methods which allows us to conclude that the simplex method is much more faster than the weighted sum method, in the examples tested.