PESQUISA OPERACIONAL parte 1 (3)

Prévia do material em texto

�PAGE �
�PAGE �1�
PESQUISA OPERACIONAL
INTRODUÇÃO
A Pesquisa Operacional (PO) é um conjunto de técnicas matemáticas que visam fornecer soluções para problemas específicos, visa a aplicação mais eficiente de recursos limitados na obtenção de resultados “ótimos” para os objetivos a serem atingidos.
Pode-se dizer que seu nascimento oficial deve-se a iniciativa dos serviços militares ingleses no início da 2ª Guerra Mundial, por causa dos esforços de guerra, cientistas e pesquisadores ingleses prestaram apoio ao seu governo na solução de importantes problemas de natureza tática e estratégica, na tentativa de, em conjunto com os militares usar mais adequadamente os poucos meios disponíveis para fazer frente a um inimigo mais poderoso.
Deste modo, alguns problemas forma solucionados, como por exemplo: a determinação do número mínimo de aviões ingleses a serem mantidos em condições de defesa frente a ataques alemães, visando se possível liberar outros aviões para realizar incursões às instalações e áreas inimigas no continente europeu.
Os cientistas foram chamados para fazer pesquisa em operações militares (daí o nome de Pesquisa Operacional) e seus esforços foram considerados decisivos em várias operações de guerra.
Após a guerra, com o retorno destes cientistas à vida civil (universidades, centros de pesquisa e indústrias) inúmeras outras aplicações foram desenvolvidas e, com o advento do computador, problemas cada vez mais complexos e com grande número de variáveis e equações puderam ser solucionados.
DEFINIÇÃO 
Não existe uma definição padrão para Pesquisa Operacional (PO), vejamos algumas delas:
• “A Pesquisa Operacional é uma ferramenta, ou melhor, um conjunto de ferramentas. È uma fonte de modelos e de métodos de como resolver os modelos. Também orienta sobre que dados coletar e como lidar com a imprecisão dos dados”. Pierre Jacques Ehrlich
• “Pesquisa Operacional é uma abordagem científica à resolução de problemas para administração executiva”. Harvey M. Wagner
• “A Pesquisa Operacional, que diz respeito à alocação eficiente de recursos escassos, é tanto uma arte como uma ciência. A arte reside na habilidade de exprimir os conceitos de eficiente e de escasso por meio de um modelo matemático bem definido para uma determinada situação; a ciência consiste na dedução de métodos computacionais para solucionar tais modelos”. Richard Bronson
• “A Pesquisa Operacional é um método científico de tomada de decisão”. James E. Shamblin e G. T. Stevens Jr.
MODELO
A descrição de um sistema por um modelo torna possível analisá-lo e testar várias alternativas, sem interromper o seu funcionamento. Outra vantagem é que o modelo torna, normalmente, o problema mais intelegível e pode esclarecer importantes relações entre as variáveis.
Assim temos o seguinte roteiro:
Para um sistema complexo original constrói-se um modelo, que representa da melhor maneira possível o sistema em estudo;
Determinação de uma solução – através do emprego de alguma técnica matemática para solução do modelo;
Teste desta solução no modelo – utilizando dados existentes, compara-se a performance do sistema e a indicada pelo modelo; verifica-se também quais as faixas de valores das variáveis, para as quais a solução sugerida é valida.;
 Aplicação da solução no sistema real – a implantação de uma solução no sistema real pode implicar em mudanças de rotinas e necessitam de grande interesse (e empenho) por parte de quem decide.
Um modelo define as variáveis importantes e quais os dados necessários para a análise do sistema. A coleta de dados é pois de extrema importância para dar confiabilidade ao modelo e sua solução.
Quando a Pesquisa Operacional é aplicada num contexto de planejamento, a solução consiste normalmente num conjunto de valores os mais favoráveis para as variáveis de decisão, com alguma informação quanto ao custo de se afastar destes valores. Porém quando a Pesquisa Operacional é usada para desenvolver um sistema operacional, tal como um meio para controlar estoques, então a solução consiste em um conjunto de regras de decisão.
O conjunto de regras de decisão passa pela definição do problema e dos fatores que o influenciam, estabelecendo critérios e objetivos, formulando um modelo ou relações entre as variáveis, a fim de identificar e selecionar a melhor alternativa e implementar a decisão.
 VISÃO GERAL DO PROCESSO DE DECISÃO:
 
