4

Na matéria de Programação Linear da minha faculdade, o professor cita um termo chamado Pesquisa Operacional no qual usa certos algoritmos para solucionar determinados tipos de problemas. No entanto, eu fiquei muito confuso a respeito do que é a Pesquisa Operacional e o que ela propõe no contexto da computação e gostaria de ter minhas dúvidas esclarecidas.

Dúvidas

  1. O que é Pesquisa Operacional no contexto da computação?
  2. Quais tipos de algoritmos são usados?
  3. Quais são os problemas que esses algoritmos propõe-se a resolver?
2
  • 2
    (1) otimização (2) buscas (3) problemas de contagem/otimização ; depois eu elaboro uma resposta completa Commented 22/02/2018 às 11:40
  • 1
    Não sabia que tinha diferença na computação :P
    – Maniero
    Commented 22/02/2018 às 12:14

2 Respostas 2

4

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):

espaço domínio

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:

caminhando sobre os vértices de um domínio em 3D

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 é:

  1. rode o método Simplex e ache a melhor solução racional
  2. 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
  3. ao fixar uma das variáveis, ela deve ser considerada constante
  4. rode este mesmo algoritmo novamente, para cada valor fixado distinto determinado no segundo passo
  5. a recursão chega ao fim quando todas as variáveis estão com valores inteiros fixados
  6. 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:

função de quarto grau com dois mínimos locais

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:

conjunto de Pareto extraído da Wikipedia

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

  1. Pesquisa operacional trata de pesquisar qual a melhor solução para determinada operação (ou melhores soluções)
  2. 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
  3. 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:

espaço solução e resposta ótima

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:

timberman ou lenhador

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.

Alocando funcionários a máquinas

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.

5
  • Eu ainda tenho uma dificuldade em relação de como identificar problemas que podem ser solucionados pela programação linear, tipo como saber se um determinado problema é linear?
    – gato
    Commented 1/03/2018 às 10:47
  • @gato você precisa considerar o problema em uma abordagem "orientada a restrições". Posso elaborar um caso concreto do alfaiate, em que ele tem alguns poucos metros quadrados de linho, algodão e seda e precisa fazer ternos e vestidos, sendo que terno consome 2 metros quadrados de linho e vestido 2 metros quadrados de seda, se vende terno com um lucro de 200 dinheiros, e vestido com lucro de 300 dinheiros. A pergunta é como otimizar a produção de modo que se obtenha lucro máximo. Commented 1/03/2018 às 10:55
  • Ah, @gato , se ficou meio confuso é porque não consegui elaborar direito no comentário, em breve virá uma atualização de resposta bem bonita ;-) Commented 1/03/2018 às 10:56
  • A propósito, se não tiver pelo menos um grau de liberdade nas restrições, então ou é impossível ou é resolver um sistema de inequações lineares que só permitirá uma única reposta, tornando o problema independente da função objetiva Commented 1/03/2018 às 11:07
  • Hum entendi, não se preocupe :) Hoje na faculdade eu dei uma pesquisada, e vi que é um pouco amplo mais estou entendendo mais. Futuramente irei fazer mais perguntas a respeito, e focada numa implementação especifica de linear e problemas.
    – gato
    Commented 1/03/2018 às 17:18
3

Em resumo resumido

Pesquisa Operacional (P.O.) é uma área da matemática aplicada que basicamente tentar solucionar problemas relacionado a otimização através da busca de soluções de equações de máximo (maior lucro, maior desempenho) e mínimo (mínimo custo, menor caminho). É usada muito em problemas logísticos e financeiros e ajuda no processo de tomada de decisão nas empresas.

Um exemplo clássico é do mascate ou caixeiro-viajante: A partir de uma mapa, com vários clientes em locais distintos e várias estradas diferentes, com distâncias diferentes, ligando esses pontos, determinar qual o melhor caminho (otimização) que o mascate pode fazer de forma a ter o menor custo possível, considerando as condições das estradas, pedágios, etc., de forma a maximizar o seu lucro.

Outro exemplos seria o prolema de alocação de professores em salas de aula. Dado um conjunto de turmas, disciplinas e agenda dos professores na semana, determinar qual a melhor disposição das aulas na semana de forma a minimizar a quantidade de vezes que o professor vem para a escola. Ou a melhor disposição de forma a utilizar melhor as salas de aula.

A computação entra com a adaptação das equações e métodos matemático em forma de algoritmos para resolver esses problemas. A computação também colabora com tipos de algorítimos numéricos/genéticos que seriam impraticáveis para se resolver com lápis e papel.

Como exemplo de aplicação na computação, existe uma lib do Python chamada PuLP que pode ser utilizada na solução dos problemas. Nessa página e nessa outra podem ser encontrados exemplos de aplicação da lib.

Se quiser algo divertido eu sugiro esse post no blog do Ricardo Bittencourt que tem a ver com PO.

A Programação Linear é a disciplina que aborda as técnicas para resolver alguns problemas de P.O. que normalmente são modelados através de uma equações onde se deseja encontrar o valor máximo ou mínimo e outro conjunto de inequações que informam as restrições que devem ser consideradas. No meu curso a disciplina era chamada de P.O. mesmo, mas varia em cada instituição. O termo "Linear" se deve ao fato dessas inequações serem todas lineares, ou seja, polinomiais de grau 1.

7
  • E os algoritmos? Você exemplificou mais a pesquisa operacional em si como disciplina ao invés da computação. Commented 22/02/2018 às 12:35
  • A parte da computação é transformar as soluções matemáticas em programas como disse no quarto parágrafo. Você diz para eu citar o nome dos algorítimos ou colocar algum código de exemplo?
    – Pagotti
    Commented 22/02/2018 às 12:55
  • Você cita o problema do caixeiro viajante, mas não cita onde a pesquisa operacional tenta resolver isso. Exemplo seria comparar um algoritmo de dijkstra contra um algoritmo A*. No A* eu utilizo dijkstra como heurística junto a outro algoritmo. Commented 22/02/2018 às 12:58
  • @GabrielColetta existem diversos e incontáveis algoritmos de pesquisa operacional. A* é uma busca. Simplex é outra busca. Tem o método das elipses que também é usado em Programação Linear. Colônia de formigas, abelhas, têmpera simulada, algoritmos genéticos também Commented 22/02/2018 às 13:20
  • @JeffersonQuesado Estou ciente disso, mas a pergunta gostaria de exemplos de algoritmos, o que eu fiz foi exemplificar um caso de algoritmo que tenta resolver o problema do caixeiro viajante. Commented 22/02/2018 às 13:33

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .