Aula+4

Prévia do material em texto

Pesquisa Operacional
Profª Elaine Ribeiro
Mestre em Educação Tecnológica/Tecnologia da Informação
Unidade 2 – Programação linear, dualidade e sensibilidade
Seção 2.1 – Introdução à programação linear
A programação linear, no campo da programação matemática, é uma área da pesquisa operacional com vasta aplicação em apoio à decisão. 
O termo “programação”, tanto linear quanto matemática, não tem a ver diretamente com programação de computadores, ou linguagem de programação. Este termo tem origem em suas aplicações, originalmente desenvolvido para resolver problemas industriais.
Assim, o termo “programação” da programação linear está relacionado ao planejamento de recursos escassos visando atender as condições operacionais. Estas, por sua vez, são representadas por funções, equações e inequações.
A aplicação da programação linear em apoio à decisão ocorre na condição que se decide para atingir um objetivo. Este, por sua vez, é resultante da alocação ótima dos recursos. Por isso caracterizamos a programação linear como uma técnica de otimização.
No problema de otimização em siderurgia, por exemplo, buscamos determinar a alocação ótima dos recursos de produção de forma a atender as limitações de capacidades de cada usina e maximizar o lucro resultante. Tanto a função de maximizar o lucro quanto as restrições de capacidade de cada planta são representados por funções lineares. 
Neste exemplo, o tomador de decisão pode escolher diversas combinações de alocação de seus produtos, no entanto apenas uma combinação é a mais lucrativa.
Embora originalmente o termo “programação” de programação linear não tem a ver diretamente com programação de computadores, os problemas reais não podem ser resolvidos manualmente, dada a dimensão de problemas reais. 
Com a evolução da tecnologia de hardware e software, os algoritmos de programação linear são implementados em uma linguagem computacional para viabilizar a resolução de problemas reais em menor tempo. A programação linear, dessa forma, teve seu desenvolvimento junto com o desenvolvimento dos computadores, a partir da década de quarenta.
Diversas áreas utilizam a programação linear para apoio a decisão. Dentre as áreas de aplicação estão: 
planejamento logístico de frotas e rotas, 
planejamento da produção de longo, médio e curto prazo,
decisão em escolha de mix de produtos em manufatura, 
estratégias operacionais em mineração, siderurgia, petroquímicas, agricultura, 
decisão de localização de facilidade ou instalação de fábricas ou centros de distribuição, 
decisão em finanças na escolha da melhor carteira de investimentos, entre outros.
Relembrando:
Na construção de modelos em pesquisa operacional, temos basicamente uma função objetivo, que é aquela que queremos otimizar (maximizar ou minimizar), as restrições funcionais e a restrição de não negatividade. A função objetivo e as restrições funcionais são equações, ou inequações (no caso das restrições funcionais), sendo compostas pelas variáveis de decisão e por coeficientes.
Uma das técnicas de programação matemática é a programação linear, que também poderemos abreviar por PL. Na PL as funções, equações e inequações apresentam comportamento linear. 
As equações lineares podem ser representadas de modo genérico por:
Em que o a é coeficiente da incógnita x e b é o termo independente.
Agora que já sabemos o que é a PL, temos que levar em conta alguns pressupostos, ou hipóteses, para a resolução de problemas de programação linear. 
Quais são essas hipóteses?
Hipótese de Aditividade
Esta hipótese pressupõe que o todo é igual à soma das partes. 
Por exemplo, se em 100ml de leite achocolatado encontramos 70mg de cálcio e, em 100g de pão de forma encontramos 2,5mg do mesmo componente, então na refeição composta por 100ml de leite achocolatado e 100g de pão de forma ingerimos 72,5mg de cálcio. 
Hipótese de Proporcionalidade
Pressupõe que para cada variável de decisão considerada no modelo, a sua contribuição em relação à função objetivo e às restrições do modelo, seja diretamente proporcional ao valor da variável de decisão.
Por exemplo, uma empresa busca maximizar sua produção de cadeiras (x1) e mesas (x2), sendo que o lucro unitário por cadeira e mesa é $4 e $7, respectivamente. Dessa forma a função objetivo Z é expressa como Max Z = 4x1 + x2, assim mostrando a contribuição da variável x1, para que a proporcionalidade seja respeitada, a cada unidade de cadeira produzida, a função objetivo deve aumentar $4.
Hipótese de Divisibilidade
As variáveis de decisão podem assumir quaisquer valores, inclusive valores não inteiros (fracionados).
Hipótese de Certeza
Garante que todos os valores dos coeficientes atribuídos à função objetivo e às restrições funcionais são assumidos como conhecidos, de modo que são não valores aleatórios.
Se para criar um modelo que descreva adequadamente a realidade você violar de forma significativa as quatro hipóteses ou se ao satisfazer as quatro hipóteses o seu modelo se distanciar muito da realidade, pare e repense o uso da programação linear. Para esses casos, temos outras possibilidades de soluções que veremos mais adiante.
Método Gráfico: 
Agora que já sabemos o que é programação linear e as hipóteses que devem ser satisfeitas para que o nosso problema possa se enquadrar nesse tipo de programação matemática, como podemos encontrar uma solução ótima para essa classe de problemas?
O primeiro método que aprenderemos é muito intuitivo e de fácil visualização; a este método chamaremos de Método Gráfico.
Para isso, necessitamos relembrar alguns conceitos, a começar pelos tipos de soluções possíveis, considerando-se que um modelo de programação linear consiste, basicamente, de um sistema de equações lineares. 
Solução viável: para uma solução ser viável todas as restrições devem ser satisfeitas. 
Solução inviável: se ao menos uma das restrições for violada, a solução é inviável. 
Região de soluções viáveis: é o conjunto de todas as soluções viáveis. 
 Solução ótima: trata-se do valor mais favorável da função objetivo (maior ou menor valor da função objetivo). 
Nenhuma solução ótima. 
De acordo com Hillier e Lieberman (2013), uma solução viável em ponto extremo (também chamada de solução FPE) é aquela que está no vértice da região de soluções viáveis.
Método Gráfico 
Antes de aprendermos o método gráfico, precisamos relembrar alguns conceitos:
Função: dados dois conjuntos A e B, e uma relação entre eles, dizemos que essa função é uma relação de A em B, se e somente se, para todo X pertencente a A, existe um único Y pertente a B.
			f(x) = 2*x ou
			y = 2*x
Equação: é uma expressão algébrica que contém uma igualdade. Ela foi criada para ajudar as pessoas a encontrarem soluções para problemas nos quais um número não é conhecido.
				x + 2 = 7
Inequação: Inequação é uma expressão matemática que possui a propriedade de expressar desigualdades, diferente da equação que expressa igualdade. 
O sinal usado na equação é o símbolo de igual (=), já na inequação usaremos os seguintes símbolos matemáticos: > : maior que; < : menor que; ≥ : maior que ou igual ; ≤ : menor que ou igual 
				ax + b ≤ 0 
Exemplo de Método Gráfico 
Veja vídeo através do link: 
https://www.youtube.com/watch?v=9DyMswZVn74 
Referências
MUNHOZ, Igor Polezi; AKKARI, Alessandra Cristina Santos. Pesquisa Operacional. Londrina: Editora e Distribuidora Educaional S.A., 2018.
https://www.marcogandra.com.br/2012/08/o-que-e-programacao-linear.html 
http://conteudo.icmc.usp.br/pessoas/mari/PM2016/PM_Aula_02.pdf 
https://books.google.com.br/books 
https://www.youtube.com/watch?v=9DyMswZVn74