aula de 01 a 10 pesquisa operacional

Prévia do material em texto

Aula 1 Introducao a pesquisa operacional
O que e pesquisa operacional? A Pesquisa Operacional, como o próprio nome já diz, abrange a pesquisa sobre operações, atividades ou ainda é utilizada em problemas para se resolver como coordenar e conduzir as operações, as atividades em uma organização.
Qual a Origem da Pesquisa Operacional? A origem da Pesquisa Operacional deu-se em torno de 1939 na Inglaterra, durante a Segunda Guerra Mundial. O aparecimento da Pesquisa Operacional é creditado a estudos feitos por cientistas contratados para criar e aperfeiçoar estratégias e táticas militares, na época, limitadas
Na verdade, durante muitos anos, a Pesquisa Operacional foi estudada e usada somente nas organizações militares. Por conta do sucesso atingido por essa ciência, no que diz respeito a atingir objetivos e metas, as grandes empresas começaram a utilizá-la.
A propagação da Pesquisa Operacional nos Estados Unidos durante e após a guerra pode ser creditada principalmente à equipe de cientistas liderada por George B. Dantzig, equipe esta que foi convocada durante a guerra.
No Brasil, a Pesquisa Operacional só surgiu no início da década de 60. Em 1969, foi fundada a Sociedade Brasileira de Pesquisa Operacional (SOBRAPO).
Podemos dizer que um modelo é uma representação de um sistema real. Se o sistema já existir, o modelo deve pretender reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No caso de se tratar de um projeto a ser executado, o modelo é utilizado para definir a estrutura ideal do sistema. Um modelo matemático é composto por três conjuntos principais de elementos:
As variáveis de decisão e parâmetros- As variáveis de decisão são as incógnitas a serem determinadas pela solução do modelo, enquanto que os parâmetros são valores fixos no problema.
As restrições - Utilizadas para levar em conta as limitações físicas do sistema, as restrições limitam as variáveis de decisão a seus valores possíveis ou viáveis.
Função – objetivo - É uma função matemática que define o objetivo da solução em função das variáveis de decisão.
A formulação do modelo depende diretamente do sistema que precisa ser representado do problema em questão. A função-objetivo e as funções de restrições podem ser lineares ou não lineares. As variáveis de decisão podem ser contínuas ou discretas, como, por exemplo, variáveis inteiras ou mesmo binárias, e os parâmetros podem ser determinísticos ou probabilísticos.
Exemplos de Modelagem – Problema do Alfaiate
Um alfaiate tem disponíveis os seguintes tecidos: 16 metros de algodão, 11 metros de seda e 15 metros de lã. Para um terno, são necessários 2 metros de algodão, 1 metro de seda e 1 metro de lã. Para um vestido, são necessários 1 metro de algodão, 2 metros de seda e 3 metros de lã. Se um terno é vendido por $300,00 e um vestido por $500,00, modele este problema de forma a determinar quantas peças de cada tipo o alfaiate deve fazer de modo a maximizar o seu lucro.
Chamaremos 
X¹ – quantidade de ternos a serem produzidos
X² – quantidade de vestidos a serem produzidos
Identificamos agora a função-objetivo: maximizar o lucro total obtido com a produção dos 2 produtos 
Max Z = 300x¹+ 500x²
E as restrições? como ficam? 
A restrição do algodão 
2x¹+x²≤16
A restrição da seda 
X¹+2x²≤ 11
A restrição da la
X¹+3x²≤15 
RESOLVENDO? 
Temos que lembrar que x¹ e x² representam unidades de produto a serem produzidos e, portanto, não podem assumir valores negativos.
x¹≥0 e x²≥ 0
O modelo ficara então
Sujeito a 2x¹+x²≤16 restricao de algodão
X¹+2x²≤11 restricao a seda
X1+3x²≤15 restricao a la
X¹≥0
x²≥0
Uma companhia de aluguel de caminhões possuía dois tipos de caminhões: o tipo A, com 2 metros cúbicos de espaço refrigerado e 4 metros cúbicos de espaço não refrigerado, e o tipo B, com 3 metros cúbicos refrigerados e 3 não refrigerados. Uma fábrica precisou transportar 90 metros cúbicos de produto refrigerado e 120 metros cúbicos de produto não refrigerado. Quantos caminhões de cada tipo ela deve alugar, de modo a minimizar o custo, se o aluguel do caminhão A era $0,30 por km e o do B, $0,40 por km? Elabore o modelo de programação linear que represente esta situação.
Resolvendo=
X¹ - Quantidade de caminhões tipo A
X² - Quantidade de caminhões tipo B
Identificaremos agora a função do objetivo minimizar os custos
Min=Z 0,30x¹ + 0,40x²
E as restrições? como ficam?
A restrição do espaço refrigerado = 2x¹+ 3x²≤90
A restricao do espaco não refrigerado = 4x¹+3x²≤120
Temos que lembrar que x e x representam quantidade de caminhões e, portanto não podem assumir valores negativos
X¹≥0
X²≥0
O modelo ficara então Min Z=0,30x¹+0,40x²
Sujeito de a 2x¹+3x²+ 0,40x²
Sujeito a= 2x¹+3x²≤90 restricao do esp refrigerado
4x¹+3x²≤120 restricao espaco não refrigerado
x¹≥0
x²≥0
Uma determinada companhia é grande fabricante de vidros de alta qualidade, produzindo um grande número de portas e janelas de vidro. A companhia possui 3 fábricas, sendo que na fábrica 1 são feitas as esquadrias de alumínio, na fábrica 2 são feitas as esquadrias de madeira e na 3 os produtos (portas e janelas) são montados. Como os lucros estão caindo, a diretoria resolveu parar a produção de alguns produtos que não estão vendendo bem.
Para aproveitar a ociosidade que irá surgir no parque de produção, dois novos produtos serão lançados no mercado. Um desses produtos (produto1) é uma porta de vidro com esquadrias de alumínio e o outro (produto 2) é uma janela com esquadrias de madeira. Após uma pesquisa de mercado, o Departamento de Vendas concluiu que esses 2 novos produtos terão grande aceitação e todas as unidades produzidas serão vendidas.
As informações disponíveis, por dia, para a produção desses 2 novos produtos estão mostrados na tabela a seguir.
Resolvendo
Chamaremos de x¹ nº de unidade de produto 1 a serem produzidas por dia
Chamaremos de x² nº de unidade de produto 2 a serem produzidas por dia
Isto e xᴶ(j=1,2) a quantidade do produto j ser produzida por dia
Identificaremos a função-objetivo maximizar o lucro total obtido com a produção de 2 produtos
Maximizar Z = 3x¹ + 5 x²
E as resticoes ? como ficam ?
O valores que x¹ e x ² podem assumir estao restritos pelas limitações da empresa que são as horas disponíveis em cada uma das fabricas 1 são 4 horas, ou seja, 
x¹≤4
As restrições semelhantes para as fabricas 2 e 3 são
2x²≤12
3x¹+2x²≤18
Devemos lembrar que x¹ e x² representam unidades de produtos a serem produzidas e, por tanto, não podem assumir valores negativos
x¹≥0, x²≥0
ficamos então com o modelo
maximizar Z= 3x¹+ 5x² - função- objetivo
sujeito a x¹≤4
2x²≤12 restricao do modelo
3x¹+2x²≤18
x¹≥0, x²≥0 restricao de não negatividade
Uma determinada confecção opera com dois produtos: calças e camisas. Como se trata de produtos semelhantes, possuem uma produtividade comparável e compartilham os mesmos recursos.
A programação da produção é realizada por lotes de produto. O Departamento de Produção informa que são necessários 10 homens/hora para um lote de calças e 20 homens/hora para um lote de camisas.
Sabe-se que não é necessária a mão de obra especializada para a produção de calças, mas são necessários 10 homens/hora desse tipo de mão de obra para produzir um lote de camisas. O Departamento Pessoal informa que a força máxima de trabalho disponível é de 30 homens/hora de operários especializados e de 50 homens/hora de não especializados.
A máquina 2 pode produzir um lote de calças a cada 30 horas e um lote de camisas a cada 35 horas, não podendo ser utilizada por mais de 130 horas no período considerado. São necessários dois tipos de matéria-prima para produzir calças e camisas. Na produção de um lote de calças, são utilizados 12 quilos de matéria-prima A e 10 da B. Na produção de um lote de camisas, são utilizados 8 quilos da matéria-prima A e 15 da B.
Max Z= 800x¹+500x²
Sujeito a = 20x¹+10x²≤50
10x¹≤30
20x¹+10x²≤80
35x¹+30x²≤130
8x¹ + 12x²≤ 120
15x¹ + 10x²≤ -100
X¹≥0
X²≥0
As faUm estudo de pesquisa operacional geralmente envolveas seguintes fases:ses do Estudo de Pesquisa Operacional
Definicao do problema- A definição do problema baseia-se em três aspectos principais:
• descrição exata dos objetivos do estudo;
• identificação das alternativas de decisão existentes;
• reconhecimento das limitações, restrições e exigências do sistema.
A descrição dos objetivos é muito importante em todo o processo, pois, a partir desta definição, o modelo é concebido. É essencial também que as alternativas de decisão e as limitações existentes sejam todas explicitadas para que as soluções obtidas ao final do processo sejam válidas e aceitáveis.
Construcao do modelo - É preciso se escolher bem o modelo para que a solução tenha qualidade. Se o modelo que se elaborou tem a forma de um modelo conhecido, podemos obter a solução através de métodos matemáticos convencionais. Se o modelo tiver relações matemáticas muito complexas, precisaremos utilizar combinações de metodologias.
Solucao do modelo - Nesta fase de procurar e encontrar uma solução para o modelo proposto, geralmente utilizamos técnicas matemáticas existentes. Se isso não for possível, cria-se um novo algoritmo, mais adequado, no que diz respeito a tempo e precisão de resposta. Tanto a utilização de técnicas existentes quanto a criação de algoritmos exige um conhecimento profundo das técnicas existentes.
Validacao do modelo - Um modelo é válido se ele for capaz de fornecer uma previsão aceitável do comportamento do sistema. Um método comum de validação do modelo é analisar seu desempenho com dados antigos e verificar se os resultados conseguem reproduzir o comportamento que o sistema apresentou anteriormente.
Implemetacao da solução - Agora é o momento de se investir em regras operacionais. Eventualmente, os valores da nova solução, quando levados à prática, podem demonstrar a necessidade de correções, exigindo a reformulação do modelo em algumas de suas partes.
Aula 02 introducao a pesquisa operacional
O que e a programação linear procura fazer? Propoe a maximizar ou minimizar uma função linear dita FUNCAOI OBJETIVO, respeitando um sistema de igualdades ou desigualdades, de funções lineares. Estas funções lineares são as RESTRICOES do modelo ou problema.
De maneira geral, as restrições podem representar limitações de recursos disponíveis, como capital, mão de obra, recursos minerais, ou fatores de produção, ou mesmo condições, exigências ou necessidades que devem ser obedecidas no problema. No modelo, essas restrições determinam uma região, região esta que dizemos ser o CONJUNTO VIÁVEL para as soluções.
Que técnicas existem para encontrarmos uma solução ótima?  
 Dentre as várias técnicas existentes para a determinação da solução, podemos citar:
