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 ([ ]).
Caso queira abrir os 2 modelos, segue links do Exemplo 1 e Exemplo 2.
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 cj independe do nível de produção xj, 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., x2; x-7/3; xn).
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., xi * xj).
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!
