Optimización en Redes

UNIVERSIDAD DEL BÍO-BÍO
VICERRECTORÍA ACADÉMICA-DIRECCIÓN GENERAL DE DOCENCIA
ASIGNATURA : Optimización en Redes

CÓDIGO : 430224
I.- IDENTIFICACIÓN
1.1 CAMPUS : CONCEPCIÓN
1.2 FACULTAD : INGENIERÍA
1.3 UNIDAD : DEPARTAMENTO DE INGENIERÍA INDUSTRIAL
1.4 CARRERA : INGENIERÍA CIVIL INDUSTRIAL
1.5 CREDITOS : 05
HORAS TEÓRICAS : 04 HRS.
HORAS PRÁCTICAS : 02 HRS.
1.6 REQUISITOS DE LA ASIGNATURA: INVESTIGACIÓN OPERATIVA I (430010)
II.- DESCRIPCION Y OBJETIVOS
Descripción:
En este curso se proporcionan al alumno los elementos analíticos necesarios para la formulación,
modelación y resolución de problemas de optimización en redes. Se estudian las propiedades teóricas
de cada problema así como diversos algoritmos que lo resuelven considerando diferentes tipos de
restricciones. Se discuten algunos aspectos de complejidad algorítmica, se enfatiza el proceso de
modelación como parte de la solución de problemas y se privilegia el empleo de paquetes
computacionales para resolver problemas de gran tamaño.
Objetivos:
Preparar al alumno en la formulación, modelación y resolución de problemas de optimización en redes.
Se atribuye especial importancia al desarrollo de algunas técnicas específicas para abordar tales
problemas y a la utilización de software de programación matemática para resolver problemas de
optimización de gran tamaño.
V. METODOLOGÍA
La metodología estará basada a través de la exposición teórica de las materias usando medios
audiovisuales, reforzada con ejercicios prácticos y entrega de apuntes y listado de ejercicios.
Además la asignatura cuenta con 2 horas prácticas en donde se reforzará a través de la solución de
ejemplos las materias impartidas.
VI. TIPOS DE EVALUACIÓN (PROCESO Y PRODUCTO)
La evaluación contará de:
- Tareas: para complementar y reforzar materias

- Tests: para evaluar resultados y tomar medidas para mejorarlos
- Certamen: Evaluación de comprensión de materias impartidas
- Examen: si el alumno no demuestra un rendimiento mínimo promedio de 60 puntos en las
evaluaciones anteriores
VI. TIPOS DE EVALUACIÓN.
PRIMER CERRTÁMEN : 40 %
SEGUNDO CERTÁMEN : 40 %
CONTROLES DE LECTURA Y TEST : 10 %
TRABAJO DE INVESTIGACIÓN : 10 %.
3.- RESUMEN DE UNIDADES PROGRAMATICAS
01 Programación Lineal Entera 10 Hrs.

02 Nociones básicas de teoría de grafos 02 Hrs.
03 Software de Programación Matemática 04 Hrs.
04 El Problema de la Ruta Más Corta 14 Hrs.
05 Problemas Especiales de Redes 10 Hrs.
06 Problemas de Localización de Instalaciones 14 Hrs.
07 Problemas de Ruteo 10 Hrs.
Total de Horas 64 Hrs
4.- UNIDADES PROGRAMATICAS
UNIDAD 01: Programación Lineal Entera

 Introducción
 Modelación con variables enteras y variables binarias
 Algoritmo de Ramificación y Acotamiento (Branch and Bound);
 Algoritmos de planos de corte
 Problemas de programación lineal entera mixta
UNIDAD 02: Nociones Básicas de Teoría de Grafos

 Definición de grafo
 Representación de un grafo
 Grafos conexos, completos, dirigidos, no dirigidos
 Concepto y caracterización de un árbol
UNIDAD 03: Software de Programación Matemática

 Elementos de lenguajes de modelación
 LINDO, CPLEX , LINGO, AMPL
UNIDAD 04: El Problema de la Ruta Más Corta

 Modelos de PL para el problema de la ruta más corta
 Ruta mas corta entre un nodo origen y un nodo destino
 Rutas mas corta entre un nodo origen y todos los nodos de la red
 Algoritmo de Dijkstra
 Algoritmo de Floyd
UNIDAD 05: Problemas Especiales de Redes

 El problema del árbol de costo mínimo
 El problema de Steiner
 El problema de flujo máximo
 El problema de flujo de mínimo costo
 Problemas de flujo multicommodity
UNIDAD 06: Problemas de Localización de Instalaciones

 Problemas de cubrimiento de conjuntos
 Problemas p-centro y Problemas p-median
 Problema de localización de instalaciones de carga fija
