Ferramentas de Utilizador

Ferramentas de Site


inf05010:dicas_exercicios_4

Dicas exercícios 4

Uma possível representação de um grafo ponderado em AMPL
data;
set V := 1 2 3 4 5 6 7 8 9 10;
set A := (1,2) (1,3) (1,6) (2,7) (2,8) (3,4) (3,9) (5,6) (6,10) (4,5) (4,8) (5,7) (7,9) (8,10) (9,10) ;
param c := 1,2 3 1,3 5 1,6 7 2,7 11 2,8 13 3,4 17 3,9 19 5,6 23 6,10 29 4,5 31 4,8 37 5,7 41 7,9 43 8,10 47 9,10 53;
end;

Como é um grafo não-direcionado, a convenção é que uma aresta (u,v) satisfaz u<v. Isso pode ser expressado no modelo por

set V;
set A within { (u,v) in V cross V : u<v};
Uma dica para implementar o problema da árvore geradora mínima

Caso a formulação escolhida possui uma restrição para cada subconjunto de um conjunto V (compare com a formulação do problema do caixeiro viajante), segue uma possível implementação em AMPL:

set V;

# constroi uma array com todos subconjuntos de V
# supoe: V = { 1,2,...,n }

param n := card(V);
set pV := 0..(2^n-1);
set PV {k in pV} := {i in V: (k div 2^(i-1)) mod 2 = 1};
# display { i in pV }: PV[i];  # para imprimir

# exemplo de uma restrição
subject to AlgumaRestrição { i in pV }:
       <restrição linear usando o conjunto PV[i]>;
inf05010/dicas_exercicios_4.txt · Esta página foi modificada pela última vez em: 2010/05/03 10:40 por marcus