Resumo P1 - PO 1 - PUC RIO

Prévia do material em texto

1) Construção do modelo matemático 
 Passo 1: Descobrir o que deve ser decidido (variáveis do problema). 
 Passo 2: Descobrir quais são as informações disponíveis (dados do problema). 
 Passo 3: Reproduzir as particularidades do problema que levam a uma solução (equações). 
Termos Técnicos 
 FUNÇÃO OBJETIVO (FO): critério de avaliação, que nos permite dizer se uma dada solução para o 
problema em questão é Melhor ou Pior que outra; 
 DIREÇÃO DE OTIMIZAÇÃO: Maximização ou minimização do critério adotado 
 VARIAVEIS DE DECISÃO: representam os elementos que podem assumir valores distintos e que, cada 
combinação destes, representa uma possível solução para o problema; 
 RESTRIÇÕES: representam a conjuntura do problema, e devem, portanto, serem respeitadas quando 
apresentada uma solução; 
 RESTRIÇÕES ATIVAS: Representam recursos que estão sendo completamente esgotados na solução 
proposta. Podem ser entendidas como as restrições que contêm o ponto ótimo. 
 RESTRIÇÕES INATIVAS: Representam recursos que não estão sendo completamente esgotados (atendidos 
com folga). Podem ser entendidas como as restrições que não contêm o ponto ótimo. 
 REGIÃO VIAVEL: Hiper espaço que contém todas as soluções viáveis para o problema 
 
2) METODO GRAFICO 
 Passo 1: Considerar o espaço matemático definido pelas equações de restrição (traçar as retas e marcar as 
regiões). 
 Passo 2: Encontrar a Direção de Otimização/Crescimento (Gradiente de Z – Será PERPENDICULAR as curvas 
de nível “retas de z”). 
Obs. 1: Os pontos que representam os vértices da região viável são os candidatos a limites de avanço da FO. 
Obs. 2: Se o problema for de Minimização, o gradiente será NEGATIVO. 
 Passo 3: Verificar os candidatos (vértices) e encontrar o vértice em que teremos o maior (ou menor caso o 
problema seja de minimização) valor para Z. 
 
 CASOS PARTICULARES 
(1) Otimizado: Problema possui uma solução viável/ótima. 
(2) Inviável: Não existem soluções viáveis para o problema 
Interseção VAZIA entre as regiões das restrições. 
(3) Ilimitado: A FO pode ser infinitamente melhorada 
Problema de maximização no qual a região viável é ilimitada 
(4) Múltiplas soluções: problema possui infinitas soluções ótimas 
A curva de nível da FO é PARALELA a uma das restrições ativas no ótimo. Dessa forma, temos um 
segmento de soluções ótimas. 
Obs. 1: Uma das restrições ser paralela a curva de nível não significa que teremos um problema com 
múltiplas soluções. A restrição deve ser ATIVA para que isso ocorra. 
Obs. 2: Retas paralelas = Coeficientes simultaneamente proporcionais 
3) Método Simplex 
Consiste de um algoritmo que permite a busca de soluções ótimas para problemas de otimização lineares 
contínuos. Baseia-se na solução sucessiva de sistemas de equações indeterminados, onde sistemas de equações 
adjacentes são avaliados de forma iterativa. 
Termos Técnicos 
 Forma Padrão: É o formato padrão adotado para problemas de programação linear a serem resolvidos 
pelo método simplex 
Direção de otimização MAX 𝒄𝑻 ∗ 𝒙 
Restrições 𝑨𝒙 ≤ 𝒃 
Variáveis positivas (𝑥 ≥ 0) 
 Forma Canônica: Formato usado para inserir o problema no Tableau 
 Variáveis de Folga (S): Variáveis arbitrarias criadas para transformar a inequação em equação 
Ao inserir as variáveis de folga, o sistema fica indeterminada... 
Sist. Indeterminado = nº de variáveis (n+m) > nº de equações (m) 
 Variáveis Não-Básicas: Variáveis que iremos utilizar o 0 como solução arbitrária 
 Variáveis Básicas (VB): Demais m variáveis que serão responsáveis por dar solução determinada ao 
sistema. Total de VB = Total de restrições (m) 
 Base: Composta pelas variáveis básicas 
 Variável Simbólica (Auxiliar): Criada arbitrariamente de modo a simplificar os cálculos. Bom uso para 
problemas com muitas variáveis. Define-se a variável simbólica de forma a “não termos que copiar” o que 
ela representa. Exemplo: 𝑀1 = 12𝑥1 + 7𝑥2 + 8𝑥3 + 10𝑥4 + ⋯ 
 
 TABLEAU 
 Passo 1: Colocar o problema na forma canônica (inserir variáveis de folga) 
 Passo 2: Reescrever z de forma que todas as variáveis fiquem do lado esquerdo. 
Obs.: Esse passo implica na inversão dos sinais dos coeficientes da FO 
 Passo 3: Montar o tableau 
 
 Passo 4: Escolher a coluna com a variável de coeficiente mais negativo (negativo de maior modulo). Esta 
