Otimização Linear Definições e Solução Gráfica - ppt carregar
Otimização Linear Definições e Solução Gráfica
Apresentação em tema: "Otimização Linear Definições e Solução Gráfica"— Transcrição da apresentação:
1 Otimização Linear Definições e Solução Gráfica
Tópicos em Otimização Otimização Linear Definições e Solução Gráfica Unicamp - Feec - Dca
2 PPL: Hipóteses Aditividade: se em 1kg do produto i houver 200g do componete k e em 2kg do produto j houver 100g do componente k, então, na mistura deverá (3kg) deverá haver 300g do componente k Linearidade: se aij for a quantidade do componente i em uma unidade da mistura j então aijxj será a quantidade em xj unidades da mistura Fracionamento: valores fracionários são aceitáveis
3 Definições - Foma Padrão de um PPL: - Em notação matricial:
Min f(x)=cTx Ax=b x≥0 CT, x, b: vetores de dimensão n; A: matriz com m linhas e n colunas; 0: vetor nulo
4 Definições: - Solução e Região Factível:
x é solução factível se satisfizer todas as restrições e condições de não negatividade. O conjunto de todas as soluções factíveis é chamado de região factível. - Solução Ótima: é uma solução factível que fornece o melhor valor para função objetivo. Denota-se x* f(x* ) ≤ f(x), para qualquer x factível.
5 Transformações de problemas na forma padrão
Existem variáveis não-positivas Seja xk  0: Solução: Criar variável xk' tal que xk' = - xk Assim, modelo terá variável xk'  0
6 Transformações de problemas na forma padrão
7 Transformações de problemas na forma padrão
Existem variáveis livres, isto é, variáveis xk que podem assumir qualquer valor real (negativo, nulo ou positivo) Solução: Substituir xk por xk+ – xk- , com xk+  0 e xk-  0 PPL é de maximização: max f(x) = min {-f(x)}
8 Solução Gráfica de PPL's
Passos para resolver graficamente um PPL: Escolher uma solução x viável qualquer Traçar o hiperplano definido pela função objetivo passando pelo ponto x Determinar o gradiente da função objetivo no ponto x Caminhar no sentido e direção do gradiente da função objetivo até tangenciar a região viável (maximização). Caminhar no sentido contrário ao gradiente em problemas de minimização. O ponto de tangência representa a solução ótima x*
9 Solução Gráfica Resolver o seguinte PPL:
10 Solução Gráfica x2 A = (0,0) B = (2,0) x1  2 C = (2,1) D = (1,2)
E = (0,2) F F = (0,3) G = (2,2) x* = (1,2), z* = 5 H = (3,0) E D G x2  2 z = 4 C x1 + x2  3 max z=x1 + 2x2 A H x1 B
11 Teorema Fundamental da Programação Linear
12 Teorema Fundamental da Programação Linear
13 Teorema Fundamental da Programação Linear
M é não vazio M é ilimitado Única solução ótima, a qual é vértice Infinidade de soluções ótimas, sendo uma vértice x*
14 Teorema Fundamental da Programação Linear
M é não vazio M é ilimitado Infinidade de soluções ótimas, sendo duas vértices Não há soluções ótimas Solução ótima ilimitada x* y*
15 Teorema Fundamental da Programação Linear
M é não vazio x* Dificuldades nos métodos de solução!!! Vértice obtido com interseção de retas diferentes : soluções ótima degenerada
Carregar ppt "Otimização Linear Definições e Solução Gráfica"
Capitulo 5: Simplex Voltando ao exemplo da confecção da D. Maria, e modificando um pouco os valores apenas para facilitar nossos cálculos e o entendimento,