Branch and Bound e Simplex com Octave-Matlab - Lista de Exercícios Resolvidos

Universidade Federal de Sao Carlos Departamento de Engenharia de Producao Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Objetivos desta semana Continuar o estudo do metodo branchandbound Usar o metodo simplex para resolver as relaxacoes lineares Ver como modificar a base otima quando ramificamos Fazer os calculos pelo OctaveMatlab Entender como ramificar em problemas com variaveis binarias e resolver as relaxacoes lineares por inspecao Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 2 Um alpinista deseja escolher quais objetos carregar na mochila a fim de maximizar a sua utilidade Para cada possıvel objeto o alpinista atribuiu uma utilidade quanto maior mais util mostrada na tabela abaixo juntamente com o peso de cada objeto Cada objeto e unico podendo ser levado ou nao O peso maximo que o alpinista pode carregar na mochila e 5 kg Faca um modelo de programacao inteira que auxilie o alpinista a decidir quais itens carregar Objeto Utilidade Peso g Barra de cereal 6 200 Agua 9 1000 Jaqueta 7 400 Tˆenis 3 400 Protetor solar 5 200 Garrafas de oxigˆenio 10 3000 Bussola 2 100 Maquina fotografica 6 500 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab Alguns exercícios resolvidos da Semana 9 Tópico 91 Exerc 2 Variáveis de decisão xi 1 se o objeto i for escolhido 0 caso contrário i18 Restrições Peso máximo 200x1 1000x2 400x3 400x4 200x5 3000x6 100x7 500x8 5000 Função objetivo Maximizar 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 2 max fx 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 sa 200x1 1000x2 400x3 400x4 200x5 3000x6 100x7 500x8 5000 x1 x8 0 1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 2 lp solve Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 2 lp solve Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab Alguns exercícios resolvidos da Semana 9 Tópico 91 Exerc 2 Observação Problemas como este são chamados de Problema da Mochila De forma geral são modelados como max fx i1n ui xi sa i1n pi xi b xi 0 1 i1n ui utilidade do item i para i1n pi peso do item i para i1n Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 3 Uma fabrica de alimentos possui 3 areas disponıveis para a instalacao de cen tros de distribuicao para atender clientes da regiao metropolitana de 3 cidades Devido aos tamanhos das areas os potenciais centros de distribuicao tˆem capaci dades maximas de armazenamento conforme mostra a tabela abaixo juntamente com os custos unitarios de transporte de cada centro ate as cidades e as deman das de cada cidade Os custos de instalacao de centros de distribuicao nas areas 1 2 e 3 sao R 12 mil R 15 mil e R 11 mil respectivamente Elabore um mo delo de programacao inteira que determine quais areas utilizar para a instalacao dos centros e quais cidades cada centro deve atender de modo a minimizar os custo totais Custo de transporte R Area 1 Area 2 Area 3 Demanda Ribeirao Preto 10 15 12 800 Sao Paulo 17 14 20 1400 S J Rio Preto 15 10 11 600 Capacidade 1200 1700 1600 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab Alguns exercícios resolvidos da Semana 9 Tópico 91 Exerc 3 Variáveis de decisão yi 1 se um centro é instalado na área i 0 caso contrário i123 xij qtd a ser transportada do centro i à cidade j ij123 Restrições Demanda 1 x11 x21 x31 800 Demanda 2 x12 x22 x32 1400 Demanda 3 x13 x23 x33 600 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 3 Restricoes Capacidade area 1 x11 x12 x13 1200y1 Capacidade area 2 x21 x22 x23 1700y2 Capacidade area 3 x31 x32 x33 1600y3 Naonegatividade xij 0 i j 1 2 3 Decisao simnao yi 0 1 i 1 2 3 Funcao objetivo Minimizar 10x11 17x12 15x13 15x21 14x22 10x23 12x31 20x32 11x33 12000y1 15000y2 11000y3 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 3 min fx y 10x11 17x12 15x13 15x21 14x22 10x23 12x31 20x32 11x33 12000y1 15000y2 11000y3 sujeito a x11 x21 x31 800 x12 x22 x32 1400 x13 x23 x33 600 x11 x12 x13 1200y1 x21 x22 x23 1700y2 x31 x32 x33 1600y3 xij 0 i j 1 2 3 yi 0 1 i 1 2 3 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 3 lp solve Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 91 Exerc 3 lp solve Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 Determine uma solucao otima e o valor otimo do modelo a seguir e tambem de sua relaxacao linear usando metodo grafico Quais seriam as solucoes inteiras obtidas usandose arredondamento max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 x2 15 x1 x2 Z Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x 3 2 fx 8 xRL 31 26 fxRL 88 xa P I 3 3 fxa P I 9 xb P I 3 2 fxb P I 8 x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x 3 2 fx 8 xRL 31 26 fxRL 88 xa P I 3 3 fxa P I 9 xb P I 3 2 fxb P I 8 x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x 3 2 fx 8 xRL 31 26 fxRL 88 xa P I 3 3 fxa P I 9 xb P I 3 2 fxb P I 8 x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Alguns exercıcios resolvidos da Semana 9 Topico 92 Exerc 1 max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z x 3 2 fx 8 xRL 31 26 fxRL 88 xa P I 3 3 fxa P I 9 xb P I 3 2 fxb P I 8 x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Objetivos desta semana Continuar o estudo do metodo branchandbound Usar o metodo simplex para resolver as relaxacoes lineares Ver como modificar a base otima quando ramificamos Fazer os calculos pelo OctaveMatlab Entender como ramificar em problemas com variaveis binarias e resolver as relaxacoes lineares por inspecao Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Resolucao da relaxacao linear pelo metodo simplex Ate o momento para simplificar a resolucao aplicamos o metodo branchandbound resolvendo as relaxacoes lineares de cada no pelo metodo grafico Na pratica temos problemas de porte maior e portanto precisamos de outra forma de resolver os problemas em cada no Podemos usar por exemplo o metodo simplex dado que em cada no temos um problema de programacao linear Para fazer isso de forma mais eficiente podemos reutilizar a base otima de cada no para inicializar o metodo simplex em um no filho Vamos ver como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Resolucao da relaxacao linear pelo metodo simplex Ate o momento para simplificar a resolucao aplicamos o metodo branchandbound resolvendo as relaxacoes lineares de cada no pelo metodo grafico Na pratica temos problemas de porte maior e portanto precisamos de outra forma de resolver os problemas em cada no Podemos usar por exemplo o metodo simplex dado que em cada no temos um problema de programacao linear Para fazer isso de forma mais eficiente podemos reutilizar a base otima de cada no para inicializar o metodo simplex em um no filho Vamos ver como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Resolucao da relaxacao linear pelo metodo simplex Ate o momento para simplificar a resolucao aplicamos o metodo branchandbound resolvendo as relaxacoes lineares de cada no pelo metodo grafico Na pratica temos problemas de porte maior e portanto precisamos de outra forma de resolver os problemas em cada no Podemos usar por exemplo o metodo simplex dado que em cada no temos um problema de programacao linear Para fazer isso de forma mais eficiente podemos reutilizar a base otima de cada no para inicializar o metodo simplex em um no filho Vamos ver como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Resolucao da relaxacao linear pelo metodo simplex Ate o momento para simplificar a resolucao aplicamos o metodo branchandbound resolvendo as relaxacoes lineares de cada no pelo metodo grafico Na pratica temos problemas de porte maior e portanto precisamos de outra forma de resolver os problemas em cada no Podemos usar por exemplo o metodo simplex dado que em cada no temos um problema de programacao linear Para fazer isso de forma mais eficiente podemos reutilizar a base otima de cada no para inicializar o metodo simplex em um no filho Vamos ver como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Resolucao da relaxacao linear pelo metodo simplex Ate o momento para simplificar a resolucao aplicamos o metodo branchandbound resolvendo as relaxacoes lineares de cada no pelo metodo grafico Na pratica temos problemas de porte maior e portanto precisamos de outra forma de resolver os problemas em cada no Podemos usar por exemplo o metodo simplex dado que em cada no temos um problema de programacao linear Para fazer isso de forma mais eficiente podemos reutilizar a base otima de cada no para inicializar o metodo simplex em um no filho Vamos ver como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Resolucao da relaxacao linear pelo metodo simplex Ate o momento para simplificar a resolucao aplicamos o metodo branchandbound resolvendo as relaxacoes lineares de cada no pelo metodo grafico Na pratica temos problemas de porte maior e portanto precisamos de outra forma de resolver os problemas em cada no Podemos usar por exemplo o metodo simplex dado que em cada no temos um problema de programacao linear Para fazer isso de forma mais eficiente podemos reutilizar a base otima de cada no para inicializar o metodo simplex em um no filho Vamos ver como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo Determine uma solucao otima e o valor otimo do modelo abaixo usando o metodo branchandbound com busca em largura e ramificacao na variavel mais fracionaria Use o metodo simplex para resolver as relaxacoes lineares em cada no com auxılio do OctaveMatlab max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 Z Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab No 0 raiz x0 RL 31 26 LS 88 No 1 x1 RL 325 2 LS 85 No 3 x3 RL 3 2 LS 8 x1 3 No 4 Eliminado por limitante x1 4 x2 2 No 2 x2 RL 25 3 LS 8 No 5 Eliminado por limitante x1 2 No 6 Eliminado por limitante x1 3 x2 3 x LI Nos 0 Método branchandbound Exemplo Nó 0 S⁰ max 2x₁ 1x₂ sa 2x₁ 3x₂ 14 4x₁ 1x₂ 15 x₁ x₂ 0 Método branchandbound Exemplo Nó 0 S⁰ min 2x₁ 1x₂ sa 2x₁ 3x₂ 1x₃ 0x₄ 14 4x₁ 1x₂ 0x₃ 1x₄ 15 x₁ x₂ x₃ x₄ 0 Método branchandbound Exemplo Nó 0 S⁰ min 2x₁ 1x₂ sa 2x₁ 3x₂ 1x₃ 0x₄ 14 4x₁ 1x₂ 0x₃ 1x₄ 15 x₁ x₂ x₃ x₄ 0 3a iteração do método simplex ℬ 21 B¹ 04 02 01 03 xB 26 31 λᵀ 02 04 ĉ₃ 02 ĉ₅ 04 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 0 xRL 31 26 fxRL 88 x2 x1 x LI Nós Nó 0 raiz x₁₀ᴿᴸ 31 26 L S 88 x LI Nós 1 2 Nó 0 raiz x₁₀ᴿᴸ 31 26 L S 88 x₂ 2 x₂ 3 Nó 1 Nó 2 Método branchandbound Exemplo Nó 1 S¹ S⁰ x₂ 2 max 2x₁ 1x₂ sa 2x₁ 3x₂ 14 4x₁ 1x₂ 15 0x₁ 1x₂ 2 x₁ x₂ 0 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Poderıamos resolver este problema iniciando com a base trivial B 3 4 5 Entretanto assim estarıamos jogando fora uma informacao muito importante a base otima do no pai O ideal e reaproveitarmos a base B 2 1 e reotimizarmos o problema Como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Poderıamos resolver este problema iniciando com a base trivial B 3 4 5 Entretanto assim estarıamos jogando fora uma informacao muito importante a base otima do no pai O ideal e reaproveitarmos a base B 2 1 e reotimizarmos o problema Como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Poderıamos resolver este problema iniciando com a base trivial B 3 4 5 Entretanto assim estarıamos jogando fora uma informacao muito importante a base otima do no pai O ideal e reaproveitarmos a base B 2 1 e reotimizarmos o problema Como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Poderıamos resolver este problema iniciando com a base trivial B 3 4 5 Entretanto assim estarıamos jogando fora uma informacao muito importante a base otima do no pai O ideal e reaproveitarmos a base B 2 1 e reotimizarmos o problema Como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Poderıamos resolver este problema iniciando com a base trivial B 3 4 5 Entretanto assim estarıamos jogando fora uma informacao muito importante a base otima do no pai O ideal e reaproveitarmos a base B 2 1 e reotimizarmos o problema Como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Poderıamos resolver este problema iniciando com a base trivial B 3 4 5 Entretanto assim estarıamos jogando fora uma informacao muito importante a base otima do no pai O ideal e reaproveitarmos a base B 2 1 e reotimizarmos o problema Como Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Dado que o problema agora tem 3 restricoes precisamos de 3 ındices na base Podemos incluir a variavel de folga da nova restricao B 2 1 5 Ate podemos mas com essa base xB 26 31 06 Infactıvel Vamos entao recorrer ao Mgrande Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Dado que o problema agora tem 3 restricoes precisamos de 3 ındices na base Podemos incluir a variavel de folga da nova restricao B 2 1 5 Ate podemos mas com essa base xB 26 31 06 Infactıvel Vamos entao recorrer ao Mgrande Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Dado que o problema agora tem 3 restricoes precisamos de 3 ındices na base Podemos incluir a variavel de folga da nova restricao B 2 1 5 Ate podemos mas com essa base xB 26 31 06 Infactıvel Vamos entao recorrer ao Mgrande Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Dado que o problema agora tem 3 restricoes precisamos de 3 ındices na base Podemos incluir a variavel de folga da nova restricao B 2 1 5 Ate podemos mas com essa base xB 26 31 06 Infactıvel Vamos entao recorrer ao Mgrande Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 x1 x2 0 xRL 31 26 fxRL 88 x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo max fx1 x2 2x1 1x2 sa 2x1 3x2 14 4x1 1x2 15 0x1 1x2 2 x1 x2 0 Solucao otima do problema anterior se torna infactıvel apos inserirmos x2 2 Violacao de 06 dado que x2 era 26 Assim 1x2 1x5 2 se e somente se x5 06 x2 x1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 2 x1 x2 x3 x4 x5 0 Dado que o problema agora tem 3 restricoes precisamos de 3 ındices na base Podemos incluir a variavel de folga da nova restricao B 2 1 5 Ate podemos mas com essa base xB 26 31 06 Infactıvel Vamos entao recorrer ao Mgrande Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 2 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 06 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 2 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 06 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 2 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 06 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 1 S1 S0 x2 2 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 2 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 06 Método branchandbound Exemplo Nó 1 S1 S0 x2 2 min 2x1 1x2 100x6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 2 x1 x2 x3 x4 x5 x6 0 Método branchandbound Exemplo Nó 1 S1 S0 x2 2 min 2x1 1x2 100x6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 2 x1 x2 x3 x4 x5 x6 0 2a iteração do método simplex iniciando com B 2 1 6 B 2 1 3 B1 0 0 1 0 025 025 1 05 25 xB 2 325 15 λT 1 2 0 c4 05 c5 05 c5 995 x LI Nós 1 2 Nó 0 raiz xR0L 31 26 LS 88 x2 2 x2 3 Nó 1 xR1L 325 2 LS 85 Nó 2 x LI Nós 1 2 3 4 Nó 0 raiz xRL⁰ 3 1 2 6 LS 8 8 x₂ 2 x₂ 3 Nó 1 xRL¹ 3 25 2 LS 8 5 x₁ 3 x₁ 4 Nó 2 Nó 3 Nó 4 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 2 S2 S0 x2 3 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 14 4x1 1x2 0x3 1x4 0x5 15 0x1 1x2 0x3 0x4 1x5 3 x1 x2 x3 x4 x5 0 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 2 S2 S0 x2 3 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 3 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 04 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 2 S2 S0 x2 3 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 3 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 04 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 2 S2 S0 x2 3 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 3 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 04 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 2 S2 S0 x2 3 min 2x1 1x2 Mx6 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 1x6 3 x1 x2 x3 x4 x5 x6 0 Inserimos uma coluna igual a da ultima variavel de folga mas com sinal trocado Iniciamos o metodo simplex com a base B 2 1 6 Assim xB 26 31 04 Método branchandbound Exemplo Nó 2 S² S⁰ x₂ 3 min 2x₁ 1x₂ 100x₆ sa 2x₁ 3x₂ 1x₃ 0x₄ 0x₅ 0x₆ 14 4x₁ 1x₂ 0x₃ 1x₄ 0x₅ 0x₆ 15 0x₁ 1x₂ 0x₃ 0x₄ 1x₅ 1x₆ 3 x₁ x₂ x₃ x₄ x₅ x₆ 0 Método branchandbound Exemplo Nó 2 S² S⁰ x₂ 3 min 2x₁ 1x₂ 100x₆ sa 2x₁ 3x₂ 1x₃ 0x₄ 0x₅ 0x₆ 14 4x₁ 1x₂ 0x₃ 1x₄ 0x₅ 0x₆ 15 0x₁ 1x₂ 0x₃ 0x₄ 1x₅ 1x₆ 3 x₁ x₂ x₃ x₄ x₅ x₆ 0 2a iteração do método simplex iniciando com 𝓑 2 1 6 𝓑 2 1 4 B¹ 0 0 1 05 0 15 2 1 5 x𝓑 3 25 2 λᵀ 1 0 2 ĉ₃ 1 ĉ₅ 2 ĉ₆ 98 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x LI Nós φ 1 2 3 4 Nó 0 raiz x0RL 31 26 LS 88 x2 2 x2 3 Nó 1 x1RL 325 2 LS 85 Nó 2 x2RL 25 3 LS 8 x1 3 x1 4 Nó 3 Nó 4 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x LI Nós φ 1 2 3 4 5 6 Nó 0 raiz x0RL 31 26 LS 88 x2 2 x2 3 Nó 1 x1RL 325 2 LS 85 Nó 2 x2RL 25 3 LS 8 x1 3 x1 4 x1 2 x1 3 Nó 3 Nó 4 Nó 5 Nó 6 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 3 S3 S1 x1 3 min 2x1 1x2 sa 2x1 3x2 1x3 0x4 0x5 0x6 14 4x1 1x2 0x3 1x4 0x5 0x6 15 0x1 1x2 0x3 0x4 1x5 0x6 2 1x1 0x2 0x3 0x4 0x5 1x6 3 x1 x2 x3 x4 x5 x6 0 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Exemplo No 3 S3 S1 x1 3 min 2x1 1x2 Mx7 sa 2x1 3x2 1x3 0x4 0x5 0x6 0x7 14 4x1 1x2 0x3 1x4 0x5 0x6 0x7 15 0x1 1x2 0x3 0x4 1x5 0x6 0x7 2 1x1 0x2 0x3 0x4 0x5 1x6 1x7 3 x1 x2 x3 x4 x5 x6 x7 0 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab Método branchandbound Exemplo Nó 3 S3 S1 x1 3 min 2x1 1x2 100x7 sa 2x1 3x2 1x3 0x4 0x5 0x6 0x7 14 4x1 1x2 0x3 1x4 0x5 0x6 0x7 15 0x1 1x2 0x3 0x4 1x5 0x6 0x7 2 1x1 0x2 0x3 0x4 0x5 1x6 1x7 3 x1 x2 x3 x4 x5 x6 x7 0 2a iteração do método simplex iniciando com B 2137 B 2134 B1 0 0 1 0 0 0 0 1 1 0 3 2 0 1 1 4 xB 2 3 2 1 λT 0 0 1 2 c5 1 c6 2 c7 98 x LI Nós 1 2 3 4 5 6 Nó 0 raiz x0RL 31 26 LS 88 Nó 1 x1RL 325 2 LS 85 Nó 2 x2RL 25 3 LS 8 Nó 3 x3RL 3 2 LS 8 Nó 4 Nó 5 Nó 6 x2 2 x2 3 x1 3 x1 4 x1 2 x1 3 x 3 2 LI 8 Nós 1 2 3 4 5 6 Nó 0 raiz x0RL 31 26 LS 88 Nó 1 x1RL 325 2 LS 85 Nó 2 x2RL 25 3 LS 8 Nó 3 x3RL 3 2 LS 8 Nó 4 Nó 5 Nó 6 x2 2 x2 3 x1 3 x1 4 x1 2 x1 3 x 3 2 LI 8 Nós 1 2 3 4 5 6 Nó 0 raiz x0RL 31 26 LS 88 Nó 1 x1RL 325 2 LS 85 Nó 2 x2RL 25 3 LS 8 Nó 3 x3RL 3 2 LS 8 Nó 4 Eliminado por limitante Nó 5 Nó 6 x2 2 x2 3 x1 3 x1 4 x1 2 x1 3 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 3 2 LI 8 Nós 0 1 2 3 4 5 6 Nó 0 raiz x0RL 31 26 LS 88 x2 2 x2 3 Nó 1 x1RL 325 2 LS 85 x1 3 x1 4 Nó 2 x2RL 25 3 LS 8 x1 2 x1 3 Nó 3 x3RL 3 2 LS 8 Nó 4 Eliminado por limitante Nó 5 Eliminado por limitante Nó 6 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 3 2 LI 8 Nós 0 1 2 3 4 5 6 FIM Nó 0 raiz x0RL 31 26 LS 88 x2 2 x2 3 Nó 1 x1RL 325 2 LS 85 x1 3 x1 4 Nó 2 x2RL 25 3 LS 8 x1 2 x1 3 Nó 3 x3RL 3 2 LS 8 Nó 4 Eliminado por limitante Nó 5 Eliminado por limitante Nó 6 Eliminado por limitante Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 1 A ramificacao em variaveis binarias e feita impondose a fixacao de variaveis No 0 raiz x0 RL 06 033 LS 127 No 1 x1 RL 0 075 LS 121 x1 0 No 2 x2 RL 1 067 LS 108 x1 1 Ao resolver a relaxacao do no filho podemos fixar a variavel no valor imposto pela ramificacao Podemos tambem simplesmente remover a variavel tomando o cuidado de no caso da fixacao em 1 descontar o valor dos coeficientes da coluna correspondente no vetor independente lado direito das restricoes e tambem no valor da funcao objetivo Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 1 A ramificacao em variaveis binarias e feita impondose a fixacao de variaveis No 0 raiz x0 RL 06 033 LS 127 No 1 x1 RL 0 075 LS 121 x1 0 No 2 x2 RL 1 067 LS 108 x1 1 Ao resolver a relaxacao do no filho podemos fixar a variavel no valor imposto pela ramificacao Podemos tambem simplesmente remover a variavel tomando o cuidado de no caso da fixacao em 1 descontar o valor dos coeficientes da coluna correspondente no vetor independente lado direito das restricoes e tambem no valor da funcao objetivo Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 1 A ramificacao em variaveis binarias e feita impondose a fixacao de variaveis No 0 raiz x0 RL 06 033 LS 127 No 1 x1 RL 0 075 LS 121 x1 0 No 2 x2 RL 1 067 LS 108 x1 1 Ao resolver a relaxacao do no filho podemos fixar a variavel no valor imposto pela ramificacao Podemos tambem simplesmente remover a variavel tomando o cuidado de no caso da fixacao em 1 descontar o valor dos coeficientes da coluna correspondente no vetor independente lado direito das restricoes e tambem no valor da funcao objetivo Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 1 A ramificacao em variaveis binarias e feita impondose a fixacao de variaveis No 0 raiz x0 RL 06 033 LS 127 No 1 x1 RL 0 075 LS 121 x1 0 No 2 x2 RL 1 067 LS 108 x1 1 Ao resolver a relaxacao do no filho podemos fixar a variavel no valor imposto pela ramificacao Podemos tambem simplesmente remover a variavel tomando o cuidado de no caso da fixacao em 1 descontar o valor dos coeficientes da coluna correspondente no vetor independente lado direito das restricoes e tambem no valor da funcao objetivo Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 1 A ramificacao em variaveis binarias e feita impondose a fixacao de variaveis No 0 raiz x0 RL 06 033 LS 127 No 1 x1 RL 0 075 LS 121 x1 0 No 2 x2 RL 1 067 LS 108 x1 1 Ao resolver a relaxacao do no filho podemos fixar a variavel no valor imposto pela ramificacao Podemos tambem simplesmente remover a variavel tomando o cuidado de no caso da fixacao em 1 descontar o valor dos coeficientes da coluna correspondente no vetor independente lado direito das restricoes e tambem no valor da funcao objetivo Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 2 A relaxacao linear pode ser resolvida de outras formas para alguns problemas especıficos Por exemplo para o problema da mochila podemos resolver o problema de cada no por inspecao isto e usando algum algoritmo especıfico para o problema que seja mais facil que o metodo simplex mas que ainda assim garanta a solucao otima da relaxacao linear no no O exercıcio resolvido a seguir explica essa ideia Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 2 A relaxacao linear pode ser resolvida de outras formas para alguns problemas especıficos Por exemplo para o problema da mochila podemos resolver o problema de cada no por inspecao isto e usando algum algoritmo especıfico para o problema que seja mais facil que o metodo simplex mas que ainda assim garanta a solucao otima da relaxacao linear no no O exercıcio resolvido a seguir explica essa ideia Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Metodo branchandbound Observacao 2 A relaxacao linear pode ser resolvida de outras formas para alguns problemas especıficos Por exemplo para o problema da mochila podemos resolver o problema de cada no por inspecao isto e usando algum algoritmo especıfico para o problema que seja mais facil que o metodo simplex mas que ainda assim garanta a solucao otima da relaxacao linear no no O exercıcio resolvido a seguir explica essa ideia Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Determine uma solucao otima e o valor otimo do problema a seguir usando o metodo branchandbound com busca em profundidade e ramificacao na variavel mais fracionaria Resolva as relaxacoes lineares por inspecao max fx 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 sa 02x1 1x2 04x3 04x4 02x5 3x6 01x7 05x8 5 x1 x8 0 1 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Ja vimos esse exercıcios antes Um alpinista deseja escolher quais objetos carregar na mochila a fim de maximizar a sua utilidade Para cada possıvel objeto o alpinista atribuiu uma utilidade quanto maior mais util mostrada na tabela abaixo juntamente com o peso de cada objeto Cada objeto e unico podendo ser levado ou nao O peso maximo que o alpinista pode carregar na mochila e 5 kg Faca um modelo de programacao inteira que auxilie o alpinista a decidir quais itens carregar Objeto Utilidade Peso g Barra de cereal 6 200 Agua 9 1000 Jaqueta 7 400 Tˆenis 3 400 Protetor solar 5 200 Garrafas de oxigˆenio 10 3000 Bussola 2 100 Maquina fotografica 6 500 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab Resolução da relaxação linear por inspeção Exercício resolvido Problemas como este são chamados de Problema da Mochila De forma geral são modelados como max fx i1n ui xi sa i1n pi xi b xi 01 i 1n ui utilidade do item i para i 1n pi peso do item i para i 1n A solução ótima da relaxação linear de um problema da mochila pode ser obtida por inspeção Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido max fx 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 sa 02x1 1x2 04x3 04x4 02x5 3x6 01x7 05x8 5 x1 x8 0 1 Calculamos a utilidade relativa uipi de cada item i i 1 2 3 4 5 6 7 8 ui 6 9 7 3 5 10 2 6 pi 02 1 04 04 02 3 01 05 ui pi 30 9 175 75 25 333 20 12 Ordenamos os itens usando a utilidade relativa u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido max fx 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 sa 02x1 1x2 04x3 04x4 02x5 3x6 01x7 05x8 5 x1 x8 0 1 Calculamos a utilidade relativa uipi de cada item i i 1 2 3 4 5 6 7 8 ui 6 9 7 3 5 10 2 6 pi 02 1 04 04 02 3 01 05 ui pi 30 9 175 75 25 333 20 12 Ordenamos os itens usando a utilidade relativa u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido max fx 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 sa 02x1 1x2 04x3 04x4 02x5 3x6 01x7 05x8 5 x1 x8 0 1 Calculamos a utilidade relativa uipi de cada item i i 1 2 3 4 5 6 7 8 ui 6 9 7 3 5 10 2 6 pi 02 1 04 04 02 3 01 05 ui pi 30 9 175 75 25 333 20 12 Ordenamos os itens usando a utilidade relativa u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido max fx 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 sa 02x1 1x2 04x3 04x4 02x5 3x6 01x7 05x8 5 x1 x8 0 1 Calculamos a utilidade relativa uipi de cada item i i 1 2 3 4 5 6 7 8 ui 6 9 7 3 5 10 2 6 pi 02 1 04 04 02 3 01 05 ui pi 30 9 175 75 25 333 20 12 Ordenamos os itens usando a utilidade relativa u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Solucao da relaxacao linear do problema da mochila por inspecao 1 Ordenar os itens em ordem decrescente da utilidade relativa uipi u1 p1 u2 p2 un pn sendo que i indica o item que esta na posicao i 2 Na ordem definida escolher os itens integralmente fazendo xi 1 ate atingir a capacidade da mochila sem violala 3 Se todos os itens foram escolhidos solucao otima inteira encontrada 4 Senao a variavel do primeiro item que nao coube integralmente na mochila deve ser igual a folga na mochila dividida pelo peso deste item Ou seja colocamos uma fracao do item de modo a completar a capacidade da mochila Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Solucao da relaxacao linear do problema da mochila por inspecao 1 Ordenar os itens em ordem decrescente da utilidade relativa uipi u1 p1 u2 p2 un pn sendo que i indica o item que esta na posicao i 2 Na ordem definida escolher os itens integralmente fazendo xi 1 ate atingir a capacidade da mochila sem violala 3 Se todos os itens foram escolhidos solucao otima inteira encontrada 4 Senao a variavel do primeiro item que nao coube integralmente na mochila deve ser igual a folga na mochila dividida pelo peso deste item Ou seja colocamos uma fracao do item de modo a completar a capacidade da mochila Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Solucao da relaxacao linear do problema da mochila por inspecao 1 Ordenar os itens em ordem decrescente da utilidade relativa uipi u1 p1 u2 p2 un pn sendo que i indica o item que esta na posicao i 2 Na ordem definida escolher os itens integralmente fazendo xi 1 ate atingir a capacidade da mochila sem violala 3 Se todos os itens foram escolhidos solucao otima inteira encontrada 4 Senao a variavel do primeiro item que nao coube integralmente na mochila deve ser igual a folga na mochila dividida pelo peso deste item Ou seja colocamos uma fracao do item de modo a completar a capacidade da mochila Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Solucao da relaxacao linear do problema da mochila por inspecao 1 Ordenar os itens em ordem decrescente da utilidade relativa uipi u1 p1 u2 p2 un pn sendo que i indica o item que esta na posicao i 2 Na ordem definida escolher os itens integralmente fazendo xi 1 ate atingir a capacidade da mochila sem violala 3 Se todos os itens foram escolhidos solucao otima inteira encontrada 4 Senao a variavel do primeiro item que nao coube integralmente na mochila deve ser igual a folga na mochila dividida pelo peso deste item Ou seja colocamos uma fracao do item de modo a completar a capacidade da mochila Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Solucao da relaxacao linear do problema da mochila por inspecao 1 Ordenar os itens em ordem decrescente da utilidade relativa uipi u1 p1 u2 p2 un pn sendo que i indica o item que esta na posicao i 2 Na ordem definida escolher os itens integralmente fazendo xi 1 ate atingir a capacidade da mochila sem violala 3 Se todos os itens foram escolhidos solucao otima inteira encontrada 4 Senao a variavel do primeiro item que nao coube integralmente na mochila deve ser igual a folga na mochila dividida pelo peso deste item Ou seja colocamos uma fracao do item de modo a completar a capacidade da mochila Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Solucao da relaxacao linear do problema da mochila por inspecao 1 Ordenar os itens em ordem decrescente da utilidade relativa uipi u1 p1 u2 p2 un pn sendo que i indica o item que esta na posicao i 2 Na ordem definida escolher os itens integralmente fazendo xi 1 ate atingir a capacidade da mochila sem violala 3 Se todos os itens foram escolhidos solucao otima inteira encontrada 4 Senao a variavel do primeiro item que nao coube integralmente na mochila deve ser igual a folga na mochila dividida pelo peso deste item Ou seja colocamos uma fracao do item de modo a completar a capacidade da mochila Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Solucao da relaxacao linear do problema da mochila por inspecao 1 Ordenar os itens em ordem decrescente da utilidade relativa uipi u1 p1 u2 p2 un pn sendo que i indica o item que esta na posicao i 2 Na ordem definida escolher os itens integralmente fazendo xi 1 ate atingir a capacidade da mochila sem violala 3 Se todos os itens foram escolhidos solucao otima inteira encontrada 4 Senao a variavel do primeiro item que nao coube integralmente na mochila deve ser igual a folga na mochila dividida pelo peso deste item Ou seja colocamos uma fracao do item de modo a completar a capacidade da mochila Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido max fx 6x1 9x2 7x3 3x4 5x5 10x6 2x7 6x8 sa 02x1 1x2 04x3 04x4 02x5 3x6 01x7 05x8 5 x1 x8 0 1 Utilidade relativa uipi de cada item i i 1 2 3 4 5 6 7 8 ui 6 9 7 3 5 10 2 6 pi 02 1 04 04 02 3 01 05 ui pi 30 9 175 75 25 333 20 12 Ordem dos itens usando a utilidade relativa u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Fazendo x1 1 x5 1 x7 1 x3 1 x8 1 x2 1 x4 1 temos um peso acumulado de 28kg folga 22kg Se colocarmos o proximo item da lista 6 o peso acumulado se tornara 58kg excedendo a capacidade da mochila 5kg Assim podemos colocar apenas uma fracao desse item para completar a capacidade da mochila x6 223 0733 numerador e a folga da mochila denominador e o peso do item Portanto a solucao otima da relaxacao linear do problema e x1 1 x2 1 x3 1 x4 1 x5 1 x6 0733 x7 1 x8 1 com fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Fazendo x1 1 x5 1 x7 1 x3 1 x8 1 x2 1 x4 1 temos um peso acumulado de 28kg folga 22kg Se colocarmos o proximo item da lista 6 o peso acumulado se tornara 58kg excedendo a capacidade da mochila 5kg Assim podemos colocar apenas uma fracao desse item para completar a capacidade da mochila x6 223 0733 numerador e a folga da mochila denominador e o peso do item Portanto a solucao otima da relaxacao linear do problema e x1 1 x2 1 x3 1 x4 1 x5 1 x6 0733 x7 1 x8 1 com fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Fazendo x1 1 x5 1 x7 1 x3 1 x8 1 x2 1 x4 1 temos um peso acumulado de 28kg folga 22kg Se colocarmos o proximo item da lista 6 o peso acumulado se tornara 58kg excedendo a capacidade da mochila 5kg Assim podemos colocar apenas uma fracao desse item para completar a capacidade da mochila x6 223 0733 numerador e a folga da mochila denominador e o peso do item Portanto a solucao otima da relaxacao linear do problema e x1 1 x2 1 x3 1 x4 1 x5 1 x6 0733 x7 1 x8 1 com fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Fazendo x1 1 x5 1 x7 1 x3 1 x8 1 x2 1 x4 1 temos um peso acumulado de 28kg folga 22kg Se colocarmos o proximo item da lista 6 o peso acumulado se tornara 58kg excedendo a capacidade da mochila 5kg Assim podemos colocar apenas uma fracao desse item para completar a capacidade da mochila x6 223 0733 numerador e a folga da mochila denominador e o peso do item Portanto a solucao otima da relaxacao linear do problema e x1 1 x2 1 x3 1 x4 1 x5 1 x6 0733 x7 1 x8 1 com fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Fazendo x1 1 x5 1 x7 1 x3 1 x8 1 x2 1 x4 1 temos um peso acumulado de 28kg folga 22kg Se colocarmos o proximo item da lista 6 o peso acumulado se tornara 58kg excedendo a capacidade da mochila 5kg Assim podemos colocar apenas uma fracao desse item para completar a capacidade da mochila x6 223 0733 numerador e a folga da mochila denominador e o peso do item Portanto a solucao otima da relaxacao linear do problema e x1 1 x2 1 x3 1 x4 1 x5 1 x6 0733 x7 1 x8 1 com fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido Fazendo x1 1 x5 1 x7 1 x3 1 x8 1 x2 1 x4 1 temos um peso acumulado de 28kg folga 22kg Se colocarmos o proximo item da lista 6 o peso acumulado se tornara 58kg excedendo a capacidade da mochila 5kg Assim podemos colocar apenas uma fracao desse item para completar a capacidade da mochila x6 223 0733 numerador e a folga da mochila denominador e o peso do item Portanto a solucao otima da relaxacao linear do problema e x1 1 x2 1 x3 1 x4 1 x5 1 x6 0733 x7 1 x8 1 com fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido O valor otimo fx 4533 e um limitante para o problema da mochila original Por corresponder a solucao otima da relaxacao linear ele e um LS Como podemos obter um LI usando a mesma ideia de solucao inspecao Aplicamos a solucao por inspecao mas sem fracionar nenhum item Seguimos os mesmos passos para escolhermos os itens integralmente na ordem definida Os que nao couberem nao sao escolhidos x1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 1 x8 1 com fx 38 LI Essa resolucao por inspecao permite resolvermos facilmente as relaxacoes lineares de cada no do metodo branchandbound Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido O valor otimo fx 4533 e um limitante para o problema da mochila original Por corresponder a solucao otima da relaxacao linear ele e um LS Como podemos obter um LI usando a mesma ideia de solucao inspecao Aplicamos a solucao por inspecao mas sem fracionar nenhum item Seguimos os mesmos passos para escolhermos os itens integralmente na ordem definida Os que nao couberem nao sao escolhidos x1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 1 x8 1 com fx 38 LI Essa resolucao por inspecao permite resolvermos facilmente as relaxacoes lineares de cada no do metodo branchandbound Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido O valor otimo fx 4533 e um limitante para o problema da mochila original Por corresponder a solucao otima da relaxacao linear ele e um LS Como podemos obter um LI usando a mesma ideia de solucao inspecao Aplicamos a solucao por inspecao mas sem fracionar nenhum item Seguimos os mesmos passos para escolhermos os itens integralmente na ordem definida Os que nao couberem nao sao escolhidos x1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 1 x8 1 com fx 38 LI Essa resolucao por inspecao permite resolvermos facilmente as relaxacoes lineares de cada no do metodo branchandbound Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido O valor otimo fx 4533 e um limitante para o problema da mochila original Por corresponder a solucao otima da relaxacao linear ele e um LS Como podemos obter um LI usando a mesma ideia de solucao inspecao Aplicamos a solucao por inspecao mas sem fracionar nenhum item Seguimos os mesmos passos para escolhermos os itens integralmente na ordem definida Os que nao couberem nao sao escolhidos x1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 1 x8 1 com fx 38 LI Essa resolucao por inspecao permite resolvermos facilmente as relaxacoes lineares de cada no do metodo branchandbound Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido O valor otimo fx 4533 e um limitante para o problema da mochila original Por corresponder a solucao otima da relaxacao linear ele e um LS Como podemos obter um LI usando a mesma ideia de solucao inspecao Aplicamos a solucao por inspecao mas sem fracionar nenhum item Seguimos os mesmos passos para escolhermos os itens integralmente na ordem definida Os que nao couberem nao sao escolhidos x1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 1 x8 1 com fx 38 LI Essa resolucao por inspecao permite resolvermos facilmente as relaxacoes lineares de cada no do metodo branchandbound Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido O valor otimo fx 4533 e um limitante para o problema da mochila original Por corresponder a solucao otima da relaxacao linear ele e um LS Como podemos obter um LI usando a mesma ideia de solucao inspecao Aplicamos a solucao por inspecao mas sem fracionar nenhum item Seguimos os mesmos passos para escolhermos os itens integralmente na ordem definida Os que nao couberem nao sao escolhidos x1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 1 x8 1 com fx 38 LI Essa resolucao por inspecao permite resolvermos facilmente as relaxacoes lineares de cada no do metodo branchandbound Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido O valor otimo fx 4533 e um limitante para o problema da mochila original Por corresponder a solucao otima da relaxacao linear ele e um LS Como podemos obter um LI usando a mesma ideia de solucao inspecao Aplicamos a solucao por inspecao mas sem fracionar nenhum item Seguimos os mesmos passos para escolhermos os itens integralmente na ordem definida Os que nao couberem nao sao escolhidos x1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 1 x8 1 com fx 38 LI Essa resolucao por inspecao permite resolvermos facilmente as relaxacoes lineares de cada no do metodo branchandbound Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 0 S0 Solucao otima da relaxacao linear x1 x5 x7 x3 x8 x2 x4 1 28 kg x6 5 283 0733 fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 0 S0 Solucao otima da relaxacao linear x1 x5 x7 x3 x8 x2 x4 1 28 kg x6 5 283 0733 fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 0 S0 Solucao otima da relaxacao linear x1 x5 x7 x3 x8 x2 x4 1 28 kg x6 5 283 0733 fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 0 S0 Solucao otima da relaxacao linear x1 x5 x7 x3 x8 x2 x4 1 28 kg x6 5 283 0733 fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 0 S0 Solucao otima da relaxacao linear x1 x5 x7 x3 x8 x2 x4 1 28 kg x6 5 283 0733 fx 4533 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab No 0 raiz x6 0733 LS 4533 No 1 x Z8 LS LI 38 Eliminado Limitante x6 0 No 2 x2 06 x4 0 LS 414 No 3 x Z8 LS LI 39 Eliminado Sol inteira x2 0 No 4 x8 02 x4 0 LS 402 No 5 x4 025 x8 0 LS 3975 No 7 x Z8 LS LI 39 Eliminado Sol inteira x4 0 No 8 x3 025 x8 0 LS 3675 Eliminado Limitante x4 1 x8 0 No 6 x Z8 LS LI 38 Eliminado Limitante x8 1 x2 1 x6 1 x 1 1 1 1 1 0 1 1 LI 38 Nos 0 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab No 0 raiz x6 0733 LS 4533 No 1 x Z8 LS LI 38 Eliminado Limitante x6 0 No 2 x2 06 x4 0 LS 414 No 3 x Z8 LS LI 39 Eliminado Sol inteira x2 0 No 4 x8 02 x4 0 LS 402 No 5 x4 025 x8 0 LS 3975 No 7 x Z8 LS LI 39 Eliminado Sol inteira x4 0 No 8 x3 025 x8 0 LS 3675 Eliminado Limitante x4 1 x8 0 No 6 x Z8 LS LI 38 Eliminado Limitante x8 1 x2 1 x6 1 x 1 1 1 1 1 0 1 1 LI 38 Nos 0 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab No 0 raiz x6 0733 LS 4533 No 1 x Z8 LS LI 38 Eliminado Limitante x6 0 No 2 x2 06 x4 0 LS 414 No 3 x Z8 LS LI 39 Eliminado Sol inteira x2 0 No 4 x8 02 x4 0 LS 402 No 5 x4 025 x8 0 LS 3975 No 7 x Z8 LS LI 39 Eliminado Sol inteira x4 0 No 8 x3 025 x8 0 LS 3675 Eliminado Limitante x4 1 x8 0 No 6 x Z8 LS LI 38 Eliminado Limitante x8 1 x2 1 x6 1 x 1 1 1 1 1 0 1 1 LI 38 Nos 0 x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 2 S2 S0 x6 1 Solucao otima da relaxacao linear iniciamos com x6 1 5 3 2kg restantes x1 x5 x7 x3 x8 1 14 kg x2 2 141 06 x4 0 fx 414 x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 3 4 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 4 S4 S2 x2 1 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 1 5 3 1 1kg restantes x1 x5 x7 x3 1 09 kg x8 1 0905 02 x4 0 fx 402 x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 3 4 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 3 4 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 11111011 LI 38 Nós 1 2 3 4 5 6 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 Nó 6 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 6 S6 S4 x8 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 1 5 3 1 05 05kg restantes x1 x5 x7 1 05kg Nenhuma folga restante x3 x4 0 Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 11111011 LI 38 Nós 1 2 3 4 5 6 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 Nó 6 x Z⁸ LS LI 38 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 11111011 LI 38 Nós 1 2 3 4 5 6 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 Nó 6 x Z⁸ LS LI 38 Eliminado Limitante Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 5 S5 S4 x8 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg x4 1 0904 025 fx 3975 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 5 S5 S4 x8 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg x4 1 0904 025 fx 3975 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 5 S5 S4 x8 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg x4 1 0904 025 fx 3975 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 5 S5 S4 x8 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg x4 1 0904 025 fx 3975 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 5 S5 S4 x8 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg x4 1 0904 025 fx 3975 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 5 S5 S4 x8 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg x4 1 0904 025 fx 3975 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 5 S5 S4 x8 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x8 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg x4 1 0904 025 fx 3975 x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 3 4 5 6 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 Nó 6 x Z8 LS LI 38 Eliminado Limitante x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 3 4 5 6 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 Nó 6 x Z8 LS LI 38 Eliminado Limitante x 1 1 1 1 1 0 1 1 LI 38 Nós 1 2 3 4 5 6 7 8 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 x4 0 x4 1 Nó 7 Nó 8 Nó 6 x Z8 LS LI 38 Eliminado Limitante Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 8 S8 S5 x4 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x4 1 5 3 1 04 06kg restantes x1 x5 x7 1 05kg x3 06 0504 025 fx 3675 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 8 S8 S5 x4 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x4 1 5 3 1 04 06kg restantes x1 x5 x7 1 05kg x3 06 0504 025 fx 3675 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 8 S8 S5 x4 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x4 1 5 3 1 04 06kg restantes x1 x5 x7 1 05kg x3 06 0504 025 fx 3675 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 8 S8 S5 x4 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x4 1 5 3 1 04 06kg restantes x1 x5 x7 1 05kg x3 06 0504 025 fx 3675 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 8 S8 S5 x4 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x4 1 5 3 1 04 06kg restantes x1 x5 x7 1 05kg x3 06 0504 025 fx 3675 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 8 S8 S5 x4 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x4 1 5 3 1 04 06kg restantes x1 x5 x7 1 05kg x3 06 0504 025 fx 3675 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 8 S8 S5 x4 1 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 e x4 1 5 3 1 04 06kg restantes x1 x5 x7 1 05kg x3 06 0504 025 fx 3675 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 11111011 LI 38 Nós 12345678 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x20 x21 Nó 3 Nó 4 x802 x40 LS402 x80 x81 Nó 5 x4025 x80 LS3975 Nó 6 xZ8 LS LI 38 Eliminado Limitante x40 x41 Nó 7 Nó 8 x3025 x80 LS3675 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 11111011 LI 38 Nós 12345678 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x20 x21 Nó 3 Nó 4 x802 x40 LS402 x80 x81 Nó 5 x4025 x80 LS3975 Nó 6 xZ8 LS LI 38 Eliminado Limitante x40 x41 Nó 7 Nó 8 x3025 x80 LS3675 Eliminado Limitante Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 7 S7 S5 x4 0 Solucao otima da relaxacao linear iniciamos com x6 1 x2 1 x8 0 e x4 0 5 3 1 1kg restantes x1 x5 x7 x3 1 09kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 11111011 LI 38 Nós 12345678 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x20 x21 Nó 3 Nó 4 x802 x40 LS402 x80 x81 Nó 5 x4025 x80 LS3975 Nó 6 xZ8 LS LI 38 Eliminado Limitante x40 x41 Nó 7 xZ8 LS LI 39 Nó 8 x3025 x80 LS3675 Eliminado Limitante Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 1 1 1 0 1 1 1 0 LI 39 Nós 1 2 3 4 5 6 7 8 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 x4 0 x4 1 Nó 7 x Z8 LS LI 39 Eliminado Sol inteira Nó 8 x3 025 x8 0 LS 3675 Eliminado Limitante Nó 6 x Z8 LS LI 38 Eliminado Limitante Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 3 S3 S2 x2 0 Solucao otima da relaxacao linear iniciamos com x6 1 e x2 0 5 3 2kg restantes x1 x5 x7 x3 x8 x4 1 18kg Todos os itens foram escolhidos Solucao inteira fx 39 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 1 1 1 0 1 1 1 0 LI 39 Nós 1 2 3 4 5 6 7 8 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 x Z8 LS LI 39 Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 x4 0 x4 1 Nó 7 x Z8 LS LI 39 Eliminado Sol inteira Nó 8 x3 025 x8 0 LS 3675 Eliminado Limitante Nó 6 x Z8 LS LI 38 Eliminado Limitante Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 1 1 1 0 1 1 1 0 LI 39 Nós 1 2 3 4 5 6 7 8 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 x Z8 LS LI 39 Eliminado Sol inteira Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 x4 0 x4 1 Nó 7 x Z8 LS LI 39 Eliminado Sol inteira Nó 8 x3 025 x8 0 LS 3675 Eliminado Limitante Nó 6 x Z8 LS LI 38 Eliminado Limitante Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Resolucao da relaxacao linear por inspecao Exercıcio resolvido u1 p1 u5 p5 u7 p7 u3 p3 u8 p8 u2 p2 u4 p4 u6 p6 No 1 S1 S0 x6 0 Solucao otima da relaxacao linear iniciamos com x6 0 5kg restantes x1 x5 x7 x3 x8 x2 x4 1 28kg Todos os itens foram escolhidos Solucao inteira fx 38 Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 1 1 1 0 1 1 1 0 LI 39 Nós 1 2 3 4 5 6 7 8 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 x Z8 LS LI 38 Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 x Z8 LS LI 39 Eliminado Sol inteira Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 Nó 6 x Z8 LS LI 38 Eliminado Limitante x4 0 x4 1 Nó 7 x Z8 LS LI 39 Eliminado Sol inteira Nó 8 x3 025 x8 0 LS 3675 Eliminado Limitante Pesquisa Operacional para a Engenharia de Produção 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Método branchandbound resolução das relaxações lineares pelo método simplex com uso do OctaveMatlab x 1 1 1 0 1 1 1 0 LI 39 Nós 1 2 3 4 5 6 7 8 Nó 0 raiz x6 0733 LS 4533 x6 0 x6 1 Nó 1 x Z8 LS LI 38 Eliminado Limitante Nó 2 x2 06 x4 0 LS 414 x2 0 x2 1 Nó 3 x Z8 LS LI 39 Eliminado Sol inteira Nó 4 x8 02 x4 0 LS 402 x8 0 x8 1 Nó 5 x4 025 x8 0 LS 3975 Nó 6 x Z8 LS LI 38 Eliminado Limitante x4 0 x4 1 Nó 7 x Z8 LS LI 39 Eliminado Sol inteira Nó 8 x3 025 x8 0 LS 3675 Eliminado Limitante Pesquisa Operacional para a Engenharia de Producao 1 Prof Dr Pedro Munari munaridepufscarbr Semana 10 Metodo branchandbound resolucao das relaxacoes lineares pelo metodo simplex com uso do OctaveMatlab Obrigado pela atencao Duvidas