resumo Pesquisa operacional aulas até av2

Prévia do material em texto

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:
PROCESSO DE TOMADA DE DECISÃO
Um estudo de pesquisa operacional geralmente envolve as seguintes fases:
definição do problema;
(2) construção do modelo;
(3) solução do modelo;
(4) validação do modelo;
(5) implementação da solução.
Construir um modelo científico (tipicamente matemático) que atenda a condição:
as características do problema a ser modelado
os dados de entrada necessários
que saídas devem ser oferecidas
Modelo matemático 
Modelo de Programação Linear (PL)
	Variáveis contínuas 
	Comportamento linear (as funções são todas lineares)
Modelo de Programação matemática (mista)
	Exibe qualquer tipo de não-linearidade
Modelo de Programação Inteira
	Qualquer variável não pode assumir valores contínuos (resultado tem q ser inteiro)
 
PROCEDIMENTOS PARA RESOLVER O MODELO
Resolução gráfica do modelo
Resolução analítica (uso de algoritmo)
E se nao resolver?
Desenvolver procedimentos específicos para o modelo em questão. 
Reformular o modelo.
Mudar a definição do problema de forma a simplificá-lo .
Implementação no mercado
Treinamento dos usuários finais para usar e interpretar os resultados do modelo. 
Essa implantação deve ser acompanhada para se observar o comportamento do sistema com a solução adotada.
MODELO MATEMÁTICO
Na modelagem de problemas devemos estabelecer:
As variáveis do problema (variáveis de decisão): 
são as incógnitas a serem determinadas pela solução do modelo;
(2) A função-objetivo: 
é uma função matemática que define o objetivo da solução em função das variáveis de decisão. (maximizar ou minimizar determinado objetivo)
(3) 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;
(4) As restrições de não-negatividade.
 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 ele precisará de: 2 metros de algodão, 1 metro de seda e 1 metro de lã e para vestido: 1 metro de algodão, 2 metros de seda e 3 metros de lã. Se um terno é vendido por R$300,00 e um vestido por R$500,00, modele este problema de forma a se determinar quantas peças de cada tipo o alfaiate deve fazer de modo a maximizar o seu lucro? 
AS VARIÁVEIS DO PROBLEMA (VARIÁVEIS DE DECISÃO) 
Que quantidade de cada produto deve-se fabricar para obter o lucro máximo? 
A FUNÇÃO-OBJETIVO 
Um terno é vendido por R$300,00 (x1)
Um vestido por R$500,00 (x2)
L=300x1+500x2
o alfaiate deseja maximizar o seu lucro. 
AS RESTRIÇÕES
Um alfaiate tem disponíveis os seguintes tecidos: 
16 metros de algodão
11 metros de seda
15 metros de lã. 
Terno:
2 metros de algodão 
1 metro de seda
1 metro de lã
Vestido: 
1 metro de algodão
2 metros de seda
3 metros de lã. 
MODELO MATEMÁTICO
L= 300x1+500x2
Sujeita a
2x1+1x2≤16
1x1+2x2≤11
1x1+3x2≤15
X1≥0
X2≥0
A indústria Alumínio Feliz S.A. fabrica 3 tipos diferentes de lâminas de alumínio: espessuras fina, média ou grossa. Toda produção da companhia é realizada em duas fábricas, uma localizada em São Paulo e a outra no Rio de Janeiro. A empresa precisa entregar 16 toneladas de lâminas finas, 6 toneladas de lâminas médias e 28 toneladas de lâminas grossas. Devido à qualidade dos produtos da Alumínio Feliz S.A. há uma demanda extra para cada tipo de lâmina. A fábrica de São Paulo tem um custo de produção diário de R$ 100.000,00 para cada capacidade produtiva de 8 toneladas de lâminas finas, 1 tonelada de lâminas médias e 2 toneladas de lâminas grossas por dia. O custo de produção diário da fábrica do Rio de Janeiro é de R$ 200.000,00 para cada produção de 2 toneladas de lâminas finas, 1 tonelada de lâminas médias e 7 toneladas de laminas grossas por dia. Quantos dias cada uma das fábricas deverá operar para atender aos pedidos ao menor custo possível? Elabore o modelo.
Resolução
Min Z = 100.000x1 + 200.000x2
 
