pesquisa operacional cadeira e mesa
861 palavras
4 páginas
Programação Linear1
Programação Linear
• Muitos dos problemas algoritmicos são problemas de otimização: – encontrar o menor caminho,
– o maior fluxo
– a árvore geradora de menor custo
• Programação linear rovê um framework que permite resolver uma série de problemas de otimização em que as restrições e o critério a ser otimizado são funções lineares
L.P.
Jose Rolim
2
Programação Linear
Abordagem
– Defina as variáveis cujos valores serão determinados. – Escreva a função objetivo, uma expressão linear envolvendo as variáveis que deve ser minimizada ou maximizada
– Escreva um conjunto de restrições lineares
– Utilize um resolvedor de LP para determinar o valor das variáveis
L.P.
Jose Rolim
3
Problema com duas variáveis
• Devemos fabricar cadeiras e mesas.
– Cada cadeira necessita de 5 tábuas de madeira e cada mesa 20. Ao todo temos 400 tábuas
– Cada cadeira precisa de 10 horas de trabalho e cada mesa 15 horas. Temos 450 horas de trabalho disponíveis. • Queremos maximizar o lucro. O lucro por cadeira é 45 e por mesa é 80
L.P.
Jose Rolim
4
Problema com duas variáveis
• x1: número de cadeiras ,
• x2 : número de mesas: maximizar 45x1 + 80x2
5x1 + 20x2 ≤ 400
10x1 + 15x2 ≤ 450 x1 ≥ 0 x2 ≥ 0
L.P.
(1)
(2)
(3)
(4)
Jose Rolim
5
Problema com duas Variáveis
40
Mesas x2
30
Melhor solução: 24 cadeiras e 14 mesas
Lucro = 45×24 + 80×14 = 2200 dollars
(1) 20
(24, 14)
10
0
0
10
20
30
40
50
Cadeiras, x1
60
(2)
70
80
90
Crescente
Decrescente
L.P.
Jose Rolim
6
Modificando o lucro
• Lucro por cadeira = 64 maximizar 64x1 + 80x2
5x1 + 20x2 ≤ 400
10x1 + 15x2 ≤ 450 x1 ≥ 0 x2 ≥ 0
L.P.
(1)
(2)
(3)
(4)
Jose Rolim
7
Solution: $64 Profit/Chair
40
Mesas, x2
30
Melhor solução: 45 cadeiras, 0 mesas
Lucro = 64×45 + 80×0 = 2880 dollars
(1) 20
10
(24, 14)
0
0
10
20
30
40
50