Upload
lucas-paquiela-prates
View
234
Download
0
Embed Size (px)
Citation preview
Tpicos em Otimizao
Otimizao Linear Definies e Soluo Grfica
PPL: Hipteses Aditividade: se em 1kg do produto i houver 200g do componete k e em 2kg do produto j houver 100g do componente k, ento, 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 ento aijxj ser a quantidade em xj unidades da mistura Fracionamento: valores fracionrios so aceitveis
2
Definies- Foma Padro de um PPL:Min f ( x1 , x2 ,..., xn ) ! c1 x1 c2 x 2 ... c n xn a11 x1 a12 x2 ... a1n xn ! b1 a 21 x1 a 22 x 2 ... a 2 n x n ! b2 ..... a m1 x1 a m 2 x 2 ... a mn x n ! bm x j u 0, j ! 1,2,..., n
- Em notao matricial: Min f(x)=cTx Ax=b x0CT, x, b: vetores de dimenso n; A: matriz com m linhas e n colunas; 0: vetor nulo 3
Definies:- Soluo e Regio Factvel: x soluo factvel se satisfizer todas as restries e condies de no negatividade. O conjunto de todas as solues factveis chamado de regio factvel. - Soluo tima: uma soluo factvel que fornece o melhor valor para funo objetivo. Denota-se x* f(x* ) f(x), para qualquer x factvel.
4
Transformaes de problemas na forma padro Existem variveis no-positivasSeja xk e 0: Soluo: Criar varivel xk tal que xk = - xk Assim, modelo ter varivel xk u 0
5
Transformaes de problemas na forma padro Restries do tipo e
2 x1 3 x2 e 5 Restries do tipo u
2 x1 3 x2 x3 ! 5x3 u 0
x1 6 x2 u 7
x1 6 x2 x4 ! 7x4 u 0
Transformaes de problemas na forma padro Existem variveis livres, isto , variveis xk que podem assumir qualquer valor real (negativo, nulo ou positivo) Soluo: Substituir xk por xk+ xk- , com xk+ u 0 e xk- u 0
PPL de maximizao:max f(x) = min {-f(x)}
Soluo Grfica de PPLs Passos para resolver graficamente um PPL:a) Escolher uma soluo x vivel qualquer b) Traar o hiperplano definido pela funo objetivo passando pelo ponto x c) Determinar o gradiente da funo objetivo no ponto x d) Caminhar no sentido e direo do gradiente da funo objetivo at tangenciar a regio vivel (maximizao). Caminhar no sentido contrrio ao gradiente em problemas de minimizao. e) O ponto de tangncia representa a soluo tima x*
Soluo GrficaResolver o seguinte PPL:
max
x1 x1
2 x2 x2 e 2 e 2 e 3 u 0
x1 x1
,
x2 x2
Soluo Grficax2 x1 e 2
maxA = (0,0) B = (2,0) C = (2,1) D = (1,2) E = (0,2) F = (0,3) G = (2,2) H = (3,0)
x1 x1 x1 x1
2 x2 x2 ,x2 e 2
e 2 e 2 e 3 u 0
x2 x2
F x* = (1,2), z* = 5 E D G
C
A
B
H
x1
Teorema Fundamental da Programao Linear O timo de um PPL, se existir, ocorre em pelo menos um vrtice do conjunto de solues viveis. Situaes que podem ocorrer com relao ao conjunto M de solues viveis:1) M = {} Neste caso no h soluo vivel => No h soluo tima
2) M no vazioa) M limitadox*
Teorema Fundamental da Programao Linear
x*
y*
nica soluo tima, a qual vrtice
Infinidade de solues timas, sendo duas vrtices
2) M no vaziob) M ilimitadox*
Teorema Fundamental da Programao Linear
x*
nica soluo tima, a qual vrtice
Infinidade de solues timas, sendo uma vrtice
Teorema Fundamental da Programao Linear2) M no vaziob) M ilimitadox*
y*
Infinidade de solues timas, sendo duas vrtices
No h solues timas Soluo tima ilimitada
Teorema Fundamental da Programao Linear2) M no vazio
x* Dificuldades nos mtodos de soluo!!!
Vrtice obtido com interseo de retas diferentes : solues tima degenerada
O Problema do Desenhista Um desenhista faz quadros artesanais para vender numa feira que acontece todo dia, noite; Ele faz desenhos grandes e desenhos pequenos, e vende-os por R$5,00 e R$2,00, respectivamente; S possvel vender 4 desenhos grandes, e 3 desenhos pequenos por noite; O desenho grande feito em uma hora (grosseiro) e o pequeno feito em duas horas (detalhado). Alm disso, o desenhista desenha 8 horas por dia antes de ir para a feira.
A Deciso do Desenhista O que o desenhista precisa decidir? O que ele pode fazer para aumentar ou diminuir a sua receita? A deciso dele como usar as 8 horas dirias: quantos desenhos pequenos e grandes ele deve fazer! Chamemos de x1 e x2 as quantidades de desenhos grandes e pequenos que ele faz, por dia, respectivamente.
Determine o Modelo!
Resumo Para obter a soluo de forma grfica, siga os passos: Desenhe a regio vivel, que depende exclusivamente das restries; Descubra a inclinao da funo objetivo (desenhe em algum ponto interno regio vivel, aleatoriamente) Descubra para que lado a funo objetivo caminha (maximizao ou minizao); Projete a funo nesta direo; em caso de dvidas, voc sempre pode aplicar a funo objetivo em mais de um ponto, escolhendo o ponto mais adequado.