�
PRINCIPAIS TÉCNICAS E INSTRUMENTOS DA PESQUISA OPERACIONAL
A Pesquisa Operacional (PO) se aplica a uma série de situações e diversos métodos foram desenvolvidos, de acordo com o tipo de problema estudado. Assim, entre outros, temos:
A) PROGRAMAÇÃO LINEAR → os problemas de Programação Linear 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 lucro ou minimização de custo;
B) TEORIA DOS JOGOS → um dos campos mais complexos de investigação em PO, é o estudo da competição entre oponentes. Seus fundamentos foram lançados por John Neumman, que em 1927 demonstrou o Teorema Minimax;
C) TEORIA DAS FILAS → 	a teoria das Filas estuda, do ponto de vista matemático, filas como seqüência de espera. A formação de filas de espera ocorre quando a solicitação por serviço supera a capacidade de efetuá-lo;
D) PROGRAMAÇÃO DINÂMICA → é um método matemático, desenvolvido há mais de 60 anos pelo americano Ricard Bellman, que permite determinar a solução ótima de um sistema que opera ou cujas decisões ocorrem em fase ou em conseqüência;
E) TEORIA DOS GRAFOS → é a base para o estudo das redes, ao contrário da maioria dos ramos da matemática originários de especulações técnicas, nasceu do confronto de problemas práticos que tinham propriedades e estruturas semelhantes;
F) MODELOS DE CONTROLE DE ESTOQUE → as empresas mantém estoques de matérias-primas e produtos acabados. Os estoques de matérias-primas servem como insumo para o processo de produção e os estoques de produtos acabados são usados para satisfazer a demanda dos consumidores. Como estes estoques exigem muito investimento, são importantes as decisões referentes a eles.
G) TEORIA DA DECISÃO → permite que a partir de um número finito de linhas de ações possíveis, atingir um determinado resultado. Decidir consiste em escolher uma destas linhas de ação que possibilite o resultado esperado.
PROBLEMAS DE TRANSPORTE
INTRODUÇÃO	​​​​​​​​​​​​
Há dois tipos especiais de problemas de Programação Linear, a saber, os problemas de transporte e de designação, que são frequentemente conhecidos como modelos de distribuição. O problema de transporte visa minimizar o custo total do transporte necessário para abastecer n centros consumidores (destinos) a partir de m centros fornecedores (origens). Admitimos F1, F2, ....., Fm, m depósitos onde encontramos estocados F1, F2, ............., Fm, quantidades de determinado produto. Sejam D1, D2, ......, Dn, n centros de consumo deste produto, que devem ser abastecidos pelos depósitos [Fi]. As demandas de cada centro [Dj] são variáveis. Supõe-se conhecidos os custos unitários de transportes do produto de Fi → Dj, e seja [Cij] esses custos.
O modelo linear, associado ao programa acima, pode ser apresentado pelas seguintes equações:
- Equações que traduzem as restrições impostas pelos centros de distribuição:
	
	X11 + X12 + .......... + X1n = F1
	
	X21 + X22 + .......... + X2n = F2
	_________________________
	Xm1 + Xm2 + .......... + Xmn = Fm
MÉTODO DO CANTO NOROESTE
Inicialmente constroe-se um retângulo, o qual subdividimos em m x n sub-retângulos. Assim o retângulo inicial conterá m linhas e n colunas.
Anota-se, a direita de cada linha as disponibilidades e abaixo de cada coluna as demandas.
O processo será aplicado no quadro de soluções segundo os seguintes passos:
a) comece pelo sub-retângulosuperior esquerdo (canto noroeste);
b) coloque no sub-retângulo superior esquerdo a menor quantidade permitida pela oferta e demanda correspondente;
c) atualize os valores da oferta e da demanda que foram modificados pelo passo anterior;
d) siga para o sub-retângulo da direita se houver alguma oferta restante e volte para o passo b. Caso contrário, siga para o sub-retângulo inferior e volte ao passo b.
O processo estará concluído quando o sub-retângulo inferior a direita do quadro de soluções for alcançado.
MÉTODO DO CUSTO MÍNIMO
Este método fornece uma solução inicial que depende não somente dos valores da oferta e da demanda, mais também dos custos de transporte, visando basicamente se houver uma solução inicial mais próxima da ótima do que aquela fornecida pelo método do canto noroeste.
Os seguintes passos devem ser seguidos nos quadros de soluções e de custos:
localize no quadro de custos o menor custo, que não tenha oferta ou demanda nula;
coloque no sub-retângulo correspondente do quadro de soluções a menor quantidade permitida pela oferta e demanda correspondente;
atualize os valores da oferta e demanda que foram modificados pelos passos anteriores.
O processo continua até que sejam esgotados as ofertas de todos as origens e atendidas as demandas de todos os destinos.
EXERCÍCIOS
Uma empresa possui três centros de distribuição de mercadorias: D1, D2 e D3, que abastecem quatro lojas da rede: L1, L2,, L3 e L4 da mesma mercadoria. Os custos unitários de transporte, a demanda e a oferta da mercadoria são dados na tabela abaixo:
 |	L1	L2	L3	L4 |	oferta
-------|---------------------------------|------------
 D1 |	10	5	6	7 |	25
-------|---------------------------------|------------
 D2 |	8	2	7	6 |	25
