Prévia do material em texto
APÊNDICE UNIDADE 2 Pesquisa Operacional: Simulação U2 - Programação dinâmica e programação não linear2 UNIDADE 2: Programação dinâmica e programação não linear Gabarito 1. Faça valer a pena - Seção 2.1 1. Alternativa C. Resposta comentada: a criação da programação dinâmica é atribuída a Richard Bellman e consiste em dividir um problema de grande porte em problemas menores mais fáceis de serem solucionados. Considerando a versatilidade na aplicação em diversos tipos de problemas de Pesquisa Operacional e dados a natureza de cada problema, não é possível a formulação de uma solução padronizada, sendo necessária a formulação de cada problema de forma distinta. 2. Alternativa B. Resposta comentada: a utilização de computadores na solução de problemas de pesquisa operacional é plenamente justificada pela complexidade de grande parte dos problemas e pela repetitividade dos algoritmos desenvolvidos para a solução desses problemas. Assim, na solução pela programação dinâmica, o tipo regressivo facilita a lógica da programação da solução utilizando o computador. 3. Alternativa A. Resposta comentada: o princípio de otimalidade enuncia que dado o estado atual, uma decisão ótima para o estágio futuro independe das decisões adotadas nos estágios anteriores. Concluímos que a decisão imediata ótima depende somente do estado atual e não das passadas. Apêndice Gabaritos comentados com resposta-padrão U2 - Programação dinâmica e programação não linear3 Gabarito 2. Faça valer a pena - Seção 2.2 1. Alternativa B. Resposta comentada: O modelo max : z x x x x sujeito x x x = −z x= −z x + −x x+ −x x + ≤x x+ ≤x x ≤ ≥ 240z x240z xz x= −z x240z x= −z x 24 240+ −240+ −x x+ −x x240x x+ −x x 24 2 3x x2 3x x+ ≤2 3+ ≤x x+ ≤x x2 3x x+ ≤x x 18 6 0 1 1x x1 1x x= −1 1= −241 124 2x x2x x2 2x2 2x+ −2 2+ −x x+ −x x2 2x x+ −x x 242 224 2 1 2+ ≤1 2+ ≤x x+ ≤x x1 2x x+ ≤x x2 31 22 3x x2 3x x1 2x x2 3x x+ ≤2 3+ ≤1 2+ ≤2 3+ ≤x x+ ≤x x2 3x x+ ≤x x1 2x x+ ≤x x2 3x x+ ≤x x 1 1 2,1 2,x x1 2x x,x x,1 2,x x, apresenta função objetiva não linear. As outras alternativas apresentam somente funções lineares apesar das variações apresentadas nas restrições dos modelos, todas já estudadas em Pesquisa Operacional: Programação Matemática. 2. Alternativa D. Resposta comentada: o objetivo dos investimentos é maximizar o valor presente líquido (a soma dos VPLs individuais). O valor total disponível para o investimento é de R$ 180.000,00, portanto, a soma de todos os investimentos está limitada a esse valor. É dito que o valor máximo em cada investimento é de R$ 60.000,00, ou seja, deve ser menor ou igual a R$ 60.000,00. Por fim, os valores investidos não podem ser negativos. 3. Alternativa E. Resposta comentada: em problemas de PNL existem funções lineares e não lineares em seu modelo, entretanto, não existe a obrigatoriedade de todas as funções serem não lineares, como afirma a primeira alternativa. Nas representações gráficas de PNL com duas variáveis a solução ótima estará na superfície de alguma restrição, e não nos pontos extremos (eles podem não existir). As condições de Karush-Kuhn-Trucker (KKT) são aplicadas para verificar se a solução é ótima, portanto a alternativa correta é a última. U2 - Programação dinâmica e programação não linear4 Gabarito 3. Faça valer a pena - Seção 2.3 1. Alternativa D. Resposta comentada: problemas de PNL são problemas de otimização e a construção do modelo é muito parecida com os problemas de Programação Linear, entretanto, nos problemas de PNL deve haver uma função não linear. E essa função não linear pode ser a função objetivo ou estar entre as restrições do problema. 2. Alternativa C. Resposta comentada: para se saber o tipo de função é preciso derivar a mesma duas vezes. A solução da primeira derivada é: f x x x'f x'f x( )f x( )f x = + +4 1x x4 1x x= +4 1= +x x= +x x4 1x x= +x x2 1x x2 1x x+2 1+ 234 134 1= +4 1= +3= +4 1= +x x= +x x4 1x x= +x x3x x= +x x4 1x x= +x x e a segunda derivada tem como resultado: f x''f x''f x( )f x( )f x = +x= +x12= +12= +122= +2= + . Como não temos resultado do tipo f x''f x''f x( )f x( )f x > 0 ou f x''f x''f x( )f x( )f x < 0 ou f x''f x''f x( )f x( )f x = 0, a função é do tipo nem convexa nem côncava. 3. Alternativa B. Resposta comentada: Para saber o tipo de função é preciso derivar duas vezes esta e analisar o resultado. A segunda derivada da primeira alternativa, temos: f x x''(f x''(f x)= 6 ® função nem convexa nem côncava. Na segunda alternativa temos: f x x''(f x''(f x)= ≥e= ≥ex= ≥x 0 ® função convexa. Na terceira alternativa: f x''(f x''(f x)= 0 ® função convexa e côncava. Na quarta alternativa: f x x''(f x''(f x)= −2 3 ® função nem convexa nem côncava. Na quinta alternativa: f x x''(f x''(f x)=− −2 ® função nem convexa nem côncava. Portanto, a alternativa correta é: f x ex( )f x( )f x = .