Resumo PO1

Prévia do material em texto

O que compõe um problema de otimização?
· Termos técnicos:
· Função Objetivo: 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;
· Variáveis 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 (requisitos) que estão sendo completamente esgotados (atendidos em seu limiar) na solução proposta;
· Podem ser entendidas como as restrições que contêm o ponto ótimo.
Restrições inativas:
· Representam recursos (requisitos) que não estão sendo completamente esgotados (atendidos com folga) na solução proposta.
· Podem ser entendidas como as restrições que não contêm o ponto ótimo.
Problemas de otimização podem culminar em 4 diferentes estágios:
· Otimizado;
· Inviável – não existem soluções viáveis para o problema apresentado;
· Ilimitado – a função objetivo pode crescer infinitamente;
· Múltiplas soluções – o problema possui mais de uma solução ótima (no caso infinitas)
O Método Simplex
· Forma canônica: forma de se representar programas matemáticos através de equações. Para isso precisamos criar variáveis de folga.
· Forma padrão: é o formato padrão adotado para problemas de programação linear (PPLs) a serem resolvidos pelo algoritmo Simplex.
· A ideia é utilizar 0 como solução arbitrária para as 𝑛 variáveis. Estas variáveis recebem a designação de variáveis não-básicas. 
· As demais 𝑚 variáveis que serão responsáveis por dar uma solução determinada ao sistema são chamadas de variáveis básicas (VB) 
· Repare: total de VB = total de restrições (𝑚) 
· A Base do sistema é composta pelas suas variáveis básicas.
· Teste da razão: A linha que representa a VB que se tornará VNB é aquela com menor razão 𝑅𝐻𝑆/ 𝐶𝐶𝑃 ; (CCP = Coef. na Col. Pivô). Esta será a Linha Pivô; O valor dessa razão representa o valor máximo da nova VB de forma a manter a viabilidade.
· As variáveis básicas mantêm no tableau uma estrutura chamada Identidade. Para tal, realizaremos operações exclusivamente com a linha pivô
Ainda não é o ótimo. Deve-se melhorar o tableau:
Esse é o tableau ótimo já que não há nenhum coeficiente negativo na função objetiva. Com isso, Z* = 28/3, x1* = 4/3 e x2* = 4/3
· Lógica para a montar o tableau do método simplex:
Casos Especiais: 
· Minimização: Qualquer problema de minimização pode ser escrito como um problema de maximização: min𝑓(𝑥)= − max(−𝑓(𝑥)) 
· Variáveis Negativas: Determinados problemas podem requerer variáveis que assumam somente valores negativos. Como modelar: 𝑥1 ≤ 0 ⇒ considere 𝑥1 ′ = −𝑥1
· 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 (do politopo) da região viável – faceta paralela a função objetivo; Isso implica que o problema possui infinitas soluções ótimas. A existência de múltiplas soluções é evidenciada quando: “Uma variável não básica (VNB) possui coeficiente nulo no tableau ótimo”
· Problemas Inviáveis: Pode acontecer de o problema de otimização não possuir nenhuma solução viável. Tal fato ficará evidenciado se verificarmos algum RHS (número do lado direito) negativo.
· Problemas Ilimitados: Reconhecemos um problema ilimitado quando não é possível realizar o teste da razão, pois todos os coeficientes da coluna pivô possuem coeficientes menores ou iguais a zero (𝐶𝐶𝑃 ≤ 0)
Método Simplex Duas Fases:
· O método das duas fases: O método é aplicado em duas fases sucessivas:
· 1ª fase (viabilização): nesta fase resolvemos um problema de otimização em busca de uma primeira solução viável;
· 2ª fase (otimização): uma vez “dentro da região viável”, podemos buscar dentro desta o ótimo com o simplex tradicional.
Para isso, utilizaremos uma função objetivo temporária que mede o “nível de inviabilidade do problema”. Nosso objetivo será minimizá-la a zero;
· 1º passo: Por o problema na forma canônica... E inserir as variáveis artificiais. Essas variáveis representam a complementaridade para viabilizar a origem
· 2º passo: montagem do primeiro tableau (o tableau da 1ª fase). Primeiro, precisamos gerar uma FO artificial, cuja minimização será nosso primeiro objetivo. Somente prosseguiremos para a fase 2 se conseguirmos obter uma solução tal que 𝑎1 + 𝑎2 + ⋯ + 𝑎𝑁 = 0. Isso significa que existe uma região viável e que conseguimos “chegar” nela.
O sistema ainda não representa perfeitamente a origem, pois a FO não está em função unicamente das VNB. Antes de começar a resolver, temos que fazer um pivoteamento que permite ajustar a FO. “Basta multiplicar as linhas com variáveis artificiais por −1 e somá-la a linha de 𝑤.”
Chegamos ao final da 1ª fase: Não existem mais coeficientes negativos na linha da FO. Como, ao final da 1ª fase, o valor de w é zero, significa que o problema possui região viável, da qual conseguimos representar o primeiro vértice com o tableau que obtivemos.
2ª fase (otimização): Devemos agora proceder com a otimização normalmente. 
· 4º passo: restituir a FO antiga e suprimir as colunas das variáveis artificiais.
· 5º passo: prosseguir com a otimização:
Resumo do procedimento:
· 1ª Fase:
· 1º passo: escrever o problema na forma canônica, inserindo variáveis de folga, excesso e artificiais: Casos: ≤ - somente variáveis de folga; ≥ - variáveis de excesso e artificiais; = - somente variáveis artificiais; 
· 2º passo: Montar o primeiro tableau do método das duas fases. Lembrar de inserir a FO artificial e reescrevê-la em função das VNB (zerar os coef. das VB) 
· 3º passo: otimizar problema de 1ª fase
 Se ao final do 3º passo obtivermos 𝑤 = 0, então prosseguir para a 2ª fase; 
· 2ª Fase: 
· 4º passo: restituir a FO original do problema, novamente reescrevendo-a em função das VNB; 
· 5º passo: otimizar o problema tradicionalmente.
Análise de Sensibilidade:
Custo Reduzido: Representa o benefício/prejuízo marginal obtido pelo aumento em uma unidade de uma variável.
Preço-sombra: Representa o valor marginal de um recurso na base ótima
O Custo Reduzido e o Preço-Sombra são representados na linha de 𝑧 do tableau final.
O preço-sombra nos mostra o quanto estamos dispostos a pagar por uma unidade a mais do recurso. Mas, além disso precisamos ter alguma informação com relação ao intervalo de variação da quantidade de recurso.
1º passo: Alteração no tableau inicial. Inserção da coluna 𝛿1:
2º passo: proceder com a otimização, aplicando as alterações de pivoteamento também na coluna 𝛿1
3º passo: definir as condições de viabilidade considerando 𝛿1.
Variação do coeficiente de variáveis não-básicas no vértice ótimo:
· 1º passo: alteração do coeficiente no tableau inicial
· 2º passo: proceder com a otimização considerando a parte incógnita do coeficiente
· 3º passo: definir as condições de otimalidade considerando 𝛿1.
Ex: 500/7 − 𝛿1 ≥ 0 ⇒ 𝛿1 ≤ 500/7
Variação do coeficiente de variáveis básicas no vértice ótimo:
· 1º passo: alteração do coeficiente no tableau inicial
· 2º passo: proceder com a otimização considerando a parte incógnita do coeficiente
· 3º passo: Ajustar o tableau para que a FO volte a ser escrita somente em função das variáveis não básicas. Basta pegar a linha da mesma variável básica, multiplicar por 𝛿2 e adicioná-la a linha da FO