Formalmente, pesquisa operacional é a busca por um ponto no domínio de uma função de modo a minimizar seu valor.
Problemas de maximizar uma função f(x)
pode ser tratada como minimizar a função g(x) = -f(x)
Você mencionou Programação Linear, isso é bom. Dá um ótimo ponto de entrada. Sem falar que fica fácil explorar alguns dos conceitos mais técnicos.
Programação Linear
Para quem não conhece, a Programação Linear é a disciplina dentro da Pesquisa Operacional que procura o melhor resultado possível de um objetivo dado restrições. Mas não é qualquer função objetiva, nem qualquer restrição, que fazem parte da Programação Linear. Apenas funções lineares são permitidas.
A função objetiva é da forma F(X) = C . X
, onde C
é um vetor de constantes, X
é o vetor de variáveis e C . X
é o produto escalar entre os dois vetores.
As restrições podem ser fornecidas de maneira individual:
A1 . X <= r1
onde A1
é um vetor e r1
é o valor escalar que a multiplicação deve satisfazer. Cada restrição tem sua própria inequação.
Mas também pode ser fornecida na forma de multiplicação de matriz por vetor:
A * X <= r
onde A
é a matriz que tem a quantidade de linhas igual à quantidade de restrições (lembra do vetor A1
? ele é a primeira linha da matriz A
) e r
é o valor máximo de cada restrição.
Quando você tem uma inequação de valor mínimo (restrição na forma Bi . X >= ri
) você pode transformar em valor máximo (para Ai = - Bi
a restrição e equivalente a Ai . X <= -ri
). Se você tem uma igualdade, você pode transformar em duas inequações:
B . X = r
(Idêntico à...)
B . X <= r
B . X >= r
Não lembro como funciona para inequações não inclusivas, como Ai . X < ri
.
Se tivermos apenas duas variáveis, o domínio seria um subconjunto do plano. Cada restrição corta o plano no meio. O domínio da função (considerando as restrições) é a interseção entre todos os semi-planos delimitados pelas restrições.
Por exemplo, com 2 variáveis e 4 variáveis, poderíamos ter esse domínio (marcado em vermelho):
Cada restrição é uma reta no caso de um problema de Programação Linear, as retas pequenas perpendiculares representam qual o semi-plano válido.
No caso das restrições lineares, essa interseção resultante será convexa, ela não terá partes "cavadas". Devido à sua convenxidade, e devido à função objetiva ser linear, a solução vai estar em um dos vértices dessa estrutura convexa. Acontece de ter um espaço solução de mesmo valor objetivo no caso de uma das faces estar perpendicular à direção de crescimento da função objetiva, isso implica que todos os pontos dessa face são ótimos também.
Um dos algoritmos usados em Programação Linear é o Simplex de Dantzig, normalmente referido apenas como método Simplex. Em termos geométricos, ele pegaria o espaço domínio (um hiper-sólido convexo) e, a partir de um vértice, caminha na aresta que provê o melhor resultado da função objetiva (C . ri
mínimo para problemas de minimização, se não me engano) e caminha até o outro vértice dessa aresta, até que chega em um vértice cujas arestas, todas elas, oferecem apenas piora da função objetiva. Isso significa que o algoritmo encontrou um ótimo local (mais sobre isso mais tarde). Como o espaço solução é convexo e a função objetiva é linear, o ótimo local também é ótimo global.
A própria Wikipedia traz um exemplo do "passeio" dos vértices sobre o hiper-sólido domínio:
A propósito, no caso geral, o método Simplex não é polinomial, existem hiper-sólidos construídos especialmente de modo que o Simplex demore um tempo exponencial de processamento. Mas o problema contém algoritmos que o resolvem em tempo polinomial, com estratégias distintas. Um deles é o algoritmo dos elipsóides, navegando pelos pontos interiores do espaço solução.
Programação Linear Inteira
Uma variação da Programação Linear é a Programação Linear Inteira (PLI). Ela é inteira porque a solução precisa estar nos inteiros. Isto é, para todo X
é um vetor de inteiros.
O método Simplex trabalha naturalmente com divisões para fazer as navegações de vértice para vértice, então é de se esperar que seus resultados sejam racionais não inteiros na maior parte das vezes. Mas isso não o impede de ser usado para auxiliar em problemas de PLI.
Uma das estratégias para se encontrar a solução exata é:
- rode o método Simplex e ache a melhor solução racional
- fixe uma das variáveis
- são feitas duas fixações, uma com o valor truncado e outro arredondado para cima
- você pode começar fixando a variável cujo quociente na função objetiva seja mais significativo
- ao fixar uma das variáveis, ela deve ser considerada constante
- rode este mesmo algoritmo novamente, para cada valor fixado distinto determinado no segundo passo
- a recursão chega ao fim quando todas as variáveis estão com valores inteiros fixados
- a resposta é a recursão que chegou no fim com o melhor valor da função objetiva possível
Não vou demonstrar, mas esse algoritmo executa o(2^size(X))
recursões. A versão de decisão dos problemas tratados pela PLI se encaixa em NP, portanto este é um problema muito mais difícil que um problema de Programação Linear.
existem problemas mistos de Programação Linear é PLI, então a solução para esse problema misto é só fazer as fixações para inteiro das variáveis inteiras, da parte PLI do problema
O problema do caixeiro viajante (devidamente mencionado na resposta do @Pagotti) pode ser facilmente convertido em um problema de PLI. Sejam os custos de atravessar da cidade A para a cidade B a função objetiva. Cada aresta constitui uma variável do problema. As restrições são:
cada aresta só pode ser trafegada ou ignorada
seja x_ab
a variável que representa a aresta direcionada de a-->b
, se ela for ignorada, ela vale 0; se ela for trafegada, vale 1; portanto, 0 <= x_ab <= 1
só se pode passar em uma cidade uma única vez, e ela precisa ser visitada (considerando que o caixeiro viajante volte ao ponto original)
somatório de x_ib
para chegar em b
(a partir de uma cidade incidente i
qualquer) tem de ser 1
toda cidade se precise entrar e sair (considerando que o caixeiro viajante volte ao ponto original)
somatório de x_aj
para cidade de destino j
qualquer igual a somatório de x_ia
para cidade de origem i
qualquer, para toda e qualquer cidade a
Programação não Linear
Quando se está em Programação não Linear, existem duas coisas que se devem levar em consideração:
- se a função objetiva é não linear
- se as restrições são não lineares
Também pode existir o caso das restrições serem lineares em um intervalo, mas serem não limitantes em outros, portanto não contínuas. Tanto restrições não lineares típicas como as não lineares por não continuidade podem deixar o espaço solução côncavo.
Restrições não lineares poderiam ocasionalmente gerar espaços soluções de faces que não são pedaços de hiper-planos, mas ainda assim um hiper-sólido convexo. Nesse caso ainda seria possível ir atrás do melhor ponto dessa face para a função objetiva em questão.
Com essas restrições novas e a possibilidade, a possibilidade de concavidade nos traz um problema adicional para ir atrás das soluções: os ótimos locais.
Em um problema de minimização, você pode acabar achando uma solução de tal modo que, ao tentar distanciar-se, você não consiga melhorar a função objetiva. Nesse caso, você está em um vale. Talvez exista algo ainda melhor, mas para isso você teria de "subir a colina" (hill climbing) para verificar.
Tome como exemplo essa função de quarto grau, tirada da Wikipedia:
Imagina que ela é sua função objetiva. Suas restrições são -10 <= x <= 10
. Se você encontrou o mínimo local em torno de +2, você precisaria subir a colina em direção ao 0 para encontrar o outro mínimo local, por volta de -3.
Estratégias para resolver problemas de Programação não Linear devem levar em conta o hill climbing.
É bastante comum atacar esses problemas com heurísticas que trazem respostas boas o suficiente. Uma heurística de hill climbing é a têmpera simulada, que tem uma possibilidade de subir colunas que diminui com a queda da "temperatura" do sistema (essa temperatura por sua vez cai com o passar do tempo).
E, sim, existe a variação inteira desses problemas. E, não, eu não sei como aplicar para atender essa restrição da solução inteira.
Muitos objetivos
Pensou que tinha acabado? Pensou errado!, cara!
Além dos problemas lineares, lineares inteiros e dos não lineares, também temos problemas com múltiplas funções objetivas.
O mais interessante dessas funções com muitos objetivos é que existem soluções codominantes. Eu posso alterar minha solução de tal modo que eu aumento mais os lucros do caixeiro, porém torno a jornada mais demorada (considerando dinheiro como objetivo a maximizar e tempo objetivo a minimizar). Como o computador deveria tratar esses problemas? Qual resposta ele deveria dar? O senso comum diz que deveria ser algo que se assemelhe ao Conjunto de Pareto:
Isso significa que quantos mais pontos que não são objetivamente melhor (em todos os objetivos) entre si obtivermos, melhor será para um gestor escolher uma solução.
Aqui meta-heurísticas capazes de trabalhar com muitos objetivos são usadas para tentar obter esse conjunto resposta:
- MOSA (têmpera simulada multi-objetiva)
- algoritmos genéticos
- formigas (existe uma variação com aranha que come as formigas que tentam fazer hill climbing sem muito sucesso)
- abelhas
Nunca vi (mas isso não quer dizer que não haja) redes neurais artificiais para resolver esses problemas. Também não conheço agentes com aprendizado que retornem um conjunto de Pareto como resposta (vale a mesma observação anterior). Para ambos, só conheço estratégias que retornam uma solução.
Respostas diretas tl;dr
- Pesquisa operacional trata de pesquisar qual a melhor solução para determinada operação (ou melhores soluções)
- Diversos algoritmos podem ser usados, dependendo do problema
- Método Simplex/Método dos elipsóides para problemas de Programação Linear
- Recursão de métodos de Programação Linear com fixação de valores inteiros para Programação Linear Inteira
- Heurísticas e meta-heurísticas para Programação não Linear e para problemas multi-objetivos
- têmpera simulada, formigas, abelhas, algoritmos genéticos, entre outros
- Ela é usada para resolver problemas de otimização, não problemas de decisão
Exemplos
Ok, a resposta está bem abstrata, fala da característica de cada problema (linear, linear inteiro e não linear), algoritmos de resolução, características algébricas dos problemas... mas mostrar um problema que é bom, Jefferson, você não fez, né?
Pois bem, a intenção dessa seção e suas divisões é fornecer exemplos até bater no limite de 30.000 caracteres (ok, exagero meu, não precisa tanto).
PUC-Rio: cadeiras e mesas
Extraído dos slides disponíveis ao público: http://www-di.inf.puc-rio.br/~laber/LP2010-2.pdf
Você ganha 45 dinheiros a cada cadeira vendida, e ganha 80 dinheiros a cada mesa vendida. Você quer maximizar seus lucros. Só botar toda a mão de obra para ficar nas mesas, correto?
Claro que não! Olhando só os lucros por item, eu não posso afirmar isso. Depende do quanto eu tenho disponível para transformar em cadeiras e do quanto eu tenho disponível para transformar em mesas.
No caso, eu tenho dois fatores limitantes:
- tempo, só 450h de trabalho
- tábuas, só tenho 400 no estoque
Para criar uma mesa, gastaria 20 tábuas e 15h. Já para uma cadeira, 5 tábuas e 10h.
Portanto, eu tenho de satisfazer as seguintes condições:
horas de trabalho: 10 * cadeiras + 15 * mesas <= 450
tábuas: 5 * cadeiras + 20 * mesas <= 400
E meu objetivo é maximizar o lucro:
objetivo: max 45 * cadeiras + 80 * mesas
É interessante perceber que 21 mesas está fora do espaço solução porque ultrapassa a minha restrição de tábuas (precisaria de 420 tábuas para 21 mesas). Você pode ver o espaço solução no slide 6 do PDF do material de origem:
Acreditando que a resposta no slide está correta, a resposta ótima é:
cadeiras = 24, mesas = 14
Variação do problema anterior: lenhador
Imagine que você tem exatamente a mesma situação anterior. Mas agora, agora você tem acesso a um lenhador. Ele consegue fornecer novas tábuas para você, consumindo das suas horas de trabalho. Ele também tem um custo para te entregar madeira nova.
Como se dá isso? Bem, sua fábrica de móveis é na Polônia em uma floresta de pinheiros e seus trabalhadores tem essa cara:
No caso, justificamos as horas gastas. E o dinheiro gasto? Seria com o desgaste dos machados de precisão que eles usam para cortar as árvores.
Como eu estou tentando derivar o problema aqui, não vou tentar colocar números adequados para acharmos a reposta. Digamos que cada 3h na floresta gere 50 tábuas ao custo de 10 dinheiros. Isso modificaria a função objetiva e as restrições também. Normalmente, se apresenta primeiro a função objetiva e só então as restrições, então vou apresentar dessa maneira o problema:
max: cadeiras * 45 + mesas * 80 - lenhadores * 10
Restrições:
horas de trabalho: 10 * cadeiras + 15 * mesas + 3 * lenhadores <= 450
tábuas: 5 * cadeiras + 20 * mesas <= 400 + 50 * lenhadores
Eu posso reescrever a restrição de tábuas assim:
5 * cadeiras + 20 * mesas - 50 * lenhadores <= 400
Como usar de lenhadores implica um custo, eu sinceramente não sei nem se vale a pena usá-los. Eu acho que sim, mas não estou com nenhum programa para fazer o cálculo. Note também que agora o espaço solução tem 3 dimensões, portanto seria um sólido geométrico.
Esse é um problema para ser atacado com programação linear. A pergunta linkada no título mostra a versão geral do problema, mais tarde eu coloco aqui uma instância dele para exemplificar.