Sujeito a: 	
8x1 + 2x2 ≥ 16 
x1 + x2 ≥ 6 
2x1 + 7x2 ≥ 28 
x1 0
x2 0
Uma confeitaria produz dois tipos de bolos de sorvete: chocolate e creme. Cada lote de bolo de chocolate é vendido com um lucro de 3 u.m e os lotes de bolo de creme com um lucro de 1 u.m . Contratos com várias lojas impõem que sejam produzidos no mínimo 10 lotes de bolos de chocolate por dia e que o total de lotes (creme e chocolate) fabricados nunca seja menor que 20. O mercado só é capaz de consumir até 40 lotes de bolos de creme e 60 de chocolate. As máquinas de preparação do sorvete disponibilizam 180 horas de operação, sendo que cada lote de bolos de chocolate consome 2 horas de trabalho e cada lote de bolos de creme 3 horas. Formule o modelo e elabore o gráfico. 
Max Z = 3x1 + x2
 
Sujeito a:
x1 ≥ 10 
x1 + x2 ≥ 20 
x1 ≤ 60 
x2 ≤ 40 
2x1 + 3x2 ≤ 180 
x1 ≥ 0
x2 ≥ 0
AS fases de um projeto são; formulação, construção do modelo, obtenção da solução, testar e avaliar o modelo e avaliação. E é na fase de Formulação, que determinamos o objetivo e há a identificação das restrições como também ocorrem o esboço dos possíveis caminhos a serem percorridos.
Programacao linear
A Programação Linear trata de modelos de programação matemática onde as restrições e a função objetivo são 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.
Max Z = 1000x1 + 1800x2
Sujeito a: 
20x1 + 30x2 ≤ 1200
x1 ≤ 40	
x2 ≤ 30
x1 ≥ 0
x2 ≥ 0
Um gerente de um SPA chamado Só é Magro Quem Quer contrata você para ajudá-lo com o problema da dieta para os hóspedes. (Observe que ele paga bem: 40% do que você precisa!) Mais especificamente, ele precisa de você para decidir como preparar o lanche das 17:00h. Existem dois alimentos que podem ser fornecidos: cheeseburguers e pizza. São unidades especiais de cheeseburguers e pizza, grandes, com muito molho e queijo, e custam, cada, R$10,00 e R$16,00, respectivamente. Entretanto, o lanche tem que suprir requisitos mínimos de carboidratos e lipídios: 40 u.n. e 50 u.n., respectivamente (u.n. significa unidade nutricional). Sabe-se, ainda, que cada cheeseburguers fornece 1 u.n. de carboidrato e 2 u.n. de lipídios, e cada pizza fornece 2 u.n. de carboidratos e 5 u.n. de lipídios. O gerente pede inicialmente que você construa o modelo MINIMIZAR
Min Z = 10x1 + 16x2
 
Sujeito a: 
 
 x1 + 2x2 ≥ 40
 2x1 + 5x2 ≥ 50	
 x1 ≥ 0
 x2 ≥ 0
 
SINAIS IGUAIS = FORMA PADRAO
CARACTERÍSTICAS DO PPL
Separabilidade, Não negatividade, Aditividade, Proporcionalidade
OBSERVAÇÕES SOBRE O PPL
Divisibilidade: Todas as unidades de atividade podem ser 
 divididas em qualquer nível fracional.
 Certeza: Todos os parâmetros do modelo são constantes 
 conhecidas. 
Solução viável: Uma solução que satisfaz todas as restrições
 do modelo.
 Solução ótima: É a melhor solução viável que atende a função
 objetivo.
Podemos encontrar essa solução através dos seguintes métodos:
 Resolução gráfica (quando o problema envolve duas variáveis de 
 decisão.
 Resolução analítica.TEOREMAS IMPORTANTES
Teorema 1. Se o problema de programação linear tem solução ótima, então esta solução está em, pelo menos, um ponto extremo do polígono 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).
GRAFICO
2X1+3X2≥90
X1=0
3X2=90
X2=90/3 = 30
X2=0
2X1=90
X1=90/2=45
O GRAFICO SERIA:
Uma mulher tem R$ 10.000,00 para investir e seu corretor sugere investir em dois títulos, A e B. O título A é bastante arriscado, com lucro anual de 10% e o título B é bastante seguro, com lucro anual de 7%. 
Depois de algumas considerações, ela resolve investir no máximo R$ 6.000,00 no título A e no mínimo R$ 2.000 no título B. 
Como ela deverá investir seus R$ 10.000,00 a fim de maximizar o rendimento anual?
Max Z = 0,10x1 + 0,07x2
 
Sujeito a:	
x1 + x2 ≤ 10.000 	(I) X1=0 X2=10000 X2=0 X1=10000
x1 ≤ 6.000 		(II) X1=6000
x2 ≥ 2.000 		(III) X2=2000
x1 ≥ 0
x2 ≥ 0
Pontos viáveis:
 
