Marcus Ritt

Esta página é apenas de leitura. Pode ver a fonte, mas não alterá-la. Informe-se com o administrador deste Wiki se achar que isto não está correcto.

=== Dicas exercícios 4 ===

== Uma possível representação de um grafo ponderado em AMPL == 

<code>
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;
</code>

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

<code>
set V;
set A within { (u,v) in V cross V : u<v};
</code>

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

<code>
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]>;
</code>

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página