UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
ASIGNATURA: OPTIMIZACIÓN CODIGO 2025971 Periodo 2019_03
Tipo Asignatura: Teórico /Practica
Dirigido a: Estudiantes de pregrado de Ingeniería
Requisitos:
Álgebra lineal
Programación de computadores en un lenguaje de alto nivel (C, JAVA)
Profesor: Luis Gerardo Astaiza Amado
Departamento de Ingenierías de Sistemas e Industrial
Oficina 453-102 Ext. 14071
E-mail lgastaizaa@[Link]
I. Descripción del curso
Los problemas de optimización se plantean muy a menudo en la industria, y la
capacidad de resolverlos es una ventaja competitiva. Sin embargo, el modelado
de problemas de Optimización requiere herramientas especiales y habilidades.
Un problema que no se entiende o se modela incorrectamente puede conducir
a la solución equivocada o puede ser muy difícil de resolver.
II. Objetivos
Proveer al estudiante los elementos que le capaciten para:
Introducir al estudiante en el ambiente de la Investigación de Operaciones
entendida ésta como un medio fundamental que soporta una toma acertada
de decisiones
Trabajar en equipo para la apropiación del modelado mediante el uso de
talleres de aplicación y estudios de casos
Formular y solucionar modelos de programación lineal;
Afianzar el concepto de optimización con el uso de modelos de
programación lineal;
Aprehender los fundamentos conceptuales de los métodos más
importantes, para solucionar problemas de programación lineal;
Comprender y aplicar la teoría de flujo en redes, y
Conocer y dominar, herramientas automatizadas que apliquen los
conceptos, tanto de programación lineal, como de análisis de redes;
Introducir al estudiante en conceptos, métodos y aplicaciones de la
programación lineal determinística;
Aplicar las técnicas de optimización en problemas de programación
determinística;
Introducir al estudiante en problemas de programación lineal entera;
Introducir al estudiante en problemas de programación dinámica.
Presentar una introducción a las técnicas Meta heurísticas (Opcional)
1
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
III. Metodología
• Clase magistral
• Lectura de textos guía y textos complementarios
• Actividades grupales durante la clase y similares
• Uso de software para resolución de problemas
• Tareas y Trabajos grupales
IV. Resultados esperados
Al terminar este curso, los alumnos serán capaces de:
Identificar los objetivos y las limitaciones basados en las descripciones de
los problemas del mundo real
Crear modelos de optimización matemática correspondiente a las
descripciones de los problemas
Seleccionar y trabajar a través de una adecuada técnica de solución
basada en el tipo de modelo
Utilizar software de optimización para llevar a cabo los análisis; interpretar
los resultados
Hacer recomendaciones sólidas basadas en las soluciones, análisis, y las
limitaciones de los modelos
V. Evaluación
Elemento Concepto % Calificacion
1 Parciales 50
2 Tareas 30
3 Exposición y proyecto 20
VI. Contenido del Curso
PARTE I: Introducción a la Optimización
¿Qué es la investigación operativa?
Orígenes y alcances de la investigación Operacional
¿Qué es programación Matemática?
PARTE II. Programación lineal
Formulación y forma estándar de problemas lineales
Geometría de problemas lineales y propiedades de poliedros
Método Simplex
El método de las dos fases
Variantes del método Simplex
El método de los pesos
El método de una sola artificial
Método Simplex Revisado
Teoría de dualidad
2
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
Análisis de sensibilidad
PARTE III: Extensiones de Programación Lineal
1. Optimización de flujo en redes
2. Programación Lineal Entera
Construcción de modelos de programación lineal entera (PLE).
Solución de problemas de PLE: algoritmo del plano cortante; algoritmo
de ramificación y acotamiento.
3. Optimización con objetivos múltiples y programación meta
Objetivo individual y objetivos múltiples.
Formulación y algoritmos de programación de metas.
PARTE IV: Programación no lineal
Optimización con restricciones de igualdad y desigualdad
Condiciones necesarias y suficientes para un mínimo local o global
Métodos de búsqueda de soluciones sin restricciones (Gradiente,
Newton)
Métodos para problemas con restricciones: penalización, gradiente y
Newton proyectado y otros.
PARTE V: Temas Opcionales
1. Programación Dinámica Determinística
Principio de optimalidad de Bellman. Terminología. Definición de la
función de valor óptimo y de sus argumentos, la función de política
óptima, la relación de recurrencia y las condiciones de frontera. Etapa y
estado.
Programación dinámica (PD) hacía adelante y PD hacía atrás. Ejemplos
de la ruta más corta, reemplazo de equipos, asignación de recursos, etc.
2. Introducción a las Meta heurísticas (Opcional) (Algoritmos genéticos,
Búsqueda Tabú, Colonia de Hormigas, Recocido Simulado)
VII. Calendario Tentativo
Fecha Tema Asignación
Agosto 27 - 29 Introducción Optimización
Setbre. 03 - 05 Programación Lineal - Formulación
Setbre. 10 - 12 Programación Lineal - Formulación
Setbre. 17 - 19 Método Simplex
Setbre. 24 - 26 Método de las dos fases
Octubre 01 - 03 Técnica de una sola artificial
Octubre 08 - 10 Método Simplex revisado
Octubre 15 - 17 Dualidad
3
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
Octubre 22 - 24 Análisis de sensibilidad
Octubre 29 - 31 Problema de transporte y
asignación
Novbre. 05 - 07 Flujo en redes
Novbre. 12 - 14 Programación entera
Novbre. 19 - 21 Programación Multiobjetivo
Novbre. 26 - 28 Exposiciones
Dicbre. 03 - 05 Exposiciones
Dicbre. 10 - 12 Exposiciones
Dicbre. 21 Cierre de calificaciones
VIII. Bibliografía
1. Bazaraa, Mokhtar S. LINEAR POGRAMMING AND NETWORK FLOWS.
John Wiley
2. Hillier, F. y Lieberman, G. (2002) Investigación de operaciones. Séptima
edición McGraw-Hill.
3. Kwang Y. Lee and Mohamed A. El-Sharkawi. Modern Heuristic
Optimization Techniques
4. Rao, Singiresu S. Engineering Optimization Theory and Practice. John
Wiley & Sons, Inc.
5. Rardin, Ronald L. Optimization in Operations Research Prentice Hall
1998
6. Taha, H.A. Investigación de Operaciones, una introducción, Prentice
Hall, México, Séptima Edición, 2004.
7. Winston, Wayne L. Investigación de Operaciones 4 edición 2005 Ed
Thomson.
IX. Referencias Bibliográficas
1. AHUJA, R. K., T. L. Magnanti y J.B. ORLIN NETWORK FLOWS:
THEORY, ALGORITHMS, AND APPLICATIONS 1993 PRENTICE HALL,
NJ. ISBN: 0-13-617549-X
2. BORYE, C. Teoría de las redes. Compañía Editorial Continental, S.A.
3. DANTZIG G LINEAR PROGRAMMING AND EXTENSIONS
4. Davis McKeon Modelos Cuantitativos para Administración Grupo
Editorial Iberoamericana
5. HARVEY M. WAGNER PRINCIPLES OF OPERATIONS RESEARCH
Prentice Hall
6. Herbert Moskowitz y Gordon P. Wright INVESTIGACION DE
OPERACIONES PRENTICE HALL INTERNATIONAL
7. Prawda, Juan METODOS Y MODELOS DE INVESTIGACION DE
OPERACIONES VOL I
8. RIOS, Sixto, RIOS, David, MATEOS, Alfonso, MARTÍN, Jacinto.
Programación Lineal y Aplicaciones. Ejercicios Resueltos. Alfaomega
S.A. 1998.
9. Xin-She Yang. Introduction to Mathematical Optimization – From
Linear Programming to Metaheuristics
4
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
X. LENGUAJES Y HERRAMIENTAS DE MODELADO
1. GAMS
2. GUROBI
3. LINDO/LINGO
4. MATLAB/OCTAVE
5. MOSEL
6. SCILAB
7. Solver
8. TORA
9. WINDOWSQSB
10. AMPL [Link]
11. Super Decisions. [Link]
12. ExpertChoice [Link]
Tanto AMPL como MOSEL tienen versiones estudiantiles que se pueden
descargar de forma gratuita. Están limitados a un máximo de 300
restricciones y variables, pero esto es más que suficiente para la mayoría de
problemas de este curso.
Problemas formulados en AMPL o GAMS pueden ser resueltos mediante la
presentación del modelo en [Link]
Muchas herramientas se pueden utilizar de forma gratuita y sin ningún tipo de
limitación en el número de restricciones y variables.
XI. TAREAS
Problemas pueden asignarse periódicamente. Estos problemas tienen como
finalidad evaluar la comprensión de los conceptos presentados en clase.
Las siguientes instrucciones deben seguirse en la entrega de trabajos
1. Identifique Número de la tarea, su equipo de trabajo y los participantes
con Apellidos, nombres, documento de identidad.
2. Identifique cada problema e Indique claramente la separación de cada
parte incluyendo su planteamiento
3. Defina toda la notación no establecida en el planteamiento del problema
4. Presente todo el trabajo realizado para llegar a las conclusiones
5. Presente las respuestas en el contexto del problema
6. Trabaje de izquierda a derecha y de arriba abajo
7. Escriba con claridad y Numere las páginas
8. Grape las páginas en la esquina superior izquierda
Puede existir situaciones en las cuales se solicite utilizar o no utilizar
computador. Para problemas utilizando computador, los resultados deben
estar bien organizados y formateados.
5
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
XII. CONDICIONES GENERALES
Durante el tiempo de clase está prohibido el uso de celulares y aparatos
electrónicos portátiles fuera de los espacios establecidos por el docente. A los
estudiantes que tengan que hacer uso de esto elementos en tiempo no
permitido se les solicitará abandonar la clase, con la respectiva falla.
No se aceptan entregas tardías de las asignaciones, y se calificarán con nota
de 0.0. No hay excepciones a esta regla. Las fechas correspondientes se
indicarán en el cronograma del curso o en el enunciado del mismo.
Es extremadamente importante que las asignaciones que usted entregue
reflejen su propia comprensión. Copiar respuestas de otra persona no sólo le
niega la retroalimentación necesaria sobre si realmente entiende o no el
material, sino que también compromete su integridad.
En esta clase, sin el permiso explícito del docente, lo siguiente no cuenta como
trabajo original y constituiría un engaño:
Entregar el mismo o en gran medida un documento similar de otra clase o
clases.
Copiar material de la web sin citarlo correctamente.
Plagio, incluyendo: copiar imágenes, gráficos y tablas de trabajos
publicados.
No citar correctamente material producido por otros.
Utilizar código fuente desarrollado por otros o extraído de la web para su
proyecto sin permiso previo explícito del docente, y referencia apropiada.
Todas las entregas de los trabajos y talleres deben especificar claramente el
título del trabajo y los integrantes del grupo que están realizando la
presentación, sino las notas sólo se colocarán a quien figure en la entrega.
Cada hora corresponde a una falla, y con el 20 % de fallas se pierde la
asignatura. Los estudiantes que lleguen después de la hora establecida de
inicio de clase, o que tengan que ausentarse de clase antes de la finalización,
tendrán la falla correspondiente.