Pesquisa Operacional com Otimização/Programação Linear

---

Contextualização da Programação Linear

A Pesquisa Operacional abrange uma série de abordagens objetivando a solução de problemas. Uma delas é a Programação Matemática, e aqui cabe destacar a matemática como ferramenta útil na solução de desafios práticos do mundo real.

“O livro do mundo está escrito em linguagem matemática.” Galileu Galilei (Século XVII)

“PESQUISA OPERACIONAL: Conjunto de técnicas e métodos aplicados por equipes multidisciplinares para se determinar a melhor utilização de recursos limitados e para programação otimizada das operações de uma empresa.” Eduardo de Andrade (1998)

E essa poderosa ferramenta – a matemática – foi criada 100% pelos humanos e é uma linguagem, ou seja, uma forma de codificar os eventos da natureza. Sempre que conseguimos transcrever um problema da linguagem natural (português) para a linguagem matemática (“matematiquês”), já temos grande parte do problema resolvido.

Nesse Artigo abordarei a Programação Linear – também conhecida como Otimização Linear – que é uma subdivisão da Programação Matemática.

Há inúmeras vantagens em codificar um problema real como um PPL (Problema de Programação Linear). A principal vantagem – do meu ponto de vista – é que, ao encontrarmos uma solução para o problema, ela será um ótimo global, e não um ótimo local, que acontece frequentemente na solução de problemas não lineares. Outra grande vantagem é que a formulação geral para resolução por computadores fica extremamente facilitada.

Solução Pelo Método Gráfico

Nos vídeos a seguir eu explico detalhes do PPL sendo resolvido pelo Método Gráfico, pois creio ser fundamental que você entenda a solução geométrica do PPL, para depois passar à solução algébrica do mesmo.

O Método Gráfico de solução de PPLs é utilizado quando temos uma Função Objetivo com apenas duas Variáveis de Decisão, geralmente chamadas X e Y ou X1 e X2. Já o número de restrições é teoricamente ilimitado.

Clique nos ícones de PLAY (⏯) na parte inferior da imagem a seguir:

Se preferir ampliar a animação, clique no ícone no canto inferior direito da imagem anterior ([ ]).

Os PPLs sempre buscam maximizar ou minimizar a função objetivo, o que – em outras palavras – significa encontrar a solução ótima para o problema, por isso também são problemas classificados como de otimização linear (e.g., maximizar a receita ou minimizar o custo de produção).

Solução Pelo Método Algébrico/Computacional

Um PPL com 3 Variáveis de Decisão também pode ser resolvido graficamente, mas em um nível de complexidade muito maior, pois exige a manipulação de geometrias em 3D – planos que definem um sólido – ao invés de linhas (elementos em 2D) dando origem a um polígono.

A melhor forma de resolver PPLs é com o Método SIMPLEX. Esse algoritmo foi considerado um dos mais importantes do século XX e foi testado pelo tempo, pois é utilizado há mais de 70 anos com ótimos resultados.

Clique Aqui e acesse os Exercícios no Otimizador Online Gratuito, mostrado a seguir:

Hipóteses Básicas da Programação Linear

Antes de modelar um problema real como um PPL, é importante que você verifique se a situação em foco respeita as suposições básicas da programação linear que são: Proporcionalidade, Aditividade e Certeza.

Proporcionalidade

Essa premissa diz que o lucro unitário c_j independe do nível de produção x_j, e não considera, portanto, a chamada economia de escala, o que não é válido na maioria dos problemas reais. Para respeitar essa hipótese você pode considerar intervalos de produção nos quais essa proporcionalidade é – aproximadamente – verificada. Proíbe variáveis com expoente diferente de 1 (e.g., x²; x^-7/3; xⁿ).

Aditividade

Declara que a contribuição do total de atividades (variáveis de decisão), é a soma das contribuições individuais de cada uma das variáveis, ou seja, as variáveis são totalmente independentes, não permitindo assim a existência de termos cruzados (e.g., x_{i *} x_j).

Certeza

Implica que todos os parâmetros do modelo são constantes conhecidas. Em situações reais essas certeza não existe, pois o mundo é incerto e complexo.
Por essa razão é importante realizar a análise de sensibilidade após uma solução ter sido classificada como ótima segundo os valores de parâmetros assumidos, pois um dos objetivos é identificar os parâmetros sensíveis (aqueles cujos valores não podem ser modificados sem alterar a solução ótima), uma vez que qualquer alteração posterior no valor de um parâmetro sensível sinaliza imediatamente a necessidade de mudar a solução adotada.

SOLVER com EXCEL e Planilhas do Google

Saiba que você pode resolver problemas com até 200 variáveis de decisão no SOLVER, que roda como suplemento (add-in) gratuito, tanto no MS EXCEL quanto nas Planilhas do Google. Veja no vídeo a seguir os exemplos, tanto do EXCEL quanto do Google Sheets:

Caso queira acessar os exemplos, segue links do EXCEL e Planilhas do Google.

Parametrizações com Linguagem R e PYTHON

Para finalizar essa série de 10 vídeos, segue informações sobre como utilizar as poderosas Linguagens R e PYTHON para resolver PPLs.

Para acessar exemplos práticos em PYTHON clique aqui!