será a Coluna Pivô. 
 
 Passo 5: Escolher a variável que irá sair da base. Para tal, fazer o Teste da Razão. 
A linha que representa a VB que se tornará VNB será aquela com menor valor no teste da razão. Esta será 
a Linha Pivô. 
obs.: Teste da Razão: 𝐦𝐢𝐧
𝒏>𝟎
(
𝑹𝑯𝑺
𝑪𝑪𝑷
) CCP = coef. coluna pivô, CCP > 0 (coef. negativos e nulos 
inviabilizam a participação no teste da razão) 
 
 Passo 6: Escolhido quem entra e quem sai da base, realizaremos operações 
exclusivamente com a Linha Pivô. Primeiramente faremos a transformação 
da linha do tableau 1 para a nova linha padronizada do tableau 2 
 
(1) No exemplo: 
𝑳𝒙𝟏
𝟐 = 𝑳𝒔𝟏
𝟏 ∗ (
𝟏
𝟐
) → 𝑳𝒑 
𝑳𝒛
𝟐 = 𝑳𝒛
𝟏 + 𝟒 ∗ 𝑳𝒑 
𝑳𝒔𝟐
𝟐 = 𝑳𝒔𝟏
𝟏 + (−𝟏) ∗ 𝑳𝒑 
 
 
 Passo 7: Verificar se, no novo tableau, ainda existem coeficientes 
negativos na linha de z. 
(1) Ainda existem coeficientes negativos: repetir os passos 4, 5 e 6. 
Obs.: O fato de ainda existirem coeficientes negativos implica que 
ainda não estamos no ótimo. 
 
(2) Não há coeficientes negativos: Encontramos o ótimo. 
 
Obs.: RHS das VB nunca < 0 
 
 
 Resumindo o método... 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Casos Especiais 
 Conversão para a forma padrão 
(1) Problemas de Minimização 
Qualquer problema de minimização pode ser escrito como um 
problema de maximização. Em termos de simplex, significa “não trocar o sinal 
quando inserir no tableau e, no fim de tudo, troca o sinal do valor de z” 
 
 
 
 
 
IPC: Trocar o valor de z encontrado no tableau ótimo 
 
(2) Variáveis Negativas 
“Determinados problemas podem requerer variáveis que assumam somente valores negativos” 
Modelamos tais problemas fazendo uma “alteração na variável”. Ao fazermos essa alteração, 
“simulamos” o efeito da variável negativa. 
 
 
 
 
 
 
 
IPC: Não esquecer de, ao final, responder com o valor real de 𝒙𝟏 (= −𝒙𝟏
′ ) 
 
(3) Variáveis irrestritas em sinal 
“Em determinadas situações é necessário (em termos de modelagem) a utilização de variáveis 
irrestritas em sinais. Para tal, criam-se 2 variáveis, uma representando a parte positiva e a outra, a 
negativa”. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Análise do Tableau 
(1) Problemas com múltiplas soluções 
“Alguns problemas de otimização possuem a característica de possuírem o sentido de crescimento da 
FO perpendicular a alguma faceta da região viável – faceta paralela a FO”. 
No tableau, podemos verificar essa particularidade uma vez que, no tableau ótimo, uma VNB possui 
coeficiente nulo. Isso significa que poderíamos inserir essa variável na base sem alterar o valor da 
solução. 
 
 
 
 
(2) Problema inviável 
“Eventualmente pode acontecer de o problema de otimização não possuir uma solução viável. 
Evidenciamos isso no caso de algum RHS negativo”. 
 
(3) Problema Ilimitado 
“Determinados problemas possuem sua direção de crescimento não limitada, permitindo que seja 
(teoricamente) auferido um benefício infinito”. 
No tableau, reconhecemos essa situação quando não é possível realizar o teste da razão, pois todos 
os coeficientesda coluna pivô são negativos ou iguais a zero (CCP ≤ 0). 
Não temos nenhum candidato apto. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4) Método Simplex de Duas Fases 
Usado quando temos problemas com restrições do tipo ≥ ou =; 
O ponto (0,0) não pertence a região viável do problema 
Para isso, utilizaremos uma função objetivo temporária que mede o “nível de inviabilidade do problema”. 
Nosso objetivo é minimiza-la a zero... 
 
 1ª Fase: Viabilização 
Nesta fase resolveremos um problema de otimização em busca de uma primeira solução viável. 
 Passo 1: Colocar o problema na forma canônica. 
Adicionam-se variáveis de excesso (𝑒1) para restrições de ≥ e variáveis artificiais (𝑎1), uma para cada 
restrição do tipo ≥ ou =. 
 
 
Obs.1: A variável artificial tem o papel de viabilizar o problema, acumula a inviabilidade da restrição. 
Obs.2: Devemos inserir as respectivas variáveis nos seguintes casos: 
 ≤ - somente variáveis de folga (s) 
 ≥ - variáveis de excesso (e) e artificiais (a) 
 = - somente variáveis artificiais (a) 
 
 Passo 2: Montar o 1º tableau: tableau da 1ª fase 