UNIDAD 07: Problemas de Ruteo

 El problema del vendedor viajero
 El problema de ruteo de vehículos
 El problema de ruteo de vehículos con ventanas de tiempo
 El problema de localización y ruteo
5.- BIBLIOGRAFÍA
 Ahuja, R.K., T.L. Magnanti y J.B. Orlin (1993). Network flows. Theory, algorithms and applications.
Prentice Hall.
 Daskin, M.S. (1995), Network and discrete location: Models, algorithms and applications, Wiley
Interscience, New York.
 Hillier, F.S. y Lieberman, G.J. (2002). Investigación de Operaciones. Editorial Mcgraw-Hill.
 Pardo L, A. Ortega y J. Pardo (1990) Programación Lineal Entera: Aplicaciones prácticas en la empresa.
Ediciones Díaz de santos, S. A.
 Taha, H.A. (1998). Investigación de Operaciones: una introducción. Editorial Prentice--Hall.
 Winston, W.L. (1994). Investigación de Operaciones: aplicaciones y algoritmos. Grupo Editorial
Iberoamérica.
 Wolsey, L.A. (1998). Integer Programming. Ed. John Wiley.
Optimización en Redes
Los modelos de optimización representan una herramienta fundamental para la toma de decisiones en
las empresas y en la gestión de sistemas productivos. Es de suma importancia saber cómo y cuándo
utilizar cada método o procedimiento en problemas del ámbito empresarial e industrial y, sobre todo,
cómo interpretar correctamente los resultados obtenidos.
Una amplia variedad de problemas del mundo real pueden ser modelados de manera natural a través de
redes. Las redes de transporte, eléctricas y de comunicaciones predominan en nuestra vida diaria. La
representación de redes se utiliza ampliamente en áreas tan diversas como producción, distribución,
localización de instalaciones, planificación y control de proyectos y administración de recursos. De
hecho, una representación de redes proporciona un panorama general tan poderoso y una ayuda
conceptual para visualizar las relaciones entre las componentes de los sistemas que se usa casi en todas
las áreas científicas, sociales y económicas.
En general, todo problema de red puede resolverse con un algoritmo de programación lineal, sin
embargo, para muchos de estos problemas existen algoritmos de propósitos especiales muy eficientes
para obtener soluciones óptimas. Estos algoritmos tienen un interés intrínseco, aunque también son
útiles para resolver subproblemas de otros más grandes o más complejos.
En este curso se proporcionan al alumno los elementos analíticos necesarios para la formulación,
modelación y resolución de problemas de optimización en redes. Se estudian las propiedades teóricas
de cada problema así como diversos algoritmos que lo resuelven considerando diferentes tipos de
restricciones. Se discuten algunos aspectos de complejidad algorítmica, se enfatiza el proceso de
modelación como parte de la solución de problemas y se privilegia el empleo de paquetes
computacionales para resolver problemas de gran tamaño.
El curso comprende tres grandes bloques: en el primero de ellos se presentan los métodos y técnicas
para resolver problemas de programación entera. En la segunda parte se estudiarán nociones básicas de
teoría de grafos y la utilización de distintos lenguajes de modelación para el desarrollo de aplicaciones.
En el último bloque se estudiarán los principales problemas de redes que tienen amplias aplicaciones en
sistemas de transporte, de telecomunicaciones, localización, distribución y ruteo de vehículos.

Optimización en Redes

Cargado por

Copyright:

Formatos disponibles

Optimización en Redes

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Optimización en Redes

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD DEL BÍO-BÍO

VICERRECTORÍA ACADÉMICA-DIRECCIÓN GENERAL DE DOCENCIA

ASIGNATURA : Optimización en Redes

II.- DESCRIPCION Y OBJETIVOS

VI. TIPOS DE EVALUACIÓN (PROCESO Y PRODUCTO)

La evaluación contará de:

- Tareas: para complementar y reforzar materias

3.- RESUMEN DE UNIDADES PROGRAMATICAS

01 Programación Lineal Entera 10 Hrs.

4.- UNIDADES PROGRAMATICAS

UNIDAD 01: Programación Lineal Entera

UNIDAD 02: Nociones Básicas de Teoría de Grafos

UNIDAD 03: Software de Programación Matemática

UNIDAD 04: El Problema de la Ruta Más Corta

UNIDAD 05: Problemas Especiales de Redes

UNIDAD 06: Problemas de Localización de Instalaciones

UNIDAD 07: Problemas de Ruteo

También podría gustarte