O que é Otimização Combinatória?

Esse nome meio "assustador" esconde um conceito bastante simples. Suponha que você possui um conjunto de itens e uma série de regras que podem ser usadas para selecionar alguns elementos (itens) desse conjunto. Usando essas regras, há várias maneiras diferentes de escolher os elementos e criar outros conjuntos menores (ou subconjuntos). Se a cada elemento estiver associado um custo, os subconjuntos criados também terão um custo que é dado, por exemplo, pela soma dos custos de seus elementos. O problema de Otimização Combinatória, em geral, se resume a encontrar, dentre todos os possíveis subconjuntos, aquele cujo custo seja o menor possível. Simples, não?

Uma forma de resolver tais problemas seria simplesmente enumerar todas as soluções possíveis e guardar aquela de menor custo. Entretanto, para qualquer problema de um tamanho minimamente interessante (e útil), este método torna-se impraticável, já que o número de soluções possíveis é muito, muito grande. Portanto, técnicas mais apuradas são necessárias.

Um Exemplo

Suponha que você é um carteiro que precisa sair da sua empresa, distribuir cartas pela redondeza e retornar ao seu local de trabalho. É claro que, como o percurso vai ser feito a pé, você vai querer andar a menor distância possível. O seu conjunto de itens, nesse caso, é o conjunto de todas as ruas em que você pode andar. Para construir um subconjunto de ruas, você tem que usar duas regras: (1) Deve ser possível construir um caminho que parte da empresa, passa apenas por ruas do seu subconjunto e retorna à empresa. Isto significa que algumas ruas do subconjunto têm que ter esquinas em comum pois, caso contrário, para passar de uma rua para outra seria preciso utilizar pelo menos uma outra rua que está fora do seu subconjunto; (2) O seu subconjunto de ruas tem que conter, no mínimo, todas as ruas em que devem ser entregues as cartas.

O custo de um subconjunto de ruas é dado pela soma dos comprimentos de cada rua que ele contém. Assim, resolver este problema de Otimização Combinatória equivale a encontrar o menor caminho que o carteiro deve percorrer para completar o seu trabalho.

Aplicações Práticas

Uma infinidade de problemas da vida real podem ser encarados como problemas de Otimização Combinatória. Para que você tenha uma idéia melhor da diversidade de aplicações possíveis, veja a lista de problemas abaixo:

• Corte de Materiais

Uma fábrica de peças de mármore vende peças sob encomenda que são produzidas cortando-se placas grandes em pedaços menores. Uma placa grande pode ser cortada de diversas maneiras e sempre haverá um desperdício de mármore oriundo dos pedaços que sobram após o corte das peças desejadas. Esses pedaços não podem ser aproveitados para produzir peças úteis. O objetivo aqui é descobrir a melhor maneira de cortar as placas grandes de modo que o desperdício seja minimizado. Este é um problema de corte em duas dimensões que também se aplica a vidro, metal, madeira etc. Há problemas de corte em uma dimensão (por exemplo, rolos de papel) e em três dimensões (por exemplo, corte de blocos de espuma para produção de colchões).

• Empacotamento

Os problemas de empacotamento podem ser encarados como o inverso dos problemas de corte. Aqui a idéia é arrumar a melhor maneira de agrupar um conjunto de itens de modo que o espaço total necessário para guardá-los seja minimizado. Em certos casos, o espaço disponível para o armazenamento é predeterminado e o objetivo é guardar o maior número de itens possível. Por exemplo, uma companhia de mudanças deseja encontrar a melhor maneira arrumar os móveis dentro dos seus caminhões de modo a realizar a mudança com um número mínimo de viagens.

• Escalonamento de mão-de-obra

Dado um conjunto de tarefas a realizar e um conjunto de funcionários, um empresário deseja encontrar a melhor maneira de alocar seus funcionários às tarefas de forma que todas as tarefas sejam cumpridas e os gastos com mão-de-obra sejam minimizados. Além disso, há restrições trabalhistas e restrições operacionais da empresa que afetam a forma com que a alocação pode ser feita. Os custos podem estar relacionados com a quantidade de operários envolvidos e/ou com o número de horas-extra que o empresário terá de pagar. Por exemplo, numa companhia aérea, é preciso decidir quais viagens serão destinadas a quais pilotos e ainda obedecer regras do tipo: um piloto não pode trabalhar mais de 8 horas seguidas sem descansar; a cada três dias seguidos de trabalho todo piloto deve ter um dia de descanso etc.

• Escalonamento de tarefas

