Programação Dinâmica Determinística

A programação dinâmica (PD) determina a solução ótima de um problema de multivariáveis decompondo-o em estágios, sendo que cada estágio compreende um subproblema com uma única variável. A vantagem da decomposição é que o processo de otimização em cada estágio envolve apenas uma variável, uma tarefa mais simples em termos de cálculo do que lidar com todas as variáveis simultaneamente. Um modelo PD é basicamente uma equação recursiva que liga os diferentes estágios do problema de maneira que garante que a solução ótima viável de cada estágio também é ótima e viável para o problema inteiro.

            A notação e a estrutura conceitual da equação recursiva são diferentes de quaisquer outras que você tenha estudado até aqui. A experiência mostrou que a estrutura da equação recursiva pode não parecer lógica para um principiante. Se você já passou por experiência semelhante, sabe que o melhor procedimento é tentar implementar o que lhe pareça lógico e então executar os cálculos de acordo com isso. Você não tardará a descobrir que as definições apresentadas no livro são as corretas e, durante o processo, aprenderá como a PD funciona.

            Embora a equação recursiva seja uma estrutura comum para a formulação de modelos de PD, os detalhes da solução são diferentes. Somente pela exposição a diferentes formulações é que você conseguirá ganhar experiência em modelagem de PD e solução de PD.

Aplicação real – Otimização de corte transversal e alocação de toras na Weyerhaeuser

            Árvores antigas são cortadas e serradas em toras para fabricar diferentes produtos finais (como madeira para construção civil, compensado, placas ou papel). As especificações das toras (por exemplo, comprimento, diâmetros finais) são diferentes dependendo da serraria onde as toras serão usadas. Com árvores cortadas de até 35 metros de comprimento, o número de combinações de cortes transversais que atende aos requisitos da serraria pode ser grande, e a maneira como a árvore é desmembrada em toras pode afetar a receita. O objetivo é determinar as combinações de cortes transversais que maximizem a receita total. O estudo usa a programação dinâmica para otimizar o processo. O sistema proposto foi implementado pela primeira vez em 1978, resultando em um aumento anual do lucro de no mínimo $ 7 milhões.

NATUREZA RECURSIVA DOS CÁLCULOS EM PD

            Os cálculos em PD são feitos recursivamente, de modo que a solução ótima de um subproblema é usada como dado de entrada para o subproblema seguinte. Quando o último subproblema é resolvido, a solução ótima para o problema inteiro está à mão. O modo como os cálculos recursivos são executados depende de como decompomos o problema original. Em particular, os subproblemas normalmente estão ligados por restrições em comum. À medida que passamos de um subproblema para o seguinte, a viabilidade dessas restrições em comum deve ser mantida.

Fonte: Taha