Primeiro devemos criar uma Função Objetivo Artificial cuja minimização será nosso primeiro objetivo. 
 Obs.1: N é o total de restrições “≥” e “=”. 
 Obs.2: A FO artificial mede o nível de inviabilidade da base atual. 
 
 
 
 
 
 
 
 
 Manipulamos o “tableau 0” de forma que a FO esteja unicamente em função das VNB (𝑎1 = 0). 
 Lembrar de inserir a FO artificial e reescreve-la em função das VNB (zerar os coef. das VB) 
 Passo 3: Resolver o Tableau até encontrar a solução ótima. 
 
 IPC: Ao encontrar o tableau ótimo, temos 2 situações: 
(1) 𝑤∗ = 0 : problema viável – Proceder para a fase 2. 
(2) 𝑤∗ > 0 : problema inviável. Na conversão de Max para Min teremos um nº < 0 no tableau. 
Fim do problema. 
 
 
 2ª Fase: Otimização 
Uma vez “dentro da região viável”, podemos buscar dentro desta, o ótimo com o simplex tradicional. 
Retomamos a FO original e otimizamos o problema normalmente. 
 
 Passo 4: Restituir a FO original e eliminar as colunas das variáveis artificiais (mantemos as variáveis de 
excesso). 
Obs.: Nessa troca, verificar se não é necessário fazer nenhuma modificação no tableau. Esse “novo” 
tableau pode vir com variáveis básicas diferentes de zero na linha de z... Devemos, portanto, fazer as 
devidas alterações antes de prosseguir com as operações no tableau. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Passo 5: Prosseguir com a otimização... 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5) Analise de Sensibilidade (pós-otimalidade) 
Analise dos impactos que variações nos parâmetros podem causar na solução ótima do problema em questão. 
 
 Conceitos 
(1) Custo Reduzido: Representa o benefício/prejuízo marginal obtido pelo aumento em uma unidade de 
uma variável. 
(2) Preço sombra: Representa o valor marginal de um recurso na base ótima. Nos mostra o quanto 
estamos dispostos a pagar por mais uma unidade a mais do recurso. Além disso, precisamos saber o 
intervalo de variação da quantidade desse recurso. 
(3) Valor Marginal: Quanto vale 1 unidade de determinado produto. 
O Custo reduzido e o preço sombra são representados na linha z do tableau final. 
 
 Variações do RHS (termo independente/disponibilidade de recursos) – reta “desloca” 
“Em quantas unidades a disponibilidade de um dado recurso pode variar, e quanto vale cada unidade 
adicional desse recurso? ”. 
Condição: manutenção da viabilidade 
 Variando a restrição ativa (madeira) 
(1) Passo 1: Alteração no tableau inicial. Inserção da coluna 𝛿1. Verifica-se que a coluna adicionada será 
idêntica a coluna de 𝑠1. Portanto, no tableau ótimo, a coluna 𝛿1será igual. 
(2) Passo 2: Proceder com a otimização, aplicando as alterações também na coluna de 𝛿1. 
(3) Passo 3: Definir as condições de viabilidade considerando 𝛿1. RHS ≥ 0 
 
 
 
 
 
 
 
 
 Variando a restrição inativa (mão de obra) 
Procedimento é o mesmo, mas note que a restrição de mão de obra está na base. Como a restrição é 
inativa, esse recurso é excedente, podemos aumentar o quanto quisermos que não fará diferença. 
Podemos diminuir o quanto estiver sobrando dessa restrição. 
 
 
 
 
 
 
 
 Variações nos coeficientes da função objetivo – reta muda o coef. angular 
“Qual é a maior variação admissível nos coeficientes para que não seja alterada a base ótima? ” 
Condição: manutenção da otimalidade (da base) 
 
 Variação do coeficiente de variáveis não básicas no vértice ótimo 
(1) Passo 1: Alteração do coeficiente no tableau inicial 
(2) Passo 2: Proceder com a otimização considerando a parte incógnita do coeficiente. 
(3) Passo 3: Definir as condições de otimalidade considerando 𝛿1. 
Obs. 1: Como são sempre realizadas adições, a incógnita termina da mesma forma que começou. 
Obs. 2: Encontrando o valor de 𝛿1 , sabemos que “o plano produtivo não se altera até que a cadeira 
valha R$500 + 𝛿1”. 
 
 
 
 
 
 
 
 
 Variação do coeficiente de variáveis básicas no vértice ótimo 
(1) Passo 1: Alteração do coeficiente no tableau inicial 
(2) Passo 2: Proceder com a otimização considerando a parte incógnita do coeficiente. 
(3) Passo 3: Ajustar o tableau para que a FO volte a ser escrita somente em função das VNB. 
Basta pegar a linha da mesma VB, multiplicar por 𝛿2 e soma-la a linha da FO. 
Obs.: Encontrando o intervalo de 𝛿2 sabemos que “o plano produtivo só se altera se o preço da mesa cair 
para $1000 - $125 = $875”. 
Obs. 2: Não é necessário achar o valor do RHS pois o mesmo não deve ser alterado.