O planejamento da operação energética de sistemas hidrotérmicos de potência tem como objetivo determinar a participação de usinas termoelétricas e hidrelétricas de forma a garantir o suprimento desta energia ao menor custo operacional possível, dentro de restrições técnicas. Alguns fatores tornam a solução desse problema bastante complexa destacando a não linearidade, presente na equação de geração hidráulica; a não separabilidade espacial, devido ao fato da decisão de quanto gerar em uma usina interferir em outra usina do sistema; a separabilidade temporal aditiva, devido a interferência de uma decisão atual em uma decisão futura e, como no caso brasileiro, de grande porte. O objetivo deste trabalho é apresentar uma nova abordagem para o planejamento da operação de sistemas hidrotérmicos de potência, com Programação Dinâmica, de forma que as usinas hidrelétricas possam ser representadas e otimizadas individualmente, completamente desacopladas. Essa aplicação é possível através da utilização de uma função objetivo modificada, considerando-se não apenas os custos, mas também os dados de afluências das usinas imediatamente a jusante. O modelo proposto, como função objetivo modificada, foi aplicado em cascatas de usinas hidrelétricas brasileiras, cujos resultados puderam ser comparados com os comportamentos ótimos obtidos de forma direta, ou seja, com a otimização de todo o sistema em conjunto. Com base nos resultados obtidos, pôde-se observar o bom comportamento do modelo implementado. / The energetic operation planning in hydrothermal power systems aims to determine the participation of hydroelectric power plants and thermoelectric power plants to ensure the supply of electricity at the lowest operating cost possible, between technical constraints. Some factors make the solution of this problem quite complex highlighting the nonlinearity, present in the equation of hydraulic generation, non-spatial separability, due the fact that the decision of the amount of energy generated in a plant interfere in another plants of the system, the additive time separability, because of the interference from an actual decision on a future decision and, as in the Brazilian case, large. The proposal of this work is to present a new approach to hydrothermal power systems, with Dynamic Programming, so that hydroelectric power plants can be represented and optimized individually, completely decoupled. This application is possible through the use of a modified objective function, considering not only costs but also the inflow data immediately on the downstream plants. The proposed model was applied in a Brazilian cascade of hydroelectric plants, comparing the optimal behavior obtained directly, by optimizing the whole system together and the new technique behavior. Based on the results obtained, we can observe the good results of the implemented model.

