Atividade_Pratica_Supervisionada_de_Pesquisa_Operacional

Prévia do material em texto

Atividade Prática Supervisionada de Pesquisa Operacional
	NOME
	RA
	André Jaime Albert Nunes
	266901
	Bruna Staxaki
	223222
	Beatriz Dummer
	439651
	Jéssica Leão Machado Valandro
	377975
	Mariane Wëlter
	198303
Tutor Presencial: Fabiano Karaim
Porto Alegre – RS
Novembro de 2013
INTRODUÇÃO
Sem dúvida nenhuma a Programação Linear é uma das técnicas da Pesquisa Operacional das mais utilizadas em se tratando de problemas de otimização. 
A Programação Linear (PL) é uma técnica de planejamento da pesquisa operacional, fortemente baseada em Álgebra Linear (Boldrini et al., 1980), que tem tornado-se das mais poderosas por seu grande leque de aplicabilidade em quase todo ramo de atividade. Ela foi criada em 1946 tendo sido aplicada em diversas áreas desde então, como: alocação de recursos e utilização de matéria-prima, transporte, localização de instalações, composição de carteira de investimentos.
Os problemas de Programação Linear (PL) buscam a distribuição eficiente de recursos limitados para atender um determinado objetivo, em geral, maximizar lucros ou minimizar custos. Em se tratando de PL, esse objetivo é expresso através de uma função linear, denominada de "Função Objetivo".
Os primeiros conceitos da programação linear foram desenvolvidos durante a II Guerra Mundial para serem aplicados a programas militares. 
Todo esse trabalho resultou num algoritmo chamado simplex que resolve de uma forma eficiente estes problemas. 
A programação linear tem sido aplicada por diversas entidades e empresas a inúmeros problemas. 
IMPLEMENTAÇÃO DE PROGRAMA DIÁRIA DE PRODUÇÃO
Fabricação de cadeiras e armários:
	Limitação de matéria prima (madeira): 24m²
Limitação de mão-de-obra: 8hs
O processo de produção é tal que, para fazer uma cadeira a fábrica gasta 2 m2 de madeira e 2hs de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m2 de madeira e 1h de mão de obra.
Além disso, sabe-se que cada cadeira dá uma margem de contribuição para o lucro de R$ 4 e cada armário de R$ 1. 
Programa de produção que maximize a contribuição de LUCRO:
As variáveis de decisão envolvidas no problema são:
x1: quantidade a produzir de cadeiras
x2: quantidade a produzir de armários
A função objetivo é:
Para as restrições, a relação lógica existente é:
Utilização de recurso = Disponibilidade
Assim temos:
Madeira: 2 x1 + 3 x2 <=24
Mão-de-obra: 2 x1 + x2 <=8
x1, x2 <=0
O modelo completo é:
Maximizar: z = 4 x1 + x2
Sujeito a 2 x1 + 3 x2 <=24
 2 x1 + x2 <=8
 x1, x2 <=0
Modelagem do problema
Utilização de recurso = Disponibilidade.
Utilização de recurso + Folga = Disponibilidade.
Isso significa que:
	Utilização de recurso < Disponibilidade implica Folga > 0;
Utilização de recurso = Disponibilidade implica Folga = 0.
Deste modo, a folga de cada recurso pode ser representada por uma variável de forma exatamente igual à produção de cada produto. Desse modo, vamos chamar:
f1: folga de madeira;
f2: folga de mão-de-obra.
Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser:
Maximizar: z = 4 x1 + x2
Sujeito a 2 x1 + 3 x2 + f1 = 24
 2 x1 + x2 + f2 = 8
 x1, x2, f1, f2 <=0
