Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

--- inf05010:dicas_exercicios_4 [2010/05/02 17:12]
marcus Criação deste novo documento.
+++ inf05010:dicas_exercicios_4 [2010/05/03 10:40] (Actual)
marcus
@@ Linha 1: / Linha 1: @@
 === Dicas exercícios 4 ===
-== Uma possível representação de um grafo em AMPL ==
+== Uma possível representação de um grafo ponderado em AMPL ==
 <code>
@@ Linha 9: / Linha 9: @@
 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