Um sistema de apoio à decisão baseado em optimização para o planeamento de auto...

• Author(s): Pereira, P. A.
• Date: 2009
• Persistent ID: http://hdl.handle.net/1822/9609
• Origin: RepositóriUM - Universidade do Minho
• Subject(s): Planeamento da auto-promoção; Sistemas de apoio à decisão; Optimização combinatória; Algoritmos genéricos; Self-promotion planning; Decision support systems; Combinatorial optimization; Genetic algorithms
• Document Type: Doctoral Thesis
• Language: Portuguese
• Advisor(s): Fontes, Fernando A. C. C.; Fontes, Dalila B. M. M.

Description

Tese de doutoramento em Ciências (ramo de conhecimento em Matemática) Neste trabalho apresentamos o processo de desenvolvimento e implementação de um sistema de apoio à decisão (SAD) para o planeamento do espaço de auto-promoção de uma estação de televisão portuguesa. As estações de televisão têm espaços temporais dedicados à promoção dos seus próprios produtos. Pretende-se que o conjunto semanal destes espaços seja utilizado de forma optimizada. Foram identicados objectivos específicos para cada produto, objectivos globais e condições sob as quais o espaço semanal deve ser planeado. O processo de traduzir matematicamente os diversos objectivos pretendidos tal como as várias restrições encontradas revelou-se complexo. Assim, o problema de optimização encontrado foi formulado como a maximização da soma do número de contactos de cada produto com o seu público-alvo, sujeito a um grande número de restrições traduzidas matematicamente. Este é um problema de optimização Combinatória com semelhanças com outros problemas da área tais como o problema da mochila e o problema de afectação. No entanto, apresenta características que o tornam bastante distinto e com necessidade de se desenvolver um tratamento específico. Não encontramos na literatura estudos sobre o problema defenido. Devido as suas caracteristicas - principalmente a complexidade e dimensção - o problema foi abordado heurísticamente com recurso a algoritmos gen eticos. O algoritmo foi desenvolvido, implementado e testado inicialmente em problema simplicados e de menor dimensão - de forma a permitir a afinação dos parâmetros. O SAD desenvolvido, que é descrito na primeira parte da tese, integra um optimizador que aborda o problema de optimização identificado. Este problema de optimização e o algoritmo desenvolvido para sua resolução são descritos na segunda parte da tese. This thesis describes the development and implementation of a Decision Support System (DSS) to plan the self-promotion space of a television station. Television stations reserve time intervals that are speci cally dedicated to the promotion of their own programs or products. The aim is to make use of this self-promotion space in an optimized way. In this process we had to identify global objectives for the campaign as well as specific objectives for each product, and conditions under which the weekly time space should be planned. The set of objectives identi ed, combined with the constraints needed for this problem, was challenging to translate into standard mathematical programming formulation. We have formulated this problem to be the maximization of the sum of all contact of each product with its target audience, subject to numerous constraints. The problem obtained is a combinatorial optimization problem with similarities with other known problems, such as, the knapsack problem and the allocation problem. However, our problem exhibits some characteristics that diferentiate it from other problems found in literature, thus requiring a specific methodology to address it. Due to its characteristics, mainly complexity and dimension, an heuristic method based on genetic algorithms was chosen to address it. The algorithm was developed, implemented and tested - initially in simplified problems of lower dimension - in order to tune the design parameters. The DSS developed, - which is described in the first part of the thesis - has as an optimizer which addresses our optimization problem. The optimization problem and the algorithms to address it are described in the second part of the thesis.