O referencial da Teoria da Localização embasa o modelo matemático de otimização dinâmico desenvolvido a fim de se determinar os melhores locais dos frigoríficos-abatedouros exportadores no Brasil visando à minimização dos custos associados ao transporte, bem como os custos associados à instalação de novas unidades industriais de abate, resultando, assim, em aumento de competitividade para a cadeia. Este trabalho visa responder a três questões: (i) localizações das unidades industriais de abate; (ii) tamanho e número ótimos de cada unidade industrial de abate e (iii) fluxos mensais da matéria-prima necessários para atender a demanda dos frigoríficos-abatedouros exportadores, bem como os fluxos ofertados mensalmente por eles a fim de se satisfazer a demanda dos países importadores da carne bovina brasileira. Desse modo, foram simulados quatro cenários alternativos. Os dois primeiros disseram respeito sobre a determinação da localização dos frigoríficos-abatedouros exportadores e respectivos fluxos de produtos num contexto ideal, ou seja, o modelo determinou onde os mesmos deveriam ser instalados. Enquanto o primeiro cenário considerou na modelagem os dez principais estados exportadores da carne bovina desossada congelada brasileira, o segundo considerou os seis principais estados, excluindo, assim, os estados que fazem parte da Amazônia Legal. No primeiro cenário, dos dez estados considerados, em cinco deveriam ser instalados ao menos um frigoríficoabatedouro exportador, enquanto no segundo cenário dos seis estados considerados em três deveriam ser instalados ao menos um frigorífico-abatedouro exportador. Ambos os cenários indicaram São Paulo como estado candidato à instalação de maior número de frigoríficosabatedouros exportadores. Além disso, em ambos os cenários a decomposição dos custos logísticos revelou que a maior parte do custo total mínimo obtido nos processamentos dos modelos decorreu da instalação dos frigoríficos-abatedouros exportadores,76,3% do custo total mínimo obtido no cenário 1 e 79,4% do custo total mínimo obtido no cenário 2, seguidos pelo custo de transporte da carne bovina aos mercados externos (14,9% e 14,1%) e custo de transporte da carne bovina aos portos exportadores (5,7% e 3,6%). O custo de transporte da matéria-prima aos frigoríficos-abatedouros exportadores foi 1,9% e 1,2% do custo total mínimo obtido no cenário 1 e 2, respectivamente, ao passo que o custo de transporte da carne bovina aos mercados internos foi de 1,2% e 1,7% do respectivo custo total mínimo. O terceiro e quarto cenários disseram respeito sobre quais frigoríficos-abatedouros exportadores já instalados deveriam ser responsáveis pelo abastecimento dos mercados externos demandantes de carne bovina desossada congelada brasileira. Ambos consideraram na modelagem as localizações atuais dos frigoríficos abatedouros exportadores existentes nos seis principais estados exportadores do produto. No entanto, o último cenário refere-se a projeção de aumento de demanda externa futura por carne bovina. Nesses cenários, como não há custo de intalação dos frigoríficos-abatedouros exportadores a ser incorridos, a maior parcela dos custos logísticos decorreu da distribuição da carne bovina aos mercados externos. Os resultados do terceiro cenário revelaram que 12 frigoríficos-abatedouros exportadores seriam suficientes para atender plenamente os mercados externos, ao passo que o aumento da demanda externa futura exigirá 14 frigoríficos-abatedouros exportadores. / The theoretical framework of the Location Theory supports the dynamic optimization mathematical model developed in order to determine the potential sites for the installation of exporter slaughterhouses in Brazil, minimizing the costs associated with transportation and the costs associated with the installation of new slaughter industrial units, thereby increasing the competitiveness of the chain. The following three questions were addressed: (i) at what locations should slaughter industrial units be installed; (ii) what is the optimal-size and number of each slaughter industrial, and (iii) what are the flows of raw material required monthly to meet the exporter slaughterhouses demand and the monthly supplied amount by them in order to meet the importing countries demands? Thus, four alternative scenarios were simulated. The first two scenarios are related to determine the exporter slaughterhousess locations and the products flows in an ideal environment, i.e., the model determines where they should be installed. The difference between these scenarios is that the former considers in the modeling the Brazilian top ten exporter states of frozen boneless beef, while the second considers the six major states, excluding, thus, the states that belong to the Amazon region. In the first scenario, at least one exporter slaughterhouse should be installed in five out of ten states considered, while in the second scenario at least one exporter slaughterhouse should be installed in three out of six states considered. Both scenarios indicated that most of the exporter slaughterhouses should be installed in São Paulo. Moreover, in both scenarios the decomposition of logistics costs has shown that most of the minimum total cost obtained in the models processing was due to the installation of the exporter slaughterhouses, 76.3% of the minimum total cost obtained in the scenario 1 and 79, 4% of the minimum total cost obtained in the scenario 2, followed by the cost of transporting beef up to the foreign markets (14.9% and 14.1%) and by the cost of transporting beef up to the exporter ports (5.7% and 3 , 6%). The cost of transporting the raw material up to the exporter slaughterhouses was 1.9% and 1.2% of the minimum total cost obtained in scenario 1 and 2, respectively, while the cost of transporting beef up to the domestic markets was 1.2% and 1.7% of the minimum total cost, respectively. The third and fourth scenarios concerned about which exporter slaughterhouses already installed should be responsible for fulfilling the demands of the external markets for the Brazilian frozen boneless beef. Both scenarios considered in the modeling the actual locations of the existing exporter slaughterhouses in the six main exporter states of the product. However, the latter scenario considers an increase in the beef future demand of the external markets. Since there is no cost related to the installation of the exporter slaughterhouses to be incurred in these scenarios, the largest share of logistics costs was related to the distribution of beef up to the foreign markets. The results of the third scenario indicates that 12 exporter slaughterhouses would be enough to fully meet the demands of the foreign markets for frozen boneless beef, while the increase in the external demands will require 14 exporter slaughterhouses.

Um dos modelos mais usados para descrever problemas de planejamento probabilístico, i.e., planejamento de ações com efeitos probabilísticos, é o processo de decisão markoviano (Markov Decision Process - MDP). Soluções tradicionais são baseadas em programação dinâmica, sendo as mais ecientes aquelas baseadas em programação dinâmica em tempo real (Real-Time Dynamic Programming - RTDP), por explorarem somente os estados alcançáveis a partir de um dado estado inicial. Por outro lado, existem soluções ecientes baseadas em métodos de busca heurística em um grafo AND/OR, sendo que os nós AND representam os efeitos probabilísticos das ações e os nós OR representam as escolhas de ações alternativas. Tais soluções também exploram somente estados alcançáveis a partir de um estado inicial porém, guardam um subgrafo solução parcial e usam programação dinâmica para a atualização do custo dos nós desse subgrafo. No entanto, problemas com grandes espaços de estados limitam o uso prático desses métodos. MDPs fatorados permitem explorar a estrutura do problema, representando MDPs muito grandes de maneira compacta e assim, favorecer a escalabilidade das soluções. Neste trabalho, apresentamos uma análise comparativa das diferentes soluções para MDPs, com ênfase naquelas que fazem busca heurística e as comparamos com soluções baseadas em programação dinâmica assíncrona, consideradas o estado da arte das soluções de MPDs. Além disso, propomos um novo algoritmo de busca heurística para MDPs fatorados baseado no algoritmo ILAO* e o testamos nos problemas da competição de planejamento probabilístico IPPC-2011. / One of the most widely used models to describe probabilistic planning problems, i.e., planning of actions with probabilistic eects, is the Markov Decision Process - MDP. The traditional solutions are based on dynamic programming, whereas the most ecient solutions are based on Real-Time Dynamic Programming - RTDP, which explore only the reachable states from a given initial state. Moreover, there are ecient solutions based on search methods in a AND/OR graph, where AND nodes represent the probabilistic eects of an action and OR nodes represent the choices of alternative actions. These solutions also explore only reachable states but maintain the parcial subgraph solution, using dynamic programming for updating the cost of nodes of these subgraph. However, problems with large state spaces limit the practical use of these methods. Factored representation of MDPs allow to explore the structure of the problem, and can represent very large MDPs compactly and thus improve the scalability of the solutions. In this dissertation, we present a comparative analysis of dierent solutions for MDPs, with emphasis on heuristic search methods. We compare the solutions which are based on asynchronous dynamic programming which are also considered the state of the art. We also propose a new factored algorithm based on the search algorithm ILAO*. It is also tested by using the problems of the International Probabilistic Planning Competition IPPC-2011.

Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.

