Upload
lamngoc
View
215
Download
0
Embed Size (px)
Citation preview
.
EFICIÊNCIA POLINOMIAL DO MÉTODO SIMPLEX PARA REDES:
ANALISE SOBRE UM PROBLEMA DE CAMINHO MAIS CURTO
(PCMC)
CARLOS EDUARDO VAREJÃO MARINHO
UNIVERSIDADE ESTADUAL DO NORTE FLUMINENSE – UENF
CAMPOS DOS GOYTACAZES, RJ
SETEMBRO 2001
ii
EFICIÊNCIA POLINOMIAL DO MÉTODO SIMPLEX PARA REDES:
ANALISE SOBRE UM PROBLEMA DE CAMINHO MAIS CURTO
(PCMC)
CARLOS EDUARDO VAREJÃO MARINHO
Dissertação submetida ao corpo docente do
Centro de Ciência e Tecnologia da
Universidade Estadual do Norte Fluminense,
como parte das exigências necessárias para
obtenção do grau de mestre em ciências de
engenharia, na área de concentração de
engenharia de produção.
ORIENTADOR: Profa. Gudelia Morales, D. Sc
CAMPOS DOS GOYTACAZES, RJ
SETEMBRO 2001
iii
EFICIÊNCIA POLINOMIAL DO MÉTODO SIMPLEX PARA REDES:
ANALISE SOBRE UM PROBLEMA DE CAMINHO MAIS CURTO
(PCMC)
CARLOS EDUARDO VAREJÃO MARINHO
Dissertação submetida ao corpo docente do
Centro de Ciência e Tecnologia da
Universidade Estadual do Norte Fluminense,
como parte das exigências necessárias para
obtenção do grau de Mestre em Ciências de
Engenharia, na área de concentração de
Engenharia de Produção.
Aprovada em 05 de setembro de 2001
Comissão Examinadora:
___________________________________________________________
Prof. Gudelia Morales, D. Sc – UENF
Presidente
____________________________________________________________
Prof. Carlos Martinhon, D. Sc - UFF.
____________________________________________________________
Prof. José Arica, D. Sc - UENF.
____________________________________________________________
Prof. Geraldo G. de Paula, D. Sc - UENF.
v
Somos vítimas de um movimento de curso cego onde a racionalidade humana
societária perde-se no mar infinito das vontades e forças individuais de ação
que produzem os fatos do dia a dia. Que paradoxo! Tudo o que ocorre na
sociedade, aceite-se a redundância, é social, porque é produzido pelos
homens; mas esses mesmos homens não se reconhecem necessariamente
nos resultados de sua produção.
(Transcrito de uma folha de um livro onde não foi possível identificar, o nome do livro nem o autor).
vi
AGRADECIMENTOS
Meus sinceros agradecimentos a todos que de algum modo contribuíram para
a realização deste trabalho, em particular:
A minha mãe por ter primado pela minha educação e ter me incutido a
necessidade de ser perseverante - Não chore! Levanta para cair de novo.
Ao meu pai, a minha irmã Dulce e ao meu irmão Alexandre a quem, mesmo
não estando mais nesta vida, tenho uma gratidão eterna.
Aos meus irmãos Vera Lúcia, Frederico Augusto, Tereza Cristina, Francisco
José, Ana Maria, Marco Antônio, Helena Regina e aos meus irmãos de coração
Luís, Sérgio, Zélia e Leila por todo o apoio e incentivo recebido.
A Andréa Cristina, Úrsula Luize, Alessandra Karina, Anna Christianna,
Ludmila, Lígia, Leonardo, Maria Clara, João Pedro, Luís Felipe, João Gabriel, Luís
Guilherme e Caio Marcelo, por engrandecerem o nosso Brasil.
Ao tio Lula (Engo Luiz Ribeiro Varejão) por todo o seu incentivo durante a
minha formação educacional, do primário à universidade.
Aos amigos Lúcia e Ronaldo da Pousada dos Coqueiros pela impagável
acolhida nos primeiros meses na Região.
A FENORTE pelo apoio financeiro fornecido durante a execução deste
trabalho.
A minha orientadora Gudelia pela paciência e objetividade com que conduziu
este trabalho.
Aos professores Hélder, Arica, Clevi, Daniel, Renato, Galdino e Gudelia pela
diversidade de conhecimentos transmitidos durante o curso de mestrado.
Aos membros da comissão examinadora, Prof. Dr. Carlos Martinhon, Prof. Dr.
José Arica e Prof. Dr. Geraldo G. de Paula, por emprestarem seu prestígio a este
trabalho e pelas sábias sugestões que muito contribuíram para aprimorá-lo, e ao
Prof. M Sc Francisco José Varejão Marinho (UFF), pelo seu conhecimento e apoio
na área computacional.
Ao amigo Alexandre Favarin. O Brasil precisa de suas idéias.
Aos amigos Luiz Guillermo, Pedro Canales, Alexandre Favarin e Maurício
Leite pelo hábito da discussão sobre assuntos diversos, relevantes ou não, na Sala
vii
de Estudo do LEPROD (sala 208). Foi uma agradável experiência acadêmica; ou, a
mais acadêmica das experiências.
A todos os funcionários do CCT, e, em especial, a Mariinha, Néia e Alice, pelo
espírito de cooperação.
Ao amigo Antônio José dos Santos Neto, colega do mestrado, pelo arrojo
demonstrado na implementação do software Simplex Acelerado. Muito obrigado.
viii
SUMÁRIO
Página
LISTA DE FIGURAS ........................................................................................... viii
SIMBOLOGIA E DEFINIÇÕES ........................................................................... ix
RESUMO ............................................................................................................ X
ABSTRACT ......................................................................................................... Xi
CAPÍTULO 1
INTRODUÇÃO............................................................................................. 1
1.1 Algoritmo ..................................................................................................... 1
1.2 O Problema de Caminho mais Curto (PCMC) ............................................ 3
1.3 Problema de Fluxo de Custo Mínimo .......................................................... 4
1.3.1 Formulação do Problema de Fluxo de Custo Mínimo.......................... 4
1.3.2 Formulação do Modelo de Fluxos para o Problema de Caminho mais
Curto de um Nó para outro Nó da Rede .............................................
5
1.3.3 Formulação do PCMC como um Problema de Fluxo de Custo
Mínimo ................................................................................................
6
1.4 Estado da Arte ............................................................................................ 6
1.5 Objetivo ....................................................................................................... 7
CAPÍTULO 2
TÓPICOS DE TEORIA DE COMPLEXIDADE DE ALGORITMOS ............. 9
2.1 A Resolução Computacional de um Problema ............................................ 9
2.2 Análise de Complexidade
............................................................................
12
2.2.1 Medidas de Complexidade ................................................................. 12
2.2.2 Tamanho do Problema ....................................................................... 15
2.2.3 Complexidade do Pior-Caso ............................................................... 16
2.2.4 Classificação de Funções pela Taxas de Crescimento Definições e
Notações ............................................................................................
16
2.2.5 Notação O grande .............................................................................. 17
2.2.6 Tempo de Execução de um Algoritmo ................................................ 18
2.2.7 Suposição de Similaridade ................................................................. 21
2.2.8 Algoritmos Polinomial e Exponencial .................................................. 21
CAPÍTULO 3
ix
ASPECTOS CLÁSSICOS DO PROBLEMA DE CAMINHO MAIS CURTO .... 25
3.1 O Método BFM ............................................................................................ 25
3.2 O Método Simplex para Redes aplicado ao PCMC .................................... 27
3.2.1 Adaptação do PFCM para o PCMC .................................................... 28
3.2.2 Regras de Pivoteamentos .................................................................. 34
. Regra de Pivoteamento do Primeiro Arco Elegível ............................ 34
Regra de Pivoteamento de Dantzig .................................................... 35
Regra de Pivoteamento Escalonado .................................................. 35
3.3 Representação Clássica em Pseudocódigo dp ASR .................................. 36
CAPÍTULO 4 37
UMA INOVAÇÃO PARA O PCMC – O SIMPLEX ACELERADO ................ 37
4.1 Descrição do Método Simplex Acelerado ................................................... 37
4.2 Representação do Método .......................................................................... 40
4.3 Propriedades do Método ............................................................................. 41
4.4 Cálculo do Número de Pivoteamentos ....................................................... 42
4.5 Cálculo da Complexidade do Método ......................................................... 42
4.6 O algoritmo Simplex Acelerado .................................................................. 43
4.7 Aplicação Numérica do Método .................................................................. 44
4.8 Implementação do Método Simplex Acelerado .......................................... 48
Descrição das Rotinas que Armazenam uma Árvore ............................ 50
Exemplo Ilustrando à Implementação...................................................
53
CONCLUSÃO ............................................................................................. 55
REFERÊNCIAS BIBLIOGRÄFICAS ........................................................... 1
APÊNDICE ΙΙΙΙ
TÓPICOS DE TEORIA DE REDES ............................................................ 4
Ι.1 O Problema de Fluxo de Custo Mínimo ...................................................... 4
Ι.2 Definições e Terminologia da Teoria de Grafos ......................................... 5
Ι.3 Representação de Um Grafo ...................................................................... 10
Ι.3.1 Matriz de Adjacência .......................................................................... 11
Ι.3.2 Matriz de Incidência Nó-Arco 11
x
..............................................................
Ι.4 Vetor Árvore ................................................................................................ 11
Ι.5 Propriedades das Árvores .......................................................................... 11
Ι.6 Posto de uma Matriz de Incidência Nó-Arco ............................................... 12
Ι.7
Representação Vetorial de um Arco Não Básico em Função dos Arcos
Básicos .......................................................................................................
15
Ι.8
Cálculo dos Custos Reduzidos no Problema de Fluxos em Redes ............ 16
APÊNDICE ΙΙΙΙΙΙΙΙ
PROGRAMA EM PASCAL DO MÉTODO BFM ......................................... 18
APÊNDICE ΙΙΙΙΙΙΙΙΙΙΙΙ
PROGRAMA EM PASCAL DO MÉTODO SIMPLEX ACELERADO .......... 23
xi
LISTA DE FIGURAS
Figura 2.1 - Modelo RAM. Fonte: Campello (1994)
Figura 3.1 - Árvore fornecedora (os fluxos consumidos nos arcos). Fonte:
Ahuja (1993)
Figura 3.2 - Potência dos nós. Fonte: Ahuja (1993)
Figura 3.3 - Seleção do arco candidato para entrar e sair da árvore. Fonte:
Ahuja (1993)
Figura 3.4 - Ciclo negativo. Fonte: Ahuja (1993)
Figura 4.1 - Fluxograma do Método Simplex Acelerado.
Figura 4.2 - Grafo. Exemplo. Fonte: Taha (1997)
Figura 4.3 - Árvore inicial (T 0), com os pré-multiplicadores (π).
Figura 4.4 - Árvore melhorada (T1), como os novos pré-multiplicadores.
Figura 4.5 - Árvore T2, com a indicação dos novos pré-multiplicadores.
Figura 4.6 - Árvore T3 com os novos pré-multiplicadores.
Figura 4.7 - Armazenamento da topologia de uma árvore binária.
Figura 4.8 - Novo estrutura de armazenamento em caso de árvores gerais.
Figura 4.9 - Implementação considerando estruturas binárias.
Figura 4.10 - Topologia da árvore exemplo.
Figura 4.11 - A pilha.
Figura 4.12 - Critério de percurso e armazenamento.
Figura Ι.1 - Exemplo de uma rede.
Figura Ι.2 - Exemplo de árvore geradora do grafo I-1, com a introdução do
arco (1,2). Fonte: Bazaraa (1990).
Figura Ι.3 - Cálculo dos valores das variáveis básicas (fluxo). Fonte: Bazaraa
(1990).
Figura Ι.4 - Calculo dos valores das variáveis duais. Fonte: Bazaraa (1990).
xii
SIMBOLOGIA E DEFINIÇÕES
ijc - Custo (generalizado) do arco (i, j)
π (i) - Representa a potência no nó i, também chamado de multiplicadores e/ou
pré-multiplicadores.
πijc - Custo reduzido
G(N,A) - Representação matemática de um grafo, onde N é o conjunto dos nós e A
é o conjunto dos arcos respectivamente.
T - Árvore geradora. O conjunto dos arcos básicos que compõem a solução
do PCMC.
L - Conjunto dos arcos não básicos com fluxos no limite inferior.
ASR - Algoritmo Simplex para Redes.
PCMC - Problema de Caminho mais Curto.
PFCM - Problema de Fluxo de Custo Mínimo.
xiii
Resumo da dissertação apresentada ao CCT/UENF como parte das exigências para
obtenção do grau de Mestre em Ciências (M.Sc.) em Engenharia de Produção.
RESUMO
EFICIÊNCIA POLINOMIAL DO MÉTODO SIMPLEX PARA REDES: ANALISE
SOBRE UM PROBLEMA DE CAMINHO MAIS CURTO (PCMC)
Carlos Eduardo Varejão Marinho
Setembro – 2001
Orientador: Professora Gudelia Morales
Curso de Mestrado em Ciências de Engenharia de Produção.
Este trabalho trata de um estudo comparativo, entre algoritmos que resolvem o
problema de caminho mais curto para encontrar a menor distancia de um nó para
qualquer outro nó de um grafo, através de uma análise de complexidade
computacional.
Usando uma formulação de uma distribuição de fluxos sobre um grafo, representa-
se o problema do caminho mais curto (PCMC) de um nó para todos os outros nós
de uma rede. Com essa formulação se faz um estudo para mostrar a equivalência
entre as complexidades dos métodos propostos por (Goldfarb et al., 1999) e o
Bellman-Ford-Moore (Bellman, 1958; Ford, 1956 e Moore, 1957), que resolvem o
problema.
O objetivo do trabalho é mostrar que não existe mais diferença entre as
complexidades dos algoritmos Bellman-Ford-Moore e o método simplex que
resolvem o PCMC. Embora a literatura mostre que o método simplex, no pior caso,
apresente um desempenho computacional exponencial, em problemas de redes,
este tem um bom desempenho.
xiv
Submitted to the CCT/UENF in partial fulfillment of the requirements for the degree
of Master of Sciences.
ABSTRACT
Carlos Eduardo Varejão Marinho
September – 2001
Advisor: Gudelia Morales
Department: Science of Engineering Production
This work deals with a comparative study between some of the algorithms that solve
the shortest path problem to find the minimal distance of a node to any another
node, in a network, analyzing yours computational complexity.
With a formulation of fluxes distribution on the graph present a shortest path problem
(SPP) of a node to another in the network. With this formulation we make a study to
show the equivalence between the complexities of methods propose by (Goldfarb et
al., 1999) and Beellman-Ford-Moore (Bellman, 1958; Moore, 1957 e Ford, 1956))
that solve the SPP.
The work target is to show that there is not more difference between the complexities
of the methods Bellman-Ford-Moore and the simplex that solve the SPP. Although
the literature shows the simplex, in the worst case, an exponential performance in
network problems, it has a good performance.
1
CAPÍTULO 1
“Tudo que se resolve com dinheiro é barato”.
INTRODUÇÃO
Este capítulo discorre sobre algoritmos que resolvem o problema de caminho
mais curto, as adaptações e implementações apresentadas até o momento, que
melhoram a complexidade dos métodos propostos para resolver o problema de
caminho mais curto de um nó para todos os outros nós de uma rede. Apresenta-se
uma nova visão para o estudo de algoritmos, bem como o estado da arte do
problema em estudo.
1.1-Algoritmo
A Enciclopédia e Dicionário Ilustrado, (Edições Delta), definem algoritmo
(termo matemático) como uma seqüência de raciocínios ou operações que oferece a
solução de certos problemas. A execução de um algoritmo não deve incluir decisões
subjetivas ou o uso da intuição e criatividade. Quando se utiliza essa palavra, em
“estrito senso”, se esta pensando em termos computacionais. (Cormen et al.,1990)
definem algoritmo como uma seqüência bem-definida de procedimentos
computacionais (passos) que levam uma entrada de dados a ser transformada em
uma saída. A idéia de associar o conceito de algoritmo ao fenômeno do
processamento de uma entrada traduzível em termos computacionais, implica a
necessidade da definição formal de um alfabeto para a codificação dessa
entrada/saída, bem como as estruturas de transformação. Segundo (Goldbarg e
Luna, 2000), algoritmo é uma espécie de função de processamento sobre o alfabeto
de entrada e saída, e, neste caso, pode-se dizer que um algoritmo é a descrição do
cálculo ou avaliação sistemática dessa função.
A verificação do desempenho de um algoritmo é um dos pontos mais
importantes dentro do tema complexidade de algoritmos. Muitas vezes um algoritmo
é capaz de solucionar somente um certo conjunto de casos de um problema. Esses
casos específicos são denominados instâncias do problema.
2
Para se garantir a eficiência de um algoritmo na solução de um certo
problema é necessário que se possa garantir sua eficiência em todas as instâncias
possíveis do mesmo. Basta a exibição de um caso de fracasso para se demonstrar
a sua ineficácia. Por outro lado, para provar seu acerto serão necessárias
providências árduas. Uma forma de reduzir a dificuldade da prova de correção de
um algoritmo é o estabelecimento de domínios de definição, ou seja, regiões ou
limites onde se pode garantir que as instâncias são solucionadas corretamente.
A eficiência de um algoritmo está relacionada ao objetivo de se encontrar
uma solução rápida e econômica do problema. O termo rapidez diz respeito à
aplicação prática do algoritmo. O termo econômico responde pela realidade dos
recursos humanos ou computacionais disponíveis. A análise de um algoritmo
significa predizer os recursos que o algoritmo irá requerer. Como recursos entende-
se: a memória, o tempo de processamento, a natureza das operações etc.
Em resumo, pode-se dizer que entender “bem” um algoritmo, que resolve
uma diversidade de problemas é tão importante quanto desenvolver um novo
algoritmo para resolver um problema ainda não estruturado. Entender um algoritmo
é interpretá-lo com uma linguagem simples; é saber estruturar os dados de entrada
e os dados de saída que minimize o espaço de memória ocupado pelos dados e o
tempo de máquina, é conhecer a sua complexidade, o funcionamento de cada
decisão, as estruturas de repetição, de cada passo de um contador, do processo de
início e de parada etc. Na ciência da computação, esse entendimento gera novas
propostas que melhoram a eficiência de um algoritmo. Por exemplo, quando se
reduz o tempo da execução computacional do algoritmo ou, quando se otimiza o
espaço de memória para o armazenamento dos dados de entrada e saída do
problema.
No presente trabalho estuda-se o problema do caminho mais curto (PCMC)
formulado como um problema de fluxos em redes, resolvido através do algoritmo
simplex para redes. O PCMC é um dos assuntos mais estudado pelos
pesquisadores devido à gama de aplicações nas diversas áreas de conhecimento,
como: o estudo das relações de liderança numa sociedade generalizada; nos
estudos de árvore de falhas de plantas industriais, no planejamento de atividades
3
(PERT/CPM) e é um problema fundamental na área de transportes, seja na área de
planejamento viário do sistema urbano ou do sistema Interurbano, seja na área de
controle de tráfego.
Por exemplo: o binômio “sinal+guarda de trânsito” para controle de tráfego
nas grandes cidades tornou-se um sistema ineficiente e ineficaz. Hoje, nessas
cidades, o controle do sistema viário, exige não só o controle do fluxo, como
também o fornecimento de informações ao motorista, principalmente durante os
congestionamentos, com indicações de caminhos alternativos, em tempo real, para
os diversos destinos de interesse do motorista, e o tempo estimado de cada
percurso proposto. Para essa modernização há a necessidade do desenvolvimento
de softwares eficientes e eficazes capazes de manipular centenas ou milhares de
variáveis e de fornecer informações precisas para auxiliar o motorista na tomada de
decisão.
1.2- O Problema de Caminho mais Curto (PCMC)
O PCMC é o primeiro problema quando se pensa em resolver problemas de
trânsito numa cidade, pois o seu custo generalizado, permite com apenas um
algoritmo, resolver não só o problema da distância mais curta, como também o
problema de tempo mínimo. (Ver o site do Departamento Nacional de Estradas de
Rodagem (DNER)).
(Dijkstra, 1957), foi um dos primeiros pesquisadores a tratar do problema ao
apresentar um método para encontrar a menor distância entre dois pontos
específicos numa rede. Dijkstra denominou esses pontos de interesse como: origem
(s) e destino (t). Este método é bastante estudado na área de transportes visto que,
em qualquer ponto em que o motorista estiver, dentro da malha viária, esse ponto
pode ser considerado como a origem; e o objetivo imediato desse motorista é
chegar em algum outro ponto, que possa ser considerado destino. Ele permite a
redução da distância entre origem e destino pela seleção do caminho entre as várias
alternativas de tempo e distância à disposição do motorista.
4
Paralelamente a Dijkstra, outros pesquisadores trataram do mesmo assunto,
destacando-se (Bellman, 1958), (Ford, 1957) e (Moore, 1958) que generalizaram o
método, inclusive, para trabalhar até com distâncias negativas. O método de
Bellman-Ford-Moore, que neste trabalho é identificado como método BFM ou
simplesmente BFM, tem grande aplicação quando se deseja encontrar o caminho
mais curto entre um nó específico, chamado fornecedor, para todos os outros nós
de uma rede, chamados demandantes. Este método é estudado com profundidade
neste trabalho.
Neste estudo será enfocado o PCMC como uma instância do problema de
fluxo de custo mínimo (PFCM) e, assim, poder avaliar o método simplex primal
desenvolvido por (Goldfarb et al., 1999) para resolver o PCMC. Esse método para
resolver o problema do caminho mais curto de um nó para todos os nós de um grafo
apresenta uma complexidade fortemente polinomial e será motivo de comparação
com os métodos heurísticos que tratam do mesmo problema e que apresentam,
também, uma complexidade polinomial.
1.3 - Problema do Fluxo de Custo Mínimo
O modelo do fluxo de custo mínimo é considerado o mais importante entre
todos os problemas de fluxos em rede. Este modelo trata do problema de
distribuição de um produto através de uma rede, satisfazendo a demanda em
determinados nós, e a oferta em outros, com o menor custo possível. O modelo tem
um grande número de aplicações, como: na distribuição de um produto das plantas
de produção para os armazéns, e destes, para o mercado varejista; no fluxo de
material (matéria prima) e produtos intermediários através das estações numa linha
de produção; no roteamento de automóveis através da malha urbana; no
roteamento de chamadas através do sistema telefônico, etc.
5
1.3.1 - Formulação do Problema do Fluxo de Custo Mínimo (PFCM)
Uma formulação do PFCM usando a Teoria de Redes é a seguinte:
Seja G (N, A) um grafo orientado, onde N representa um conjunto de n nós, e
A o conjunto de m arcos. A cada arco (i, j) ∈ A é atribuído um número cij,, que indica
o custo de transporte de uma unidade de fluxo naquele arco e um número uij, que
indica a capacidade máxima do fluxo permitido no arco e lij a capacidade mínima.
Adicionalmente, a cada nó i∈ N é atribuído um número inteiro b(i): se b(i) > 0, o nó é
fornecedor de fluxo; se b(i)< 0, o nó é de demanda e, se b(i)=0, o nó é de
transbordo. Os números xij representam no PFCM os fluxos nos arcos.
A formulação do problema do PFCM como um problema de Programação
Linear é:
Min cx
s.a Ax = b
l≤≤≤≤ x ≤≤≤≤ u
Onde, A é uma matriz n x m, chamada matriz de incidência nó-arco, do
problema, m representa o número de variáveis e n o número de equações. As
colunas dessa matriz correspondem aos arcos (i, j) de um grafo e contém +1 na i-
ésima linha e -1 na j-ésima linha, e zeros nas demais, as linhas correspondem aos
nós do grafo. Essa matriz é unimodular. As definições, e o desenvolvimento da
teoria de redes são tratados no APÊNDICEΙ - TÓPICOS DE TEORIA DE REDES.
1.3.2 – Formulação do Modelo de Fluxos para o Problema de Caminho mais
Curto, de um Nó para outro Nó.
O problema do caminho mais curto se apresenta como o mais simples, dentre
todos os problemas de fluxos em redes. Neste problema o que se deseja é
encontrar um caminho de “custo” (ou comprimento) mínimo, de um nó chamado
origem (s), para um outro nó, chamado de destino, atribuindo-se a cada arco (i, j) ∈∈∈∈
A um custo (ou comprimento) cij.
6
Este problema é formulado como:
Minimizar ∑∑∑∑(i, j)∈∈∈∈A cij xij.
s.a
∑∑∑∑j(j, i)∈∈∈∈A xji - ∑∑∑∑j(i, j)∈∈∈∈A xij = b(i), onde .
xij ≥≥≥≥ 0 para todo (i, j) ∈∈∈∈ A.
1.3.3 – Formulação do PCMC como um Problema de Fluxos de Custo Mínimo.
Minimizar ∑∑∑∑(i, j)∈∈∈∈A cij xij.
s.a
∑∑∑∑j(i, j)∈∈∈∈A xij - ∑∑∑∑j(j, i)∈∈∈∈A xji = b(i), onde
xij ≥≥≥≥0 para todo (i, j) ∈∈∈∈ A, e tal que ∑∑∑∑ni= 1b(i)=0.
1.4- Estado da Arte
(Syslo et al., 1983), capítulo 3 pp. [235-239], apresenta uma análise da
performance entre o método BFM e o método de Dijkstra e afirma que os dois
métodos são rápidos e eficientes quando os custos nos arcos são todos positivos.
No caso de arcos com custo negativo, o método de Dijkstra não funciona; e, neste
caso, o método a ser utilizado é o método BFM. Pode-se dizer ainda, se o que se
deseja, é encontrar somente o caminho mais curto de um nó origem s para um nó
destino t, o algoritmo de Dijkstra é o mais rápido.
Uma expressão analítica para o tempo de execução do algoritmo de Bellman
é mais difícil de se determinar, segundo (Syslo et al., 1983), devido ao número de
vezes que vários nós são revisitados, numa rede arbitrária. Se cada nó entra na fila
exatamente uma vez, a complexidade será proporcional ao número de arcos na
rede e, neste caso, o algoritmo BFM tem uma performance semelhante ao de
Dijkstra. Redes patológicas podem ser construídas de tal modo que a complexidade,
para o pior caso, torna-se exponencial em relação ao número de nós. Na prática,
entretanto, tais redes não ocorrem. O método de Dijkstra, quando todos os custos
b(s)= -1, i=s, nó fornecedor
b(t)= + 1,i=t, nó consumidor
b(i)= 0, para i∈N, i≠s, t
b(s) = -(n-1), i=s,nó fornecedor
b(i)=-1, com i≠s, nó consumidor
7
são positivos, apresenta uma complexidade de ordem O(n2). (Ahuja et al., 1993)
Syslo cita que em extensivos experimentos, (Denardo e Fox, 1979); (Dial et
al., 1979) e (Van Vliet, 1978), mostraram que quando a rede de entrada apresenta
um número pequeno de arcos, em relação ao número de nós, o método de BFM
comporta-se como o método mais rápido, até então conhecido, para resolver PCMC,
de um nó para todos os outros nós da rede, apresentando uma complexidade de
ordem O (nm).
(Dantzig, 1963) apresenta uma regra para selecionar o arco que entra na
árvore, usando um critério de maior violação da condição de otimalidade inspirado
no método simplex. Com este critério, denotando por C a maior distância nos arcos,
(Ahuja et al., 1993) mostram que o algoritmo simplex para redes tem um número de
pivoteamentos da ordem O(n2log(nC)) e um tempo de execução da ordem
O(n2mlog(nC)).
Recentemente, utilizando o método simplex, o primeiro resultado dos estudos
realizados por (Goldfarb et al., 1990) para o problema de encontrar a distância
mínima distância de um ponto para todos os outros pontos de uma rede, aceitando
distâncias sem restrições de sinal, com uma formulação de programação linear
apresenta uma complexidade O(n3) realizando, no máximo, (n-1)(n-2)/2
pivoteamentos para encontrar a solução ótima, isto é, achando a árvore geradora
ótima ou um ciclo negativo.
(Goldfarb et al., 1999) apresenta uma variante do método simplex, de
complexidade de ordem O(nm). Portanto, uma implementação fortemente
polinomial, isto é, a sua medida de complexidade depende apenas dos parâmetros
n e m, para encontrar as distâncias mínimas de um nó para todos os outros nós de
uma rede, com n nós e m arcos ou achar um ciclo direcionado de comprimento
negativo. O tempo de execução deste algoritmo, num pior caso, é tão rápido quanto
qualquer outro método, até então proposto, para resolver o problema.
8
1.5 - Objetivo
O objetivo do trabalho é mostrar, fazendo uma análise de pior-caso e
implementando o algoritmo simplex de (Goldfarb, 1999), os resultados sobre o
número máximo de pivoteamentos do simplex para redes e fazer um estudo
comparativo entre as complexidades dos métodos BFM e o simplex primal, que
neste trabalho é chamado de simplex acelerado. A medida de complexidade refere-
se à estimativa do número de iterações necessárias para atingir a solução como
uma função dos parâmetros n, número de nós ou vértices e m, número de arcos.
A implementação do método BFM, conhecido como algoritmo de rotulação
temporária, por permitir arcos com custos negativos, realiza o melhor tempo
conhecido, até os anos 90. É de ordem O(nm), isto é, o algoritmo BFM para resolver
o PCMC, de um nó para todos os outros nós é fortemente polinomial, numa rede de
n nós e m arcos; o que mostra não existir mais o gap entre as complexidades do
algoritmo simplex para redes, no que diz respeito a algoritmos de natureza
heurística que resolvem o PCMC.
No capitulo 2 são apresentados Tópicos da Teoria de Complexidade, tais
como: definições básicas e a terminologia utilizada para permitir uma melhor
compreensão do tema abordado nos capítulos subseqüentes. Como o tema central
deste trabalho é mostrar uma equivalência, em termos de complexidade, entre o
método de BFM e o Simplex Acelerado proposto por Goldfarb (1999), para encontrar
as distâncias mínimas entre um nó e todos os outros nós da rede. No capítulo 3 são
apresentados os aspectos clássicos para o tema em questão, aplicando-se os
métodos BFM e o simplex para fluxos em rede. No capítulo 4 é apresentado o
método simplex acelerado como uma inovação para resolver o problema de
distâncias mínimas. O APÊNDICE Ι aborda tópicos de teoria de redes e
generalização do simplex para redes. O APÊNDICE ΙΙ apresenta o código da fonte
(Sylos et al., 1983) para o método BFM e o APÊNDICE ΙΙΙ apresenta o código fonte
do simplex acelerado. Ambos os códigos em linguagem Pascal.
10
CAPÍTULO 2
“A discussão é válida quando não existe um dono da verdade”.
TÓPICOS DE TEORIA DE COMPLEXIDADE DE ALGORITMOS
O cálculo científico está presente em diversos campos do conhecimento,
dentre os quais, e de importância fundamental estão a matemática, a física, a
ciência da computação, a pesquisa operacional e a engenharia.
Neste capítulo são apresentadas as ferramentas que medem a complexidade
de um algoritmo, exemplificando estas complexidades. Discute também, a forma de
se estruturar os dados para o computador a partir de instâncias de um problema.
Apresentam-se as três notações básicas, em especial a notação O grande, que
mede a complexidade assintótica de um algoritmo.
2.1 – A resolução Computacional de um Problema.
A resolução de um problema pelo computador envolve os seguintes
elementos básicos:
a) Algoritmo: ou uma seqüência de passos para resolver uma classe
particular de problemas;
b) Uma linguagem para codificar esse procedimento para uso do
computador;
c) Um relatório que resuma as respostas da aplicação de um método aos
dados de um problema específico processados pelos itens a) e b).
Para resolver um problema específico, pode-se lançar mão de uma
calculadora que contém este algoritmo e/ou ainda construir o seu circuito. O primeiro
passo, é armazenar os dados na calculadora, o segundo é instruir a calculadora a
resolver o problema para os dados de entrada.
Multiplicar duas matrizes não é um cálculo difícil quando essas matrizes têm
11
dimensões pequenas. Mas, para matrizes grandes, o calculo do produto dessas
matrizes é algo muito trabalhoso. Para se multiplicar duas matrizes
computacionalmente, o tamanho da entrada dos dados corresponde às dimensões
das matrizes. Neste caso, sendo dada as matrizes A = (aij) e B = (bij), ambas
quadradas n x n, o produto destas matrizes é C = AB. O algoritmo para resolver o
problema (item a) está representado na escrita do algoritmo em um pseudocódigo
mostrado abaixo. Para representar o algoritmo num código computacional (item b)
pode ser usada qualquer linguagem: Pascal, C++, Fortran ou outra. Para finalmente
mostrar a matriz C (item c) num formato final do tipo tabela.
Para i = 1 até n, fazer
Para j = 1 até n, fazer
c i j = 0
para k = 1 até n, fazer ci j = ci j + aikbkj
fim (para k)
fim (para j)
fim (para i)
Assim, para se resolver o problema de fluxos em redes, com centenas de
milhares de nós e arcos, modelados matematicamente por equações e inequações,
só é possível com o uso do computador. Não basta expressar os passos
matemáticos de um algoritmo como um programa de computador, é necessário,
também, desenvolver uma estrutura de dados (com uma grande quantidade de
informações) para representar o problema para o computador.
O item (a) acima, se refere à necessidade de se ter um algoritmo para
atender a resolução de uma classe de problemas. Esta etapa é conhecida como a
parte virtual de um problema por tratar da representação visando a eficiência.
Embora a idéia de algoritmo seja antiga, - matemáticos chineses três séculos
aC, já projetavam algoritmos para resolver pequenos sistemas de equações, os
pesquisadores só começaram formalizar e estudar a noção de eficiência algorítmica
a partir de 1970. Esse tópico particular, conhecido como Teoria de Complexidade,
provê uma estrutura e um conjunto de ferramentas de análises para medir o
12
trabalho computacional realizado, com relação ao tempo, fazendo a contagem das
operações elementares de adição e multiplicação realizadas. Uma grande linha de
pesquisa na teoria de algoritmos computacionais tem focado a análise da eficiência
de algoritmos fazendo um estudo do pior caso. O pior caso é entendido, em termos
comparativos, como a contagem de operações elementares ao se aplicar um
algoritmo em um problema, com maior grau de dificuldade. Pode-se especificar esta
relação em termos do limite superior sobre a quantidade de cálculos que um
algoritmo requer para resolver o problema. Para um problema de fluxos em redes, a
complexidade dependerá dos coeficientes que informam o número de nós n, e o
número de arcos m, do grafo em estudo. Será visto mais adiante que a
complexidade para resolver PCMC, com arcos com comprimento não negativo é
2n2. Isto significa que o número de cálculos cresce não mais rápido que duas vezes
o quadrado do número de nós. Em geral, se diz que um algoritmo é eficiente quando
os seus cálculos estão limitados superiormente por um polinômio em relação ao
tamanho do problema, que, neste exemplo, corresponde ao número de nós.
No exemplo de produtos de matrizes quadradas A e B o número dado de
entradas é 2n2. A quantidade de multiplicações e somas é n3 então, ao todo são
realizadas 2n3 operações.
Quando se comparam dois algoritmos - aquele com, por exemplo, menor
limite superior é preferido do ponto de vista de pior-caso. É conhecido na literatura o
comportamento ineficiente, em pior-caso, do algoritmo simplex, mostrado por um
problema preparado por (Klee e Minty, 1972). Para este problema provou-se que o
método simplex requer 2k-1 iterações, sendo k o número de restrições de igualdade
e 2k variáveis. (Bazaraa et al., 1990, pp. [375]).
2.2 – Análise de Complexidade
Um algoritmo é um procedimento passo-a-passo para resolver um problema.
Por problema, entendemos um modelo genérico, tal como, um problema de
programação linear, um PCMC ou um PFCM com custos negativos.
Uma instância é um caso especial de um problema com dados próprios
13
especificados para todos os parâmetros do problema. Por exemplo, para definir uma
instância do problema de caminho mais curto é necessário especificar a topologia
da rede G= (N, A), o (s) nó (s) fonte e o (s) nó (s) destino, e os valores dos custos
nos arcos.
Diz-se que um algoritmo resolve um problema P, se aplicado para qualquer
instância de P, garante uma solução.
A seguir são apresentados os parâmetros que medem a eficiência de um
algoritmo na solução de problemas. Em um sentido mais amplo, a noção de
eficiência envolve todos os recursos computacionais necessários para a execução
do algoritmo.
2.2.1 – Medidas de Complexidade
Conforme foi dito, um algoritmo é um procedimento passo - a - passo para
resolver um problema. Aqui são considerados os passos típicos de um algoritmo
como as operações necessárias para um procedimento. Estas são:
1. Atribuição de valores às variáveis;
2. Operações aritméticas (adição, subtração, multiplicação e divisão).
3. Operações lógicas (comparação, pergunta).
O número total de operações (ou passos) realizadas pelo algoritmo é a soma
total de todas as operações realizadas. O número de operações realizadas por um
algoritmo determinará o tempo por ele requerido e será diferente de uma instância
para outra. Embora um algoritmo possa resolver algumas “boas” instâncias de um
problema específico rapidamente, ele pode tomar um longo tempo em outras
instâncias.
Desta gama de possibilidades resulta a questão de como medir o
desempenho de um algoritmo, de tal modo a poder selecionar o melhor algoritmo,
dentre os vários algoritmos competentes, para resolver um problema.
A literatura adota três abordagens básicas para medida de desempenho de
14
um algoritmo:
1) Análise teórica
O objetivo dessa análise é estimar como os algoritmos se comportam na
prática. Nessa análise escreve-se um programa de computador para os
algoritmos e se testa a performance dos programas em algumas instâncias
do problema.
2) Análise de tempo médio
O objetivo é estimar o número médio de passos que um algoritmo realiza.
Nessa análise escolhe-se uma distribuição de probabilidade para instâncias
do problema e, usando a análise estatística extraí-se os tempos de execução
esperados assintóticos, nas estimativas em instâncias de tamanho grande.
3 - Análise do pior - caso.
A análise de pior - caso provê limites superiores sobre o número de passos
(operações) que um algoritmo pode tomar sobre qualquer instância do
problema. Nessa análise toma-se em conta o maior número de passos
possíveis; conseqüentemente, essa análise provê uma segurança sobre o
número de passos que um algoritmo realiza para resolver qualquer instância
do problema.
Cada uma das três medidas de desempenho tem seus méritos e
inconvenientes. A seguir comenta-se estas características em cada tipo de análise
refinadas em (Ahuja et al., 1993).
Na análise teórica podem ser citados vários inconvenientes entre eles:
• Alta dependência da linguagem adotada; do compilador e do computador
usados para os experimentos computacionais, assim como da habilidade
do programador que escreve o programa;
• Consome muito tempo e é cara a sua realização;
• A comparação de algoritmos é freqüentemente pouco conclusiva.
Diferentes algoritmos têm atuação melhor em diferentes classes de
instâncias de problemas. Ao mesmo tempo são apresentados relatórios
15
contraditórios sobre diversos estudos empíricos.
Na análise de tempo médio cita-se como os maiores inconvenientes
encontrados os seguintes:
• A dependência da distribuição de probabilidade escolhida para
representar as instâncias do problema, e diferentes escolhas podem
conduzir a diferentes avaliações sobre os méritos relativos do algoritmo
em questão;
• Dificuldade para se determinar à distribuição de probabilidade para
problemas conhecidos na prática;
• Requer uma sistemática intrincada, mesmo para avaliação de algoritmos
mais simples.
Na análise de pior caso, alguns dos inconvenientes citados acima são
evitados. Esta análise é independente do ambiente de cálculo e é
relativamente mais fácil de se realizar, provendo uma segurança sobre o
cálculo dos passos (operações) e do tempo de execução consumido pelo
algoritmo. É, também definitivo no sentido de que provê uma prova conclusiva
de que um algoritmo é superior a outro sobre as piores instâncias de
problemas que um analista pode encontrar. Mas, a análise de pior-caso não é
perfeita. Um dos inconvenientes é que permite experimentar em instâncias
patológicas para determinar a performance de um algoritmo, mesmo que elas
possam ser raras na prática.
2.2.2 – Tamanho do Problema
Para expressar o tempo requerido por um algoritmo, precisa-se definir alguma
medida de desempenho da complexidade de instâncias do problema encontradas.
Uma simples medida de performance para todas as instâncias do problema
raramente faz sentido, quando essas instâncias tornam-se muito grandes e,
conseqüentemente, mais difíceis de serem resolvidas, isto é, tomam muito tempo.
Os esforços envolvidos na resolução dessas instâncias têm forte correlação com o
seu tamanho. Portanto, a medida de complexidade de instâncias de um problema
deve considerar o tamanho da instância do problema. No final desta seção explica-
16
se tamanho do problema. Antes é necessário entender o que é o tamanho de um
dado cujo valor é x.
Pode-se fazer uma das duas suposições plausíveis; a primeira é assumir que
o tamanho do item dado é x; a segunda é assumir que o tamanho do item dado é
logx. Por várias razões a segunda suposição é a mais comum. A razão principal é
que logx reflete o modo que os computadores trabalham. Os computadores mais
modernos representam os números na forma binária; isto é, em bits e são
armazenados em locais da memória de tamanho do bit fixado. A representação
binária do item x requer logx bits, e conseqüentemente, o espaço requerido para
armazenar x é proporcional a logx.
O tamanho de um problema de rede está em função de como o problema é
formulado. Supondo que uma rede é representada como uma lista de adjacência1,
então, o tamanho do problema corresponde ao número de bits necessários para
armazenar essa representação. Assim, numa representação em lista de adjacência,
armazena-se um ponteiro para cada nó e arco, e os elementos de custo e
capacidade associados aos arcos. Nesse caso, a representação binária é a
seguinte: um bit para identificar (espaço logn) vezes o número de nós, n; um bit para
identificar (espaço logm) vezes o número de arcos, m, um bit para identificar
(espaço logC) vezes o número de arcos e um bit para identificar (espaço logU)
vezes o número de arcos; isto quer dizer: nlogn + mlogm + mlogC + mlogU bits, para
armazenar todos os dados do PFCM, onde U representa a maior capacidade dos
arcos da rede e C representa o maior custo dos arcos na rede. Se a relação entre
nós e arcos da rede é verificada, m< n2, logm ≤ logn2 = 2logn. Por essa razão,
quando firmamos o tamanho do problema utilizando a notação de complexidade O
grande, isto quer dizer que as constantes são ignoradas, e pode-se substituir logm
por logn.
Em principio, pode-se expressar o tempo de execução de um algoritmo como
uma função do tamanho do problema; ou mais simplesmente, como uma função dos
1 Lista de adjacência é uma estrutura de armazenamento, de parâmetros de um problema, utilizando
ponteiro.
17
parâmetros da rede n, m, logC e logU. O tempo de execução computacional de um
algoritmo é tratado na seção 2.2.6.
2.2.3 – Complexidade do Pior-Caso
O tempo de execução (running time) do algoritmo depende da natureza e do
tamanho dos dados de entrada. Problemas grandes requerem mais tempo de
solução, e diferentes problemas do mesmo tamanho, tipicamente requerem
diferentes tempos de solução para convenientes diferenças nos dados. Dizemos
que uma função complexidade de tempo (time complexity function) de um algoritmo
é uma função do tamanho do problema e especifica a maior quantidade de tempo
requerido pelo algoritmo para resolver qualquer instância do problema de um dado
tamanho. Em outras palavras, a função complexidade mede a taxa de crescimento
(ver seção 2.2.4) do tempo de solução, da instância de um problema em relação ao
crescimento do tamanho do problema. Por exemplo, se a função complexidade de
tempo de um algoritmo de rede é knm para alguma constante k ≥ 0, o tempo de
execução necessário para resolver qualquer problema de rede com n nós e m arcos
é no máximo knm. Notar que a função complexidade contabiliza a dependência do
tempo de execução, sobre o tamanho do problema, pela medição do maior tempo
necessário para resolver qualquer instância de um dado tamanho; para esse nível
de detalhe na medição da performance do algoritmo, a função complexidade provê
uma garantia de performance que depende da medida apropriada dos dados de
entrada do problema. A função complexidade de tempo é uma referencia da
complexidade no pior caso (neste trabalho, simplesmente, complexidade) do
algoritmo. Também, se refere à complexidade do pior caso como o limite de tempo
necessário à solução da mais difícil instância do problema.
2.2.4 – Classificação de Funções pelas Taxas de Crescimento, Definições e
Notações.
Pode-se dizer que um algoritmo é aceitável, se o número de passos
executados é, a “grosso modo”, proporcional ao número de operações básicas
contadas. Isto é suficiente para separar algoritmos que realizam diferentes
quantidades de trabalho, quando os dados de entrada tornam-se grandes.
18
Supondo que um algoritmo para um problema executa n3/2 multiplicações, e
outro algoritmo executa 5n2. Pode-se afirmar que, para pequenos valores de n, o
primeiro algoritmo executa menos multiplicações; mas, para n grande, o segundo
algoritmo é melhor. No exemplo dado, o que se quer é encontrar uma maneira de se
comparar ou classificar funções de complexidade que ignoram constantes e
entradas pequenas. Este tipo de classificação é conhecido como taxa de
crescimento assintótica, ou simplesmente, a ordem de complexidade de um
algoritmo.
2.2.5 – Notação O
A seguir reapresenta-se a notação utilizada em (Cormen et al., 1990).
a) Notação assintótica com um parâmetro
Fazendo ℵ e ℜ representar o conjunto de números naturais e o conjunto dos
números reais respectivamente, o conjunto ℜ* representando o conjunto dos reais
não negativos e ℜ+ o conjunto dos reais estritamente positivo, pode-se definir:
f: ℵ→ℜ* e t: ℵ→ℜ* funções quaisquer
então, pode-se estabelecer a seguinte notação que relaciona as funções t(n) e f(n),
n∈ℵ:
O(f(n)0 = t: ℵ→ℜ* | (∃ k∈ℜ+) (∃ no ∈ℵ) (∀ n ≥ no [t(n) ≤ kf (n)]
A notação O é chamada de ordem de uma função f(n), e representa o
conjunto de todas as funções t(n) limitadas superiormente por um múltiplo positivo
de f(n), considerando-se n um valor suficientemente grande para que esse efeito
ocorra. Se diz que t(n) é da ordem de f(n) se t(n) ∈ O(f(n)). Essa notação é
extremamente importante para a análise de algoritmos, especialmente para
expressar sua complexidade de execução em função do tempo. Assim, se é
desejado avaliar a função tempo para a execução de um algoritmo, onde a variável
de entrada é, por exemplo, o comprimento da entrada de dados n, O (f(n)) significa
que o tempo gasto por um algoritmo para alcançar seu resultado é proporcional a
f(n). A notação O objetiva proporcionar um embasamento matemático de avaliação
19
de eficiência. Quando se usa a notação O para representar o comportamento de
uma função abre-se mão de seu valor exato e concentra-se na ordem de sua
grandeza, ou no seu comportamento assintótico, daí o nome notação. Essa
simplificação é de extraordinário efeito para o cálculo da eficiência do algoritmo, sem
deixar, contudo, de ser um indicador bastante aproximado de comportamento para
valores suficientemente grande de n.
b) Notação assintótica com vários parâmetros
A notação assintótica O tem um objetivo claro dentro do cálculo da eficiência
dos algoritmos. Em muitos casos o tempo de execução de um algoritmo depende
simultaneamente de mais de um parâmetro. Esse é o caso, por exemplo, de
algoritmos em grafos que envolvem a busca em vértices ou nós (em número n) e em
arcos ou arestas (em número m). Nesse caso, fazendo:
f: ℵx ℵ→ℜ* uma função arbitrária
então se pode estabelecer a seguinte notação:
O(f(m, n)) = t: ℵx ℵ | (∃ k∈ℜ+) (∃ mo, no ∈ℵ) (∀ n ≥ mo ) (∀m≥mo)[t(m, n))≤ kf(m, n))]
2.2.6 – Tempo de Execução de um Algoritmo
Estimar a complexidade de um algoritmo não é uma tarefa fácil. O caminho
de medir teoricamente o desempenho de um algoritmo esbarra em dificuldades que
vão desde o equipamento e compilador empregado, até as habilidades do
programador. Desde o final da década de 1960 um modelo interessante de análise
vem sendo adotado. Uma providência importante desse modelo foi propor um
modelo geral para a máquina computacional , facilitando sobremaneira a análise da
computação das instruções. O modelo RAM (Random Acess Machine) está
expresso na figura 2.1 abaixo:
20
Unidadede
Memória
Unidade deControle e
Processamento
Unidadede
Entrada
UnidadedeSaída
Figura 2.1- Modelo RAM. Fonte: Campello (1994)
O modelo RAM simula o funcionamento de um computador elementar. À
memória cabe armazenar os dados do programa. Um programa é constituído por
um conjunto de instruções ou comandos que implementa o algoritmo. O modelo
considera que cada instrução Ι possuirá um tempo associado t(Ι) para ser
operacionalizada em RAM. Então se para executarmos um algoritmo codificado em
um programa P, com uma certa entrada fixa, são processadas r1 instruções do tipo
Ι1, r2 do tipo Ι2, até rm instruções do tipo Ιm. Nesse caso o tempo para executar o
programa P será dado por:
∑j=1mrjt(Ιj) (1)
Em última análise, no modelo RAM, o estudo da complexidade de um
algoritmo poderia ser resolvido através da avaliação do somatório (1). Para
simplificar o problema do cálculo do tempo de duração da computação das
instruções do tipo Ιj , para j=1,2,...,m, considera-se t(Ιj) = 1 para qualquer instrução Ι.
Essa simplificação é perfeitamente coerente com o uso da notação O (.) para a
avaliação da complexidade em tempo computacional , uma vez que a relação entre
a duração dos diversos tipos de instruções é obviamente de natureza constante, o
que seria irrelevante, no cálculo da ordem de complexidade. Outra vantagem em se
adotar t(Ι) = 1 é que assim o valor do tempo de execução de um programa iguala-se
ao número total de instruções computadas.
Denominando por passo de um algoritmo α a computação de uma instrução
do programa P que o implementa, a complexidade local do algoritmo α é definida
21
como o número total de passos necessários à perfeita computação de P, para uma
certa entrada de dados E de comprimento n. Raciocinando assim, a complexidade
de um algoritmo α confunde-se com seu tempo de execução, denominado por T(n),
e será fundamentalmente dependente da entrada de dados.
Nesse ponto, é importante se firmar o discernimento entre um problema e
suas instâncias. O termo instância, como visto anteriormente, refere-se a uma
especificação de valores dados aos parâmetros de entrada num determinado
momento, satisfazendo às condições ou restrições próprias do problema. O
tamanho de uma instância é o total de códigos necessários a sua identificação,
considerando o tipo e a estrutura de dados utilizada. E, no cálculo de complexidade,
refere-se ao tamanho da instância, independendo dos valores associados aos
parâmetros que alimentarão o programa P. Nesse sentido, torna-se fundamental
bem avaliar o tamanho da entrada.
Como normalmente se está interessado em avaliar o desempenho de
algoritmos sobre instâncias de grande tamanho, seria muito útil se fosse possível se
definir um limite superior para o número de passos do algoritmo α quando, através
de P, atuasse sobre a tal entrada E. Define-se complexidade local assintótica de um
algoritmo como sendo um limite superior da sua complexidade, para uma certa
entrada E, julgada suficientemente grande. Em tese, se está sempre interessado no
verdadeiro valor da complexidade do algoritmo mas, esse valor, pode ser
extremamente difícil de ser calculado. O uso do conceito de complexidade local
assintótica, segundo (Goldbarg e Luna, 2000), é uma simplificação adequada
quando se pode encontrar um limite superior para a complexidade suficiente
próximo ao valor exato procurado. Nesse ponto, busca-se o auxílio da notação O (.).
Usando esta notação se está apto a encontrar com mais facilidade um limite
superior para função complexidade em entradas de grande tamanho.
Para que se possa completar essa análise de complexidade, é necessário se
considerar o comportamento das instâncias. A complexidade assintótica de um
algoritmo não será a única pois, mesmo para entradas de igual comprimento, P
poderá exigir um número de passos completamente diferente para diferentes
instâncias do problema. Dentro de uma grande diversidade de entradas duas são
22
importantes: a que conduz a um desempenho mais otimista e a que leva um mais
pessimista.
Sabendo T(n)≤ k × f(n), para algum valor de k > 0 e ∀ n, define-se
complexidade de pior caso O(f(n)) ao valor máximo dentre todas as suas
complexidades assintóticas, para entradas de tamanho suficientemente grandes.
Define-se complexidade de melhor caso Ω(f(n)) ao valor mínimo dentre todas as
suas complexidades assintóticas, para entradas de tamanho suficientemente
grandes. A complexidade de melhor caso corresponde a um limite superior do
número de passos necessários à computação da solução considerando a entrada
mais desfavorável. Eventualmente o comportamento assintótico do algoritmo poderá
ser limitado simultaneamente por ambas as complexidades anteriormente definidas.
Nesse caso particular é introduzida a noção de ordem exata de f(n), Θ(f(n)):
Θ(f(n))=O(f(n)) ∩ Ω(f(n))
Propriedades da ordem O:
1) O (f(n)) + O (g(n)) = O max f(n), g(n).
2) O (cf (n)) = cO (f(n))=O (f(n))
3) O (f(n).g(n))= O (f(n)). O (g(n))
(Goldbarg e Luna, 2000, pp [607])
2.2.7 – Suposição de Similaridade
A suposição de que cada operação aritmética toma uma unidade (um passo),
pode conduzir a uma sub estimação do tempo de execução assintótica de
operações aritméticas envolvendo números grandes, nos computadores atuais. Na
prática, um computador deve armazenar tais números em várias palavras de sua
memória; portanto, para realizar cada operação com números muito grandes, um
computador deve poder acessar um número de palavras de dados e, assim, tomar
muito mais do que um número constante de passos. Então os tempos de execução
darão uma estimativa imprecisa quando os números são exponencialmente
grandes. Para evitar essa subestimação sistemática do tempo de execução, quando
se comparam dois tempos de execução, se assume que tanto C, quanto U, sejam
limitados polinomialmente na ordem O grande de n (C = O(nk) e U = O(nk), para
alguma constante k. Essa suposição é referida como suposição de similaridade.
23
(Ahuja et al., 1993).
2.2.8 - Algoritmos Polinomiais e Exponenciais
O questionamento que é feito quando se estuda a complexidade de um
algoritmo é tentar se estabelecer a “bondade” desse algoritmo. O ideal seria dizer
que um algoritmo é “bom”, se o algoritmo é suficientemente eficiente, para ser
usado na prática. Mas, essa definição é imprecisa e não tem embasamento teórico.
A idéia aceita atualmente é considerar um algoritmo “bom”, se a sua complexidade,
no pior caso, é limitada por uma função polinomial, em relação aos parâmetros do
problema; isto é, no caso da tese, em função de n, m, logC. Esse algoritmo é
conhecido como polinomial. Alguns exemplos de conjuntos de ordem polinomial
são: O(n2), O(nm), O(m + nlogC), O(mlog(n2/m) e O(nm + n2logU). (Notar que logn é
limitado polinomialmente porque sua taxa de crescimento é muito menor que n). Um
algoritmo de tempo polinomial é dito ser um algoritmo fortemente polinomial, se o
seu tempo de execução é limitado por uma função polinomial em n e m; não
envolvendo logC ou logU, em outro caso, o algoritmo é fracamente polinomial.
Alguns limites de tempo fortemente polinomial são O(n2m) e O(mlogn). Em princípio,
algoritmos de tempo fortemente polinomial são preferidos aos fracamente
polinomial, porque eles podem resolver problemas com os valores arbitrariamente
grandes para os dados de custo e capacidade.
Um algoritmo é exponencial quando o seu tempo de execução, numa
instância de pior caso cresce como uma função exponencial, em relação aos
parâmetros e comprimento (tamanho) dos dados.
Exemplos de conjuntos de ordem exponencial.
O(nC), O(2n), O(n!) e O(nlogn). (observa-se que nC não pode ser limitada por
uma função polinomial de n e logC).
Um algoritmo é pseudopolinomial quando o seu tempo de execução é
limitado superiormente por um polinômio em função de n, m, C e U. Os algoritmos
pseudopolinomiais formam uma importante subclasse dos algoritmos exponenciais.
Exemplos de conjuntos de ordem pseudopolinomial: O(m + nC) e O(mC).
24
Assume-se que para problemas que satisfaçam o conceito suposição de
similaridade, os algoritmos de tempo pseudopolinomial tornam-se algoritmos de
tempo polinomial; mas, estes algoritmos não são atrativos se C e U são polinomiais
de alto grau n.
Existem várias razões pela preferência dos algoritmos polinomiais aos
exponenciais. Qualquer algoritmo de tempo polinomial é assintoticamente superior a
qualquer algoritmo de tempo exponencial, mesmo em caso extremos. Por exemplo,
para n= 107 ≥ 2 100 000 temos n4000= 1x 1028000 e n0,1logn que tem 12 casas inteiras
e duas decimais, isto é, 191719794860,09.
No quadro a seguir é mostrada a taxa de crescimento de várias funções que
servem de referência para a complexidade. As funções de complexidade
exponenciais têm uma taxa de crescimento explosiva, e, em geral, são hábeis para
resolver somente pequenos problemas. Além disso, as experiências práticas têm
mostrado que os algoritmos chamados de polinomiais encontrados na prática têm
grau pequeno, e, geralmente, estes têm um desempenho melhor do que algoritmos
exponenciais.
Quadro 1 - Taxas de crescimento de algumas funções polinomiais e exponenciais. Fonte:
Ahuja(1993).
N ln n0, 5 N2 n3 2n N!
10 3,32 3,16 102 103 210 3,6 * 106
100 6,64 10,00 104 106 1,27 * 1030 9,33 * 10157
1000 9,97 31,02 106 109 1,07 * 10301 4,02 * 10 2.567
10000 13,29 100,00 108 1012 0,99 * 103010 2,85 * 10 35.659
Para se concluir a discussão sobre algoritmos polinomiais e exponenciais, na
área da teoria da complexidade o objetivo é obter algoritmos polinomiais; e, dentre
eles, obter um algoritmo com a menor taxa de crescimento possível para resolver
problemas de grande porte, minimizando o tempo computacional. Essa minimização
depende, também, das constantes que acompanham a função.
25
Por exemplo, prefere-se O(logn) a O(nk), para qualquer k>0; e, O(n2), em vez
de O(n3).
Entretanto, tempos de execução envolvendo mais que um parâmetro, tais
como O(nmlogn) e O(n3) pode não ser comparável. Veja-se, por exemplo, o caso:m<
n2logn; nessas condições, O(nmlogn) é superior; de outro modo, O(n3) é superior.
Pode-se dizer que um algoritmo polinomial apresenta, ao menos
teoricamente, uma performance superior ao algoritmo exponencial. Embora esta
afirmação seja geralmente aceita, existem muitas exceções a regra. Uma exceção
clássica é provida pelo método simplex e o algoritmo elipsoidal de (Khachian, 1979),
ou de pontos interiores, que resolvem problemas de programação linear. O
algoritmo simplex é conhecido como um algoritmo de tempo exponencial, mas, na
prática, o método simplex apresenta um desempenho melhor que o algoritmo de
tempo polinomial de Khachian. Muitas dessas exceções podem ser explicadas pelo
fato da complexidade no pior-caso ser muito inferior à complexidade de tempo
médio de alguns algoritmos, enquanto para outros algoritmos a complexidade média
pode ser comparada. Como conseqüência, (Ahuja et al., 1993) afirmam que ao se
considerar a complexidade de pior-caso, como sinônimo de complexidade média,
pode-se incorrer em conclusões incorretas.
26
CAPÍTULO 3
“Enquanto o pobre falar a linguagem do rico, ele não deixará de ser pobre”.
ASPECTOS CLÁSSICOS DO PROBLEMA DE CAMINHO MAIS CURTO
Neste capítulo é abordado o problema de caminho mais curto de um nó, para
todos os outros nós de um grafo, sem restrição de sinal para os custos (distâncias)
nos arcos. Inicialmente é apresentado o método do tipo “combinatório” de Bellman-
Ford-Moore (BFM), que resolve o problema e, em seguida, o problema formulado
como um problema de programação linear, e resolvido pelo método simplex.
No aspecto inovativo, uma implementação do algoritmo simplex proposta
para resolver o problema de caminho mais curto de um nó para todos os outros nós
de um grafo, que mostra uma performance fortemente polinomial do simplex será
apresentada no capítulo IV.
3.1 – O Método BFM
O algoritmo de BFM foi assim denominado, para homenagear os trabalhos
simultâneos dos pesquisadores Bellman, Ford e Moore, mas publicados em épocas
diferentes. Neste método se faz uma rotulação temporária de um nó, a cada
iteração, e se examinam todos os outros nós até não poder ser encontradas
menores distâncias entre o nó raiz e cada um dos outros nós; permitindo com isso,
aceitar arcos com custos ou distâncias negativas.
A idéia básica de cada iteração é a seguinte: Se um caminho do nó s, para
um nó u contém k arcos, um caminho melhor de s para u conterá, no máximo, k + 1
arcos.
Repete este procedimento revisando novos arcos até satisfazer um critério de
parada que está associado à não modificação de todos os rótulos em uma iteração.
O método BFM que resolve o problema de caminho mais curto de um nó para
27
todos os outros nós de um grafo direcionado G(N, A), diferente do algoritmo de
Dijkstra, (1957) trabalha com arcos de custos negativos utilizando a técnica de
rotulação temporária (dinâmica) para modificar as informações de distância nos nós.
Esta técnica consiste na permissão para que um nó já rotulado seja visitado mais de
uma vez e, a cada nova visita, seja realizado um teste de comparação, entre a
distância do caminho atual do nó s (origem) até o nó v, e o novo caminho
encontrado. Se um novo caminho melhora a distância do nó s ao nó v, a nova
distância (dist (v)) substitui a atual, e o nó predecessor pred (u) de v, responsável
por essa melhora é indicado, simbolizando o novo caminho.
Este método de busca do caminho mais curto consiste na realização de uma
varredura nos arcos com a calda no nó u ∈ N e, calculando as distâncias dist(v), aos
nós adjacentes ao nó u, até, o nó s. Se dist(v) > dist(u) + cu,v, dist(v) assume o valor
dist(u) + cu, v.
Em cada nó v visitado, uma nova varredura é realizada nos arcos com a
calda em u e, se uma distância menor de s a v é encontrada, um novo caminho é
encontrado; e continua a varredura enquanto houver nós adjacentes ao nó u ∈ N
não analisados, e o método iterativo é repetido, na busca de caminhos que
melhoram a distância entre os nós s e u. O modo como o método foi estruturado
toma muito tempo computacional. Essa deficiência do método foi percebida e
resolvida por (Pape, 1974 e d’Esopo, 1980) com uma implementação de ordem de
visita, isto é, a constituição de uma fila Q, que controla a entrada e a saída dos nós
de acordo com a sua condição de já ter sido visitado, ou não, pelo método. Se um
nó v já esteve em Q, apenas os arcos que terminam em v fornecem informações
para minimizar dist (v), isto é, um arco que informa a distância de s a v no caminho
atual, a menor até o momento, e o outro arco que traz a informação sobre uma
possível minimização da distância de s a v, para comparação, reduzindo desta
maneira o tempo computacional. Esta implementação é eficiente quando aplicada
em redes de pouca densidade de um problema de caminho mais curto de s para
todos os outros nós u da rede. O conjunto formado por estes caminhos forma uma
arborescência (skim) enraizada em s. (Obs. Essa árvore é equivalente a árvore
geradora ótima encontrada pelo método simplex para rede).
A seguir se coloca a representação do método BFM em um pseudocódigo Fonte:
28
Syslo (1983).
INÍCIO
Para v ∈ N, faça
comece (01)
dist(v) ← ∞;
pred (v) ← -1;
Q(v) ← -1;
fim (01)
dist (s) ← 0;
iniciar a fila Q, com apenas o nó s;
cabeça de Q ← s;
ITERAÇÃO
enquanto Q não é vazia, faça
comece (02)
delete o nó u cabeça de Q;
para cada arco (u, v) que inicia em u, faça
comece (03)
novo rótulo ← dist ( u ) + wu, v;
se, novo rótulo < dist ( u ) + wu, v, então
comece (04)
dist ( v ) ← novo rótulo;
pred ( v ) ← u;
se v nunca esteve em Q, então
incluir v na calda de Q
senão, v esteve em Q, mas não está agora, então
incluir v na cabeça de Q
fim (04)
fim (03)
fim (02)
fim(01)
29
3.2 – O Método Simplex para Redes aplicado ao PCMC
Nesta seção é apresentado o problema de caminho mais curto de um nó,
para todos os outros nós de um grafo G(N, A), com uma formulação de
programação linear, como um caso do problema de fluxos em redes (APÊNDICE Ι).
O método descrito incorpora os seguintes estudos:
a ) Uma variante na implementação do simplex para redes proposto por
(Goldfarb et al., 1990a), para encontrar a árvore geradora ótima de caminhos
mais curtos do nó raiz para todos os outros nós, ou, um ciclo de comprimento
negativo. A estimativa, no pior caso, desta variante é realizar no máximo (n-
1)(n-2)/2 iterações, apresentando uma complexidade da ordem O(n3).
b ) Um resultado é incorporado que evita o problema de antidesaceleração (anti-
stalling). A desaceleração no simplex é definida como uma seqüência
exponencial de pivoteamentos consecutivos, sem apresentar ciclo, mas, sem
melhoras significativas na busca do mínimo. Neste estudo (Goldfarb et al.,
1990b) apresenta regras de pivoteamento para o simplex para redes, que
previne o problema de desaceleração do método simplex para redes. As
regras ditadas limitam o número de pivoteamentos, que são ocasionados por
uma degeneração encontrada, em no máximo n(n-1)/2, onde n é o número de
nós do grafo. No estudo também são descritas as relações entre essas
regras de pivoteamentos para o simplex, e adaptações que fornecem uma
complexidade polinomial, para resolver o problema de caminho mais curto.
3.2.1 – Adaptação do PFCM para PCMC
O problema de fluxos em redes apresenta na sua estrutura geral, um conjunto
solução básica (isto é,formado por arcos com fluxos que tomam valores entre os
limites de capacidade, inferior e superior, formando o conjunto T); o conjunto de
arcos não básicos, com fluxos nos limites inferiores, formando o conjunto (L) e, os
arcos não básicos com fluxos nos limites superiores, formando o conjunto (U).
Na seção 3.1 foi tratado o algoritmo que resolve o PCMC, de um nó para
todos os outros nós de uma rede, denominada BFM. Nesta seção o PCMC é tratado
como um problema de programação linear, formulado a partir da formulação do
30
problema de fluxos em redes. Esta formulação é um caso do PFCM, e as suas
soluções básicas apresentadas na forma de árvores geradoras, constituídas pelos
arcos básicos que formam o conjunto T, como será visto mais adiante, e por arcos
não básicos formando o conjunto L. O conjunto U é vazio.
A seguir apresenta-se uma adaptação do método simplex para resolver o
problema de caminhos mais curtos de um nó específico (raiz) para todos os outros
nós dessa rede. O algoritmo resultante apresenta algumas semelhanças com o
algoritmo BFM tratado na seção anterior.
O problema de encontrar o caminho mais curto entre um nó raiz e todos os
nós de um grafo, resolvido como um problema de fluxo em redes, pode ser
interpretado como “o desejo de” se enviar de um nó s, chamado fonte, para todos os
outros nós da rede, uma unidade de fluxo, pelo caminho mais curto. A formulação
matemática do problema foi apresentada na seção 1.3.3:
Se a rede contém um ciclo negativo, isto é, a soma das distâncias, dos arcos
que formam o ciclo, é negativa, encontra-se no caso de valor ótimo ilimitado.Pode-
se, percorrer este caminho diminuindo a distância sem violar as restrições de
demanda unitária (em cada nó v≠s) e mantendo o consumo da fonte s. O algoritmo
simplex é capaz de detectar a presença de um ciclo negativo; e, se a rede não
contém esse ciclo, o método encontra as distâncias mais curtas. Igual a outros
problemas de fluxo de custo mínimo, o problema de caminho mais curto de um nó
para todos os outros nós, apresenta as soluções básicas na forma de árvores
geradoras caracterizadas no APÊNDICE Ι. Pelo modelo assumido, onde se define
um único nó como fonte e, todos os demais nós, caracterizados como
demandantes, as árvores que gera o algoritmo apresentam arestas ou arcos
orientados. Isto é, árvores geradoras direcionadas, onde no nó i está à calda do arco
(i, j)∈ T. A representação dessas árvores é mostrada na figura 3.1, que é conhecida
como árvore direcionada para fora da raiz por formar caminhos entre os nós s e j de
T.
31
i j
1 2 4
3
5
6 10
9
11
7
8 12
11
5
4
1
1
1
2
4 1
1
1
s
xij
Figura 3.1 - Árvore fornecedora. Fonte: Ahuja (1993)
Como cada nó da rede, exceto o nó s, que é fonte, tem uma demanda de
uma unidade, o fluxo do arco (i, j) é |D(j)|, a cardinalidade do conjunto D(j), onde D(j)
é o conjunto de nós descendentes do nó j, inclusive este nó, na árvore geradora.
Portanto, cada árvore do problema de fluxos em redes é não degenerada.
Considere que P(j) representa a distância do caminho desde o nó s para o nó
j. Para se calcular as potências dos nós pertencentes à árvore T é atribuída a
potência zero ao nó s (ππππ(s)=0). As demais potências, são calculadas pela equação
dos custos reduzidos do simplex usual cijπ= cij - π (i) +π (j)=0, para cada arco (i, j) ∈
T, percorrendo a árvore a partir de s pelo caminho direcionado que leva ao nó u. A
figura 3.2 mostra um exemplo de árvore de caminhos mínimos incorporando o valor
das potências em cada nó.
32
i j
1 2 4
3
5
6 10
9
11
7
8 12
5
3
7
2
4
8
6
4 1
2
9
s
cij
π(i) π(j)
0 -5
-8 -15
-17
-19
-23-7
-10
-9
-15 -24
Fig. 3.2 - Potência dos nós. Fonte: Ahuja (1993)
Para se calcular a potência de um nó j, em árvore geradora, é aplicada a
seguinte equação: π (j) = - ∑(i, j)∈P(j) cij. Desse modo, π(j) é o oposto do comprimento
do caminho P(j).
Como as variáveis do problema possuem apenas restrições de não
negatividade, todos os arcos (i, j)∉ T têm fluxo zero. O algoritmo simplex seleciona
um arco (k, l)∉ T, com um custo reduzido negativo para ser incorporado a árvore. A
adição desse arco cria um ciclo (W) orientado com a direção de (k, l), conforme
mostra a figura 3.3
w
l
6
53
k
s
11
11
1
43
1
12
1
Arco candidato a entrar na base
Arco candidato a sair da base
pred (l)
Figura 3.3 - Seleção de arco candidato para entrar e deixar a árvore. Fonte: Ahuja (1993)
Nesse ciclo, cada arco entre o nó l e nó w forma um segmento (“caminho”
contrário as suas direções) e cada arco entre o nó w e o nó k forma um caminho de
33
w a k. Desse modo, o arco que sai da árvore está no caminho inverso entre l e w e,
o arco que deixa a árvore é o arco (pred(l), l) por apresentar o menor fluxo entre
todos os arcos do segmento entre o nó l e o nó w. O algoritmo então aumenta as
potências dos nós na subárvore do nó w até o nó l da quantidade |cklπ|, e atualiza as
potências dos nós da árvore T.
O algoritmo repete esse procedimento, segundo o critério de otimalidade,
para os arcos não básicos, isto é os arcos (i, j) ∉T até encontrar a árvore ótima,
momento em que os custos reduzidos dos arcos não básicos serão todos não
negativos (isto é, o conjunto dos arcos (i, j) ∉ T, apresentam custos reduzidos, cijπ
≥0), que é o critério de parada.
No problema de fluxos em rede conhecer os valores dos fluxos nos arcos da
árvore T é fundamental para escolha do arco candidato a sair da árvore. No entanto,
no PCMC, quando modelado como um problema de fluxos em redes, pode-se
determinar o arco que deixa a árvore sem se precisar considerar esses valores de
fluxos. Se (k, l) é o arco escolhido para ser adicionado à árvore, então o (pred (l), l) é
o arco que será retirado da árvore. Desse modo, o algoritmo simplex para PCMC
não precisa manter os fluxos nos arcos. A atualização das potências dos nós na
árvore T resulta então muito simples de se calcular quando o problema é o de achar
o caminho mais curto.
Mostra-se a seguir que o algoritmo simplex para redes (ASR), aplicado ao
PCMC, é similar ao método BFM apresentado na seção 3.1. No método BFM fixa-se
à distância dist(i) e pesquisa-se um arco que satisfaz a condição dist(j)> dist(i) + cij e
rotula-se à distância do nó j até ao nó fonte (raiz) como dist(i) + cij. No algoritmo
simplex para redes, define-se dist(i) = -π(i), então dist(i) são os rótulos das distâncias
válidas, isto é, elas representam o comprimento do caminho direcionado do nó
s(fonte) ao nó i. Em cada iteração, o simplex seleciona um arco (i, j) com o custo
reduzido negativo (cijπ < 0) para ser incorporado à árvore T. Observar que cij
π = cij -
π(i) + π(j) = cij + dist(i) - dist(j)<0. Portanto, igual ao método BFM, o ASR seleciona
um arco que viola a condição dist(j) > dist(i) + cij; e, do mesmo modo que o método
BFM, o simplex aumenta a potência dos nós pertencentes à subárvore do arco
adicionado ( isto é, o novo caminho entre o nó s e o nó j), em uma quantidade |cij| e,
34
subtrai essa mesma quantidade das potências dos nós, pertencentes a subárvore
do arco retirado.
Quando a rede não contém ciclo negativo, o ASR termina com uma árvore de
caminhos mais curtos; mas se a rede contém um ciclo negativo, o algoritmo poderá
encontrar uma situação parecida com a representada na figura 3.4.
,
s
l
k
Fig. 3.4 - Ciclo negativo. Fonte: Ahuja (1993).
Este tipo de situação ocorrerá somente quando a calda do arco (k, l)
escolhido para entrar na árvore; isto é, o nó k pertencer ao conjunto de nós
descendentes do nó l (o conjunto D(l) é formado pelo pai/filho da árvore). O simplex
para redes pode detectar essa situação facilmente sem qualquer aumento
significativo de esforço computacional. Após a introdução do arco (k, l), o algoritmo
atualiza as potências dos nós em D(l), e, se essa situação é observada, isto é, o nó
calda k, precede o nó cabeça l, o algoritmo termina. Neste caso, o método simplex
identifica os índices predecessores que produz o ciclo negativo.
A versão genérica do algoritmo simplex para rede (ASR) para o problema de
caminho mais curto desde um nó a todos os outros nós é executado em tempo
pseudopolinomial. Isso resulta nos seguintes fatos:
1) Para cada nó i, -nC ≤ π(i) ≤ nC (porque o comprimento de cada caminho
direcionado do nó s para o nó i cai entre -nC para nC);
2) A cada iteração aumenta o valor de pelo menos o potencial de um nó.
Pode-se, entretanto, desenvolver implementações especiais executadas em
tempo polinomial.
35
3.2.2 – Regras de Pivoteamentos
A seguir são apresentadas as regras usuais de pivoteamentos utilizadas pelo
método simplex, que garantem a boa performance do método quando aplicado ao
PCMC.
3.2.2.1 – Regra de Pivoteamento do Primeiro Arco Elegível
O algoritmo simplex para rede carrega uma forte semelhança com o critério
FIFO2 de revisões dos nós(o primeiro que entra, é o primeiro que sai) do método de
rotulação temporária descrito na seção 3.2, na construção da fila Q para visitação
dos nós pelo método. O algoritmo FIFO examina a lista de arcos com o mesmo nó
calda (nó que está sendo analisado). Se um arco (i, j) viola sua condição de
otimalidade, (isto é, esse arco é elegível), o algoritmo atualiza o rótulo de distância
do nó j. Essa forma de examinar os arcos assegura que após o k-ésima iteração o
algoritmo computa a distância de caminho mais curto para todos aqueles nós que
tem um caminho mais curto com k ou menos arcos. O algoritmo simplex para redes
com a regra do primeiro arco elegível também examina a lista de arcos em grupo. E,
se um arco (i, j) é elegível, isto é, viola sua condição de otimalidade, essa regra
atualiza os rótulos das distâncias de cada nó em D(j), que inclui, também, o nó j.
Conseqüentemente, essa regra de pivoteamentos também, dentro de k passos,
encontra a distância de caminho mais curto entre todos aqueles nós que estão
conectados à fonte (o nó s) por um caminho mais curto com k ou menos arcos. Com
isso, o algoritmo simplex para redes realiza no máximo n passos sobre a lista de
arcos. Como resultado, o algoritmo realiza no máximo nm pivoteamentos, com uma
complexidade de O(n2m), segundo Goldfarb (1990a).
3.2.2.2 – Regra de Pivoteamento de Dantzig
Esta regra seleciona o arco para entrar na árvore usando o critério da maior
violação de otimalidade, isto é, o arco com o custo reduzido mais negativo. Com
este critério, denotando por C a distância maior nos arcos, Ahuja (1993) mostra que
2 FIFO: first in-first out, é um tipo de estrutura de dados semelhante a uma FILA.
36
o algoritmo simplex para redes tem um número de pivoteamentos da ordem
O(n2log(nC) e o tempo de execução da O(n2mlog(nC)).
3.2.2.3 – Regra de Pivoteamento Escalonado
Esta regra de pivoteamento é uma versão aproximada da regra de Dantzig.
Nesta são realizados um número de fases de aproximação (scaling phases)
variando os valores de um parâmetro de aproximação ∆. O valor inicial atribuído
para ∆= 2logC, isto é, atribui-se ao parâmetro ∆ o valor 2 a potencia (maior ou igual
a logC) e pivota com qualquer arco não básico, com uma violação de no mínimo ∆/2.
Quando nenhum arco não básico deixar de apresentar a violação ∆/2, substituí-se ∆
por ∆/2 e repete-se o passo. O algoritmo termina quando ∆ < 1.
(Ahuja et al., 1993, capítulo 11) mostra que o algoritmo simplex para redes,
com a regra de pivoteamento escalonada, resolve o PCMC, em tempo polinomial; -e
afirma - ser a regra de pivoteamento de Dantzig um caso especial da regra
pivoteamento escalonado. Portanto, esse resultado também mostra que, quando
implementada com a regra de pivoteamento de Dantizig, apresenta também, uma
complexidade polinomial.
Chama-se a seqüência de iterações quando ∆ permanece inalterado de ∆-
fase escalonada. Fazendo π denotar o conjunto de potências dos nós para o início
da ∆ - fase escalonada, e mais, P* (p) denotar um caminho mais curto de s para o
nó p e fazendo π*(p) = - ∑ (i, j) ∈P* ci j denotar a potência ótima do nó p. A análise da
regra de pivoteamento escalonado conduz ao seguinte propriedade lema:
Se ππππ denota as potências atuais dos nós para o início da ∆∆∆∆- fase de
escalonamento, então ππππ*(p)-ππππ (p) ≤≤≤≤ 2n∆∆∆∆ para cada nó p.(Ahuja et al., 1993)
37
3.3 – Representação clássica ASR em pseudocódigo.
(Procedimento simplex para rede)
variáveis do problema
begin
escolha uma árvore básica viável T;
calcule os multiplicadores do simplex π (u) para todo u ∈ N;
While L= (g,h) ∉ T | cvwπ < 0 ≠ 0 do begin
escolha um arco (g, h)∈L para entrar na árvore;
If g∈Dh then termine (ciclo (g, h) é um ciclo negativo);
procedimento simplex
π(h) ←π(h) + cghπ para todo v∈ Dh;
T ← T + (g, h) - pred(h), h;
end;
end.
38
CAPÍTULO 4
“A crença valoriza o passado, faz o presente promissor e um futuro de glória”.
UMA INOVAÇÃO PARA O PCMC - O SIMPLEX ACELERADO
Neste capítulo é apresentado o método simplex primal proposto por (Goldfarb
et al., 1999) para resolver o PCMC de um nó específico para todos os outros nós da
mesma rede ou, encontrar um ciclo de comprimento negativo e, finalmente uma
descrição da implementação desse método, intitulado simplex acelerado,
sublinhando as variáveis mais importantes usados na codificação em linguagem
PASCAL.
O problema de encontrar o caminho mais curto de um nó para todos os
outros nós de uma rede, usando metodologias “combinatórias”, foi apresentado por
Bellman-Ford-Moore (seção 3.1), como uma generalização do método de rotulação
permanente, proposto por Dijkstra, caso exista solução. Em outro caso termina a
busca quando encontra um ciclo negativo. Este método trabalha, também, com
custos negativos nos arcos e apresenta uma complexidade de ordem O(nm) para
resolver o PCMC de uma rede com n nós e m arcos e, até Goldfarb, considerado o
mais eficiente para resolver o problema em questão. No método de Goldfarb, os
modelos de fluxos usados para formular o PCMC conseguiram identificar, nas
variáveis duais, o valor das distâncias entre o nó raiz e qualquer outro nó, de
qualquer caminho que os ligue.
Como o problema trata da busca do caminho mais curto de um nó para todos
os outros nós de uma rede, o método proposto potencializa os custos nos arcos, em
vez dos fluxos, igualando-se à eficiência do método BMF.
4.1 – Descrição do Método simplex acelerado
Considerar um grafo direcionado G = (N, A), com n nós e m arcos. A cada
arco(v, w) ∈ A é associado um comprimento cv,w. O problema de caminho mais curto
abordado consiste em achar uma árvore de caminhos orientados entre o nó s ∈ N e
todos os outros nós de G. A formulação matemática do problema está descrita na
39
seção 1.3.3.
O algoritmo simplex acelerado é uma implementação melhorada do algoritmo
simplex para o PCMC, tratado no capítulo 3, e apresenta uma complexidade
fortemente polinomial, no pior caso, da ordem O(nm). Esta complexidade do
algoritmo iguala a eficiência do método BFM.
A seguir é apresentado o procedimento proposto por (Goldfarb et al., 1999)
para simplex acelerado onde, a cada iteração, o algoritmo executa, em três etapas,
a seguinte rotina para selecionar um arco que deve ser adicionado na árvore
geradora T^ e escolher o arco a ser retirado: atualiza a árvore geradora e testa as
condições de otimalidade.
Primeira etapa (ordenação):
O algoritmo é estruturado como uma seqüência de passos, onde em cada
passo, todos os m arcos do grafo são analisados; e aqueles arcos com o
mesmo nó cabeça são analisados em grupo. A ordem em que esses grupos
são analisados é B(wn), B(wn-1),..., B(w1), onde w1, w2,..., wn são os nós
cabeça numa pré-ordenação na árvore geradora T^ para o começo do passo
inicial. Os grupos B (w) = (v,w) ∈ A, são os conjuntos que correspondem aos
arcos que têm como nó cabeça o nó (w). Os nós que definem os grupos são
ordenados em uma pilha (S) montada percorrendo-se a árvore em
profundidade e logo em amplitude. Outras ordenações dos nós wi são
possíveis desde que seja mantida a relação i < j se wi é o pai de wj.
Segunda etapa:
Somente a potência do nó h, isto é, π^(h) do nó cabeça do arco (g, h)
escolhido para entrar na árvore T é atualizado num pivoteamento do simplex.
Esse arco é escolhido pela equação de pseudo custo reduzido cvwπ^= cvw +
π(v) - π(w), onde as potências dos nós π^(u), u ∈ N, são valores
superestimados dos multiplicadores do simplex associados à árvore geradora
T, sendo nomeado como o nó 1 a raiz ou nó fonte. Os valores
40
superestimados dos multiplicadores são conhecidos como pré-
multiplicadores. (Orlin, 1995)
Para o arco (v, w) entrar na base, o seu pseudocusto reduzido (cvwπ^) tem que
satisfazer a condição cvwπ^< 0; onde as potências dos nós, (π^(u)) com u ∈ N,
são referenciadas como pré-multiplicadores com respeito a árvore T, em todo
o algoritmo, e os pseudocustos, cvwπ^≤0, para todos os arcos (v,w) ∈ T e, a
potência do nó raiz, π(1) = 0.
Terceira etapa:
Todos os arcos de um grupo B (wi) são analisados, e seus pseudocustos
reduzidos calculados. Se mais de um arco do conjunto B é elegível para
entrar na base, então, aquele arco com pseudocusto reduzido (cvwπ) mais
negativo é escolhido para entrar na árvore e um pivoteamento simplex é
realizado. Se wi = 1 é o primeiro nó na pilha gerada, a partir da árvore T,
chegou-se ao fim da iteração, isto é, ao fim da pilha S. Caso contrário, é
visitado o nó wi-1, isto é, se revisam os arcos do grupo B(wi-1), o grupo
predecessor do nó wi em T^.
A regra do pivoteamento do simplex acelerado é uma versão modificada da
regra de escolha do arco com a maior violação negativa (inward most
negative pivot) proposta por (Cunningham, 1979) e (Goldfarb et al., 1990b).
Este método inclui duas técnicas para a detecção de um ciclo negativo:
A primeira técnica:
Se a árvore T contém um ciclo de comprimento negativo, que não inclui o nó
1, então T é composta de duas ou mais componentes; e, uma delas, que
inclui o nó 1, é uma árvore com menos de n nós.
41
A segunda técnica:
Baseia-se no conhecido método proposto por Bellman-Ford-Moore que diz:
se, durante o k-ésimo passo, isto é, após uma análise completa de todos os
arcos da rede, as rotulações dos nós, de pelo menos n - k nós diminuem,
então a rede contém um ciclo negativo (Lawler, 1976), teorema 11.2. A
aplicabilidade desse critério no algoritmo simplex acelerado é justificada pelo
Lema:
Uma vez que T torna-se cíclica, ela permanecerá cíclica.
Diferente do teste para saber se g está em Dh, isto é, se g é descendente de
h, esse critério nem sempre detecta a criação de um ciclo negativo em um
pivoteamento. Entretanto, este teste é importante para estabelecer o limite do
número de pivoteamentos requeridos pelo algoritmo. A seguir é enunciada
propriedade de (Goldfarb et al., 1999) que reflete a observação acima mencionada.
Teorema:
“O algoritmo simplex para rede pode ser implementado para resolver o
problema de caminho mais curto realizando no máximo (n-1)(n-2)/2
pivoteamentos com uma complexidade, de pior caso, da ordem (nm).”.
4.2 – Representação do Método
Na figura 4.1 representa-se o fluxograma do simplex acelerado. Nesse
fluxograma observam-se duas importantes rotinas numa iteração k: A primeira
refere-se à rotina de melhoramento da solução, através de pivoteamentos sobre os
arcos não básicos, que violam as condições de otimalidade; e a segunda rotina que
informa que o arco não básico está na condição otimalidade, isto é, a solução atual
é ótima.
42
Enquanto ötimo= F
Monta ávore T, empilha nós
(S)|S|< n
Parar
Ótimo= VCalcular p (u)k= k + 1pivô= 0
Enquanto|S|<> 0
INÍCIO
h= último nó em S S= S - h
Calcular os custos reduzidos dos arcos
Cr(v,h),
Min Cr < 0
pivô= pivô + 1
Parar
Ótimo= FAtualizar p(u)T=T + (v, h) -
(g, h)
G contém um ciclo negativo
G contémCiclo negativo
Ler dadosMatriz de custos Vetor árvore TÓtimo= Fk= 0
N
Sim
Sim
Não
Sim
SimSim
Não
ão
Não
Não
h= s, ou pivô>= n -k
Fim
A árvore T é ótima
(Cr = cvwπ^ , p(u)= π^(u))
Figura 4.1 - Fluxograma do Método Simplex Acelerado
4.3 – Propriedades do Método
A seguir são apresentadas as propriedades mantidas durante toda a execução
do algoritmo, até encontrar uma árvore T ótima ou, que seja encontrado um ciclo
negativo.
i) cvwπ^≤ 0, para todos os arcos (v,w) ∈ T,
ii) π^(u)≥0, para todos os nós u ∈ T.
Quando um nó h é analisado para um possível pivoteamento.
iii) π ^(h) =π(h),
43
iv) cvh ≤ cvhπ^ para todos os arcos (v,h) ∈ B(h).
v) Uma vez que a árvore T se torna cíclica ela permanece cíclica.
Observações:
a) As propriedades (i) até (iv)podem ser pelo Lema1 de (Goldfarb et al., 1999).
b) A propriedade (v) é mostrada no Lema 2 de (Goldfarb et al., 1999).
4.4. – Cálculo do Número de Pivoteamentos
Para se estimar o número máximo de pivoteamentos realizados pelo
algoritmo simplex acelerado, até encontrar a solução ótima ou um ciclo negativo,
inicia-se a abordagem com um problema que tenha soluções viáveis. O método
simplex seqüencialmente atualiza árvores geradoras que vão melhorando os valores
dos pré-multiplicadores.
O algoritmo simplex acelerado é estruturado para realizar em cada iteração k
uma revisão completa em todos os conjuntos B(wi) da pilha. A pilha é identificada na
implementação deste algoritmo com a letra S.
Em um problema com solução, em cada iteração k, são realizados no máximo
n-k-1 pivoteamentos. Observa-se que a série gerada pelo número máximo de
pivoteamentos, em cada iteração, constitui uma progressão aritmética de razão –1,
onde, o primeiro termo é n-2, o segundo é n-3 e o último é zero. O número de
termos da progressão formada é n-1, que corresponde ao valor máximo que pode
assumir a variável k em um problema com solução ótima, ou com ciclo(s)
negativo(s). A soma dos termos desta PA fornece o número máximo de
pivoteamentos realizados pelo algoritmo, isto é (n-1)(n-2)/2.
4.5 – Cálculo da Complexidade do Método
Para estimar o tempo de execução requerido pelo algoritmo simplex
acelerado inicia-se com a contagem do tempo para:
1 - Formar árvore inicial do algoritmo com tempo de execução de O (m), no
caso geral;
44
2 - Percorrer T^, calcular π^ e realizar todas as operações em B(wi), toma um
tempo de O(n);
3 - Realizar todas as operações nos arcos, isto é, o cálculo e a comparação
dos pseudocustos reduzidos, o tempo de execução é de O(m);
4 - Armazenar a árvore T encontrada em cada pivoteamento (árvore atual),
toma um tempo da ordem O(1).
Como o número máximo de pivoteamentos é da ordem O(n2), e o número de
iterações k = n-1, a quantidade de trabalho realizado para atualizar as árvores
geradoras é no máximo de ordem O(n2), portanto a quantidade total do trabalho é de
ordem O(nm), assumindo que m>>n.
4.6 – O Algoritmo Simplex Acelerado
(Listagem do algoritmo em pseudocódigo:)
begin
escolha uma árvore inicial T^;
optimal ←false;
k←0;
while optimal=false do begin
T^←T;
Construa a pilha S de acordo com a ordem de visita aos nós de T^;
if |S| < n then pare ( T^=T contem um ciclo negativo);
calcule os multiplicadores do simplex p(u)=p^(u) correspondentes a T=T^ para todo u ∈ N;
k ←k + 1
pivots←0
optimal← true;
while S≠φ do begin
h← nó do topo de S, e remova-o de S;
if cghπ^ = min cvh
π^/(v, h)∉T < 0 then
begin
pivot ← pivot + 1;
if h=s ou pivots ≥ n - k then pare (ciclo negativo)
45
executar simplex
T ←T + g, h - pred(h), h
π^(h) ← π^(h) + cghπ^
optimal←false;
end;
end;
end;
end.
4.7 – Aplicação Numérica do Método
O exemplo utilizado para aplicação do método simplex acelerado
corresponde ao exemplo2-figura 6.16 da seção 6.4 pp [231] do livro Operations
Research. (Taha, 1997).
Encontrar o caminho mais curto do nó 1, para todos os demais de G(N, A),
onde |N|=7 nós e |A| = 16 arcos.
2
3
6
5
71 4
5
1
2
6
7
7
7
7
6
14
6
5
3
2
9
Figura 4.2 – Grafo. Exemplo. Fonte: Taha (1997)
Inicia-se a resolução do problema com a abstração da árvore geradora viável
To (1, v), mostrada na figura 4.2. No caso de não haver uma ligação direta entre os
nós 1 e v, arcos artificiais com custos penalizados, devem ser introduzidos em G. No
processo iterativo esses arcos artificiais devem sair da árvore T. No caso da solução
46
final apresentar algum arco artificial, o problema é inviável. Para garantir que esse(s)
arco(s) seja(m) retirado(s) da árvore T, durante o procedimento simplex, é usual
atribuir a cada arco artificial, um custo cujo valor seja maior que duas vezes a soma
de todos os custos do grafo, isto é, M= 2∑(v,w)∈A cvw.
1
4 5 3 6 7 2
0
5 1 M M M M
Figura 4.3 - Árvore inicial(To), com os multiplicadores (π) indicados ao lado de cada nó.
Para se construir a pilha S (ordem de visita aos nós de G), no passo k=0,
percorre-se a árvore T^o em profundidade na busca dos filhos e, em amplitude, na
busca dos irmãos, para montar a pilha S. A pilha encontrada é S= 1,2,3,4,5,6,7.
Os arcos (v, h)∉T, que formam os conjuntos B(wi), com o nó cabeça h, são:
B(7) = (4, 7), (5, 7), (6, 7);
B(6) = (2, 6), (4, 6), (5, 6);
B(5) = (2, 5), (3, 5), (4, 5);
B(4) = (2, 4), (3, 4);
B(3) = (4, 3);
B(2) = (3, 2), (6, 2)
B(1) = (0).
Com o nó que está no topo da pilha S inicia-se o método calculando-se os
custos reduzidos cp^π dos arcos do conjunto B(7).
cp^π (4, 7) = c(4, 7) + π(4) - π(7) = 6 + M - M > 0
cp^π (5, 7) = c(5, 7) + π(5) - π(7) = 9 + M - M > 0
cp^π(6, 7) = c(6, 7) + π(6) - π(7) = 2 + M - M > 0
Como os custos reduzidos dos arcos em B(7) são todos positivos, às
condições de otimalidade são satisfeitas. Portanto, nenhum dos arcos melhora o
caminho do nó 1 ao nó 7.
47
Analisando o conjunto B(6) e calculando os cp^π dos arcos do conjunto tem-
se:
cp^π (4, 6) = c(4, 6) + π(4) - π(6) = 4 + M - M > 0
cp^π (2, 6) = c(2, 6) + π(2) - π(6) = 6 + 5 - M < 0
cp^π(5, 6) = c(5, 6) + π(5) - π(6) = 5 +M - M > 0
Neste caso o arco (2,6), por contrariar as condições de otimalidade, é
candidato a entrar na árvore. O arco (pred(h), h) = (1, 6) é o arco a ser retirado. O
valor do pré-multiplicador é π^(6) = π^(6) + cp^π (2, 6)= Μ + 6 + 5 - ∞ = 11
Analisando o conjunto B(5) e calculando os cp^π dos arcos deste conjunto
tem-se:
cp^π (2, 5) = c(2, 5) + π(2) - π(5) = 1 + 5 - M << 03
cp^π (3, 5) = c(3, 5) + π(3) - π(5) = 7 + 1 - Μ < 0
cp^π(4, 5) = c(4, 5) + π(4) - π(5) = 3 + Μ - Μ > 0
Há dois arcos candidatos para serem escolhidos por contrariar as condições
de otimalidade. Neste caso é escolhido a arco (2,5), por apresentar o custo reduzido
mais negativo. O arco que sai é (1,5). O valor do pré-multiplicador π^(5)= π^(5) + cp^π
(2, 5)= Μ + 1 + 5 - M = 6
Analisando o conjunto B(4) e, calculando-se os cp^π dos arcos do conjunto, se
tem:
cp^π (2, 4) = c(2, 4) + π(2) - π(4) = 7 + 5 - M < 0
cp^π(3, 4) = c(3, 4) + π(3) - π(4) = 6 + 1 - Μ << 0
O arco escolhido para ser adicionado à árvore é (3,4). O arco a ser retirado é
(1,4). O valor do pré-multiplicador π^(4)= π^(4) + cp^π (3, 4)= M + 6 + 1 - M =7
Analisando o conjunto B(3) e calculando cp^π do arco (4,3), verifica-se que
este arco está na sua condição de otimalidade. Sua inclusão na árvore básica não
3 O mais negativo.
48
melhora o caminho do nó 1 até ele, portanto, permanece o arco atual, isto é, o arco
(1,3).
Analisando os arcos (3, 2) e (6, 2) do conjunto B(2), verifica-se que o custo
reduzido do arco (3, 2) é negativo (cp^π(3, 2) = c(3, 2) + π(3) - π(2) = 2 + 1 - 5 < 0), e
do arco (6, 2) é positivo. Nesse caso, o arco (3,2) é incorporado à árvore e é retirado
o arco (1,6). O valor do pré-multiplicador π^(2) = π^(2) + cp^π (3,2) = 5 + 2 + 1 – 5 = 3.
O conjunto B(1) é sempre um conjunto vazio, por se ter considerado o nó raiz
como o nó1.
A figura 4.4 mostra a nova árvore constituída pelos novos arcos que
melhoram as distâncias dos caminhos do nó 1 ao nó v.
1
3
2
5 6
4
7
0
1
3
4
7
9
M
Figura 4.4 - Árvore melhorada (T1), com os novos pré-multiplicadores.
Percorrendo-se a árvore da figura 5.4, constrói-se a seguinte pilha S =
1,3,2,6,5,4,7. Os novos conjuntos B(wi) são:
B(7) = (4,7), (5,7), (6,7);
B(4) = (2,4);
B(5) = (3,5), (4,5);
B(6) = (4,6), (5,6);
B(2) = (1,2), (6,2)
B(3) = (4,3);
B(1) = (0).
Aplicando a mesma rotina anterior para escolha do arco que contraria a sua
49
condição de otimalidade, para ser incorporado a árvore, tem-se:
i) No conjunto B(7) é escolhido o arco (5, 7) para entrar na árvore T1 , e sai o
arco (1, 7). O valor do pré-multiplicador π^(7) = π^(7) + cp^π (5,2) =13. Como os
arcos pertencentes aos conjuntos B(4), B(5), B(2) e B(3) atendem as
condições de otimalidade, estes são mantidos na árvore.
ii) Do conjunto B(6) apenas o arco (5,6) contraria a sua condição de
otimalidade, portanto, esse arco é adicionado em T1 e o arco (2,6) é retirado.
O pré-multiplicador π^(6) = 9.
iii) O conjunto B(1)= (0).
A nova árvore T2 é mostrada na figura 4.5, com a indicação dos novos
multiplicadores.
1
0
3
2 4
5
6 7
1
73
4
9 13
Figura 4.5 - Árvore T2, com a indicação dos novos pré-multiplicadores.
Da árvore T2, constrói-se a seguinte pilha S=1,3,2,5,6,7,4. Os conjuntos dos
arcos não básicos são:
B(4) = (2,4);
B(7) = (4,7), (6,7);
B(6) = (2,6), (4,6);
B(5) = (3,5), (4,5);
B(2) = (1,2), (6,2)
B(3) = (4,3);
B(1) = (0).
O arco do conjunto B(4) está na sua condição de otimalidade. Permanece em
50
T2, o arco atual. O arco (6,7), pertencente ao conjunto B(7), contrária à condição de
otimalidade; portanto, o arco (6,7) é adicionado à árvore T2 sendo retirado o arco (5,
7). O pré-multiplicador π^(7) = 11. Todos os arcos dos conjuntos B(5), B(2) e B(3)
atendem as condições de otimalidade, permanecendo na árvore os arcos atuais.
A nova árvore T3 é mostrada na figura 4.6.
1
0
3
2 4
5
1
73
4
69
711
Figura 4.6 - Árvore T3 com os novos pré-multiplicadores.
Da nova árvore cria-se a pilha S=1,3,2,5,6,7,4 e os conjuntos B(wi).
B(4) = (2,4);
B(7) = (4,7), (5,7);
B(6) = (2,6), (4,6);
B(5) = (3,5), (4,5);
B(2) = (1,2), (6,2)
B(3) = (4,3);
B(1) = (0).
Calculando-se os custos reduzidos dos arcos pertencentes aos conjuntos
B(wi) acima, verifica-se que todos arcos atendem as condições de otimalidade;
portanto, permanecem os arcos atuais e a árvore T3 é ótima.
Os multiplicadores indicados representam as distâncias mínimas dos
caminhos do nó 1 para cada nó v.
51
Tabela 4.1 - Análise do Número de Pivoteamentos
K Árvore Nós Pivoteamento
1 2 3 4 5 6 7 NMP NPR
0 T0 0 1 1 1 1 1 1 6 - 1 T1 0 3 1 3 2 2 1 5 4 2 T2 0 3 1 3 2 5 5 4 2 3 T3 0 3 1 3 2 5 6 3 1 4 T* 0 3 1 3 2 5 6 2 0 NMP – número máximo de pivoteamentos permitidos em um passo k. NPR – número de pivoteamentos efetivamente realizados.
Observa-se que o número máximo de pivoteamentos permitidos pelo método
para encontrar as distâncias mínimas, entre o nó raiz e todos os outros nós da rede,
ou um ciclo negativo é 15. Foram realizados ao todo 7(sete) pivoteamentos para
resolver este exemplo.
4.8 – Implementação do Método Simplex Acelerado
Esta seção apresenta as ferramentas de estrutura de dados e a explicação
dos nomes das variáveis utilizadas na codificação do algoritmo simplex acelerado
apresentado no APÊNDICE ΙΙΙ.
Seguindo o fluxograma mostrado na figura 4.1 desenvolvido a partir do
algoritmo simplex acelerado, foi percebido que a possível dificuldade na
implementação computacional do método, estaria no empilhamento dos nós. Este
empilhamento organiza a ordem em que os nós são visitados pelo método e é
importante na detecção de um ciclo negativo.
Devido a possível dificuldade, a prioridade foi desenvolver primeiramente as
rotinas envolvidas nesta parte do algoritmo.
4.8.1 – Descrição das Rotinas que Armazenam uma Árvore.
Em um primeiro momento foram construídos procedimentos utilizando apenas
estruturas simples como vetores e matrizes. No decorrer da modelagem foi
percebida a necessidade de se adicionar estruturas de dados mais complexas,
52
como pilhas e árvores-computacionais, trabalhando-se, portanto, com as variáveis
do tipo ponteiro.
Inicialmente foi adotado o seguinte procedimento com árvores binárias:
FE FD A
B C
D
A
B C
D
Representação computacional Representação no grafo
Figura 4.7- Armazenamento da topologia de uma árvore binária.
Esta árvore mostra o encadeamento hierárquico dos nós, onde cada nó
subseqüente ao nó atual é chamado Filho do nó atual e, conseqüentemente, o nó
hierarquicamente acima o Pai do nó atual. Este modelo de armazenamento gera
uma árvore-computacional binária que apresenta uma desvantagem, que como
pode ser visto na figura 4.7, um nó pode possuir apenas dois Filhos; um à direita e
outro à esquerda. Porém, em geral, os PCMC podem gerar árvores geradoras
(soluções básicas do simplex) não necessariamente binárias. Devido a este fato,
houve a necessidade de fazer uma nova utilização deste modelo binário visando a
representação de qualquer topologia de uma árvore, usando uma árvore-
computacional binária. Nesta implementação, quando um nó tem mais de dois
filhos, na representação árvore-computacional este nó aponta apenas para o filho,
cabendo a este filho, apontar para o seu irmão, e assim por diante. Esta
implementação é mostrada na figura 4.8.
53
F I A
B
C
A
C B
D
E
F
/
/
/
/ /
/
/
E
D
F
Representação computacional Representação num grafo
Figura 4.8- Nova estrutura de armazenamento em caso de árvores gerais.
Comparando estas duas implementações de armazenamento das topologias
de grafo das árvores, são obtidas as seguintes estruturas:
Primeira interpretação Segunda interpretação
Filho a
esquerda Dado
Filho
a
direita
1o
Filho Dado Irmão
Figura 4.9- Implementação considerando estruturas binárias.
Na implementação do simplex acelerado a PROCEDURE que armazena a
topologia de uma árvore é chamada de ALOCA (APÊNDICE ΙΙΙ). Essa rotina tem como parâmetro inicial alocar o nó escolhido como raiz da árvore.
Por exemplo: ALOCA (3), significa que o nó 3 é a raiz da árvore. Para a
construção da árvore-computacional o ALOCA baseia-se na topologia do problema,
isto é, o grafo da árvore geradora atual é interpretado a partir dos valores
encontrados no vetor-árvore, ou seja, a representação de uma árvore atual é
definida no início da execução do software através da inserção de valores no vetor-
árvore.
54
4.8.2- Exemplo Ilustrando a Implementação dos Critérios Mencionados na
Seção Anterior.
1 - O armazenamento de uma árvore
Uma árvore na rede será representada mediante um vetor, cujo valor inserido
numa POSIÇÃO do vetor, corresponde ao nó calda; e, a POSIÇÃO,
corresponde ao nó cabeça. Considere a árvore da figura 4.9.
3
5
4
1
2
6
Figura 4.10 – Topologia da árvore exemplo.
O vetor-árvore correspondente à topologia do grafo acima é:
POSIÇÃO 1 2 3 4 5 6
Conteúdo 2 3 0 3 2 2
2 - O procedimento de empilhamento
O procedimento chamado EMPILHAMENTO, como o nome sugere, faz o
armazenamento de uma ordem dos nós de uma árvore formando uma pilha
construída pela procedure ALOCA, de acordo com um critério de percurso. Este
percurso é feito a partir da raiz da árvore percorrendo-a em profundidade, isto é,
percorrendo todos os filhos do nó atual e, em seguida, por amplitude, colocando na
pilha os irmãos. No exemplo anterior então se obtém (figura 4.10). A árvore-
computacional está representada na figura 4.11.
55
F I
3
4
2
1
5
/
/
/
/
/ /6
Figura 4.11- A pilha
3- Na figura 4.12 representa-se o critério de percurso e armazenamento da árvore
da figura 4.9.
Figura 4.12- Percurso (ordem de visita aos nós)
OBS: Vale lembrar que esta estrutura é do tipo FILO4.
4 FILO: first in-last out significa uma estrutura de dados chamada PILHA
56
CONCLUSÃO
Nos dias atuais entender “bem” um algoritmo, que resolve uma gama de
problemas, é tão importante quanto desenvolver um novo algoritmo para resolver
um problema ainda não estruturado para o computador. Na ciência da computação
este entendimento gera novos avanços ou propostas que melhoram a eficiência de
um algoritmo, candidatando-o a novas aplicações, principalmente em sistemas que
demandam decisões em tempo real.
Durante a pesquisa foi observado que a performance de um algoritmo que
resolve problemas sobre redes, em geral, não depende somente da forma como o
algoritmo é desenvolvido e da seqüência de passos a serem executados, mas
depende, também, das estruturas de dados utilizadas para representar essa rede no
computador. Foi assim que observamos que quando se utiliza estrutura de dados
mais elaborada, melhora-se também o tempo de execução do algoritmo. Portanto, a
dualidade - estudo teórico e computacional - é necessária para tornar eficientes
algoritmos que resolvem problemas de otimização em redes.
Neste trabalho foi usada a matriz de adjacência para armazenar os dados de
uma rede para o problema de caminho mais curto, carregada com os valores das
distâncias, denominada de matriz de custo e um vetor para representar a árvore
inicial. Esse vetor, denominado de “vetor-árvore” (APÊNDICEΙ) foi proposto neste
trabalho para representar uma árvore geradora, com a vantagem de permitir que
qualquer nó da árvore possa assumir a condição de nó raiz. Esta proposta foi o
passo fundamental para a representação da topologia de árvore geradora usando a
estrutura de empilhamento, conforme visto na seção 4.8.
Na seção 4.5, foi mostrado que o método simplex acelerado apresenta uma
complexidade de pior-caso da ordem O (nm). Esta complexidade é equivalente a
complexidade do método BFM mostrada nos estudos dos pesquisadores (Denardo,
1979), (Dial et al., 1979) e (Van Vliet, 1978), conforme citados por (Syslo et al.,
1983). Na época, o método BFM foi considerado o mais eficiente método para
resolver o problema de caminho mais curto de um nó para todos os outros de uma
rede, por apresentar uma complexidade fortemente polinomial.
57
Nesta tese conforme foi proposto no artigo de (Goldfarb et al., 1999) verifica-
se que o método simplex para redes apresenta uma complexidade fortemente
polinomial para resolver o PCMC. Esta afirmação só é possível de constatar quando
os passos de execução do simplex ganham uma implementação que explora uma
estrutura de dados.
Para pesquisas futuras sugere-se:
Fazer um estudo e implementação do simplex acelerado para o PFCM onde é
necessário trabalhar com arcos capacitados e com limitantes inferiores para os
fluxos.
Fazer uma análise de complexidade do algoritmo tipo simplex acelerado para
o PFCM em comparação com o algoritmo primal-dual out-of-kilter para resolver o
dito problema.
60
REFERÊNCIAS BIBLIOGRÁFICAS
Ahuja, R. K; Magnanti, T. L; Orlin, J. B. Network Flows, Theory, Algorithms
and Applications. Prentice-Hall, Inc, 1993.
Baase, S. Computer Algorithms – Introduction to Design end Analysis.
Second Edition, Library of Congress Catalog in Publication Data,
USA/Canada-1988.
Bazaraa M. S; Sherrali, H. D. and Shetty C.M. Linear Programming Theory
and Algorithms. John Willey end Sons, Inc, 1990.
Bellman R. On a Route Problem. Quarterly Applied Mathematics 16 pp.[87-
90], 1958.
Campello R. E. e Maculan, N. Algoritmos e Heurísticas –Desenvolvimento e
Avaliação de Performance. Editora da UFF-RJ, 1994.
Cormen, T. H; Leiserson C. E and Rivest R. L. Introduction to Algorithms C.
The Massachusetts Institute of Technology, 1990.
Cunningham, W. A Network Simplex Method. Math. Programming11 pp
[105-116], 1976.
Dantizig, G.B. Discrete–Variable Extremum Principles. Operations
Research, Vol.5 pp[266-277], 1957.
Denardo, E V; Fox, B L; Shortest-Route Methods: 2. Reaching, Pruning, and
Buckets. Operations Research, Vol. 27, pp[161-186], 1979a.
Denardo, E V; Fox, B L; Shortest-Route Methods: 1. Group Knapsacks,
Expanded Networks end Branch-and-Bound. Operations Research, Vol.
27, pp[548-566], 1979b.
Dial, R B. Algorithm 360: Shortest Path Forest with Topological Ordering.
Communications of the ACM Vol. 12, pp[632-633], 1969.
Dijkstra, E W. A Note on Two Problems in Connexion with Graphs.
Numerishe Matematik Vol. 1, pp[269-271], 1959.
Ford, L R. Network Flow Theory. The Rand coporation Report P-923, Santa
Mônica, CA, 1956.
Goldbarg, M. C.; Luna, H. P. L. Otimização Combinatória e Programação
Linear – Modelos e Algoritmos. Editora Campus, 2000.
Goldfarb, D. and Jin, Z. An O(nm) Time Network Simplex Algorithm For the
Shortest Path Problem. Operations Research, Vol.47, N0 3, pp [445-448],
61
May-Jun-1999.
Goldfarb, D; Hao, J. and Kai, S-R. Efficient Shortest Path Simplex
Algorithms. Operations Research, vol. 38 No 4, pp. [624-628], July-
August, 1990a.
Goldfarb, D; Jianxiu, H; Kai, S-R. Anti-stalling Pivot Rules for the Network
Simplex Algorithm. Netwoks-Vol.20 Pp 79-91-John Wilev and Sons, Inc-
1990b.
Khachian, L. G. A Polynomial Algorithm in Linear Programming, Soviet
Mathematics Doklady, 20, pp[191-194], 1979.
Khachian, L. G. Polynomial Algorithms in Linear Programming, USSR
Computational Mathematics and Mathematical Physics, 20, pp[53-72],
1980.
Klee, V.; Minty, G.J How Good is the Simplex Algorithm? In O. Shisha Ed.,
Inequalities ΙΙΙ, Academic, pp[159-175], New York, 1972.
Koogan, A; Houaiss, A. Enciclopédia Dicionário Ilustrado-4a Edição, Rio de
Janeiro.
Lawler, E L. Combinatorial Optimization: Networks and Matroids. Holt,
Rinehart and Winston, New York, 1956.
Monma, C. L.and Segal, M. A Primal Algorithm for Finding Minimum Cost
Flows In Capacitated Networks With Applications. The Bell System
Technical Journal-Vol. 61 No. 6, July-August 1982.
Moore, Z F. The Shortest Path Through a Maze. Proc. Internat. Sympos. On
Theory of Switching, Part ΙΙ. Pp[285-292], 1957.
Orlin B. J. A Polynomial Time Primal Network Simplex Algorithm For
Minimum Cost Flows. The Mathematical Programming Society Inc,
Published by Elsevier Science B.V-pp [109-127], 1997.
Pape, U. Implementation and Efficiency of Moore- Algorithms for the
Shortest Route Problem. Mathematical Programming Vol. 7, pp[212-222],
1974.
Pape, U. Algorithm 562: Shortest Path Lenghts, ACM Trans. Math. Software
Vol. 5, pp[450-455], 1880.
Syslo, M. M; Deo, N. and Kowalik, J. Discrete Optimization on Algorithms
with Pascal Programs. Prentice Hall, Inc, Englewood Cliffs, New York
1983.
62
Taha, H. A. Operations Research: An Introduction. Prentice Hall Inc, 6th
Edition-1997.
Van Vliet, D. Improved Shortest Path Algorithms for Transport Network.
Transportation Research Vol. 12, pp[7-20], 1978.
Veloso, P; Dos Santos, C.;Azeredo, P; Furtado, A. Estrutura de Dados.
Editora Campus, 3a Edição, Rio de Janeiro, 1983.
Wright, S. J. Interior Points Methods. Published SIAM-Philadelphia –1997.
63
APÊNDICE ΙΙΙΙ
TÓPICOS DE TEORIA DE REDES
I.1 - O Problema de Fluxo de Custo Mínimo (PFCM)
Um grafo é representado por G(N, A), onde N é um conjunto finito de
elementos chamados nós 1, 2, 3..., n, e A um conjunto de pares de elementos do
conjunto de nós, chamados arcos: 1, 2, 1, 3, 2, 3,...,.
Um grafo orientado, também chamado de dígrafo, está definido da mesma
forma, exceto que os arcos são pares ordenados, de forma que sua direção está
definida pela ordem do par; a primeira componente é o nó de saída e a segunda o
nó de chegada.
Um arco (i, j) é dito ser incidente para os nós i e j, se esse arco é orientado do
nó i para o nó j. O número de nós e o número de arcos de um grafo G(N, A) são
representados por n= |N| e m= |A| respectivamente.
A cada nó i do grafo G é associado um número bi que pode ser interpretado
como uma oferta no nó se bi > 0 e, uma demanda, se bi < 0. Se bi = 0 pode-se
interpretar como um nó que não exporta e nem consome produto importado; nesse
caso, é chamado nó intermediário (ou nó de transbordo).
Quando os arcos (i, j) de um grafo G(N,A) é atribuído uma quantidade de
fluxo de produto xi j ≥ 0, e/ou um custo cij que corresponderia ao custo unitário do
produto transportado no arco, esse grafo, é conhecido com o nome de rede . Numa
formulação matemática de redes, assume-se que toda a produção na rede é
consumida na própria rede; isto é, ∑ bi = 0. Em caso contrário, se usa a seguinte
estratégia: se, ∑ i=1n bi > 0, é adicionado na rede, um nó fictício n+1, com uma
demanda bn+1 = - ∑ i=1n bi segundamente ligando este nó fictício, aos nós de ofertas,
por arcos com custo zero.
A formulação matemática, do PFCM, é interpretada como:
64
“Transportar a produção disponível em um nó, através de uma rede, satisfazendo a
demanda e, com custo mínimo”.
O problema é formulado como:
Min ∑i =1n ∑j = 1
n ci j xi j
Sujeito a:
∑j = 1n xi j - ∑k = 1
n x k i = bi ⇒ i = 1, 2, 3,..., n
xi j ≥ 0 ⇒ i, j = 1, 2, 3,..., n
As restrições são conhecidas como leis de conservação de fluxos ou Leis de
Kirchhoff e indicam que a rede não cria nem destrói o fluxo. Uma rede onde os
fluxos apresentam apenas restrições de não negatividade é chamada de rede não
capacitada. Caso contrário, se os fluxos são limitados, a rede é chamada de
capacitada.
A figura Ι.1 mostra uma configuração de uma rede direcionada (dígrafo) G
(N, A), com n = 4 nós e m = 7 arcos.
1 4
3
2
Figura I.1 - Exemplo de uma rede. Fonte Bazaraa (1990).
65
I.2 - Definições e Terminologia da Teoria de Grafos.
A seguir são apresentadas algumas definições e terminologias de Teoria de
Grafos que ajudarão na interpretação dos fatos descritos no trabalho.
GRAFO PRÓPRIO
Um grafo G(N, A), onde N representa o conjunto de nós; e, A o conjunto de
arcos é dito próprio, se as cardinalidade de N e A satisfazem N≥ 2 e A≥ 1.
NÓS ADJACENTES OU CONECTADOS
Dois nós em um grafo são adjacentes ou conectados, se eles estão ligados
diretamente por algum arco.
ARCO ORIENTADO
O arco (i, j) ∈ A é orientado, se o nó i é o início do arco e, o nó j é o seu
término.Respeita-se sua direção. Essa situação é representada por uma seta, e i é
chamado nó calda do arco (i, j) e j o nó cabeça.
ARCOS QUE PARTEM DE UM NÓ (FORWARD STAR)
Dado um nó i, e o conjunto de nós j que formam os arcos (i, j), o grafo
formado por esses nós e arcos, é chamado de grafo estrela fornecedora(forward
star).
ARCOS QUE CHEGAM A UM NÓ (BACKWARD STAR)
Dado um nó i e o conjunto de nós j, que formam os arcos (j, i), o grafo
formado por esses nós e arcos é chamado de grafo estrela coletora (backward star).
66
ARCO NÃO ORIENTADO
É o arco que no grafo não tem uma direção explícita. Assume-se que permite
fluxo nas duas direções.
GRAFO DIRECIONADO, NÃO DIRECIONADO E MIXTO.
Um grafo é direcionado, ou um dígrafo, quando todos os seus arcos são
orientados; isto é, existe uma direção determinada no caminho, entre cada par de
nós. O número máximo de arcos ou arestas em um grafo direcionado com n nós é
n(n-1).
Um grafo é dito não direcionado quando não apresenta uma orientação
definida para os arcos, isto é, assume-se a existência dos arcos (i, j) e (j, i). O
número máximo de arcos não direcionados em um grafo de n nós é n(n-1)/2.
Um grafo mixto contém, tanto arcos orientados, como arcos não orientados.
GRAFO CONEXO OU CONECTADO
Um grafo não direcionado é dito conexo se existe uma seqüência de
arcos ligando qualquer par de nós do grafo G.
GRAFO COMPLETO
Um grafo não direcionado é dito grafo completo se, qualquer nó está ligado
com todos os nós de G: isto é de cada nó partem n-1 arcos. Observar que um grafo
completo é conexo.
SUBGRAFO
Um grafo G’(N’, A’) é um subgrafo do grafo G(N, A) quando satisfaz as
condições: N’⊆ N e A’⊆ A com a compreensão que, se (i, j)∈A’, então i e j estão em
N’. Quando G’≠G é chamado de um subgrafo próprio de G.
67
COMPONENTE DE UM GRAFO
Uma componente de um grafo G (N, A) é um subgrafo conectado que
é um subgrafo próprio de G. Componentes são subgrafos com máxima
conectividade de partes separadas de um grafo. Na figura Ι.1 retirando os arcos (1,
2), (1, 3) e (4, 1) o grafo resultante tem duas componentes; ou seja, o nó 1 é o
subgrafo constituído dos nós 2, 3 e 4 e arcos (2, 3), (2, 4), (3, 2) e (3, 4).
SUBGRAFO GERADOR
Um subgrafo G’(N’, A’) de G(N,A) é um subgrafo gerador quando pode conter
todos os nós do grafo G. (N’=N).
SUBGRAFO INDUZIDO
Um subgrafo G’(N’, A’) de G(N, A) é induzido pelo conjunto de nós N’ se, A’
contém todos os arcos de A que tem seus nós presentes em N’. Na figura Ι.1, por
exemplo, o subgrafo induzido pelo conjunto de nós N’= 1, 2, 4 é o grafo com os
nós 1, 2 e 4 com o conjunto de arcos A’= (1, 2), (2, 4), (4, 1).
CAMINHO
Caminho do nó io para o nó ip é uma seqüência de arcos orientados P = (io,
i1), (i1, i 2), (i p - 1, ip) onde o nó inicial de cada arco é o mesmo nó terminal do arco
anterior na seqüência io , ..., ip com todos os nós distintos. Um caminho (io, ip) é
chamado aberto se io≠ ip, e caminho fechado se io= ip.
CADEIA OU ELO
Cadeia ou elo é uma seqüência de nós ligados, por arcos, alguns deles
tomando direções contrárias.
68
CIRCUITO
É uma seqüência de nós ligados por arcos com a mesma direção, com o nó
final ligado ao nó inicial por um arco com a mesma direção. Circuito é um caminho
direcionado fechado.
CICLO
É um caminho (io, io), onde, nenhum nó, exceto do subíndice é repetido. Um
ciclo contém no mínimo três arcos. Um grafo sem ciclo é chamado de acíclico.
OBSERVAÇÃO:
Em um problema de fluxo de custo mínimo o grafo em estudo é conectado,
isto é, cada par de nós de G(N, A) ligado por uma cadeia. Os grafos que
apresentam estas características são conhecidos como grafos fracamente conexos.
Um grafo é fortemente conexo quando existe um caminho direto entre cada nó para
qualquer outro nó.
ÁRVORE
É um grafo conexo, sem ciclos.
FOLHAS
São os nós mais externos da árvore que não possuem descendentes, isto é,
é a última geração de uma árvore.
GRAU DE UM NÓ
Em um grafo e orientado, o grau de um nó é o número de arcos que incidem
no nó. Em um grafo orientado é a soma da quantidade de arcos que chegam no nó
e a quantidade de arcos que saem do nó. Um nó de grau zero é um nó isolado e um
nó de grau 1 pode ser associado aos nós folhas de qualquer árvore.
69
ÁRVORE GERADORA (SPANNING TREE)
Árvore geradora de um grafo G(N, A) é uma árvore que inclui cada nó do
grafo, gerando um subgrafo com a máxima conectividade, e sem ciclos.
ÁRVORE GERADORA COLETORA (SPANNING IN TREE)
É uma árvore onde o nó raiz é considerado um sumidouro ou, consumidor de
fluxos.
ÁRVORE GERADORA FORNECEDORA (SPANNING OUT TREE)
É uma árvore onde o nó raiz é considerado uma fonte ou, um fornecedor
fluxos.
I.3- Representação de um grafo.
Uma das formas de melhorar a performance de um algoritmo para redes
depende da maneira como essa rede pode ser armazenada, processada e
atualizada computacionalmente. Estruturando-se melhor os dados de entrada e
atualização para o processamento, melhora-se o tempo final de execução do
algoritmo.
Para representar uma rede no computador são necessários dois tipos de
informações: a primeira informação se refere à topologia que corresponde ao
desenho da rede, isto é, pelas ligações entre os nós e arcos e, a segunda pelos
dados associados aos arcos e nós (custo, capacidade, oferta/demanda). Um grafo
direcionado pode ser representado por diversos tipos de estruturas, mas, neste
apêndice são abordados apenas os tipos de estruturas utilizadas na representação
dos dados de entradas de uma rede.
70
ΙΙΙΙ.3.1- Matriz de adjacência
Nessa estrutura matricial o grafo direcionado é representado por uma matriz
quadrada H(nxn), onde cada nó está representado por uma linha e por uma
coluna, apresentando na i-ésima linha uma entrada hij =1, se (i, j)∈ A e, zero em
caso contrário. Desejando-se armazenar custos, capacidades e a topologia da rede,
essas informações devem ser representadas numa só matriz quadrada (nxn). Uma
matriz de adjacência tem n2 elementos e, somente m entradas da matriz são
diferentes de zero. Essa representação é eficiente para redes densas.
ΙΙΙΙ.3.2- Matriz de incidência nó-arco
A matriz de incidência representa as restrições de uma formulação como um
problema de programação linear do PFCM. Essa representação armazena a rede
como uma matriz A de ordem nxm que contém uma linha para cada nó da rede e
uma coluna para cada arco. A coluna que corresponde ao arco (i, j) apresenta
somente dois elementos diferentes de zero: +1 na linha correspondente ao nó i e -1
na linha correspondente ao nó j . As demais linhas são completadas com zero. Das
nm entradas da matriz de incidência apenas 2m entradas são não zeros. O número
de entradas +1 na linha i fornece o grau de arcos de entradas no nó i, enquanto,
entradas -1 fornece o grau de arcos que saem do nó. O grau do nó i é a soma das
entradas diferentes de zero na linha i.
Na matriz de incidência nó-arco, cada coluna da matriz A é representada
vetorialmente por aij = ei - ej, onde ei e ej são vetores unitários em En.
ΙΙΙΙ.4- Vetor- árvore
Ao preparar o código do algoritmo simplex acelerado foi preciso definir uma
estrutura para representar a topologia de uma árvore geradora.
Vetor-árvore é um array [1 ... n] , onde n=|N| representa o conjunto de nós da
árvore. Cada valor numa posição do vetor representa o nó origem ou, de
precedência do arco cujo nó final corresponde a aquela posição .
71
1
2
4
3 0 1 2 2
1 2 3 4i =
vetor árvore
Na figura acima, observar que a representação do grafo em um vetor árvore o
nó 1 precede o no 2 e os nós 3 e 4 são precedidos pelo no 2. O nó 1 é a raiz.
ΙΙΙΙ.5- Propriedades das árvores
Propriedade 1
Seja T uma árvore própria de um grafo, isto é, com n≥2 nós e (i, j) ∈ T. Se,
um arco (i, j) é removido de T, mas permanecendo os nós i e j, a árvore é
decomposta em duas subárvores T1 e T2.
Propriedade 2
A representação do vetor-árvore representa qualquer árvore utilizando menos
espaço de armazenamento.
Propriedade 3
Uma árvore de um grafo G, com n nós, é constituída por n -1 arcos.
Propriedade 4
Seja T é uma árvore de um grafo G(N, A), N = n, A = m.
As seguintes proposições são equivalentes:
• T é conectada e não tem ciclos.
• T é conectado e tem n-1 arcos.
• T tem n-1 arcos e nenhum ciclo.
• T é conectado, mas, removendo qualquer arco de T resulta em duas
componentes.
• T não tem ciclos, mas, adicionando qualquer novo arco em T, resulta num
grafo com exatamente um ciclo.
• T tem uma única cadeia conectando cada par de seus nós.
72
I.6- Posto da matriz de incidência nó-arco.
Esta matriz está mais associada ao algoritmo simplex para redes e tem posto
n-1. Esta propriedade é demonstrada por (Bazaraa et al., 1990) pp. [425-430].
Define-se como nó raiz de um grafo ao nó associado a um arco “aberto”, isto
é, o arco iniciado no nó raiz, mas sem ser conectado a nenhum outro nó de G. A
variável correspondente ao fluxo xi nesse arco tem valor zero. Essa variável,
chamada artificial, completa o posto da submatriz associada ao PFCM; e, com esse
artifício, cria-se uma solução básica para o simplex. Observar que o nó raiz de um
grafo é diferente do nó raiz de uma árvore, que foi usado neste trabalho nas
implementações do método simplex para redes.
O algoritmo simplex para rede busca a solução ótima ou, encontra um ciclo
negativo, iniciando o processo com uma solução básica inicial que corresponde a
matriz de incidência nó-arco A abstraída das restrições do problema e, como foi dito,
é uma matriz de posto incompleto, isto é, n-1. Para completar o seu posto uma
variável artificial é requerida para completar o posto desta matriz, isto é, posto n. A
matriz de restrição estendida é representada por (A, em). Aqui, em é um vetor
canônico associado ao nó e um arco raiz que forma a variável artificial para o
método simplex. Na matriz de restrições estendida pode-se achar as matrizes
básicas B para o simplex.
Cada matriz básica em um problema de fluxos em redes forma uma árvore
geradora enraizada do grafo G. Essas árvores geradoras apresentam as
propriedades descritas na seção I.3. A seguinte propriedade faz a ligação de um
grafo G(N, A) representado por uma matriz nó-arco estudada(A, em).
“Se o problema de fluxo de custo mínimo é representado em um grafo
conexo, com um arco aberto (arco raiz), então, a matriz B é uma base para esse
problema se, somente se, essa matriz for uma matriz de incidência nó-arco de uma
árvore geradora do grafo”.
Esta matriz básica B é constituída de elementos ±1 ou 0, e pode ser
arranjada na forma triangular inferior ou superior, com +1, -1 nas diagonais, portanto
73
a matriz apresenta as seguintes características: triangularidade, integralidade e
unimodularidade e, isto implica em:
• Os sistemas de equações BxB = b e wB = cB que determinam os
valores das variáveis básicas xB e, das variáveis duais (w), conhecidas
como multiplicadores do simplex, podem ser resolvidos diretamente na
rede.
• A solução de BxB = b é inteira.
• A matriz B é dita ser totalmente unimodular porque se cada submatriz
quadrada de B possuem, determinantes cujos valores podem ser
somente +1, -1, ou 0.
As restrições do problema, mostradas na figura I-1, formam uma matriz de
incidência nó-arco de posto n-1 conforme dito anteriormente.
Para completar o posto dessa matriz é introduzida uma raiz artificial,
formando uma base para o simplex para redes, isto é, cada solução básica xB do
simplex é obtida da matriz estendida (A, em), onde em é um vetor canônico, que
representa a posição da variável artificial na coluna da matriz.
Os sistemas BxB = b e wB=cB que calculam as variáveis primais, isto é, os
fluxos sobre redes, e as variáveis duais correspondentes a uma árvore geradora
podem ser resolvidas facilmente porque a matriz A é unimodular. Adicionalmente os
cálculos necessários para resolver BxB=b têm sido identificados com os cálculos
realizados diretamente no grafo, num procedimento que se inicia nos nós folhas da
árvore xk,folha= bfolha em direção à raiz. Analogamente, para se calcular wB= cB o
procedimento sobre grafo se inicia no nó raiz, associando o valor wraiz = 0 então, as
outras (n-1) variáveis duais são facilmente encontradas. Estes procedimentos
podem ser representados pelas figuras I-3 e I-4. (Mas detalhes sobre o assunto
podem ser encontrados em Bazaraa et al., 1990).
74
ΙΙΙΙ.7- Representação Vetorial de um Arco Não Básico em Função dos Arcos
Básicos.
Na figura I-2, é mostrado a adição do arco não básico (1, 2), na árvore
geradora abstraída do grafo da figura I-1.
1
2
3
4
Figura I-2 - Exemplo de árvore geradora do grafo I-1, com a introdução do arco (1,2). Fonte: Bazaraa
(1990).
A soma dos vetores, seguindo a direção do arco (1, 2) é:
a12 + a23 - a13 = 0
Explicitando o arco a12 em função dos arcos básicos, a12=a13-a23. Escrevendo
os vetores a13, a23 na sua forma canônica, a12 = (e1-e3) -(e2-e3), portanto,
a12 = e1 - e2
Folha Folha
Folha
r
l
j
k
Raiz
Figura I-3 - Calculo dos valores das variáveis básicas (fluxo). Fonte: Bazaraa (1990).
75
Folha Folha
Folha
r
l
j
k
Raiz
Figura I-4 - Calculo dos valores das variáveis duais. Fonte: Bazaraa, (1990).
ΙΙΙΙ.8- Cálculo dos Custos Reduzidos no Problema de Fluxos em Redes.
Os custos reduzidos zij - cij dos arcos não básicos, para saber qual deles
violam as condições de otimalidade, isto é, para se identificar um possível candidato
para entrar na árvore, são calculados pela equação:
zij-cij=waij - cij = w(ei - ej) - cij= wi -wj-cij , onde w (variáveis duais) são
referenciados em problemas de fluxos em redes como potencias dos nós.
(Bazaraa et al., 1990) apresenta como condições de otimalidade, em um
problema de minimização, a máxima violação positiva das condições de otimalidade;
isto é, o arco candidato para entrar na base apresentará a maior positividade entre
os arcos candidatos. Sendo assim, os custos reduzidos dos arcos não básicos são
calculados pela equação: zij - cij = wi - wj - cij.
Na tese foi adotado como critério de otimalidade a máxima violação negativa,
isto é, o candidato para entrar na árvore apresenta a maior negatividade entre os
arcos candidatos. Nesse caso, os custos reduzidos dos arcos não básicos serão
calculados pela equação: zij - cij = cij - wi + wj .
76
APÊNDICE ΙΙΙΙΙΙΙΙ
PROGRAMA EM PASCAL DO MÉTODO BFM
Fonte: Syslo (1983). Adaptado.
Uses crt, dos;
Var
n, m, s, inf : integer;
pointer : array[1..100] of integer;
endv, wt : array[1..100] of integer;
dist, pred, queue : array[1..100] of integer;
u, v, head,
next, first,
last, j,
newlabel,
temp, i : integer;
simnao : string;
procedure BFM;
begin
writeln(''); writeln ('');
writeln('entre com os valores de m, n, s e inf');
writeln ('');
write('m = ');readln (m);
write('n = ');readln (n);
write('s = ');readln (s);
write('inf = ');readln (inf);
writeln(''); writeln ('');
writeln ('entre com o vetor pointer');
for i:=1 to m+1 do
begin
write ('[',i,'] = '); read (pointer[i]);
end;
77
writeln(''); writeln ('');
writeln ('entre com o vetor endv');
for i:=1 to n do
begin
write ('[',i,'] = ');read (endv[i]);
end;
writeln(''); writeln ('');
writeln ('entre com o vetor wt');
for i:=1 to n do
begin
write ('[',i,'] = ');read (wt[i]);
end;
writeln(''); writeln ('');
writeln ('entre com o vetor dist');
for i:=1 to m do
begin
write ('[',i,'] = ');read (dist[i]);
end;
writeln(''); writeln ('');
writeln ('entre com o vetor pred');
for i:=1 to m do
begin
write ('[',i,'] = ');readln (pred[i]);
end;
for v:=1 to m do
begin
dist[v]:=inf; (* inf=é o peso de um arco inexistente *)
78
pred[v]:= -1;
queue[v]:= -1
end;
dist[s]:=0; head:=s; u:=s;
queue[head]:=inf; (* v é o último item da fila *)
(* initialization over *) (* se queue(v) = inf. *)
while u<> inf do (* a fila está vazia se u = inf *)
begin
next:=queue[u];
queue[u]:=0;
first:=pointer[u];
last:=pointer[u+1]-1;
for j:=first to last do (* fazer para cada arco (u, v) tal que inicia em u *)
begin
v:=endv[j];
newlabel:=dist[u]+wt[j];
if dist[v] >newlabel then (* mudar rótulo *)
begin
pred[v]:=u;
dist[v]:=newlabel;
temp:=next;
if queue[v]<0 then (* o nó v nunca esteve na fila *)
begin
queue[head]:=v;
head:=v;
queue[head]:=inf;
if temp=inf then temp:=v;
next:=temp;
79
end
else if queue[v]=0 then (* v was in queue, but *)
begin (* not in queue now *)
queue[v]:=temp;
next:=v
end
else next:=temp (* v is in queue *)
end; (* dist[v] > newlabel *)
end; (* j *)
u:=next;
end; (* while *)
clrscr;
write ('a solucao otima encontrada e');
writeln ('');
writeln ('');
writeln ('');
for i:=1 to m do
begin
write (dist[i]:6);
end;
writeln('');
writeln('');
for i:=1 to m do
begin
write (pred[i]:6);
end;
writeln ('');writeln ('');
write ('deseja otmizar outro, s/n ');
80
read (simnao);
if (simnao='s') or (simnao='s') then pdm;
end;
begin
clrscr;
writeln ('deseja gravar em disco os dados e o resultado?, s/n');
read (simnao);
if (simnao='s') or (simnao='s') then
BFM;
end. (* BFM *)
81
APENDICE ΙΙΙΙΙΙΙΙΙΙΙΙ
PROGRAMA PASCAL DO MÉTODO SIMPLEX
ACELERADO5
PROGRAM Simplex_Acelerado;
USES winCRT;
TYPE
pont = ^no;
no = record
dado : integer;
filho : pont; aponta para o primeiro filho
irmao : pont; aponta para o irmão seguinte
end;
PontPilha = ^pilha;
pilha = record
dado : integer;
Ant : PontPilha; aponta para o imediatamente anterior na pilha
end;
Cada nó(pai) pode ter vários filhos. Mas, a implementação é feita por uma árvore
binária e, se um nó possui vários filhos, esse nó aponta somente para o primeiro
filho, e este, aponta para o irmão seguinte que, por sua vez, aponta para outro irmão
e assim por diante. O ultimo irmão de uma seqüência tem seu campo 'irmão'
apontando para NIL. Os nós folha tem seu campo “filho” apontando para NIL.
vet = array[1..100] of integer;
mat = array [1..100,1..100] of integer;
5 Fonte: Programa preparado pelo autor e com a excelente colaboração de Dos Santos, A .J (Agosto,
2001).
82
VAR
raiz, novo, aux : pont;
nuevo,topo, auxPilha, auxP : PontPilha;
vetor, PotN : vet;
MatCusto : mat;
n, k, h, cr, NoMenor,NNP, Menor, pivo : integer;
otimo : boolean;
Function ContPilha : integer;
var
Pp : PontPilha;
CountP: integer;
begin
Pp := topo;
countP := 0;
while Pp <> nil do
begin
Inc (countP);
Pp := Pp^.ant;
end;
ContPilha := CountP;
end;
Procedure aloca (procura : integer);
var
Estas três variáveis devem ser locais
i : integer;
prim_filho_alocado : boolean;
atual : pont;
Begin
83
prim_filho_alocado := false;
for i := 1 to n do
begin
if vetor[i] = procura
then
begin
if raiz = NIL aloca o primeiro ponteiro
then
begin
new(novo);
novo^.dado := i;
novo^.filho := NIL;
novo^.irmao := NIL;
raiz := novo;
atual := novo;
end
else aloca os ponteiros diferentes do primeiro
begin
if prim_filho_alocado = false aloca o primeiro filho
then
begin
new(novo);
atual^.filho := novo;
novo^.dado := i;
atual := novo;
atual^.irmao := NIL;
atual^.filho := NIL;
prim_filho_alocado := true;
end
else aloca os outros irmãos diferentes do primeiro filho
begin
new(novo);
atual^.irmao := novo;
novo^.dado := i;
84
atual := novo;
atual^.irmao := NIL;
atual^.filho := NIL;
end;
end;
aloca(i); a chamada recursiva é a alma do programa
end;
end;
end;
Procedure EncherVetorArvore;
var ind : integer; variável criada para ser o índice do for
begin
clrscr;
writeln ('============ ENCHENDO O VETOR ARVORE ================');
writeln;
writeln;
writeln;
for ind:= 1 to n do
begin
gotoxy((ind+5)*4, 5);
read (vetor[ind]);
end;
end;
procedure MostrarVetorArv;
var indi :integer;
begin
writeln ('============= VETOR ARVORE FINAL ============= ');
writeln;
writeln;
writeln;
85
for indi:= 1 to n do
begin
gotoxy((indi+5)*4, 5);
write (vetor[indi], ' ');
end;
end;
procedure MostrarVetorArv2;verificação dos pivoteamentos
var indi :integer;
begin
for indi:= 1 to n do
begin
write (vetor[indi], ' ');
end;
end;
Procedure MontarMatrizCusto;
var l,c : integer; l = linha ; c = coluna
begin
clrscr;
writeln ('=========== ENTRE COM A MATRIZ DE CUSTOS
================');
writeln ;
writeln ;
for l := 1 to n do
begin
for c := 1 to n do
begin
gotoxy((c+5)*4, l+5);
read (MatCusto [l,c]);
end;
end;
86
writeln;
writeln;
end;
Procedure Empilhamento (atual2 : pont);
begin
salvando na pilha
new (nuevo);
nuevo^.dado := atual2^.dado;
nuevo^.ant := topo;
topo := nuevo;
Rastreando a árvore
if (atual2^.filho <> nil) then Empilhamento (atual2^.filho);
if (atual2^.irmao <> nil) then Empilhamento (atual2^.irmao);
end;
Procedure MostrarPilha;
begin
auxPilha := Topo;
writeln (' ====================== MOSTRANDO A PILHA
================== ');
writeln;
writeln;
while auxPilha <> NIL do
begin
writeln ( auxPilha^.dado);
auxPilha := auxPilha^.ant;
end;
end;
procedure CalcPotN (comeca, avo : pont);
87
begin
if (comeca^.filho <> Nil) then
begin
PotN [comeca^.filho^.dado] := PotN [comeca^.dado] + MatCusto [comeca^.dado ,
comeca^.filho^.dado];
CalcPotN (comeca^.filho, comeca);
end;
if (comeca^.irmao <> Nil) then
begin
PotN [comeca^.irmao^.dado] := PotN [avo^.dado] + MatCusto [avo^.dado ,
comeca^.irmao^.dado];
CalcPotN (comeca^.irmao, avo);
end;
end;
Procedure CalcCustoReduzido;
var
cont: integer; para indice
begin
menor := 10000; menor deve ser um número grande para garantir que
for cont :=1 to n do o primeiro a entrar seja menor
begin
cr := MatCusto[cont,h] + PotN[cont] - PotN[h];
if cr < menor then
begin
menor := cr;
NoMenor := cont;
end;
end;
end;
88
procedure MostrarPotNFinal;
var ipn : integer;
begin
writeln;
writeln;
writeln ( 'ESTAS SÃO AS DISTÂNCIAS MÍNIMAS DA RAIZ PARA CADA OUTRO
NÓ DO GRAFO');
writeln;
writeln;
for ipn := 1 to n do
begin
gotoxy((ipn+5)*4, 10);
write (PotN [ipn]);
end;
end;
Procedure InicializaPotN;
var a: integer; indice
begin
for a := 1 to n do
PotN [a] := 0;
end;
label fim;
BEGIN
clrscr;
writeln ('=========================== Simplex Acelerado
=========================');
writeln (Marinho, C. E. V; Santos, A.J;LEPROD/CCT/UENF');
writeln (‘Tese de Mestrado: EFICIÊNCIA POLINOMIAL DO SIMPLEX PARA
REDES: ANÁLISE SOBRE UM PROBLEMA DE CAMINHO MAIS CURTO (PCMC’));
writeln
writeln;
89
writeln;
writeln;
writeln ('Entre com o número de nós’);
readln (n);
MontarMatrizCusto;
EncherVetorArvore;
InicializaPotN;
otimo := false;
k := 0;
while otimo = false do
begin
******************** Criar Arvore e Empilhar ********************
raiz := NIL;
aloca(0); Chama o procedimento que monta árvore
Topo := NIL;
Empilhamento (raiz); começa o empilhamento a partir da raiz
******************************************************************
NNP := ContPilha; ContPilha retorna a quantidade de elementos da Pilha
para a variavel NNP(Número de No's da Pilha)
if NNP < n then
begin
writeln (' CICLO NEGATIVO!!! ');
gotoxy (5, 21);
write ('Tecle Algo para terminar');
readkey;
goto FIM;
end
else
begin
otimo := true;
90
Inc(k);
pivo := 0;
CalcPotN (raiz, raiz);
while (Topo <> nil) do
begin
h := topo^.dado;
auxP := topo; tira o ultimo elemento da pilha
topo := topo^.ant;
dispose (auxP);
CalcCustoReduzido;
if menor < 0 then
begin
inc (pivo);
NNP := ContPilha;
if (h = Raiz^.dado) or (pivo >= n - k) then
begin
writeln (' CICLO NEGATIVO!!! ');
gotoxy (5, 21);
write ('Tecle Algo para terminar');
readkey;
goto fim;
end
else
begin
otimo := false;
PotN[h] := PotN[h] + menor;
Vetor[h]:= NoMenor;
end;
end;
end;
MostrarVetorArv2;
writeln;
readkey;
91
end;
end;
clrscr;
MostrarVetorArv;
writeln;
MostrarPotNFinal;
writeln;
gotoxy (5, 21);
writeln('TERMINOU......APERTE UMA TECLA');
readkey;
FIM:
END.
Marinho, Carlos Eduardo Varejão.
Eficiência polinomial do método simples para redes: análise sobre um
problema de caminho mais curto (PCMC). – Campos dos Goytacazes, RJ.
- UENF, 2001.
xi, f. 59, enc. : il. ; 30 cm.
Dissertação (mestrado) M. Sc. Em Ciência de Engenharia modalidade Engenharia de Produção. Universidade Estadual do Norte Fluminense. Centro de Ciências e Tecnologia. Laboratório de Engenharia de Produção, 2001.
1. Programação linear 2. Complexidade fortemente polinomial. 3. Vetor- árvore. 4. Simplex acelerado. 5. Potências dos nós. I. Título.
CDD – 519.7
Ficha catalográfica feita na Biblioteca do CCT/ UENF.