4 Otimização Combinatoria

Prévia do material em texto

Pesquisa Operacional
Material Teórico
Responsável pelo Conteúdo:
Prof. Esp. Roberto Seraglia Martins 
Revisão Textual:
Prof. Ms. Claudio Brites
Otimização combinatória
• Teoria dos Grafos
• Tipos de grafos
• Árvores, caminhos e emparelhamento
• Fluxos em redes
 · O principal objetivo desta Unidade é conhecer problemas de 
conexão: árvores, caminhos e emparelhamento; problemas de fluxos 
em redes; problemas de roteamento.
OBJETIVO DE APRENDIZADO
Leia atentamente o conteúdo desta Unidade, ele lhe possibilitará 
conhecimentos da otimização combinatória.
Você também encontrará aqui uma atividade composta por questões de múltipla 
escolha, relacionada com o conteúdo estudado. Além disso, terá a oportunidade 
de trocar conhecimentos e debater questões no fórum de discussão.
É extremante importante que você consulte os materiais complementares, 
pois são ricos em informações, possibilitando-lhe o aprofundamento de seus 
estudos sobre esse assunto
ORIENTAÇÕES
Otimização combinatória
UNIDADE Otimização combinatória
Contextualização
Quantas vezes você já se deparou com o problema abaixo?
Combinou com um grupo de amigos para a balada do sábado à noite. No 
seu carro, irão você e mais três amigos. O local é do outro lado da cidade. Você 
deve pensar na ordem em que irá pegar as pessoas para chegar ao local no 
horário combinado.
• Qual o caminho com menor trânsito?
• Quem demora mais para se preparar?
• Como você fará para gastar menos combustível?
E na volta encontra o mesmo dilema.
Seus problemas acabaram, este módulo trará respostas para suas dúvidas, você 
poderá maximizar coisas boas e minimizar seus problemas nesse sentido!
6
7
Teoria dos Grafos
História
Conta-se que a Teoria dos Grafos surgiu em uma cidade da antiga Prússia, hoje 
na atual Rússia. Sete pontes ligavam as partes dessa cidade, que era cortada por 
um rio formando uma ilha na parte central (Figura 1).
Figura 1 – Representação do problema das pontes
Fonte: Acervo do autor
O desafio surgiu, a proposta era fazer um tour pela cidade passando pelas sete 
pontes, sendo que deveria ser uma vez por cada uma delas.
Esse enigma foi trabalhado pelo Matemático Euler, em 1736, que acabou criando 
a teoria que pode ser aplicada em vários problemas dessa natureza (Figura 2).
Euler utilizou um modelo simplificado pela observação das pontes entre as 
regiões, estabelecendo um teorema que apresenta as possibilidades de percorrer 
cada linha uma vez com retorno ao ponto de partida.
Figura 2 – Esquema de Euler para trabalhar o problema
Fonte: Acervo do autor
7
UNIDADE Otimização combinatória
Euler provou que não havia forma de fazer o passeio passando pelas sete pontes 
uma vez apenas.
Figura 3 – Modelo do Problema das Pontes
Fonte: Acervo do autor
• V = (m, onde m é uma margem)
• A = (m1, m2, p, onde p é a ponte que une a margem 1; m1 a margem 2, m2)
Temos os conjuntos
• V = (A, B, C, D)
• A = (A, C, c) (A, C, d) (A, B, a) (A, B, b) (A, D, e) (B, D, f) (C, D, g)
Esquematizando, temos a Figura 4 de um Grafo não orientado, multigrafo 
e conexo:
C
a
d
e
b
f
g
D
C
A
B
Figura 4 – Grafo do Problema
Solução
Partindo de um dos vértices, devemos atravessar todas as arestas de uma única 
vez e finalizar retornando ao vértice de origem.
A solução de Euler consistia em descobrir em que tipos de grafos se pode fazer 
esse caminho, passando por todas as arestas uma única vez. Nasce daí o “Caminho 
de Euler” e o “Grafo de Euler”.
8
9
Teorema
Um grafo conexo pode ser considerado Grafo de Euler se, e somente se, seus 
vértices são de grau par.
Prova
Chega-se a um vértice “entrando” por uma aresta e encontrando outra aresta 
para “sair” e continuar o caminho. Ou seja, duas linhas são necessárias para 
atravessar, uma linha para entrar e outra para sair. Cada vértice tem um par de 
linhas. O Grafo das Pontes não tem solução pois apresenta um número ímpar 
de vértices.
Os carteiros e lixeiros (Figura 5) utilizam-se muito dessa teoria para fazer seu 
trabalho diário sem repetição, ou seja, passando mais de uma vez pela mesma rua 
o mínimo de vezes para não perder tempo, pois esses trabalhadores saem de um 
ponto central e devem retornar para o mesmo.
Figura 5 – Carteiros e lixeiros saem da central e fazem seu percurso 
de entrega ou coleta e devem retornar para o mesmo ponto 
Desse estudo, surge a Teoria dos Grafos.
Tempos depois, houve a aplicação da Teoria dos Grafos nos fluxos de rede e 
então várias são as aplicações dessa teoria na área da Pesquisa Operacional.
Na literatura, encontramos vários casos de sua aplicação:
• Conjuntos de grafos;
• Árvores de extensão;
• Problema do carteiro viajante;
• Coloração de grafos;
• Problema de inspeção de rotas;
• Fluxos de rede.
Podemos utilizar os grafos ainda em redes PERT e CPM no planejamento e 
programação de projetos.
9
UNIDADE Otimização combinatória
Pode ser utilizado em diversas áreas, com a ajuda da teoria algorítmica 
computacional, e chegar a bons resultados. Como se observa, a Teoria de 
Grafos é uma área de pesquisa com vasta aplicabilidade, mas, para a solução 
de modelos complexos, novos resultados precisam ser estudados. Esses 
resultados requerem conhecimentos profundos da Matemática e da Ciência da 
Computação. Alguns exemplos:
• redes de distribuição de energia, telecomunicações;
• malha viária de uma cidade;
• circuitos elétricos;
• processos industriais e processos de negócio.
Grafos
Trocando em miúdos, os grafos são pequenos círculos que representam os 
vértices e arcos que representam por sua vez arestas e conectam as extremidades 
(Figura 5). No caso de grafos direcionados, temos uma seta que indica seu sentido 
na aresta.
1
23
4 5
6
Figura 6 – Representação gráfica ou layout de um Grafo
O grafo representado nesta figura é um grafo simples
Com vértices
V = (1, 2, 3, 4, 5, 6)
E arestas
E = ((1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6))
Quando uma aresta conecta dois vértices, dizemos que os vértices são incidentes 
à aresta em questão.
O número de arestas que incidem nele determina:
• Grau ou valência de um vértice.
10
11
No exemplo,
• o vértice 3 tem grau;
• os vértices 1 e 3 possuem grau 2; e
• os vértices 2, 4 e 5 possuem grau 3.
Caso o conjunto de arestas E seja finito como o exemplo, o grau dos vértices é 
o dobro do número de arestas.
Surge o termo vértice adjacente quando existe uma aresta entre eles. No caso 
acima, são adjacentes os vértices 1 e 2, e não são adjacentes os vértices 2 e 4.
Os conjuntos vizinhos de um vértice são todos os vértices adjacentes a ele. No 
grafo representado acima, o vértice 3 possui 2 vizinhos: vértice 4 e vértice 2. No caso 
dos grafos simples, o número de vizinhos é sempre igual ao seu grau ou valência.
Tipos de grafos
De acordo com a teoria, os tipos de grafos são:
• Grafo simples: é um grafo não direcionado, sem laços e em que existe no 
máximo uma aresta entre quaisquer dois vértices.
No grafo de exemplo, (1, 2, 5, 1, 2, 3), é um caminho com comprimento 5; 
e (5, 2, 1) é um caminho simples de comprimento 2;
• Grafo completo: é o grafo simples em que, para cada vértice do grafo, existe 
uma aresta conectando esse vértice a cada um dos demais (Figura 6), ou seja, 
todos os vértices do grafo possuem mesmo grau.
k1 k2 k3 k4 k5
Figura 7 – Exemplos de grafos completos
• Grafo nulo: é o grafo cujo conjunto de vértices é vazio;
• Grafo vazio: é o grafo cujo conjunto de arestas é vazio;
• Grafo regular: é um grafo em que todos os vértices têm o mesmo grau;
• Multigrafo: é um grafo que permite múltiplas arestas ligando os mesmos 
vértices;
11
UNIDADE Otimização combinatória
• Ciclo (ou circuito): é um caminho que começa eacaba com o mesmo vértice. 
No grafo do exemplo (1, 2, 3, 4, 5, 2, 1), é um ciclo de comprimento 6. Um 
ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o 
vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices 
aparecem só uma vez. No grafo acima (1, 5, 2, 1), é um ciclo simples. Um 
grafo chama-se acíclico se não contém ciclos simples;
• Árvore: é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore 
é distinto e chamado de raiz;
• Floresta: é um conjunto de árvores, equivalentemente a uma floresta, em 
algum grafo acíclico;
• Caminho: é uma sequência de vértices, tal que de cada um dos vértices existe 
uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum 
dos vértices no caminho se repete. O comprimento do caminho é o número de 
arestas que o caminho usa, contando-se arestas múltiplas vezes. O custo de um 
caminho num grafo balanceado é a soma dos custos das arestas atravessadas. 
Dois caminhos são independentes se não tiverem nenhum vértice em comum; 
exceto o primeiro e o último;
• Lema do aperto de mãos: diz que se os convidados de uma festa apertarem 
as mãos quando se encontrarem pela primeira vez, o número de convidados 
que apertam a mão um número ímpar de vezes é par. Também em grafos 
não direcionados, a soma dos graus de todos os vértices é igual ao dobro do 
número de arestas;
• Teorema das quatro cores: é baseado no problema das cores necessárias 
para se colorir um mapa sem que os países vizinhos compartilhem da mesma 
cor. Transformando o mapa em um grafo, pode-se provar que é possível 
representar qualquer mapa (um grafo planar) com apenas 4 cores (4 partições).
Leia mais em: Teoria dos Grafos. Disponível em: http://goo.gl/5FbHVd
Ex
pl
or
Árvores, caminhos e emparelhamento
Os conceitos de grafos são muito importantes para que se entenda o que é uma 
árvore geradora.
• Em um grafo, dizemos que um caminho é a sequência de vértices de modo 
que, com exceção do último vértice, todos eles têm uma aresta que sai dele e 
vai para o próximo;
12
13
• O caminho que possui o primeiro vértice igual ao último, pelo menos 
uma aresta, onde todos os vértices são distintos, é um caminho que forma um 
ciclo simples;
Resumindo: árvore é um gráfico não orientado, conexo e acíclico.
Como toda árvore, a nossa também possui raiz e folhas:
• Nesse caso, a raiz é um nó que é diferente dos outros;
• A folha é um nó sem filhos; e
• A altura da árvore pode ser medida pela quantidade de arestas no caminho 
mais longo entre sua raiz e uma folha.
Figura 8 – Esquema de uma árvore
Chama-se Árvore Geradora
A árvore de um determinado grafo que conecta todos os vértices desse grafo por 
meio de um subconjunto de arestas.
As árvores geradoras são importantes ferramentas pois, a partir de um 
determinado nó, pode-se atingir qualquer outro. Elas têm menos arestas do que o 
grafo inicial e não possuem ciclos. 
As árvores são interessantes para modelar problemas de redes de computadores, 
transmissão de energia, comunicação entre aviões e rodovias.
Exemplo
Uma empresa de televisão a cabo em processo de expansão precisa cobrir 
vários pontos novos em bairros da cidade. A distribuição pode ser feita de várias 
maneiras, inclusive considerando que mais de um cabo chegue ao mesmo lugar. 
Porém, a empresa de televisão a cabo, como toda empresa, precisa viabilizar custos 
e quanto menos cabos utilizar mais irá economizar nos custos.
13
UNIDADE Otimização combinatória
Figura 9 – Conexão de TV a cabo
A Árvore Geradora é grande aliada para resolver esse problema, pois ela garante 
que todos os pontos serão cobertos sem redundâncias, fazendo com que o sinal 
chegue a todos os pontos de interesse da empresa e dos consumidores.
Figura 10 – Grafo de 4 nós
14
15
Observe, na Figura 7, um único grafo de apenas 4 nós possui várias árvores 
geradoras. Temos um grafo com 4 nós e 6 arestas, podemos considerar 26 grafos 
que podem ser obtidos pela remoção de 0 ou mais arestas chegando a 16 árvores 
geradoras possíveis, um quarto do total.
Fluxos em redes
Uma rede de fluxo pode ser definida como um grafo direcionado, onde cada 
aresta tem fluxo e capacidade associados.
Considerando a aresta, o fluxo não pode ultrapassar sua capacidade e deve 
satisfazer a norma da restrição de conservação de fluxo: toda quantidade de fluxo 
que entra, sai.
Respeitando o fato de que de um nó fonte o fluxo só sai e, em um nó sorvedouro, 
o fluxo só chega.
Problemas
Os problemas chamados de fluxo de custo mínimo em redes podem aparecer 
ligados ao transporte ou à distribuição de mercadorias entre locais determinados.
Já os problemas de fluxo máximo podem aparecer na modelagem de planos de 
evacuação de segurança de ambientes.
Nos casos de problemas de transporte, falamos de fluxo de custo mínimo, ou 
seja, atingir a maior quantidade de locais com o menor deslocamento.
Figura 11 – Movimentação de materiais
15
UNIDADE Otimização combinatória
Como exemplo, podemos imaginar o transporte de um material de diversos 
centros de distribuição para outros centros onde há demanda para essa mercadoria.
Seja
• si = mercadoria armazenada na origem i
• dj = demanda no destino j
O objetivo é transportar esse material para os locais desejados a um custo mínimo.
Então
• cij = custo de transporte de uma mercadoria de i para j
E
• xij = número de unidades de mercadoria que vai de i para j
• I e J serão os conjuntos de origem e destino, respectivamente
Então
Minimizar custo, sujeito à quantidade armazenada na origem e à quantidade a 
ser distribuída.
Colocando números
Temos duas origens de mercadorias com 50 e 30 unidades respectivamente e 
quatro destinos com as quantidades procuradas, 20, 10, 30 e 20, respectivamente, 
e com custos designados abaixo:
1 2 3 4
1 5 4 8 9
2 10 1 7 1
O grafo que simboliza esse problema é:
50
30
1 2
1 2 3
4
20 10 30
20
16
17
Colocando em termos de programação linear:
Minimizar
5 x11 + 4 x12 + 8 x13 + 9 x14 + 10 x21 + x22 + 7 x23 + x24
Sujeito a
x11 + x12 + x13 + x14 = 50
x21 + x22 + 7x23 + x24 = 30
x11 + x21 = 20
x12 + x22 = 10
x13 + x23 = 30
x14 + x24 = 20
x11 x12 x13 x14 x21 x22 x23 x24 ≥ 0
Uma solução pode ser dada por
x11 = 20
x13 = 30
x22 = 10
x24 = 20
Problemas de roteamento
Outro problema muito estudado no tema de otimização combinatória é o 
Problema de Roteamento de Veículos – PRV.
Esse estudo (Figura 9) visa atender um conjunto de consumidores por meio de 
uma frota de veículos que se deslocam a partir de um ou mais depósitos.
Depot
Figura 12 – Demonstrativo de PRV
17
UNIDADE Otimização combinatória
A grande restrição do PRV é que cada veículo denominado v possui uma 
determinada capacidade Cv e a soma de todas as demandas detectadas pelos 
consumidores que são atendidos por um determinado veículo v não pode ser maior 
do que Cv.
O PRV apresenta alta complexidade de resolução contando com a ferramenta 
computacional como poderosa aliada nos métodos de resolução.
A função objetivo, como sempre, está intimamente ligada às características do 
problema:
• Operadores logísticos;
• Transportes especiais;
• Distribuidores de refrigerados.
Dentre eles, podemos enumerar a minimização de:
• Tempo de corrida;
• Distância percorrida;
• Custo operacional;
• Tempo de espera.
Com maximização de:
• Benefícios;
• Qualidade;
• Fidelização;
• Sustentabilidade.
Procure exemplos, aplicações no seu dia a dia!
18
19
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Introdução à pesquisa operacional: método e modelos para análise de decisões
ANDRADE, Eduardo Leopoldino de. Introdução à pesquisa operacional: métodoe 
modelos para análise de decisões. 5. ed. Rio de Janeiro: LTC, 2015.
Introdução à pesquisa operacional
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à pesquisa operacional. 
9. ed. Porto Alegre: AMGH, 2013.
Introdução à pesquisa operacional
LONGARAY, André Andrade. Introdução à pesquisa operacional. São Paulo: 
Saraiva, 2013.
 Leitura
