Avaliacao AP3 Pesquisa Operacional II - Resolucao de Problemas de Programacao Inteira e Rotas

Avaliação AP3 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior Questão 1 3pts Considere o seguinte Problema de Programação Inteira max 𝑧 4𝑥1 3𝑥2 s a 4𝑥1 9𝑥2 26 8𝑥1 5𝑥2 17 𝑥1 𝑥2 ℤ Empregue o método BranchandBound baseado em Programação Linear para resolvêlo usando a estratégia de busca em profundidade e selecionando a variável mais fracionária para sofrer a operação de ramificação em cada iteração Caso não se possa provar a otimalidade após a exploração do oitavo nodo à exceção do nodo raiz pare e calcule o máximo erro que se cometeria caso a melhor solução viável encontrada não seja ótima Questão 2 3pts Uma empresa localizada em El Cajon precisa distribuir mercadorias para clientes em sete outras cidades O grafo abaixo esboça as ligações rodoviárias entre as cidades envolvidas Identifique as rotas de comprimento mínimo entre o armazém e os clientes considerando que os carregamentos são feitos em veículos com carga cheia Questão 3 4pts Uma distribuidora de combustíveis dispõe de um caminhão tanque dedicado ao atendimento da demanda de um consumidor de grande porte Este veículo possui cinco compartimentos de capacidades 2700 2800 1100 1800 e 3400 litros A companhia deve entregar três tipos de gasolina a este cliente super regular e sem chumbo As demandas as penalidades por litro não entregue e a máxima falta permita são dados na tabela abaixo Tipo de Gasolina Demanda litros Custo de falta litro Máx falta permita litros Super 2900 10 500 Regular 4000 8 500 Sem chumbo 4900 6 500 Por razões óbvias cada compartimento pode carregar somente um tipo de gasolina Formule um modelo de Programação Inteira para determinar a forma de carregar o caminhão que minimize os custos os custos de falta Resolução Questão 1 𝑓1 𝑚𝑖𝑛𝑥1 𝑥1 𝑥1 𝑥1 𝑚𝑖𝑛23 52 23 52 23 52 23 52 𝑚𝑖𝑛29 52 23 52 23 52 𝑓2 𝑚𝑖𝑛𝑥2 𝑥2 𝑥2 𝑥2 𝑚𝑖𝑛35 13 35 13 35 13 35 13 𝑚𝑖𝑛4 13 9 13 9 13 Como 𝑓1 𝑓2 ramificase 𝑥1 𝐺𝐴𝑃 𝑧0 𝑧7 𝑧7 128 13 7 7 37 91 4065 43 5 10 𝑥2 0 𝑥2 1 9 0 128 13 𝑥1 0 𝑥1 1 6 6 1 3 4 𝑥2 2 𝑥2 3 26 3 2 6 𝑥2 1 𝑥2 2 47 5 5 7 8 𝑥1 1 𝑥1 2 9 7 7 Questão 2 EC SD R PS LA M SB B 0 EC 15 SD 105 SD 115 R 180 R 130 R 180 LA 135 LA 145 M 180 SB 190 Rotas CECSD ECSD e vCECSD 15 C ECR ECSD SDR e vC ECR 105 C ECPS ECSD SDR RPS e vC ECPS 180 C ECLA ECSD SDLA e vC ECLA 115 C ECM ECSD SDLA LAM e vC ECM 135 C ECSB ECSD SDLA LASB e vC ECSB 145 C ECB ECSD SDR RB e vC ECB 180 Questão 3 Variáveis de Decisão 𝑡𝑖𝑗 1 se a gasolina 𝑖 é alocada no veículo 𝑗 𝑖 123 𝑗 12345 0 𝑐 𝑐 𝑥𝑖𝑗 quantidade transportada da gasolina 𝑖 no veículo 𝑗 𝑖 123 𝑗 12345 𝑦𝑖 quantidade faltante da gasolina tipo 𝑖 𝑖 123 Função Objetivo Minimizar os custos de falta min 𝑧 10𝑦1 8𝑦2 6𝑦3 Restrições R1 Limitação de falta 𝑦1 500 item 1 𝑦2 500 item 2 𝑦3 500 item 3 R2 Demandas Mínimas 𝑥11 𝑥12 𝑥13 𝑥14 𝑥15 𝑦1 2900 item 1 𝑥21 𝑥22 𝑥23 𝑥24 𝑥25 𝑦2 4000 item 2 𝑥31 𝑥32 𝑥33 𝑥34 𝑥35 𝑦3 4900 item 3 R3 Alocação das gasolinas aos tanques 𝑡11 𝑡21 𝑡31 1 tanque 1 𝑡12 𝑡22 𝑡32 1 tanque 2 𝑡13 𝑡23 𝑡33 1 tanque 3 𝑡14 𝑡24 𝑡34 1 tanque 4 𝑡15 𝑡25 𝑡35 1 tanque 5 R4 Ligação de Variáveis e capacidades 𝑥11 2700𝑡11 cap 1 𝑥21 2700𝑡21 𝑥31 2700𝑡31 𝑥12 2800𝑡12 cap 2 𝑥22 2800𝑡22 𝑥32 2800𝑡32 𝑥13 1100𝑡13 cap 3 𝑥23 1100𝑡23 𝑥33 1100𝑡33 𝑥24 1800𝑡24 cap 4 𝑥14 1800𝑡14 𝑥34 1800𝑡34 𝑥15 3400𝑡15 cap 5 𝑥25 3400𝑡25 𝑥35 3400𝑡35 R5 Declaração de variáveis 𝑦1 𝑦2 𝑦3 0 𝑥11 𝑥15 𝑥21 𝑥35 0 𝑡11 𝑡15 𝑡21 𝑡35 01 Avaliação APX3 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior INSTRUÇÕES GERAIS A memória de cálculo de todas as questões deve ser apresentada Questão 1 Um planejador possui 30 folhas de madeira compensada de tamanho 10 pés 10 pés Atualmente elas precisam de 20 folhas na forma de discos de diâmetro de 5 pés e 15 folhas de madeira compensada no forma de retângulos de 4 pés 6 pés Os padrões de corte considerados pelo tomador de decisão são mostrados na figura abaixo Sabese que o corte de um disco custa 200 e de um retângulo 150 Esses preços incluem todos os cortes necessários e é independente do padrão de corte da forma Como alternativa podese comprar um disco por 450 e um retângulo por US 300 a partir de um fornecedor externo Formule um programa inteiro que minimize o custo de obtenção das formas necessárias não utilize mais folhas de 10 pés x 10 pés do que o disponível produza o número necessário de discos e retângulos garanta que o corte não resulte em mais de 30 de resíduos Questão 2 Considere o seguinte PPI max z 5𝑥1 9𝑥2 s a 5𝑥1 11x2 94 10𝑥1 6𝑥2 87 𝑥1 𝑥2 0 e inteiras a Resolver o problema pelo método branchandbound baseado em Programação Linear Adote a estratégia de busca em profundidade para selecionar os nós a serem explorados em cada iteração e use a variável mais fracionária para ramificar os subproblemas b Se a busca tivesse sido interrompida na primeira solução viável qual seria o gap dual relativo Interprete este resultado c O valor da solução da relaxação de Programação Linear subestima ou superestima o valor da solução do problema inteiro Em quanto OBS Em sua memória de cálculo é necessário ilustrar a árvore de branchandbound conforme as convenções apresentadas nas notas de aula Questão 3 Uma construtora levantou dados sobre os custos de caminhões basculantes Idade anos 01 12 23 34 45 Custo de Manutenção 7000 7500 9700 7700 9000 Custo de perdas com paradas 500 800 1200 800 1000 Valor Residual 16000 6000 9000 3500 2500 OBS O 0 na primeira coluna indica o início do primeiro ano Nenhum caminhão pode ser usado por mais de 5 anos Empregue um algoritmo ótimo para determinar uma política de reposição de um caminhão para os próximos 4 anos considerando que ele possui atualmente 1 ano de uso e que um novo caminhão seja adquirido por 21000 Antes de iniciar a solução do problema esboce uma rede que represente o problema Questão 4 Empregue o método da Secção Áurea para aproximar a solução ótima do programa não linear abaixo descrito considerando um intervalo de incerteza não superior a ϵ 01 max fx 5x x2 s a 0 x 10 Avaliação AP3 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior Questão 1 3pts A empresa Investilila está considerando cinco projetos para investimento Cada projeto possui um Valor Presente Líquido VPL e requer investimentos no ano presente e nos dois anos seguintes Além disso para cada ano há um limite de investimento disponível Todos esses dados estão disponíveis na Tabela 63 A empresa quer decidir em qualis projetos investir de forma a maximizar o VPL total Modele o problema de orçamento de capital da empresa Investilila Considere que por razões administrativas não se pode escolher os projetos 1 e 5 simultaneamente Questão 2 3pts Uma pessoa pega um carro de aplicativo para ir a um show de rock mas antes de chegar ao destino final pede para que o motorista passe na casa de um amigo para lhe dar carona A rede abaixo ilustra as ligações viárias capazes de conectar a localização do cliente no vértice 1 aos endereços do show e da casa do amigo nos vértices 8 e 4 respectivamente As ligações indicam ruas ou avenidas e seus valores são os tempos médios de viagem através das mesmas Sabendose que os melhores lugares são ocupados rapidamente os passageiros desejam chegar o mais rápido o possível ao show Encontre uma rota ótima para atingir este objetivo Questão 3 4pts O Problema de Programação Inteira abaixo descrito consiste na maximização da receita com a produção dos itens 1 e 2 As variáveis de decisão representam as quantidades a produzir de cada item e seus coeficientes na fo representam as respectivas receitas unitárias de venda Os termos independentes nas restrições são as quantidades disponíveis dos três recursos usados na produção e os coeficientes nas restrições são os consumos unitários dos correspondentes recursos Empregue o método BranchandBound baseado em Programação Linear para resolver este problema usando a estratégia de busca em largura e selecionando a variável mais fracionária para sofrer a operação de ramificação quando necessário empates devem ser quebrados com a escolha da variável de menor índice Pare após encontrar ao menos duas soluções viáveis ou até atingir a otimalidade aquilo que ocorrer primeiro Caso esta solução final não seja ótima calcule o quanto melhor poderia ser uma eventual solução ótima em termos percentuais Resolução Questão 1 Variáveis de Decisão 𝑥𝑖 1 se projeto 𝑖 é selecionado 𝑖 12345 0 𝑐 𝑐 Função Objetivo Maximizar o VPL total max 𝑧 22𝑥1 17𝑥2 16𝑥3 14𝑥4 20𝑥5 Restrições R1 Capacidade de Investimento por ano 5𝑥1 4𝑥2 3𝑥3 4𝑥4 5𝑥5 12 ano 1 4𝑥1 3𝑥2 2𝑥3 𝑥4 3𝑥5 10 ano 2 6𝑥1 3𝑥2 𝑥3 2𝑥4 6𝑥5 9 ano 3 R2 Projetos excludentes 𝑥1 𝑥5 1 R3 Declaração de variáveis 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 01 Questão 2 Solução pelo método em tabelas 1 Iteração 1 Nó dj pj Status 1 0 Rotulado 2 01 1 11 Não Rotulado 3 02 1 2701 Não Rotulado Iteração 2 Nó Rótulo Status 1 0 Rotulado 2 11 Rotulado 3 21 ou 11 2 2 2 Não Rotulado 4 15 2 6 2 Não Rotulado 5 12 2 3 2 Não Rotulado Iteração 3 Nó Rótulo Status 1 0 Rotulado 2 11 Rotulado 3 22 Rotulado 4 6 2 ou 22 2 4 3 Não Rotulado 5 3 2 ou 21 3 3 3 Não Rotulado 6 24 3 6 3 Não Rotulado Iteração 4 Nó Rótulo Status 1 0 Rotulado 2 11 Rotulado 3 22 Rotulado 4 22 2 4 3 Não Rotulado 5 3 2 Rotulado 6 6 3 ou 33 5 6 5 Não Rotulado 7 37 5 10 5 Não Rotulado Iteração 5 Nó Rótulo Status 1 0 Rotulado 2 11 Rotulado 3 22 Rotulado 4 4 3 Rotulado 5 3 2 Rotulado 6 6 3 ou 46 4 10 4 Não Rotulado 7 10 5 ou 48 4 12 4 Não Rotulado Uma vez que o nó de destino 𝑠4 foi rotulado o algoritmo para retornando o caminho ótimo 13 34 de custo igual a 4 Iniciase a partir deste nodo o recálculo para determinar a menor rota entre a nova origem r4 e novo destino s8 Iteração 1 Nó dj pj Status 4 0 Rotulado 5 03 4 34 Não Rotulado 6 06 4 64 Não Rotulado 7 08 4 84 Não Rotulado Iteração 2 Nó Rótulo Status 4 0 Rotulado 5 34 Rotulado 6 64 ou 33 5 6 5 Não Rotulado 7 84 ou 37 5 10 5 Não Rotulado Iteração 3 Nó Rótulo Status 4 0 Rotulado 5 34 Rotulado 6 64 Rotulado 7 8 4 ou 65 6 11 6 Não Rotulado 8 62 6 8 6 Não Rotulado Iteração 4 Nó Rótulo Status 4 0 Rotulado 5 34 Rotulado 6 64 Rotulado 7 8 4 Rotulado 8 8 6 ou 86 7 14 7 Não Rotulado Iteração 5 Nó Rótulo Status 4 0 Rotulado 5 34 Rotulado 6 64 Rotulado 7 8 4 Rotulado 8 8 6 Rotulado Uma vez que o nó de destino 𝑠8 foi rotulado o algoritmo para retornando o caminho ótimo 46 68 de custo igual a 6 Logo a rota ótima é dada por 13 34 46 68 com custo apurado de 12 Solução pelo método em tabelas 2 Iter 1 2 3 4 5 6 7 8 k0 0 k1 1 1 2 1 k2 2 2 6 2 3 2 k3 4 3 3 3 6 3 k4 6 5 10 5 k5 10 4 12 4 Iter X X X X X X X X k0 0 3 4 k1 6 4 8 4 k2 6 5 10 5 k3 11 6 8 6 k4 14 7 k5 Rotas C1 4 13 34 e vC1 4 4 C4 8 46 68 e vC4 8 8 Questão 3 Nodo 0 Iniciase a questão pela resolução da relaxação de programação linear pelo método gráfico omitiremos as ilustrações neste gabarito O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 5𝑥1 7𝑥2 44 e 6𝑥1 3𝑥2 24 Após a resolução chegase a seguinte solução ótima do problema relaxado 𝑧𝑅𝑃𝐿 0 32 𝑥1 0 𝑥2 0 4 3 16 3 Como ambas as variáveis são fracionárias aplicase a regra da variável mais fracionária 𝑓1 𝑚𝑖𝑛𝑥1 𝑥1 𝑥1 𝑥1 𝑚𝑖𝑛43 43 43 43 𝑚𝑖𝑛23 13 13 𝑓2 𝑚𝑖𝑛𝑥2 𝑥2 𝑥2 𝑥2 𝑚𝑖𝑛163 163 163 163 𝑚𝑖𝑛23 13 13 Como 𝑓1 𝑓2 selecionase variável de menor índice 𝑥1 a se ramificar com a seguinte árvore de branchandbound Como os nodos 1 e 2 possuem mesmo limitante 𝑧0 explorase arbitrariamente o nodo 1 pela busca em largura Nodo 1 O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 5𝑥1 7𝑥2 44 e e 𝑥1 1 Após a resolução chegase a seguinte solução ótima do problema relaxado 𝑧1 223 7 𝑥1 1 𝑥2 1 1 39 7 Como a variável 𝑥2 é fracionária ramificase o nodo 1 com a seguinte árvore de branchandbound Como o nodo 2 possui melhor limitante 𝑧0 explorase este nodo pela busca em largura 0 32 𝑥1 1 𝑥1 2 1 2 Nodo 2 O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 6𝑥1 3𝑥2 24 e e 𝑥1 2 Após a resolução chegase a seguinte solução ótima do problema relaxado 𝑧2 28 𝑥1 1 𝑥2 1 24 Sendo ambas as variáveis são inteiras podase o nodo 2 por otimalidade Como os nodos 3 e 4 possuem mesmo limitante 𝑧1 explorase arbitrariamente o nodo 3 pela busca em largura 0 32 𝑥1 1 1 3 4 223 7 2 0 32 𝑥1 1 𝑥1 2 1 3 4 𝑥2 5 𝑥2 6 223 7 2 28 28 O Nodo 3 O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 𝑥1 1 e 𝑥2 5 Após a resolução chegase a seguinte solução ótima do problema relaxado 𝑧3 29 𝑥1 1 𝑥2 1 15 Sendo ambas as variáveis são inteiras podase o nodo 3 por otimalidade Como sugere o enunciado após encontrar duas soluções inteiras viáveis encerrase o processo com o seguinte valor de gap e a seguinte árvore de branchandbound 𝐺𝐴𝑃 𝑧1 𝑧3 𝑧3 223 7 29 29 20 203 985 0 32 𝑥1 1 𝑥1 2 29 29 1 3 4 𝑥2 5 𝑥2 6 223 7 2 28 28 O O Avaliação AP3 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior Questão 1 4pts Uma siderúrgica recebeu um pedido 25 toneladas de aço O carbono e o molibdênio devem corresponder a no máximo 5 e 4 do seu peso total respectivamente O aço é produzido combinandose três tipos de metais lingotes de aço aço de sucata e ligas de aço Quatro lingotes estão disponíveis para compra sendo que suas massas em toneladas custos por tonelada e porcentagens de carbono e molibdênio são mostrados na tabela 1 Por simplicidade assuma que os lingotes devem ser integralmente usados Na tabela 2 são mostrados os dados das ligas de aço que podem ser compradas em qualquer quantidade Também se pode empregar sucata a R5000tonelada com 3 de carbono e 9 de molibdênio em qualquer quantidade Tabela 1 Dados dos lingotes disponíveis para compra Lingote Massa ton Custo Rton Carbono Molibdênio 1 5 150 5 3 2 3 138 4 3 3 4 115 5 4 4 6 75 3 4 Tabela 2 Dados das ligas disponíveis para compra Liga Custo Rton Carbono Molibdênio 1 270 9 6 2 215 7 7 3 186 5 8 Formule o problema de minimizar o custo total da siderúrgica para atender este pedido OBS Assuma que toda a matériaprima seja integralmente convertida Ou seja não há perdas no processo Questão 2 3pts Considere o seguinte Problema de Programação Inteira min 𝑧 4𝑥1 3𝑥2 sa 8𝑥1 8𝑥2 44 4𝑥1 2𝑥2 27 𝑥2 2 𝑥1 𝑥2 0 inteiras Empregue o método BranchandBound baseado em PL para resolvêlo usando a estratégia de busca em largura e selecionando a variável mais fracionária para sofrer a operação de ramificação quando necessário Pare após encontrar a primeira solução viável ou após atingir a otimalidade aquilo que ocorrer primeiro Caso esta solução final não seja ótima calcule o quanto melhor poderia ser uma eventual solução ótima em termos percentuais Questão 3 3pts Uma estação de tratamento de esgoto precisa determinar sua máxima capacidade de tratamento em termos da vazão em 103 m3s A rede abaixo ilustrada apresenta as conexões existentes entre o ponto de recebimento dos efluentes vértice A os tanques de tratamento vértices D a E e o ponto de despejo da água tratada vértice F Os arcos indicam as possíveis conexões e seus valores as capacidades em 103 m3s a Determine por inspeção o corte de menor capacidade nesta rede A partir dele podese dizer qual o valor do fluxo máximo ou pelo menos estabelecer um limite superior para ele b Empregue o algoritmo de FordFulkerson para determinar os fluxos em cada arco que maximizam a quantidade de esgoto tratada Resolução Questão 1 Variáveis de Decisão 𝑥𝑖 quantidade da liga 𝑖 em toneladasusada na composição do aço 𝑖 123 𝑦𝑗 quantidade de lingotes do tipo 𝑖 usados na composição do aço em toneladas𝑖 1234 𝑤 quantidade de sucata usada na composição do aço em toneladas Função Objetivo Minimizar o custo total da siderúrgica para atender este pedido min 𝑧 270𝑥1 215𝑥2 186𝑥3 750𝑦1 414𝑦2 460𝑦3 450𝑦4 50𝑧 Restrições R1 Disponibilidade de Aço 𝑥1 𝑥2 𝑥3 5𝑦1 3𝑦2 4𝑦3 6𝑦4 𝑤 25 toneladas de aço R2 Porcentagens máximas de elementos 003𝑧 009𝑥1 007𝑥2 005𝑥3 025𝑦1 012𝑦2 02𝑦3 018𝑦4 005 𝑧 𝑥1 𝑥2 𝑥3 5𝑦1 3𝑦2 4𝑦3 6𝑦4 quantidade máxima de carbono na liga 009𝑧 006𝑥1 007𝑥2 008𝑥3 015𝑦1 009𝑦2 016𝑦3 018𝑦4 024 𝑧 𝑥1 𝑥2 𝑥3 5𝑦1 3𝑦2 4𝑦3 6𝑦4 quantidade máxima de molibdênio na liga R3 Declaração de variáveis 𝑦1 𝑦2 𝑦3 𝑦4 01 𝑥1 𝑥2 𝑥3 𝑧 0 Questão 2 Nodo 0 Iniciase a questão pela resolução da relaxação de programação linear pelo método gráfico omitiremos as ilustrações neste gabarito O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 4𝑥1 2𝑥2 27 e 8𝑥1 8𝑥2 44 Após a resolução chegase à seguinte solução ótima do problema relaxado 𝑧𝑅𝑃𝐿 0 211 6 𝑥1 0 𝑥2 0 8 3 49 6 Como ambas as variáveis não são inteiras aplicase a regra da variável mais fracionária 𝑓1 min8 3 8 3 8 3 8 3 min3 8 3 8 3 2 min1 3 2 3 2 3 𝑓2 min49 6 49 6 49 6 49 6 min9 49 6 49 6 8 min5 6 1 6 1 6 Como 𝑓1 𝑓2 selecionase variável 𝑥1 a se ramificar com a seguinte árvore de branchandbound O próximo nodo a ser explorado de acordo com a estratégia de busca em largura é o nodo 1arbitrariamente adotamos o nodo à esquerda Nodo 1 O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 8𝑥1 8𝑥2 44 e e 𝑥1 2 Após a resolução chegase a seguinte solução ótima 𝑧1 61 2 𝑥1 1 𝑥2 1 2 15 2 Selecionase variável 𝑥2 a se ramificar com a seguinte árvore de branchandbound O próximo nodo a ser explorado de acordo com a estratégia de busca em largura é o nodo 2 0 211 6 𝑥1 2 𝑥1 3 1 2 Nodo 2 O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 4𝑥1 2𝑥2 27 e e 𝑥1 3 Após a resolução chegase a seguinte solução ótima 𝑧2 69 2 𝑥1 2 𝑥2 2 3 15 2 Selecionase variável 𝑥2 a se ramificar com a seguinte árvore de branchandbound O próximo nodo a ser explorado de acordo com a estratégia de busca em largura é o nodo 5 0 211 6 𝑥1 2 𝑥1 3 2 1 61 2 𝑥2 7 𝑥2 8 3 4 0 211 6 𝑥1 2 𝑥1 3 1 61 2 𝑥2 7 𝑥2 8 3 4 2 69 2 𝑥2 7 𝑥2 8 6 5 Nodo 5 O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 4𝑥1 2𝑥2 27 e e 𝑥2 7 Após a resolução chegase a seguinte solução ótima 𝑧5 34 𝑥1 5 𝑥2 5 13 4 7 Selecionase variável 𝑥1 a se ramificar com a seguinte árvore de branchandbound O próximo nodo a ser explorado de acordo com a estratégia de busca em largura é o nodo 6 Nodo 6 O gradiente da função objetivo não fornece o valor ótimo pois não há ponto de interseção entre o espaço de solução até o nodo 2 e 𝑥2 8 Após a resolução chegase a seguinte solução 𝑧6 Podase o nodo 6 por inviabilidade com a seguinte árvore de branchandbound O próximo nodo a ser explorado de acordo com a estratégia de busca em largura é o nodo 7 0 211 6 𝑥1 2 𝑥1 3 1 61 2 𝑥2 7 𝑥2 8 3 4 2 69 2 𝑥2 7 𝑥2 8 6 5 34 𝑥1 3 𝑥1 4 7 8 Nodo 7 O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 𝑥1 3 e 𝑥2 7 Após a resolução chegase a seguinte solução ótima inteira 𝑧7 33 𝑥1 7 𝑥2 7 37 Podase o nodo 7 por otimalidade e os nodos 3 e 4 por limitante Como sugere o enunciado encerrase as iterações ao encontrar a primeira solução ótima inteira viável com a seguinte árvore de branchandbound e valor de gap 0 211 6 𝑥1 2 𝑥1 3 1 61 2 𝑥2 7 𝑥2 8 3 4 2 69 2 𝑥2 7 𝑥2 8 6 5 34 𝑥1 3 𝑥1 4 7 8 I 𝐺𝐴𝑃 𝑧 𝑧 𝑧 𝑧5 𝑧7 𝑧7 34 33 33 1 33 303 33 33 0 211 6 𝑥1 2 𝑥1 3 1 61 2 𝑥2 7 𝑥2 8 3 4 2 69 2 𝑥2 7 𝑥2 8 6 5 34 𝑥1 3 𝑥1 4 7 8 I L L O Questão 3 a Por inspeção verificase que a capacidade do corte AF mínimo é 15 sendo este corte definido pelos arcos DF e EF cujas capacidades são respectivamente 6 e 9 Portanto o fluxo máximo nesta rede vale 15 unidades b A aplicação do algoritmo de FordFulkerson produz as seguintes iterações 1ª Iteração Solução inicial 𝑥 0 com grafo auxiliar correspondente abaixo A cadeia enumerada é 𝐶 𝐴 𝐵 𝐵 𝐷 𝐷 𝐹 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min976 6 unidades Com isso 𝑓 𝑓 Δ𝑓 0 6 6 𝑥𝐴𝐵 0 6 6 𝑥𝐵𝐷 0 6 6 𝑥𝐷𝐹 0 6 6 Com as capacidades residuais 𝑣𝐴 𝐵 9 6 3 𝑣𝐴 𝐵 6 0 6 𝑣𝐵 𝐷 7 6 1 𝑣𝐵 𝐷 6 0 6 𝑣𝐷 𝐹 6 6 0 𝑣𝐷 𝐹 6 0 6 2ª Iteração A próxima cadeia enumerada é 𝐶 𝐴 𝐵 𝐵 𝐸 𝐸 𝐹 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min329 2 unidade Com isso 𝑓 𝑓 Δ𝑓 6 2 8 𝑥𝐴𝐵 6 2 8 𝑥𝐵𝐸 0 2 2 𝑥𝐸𝐹 0 2 2 Com as capacidades residuais 𝑣𝐴 𝐵 3 2 1 𝑣𝐴 𝐵 8 0 8 𝑣𝐵 𝐸 2 2 0 𝑣𝐵 𝐸 2 0 2 𝑣𝐸 𝐹 9 2 7 𝑣𝐸 𝐹 2 0 2 3ª Iteração A próxima cadeia enumerada é 𝐶 𝐴 𝐶 𝐶 𝐸 𝐸 𝐹 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min767 6 unidades Com isso 𝑓 𝑓 Δ𝑓 8 6 14 𝑥𝐴𝐶 0 6 6 𝑥𝐶𝐸 0 6 6 𝑥𝐸𝐹 2 6 8 Com as capacidades residuais 𝑣𝐴 𝐶 7 6 1 𝑣𝐴 𝐶 6 0 6 𝑣𝐶 𝐸 6 6 0 𝑣𝐶 𝐸 6 0 6 𝑣𝐸 𝐹 7 6 1 𝑣𝐸 𝐹 8 0 8 4ª Iteração A próxima cadeia enumerada é 𝐶 𝐴 𝐶 𝐶 𝐷 𝐷 𝐸 𝐸 𝐹 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min1431 1 unidades Com isso 𝑓 𝑓 Δ𝑓 14 1 15 𝑥𝐴𝐶 6 1 7 𝑥𝐶𝐷 0 1 1 𝑥𝐷𝐸 0 1 1 𝑥𝐸𝐹 8 1 9 Com as capacidades residuais 𝑣𝐴 𝐶 1 1 0 𝑣𝐴 𝐶 7 0 7 𝑣𝐶 𝐷 4 1 3 𝑣𝐶 𝐷 1 0 1 𝑣𝐷 𝐸 3 1 2 𝑣𝐷 𝐸 1 0 1 𝑣𝐸 𝐹 1 1 0 𝑣𝐸 𝐹 9 0 9 5ª Iteração Como se vê na rede abaixo não há caminhos para o aumento do fluxo entre os vértices A e F pois todas as capacidades residuais dos arcos que saem do vértice F são nulas indicando que estes arcos foram saturados O algoritmo então termina com o fluxo ótimo de 𝑓 15 unidades Observe que este valor é o mesmo obtido para o corte de capacidade mínima na letra a