Em certas fábricas, um produto final é criado a partir da execução de pequenas tarefas. Essas tarefas possuem regras de precedência entre si e particularidades que exigem um ou outro tipo de máquina para sua execução. Com isso, dado um conjunto de itens a produzir, deseja-se descobrir, para cada máquina da fábrica, a ordem em que as tarefas devem ser processadas de forma a minimizar o tempo de produção.

• Localização de Facilidades

Dado um conjunto de clientes que precisam ser atendidos e um conjunto de possíveis locais para instalação de facilidades, deseja-se determinar quais os melhores locais para instalação das facilidades de forma que todos os clientes sejam atendidos a um custo mínimo. Por exemplo, os clientes podem ser um conjunto de casas e as facilidades a instalar podem ser postos de pronto-socorro. O custo pode estar relacionado com a distância das casas ao pronto-socorro mais próximo.

• Distribuição de Bens de Consumo

Dado um conjunto de fregueses que precisam receber mercadorias, a fábrica tem que decidir a quantidade de carga a ser colocada em cada caminhão e quais caminhões irão atender quais clientes. Além disso, é preciso otimizar as rotas dos veículos e, em alguns casos, levar em consideração a eventual necessidade de reabastecimento da carga por parte de alguns caminhões. Por exemplo, os clientes podem ser bares e a fábrica pode ser uma fábrica de bebidas.

• Projeto de Circuitos Integrados

Antes que um circuito integrado seja impresso na placa, é preciso decidir em que lugares serão colocados os chips e por onde passarão as ligações entre os componentes. O objetivo é minimizar os gastos com as ligações entre componentes e também as distâncias entre componentes que se comunicam com maior freqüência.

• Planejamento de Produção

Dado um horizonte de demanda por produtos, um fabricante de determinado item de consumo precisa decidir quanto deve produzir por mês de forma a atender toda a demanda e ainda minimizar os custos. Existe um limite no poder de estocagem e um preço a ser pago por quantidade de produto estocada. Além disso, os produtos podem ter data de validade e atrasos na entrega de mercadoria podem ser tolerados (gerando custo adicional) ou não.

Técnicas Utilizadas

Problemas de Otimização Combinatória precisam ser transformados em modelos concretos para que possam ser resolvidos com o auxílio de computadores. Como já vimos, é preciso aplicar métodos mais inteligentes do que a simples enumeração de todas as possíveis soluções. Atualmente, temos utilizado as seguintes técnicas na resolução de diversos problemas de otimização:

• Programação Linear e Programação Inteira

Essas técnicas já são bastante conhecidas no campo da Otimização, tendo suas origens na década de 40. A Programação Linear consiste em se expressar um problema em termos de variáveis contínuas e um conjunto de restrições lineares sobre essas variáveis. Dada uma função objetivo que descreve basicamente como é calculado o "custo" a ser minimizado, aplica-se um algoritmo (normalmente o Simplex) que resolve o problema de forma eficiente. Na vida real, entretanto, é muito comum que as variáveis precisem assumir valores inteiros e não contínuos. Por exemplo, para resolver um problema em que se precisa decidir quantos empregados serão atribuídos a uma determinada tarefa, gostaríamos de obter como resposta um número inteiro e não 5.78. O que são 5.78 empregados? 5 ou 6? Por incrível que pareça, quando se impõe a restrição de que as variáveis assumam valores inteiros o problema pode ficar muito mais difícil. E a idéia natural de simplesmente arredondar os valores nem sempre traz bons resultados. É aí que entra a Programação Inteira. Ela se baseia fundamentalmente em relaxar, de alguma forma, o problema original e resolvê-lo aos poucos até que se consiga encontrar a melhor solução possível, com o requerimento adicional de que a resposta seja dada em função de números inteiros.

• Programação por Restrições

Técnica mais recente que começou a ganhar força na década de 80. Teve suas origens no campo da Inteligência Artificial, mais especificamente no ramo da Programação Lógica. Em termos simplificados, consiste em um mecanismo de inferência lógica auxiliado por um resolvedor de restrições que são impostas sobre as variáveis do problema em questão. A modelagem dos problemas é facilitada por se tratar de uma linguagem declarativa baseada em implicações lógicas. Restrições complexas podem ser escritas de forma clara e concisa. Tem obtido bastante sucesso em problemas de porte industrial.

• Algoritmos Híbridos