-------|---------------------------------|------------
 D3 |	9	3	4	8 |	50
-------|---------------------------------|------------
DEM| 15	20	30	35 |	
Identifique o plano ótimo de transporte para a empresa, utilizando os métodos do canto noroeste e custo mínimo.
Três postos de gasolina da rede Alfa: A, B, e C, necessitam de 80 mil, 70 mil e 40 mil litros de gasolina comum por semana, respectivamente. É possível suprir estas demandas partindo de três depósitos 1, 2 e 3 que dispõem de 100 mil, 60 mil e 30 mil litros respectivamente. Os custos de transporte em centavos de cada litro é dado na tabela abaixo:
 |	A	B	C
	------|--------------------------
	 1 |	8	4	2
	------|-------------------------
	 2 |	12	6	6
	------|--------------------------
	 3 |	11	12	8	
Identifique o plano ótimo de transporte para a empresa, utilizando os métodos do canto noroeste e custo mínimo.
Uma empresa fabrica um determinado produto em três fábricas: X, Y e Z. O produto destina-se a três centros de consumo I, II e III. Sabe-se que as três fábricas tem capacidade semanal de produção de 40 mil, 30 mil e 20 mil unidades respectivamente. Os centros de consumo necessitam semanalmente de 30 mil, 40 mil e 20 mil unidades. Os custos de transporte são dados na tabela abaixo:
 |	I	II	III
	------|--------------------------
	 X |	8	4	2
	------|-------------------------
	 Y |	12	6	6
	------|--------------------------
	 Z |	11	12	8	
Identifique o plano ótimo de transporte para a empresa, utilizando os métodos do canto noroeste e custo mínimo.
PROCESSO DE OTIMIZAÇÃO DA SOLUÇÃO BÁSICA INICIAL DA TEORIA DE TRANSPORTE
No processo de otimização tem-se que levar em conta as seguintes regras na tabela auxiliar.
	a) construir uma tabela auxiliar;
b) colocar nos sub-retângulos onde ocorreram designações, o seu respectivo custo; 
c) os demais sub-retângulos onde não ocorreram designações devem ser divididos ao meio, e colocar na parte inferior do sub-retângulo o seu respectivo custo;
d) colocar zero no sub-retângulo correspondente a última coluna e penúltima linha;
e) repetir os valores de custo dos sub-retângulos da última linha onde ocorreram designações;
f) o valor do sub-retângulo não subdividido tem que ser igual a soma dos valores dos sub-retângulos extremos;
g) o valor da parte superior do sub-retângulo dividido tem que ser igual a parte inferior menos a soma dos sub-retângulos extremos.
Após o preenchimento da tabela auxiliar, escolhe-se para participar da otimização, o sub-retângulo dividido que tiver o maior valor negativo.
Em seguida passa-se para a tabela auxiliar, colocando o valor de + θ , no sub-retângulo que foi escolhido no passo anterior. Temos que formar um circuito nesta tabela, de tal forma que nos sub-retângulos de cada linha e coluna que participam das designações, tenhamos um + θ positivo e um – θ (negativo).
Após completarmos o circuito, atribuiremos um valor ao θ que deu início ao circuito, igual ao seu valor correspondente na linha (-θ).
O passo seguinte e construir uma nova tabela principal e uma auxiliar.
A tabela principal terá suas designações a partir do sub-retângulo que deu início ao circuito, com o valor que foi atribuído ao θ.
Utilizaremos também os demais sub-retângulos que tiveram designações. Para a tabela auxiliar, será utilizada as mesmas regras anteriores e só chegaremos a solução final quando não tivermos nenhum valor negativo na parte superior dos sub-retângulos divididos.
�
PROBLEMA DO CAIXEIRO VIAJANTE
Sejam quatro empresas A1, A2, A3 e A4 localizadas em cidades distintas. A empresa A1 designa um seu caixeiro viajante para visitar as empresas A2, A3 e A4 e voltar a A1, sua sede. Os diferentes itinerários possíveis para o viajante são em número de (n – 1)! Neste exemplo será (4 – 1)! = 6, a saber:
	1) A1	A2	A3	A4	A1
	
	2) A1	A2	A4	A3	A1
	3) A1	A3	A2	A4	A1
	4) A1	A3	A4	A2	A1
	5) A1	A4	A2	A3	A1
	6) A1	A4	A3	A2	A1
O problema consiste em decidir entre todos os itinerários possíveis, aquele que minimiza os gastos totais do viajante, estando implícito o conhecimento dos gastos de viagem entre duas cidades.
Admitindo-se que os gastos de viagem entre duas cidades é proporcional à distância, o problema consiste em determinar a trajetória mínima envolvendo as cidades.
	
	
MODELO
CÁLCULOS
DECISÕES
PROBLEMA
 ANÁLISE