A (0, 2.000)
	
B (6.000, 2.000)
 
C (6.000, 4.000)
 		
D (0, 10.000)
	 O Método Simplex foi desenvolvido em1947 por George B. Dantzig.
 
	é uma técnica utilizada para se 	determinar numericamente a 
	solução ótima de um modelo de Programação Linear.
	O que o método simplex faz, em linhas gerais, é resolver 	diversas vezes um sistema de equações lineares para obter 	uma sucessão de soluções básicas viáveis, cada uma melhor 	do que a anterior, até se chegar a uma solução básica ótima.
O conjunto de todas as soluções do problema de programação linear é um conjunto convexo cujos vértices, ou seja, cujos pontos extremos correspondem a soluções ditas básicas viáveis.
Sabemos ainda que se a função objetivo possui um máximo finito, então pelo menos uma solução ótima é um ponto extremo do conjunto convexo.
Uma pequena metalúrgica deseja maximizar sua receita com a venda de dois tipos de finas fitas de aço que se diferenciam em qualidade no acabamento de corte. As fitas são produzidas a partir do corte de bobinas de grande largura. Existem duas máquinas em operação. Uma das máquinas é mais antiga e permite o corte diário de 4.000m de fita. A outra, mais nova, corta até 6.000m. A venda das chapas no mercado varia com a qualidade de cada uma. Fitas produzidas na máquina antiga permitem um lucro de 3 u.m por mil metros de produção. Fitas cortadas na máquina mais moderna produzem um lucro de 5 u.m por mil metros de produção. Cada mil metros de fita cortada na máquina antiga consome 3 homens x hora de mão-de-obra. Na máquina moderna são gastos apenas 2 homens x hora. Diariamente são disponíveis 18 homens x hora para a operação de ambas as máquinas. Determinar a produção que otimiza o lucro da metalúrgica. 
Max Z = 3x1 + 5x2
Sujeito a:	
x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0
PASSO 1: ESCREVER O PPL NA FORMA PADRÃO
Max Z = 3x1 + 5x2
Sujeito a:	
x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0
PASSO 2: PASSAR A FORMA PADRÃO PARA O TABLEAU
	Forma Padrão da função objetivo
	Z - 3x1 - 5x2 = 0
	Forma Padrão das restrições
	x1 + x3 = 4
	x2 + x4 = 6
	3x1 + 2x2 + x5 = 18
	
	
	
	
	
	
	
	
	Coluna base
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
O quadro Q1 não é ótimo, pois temos na linha da função objetivo, dois valores negativos: -3 e -5. 
O quadro é ótimo quando todos os valores, nessa linha, são positivos.
Variável que entra na coluna da base: X2 (procure o menor valor numérico)
Variável que sai da coluna da base: X4 (menor valor encontrado na divisão)
Monte o próximo quadro realizando a troca acima.
	
	Z
	X1
	X2
	X3
	X4
	X5
	b
	Coluna base
	1
	-3
	-5
	0
	0
	0
	0
	X3
	0
	1
	0
	1
	0
	0
	4
	X4
	0
	0
	1
	0
	1
	0
	6
	X5
	0
	3
	2
	0
	0
	1
	18
	
	Z
	X1
	X2
	X3
	X4
	X5
	b
	Coluna base
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	Z
	X1
	X2
	X3
	X4
	X5
	b
	Coluna base
	1
	-3
	0
	0
	5
	0
	30
	X3
	0
	1
	0
	1
	0
	0
	4
	X2
	0
	0
	1 
	0
	1
	0
	6
	X5 
	0
	3 
	0
	0
	-2
	1
	6
	
	Z
	X1
	X2
	X3
	X4
	X5
	b
	Coluna base
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	Z
	X1
	X2
	X3
	X4
	X5
	b
	Coluna base
	1
	0
	0
	0
	3
	1
	36
	X3
	0
	0
	0
	1
	2/3
	-1/3
	2
	X2
	0
	0
	1
	0
	1
	0
	6
	X1 
	0
	1
	0
	0
	-2/3
	1/3
	2
