Métodos tipo dual simplex para problemas de otimização linear canalizados e esparsos

Pesquisa Operacional

Carla Taviane Lucke Da Silva²  Marcos Nereu Arenales²  Ricardo Silveira Sousa¹ 

[1] ,Universidade de São Paulo Inst. de Ciências Matemáticas e de Computação São Carlos SP

关键词: otimização linear;    otimização linear por partes;    dualidade;    esparsidade;    linear optimization;    piecewise linear optimization;    duality;    sparsity;   

DOI  :  10.1590/S0101-74382007000300004

来源: SciELO

【 摘 要 】

Os problemas de otimização linear canalizados e esparsos, objeto principal deste trabalho, surgem em várias aplicações, como por exemplo, problemas de planejamento da produção, problemas de mistura, entre outras. Métodos tipo dual simplex com busca linear por partes foram propostos e analisados em Sousa et al. (2005), com resultados efetivos para problemas densos pequenos e agora são analisados para problemas esparsos maiores. Algumas heurísticas de pivotamento foram implementadas para tentar manter a esparsidade e reduzir o tempo total de resolução dos problemas. Um conjunto de exemplos com estruturas esparsas que tipicamente ocorrem na prática foram gerados aleatoriamente para analisar o desempenho dos métodos. Os resultados computacionais demonstram a eficiência da abordagem.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License