O planejamento da operação energética de sistemas hidrotérmicos de potência tem como objetivo determinar a participação de usinas termoelétricas e hidrelétricas de forma a garantir o suprimento desta energia ao menor custo operacional possível, dentro de restrições técnicas. Alguns fatores tornam a solução desse problema bastante complexa destacando a não linearidade, presente na equação de geração hidráulica; a não separabilidade espacial, devido ao fato da decisão de quanto gerar em uma usina interferir em outra usina do sistema; a separabilidade temporal aditiva, devido a interferência de uma decisão atual em uma decisão futura e, como no caso brasileiro, de grande porte. O objetivo deste trabalho é apresentar uma nova abordagem para o planejamento da operação de sistemas hidrotérmicos de potência, com Programação Dinâmica, de forma que as usinas hidrelétricas possam ser representadas e otimizadas individualmente, completamente desacopladas. Essa aplicação é possível através da utilização de uma função objetivo modificada, considerando-se não apenas os custos, mas também os dados de afluências das usinas imediatamente a jusante. O modelo proposto, como função objetivo modificada, foi aplicado em cascatas de usinas hidrelétricas brasileiras, cujos resultados puderam ser comparados com os comportamentos ótimos obtidos de forma direta, ou seja, com a otimização de todo o sistema em conjunto. Com base nos resultados obtidos, pôde-se observar o bom comportamento do modelo implementado. / The energetic operation planning in hydrothermal power systems aims to determine the participation of hydroelectric power plants and thermoelectric power plants to ensure the supply of electricity at the lowest operating cost possible, between technical constraints. Some factors make the solution of this problem quite complex highlighting the nonlinearity, present in the equation of hydraulic generation, non-spatial separability, due the fact that the decision of the amount of energy generated in a plant interfere in another plants of the system, the additive time separability, because of the interference from an actual decision on a future decision and, as in the Brazilian case, large. The proposal of this work is to present a new approach to hydrothermal power systems, with Dynamic Programming, so that hydroelectric power plants can be represented and optimized individually, completely decoupled. This application is possible through the use of a modified objective function, considering not only costs but also the inflow data immediately on the downstream plants. The proposed model was applied in a Brazilian cascade of hydroelectric plants, comparing the optimal behavior obtained directly, by optimizing the whole system together and the new technique behavior. Based on the results obtained, we can observe the good results of the implemented model.

