Resultados da teoria de grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2363 palavras )
  • Download(s) : 0
  • Publicado : 22 de março de 2013
Ler documento completo
Amostra do texto
Alguns resultados da teoria de grafos para o problema de redes.

A especialização do algoritmo simplex primal de George Dantzig para o problema de fluxo em rede com custo mínimo PL é de grande importância, pois o método simplex primal pode ser realizado diretamente na rede eliminando o peso computacional na atualização da inversa da matriz básica.
Antes da formulação para problema PLespecializado, alguns conceitos de rede serão apresentados.
Uma rede pode ser representada por um grafo G que consiste de um conjunto finito [] de nós e arcos respectivamente.
Uma rede contendo nós e arcos deve possuir nós e arcos ordenados de forma que exista uma correspondência biunívoca entre os nós da rede e os números inteiros, com 1,.., . A mesma correspondência biunívoca deve existir para osarcos da rede, com 1,.., .
A estrutura da rede é ilustrada através da figura III-1, onde os nós são representados por círculos e os arcos por segmentos de linha orientados que conectam dois nós. A seta no segmento de linha indica a direção de fluxo no arco da rede. Por exemplo, o primeiro arco está direcionado a partir do nó 1 na direção do nó 5.

2
3
1
5
4
1
8
2
7
6
5
4
3
2
3
15
4
1
8
2
7
6
5
4
3




Figura III-1 – Representação de uma rede através de um grafo G.

A estrutura da rede pode também ser descrita por uma mátria A de dimensão Ix, definida como segue



A matriz A definida acima é chamada de matriz de incidência nó-arco. A matriz deincidência A, correspondente à rede da figura III-1, é mostrada a seguir:
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
Nós
Nós
Arcos
Arcos

A =

A característica dessa matriz é que cada coluna possui exatamente duas entradas não nulas, uma entrada (+1) e a outra (-1).
As definições deoutras quantidades associadas à rede são também necessárias. A variável de decisão xj denota a quantidade de fluxo através do arco j, com o vetor x de dimensão denotando o fluxo em todos os arcos da rede. O custo unitário de fluxo no arco j denotado por cj, com o correspondente vetor c de dimensão . As capacidades mínima e máxima de fluxo através do arco j denotada por lj e uj respectivamente, com oscorrespondentes vetores l e u de dimensão . As quantidades de oferta e demanda para o nó i denotadas por ri, com o correspondente vetor r de dimensão . Se ri > 0, o nó i é um ponto de oferta, com oferta igual a ri. Se, ri < 0, o nó i é um ponto de demanda, com demanda igual a | ri |. Nós da rede possuindo ri = 0 são chamados pontos de transbordo. Matematicamente o problema de rede de mínimocusto pode ser formulado como segue:

Min cx (3.1)
s.a. Ax = r (3.2)
l x u(3.3)

onde, A é a matriz de incidência nó-arco, x a quantidade de fluxo através dos arcos, r o vetor de ofertas e demandas associados aos nós da rede, c o vetor de custos, l e u representando as capacidades mínimas e máximas de fluxo nos arcos da rede.
Resultados a partir da teoria de grafos serão utilizados no desenvolvimento do algoritmo especializadopara redes.
Considera-se uma rede contendo nós e arcos e uma matriz de incidência A associada à rede. Para cada arco j, tem-se F(j) = i, onde Aij =1 e T(j) = k, onde Akj = -1. O arco j é formalmente descrito como um par (F(j), T(j)) tal que F(j)T(j).
Seja R = {e1, e2,..... } o conjunto de arcos, onde ej = (F(j), T(j)). Seja N = { 1,2,..., } o conjunto de nós. Então, o grafo G consiste de um...
tracking img