PROBLEMAS DE ALOCAÇÃO DE RECURSOS
Os problemas de Alocação de Recursos são muito comuns em PO. Problemas desse tipo dizem respeito à atribuição e distribuição de recursos entre diversas tarefas ou atividades que devem ser realizadas. Normalmente, os recursos disponíveis não são suficientes para que todas as atividades sejam executadas no nível mais elevado que se possa desejar. Assim, o que se procura, nesses casos, é encontrar a melhor distribuição possível dos recursos entre as diversas tarefas ou atividades, de forma a atingir um valor ótimo do objetivo estabelecido. 
As indústrias dos mais diversos setores utilizam estes problemas para fazer uma programação de produção, ou seja, saber qual a quantidade a produzir de um determinado produto, entre vários, para se obter o maior lucro possível ou o menor custo possível e obedecendo as limitações do sistema em estudo, como por exemplo, matéria-prima, mão-de-obra, demanda de mercado, maquinário disponível, etc.
Na agricultura pode-se saber que alimentos devem ser plantados de modo que o lucro seja máximo e sejam respeitadas as características do solo, do mercado, do comprador e dos equipamentos disponíveis. Pode-se também querer saber qual quantidade de terra deve-se destinar a cada atividade (plantação, pecuária, etc.) de modo a ter o melhor retorno financeiro, respeitando as limitações de cada atividade. 
MODELOS MATEMÁTICOS: PROGRAMAÇÃO LINEAR
Características do Modelo de Programação Linear
Os modelos de Programação Linear são básicos para a compreensão de todos os outros modelos de Programação Matemática. Os conceitos nele firmados serão estendidos aos demais, concedendo suporte a estudos mais avançados. Outra vantagem desse modelo está na extraordinária eficiência dos algoritmos de solução hoje existentes, disponibilizando alta capacidade de cálculo e podendo ser facilmente implementado até mesmo através de planilhas e com o auxílio de microcomputadores pessoais. 
Os modelos de Programação Linear são um tipo especial de modelos de otimização. Para que um determinado sistema possa ser representado por meio de um modelo de Programação Linear, ele deve possuir as seguintes características: 
1. Proporcionalidade: a quantidade de recurso consumido por uma dada atividade deve ser proporcional ao nível dessa atividade na solução final do problema. 
2. Além disso, o custo de cada atividade é proporcional ao nível de operação da atividade; 
3. Não Negatividade: deve ser sempre possível desenvolver dada atividade em qualquer nível não negativo e qualquer proporção de um dado recurso deve sempre ser utilizado; 
4. Aditividade: o custo total é a soma das parcelas associadas a cada atividade; 
5. Separabilidade: pode-se identificar de forma separada o custo (ou consumo de recursos) específico das operações de cada atividade. 
Um modelo de Programação Linear é um modelo matemático de otimização no qual todas as funções são lineares. Estes modelos são compostos por uma função objetivo linear e por restrições técnicas representadas por um grupo de inequações também lineares. 
Formulação de problemas de Programação Linear
Quais são as variáveis de decisão? 
Aqui o trabalho consiste em explicitar as decisões que dever ser tomadas e representar as possíveis decisões através de variáveis chamadas variáveis de decisão. Se o problema é de programação de produção, as variáveis de decisão são as quantidades a produzir no período; se for um problema de programação de investimento, as variáveis vão representar as decisões de investimento, e em que período. 
 Qual o objetivo? 
