Antônio Carlos Moretti

Departamento de Matemática Aplicada
Universidade Estadual de Campinas

Resumo

Desenvolvemos um procedimento para achar centro de politopos originários de programação linear (P.L.) usando um método de projeções ponderadas. Começando-se em um ponto factível, x(k),  uma iteração é definida como :

1. Sejam p(i,k), i=1,2,...m,as projeções ortogonais nos hiperplanos associados com as m inequações que definem o politopo de programação linear.
2. Sejam d(i,k) = p(i,k) – x(k), i=1,2,...,m.
3. Ajusta-se estas projeções afim de se obter pontos factíveis.
4. Calcula-se mais m projeções usando as direções -d(i,k),i=1,2,...,m.
5. O ponto x(k+1) será o centróide dos pontos obtidos em (2) mais o pontos obtidos em (4).

Observamos que o ponto fixo resultante é menos sensível a restrições redundantes que o centro analítico ( comumente usado como centro de politopo de P.L. ). Além disso, o algoritmo é menos sujeito a erros de arredondamento, uma vez que, sempre usamos os dados originais da matriz que define o problema de P.L.
O algoritmo pode ser facilmente implementável em ambientes seqüenciais ou paralelos. Apresentamos exemplos numéricos para mostrar com o método funciona na prática e definimos uma medida de centricidade para comparar a qualidade dos centros obtidos usando-se projeções com os centros obtidos usando-se a noção de centros analíticos. O uso do método em problemas de geração de colunas para problemas de corte e problemas de factibilidade linear também são exemplificados.