Programação linear

A palavra programação nos induz a pensar na necessidade de um programa computacional que utilize um conjunto de instruções que nos permita resolver os problemas. O termo Programação Linear (PL) foi utilizado pela primeira vez por George Dantzig para analisar um problema de planejamento para a força aérea americana. A PL se encaixa no campo da programação matemática e é uma área da pesquisa operacional que possue vasta aplicação em apoio à tomada de decisão. O termo “programação”, tanto linear quanto matemática, não possue ligação direta com a programação de computadores ou linguagem de programação. O termo PL foi desenvolvido originalmente para resolver problemas industriais. Assim, o termo “programação” da PL está relacionado ao planejamento de recursos escassos, visando atender as condições operacionais. O termo “linear” como o próprio nome já diz, expressa que as funções do modelo são lineares.

A programação linear busca fazer a designação ótima dos recursos disponíveis para que uma determinada atividade aconteça, ou seja, não há solução melhor do que a ofertada utilizando-se a PL. Problemas de PL referem-se à distribuição eficiente de recursos limitados entre atividades competitivas, com a finalidade de atender a um determinado objetivo, por exemplo, maximização de lucros ou minimização de custos. Se tratando de programação linear, esse objetivo será expresso por uma função linear, a qual chamamos de função objetivo (F.O.). É necessário que se faça o esclarecimento do consumo destes recursos e a proporção em que se dá esse consumo. Essas informações serão fornecidas por meio de equações ou inequações lineares, uma para cada recurso. O conjunto das equações ou inequações lineares são nomeadas como restrições do modelo. As restrições estão ligadas diretamente ao tipo de problema. Exemplo: se for um problema relacionado a área de um plantio, as restrições de recursos econômicos para a realização do mesmo, assim como, a área em hectares disponíveis devem aparecer no problema.

Pressuposições da PL

A programação linear necessita de quatro parâmetros, sendo eles:

  • Proporcionalidade: a necessidade da proporcionalidade indica que as contribuições de cada variável de decisão são proporcionais ao valor da variável de decisão. As contribuições da variável de decisão acontecem tanto na função-objetivo como nos lados esquerdos das restrições.
  • Aditividade: a suposição da aditividade indica que os relacionamentos entre as variáveis são sempre adições e subtrações, mas nunca outras operações. A implicação dessa suposição é que não pode haver relacionamentos de dependência (funcionais) entre as variáveis.
  • Divisibilidade: a divisibilidade indica que as variáveis podem ter valores fracionados, ou seja, as variáveis podem ser divididas em qualquer nível fracional. A implicação dessa suposição é que não pode haver a exigência de que as variáveis sejam inteiras.
  • Certeza: a suposição de certeza indica que todos os parâmetros utilizados nos modelos são conhecidos com certeza. Como muitas vezes acontece de essa suposição não ser verdadeira, utilizamos a análise de sensibilidade para alterar os parâmetros, capturando um pouco da incerteza associada a eles.

Possiveis soluções

Um problema de PL pode:

  • ter apenas uma solução ótima.
  • múltiplas soluções.
  • não ter solução.

A princípio, todos os problemas de programação matemática poderiam ser resolvidos com o simples uso de um lápis e papel. Mas o número de iterações necessárias aumenta muito conforme aumenta o número de variáveis envolvidas no modelo. Para problemas relativamente simples, é possível obter uma solução analítica com recursos bastante simples de álgebra. Um algoritmo é um conjunto de operações implementadas de acordo com uma sequência pré-definida. A partir de uma solução inicial, o algoritmo busca uma nova solução melhor que a anterior. A sequência de operações que conduz a uma nova solução é chamada iteração. As iterações são interrompidas apenas quando um pré-determinado critério de otimalidade é satisfeito.

O principal desafio em qualquer técnica de otimização é encontrar uma solução ótima sem ter que recorrer a uma busca exaustiva de todas as possíveis soluções. Em muitos casos, as possíveis soluções são infinitas. Os algoritmos de programação matemática são desenhados para acelerar a busca e ao mesmo tempo garantir uma solução ótima. Uma forma concisa de resumir as intenções por trás do uso de modelos de programação matemática é dizer que a programação matemática se preocupa com a alocação ótima de recursos escassos entre atividades alternativas.

Software

É fato que a maioria dos problemas de programação matemática é resolvida em computadores, mas isto não quer dizer que essa seja a única maneira de resolver esses problemas. A solução computacional é necessária e conveniente quando os problemas envolvem um número muito grande de variáveis. Existem disponíveis diversos programas de computador para resolução de problemas de programação linear. Ao longo deste material apresentaremos a maior parte das soluções no LPSolve. Mas em alguns momentos usaremos também o Excel com seu suplemento Solver ativado.

Excel

Para utilizar o Excel é necessário habilitar a ferramenta Solver:

  1. Clique na guia Arquivo.
  2. Clique em Opções e, em seguida, clique na categoria Suplementos.
  3. Próximo ao final da caixa de diálogo Opções do Excel, verifique se Suplementos do Excel está selecionado e clique em Ir.
  4. Se o Excel exibir uma mensagem declarando que não pode executar esse suplemento e solicitar que você o instale, clique em Sim para instalá-lo.
  5. Na guia Dados, observe que um grupo Análise foi adicionado. Esse grupo contém um botão de comando Solver.

LPSolve

Programa de código aberto, disponível para download na plataforma Sourceforge. A sintaxe é muito parecida com a formulação matemática e é compatível com a \textit{sintaxe} de outros programas de otimização como LINGO e LINDO. Para download acesse a página https://sourceforge.net/projects/lpsolve/

Modelo genérico

(1)
\begin{align} max: \sum_{i=1}^{N} \sum_{k=1}^{M} D_{ik}X_{ik} \end{align}
(2)
\begin{equation} S.a. \end{equation}
(3)
\begin{align} \sum_{i=1}^{N} X_{ik} \geq R_i \end{align}
(4)
\begin{align} X_{ik} \geq 0 \end{align}
Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License