REPORTE DE ASIGNATURA
fecha y hora de generación: 27/09/2022 04:14 PMreporte impreso por: visitante [no identificado], para el período académico [ 2022-II ]
--- | visitante[no identificado] [visitante]

3006995 |  PROGRAMACIÓN LINEAL Y OPTIMIZACIÓN COMBINATÓRICA 
[ Información de la Asignatura ]
Asignatura vigente
Si
Unidad Académica Básica
ESCUELA DE MATEMATICAS
Créditos
4
Horas presenciales
4
Horas no presenciales
---
Validable
No
Libre Elección
No
Porcentaje Mínimo de Asistencia
%
Número de Semanas

[ Descripción de la Asignatura ]
Descripción
El objetivo del curso es introducir al estudiante a los problemas y técnicas de la optimización discreta o combinatórica. Incluye primero el estudio de la programación lineal y la teoría de la dualidad, con énfasis en la aplicación a problemas de optimiza
[ Planes Relacionados ]

códigoplan
3647CIENCIAS DE LA COMPUTACIÓN
3507MATEMÁTICAS
[ Contenidos ]



1. Introducción a la optimización
1. 1.1. Problemas 2. 1.2. Optimos locales y globales 3. 1.3. Conjuntos y funciones convexas 4. 1.4. Problemas de programación convexa


2. Programación Lineal: el Algoritmo Simplex
1. 2.1. Programación lineal 2. 2.2. Soluciones básicas posibles (sbp) 3. 2.3. Geometría de la programación lineal 4. 2.4. Pivoteo, organización de la tabla, algoritmo simplex


3. Dualidad
1. 3.1. Dual de un programa lineal 2. 3.2. Distensión complementaria 3. 3.3. Lema de Farka 4. 3.4. Algoritmo simplex dual


4. Complejidad del algoritmo simplex
1. 4.1. Computabilidad, cotas de tiempo, tamaño de la entrada 2. 4.2. Complejidad y análisis de algoritmos 3. 4.3. El algoritmo simplex no es polinomial 4. 4.4. Algoritmos polinomiales para programación lineal


5. Algoritmos primales-duales
1. 5.1. Algoritmo primal-dual 2. 5.2. Algoritmo aplicado al problema de caminos cortos en un grafo


6. Algoritmos para máximo flujo, apareamiento, camino más corto, árboles con cobertura total
1. 6.1.Algoritmo de Ford-Fulkerson para máximo flujo 2. 6.2. Algoritmo de Dijkstra para caminos cortos 3. 6.3. Algoritmos para apareamiento 4. 6.4. Algoritmos para árboles mínimos con cobertura total


7. Programación lineal entera
1. '7.1. Problema. Unimodularidad total. 2. '7.2. Problemas NP difíciles 3. '7.3 Cotas para soluciones. Cortaduras de Gomory.


8 Otros algoritmos
1. 8.1. Aproximación 2. 8.2. Acote y ramificación 3. 8.3. Programación dinámica 4. 8.4. Búsqueda local






















































































INFORMACIÓN IMPORTANTE
Señor Usuario:
Si encuentra inconsistencias en la información aqui presentada, por favor dirijase al Departamento, Escuela o Instituto que ofrece esta asignatura, con los documentos que permitan verificar la veracidad en los datos.