1
Programación lineal / Problema del agente viajero
« en: 28 Enero, 2022, 07:02 am »
Hola amigos me podrían ayudar con un ejemplo del problema del agente viajero que utilice ramificación y acotamiento pero que no sea simétrico
Hasta el momento tengo uno con 5 ciudades:
$\begin{aligned} \operatorname{Min} z=& 3 x_{a b}+5 x_{a c}+4 x_{a d}+2 x_{a e}+3 x_{b a}+6 x_{b c}+2 x_{b d}+4 x_{b e}+5 x_{c a}+6 x_{c b} \\ &+5 x_{c d}+3 x_{c e}+4 x_{d a}+2 x_{d b}+5 x_{d c}+3 x_{d e}+2 x_{e a}+4 x_{e b}+3 x_{e c}+3 x_{e d} \end{aligned}$
s. $a$
$$
\begin{array}{ll}
x_{a b}+x_{a c}+x_{a d}+x_{a e}=1 & x_{b a}+x_{c a}+x_{d a}+x_{e c}=1 \\
x_{b a}+x_{b c}+x_{b d}+x_{b e}=1 & x_{a b}+x_{c b}+x_{d b}+x_{e b}=1 \\
x_{c a}+x_{c b}+x_{c d}+x_{c e}=1 & x_{a c}+x_{b c}+x_{d c}+x_{e c}=1 \\
x_{d a}+x_{d b}+x_{d c}+x_{d e}=1 & x_{a d}+x_{b d}+x_{c d}+x_{e d}=1 \\
x_{e a}+x_{e b}+x_{e c}+x_{e d}=1 & x_{a e}+x_{b e}+x_{c e}+x_{d e}=1 \\
x_{i j}=0,1 \text { con } \mathrm{i}, j=\{a, b, c, d, e\}, i \neq j &
\end{array}
$$
Disculpen que a partir de aquí no use LaTeX, sería complicado por las tablas tachadas y los caminos dibujados
Pero como ven se trata de un problema simétrico, he intentado cambiando el numero de ciudades, pero no se si sea mala suerte (o estoy haciendo algo mal) porque siguen siendo simétricos, entonces podrían darme un ejemplo del problema del agente viajero que utilice ramificación y acotamiento que no sea simétrico o decirme que podría cambiar en el problema para hacerlo no-simétrico. Muchas gracias de antemano
Hasta el momento tengo uno con 5 ciudades:
$\begin{aligned} \operatorname{Min} z=& 3 x_{a b}+5 x_{a c}+4 x_{a d}+2 x_{a e}+3 x_{b a}+6 x_{b c}+2 x_{b d}+4 x_{b e}+5 x_{c a}+6 x_{c b} \\ &+5 x_{c d}+3 x_{c e}+4 x_{d a}+2 x_{d b}+5 x_{d c}+3 x_{d e}+2 x_{e a}+4 x_{e b}+3 x_{e c}+3 x_{e d} \end{aligned}$
s. $a$
$$
\begin{array}{ll}
x_{a b}+x_{a c}+x_{a d}+x_{a e}=1 & x_{b a}+x_{c a}+x_{d a}+x_{e c}=1 \\
x_{b a}+x_{b c}+x_{b d}+x_{b e}=1 & x_{a b}+x_{c b}+x_{d b}+x_{e b}=1 \\
x_{c a}+x_{c b}+x_{c d}+x_{c e}=1 & x_{a c}+x_{b c}+x_{d c}+x_{e c}=1 \\
x_{d a}+x_{d b}+x_{d c}+x_{d e}=1 & x_{a d}+x_{b d}+x_{c d}+x_{e d}=1 \\
x_{e a}+x_{e b}+x_{e c}+x_{e d}=1 & x_{a e}+x_{b e}+x_{c e}+x_{d e}=1 \\
x_{i j}=0,1 \text { con } \mathrm{i}, j=\{a, b, c, d, e\}, i \neq j &
\end{array}
$$
Disculpen que a partir de aquí no use LaTeX, sería complicado por las tablas tachadas y los caminos dibujados
Pero como ven se trata de un problema simétrico, he intentado cambiando el numero de ciudades, pero no se si sea mala suerte (o estoy haciendo algo mal) porque siguen siendo simétricos, entonces podrían darme un ejemplo del problema del agente viajero que utilice ramificación y acotamiento que no sea simétrico o decirme que podría cambiar en el problema para hacerlo no-simétrico. Muchas gracias de antemano