Desenvolvimento e otimização de modelos matemáticos por meio da linguagem
SILVA, A, F. DA; MARINS, F. A. S.; SILVA, G. M.; LOPES, P.R. M. DE A. 
Desenvolvimento e otimização de modelos matemáticos por meio da linguagem. 
São Paulo: GAMS, 2011.
http://goo.gl/TIgLwL
19
UNIDADE Otimização combinatória
Referências
ANDERSON, D. R.; SWEENEY, D. J.; WILLIAMS, T. A. An Introduction to 
Management Science. 9. ed. South-Western College Publishing, 2000.
ANDRADE, E.; FURST, P.; RODRIGUES, P. C. P. Elementos de programação 
linear. Rio de Janeiro: Editora Universidade Rural, 1998. 
ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa 
operacional para cursos de engenharia: modelagem e algoritmos. Rio de 
Janeiro: Campus, 2007.
GOLDBARG, M. C.; LUNA, H. P. Otimização combinatória e programação 
linear: modelos e algoritmos. Rio de Janeiro: Campus, 2000.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 8. ed. 
São Paulo: McGraw-Hill, 2006.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisão 
(modelagem em Excel). 3. ed. Rio de Janeiro: Campus, 2007.
LUNA, H. P.; GOLDBARG, M. C. Otimização combinatória e programação linear. 
2. ed. Rio de Janeiro: Campus, 2005.
TAHA, H. A. Pesquisa Operacional. 8. ed. São Paulo: Pearson/Prentice Hall, 2008.
20