O quadro é ótimo.
Z=36 x1=2 x2=6 x3=2 x4=0 x5=0
Seja a primeira tabela do método simplex para cálculo da solução de um problema de PL: z x1 x2 xF1 xF2 xF3 b 1 -3 -5 0 0 0 0 0 2 4 1 0 0 10 0 6 1 0 1 0 20 0 1 -1 0 0 1 30 Qual é o valor do elemento pivô? Certo 4 -5 -1 Errado 1 0
Localize o número mais negativo da segunda linha do quadro simplex,excluída a última coluna, e chame a coluna onde este número aparece de coluna de trabalho. Neste nosso caso é o número -5, o número mais negativo. A partir daí, forme quocientes da divisão de cada número positivo da coluna de trabalho pelo elemento da última coluna da linha correspondente. E assim,10 : 4 =2,5 e 20: 1 = 20 Designe o elemento pivô o elemento da coluna de trabalho que conduz ao menor quociente, e desta forma o elemento pivô é 4.
Analisando o quadro final do método Simplex dado abaixo, realize a identificação da solução ótima e de cada uma das variáveis. x1 x2 xF1 xF2 TI 10 0 30 0 9000 2/3 1 1/3 0 100 20/3 0 -5/3 1 500
Para encontrar a solução ótima, identifique na primeira linha o último resultado, ou seja, a coluna termo independente, logo a solução é 9000. Para determinar o valor das variáveis que em sua coluna apresenta um único valor igual a 1 e os demais igual a zero, o termo independente situado na mesma linha do valor igual a 1, será o valor da variável.Logo, x2=100 e xF2=500 . E para as variáveis que apresentam colunas com valores diversos significa que estas variáveis são iguais a zero e assim, x1=0 e xF1=0.
O PROBLEMA DUAL
	O problema dual é um modelo associado ao modelo original que busca analisar os valores dos recursos e os coeficientes da função objetivo. 
Estimar o valor ótimo da função objetivo 
Valores dos limites inferiores e superiores
	
CONSIDERAÇÕES SOBRE O PRIMAL E O DUAL 
A função objetivo: Primal é de maximização, enquanto que a do Dual é de minimização.
Os coeficientes da função objetivo do Primal são os termos constantes das restrições do Dual. 
Os termos constantes das restrições do Primal são os coeficientes da função objetivo do Dual .
As restrições do Primal são ≤, enquanto que as do Dual são do tipo ≥ 
O número de restrições do Primal é igual ao número de incógnitas do Dual.
O número de incógnitas do Primal é igual ao número de restrições do Dual. 
A matriz dos coeficientes do Primal é a transposta da matriz dos coeficientes do Dual. 
TEOREMAS IMPORTANTES
 
O dual do Dual é o Primal.
Se a k-ésima restrição do Primal é uma igualdade, então a variável yk do Dual não tem restrição de sinal.
Se a variável p do Primal não tem restrição de sinal, então a restrição p do dual é uma igualdade.
OBSERVAÇÕES SOBRE O DUAL
Quais as condições que devem ser observadas para se determinar o Dual?
Precisamos verificar se o problema for de
maximizar, então não pode haver restrição de maior ou igual.
minimizar, então não pode haver restrição de menor ou igual.
A partir de um modelo primal é possível encontrar o modelo dual ? qual seria o caminho ?
obtenção do dual ocorre da seguinte forma: - Para cada restrição será atribuída uma variável de decisão (yi) - Caso a função objetivo do primal seja de maximização o DUAL seráde minimização e cada uma de suas parcelas será o produto yi pelo termo da direita da restrição correspondente ( termo independente) - Cada variável de decisão do PRIMAL gera uma restrição do DUAL.Neste caso, o sinal será de >= e o termo da direita será o coeficiente da variável primal da função objetivo -E todas as variáveis do DUAL são não negativas. Bons estudos!
Como encontrar as restrições do modelo dual, dado o primal MaxZ= 3x1+5x2 /Sujeito a x1+2x2<=14/3x1+x2<=16 e x1 -x2<=0 , onde x1, x2 e x3>=0 ?
As restrições do tipo <= do primal serão >= no dual, onde o coeficiente da função objetivo do primal serão os termos independentes de cada restrição.Logo, as restrições do dual são: y1+3y2+y3>=3 e 2y1 +y2 -y3>=5. Sendo válido ressaltar que y1,y2 e y3>=0
Sabendo que o modelo matemático primal Z é de maximização e que apresenta as seguintes restrições, x1+2x2<=20 e 2x1+x2<=20, como encontrar a função objetivo do modelo matemático dual?
Como a função objetivo do modelo primal é de maximização, a função objetivo do modelo dual será de minimização, onde os coeficientes de cada uma das variáveis ( y) serão os termos independentes de cada uma das restrições do primal.Logo, a função objetivo do dual será Min Z= 20y1 + 20 y2
Como encontrar a função objetivo do modelo dual Z de minimização , dado apenas as restrições do modelo primal 3x1+4x2 +2x3<=12, 2x1+6x2 +x3<+15 e x1-x2-x3<=20 ?
Como encontrar a função objetivo do modelo dual Z de minimização , dado apenas as restrições do modelo primal 3x1+4x2 +2x3<=12, 2x1+6x2 +x3<+15 e x1-x2-x3<=20 ?
O PAR PRIMAL-DUAL
Resultados sobre a existência dos problemas
 
(1) Se um dos problemas tiver solução viável e sua função objetivo for limitada, então o outro problema também terá.
(2) Se um dos problemas tiver soluções viáveis, porém uma função objetivo ilimitada, então o outro problema não terá soluções viáveis.
(3) Se um dos problemas não tiver solução viável, então o outro problema não terá soluções viáveis ou terá soluções ilimitadas.
ALGORITMO DUAL SIMPLEX
	Teorema da Dualidade
	“Se um problema primal (dual) tem uma solução ótima finita, então o problema dual (primal) em também uma solução ótima finita e as funções objetivo do primal e do dual têm valores iguais.”
	
		
	INTERPRETAÇÃO ECONÔMICA DAS VARIÁVEIS DUAIS
As variáveis duais podem ser interpretadas como avaliações unitárias dos recursos, relativas às contribuições de cada um para a obtenção do lucro total.
Isso significa que, resolvendo os problemas apresentados, as variáveis duais indicam as variações que ocorrem no valor da função objetivo do primal, para variações unitárias nos níveis de recursos.
DEFINIÇÕES
(1) PREÇO-SOMBRA
Agora sabemos que cada variável yi do Problema Dual está relacionada a restrição i do problema Primal. Chamamos o valor ótimo da variável dual, yi* , de Preço-Sombra ou Preço-Dual. 
Os valores ótimos das variáveis duais, ou ainda, os Preços-Sombra, podem ser interpretados como sendo os preços que alguém estaria disposto a pagar por unidades adicionais dos recursos envolvidos nas restrições do Primal. 
Assim, cada restrição i possui um Preço de Sombra yi*.
O Preço Sombra yi* referente ao recurso i fornece o valor marginal deste recurso em relação o lucro total.
(2) CUSTO REDUZIDO
 
Cada variável de folga, ou seja, cada restrição do Dual está diretamente relacionada com uma variável original do problema Primal. Este valor é chamado de Custo Reduzido. 
Cada variável do problema original possui um determinado custo reduzido. 
Nos problemas de maximização, o Preço Sombra é o valor, yi , da variável dual.
 Nos problemas de minimização, o Preço Sombra é o valor, −yi , da variável dual.
Vale destacar que Custo Reduzido e Preço Sombra dizem respeito a alterações unitárias, podendo ser garantidas somente dentro de intervalos. 
Chama-se custo reduzido  o preço-sombra para uma restrição igual a zero.
O Preço Sombra indica o quanto irá mudar o valor da função objetivo se houver a alteração de uma unidade no fator de restrição indicado, permanecendo todos os demais coeficientes constantes. Sobe o Preço-sombra POSITIVO é possível afirmar que:
ANÁLISE DE SENSIBILIDADE
Técnica utilizada para avaliar os impactos que o programa sofre quando existem modificações nas condições de modelagem. 
MUDANÇAS
Nas quantidades de recursos;
Nos coeficientes da função objetivo;
Nos coeficientes das atividades;
Acréscimo de uma nova variável;
Acréscimo de uma nova restrição.
DOIS TIPOS DE ANÁLISE DE SENSIBILIDADE
O primeiro estabelece limites inferiores e superiores para todos os coeficientes da função objetivo e para as constantes das restrições.
O segundo verifica se mais de uma mudança simultânea em um problema altera a sua solução ótima.
Se modificarmos um coeficiente da função objetivo, teremos uma alteração no coeficiente angular da função objetivo. 
OBSERVAÇÃO
 
Quando a rotação da função objetivo em torno do extremo ótimo passa pela reta vertical, significa que não existirá o limite superior ou inferior para a declividade.
ANÁLISE DAS CONSTANTES DAS RESTRIÇÕES
Os limites relacionados às constantes das restrições têm a ver com os Preços Sombra, e não à solução ótima.
Lembrando que os Preços-Sombra equivalem à solução ótima do dual, onde as constantes das restrições são os coeficientes da Função Objetivo.
Para a informação dos limites das constantes das restrições, basta observar as colunas referentes às restrições.