Há problemas em que nem Programação (Linear) Inteira nem Programação por Restrições conseguem obter êxito. Em certos casos, as fraquezas inerentes a cada uma dessas duas técnicas colaboram para que seja muito difícil encontrar uma solução. Desse modo, torna-se necessário que se combinem os pontos fortes de cada uma, criando o que se chamam Algoritmos Híbridos. Tratam-se de algoritmos cooperativos onde Programação Inteira e Programação por Restrições ajudam-se mutuamente. Vários tipos de integrações são possíveis, dando origem a algoritmos bastante interessantes e eficientes.

• Métodos Heurísticos

Nem sempre é possível encontrar a melhor solução de um problema de otimização em tempo razoável. Nesses casos, uma solução relativamente boa pode já ser suficiente para a aplicação que se tem em mãos. Os Métodos Heurísticos são algoritmos que não garantem encontrar a solução ótima de um problema, mas são capazes de retornar uma solução de qualidade em um tempo adequado para as necessidades da aplicação.

• Algoritmos Aproximados

Nos Métodos Heurísticos, não há garantia alguma a respeito da solução encontrada. Isto é, não há como saber se a solução obtida está "perto" ou "longe" da melhor solução possível em termos de qualidade. Contudo, há ocasiões em que essa noção de proximidade faz-se necessária. Por exemplo, eu posso estar interessado em uma solução que não precisa ser a melhor, mas deve ser, no máximo, 10% pior que a melhor solução possível. Nesses casos, entram em ação os Algoritmos Aproximados.

Aprenda Mais

Existem muitos sites na Internet com textos introdutórios sobre Otimização Combinatória e cada uma das técnicas mencionadas acima. Se você deseja ler um pouco mais sobre o assunto, dê uma olhada nos links abaixo:

• Página do Prof. Michael Trick -> um repositório gigantesco de links relacionados a Otimização e Pesquisa Operacional: tutoriais, software, grupos de pesquisa, FAQs, etc.
• e-optimization.com -> um excelente site com diversas informacoes sobre Otimização direcionado para não-experts.

O que você tem a ganhar?

Na sociedade da informação, mais preparado é aquele que possui o conhecimento certo para ser aplicado ao problema certo. Quanto vale um profissional capaz de reduzir os custos de uma empresa em 30% ? Nem é preciso responder, certo? Capacitação profissional é a moeda forte no mercado de trabalho atual. E é isso que nós podemos lhe oferecer.

Dentro do meio acadêmico, não podemos nos esquecer de que o mercado lá fora está mais competitivo a cada dia que passa. Trabalhos de Graduação ou de Iniciação Científica podem ajudar a complementar a sua formação. E se você tem vontade de fazer uma pós-graduação, por que não se especializar em uma área que está em pleno crescimento?

O que as empresas têm a ganhar?

Infelizmente, ainda é pequeno o número de empresas que utilizam em seus processos (sejam eles produtivos ou não) alguma técnica de otimização. Isto se deve, principalmente, a uma falta de conhecimento a respeito do poder real de tais técnicas.

Durante muitos anos, as teorias e métodos desenvolvidos por matemáticos e cientistas foram arquivados em livros e periódicos especializados e muito pouco foi absorvido pelo setor empresarial. Felizmente, contudo, essa situação vem se alterando. É cada vez maior o número de companhias que adotam modelos de otimização no seu dia-a-dia, diminuindo seus custos e, por conseguinte, aumentando os lucros. Além do mais, com a onda crescente de privatizações nos diversos setores da sociedade, a concorrência se fortifica e a sobrevivência dos negócios começa a depender seriamente do desempenho de cada um com relação aos demais. Quem estiver melhor preparado irá, sem dúvida alguma, suplantar os adversários. No Brasil, esse processo vem ganhando força mas ainda é incipiente. Nos demais países, principalmente na Europa e nos Estados Unidos, a utilização de técnicas de otimização dentro das empresas é bem mais difundida, assumindo um papel de grande relevância.

É muito comum que as empresas não tenham consciência de que certas tarefas são passíveis de otimização. Processos de produção altamente ineficientes poderiam ser melhorados significativamente, mas continuam a promover prejuízos que passam despercebidos porque, afinal de contas, "sempre funcionou tão bem assim, não é mesmo?". Ter prejuízo não significa somente terminar o mês com o caixa negativo. Significa também terminar o mês com um "lucro" de R$ 100.000,00 sem se dar conta de que o lucro poderia ter sido de R$ 250.000,00, caso os recursos fossem administrados de forma mais adequada. Esse tipo de comportamento é bastante freqüente, e precisa ser mudado.

Perfil desejado para alunos nesta área:

Afinidade com e gosto por Matemática, Análise de Algoritmos e programação; criatividade, iniciativa, motivação e organização; capacidade de trabalhar em grupo e individualmente.