·
Engenharia de Produção ·
Pesquisa Operacional 2
· 2023/2
Send your question to AI and receive an answer instantly
Recommended for you
16
Slide - Exemplo Resolvido Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
30
Slide - Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
29
Slide - Algoritmo de Planos de Corte - 2023-2
Pesquisa Operacional 2
UFRN
13
Lista - Problema de Transporte Pim - 2023-2
Pesquisa Operacional 2
UFRN
28
Slide - Otimização Combinatória e Programação Inteira - 2023-2
Pesquisa Operacional 2
UFRN
4
Trabalho Prático - Po2 2022-1
Pesquisa Operacional 2
UFF
12
Variável Aleatória Discreta
Pesquisa Operacional 2
UFF
3
Avaliação 1 - 2023-1
Pesquisa Operacional 2
UFPR
2
Tarefa 5 - Problema de Progpagação e Sequenciamento - Pesquisa Operacional 2 - 2023-2
Pesquisa Operacional 2
USP
10
Teorema da Probabilidade Total
Pesquisa Operacional 2
UFF
Preview text
Branck-and-Bound Exercício Resolvido Werner K. S. Soares Como usar estes slides Para uma melhor compreensão dos exercícios a seguir, considere as seguintes sinalizações de cores: prossiga pare faça primeiro / fique atento faça depois possui base Exercício 1 Max z = 3x1 + 8x2 s.a. 3x1 + x2 ≤ 7 x1 + 2x2 ≤ 5 x1 ,x2 inteiros x1 ,x2 ≥ 0 z x1 x2 x3 x4 b base 1 -3 -8 0 0 0 x3 0 3 1 1 0 7 x4 0 1 2 0 1 5 z x1 x2 x3 x4 b base 1 -3 -8 0 0 0 x3 0 3 1 1 0 7 x4 0 1 2 0 1 5 z x1 x2 x3 x4 b base 1 1 0 0 4 20 x3 0 2.5 0 1 -0.5 4.5 x2 0 0.5 1 0 0.5 2.5 x1 =0 x2 =2.5 x2 não é inteiro gera x2 ≤ 2 e x2 ≥ 3 Relaxado: Max z = 3x1 + 8x2 s.a. 3x1 + x2 ≤ 7 x1 + 2x2 ≤ 5 x1 ,x2 ≥ 0 Forma Padrão: Max z - 3x1 - 8x2 - 3 - 8x2 = 0 s.a. 3x1 + x2 + x3 - 8x2 = 7 x1 + 2x2 - 3x1 + x4 = 5 7/1 5/2 z = 20 x1 = 0 x2 = 2,5 x2 ≤ 2 x2 ≥ 3 O A B ATIVO ATIVO Exercício 1 sub A (x2 ≤ 2) → x2 + x5 = 2 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 ? 0 2.5 0 1 -0.5 0 4.5 ? 0 0.5 1 0 0.5 0 2.5 ? 0 0 1 0 0 1 2 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 x3 0 2.5 0 1 -0.5 0 4.5 x2 0 0.5 1 0 0.5 0 2.5 x5 0 -0.5 0 0 -0.5 1 -0.5 z x1 x2 x3 x4 x5 b base 1 0 0 0 3 2 19 x3 0 0 0 1 -3 5 2 x2 0 0 1 0 0 1 2 x1 0 1 0 0 1 -2 1 x1 =1 x2 =2 PODA POR OTIMALIDADE z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 x3 0 2.5 0 1 -0.5 0 4.5 x2 0 0.5 1 0 0.5 0 2.5 x5 0 -0.5 0 0 -0.5 1 -0.5 1/-0,5 -2 4/-0,5 -8 z = 20 x1 = 0 x2 = 2,5 x2 ≤ 2 x2 ≥ 3 O A B ______ z = 19 OTIMAL. x1 = 1 x2 = 2 ATIVO Exercício 1 sub B (x2 ≥ 3) → x2 - x5 = 3 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 ? 0 2.5 0 1 -0.5 0 4.5 ? 0 0.5 1 0 0.5 0 2.5 ? 0 0 1 0 0 -1 3 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 ? 0 2.5 0 1 -0.5 0 4.5 ? 0 0.5 1 0 0.5 0 2.5 ? 0 -0.5 0 0 -0.5 -1 0.5 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 x3 0 2.5 0 1 -0.5 0 4.5 x2 0 0.5 1 0 0.5 0 2.5 x5 0 0.5 0 0 0.5 1 -0.5 nenhum coeficiente na linha da restrição menor que zero apesar de b<0, não se pode usar dual simplex PODA POR INFACTIBILIDADE z = 20 x1 = 0 x2 = 2,5 x2 ≤ 2 x2 ≥ 3 O A B ______ INFACT. ______ z = 19 OTIMAL. x1 = 1 x2 = 2 Resposta: x1 = 1 x2 = 2
Send your question to AI and receive an answer instantly
Recommended for you
16
Slide - Exemplo Resolvido Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
30
Slide - Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
29
Slide - Algoritmo de Planos de Corte - 2023-2
Pesquisa Operacional 2
UFRN
13
Lista - Problema de Transporte Pim - 2023-2
Pesquisa Operacional 2
UFRN
28
Slide - Otimização Combinatória e Programação Inteira - 2023-2
Pesquisa Operacional 2
UFRN
4
Trabalho Prático - Po2 2022-1
Pesquisa Operacional 2
UFF
12
Variável Aleatória Discreta
Pesquisa Operacional 2
UFF
3
Avaliação 1 - 2023-1
Pesquisa Operacional 2
UFPR
2
Tarefa 5 - Problema de Progpagação e Sequenciamento - Pesquisa Operacional 2 - 2023-2
Pesquisa Operacional 2
USP
10
Teorema da Probabilidade Total
Pesquisa Operacional 2
UFF
Preview text
Branck-and-Bound Exercício Resolvido Werner K. S. Soares Como usar estes slides Para uma melhor compreensão dos exercícios a seguir, considere as seguintes sinalizações de cores: prossiga pare faça primeiro / fique atento faça depois possui base Exercício 1 Max z = 3x1 + 8x2 s.a. 3x1 + x2 ≤ 7 x1 + 2x2 ≤ 5 x1 ,x2 inteiros x1 ,x2 ≥ 0 z x1 x2 x3 x4 b base 1 -3 -8 0 0 0 x3 0 3 1 1 0 7 x4 0 1 2 0 1 5 z x1 x2 x3 x4 b base 1 -3 -8 0 0 0 x3 0 3 1 1 0 7 x4 0 1 2 0 1 5 z x1 x2 x3 x4 b base 1 1 0 0 4 20 x3 0 2.5 0 1 -0.5 4.5 x2 0 0.5 1 0 0.5 2.5 x1 =0 x2 =2.5 x2 não é inteiro gera x2 ≤ 2 e x2 ≥ 3 Relaxado: Max z = 3x1 + 8x2 s.a. 3x1 + x2 ≤ 7 x1 + 2x2 ≤ 5 x1 ,x2 ≥ 0 Forma Padrão: Max z - 3x1 - 8x2 - 3 - 8x2 = 0 s.a. 3x1 + x2 + x3 - 8x2 = 7 x1 + 2x2 - 3x1 + x4 = 5 7/1 5/2 z = 20 x1 = 0 x2 = 2,5 x2 ≤ 2 x2 ≥ 3 O A B ATIVO ATIVO Exercício 1 sub A (x2 ≤ 2) → x2 + x5 = 2 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 ? 0 2.5 0 1 -0.5 0 4.5 ? 0 0.5 1 0 0.5 0 2.5 ? 0 0 1 0 0 1 2 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 x3 0 2.5 0 1 -0.5 0 4.5 x2 0 0.5 1 0 0.5 0 2.5 x5 0 -0.5 0 0 -0.5 1 -0.5 z x1 x2 x3 x4 x5 b base 1 0 0 0 3 2 19 x3 0 0 0 1 -3 5 2 x2 0 0 1 0 0 1 2 x1 0 1 0 0 1 -2 1 x1 =1 x2 =2 PODA POR OTIMALIDADE z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 x3 0 2.5 0 1 -0.5 0 4.5 x2 0 0.5 1 0 0.5 0 2.5 x5 0 -0.5 0 0 -0.5 1 -0.5 1/-0,5 -2 4/-0,5 -8 z = 20 x1 = 0 x2 = 2,5 x2 ≤ 2 x2 ≥ 3 O A B ______ z = 19 OTIMAL. x1 = 1 x2 = 2 ATIVO Exercício 1 sub B (x2 ≥ 3) → x2 - x5 = 3 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 ? 0 2.5 0 1 -0.5 0 4.5 ? 0 0.5 1 0 0.5 0 2.5 ? 0 0 1 0 0 -1 3 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 ? 0 2.5 0 1 -0.5 0 4.5 ? 0 0.5 1 0 0.5 0 2.5 ? 0 -0.5 0 0 -0.5 -1 0.5 z x1 x2 x3 x4 x5 b base 1 1 0 0 4 0 20 x3 0 2.5 0 1 -0.5 0 4.5 x2 0 0.5 1 0 0.5 0 2.5 x5 0 0.5 0 0 0.5 1 -0.5 nenhum coeficiente na linha da restrição menor que zero apesar de b<0, não se pode usar dual simplex PODA POR INFACTIBILIDADE z = 20 x1 = 0 x2 = 2,5 x2 ≤ 2 x2 ≥ 3 O A B ______ INFACT. ______ z = 19 OTIMAL. x1 = 1 x2 = 2 Resposta: x1 = 1 x2 = 2