Programa linear - A Programação Linear é usada para analisar modelos onde as restrições e a Função Objetivo são lineares.
A Programação Inteira - se aplica a modelos que possuem variáveis inteiras ou discretas.
A Programação Dinâmica - é utilizada em modelos onde o problema completo pode ser decomposto em subproblemas.
A Programação Estocástica - é aplicada a modelos onde os parâmetros são descritos por funções de probabilidade.
A Programação Não Linear - é utilizada em modelos contendo funções não lineares.
A Formulação do Modelo de Programação Linear
Para se resolver um problema de Programação Linear, devemos formulá-lo definindo a Função Objetivo e as restrições e, para isso, precisamos definir as variáveis de decisão envolvidas.
Definimos, a princípio, o objetivo do problema. Como exemplos de Função Objetivo, podemos ter os casos de maximizar lucros ou desempenhos, minimizar custos, perdas, ou tempo.  
Com relação às variáveis de decisão, de maneira geral, estas variáveis são não negativas, já que quase sempre são representativas de questões positivas. As variáveis de decisão e a Função Objetivo estão sujeitas a uma série de restrições, representadas por equações ou, na maioria das vezes, inequações.
Em um problema de Programação Linear, todas as funções envolvidas são lineares, em outras palavras, todas as relações entre as variáveis devem ser lineares, significando que as quantidades envolvidas são proporcionais de alguma forma.
A linearidade pode ser uma característica determinante no que se refere à simplificação da estrutura matemática envolvida, no entanto pode ser problemática para se representar fenômenos não lineares.
Considerando todas as decisões possíveis que satisfazem as restrições, as chamadas decisões viáveis, procuramos determinar aquela decisão que é a “melhor”, a solução ótima, àquela que proporciona maior contribuição total do lucro, menor custo, maior retorno: uma decisão ótima.
O Modelo de Problema de Programação Linear
Como sabemos então, o Problema de Programação Linear (PPL) é um problema de programação matemática em que a FunçãoObjetivo e as restrições são funções lineares.
Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto P1 é de 1000 unidades monetárias e o lucro unitário de P2 é de 1800 unidades monetárias. A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo anual de produção disponível para isso é de 1200 horas. A demanda esperada para cada produto é de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual é o plano de produção para que a empresa maximize seu lucro nesses itens? Construa o modelo de Programação Linear para esse caso.
Navegue na tela e veja como modelar o problema:
Teoremas Importantes
A ideia do estudo de Programação Linear é encontrarmos a solução ótima dos problemas. Para isso, devemos atender aos teoremas cujos enunciados extraímos do livro Programação Linear como instrumento da pesquisa operacional, de Eduardo Jose Franco dos Passos.
Teorema 1: Se o problema de Programação Linear tem solução ótima, então esta solução ETA tem, pelo menos, um ponto extremo do polido de soluções viáveis.
Teorema 2: Se a região de soluções viáveis de um problema de programação linear é não vazia, então existe uma solução ótima.
Teorema 3: O conjunto de soluções viáveis de um Problema de Programação Linear é um conjunto convexo.
Teorema 4: O conjunto de soluções viáveis de um Problema de Programação Linear tem um número finito de pontos extremos (vértices).
Resolução Gráfica
Quando temos somente duas variáveis de decisão, podemos encontrar a solução ótima graficamente.
Vamos considerar a reta 2x1+x2=6 representada abaixo. Os pontos pertencentes a reta atendem à igualdade. Como determinar se os pontos (x1, x2) da região acima da reta são pontos de tal forma que 2x1+x2≤6 ou 2x1+x2≥6?
No nosso exemplo, o ponto (0,0) está abaixo da reta. Substituindo (0,0) em 2x1+x2, obtemos 0, que é menor que 6. Assim, a região abaixo da reta 2x1+x2=6 é a região 2x1+x2≤6, pois o ponto (0,0) precisa atender à inequação.
A região sinalizada em vermelho é a região 2x1+x2≤6.
Como resolver graficamente?
Primeiro, devemos estabelecer os eixos que irão representar as variáveis de decisão. Devemos construir um eixo com as dimensões x1 e x2.
Encontrar o conjunto de soluções viáveis: a região viável. Precisamos identificar os valores (x1, x2) que são permitidos pelas restrições. Depois de traçarmos as inequações (que representam as restrições do problema), um poliedro convexo é formado. Este poliedro contém todas as soluções do problema, uma vez que qualquer ponto dentro desta região ou na aresta do poliedro atende às restrições do problema. 
Escolher o ponto da região viável que maximiza o valor da Função Objetivo. Esta escolha pode ser feita dando valores a z, a Função Objetivo, e observar o quanto podemos “melhorar” o valor de z, sem sair da região viável, clique no PDF. Aula 2 pag 14
Podemos também utilizar o vetor gradiente, que é formado pelos coeficientes da Função Objetivo (c1, c2). Este vetor tem a origem na origem dos eixos e, traçando perpendiculares a este vetor, podemos procurar o ponto utilizando estas perpendiculares. Clique no PDF.