Resolver os Exercícios em Anexo de Forma Detalhada

Problema de Gestão Financeira Exemplo 2 Desejase investir 14000 12000 e 15000 em cada mês do próximo trimestre Foram identificadas 4 oportunidades de investimento Investimento 1 requer 5000 8000 e 2000 no mês 1 2 e 3 respectivamente e tem um valor presente de 18000 Investimento 2 requer 7000 no mês 1 e 10000 no mês 3 tendo um valor presente de 19000 Investimento 3 requer 4000 no período 2 e 6000 no período 3 tendo um valor presente de 12000 Investimento 4 requer 3000 4000 e 5000 tendo valor presente de 15000 Como realizar o investimento 1114 A diretoria da General Wheels Co está considerando sete grandes investimentos de capital Cada investimento pode ser feito somente uma vez Esses investimentos diferem no lucro estimado a longo prazo valor presente líquido que eles vão gerar bem como no volume de capital necessário conforme ilustrado na seguinte tabela em unidades de milhões de dólares Oportunidade de Investimento 1 2 3 4 5 6 7 Lucro estimado 17 10 15 19 7 13 9 Capital necessário 43 28 34 48 17 32 23 O volume de capital disponível para esses investimentos é de US 100 milhões As oportunidades de investimentos 1 e 2 são mutuamente exclusivas e da mesma forma as oportunidades 3 e 4 Além disso nem a oportunidade 3 nem a 4 podem ser empreendidas a menos que uma das duas primeiras oportunidades seja realizada Não há tais restrições sobre as oportunidades de investimento 5 6 e 7 O objetivo é selecionar a combinação de investimentos de capital que vai maximizar o lucro total estimado a longo prazo valor presente líquido a Formule um modelo de PIB para esse problema b Use o computador para solucionar esse modelo Exercício 1114 a Considere as seguintes variáveis xi foi realizado o investimento na oportunidade i17 Temos então o seguinte modelo max 17 x110x215 x319 x47 x513 x69 x7 Lucro total sa 43 x128 x234 x348 x417 x532 x623 x7100 Valor total investido x1 x21 Não podemos investir em 1 e 2 ao mesmo tempo x3x4x1x2 Não podemos investir em 3 e 4 ao mesmo tempo e sem ter investido em 1 ou 2 xi01 i17 b Vamos relaxar a restrição de integralidade e formular o problema P1 como problema inicial do Branch and Bound Abaixo é apresentado a árvore do Branch and Bound e a descrição de cada um dos problemas da árvore e sua respectiva solução P1 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 0 xi1 i17 Solução x11 x20 x31 x40 x51 x601875 e x70 Valor da função objetivo 414375 P2 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 0 xi1 i17 Solução x11 x20 x31 x40 x51 x60 e x70260869565 Valor da função objetivo 4134782609 P3 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 0 xi1 i17 Solução x11 x20x3057142857 x4042857142857 x51 x60 e x70 Valor da função objetivo 40714285 P4 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x30 0 xi1 i17 Solução x109120879 x20 x30 x409120879 x51 x60 e x70260869565 Valor da função objetivo 398351648 P5 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x30 x10 0 xi1 i17 Solução x10 x21 x30 x41 x51 x60 e x70 Valor da função objetivo 398351648 P6 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x30 x11 0 xi1 i17 Solução x11 x20 x30 x40833333333 x51 x60 e x70 Valor da função objetivo 398333333333 P7 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x30 x11 x40 0 xi1 i17 Solução x11 x20 x30 x40 x51 x60 e x70 Valor da função objetivo 24 P8 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x30 x11 x41 0 xi1 i17 Solução x11 x20 x30 x41 x5052941176 x60 e x70 Valor da função objetivo 3970588235 P9 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x30 x11 x41 x50 0 xi1 i17 Solução x11 x20 x30 x41 x50 x60 e x70 Valor da função objetivo 36 P10 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x30 x11 x41 x51 0 xi1 i17 Solução Inviável P11 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x70 x31 0 xi1 i17 Solução x11 x20x31 x40 x51 x60 e x70 Valor da função objetivo 39 P12 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x60 x71 0 xi1 i17 Solução x11 x20x31 x40 x50 x60 e x71 Valor da função objetivo 41 P13 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x61 0 xi1 i17 Solução x10883116883 x20 x30883116883 x40 x50 x61 e x70260869565 Valor da função objetivo 4125974026 P14 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x61 x10 0 xi1 i17 Solução x10 x20822580645 x30822580645 x40 x51 x61 e x70 Valor da função objetivo 4056451613 P15 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x61 x11 0 xi1 i17 Solução x11 x20 x30755294118 x40 x50 x61 e x70 Valor da função objetivo 4102941176 P16 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x61 x11 x30 0 xi1 i17 Solução x11 x20 x30 x4016666666 x51 x61 e x70 Valor da função objetivo 401666666666 P17 max 17 x110x215 x319 x47 x513 x69 x7 sa 43 x128 x234 x348 x417 x532 x623 x7100 x1 x21 x3x4x1x2 x61 x11 x31 0 xi1 i17 Solução Inviável SOLUÇÃO ÓTIMA Solução x11 x20x31 x40 x50 x60 e x71 Valor da função objetivo 41 Exemplo 2 Considere as seguintes variáveis xi foi realizado o investimento na oportunidade i14 Temos então o seguinte modelo max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x62 Restrição adicional podemos investir no máximo em 3 oportunidades xi01 i14 Vamos relaxar a restrição de integralidade e formular o problema P1 como problema inicial do Branch and Bound Abaixo é apresentado a árvore do Branch and Bound e a descrição de cada um dos problemas da árvore e sua respectiva solução P1 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades 0 xi1 i14 Solução x11 x208 x30 e x41 Valor da solução 48200 P2 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x20 0 xi1 i14 Solução x105 x20 x31 e x41 Valor da solução 36000 P3 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x20 x10 0 xi1 i14 Solução x10 x20 x31 e x41 Valor da solução 27000 P4 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x20 x11 0 xi1 i14 Solução x11 x20 x30 e x41 Valor da solução 33000 P5 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x21 0 xi1 i14 Solução x11 x21 x30 e x406 Valor da solução 46000 P6 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x21 x40 0 xi1 i14 Solução x11 x21 x305 e x40 Valor da solução 43000 P7 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x21 x40 x30 0 xi1 i14 Solução x11 x21 x30 e x40 Valor da solução 37000 P8 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x21 x40 x31 0 xi1 i14 SoluçãoInviável P9 max 18000 x119000 x212000 x315000 x4 Valor Presente Total sa 5000 x17000 x23000 x414000 Mês 1 8000 x14000 x34000 x412000 Mês 2 2000 x110000 x26000 x35000 x415000 Mês 3 x1 x2x3x63 Restrição adicional podemos investir no máximo em 3 oportunidades x21 x41 0 xi1 i14 Solução x10 x21 x30 e x41 Valor da solução 34000 SOLUÇÃO ÓTIMA Solução x11 x21 x30 e x40 Valor da solução 37000 Exercício 1114 a Considere as seguintes variáveis 𝑥𝑖 foi realizado o investimento na oportunidade 𝑖 1 7 Temos então o seguinte modelo max Lucro total 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa Valor total investido 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 Não podemos investir em 1 e 2 ao mesmo tempo 𝑥1 𝑥2 1 Não podemos investir em 3 e 4 ao mesmo tempo e sem ter 𝑥3 𝑥4 𝑥1 𝑥2 investido em 1 ou 2 𝑥𝑖 0 1 𝑖 1 7 b Vamos relaxar a restrição de integralidade e formular o problema como problema 𝑃1 inicial do Branch and Bound Abaixo é apresentado a árvore do Branch and Bound e a descrição de cada um dos problemas da árvore e sua respectiva solução 𝑃1 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 1 𝑥4 0 𝑥5 1 𝑥6 0 1875 e 𝑥7 0 Valor da função objetivo 41 4375 𝑃2 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 1 𝑥4 0 𝑥5 1 𝑥6 0 e 𝑥7 0 260869565 Valor da função objetivo 41 34782609 𝑃3 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 0 𝑥𝑖 1 𝑖 1 7 Solução e 𝑥1 1 𝑥2 0 𝑥3 0 57142857 𝑥4 0 42857142857 𝑥5 1 𝑥6 0 𝑥7 0 Valor da função objetivo 40 714285 𝑃4 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 0 0 𝑥𝑖 1 𝑖 1 7 Solução e 𝑥1 0 9120879 𝑥2 0 𝑥3 0 𝑥4 0 9120879 𝑥5 1 𝑥6 0 𝑥7 0 260869565 Valor da função objetivo 39 8351648 𝑃5 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 0 𝑥1 0 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 0 𝑥2 1 𝑥3 0 𝑥4 1 𝑥5 1 𝑥6 0 e 𝑥7 0 Valor da função objetivo 39 8351648 𝑃6 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 0 𝑥1 1 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 0 𝑥4 0 833333333 𝑥5 1 𝑥6 0 e 𝑥7 0 Valor da função objetivo 39 8333333333 𝑃7 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 0 𝑥1 1 𝑥4 0 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 0 𝑥4 0 𝑥5 1 𝑥6 0 e 𝑥7 0 Valor da função objetivo 24 𝑃8 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 0 𝑥1 1 𝑥4 1 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 0 𝑥4 1 𝑥5 0 52941176 𝑥6 0 e 𝑥7 0 Valor da função objetivo 39 70588235 𝑃9 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 0 𝑥1 1 𝑥4 1 𝑥5 0 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 0 𝑥4 1 𝑥5 0 𝑥6 0 e 𝑥7 0 Valor da função objetivo 36 𝑃10 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 0 𝑥1 1 𝑥4 1 𝑥5 1 0 𝑥𝑖 1 𝑖 1 7 Solução Inviável 𝑃11 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 0 𝑥3 1 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 1 𝑥4 0 𝑥5 1 𝑥6 0 e 𝑥7 0 Valor da função objetivo 39 𝑃12 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 0 𝑥7 1 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 1 𝑥4 0 𝑥5 0 𝑥6 0 e 𝑥7 1 Valor da função objetivo 41 𝑃13 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 1 0 𝑥𝑖 1 𝑖 1 7 Solução e 𝑥1 0 883116883 𝑥2 0 𝑥3 0 883116883 𝑥4 0 𝑥5 0 𝑥6 1 𝑥7 0 260869565 Valor da função objetivo 41 25974026 𝑃14 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 1 𝑥1 0 0 𝑥𝑖 1 𝑖 1 7 Solução e 𝑥1 0 𝑥2 0 822580645 𝑥3 0 822580645 𝑥4 0 𝑥5 1 𝑥6 1 𝑥7 0 Valor da função objetivo 40 56451613 𝑃15 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 1 𝑥1 1 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 0 755294118 𝑥4 0 𝑥5 0 𝑥6 1 e 𝑥7 0 Valor da função objetivo 41 02941176 𝑃16 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 1 𝑥1 1 𝑥3 0 0 𝑥𝑖 1 𝑖 1 7 Solução 𝑥1 1 𝑥2 0 𝑥3 0 𝑥4 0 16666666 𝑥5 1 𝑥6 1 e 𝑥7 0 Valor da função objetivo 40 1666666666 𝑃17 max 17𝑥1 10𝑥2 15𝑥3 19𝑥4 7𝑥5 13𝑥6 9𝑥7 sa 43𝑥1 28𝑥2 34𝑥3 48𝑥4 17𝑥5 32𝑥6 23𝑥7 100 𝑥1 𝑥2 1 𝑥3 𝑥4 𝑥1 𝑥2 𝑥6 1 𝑥1 1 𝑥3 1 0 𝑥𝑖 1 𝑖 1 7 Solução Inviável SOLUÇÃO ÓTIMA Solução 𝑥1 1 𝑥2 0 𝑥3 1 𝑥4 0 𝑥5 0 𝑥6 0 e 𝑥7 1 Valor da função objetivo 41 Exemplo 2 Considere as seguintes variáveis 𝑥𝑖 foi realizado o investimento na oportunidade 𝑖 1 4 Temos então o seguinte modelo max Valor Presente Total 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 2 oportunidades 𝑥𝑖 0 1 𝑖 1 4 Vamos relaxar a restrição de integralidade e formular o problema como problema 𝑃1 inicial do Branch and Bound Abaixo é apresentado a árvore do Branch and Bound e a descrição de cada um dos problemas da árvore e sua respectiva solução max Valor Presente Total 𝑃1 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 1 𝑥2 0 8 𝑥3 0 e 𝑥4 1 Valor da solução 48200 max Valor Presente Total 𝑃2 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 0 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 0 5 𝑥2 0 𝑥3 1 e 𝑥4 1 Valor da solução 36000 max Valor Presente Total 𝑃3 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 0 𝑥1 0 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 0 𝑥2 0 𝑥3 1 e 𝑥4 1 Valor da solução 27000 max Valor Presente Total 𝑃4 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 0 𝑥1 1 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 1 𝑥2 0 𝑥3 0 e 𝑥4 1 Valor da solução 33000 max Valor Presente Total 𝑃5 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 1 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 1 𝑥2 1 𝑥3 0 e 𝑥4 0 6 Valor da solução 46000 max Valor Presente Total 𝑃6 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 1 𝑥4 0 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 1 𝑥2 1 𝑥3 0 5 e 𝑥4 0 Valor da solução 43000 max Valor Presente Total 𝑃7 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Mês 3 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 1 𝑥4 0 𝑥3 0 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 1 𝑥2 1 𝑥3 0 e 𝑥4 0 Valor da solução 37000 max Valor Presente Total 𝑃8 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 1 𝑥4 0 𝑥3 1 0 𝑥𝑖 1 𝑖 1 4 SoluçãoInviável max Valor Presente Total 𝑃9 18000𝑥1 19000𝑥2 12000𝑥3 15000𝑥4 sa Mês 1 5000𝑥1 7000𝑥2 3000𝑥4 14000 Mês 2 8000𝑥1 4000𝑥3 4000𝑥4 12000 Mês 3 2000𝑥1 10000𝑥2 6000𝑥3 5000𝑥4 15000 Restrição adicional podemos investir no máximo em 3 𝑥1 𝑥2 𝑥3 𝑥6 3 oportunidades 𝑥2 1 𝑥4 1 0 𝑥𝑖 1 𝑖 1 4 Solução 𝑥1 0 𝑥2 1 𝑥3 0 e 𝑥4 1 Valor da solução 34000 SOLUÇÃO ÓTIMA Solução 𝑥1 1 𝑥2 1 𝑥3 0 e 𝑥4 0 Valor da solução 37000