-
UNIVERSIDAD DE LOS ANDES
FACULTAD DE INGENIERA
DEPARTAMENTO DE SISTEMAS Y COMPUTACIN
Modelado, Simulacin y Optimizacin
Profesor
Yezid Donoso Meisel
[email protected]
Monitor
Germn Montoya O. [email protected]
(1.5.) TALLER #2 Construccin de modelos de optimizacin y
representacin de datos
1. OBJETIVO GENERAL
Desarrollar mediante un ejemplo el modelamiento de variables de
decisin, el modelamiento de funciones objetivo y el modelamiento de
restricciones.
2. CASO
El problema de M orgenes y N destinos Se poseen M orgenes (s1 y
s2) desde los cuales se debe enviar informacin a N destinos (d1 y
d2), transportndose dicha informacin a travs de nodos intermedios
mediante enlaces con un determinado costo, tal como lo indica la
siguiente figura.
Figura 1. Topologa de red para M orgenes y N destinos.
-
Dado lo anterior, se desean hallar los enlaces que establezcan
caminos de mnimo costo desde cada nodo origen hasta cada uno de los
nodos destino.
3. PREGUNTAS
Definir: a. La variable de decisin que permita modelar
matemticamente el problema. b. La funcin objetivo que permita
encontrar la solucin del problema. c. Las restricciones que
delimiten el problema. d. Defina una representacin de datos para
este problema. Nota: Basarse en el modelo matemtico visto en clase
para el caso de un origen y varios destinos.
4. SOLUCIN
E: conjunto de enlaces N: conjunto de nodos O: conjunto de
orgenes D: conjunto de destinos Cij: Costo del enlace entre los
nodos i y j.
{
Min
s.a: Nodos origen:
Nodos destino:
Nodos intermedios:
-
Representacin de datos de la solucin:
S1 N1 N2 T1 -1 S1 N1 N2 T2 S2 N1 N2 T1 -1 S2 N1 N2 T2 Donde Si
es un nodo fuente, y Ti es un nodo destino. Ejemplo de la
solucin:
1 3 6 8 -1 1 3 6 9
2 4 7 8 -1 2 4 7 9
Otra posible representacin de la solucin:
N1 N2 N3 N4 N5 N6 N7 N8 N9 N1 1 N2 N3 2 N4 N5 N6 3 N7 N8 N9
Donde el nmero en la matriz indica el orden en el cual el par (Ni,
Nj) debe ir situado para formar el path desde la fuente al destino.
N1,N3 : enlace nmero 1 N3,N6 : enlace nmero 2 N6,N6 : enlace nmero
3 El path sera: enlace 1, enlace 2, enlace 3 = N1 N3 N6 N8 Para los
dems casos sera:
N1 N2 N3 N4 N5 N6 N7 N8 N9 N1 1 N2 N3 2 N4 N5 N6 3
N7 N8 N9 El path sera: enlace 1, enlace 2, enlace 3 = N1 N3 N6
N9
-
N1 N2 N3 N4 N5 N6 N7 N8 N9 N1 N2 1 N3 N4 2 N5 N6
N7 3 N8 N9 El path sera: enlace 1, enlace 2, enlace 3 = N2 N4 N7
N8
N1 N2 N3 N4 N5 N6 N7 N8 N9 N1 N2 1 N3 N4 2 N5 N6
N7 3
N8 N9 El path sera: enlace 1, enlace 2, enlace 3 = N2 N4 N7
N9
