São Paulo (AUN - USP) - Como achar uma melhor rota de entrega de um determinado produto, como proceder melhor no corte de uma placa de metal para haver o menor desperdício possível do material, ou determinar a seqüência do código genético? Essas são algumas das várias aplicações práticas da linha de pesquisa otimização combinatória, do Instituto de Matemática e Estatística (IME) da USP.

A característica comum a todos esses problemas, em que essa técnica é utilizada, é o fato de possuírem uma gama muito grande de combinações possíveis como solução. Encontrar matematicamente a solução mais interessante, através de algoritmos (formas de resolver), é o que busca o grupo de pesquisa. Entretanto, como ressalta o professor Paulo Feofiloff, os problemas não aparecem para os pesquisadores para serem resolvidos. Em geral os modelos teóricos, juntamente com programas de computador que os apliquem, são criados independentemente de serem levados à prática, o que posteriormente pode ocorrer. Este foi o caso de um algoritmo desenvolvido pelo professor Carlos Eduardo Ferreira, que após ser concluído, pode ser aplicado em indústrias canavieiras.

Muitas vezes, porém, os pesquisadores partem de problemas já clássicos no meio, como o caso do caixeiro viajante. Como achar a melhor combinação entre as várias possibilidades de rotas possíveis para um comerciante peregrino, para que tenha o máximo aproveitamento possível em relação aos pontos de venda e de reabastecimento. Problema semelhante foi tratado pelos pesquisadores do IME em relação aos barcos que faziam o transporte de pessoal entre as plataformas da Petrobrás.

Outro problema clássico na área é o que envolve o corte de diferentes tamanhos de um determinado material. Em uma fábrica de peças de vidro, por exemplo, como proceder na divisão de uma única grande peça em outras de diferentes tamanhos, previamente encomendados, para se ter o menor desperdício possível. O grupo desenvolveu um algoritmo para um problema semelhante encontrado em uma indústria de cerâmica.

É importante ressaltar, por outro lado, que o sistema de busca de soluções para os problemas nunca é perfeito. Sempre, por mais desenvolvido que seja o algoritmo, há uma margem de erro, que é estabelecida em seu desenvolvimento. O que se busca, portanto, é a resposta mais adequada possível para os desafios propostos. A professora Yoshiko Wakabayashi, por exemplo, conseguiu uma melhora espantosa no grau de erro encontrado no sistema de encaixotamento em contêineres. Anteriormente, a falibilidade ficava em torno de 600%, ou seja, uma resposta possível para a quantidade necessária para abrigar determinada carga poderia ser dada como estando entre 6 e 36 contêineres. Agora, esta margem de erro caiu para 200%, sendo a resposta para o mesmo problema anterior dada entre 36 e 18 compartimentos.

Um grupo que faz pesquisas semelhantes na Unicamp teve seus serviços requisitados para auxiliar o famoso projeto que mapeou todo o código genético do causador da doença do amarelinho nos pés de laranja. Como o DNA tem de ser quebrado para poder ser analisado, sua recombinação pode ser extremamente trabalhosa, apresentando, entretanto, características que possibilitaram a aplicação de programas de computador desenvolvidos com as técnicas da otimização combinatória. Essa também é uma das áreas de interesse do grupo de pesquisadores da USP.