ࡱ> Root Entry*0_^`Contents Root Entry*0_^QContents   !"#$%&'()*+,-./0123456789:;<=> @SUM\plain\f4\fs20\cf0 (MATRIZ(I,J): Y(I,J)) - \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (MATRIZ(I,J): Y(J,I)) = 1 \par ); \par \par \plain\f4\fs20\cf2 ! A quantidade de fluxo de I para J \'e9 limitada;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (MATRIZ(I,J): Y(I,J) <= (N - M)*X(I,J)); \par \par \plain\f4\fs20\cf1 END\plain\f4\fs20\cf0 \par } {\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fmodern Courier New;}{\f3\fswiss\fprq2 System;}{\f4\fmodern Courier New;}} {\colortbl\red0\green0\blue0;\red0\green0\blue255;\red0\green175\blue0;} \deflang1046\pard\plain\f4\fs20\cf1 MODEL\plain\f4\fs20\cf0 : \par \par \plain\f4\fs20\cf2 ! Problema dos n caixeiros viajantes (nPCV);\plain\f4\fs20\cf0 \par \par \plain\f4\fs20\cf1 SETS\plain\f4\fs20\cf0 : \par CIDADE/ D C1 C2 C3 C4 C5 C6 C7/: ; \par \par \plain\f4\fs20\cf2 ! D(I,J) \'e9 a dist\'e2ncia da cidade I \'e0 cidade J \par X(I,J) \'e9 uma vari\'e1vel 0-1: Ela vale 1 se o ve\'edculo faz a \par viagem da cidade I \'e0 cidade J e vale 0 caso contr\'e1rio \par Y(I,J) \'e9 a quantidade de fluxo da cidade I \'e0 cidade J;\plain\f4\fs20\cf0 \par MATRIZ(CIDADE, CIDADE): D, X, Y; \par \plain\f4\fs20\cf1 ENDSETS\plain\f4\fs20\cf0 \par \par \plain\f4\fs20\cf1 DATA\plain\f4\fs20\cf0 : \par \plain\f4\fs20\cf2 ! N\'famero de caixeiros viajantes;\plain\f4\fs20\cf0 \par M = 3; \par \par D = \par 0 996 2162 1067 499 2054 2134 2050 \par 0 0 1167 1019 596 1059 1227 1055 \par 0 1167 0 1747 1723 214 168 250 \par 0 1019 1747 0 710 1538 1904 1528 \par 0 596 1723 710 0 1589 1827 1579 \par 0 1059 214 1538 1589 0 371 36 \par 0 1227 168 1904 1827 371 0 407 \par 0 1055 250 1528 1579 36 407 0; \par \par \plain\f4\fs20\cf1 ENDDATA\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf2 ! N\'famero de cidades;\plain\f4\fs20\cf0 \par N = \plain\f4\fs20\cf1 @SIZE\plain\f4\fs20\cf0 (CIDADE); \par \plain\f4\fs20\cf2 ! Minimize a dist\'e2ncia total percorrida;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 MIN\plain\f4\fs20\cf0 = FO; \par FO = \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (MATRIZ(I,J): D(I,J) * X(I,J)); \par \par \plain\f4\fs20\cf2 ! Um ve\'edculo n\'e3o viaja de uma cidade para ela mesma....;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (CIDADE(J): \par X(J,J) = 0; \par ); \par \par \plain\f4\fs20\cf2 ! As vari\'e1veis X s\'e3o bin\'e1rias;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (MATRIZ(I,J): \plain\f4\fs20\cf1 @BIN\plain\f4\fs20\cf0 (X(I,J))); \par \par \plain\f4\fs20\cf2 ! De uma cidade J, exceto a origem, s\'f3 pode chegar um caixeiro;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (CIDADE(J) | J #NE# 1: \par \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (CIDADE(I): X(I,J)) = 1 \par ); \par \par \plain\f4\fs20\cf2 ! De uma cidade J, exceto a origem, s\'f3 pode sair um caixeiro;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (CIDADE(J) | J #NE# 1: \par \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (CIDADE(I): X(J,I)) = 1 \par ); \par \par \plain\f4\fs20\cf2 ! M caixeiros devem chegar \'e0 origem;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\  !"#$%&'()*+,-./0123456789:;<=> @SUM\plain\f4\fs20\cf0 (MATRIZ(I,J): Y(I,J)) - \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (MATRIZ(I,J): Y(J,I)) = 1 \par ); \par \par \plain\f4\fs20\cf2 ! A quantidade de fluxo de I para J \'e9 limitada;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (MATRIZ(I,J): Y(I,J) <= (N - M)*X(I,J)); \par \par \plain\f4\fs20\cf1 END\plain\f4\fs20\cf0 \par } {\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fmodern Courier New;}{\f3\fswiss\fprq2 System;}{\f4\fmodern Courier New;}} {\colortbl\red0\green0\blue0;\red0\green0\blue255;\red0\green175\blue0;} \deflang1046\pard\plain\f4\fs20\cf1 MODEL\plain\f4\fs20\cf0 : \par \par \plain\f4\fs20\cf2 ! Problema dos n caixeiros viajantes (nPCV);\plain\f4\fs20\cf0 \par \par \plain\f4\fs20\cf1 SETS\plain\f4\fs20\cf0 : \par CIDADE/ D C1 C2 C3 C4 C5 C6 C7/: ; \par \par \plain\f4\fs20\cf2 ! D(I,J) \'e9 a dist\'e2ncia da cidade I \'e0 cidade J \par X(I,J) \'e9 uma vari\'e1vel 0-1: Ela vale 1 se o ve\'edculo faz a \par viagem da cidade I \'e0 cidade J e vale 0 caso contr\'e1rio \par Y(I,J) \'e9 a quantidade de fluxo da cidade I \'e0 cidade J;\plain\f4\fs20\cf0 \par MATRIZ(CIDADE, CIDADE): D, X, Y; \par \plain\f4\fs20\cf1 ENDSETS\plain\f4\fs20\cf0 \par \par \plain\f4\fs20\cf1 DATA\plain\f4\fs20\cf0 : \par \plain\f4\fs20\cf2 ! N\'famero de caixeiros viajantes;\plain\f4\fs20\cf0 \par M = 3; \par \par D = \par 0 996 2162 1067 499 2054 2134 2050 \par 0 0 1167 1019 596 1059 1227 1055 \par 0 1167 0 1747 1723 214 168 250 \par 0 1019 1747 0 710 1538 1904 1528 \par 0 596 1723 710 0 1589 1827 1579 \par 0 1059 214 1538 1589 0 371 36 \par 0 1227 168 1904 1827 371 0 407 \par 0 1055 250 1528 1579 36 407 0; \par \par \plain\f4\fs20\cf1 ENDDATA\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf2 ! N\'famero de cidades;\plain\f4\fs20\cf0 \par N = \plain\f4\fs20\cf1 @SIZE\plain\f4\fs20\cf0 (CIDADE); \par \plain\f4\fs20\cf2 ! Minimize a dist\'e2ncia total percorrida;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 MIN\plain\f4\fs20\cf0 = FO; \par FO = \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (MATRIZ(I,J): D(I,J) * X(I,J)); \par \par \plain\f4\fs20\cf2 ! Um ve\'edculo n\'e3o viaja de uma cidade para ela mesma....;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (CIDADE(J): \par X(J,J) = 0; \par ); \par \par \plain\f4\fs20\cf2 ! As vari\'e1veis X s\'e3o bin\'e1rias;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (MATRIZ(I,J): \plain\f4\fs20\cf1 @BIN\plain\f4\fs20\cf0 (X(I,J))); \par \par \plain\f4\fs20\cf2 ! De uma cidade J, exceto a origem, s\'f3 pode chegar um caixeiro;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (CIDADE(J) | J #NE# 1: \par \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (CIDADE(I): X(I,J)) = 1 \par ); \par \par \plain\f4\fs20\cf2 ! De uma cidade J, exceto a origem, s\'f3 pode sair um caixeiro;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (CIDADE(J) | J #NE# 1: \par \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (CIDADE(I): X(J,I)) = 1 \par ); \par \par \plain\f4\fs20\cf2 ! M caixeiros devem chegar \'e0 origem;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (CIDADE(I) | I #NE# 1: X(I,1)) = M; \par \par \plain\f4\fs20\cf2 ! M caixeiros devem sair da origem;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @SUM\plain\f4\fs20\cf0 (CIDADE(J) | J #NE# 1: X(1,J)) = M; \par \par \par \plain\f4\fs20\cf2 ! Ao passar por uma cidade I a quantidade de cidades ainda n\'e3o visitadas \par pelo caixeiro deve decrescer de uma unidade;\plain\f4\fs20\cf0 \par \plain\f4\fs20\cf1 @FOR\plain\f4\fs20\cf0 (CIDADE(I) | I #NE# 1: \par \plain\f4\fs20\cf1