Buscando-se a aplicação prática da teoria de Wave Field Synthesis (WFS) na música, foi feita uma pesquisa visando à modelagem de um sistema de sonorização capaz de criar imagens sonoras espaciais com a utilização desta técnica. Diferentemente da maioria das outras técnicas de sonorização, que trabalham com uma região de escuta pequena e localizada, WFS permite projetar os sons de cada fonte sonora - como instrumentos musicais e vozes - em diferentes pontos do espaço de audição, em uma região de escuta que pode abranger quase toda a área compreendida por este espaço, dependendo da quantidade de alto-falantes instalados. O desenvolvimento de um código de estrutura modular para WFS foi baseado na plataforma orientada a patches Pure Data (Pd), e no sistema de auralização AUDIENCE, desenvolvido na USP, sendo integrável como ferramenta para espacialização sonora interativa. A solução emprega patches dinâmicos e uma arquitetura modular, permitindo flexibilidade e manutenabilidade do código, com vantagens frente a outros software existentes, particularmente na instalação, operação e para lidar com um número elevado de fontes sonoras e alto-falantes. Para este sistema também foram desenvolvidos alto-falantes especiais com características que facilitam seu uso em aplicações musicais. / Seeking the practical application of the theory of Wave Field Synthesis (WFS) in music, a research aimed at modeling a sound system capable of creating spatial sound images with the use of this technique was made. Unlike most other techniques for sound projection that work with a small, localized listening area, WFS allows projecting the sounds of each sound source - such as musical instruments and voices - at different points within the hearing space, in a region that can cover almost the entire area comprised by this space, depending on the amount of installed speakers. The development of a modular structured code for WFS was based on the patch-oriented platform Pure Data (Pd), and on the AUDIENCE auralization system developed at USP, and it is integrable as a tool for interactive sound spatialization. The solution employs dynamic patches and a modular architecture, allowing code flexibility and maintainability, with advantages compared to other existing software, particularly in the installation, operation and to handle a large number of sound sources and speakers. For this system special speakers with features that facilitate its use in musical applications were also developed.

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-08-24T14:39:48Z No. of bitstreams: 1 José Artur.pdf: 1071380 bytes, checksum: e1992e06fe45627db90b9f36e8a88d84 (MD5) / Made available in DSpace on 2017-08-24T14:39:48Z (GMT). No. of bitstreams: 1 José Artur.pdf: 1071380 bytes, checksum: e1992e06fe45627db90b9f36e8a88d84 (MD5) Previous issue date: 2012-09-21 / This master dissertation presents a optimization mathematical programming model derived from the classical problem of transport, which aims to scale, with global optimization, the fleet of a system of road passenger transport, describing possible routes between each source/target to meet the constraints of cost (profitability) and quality of service. It covers classic methods of solution of linear programming models considered streaming networks and proposes improvements to the canonical model of the transport problem from the perspective of transit planning, and analyze the use of dynamic programming, evolutionary methods and heuristics for solving the problem of minimization of the model. / Neste trabalho é apresentado um modelo de otimização derivado do problema clássico de transporte, que tem a finalidade de dar suporte ao planejamento de transporte de passageiros , com otimização global, dimensionando a frota de veículos de transporte rodoviário, qualificando as rotas possíveis entre cada origem/destino para satisfazer as restrições de custo (rentabilidade) e qualidade de serviço. Abrange métodos clássicos de solução de modelos de programação linear considerados de fluxo contínuo de redes e propõe melhorias no modelo canônico do problema de transporte a partir da perspectiva do planejamento operacional, além de analisar o uso de métodos de programação dinâmica, métodos evolutivos e heurísticos para a solução do problema de minimização.

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-09-04T13:10:41Z No. of bitstreams: 1 Marcio Eduardo.pdf: 7939176 bytes, checksum: 3b90c4b32aeabafd3b87e4f3c36d2ed6 (MD5) / Made available in DSpace on 2017-09-04T13:10:41Z (GMT). No. of bitstreams: 1 Marcio Eduardo.pdf: 7939176 bytes, checksum: 3b90c4b32aeabafd3b87e4f3c36d2ed6 (MD5) Previous issue date: 2014-08-21 / The technique of linear control based on the minimization of a quadratic performance index using the second method of Lyapunov to guarantee the stability of the system, if this is controllable and observable. however, this technique is inevitably necessary to find the solution of the HJB or Riccati equation. The control system design online need, real time, to adjust your feedback gain to maintain a certain dynamic, it requires the calculation of the Riccati equation solution in each sampling generating a large computational load that can derail its implementation. This work shows an intelligent control system design that meets the optimal or suboptimal control action from the sensory data of process states and the instantaneous cost observed after each state transition. To find this optimal control action or policy, the approximate dynamic programming and adaptive critics are used, based on the parameterizations given by the problem of linear quadratic regulator (LQR), but without explicitly solving the associated Riccati equation. More specifically, the LQR problem is solved by four different methods which are the Dynamic Programming Heuristic, the Dual Heuristic Dynamic Programming, Action Dependent Dynamic Programming Heuristic and Action Dependent Dual Heuristic Dynamic Programming algorithms. However, these algorithms depend on knowledge of the value functions to derive the optimal control actions. These value functions with known structures have their parameters estimated using the least mean square family and Recursive Least Squares algorithms. Two processes that have the Markov property were used in the computational validation of the algorithms adaptive critics implemented, one corresponds to the longitudinal dynamics of an aircraft and the other to an electrical circuit. / A técnica de controle linear baseado na minimização de um índices de desempenho quadrático utilizando o segundo método de Liapunov garante a estabilidade do sistema, se este for controlável e observável. Por outro lado, nessa técnica inexoravelmente é necessário encontrar a solução da Equação Hamilton-Jacobi-Bellman (HJB) ou Riccati. Em projeto de sistema de controle online que necessita, em tempo real, alterar seus ganhos de retroação para manter uma certa dinâmica, impõe o cálculo da solução da equação de Riccati em cada instante de amostragem gerando uma grande carga computacional que pode inviabilizar sua implementação. Neste trabalho, mostra-se o projeto de um sistema de controle inteligente que encontra a ação de controle ótima ou subótima a partir de dados sensoriais dos estados do processo e do custo instantâneo observados após cada transição de estado. Para encontrar essa ação de controle ou política ótima, a programação dinâmica aproximada ou críticos adaptativos são utilizados, tendo como base as parametrizações dado pelo problema do regulador linear quadrático (LQR), mas sem resolver explicitamente a equação de Riccati associada. Mais especificamente, o problema do LQR é resolvido por quatro métodos distintos que são os algoritmos de Programação Dinâmica Heurística, a Programação Dinâmica Heurística Dual, a Programação Dinâmica Heurística Dependente de Ação e a Programação Dinâmica Heurística Dual Dependente de Ação. Entretanto, esses algoritmos dependem do conhecimento das funções valor para, assim, derivar as ações de controle ótimas. Essas funções valor com estruturas conhecidas tem seus parâmetros estimados utilizando os algoritmos da família dos mínimos quadrados médios e o algoritmo de Mínimos Quadrados Recursivo. Dois processos que obedecem à propriedade de Markov foram empregados na validação computacional dos algoritmos críticos adaptativos, um corresponde à dinâmica longitudinal de uma aeronave e o outro à de um circuito elétrico.

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado. / Markov Decision Process (MDP) model problems of sequential decision making, where the possible actions have probabilistic effects on the successor states (defined by state transition matrices). Real-time dynamic programming (RTDP), is a technique for solving MDPs when there exists information about the initial state. Traditional approaches show better performance in problems with sparse state transition matrices, because they can achieve the convergence to optimal policy efficiently, without visiting all states. But, this advantage can be lose in problems with dense state transition matrices, in which several states can be achieved in a step (for example, control problems with exogenous events). An approach to overcome this limitation is to explore regularities existing in the domain dynamics through a factored representation, i.e., a representation based on state variables. In this master thesis, we propose a new algorithm called FactRTDP (Factored RTDP), and its approximate version aFactRTDP (Approximate and Factored RTDP), that are the first factored efficient versions of the classical RTDP algorithm. We also propose two other extensions, FactLRTDP and aFactLRTDP, that label states for which the value function has converged to the optimal. The experimental results show that when these new algorithms are executed in domains with dense transition matrices, they converge faster. And they have a good online performance in domains with dense transition matrices and few dependencies among state variables.