Aqui devemos identificar o objetivo da tomada de decisão. Eles aparecem geralmente na forma de maximização de lucros ou receitas, minimização de custos, perdas, etc. 
A função objetivo é a expressão que calcula o valor do objetivo (lucro, custo, receita, perda, etc.), em função das variáveis de decisão. 
Quais as restrições? 
Cada restrição imposta na descrição do sistema deve ser expressa como uma relação linear (igualdade ou desigualdade), montadas com as variáveis de decisão. 
Resolução gráfica de problemas de Programação Linear
Os problemas de programação linear que envolvem apenas duas variáveis de decisão podem facilmente ser resolvidos por método gráfico. Um problema com três variáveis também pode ser resolvido graficamente, embora, na maioria das vezes, isso não seja fácil. A partir de quatro variáveis, a resolução gráfica não é mais possível. 
Em programação linear podem ocorrer 4 diferentes tipos de problemas, de acordo com suas respostas: 
· Problemas com uma única solução ótima; 
· Problemas com soluções múltiplas: este caso ocorrerá quando a região viável for fechada e a última reta que delimita esta região for perpendicular ao vetor gradiente; 
· Problemas com solução infinita: este caso ocorrerá quando a região viável for aberta e quanto maior for o valor assumidopor uma das variáveis xi, maior será o valor da função objetivo.
O problema geral da Programação Linear pode ser descrito da seguinte forma: Dado um conjunto de “m” desigualdades ou equações lineares em “n” variáveis, queremos determinar valores não-negativos dessas variáveis que satisfarão as restrições e maximizarão ou minimizarão alguma função linear das variáveis. Matematicamente, temos:
Max (ou Min) Z= C1 x1 + C2 x2 + ...+ Cn xn
Sujeito a:
≤
ai1 x1 + ai2 x2 + ...+ ain xn
=
bi
,
para i=1,2, ..., m
≥
xj ≥ 0
,
para j = 1,2,...,n
onde para cada restrição um e somente um dos sinais ≥ , = , ≤ vale, mas o sinal varia de uma restrição para outra.
Utilizando a Função Solver
Dada a equação abaixo de folgas, temos o seguinte passo a passo:
Maximizar: z = 4 x1 + x2
Sujeito a 2 x1 + 3 x2 + f1 = 24
 2 x1 + x2 + f2 = 8
 x1, x2, f1, f2 <=0
CONSIDERAÇÕES FINAIS
A Pesquisa Operacional é uma ferramenta prática que oferece subsídios para a atividade de gestão. Como ferramenta quantitativa, fornece parâmetros decisórios confiáveis, considera cenários e estabelece, por meio de modelos matemáticos, visualizações de possíveis soluções de problemas que apresentam variáveis, restrições, e função objetivo, analisadas por meio de cálculos estruturados em fases. Desta forma, a P.O. constitui-se de um moderno instrumental para a tomada de decisões.
Em face da globalização as empresas se encontram em mercados cada vez mais competitivos, exigindo que as mesmas, tomem diversas decisões que, quando não bem fundamentadas e analisadas, podem levar ao fracasso. A pesquisa operacional, devido ao seu caráter multidisciplinar e cientifico, pode produzir contribuições significativas, podendo ser estendida por praticamente todos os ramos do conhecimento, desde a engenharia à medicina, em especial na gestão empresarial. 
Com todos os dados levantados, pesquisas e argumentações, pode concluir-se que a Pesquisa Operacional, aliada á Programação Linear tem muito a contribuir dentro das empresas, pois a maximização do lucro é um ponto fundamental e talvez o primordial que o administrador deve buscar nestas empresas. Desta forma, este estudo pode nos mostrar qual o papel da Pesquisa Operacional dentro de uma empresa, orientada ao administrador, com exemplos nítidos da utilização das ferramentas da Pesquisa Operacional, como por exemplo, a Programação Linear.
REFERÊNCIAS BIBLIOGRÁFICAS
Boldrini, José Luiz; Costa, Sueli I. R.; Figueiredo, Vera Lúcia; Wetzler, Henry G. Álgebra Linear. 3a Edição. Editora Harbra, 1980.
Puccini, Abelardo de Lima; Pizzolato, Nélio Domingues. Programação Linear. Livros Técnicos e Científicos, 1987.
Andrade, Eduardo Leopoldino de. Introdução à Pesquisa Operacional – Métodos e Modelos para a Análise de Decisão. Livros Técnicos e Científicos, 2a Edição, 1998
http://www.inf.ufpr.br/ess07/Meus_Programas/PO/Textos/unioeste.pdf Acesso em 10 nov 2013.
Lucro: z = 4 x1 + x2