UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
ASIGNATURA: OPTIMIZACIÓN CODIGO 2025971 Periodo 2019_01
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)
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. Objetivo
El objetivo de este curso es:
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
Proporcionar las herramientas y conocimientos necesarios para modelar
problemas de optimización prácticos y obtener una solución.
Propender por el trabajo en equipo y la apropiación de la modelación
mediante el uso de talleres de aplicación y estudios de casos
Entender y aplicar el algoritmo Simplex para programación lineal y otros
algoritmos para enfrentar y resolver problemas no lineales, enteros, y en
estructuras de redes
Conocer y aplicar herramientas computacionales (softwares) para resolver
modelos de optimización.
Capacitar al estudiante en la utilización de diferentes técnicas, algorítmicas
y modelos como herramientas para resolver problemas de programación
lineal, entera, no lineal, redes, dinámica y de proyectos.
Presentar una introducción a las técnicas Meta heurísticas (Opcional)
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
1
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
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
Análisis de sensibilidad
2
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
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
Clase / Fecha Tema Lectura Asignación
Abril 02-04 Introducción a la Optimización
Abril 09-11 Programación Lineal - Formulación
Abril 16 Programación Lineal - Formulación
Abril 18-21 Semana Santa
Abril 23-25 Método Simplex
3
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
Abril 30 Método de las dos fases
Mayo 02 Técnica de una sola artificial
Mayo 07 - 09 Método Simplex Revisado
Mayo 14 - 16 Dualidad
Mayo 21 - 23 Análisis de Sensibilidad
Mayo 28 - 30 Problema de Transporte y
Asignación
Junio 04 - 06 Modelo de redes
Junio 11 - 13 Programación Entera
Junio 18 - 20 Programación Multiobjetivo
Junio 25 - 27 Programación Meta
Julio 02 - 04 Exposiciones
Julio 09 - 11 Exposiciones
Julio 16 - 19 Exposiciones
Julio 27 Cierre de calificaciones
VIII. Bibliografía
1. Mokhtar S. Bazaraa LINEAR POGRAMMING AND NETWORK FLOWS.
John Wiley
2. Ronald L. Rardin Optimization in Operations Research Prentice Hall
1998
3. H.A. Taha. Investigación de Operaciones, una introducción,, Prentice
Hall, México, Septima Edición, 2004.
4. Xin-She Yang. Introduction to Mathematical Optimization – From
Linear Programming to Metaheuristics
5. Kwang Y. Lee and Mohamed A. El-Sharkawi Modern Heuristic
Optimization Techniques
IX. Referencias Bibliográficas
1. Hillier, F. y Lieberman, G. (2002) Investigación de operaciones. Séptima
edición Mcgraw-Hill.
2. Winston,Wayne L. Investigación de Operaciones 4 edición 2005 Ed
Thomson
3. 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
4. Herbert Moskowitz y Gordon P. Wright INVESTIGACION DE
OPERACIONES PRENTICE HALL INTERNATIONAL
5. Prawda, Juan METODOS Y MODELOS DE INVESTIGACION DE
OPERACIONES VOL I
6. HARVEY M. WAGNER PRINCIPLES OF OPERATIONS RESEARCH
Prentice Hall
7. Davis McKeown Modelos Cuantitativos para Administración Grupo
Editorial Iberoamericana
4
UNIVERSIDAD NACIONAL DE COLOMBIA
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA DE SISTEMAS E INDUSTRIAL
8. DANTZIG G LINEAR PROGRAMMING AND EXTENSIONS
X. LENGUAJES Y HERRAMIENTAS DE MODELADO
1. GAMS
2. GUROBI
3. LINDO/LINGO
4. MATLAB
5. MOSEL
6. SCILAB
7. Solver
8. TORA
9. WINDOWSQSB
10. AMPL [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.