O referencial da Teoria da Localização embasa o modelo matemático de otimização dinâmico desenvolvido a fim de se determinar os melhores locais dos frigoríficos-abatedouros exportadores no Brasil visando à minimização dos custos associados ao transporte, bem como os custos associados à instalação de novas unidades industriais de abate, resultando, assim, em aumento de competitividade para a cadeia. Este trabalho visa responder a três questões: (i) localizações das unidades industriais de abate; (ii) tamanho e número ótimos de cada unidade industrial de abate e (iii) fluxos mensais da matéria-prima necessários para atender a demanda dos frigoríficos-abatedouros exportadores, bem como os fluxos ofertados mensalmente por eles a fim de se satisfazer a demanda dos países importadores da carne bovina brasileira. Desse modo, foram simulados quatro cenários alternativos. Os dois primeiros disseram respeito sobre a determinação da localização dos frigoríficos-abatedouros exportadores e respectivos fluxos de produtos num contexto ideal, ou seja, o modelo determinou onde os mesmos deveriam ser instalados. Enquanto o primeiro cenário considerou na modelagem os dez principais estados exportadores da carne bovina desossada congelada brasileira, o segundo considerou os seis principais estados, excluindo, assim, os estados que fazem parte da Amazônia Legal. No primeiro cenário, dos dez estados considerados, em cinco deveriam ser instalados ao menos um frigoríficoabatedouro exportador, enquanto no segundo cenário dos seis estados considerados em três deveriam ser instalados ao menos um frigorífico-abatedouro exportador. Ambos os cenários indicaram São Paulo como estado candidato à instalação de maior número de frigoríficosabatedouros exportadores. Além disso, em ambos os cenários a decomposição dos custos logísticos revelou que a maior parte do custo total mínimo obtido nos processamentos dos modelos decorreu da instalação dos frigoríficos-abatedouros exportadores,76,3% do custo total mínimo obtido no cenário 1 e 79,4% do custo total mínimo obtido no cenário 2, seguidos pelo custo de transporte da carne bovina aos mercados externos (14,9% e 14,1%) e custo de transporte da carne bovina aos portos exportadores (5,7% e 3,6%). O custo de transporte da matéria-prima aos frigoríficos-abatedouros exportadores foi 1,9% e 1,2% do custo total mínimo obtido no cenário 1 e 2, respectivamente, ao passo que o custo de transporte da carne bovina aos mercados internos foi de 1,2% e 1,7% do respectivo custo total mínimo. O terceiro e quarto cenários disseram respeito sobre quais frigoríficos-abatedouros exportadores já instalados deveriam ser responsáveis pelo abastecimento dos mercados externos demandantes de carne bovina desossada congelada brasileira. Ambos consideraram na modelagem as localizações atuais dos frigoríficos abatedouros exportadores existentes nos seis principais estados exportadores do produto. No entanto, o último cenário refere-se a projeção de aumento de demanda externa futura por carne bovina. Nesses cenários, como não há custo de intalação dos frigoríficos-abatedouros exportadores a ser incorridos, a maior parcela dos custos logísticos decorreu da distribuição da carne bovina aos mercados externos. Os resultados do terceiro cenário revelaram que 12 frigoríficos-abatedouros exportadores seriam suficientes para atender plenamente os mercados externos, ao passo que o aumento da demanda externa futura exigirá 14 frigoríficos-abatedouros exportadores. / The theoretical framework of the Location Theory supports the dynamic optimization mathematical model developed in order to determine the potential sites for the installation of exporter slaughterhouses in Brazil, minimizing the costs associated with transportation and the costs associated with the installation of new slaughter industrial units, thereby increasing the competitiveness of the chain. The following three questions were addressed: (i) at what locations should slaughter industrial units be installed; (ii) what is the optimal-size and number of each slaughter industrial, and (iii) what are the flows of raw material required monthly to meet the exporter slaughterhouses demand and the monthly supplied amount by them in order to meet the importing countries demands? Thus, four alternative scenarios were simulated. The first two scenarios are related to determine the exporter slaughterhousess locations and the products flows in an ideal environment, i.e., the model determines where they should be installed. The difference between these scenarios is that the former considers in the modeling the Brazilian top ten exporter states of frozen boneless beef, while the second considers the six major states, excluding, thus, the states that belong to the Amazon region. In the first scenario, at least one exporter slaughterhouse should be installed in five out of ten states considered, while in the second scenario at least one exporter slaughterhouse should be installed in three out of six states considered. Both scenarios indicated that most of the exporter slaughterhouses should be installed in São Paulo. Moreover, in both scenarios the decomposition of logistics costs has shown that most of the minimum total cost obtained in the models processing was due to the installation of the exporter slaughterhouses, 76.3% of the minimum total cost obtained in the scenario 1 and 79, 4% of the minimum total cost obtained in the scenario 2, followed by the cost of transporting beef up to the foreign markets (14.9% and 14.1%) and by the cost of transporting beef up to the exporter ports (5.7% and 3 , 6%). The cost of transporting the raw material up to the exporter slaughterhouses was 1.9% and 1.2% of the minimum total cost obtained in scenario 1 and 2, respectively, while the cost of transporting beef up to the domestic markets was 1.2% and 1.7% of the minimum total cost, respectively. The third and fourth scenarios concerned about which exporter slaughterhouses already installed should be responsible for fulfilling the demands of the external markets for the Brazilian frozen boneless beef. Both scenarios considered in the modeling the actual locations of the existing exporter slaughterhouses in the six main exporter states of the product. However, the latter scenario considers an increase in the beef future demand of the external markets. Since there is no cost related to the installation of the exporter slaughterhouses to be incurred in these scenarios, the largest share of logistics costs was related to the distribution of beef up to the foreign markets. The results of the third scenario indicates that 12 exporter slaughterhouses would be enough to fully meet the demands of the foreign markets for frozen boneless beef, while the increase in the external demands will require 14 exporter slaughterhouses.