PROGRAMACIÓN LINEAL
Código  Créditos  Horas Teóricas  Horas Prácticas Habilitable Validable
IIN-304 4 sem.  0 sem. Si Si 
Pertenece al pénsum de: 
Materiales Química  Industrial  Sistemas 
Electrónica Eléctrica  Mecánica  Sanitaria 

Universidad de Antioquia
Facultad de Ingeniería
Departamento de Ingeniería Industrial


PROGRAMACIÓN LINEAL
IIN-304


Créditos: 4
Horas teóricas semana: 4
Prerrequisito: INM- 275 (Álgebra lineal)
Correquisito: ISI-265 (Computadores I y Lab.)
Cursado por estudiantes de: Ingeniería Industrial, Ingeniería de Sistemas.

Semestre: 2003/1
Profesores: Hugo García Jiménez
Javier Gallego Márquez

 


OBJETIVOS GENERALES

· Valorar la importancia del uso de métodos cuantitativos
· Aprender a modelar y solucionar problemas de programación lineal así como a interpretar y hacer análisis de sensibilidad de la solución obtenida.
· Iniciar la adquisición de destrezas para utilizar algoritmos cuantitativos en la solución de diferentes clases de problemas que encontrará en su ejercicio profesional en todo tipo de organizaciones.


OBJETIVOS ESPECIFICOS


· Apreciar las ventajas y limitaciones de construir modelos matemáticos al tomar decisiones administrativas.
· Entender las características matemáticas y conceptuales de un modelo de programación lineal general y de programación lineal entera.
· Construir un modelo de programación lineal para encontrar la solución de algunos problemas típicos en la gestión de empresas.
· Comprender los algoritmos de solución de los modelos.
· Utilizar los algoritmos para obtener la solución de un modelo.
· Utilizar un programa de computadora para obtener la solución de un modelo.
· Interpretar la solución optima de un modelo.
· Escribir el modelo dual asociado a un modelo dado y entender el significado económico de las variables duales.
· Efectuar un análisis de sensibilidad de la solución óptima.
· Comprender uno de los algoritmos más usados para resolver problemas de programación entera.
· Utilizar un programa de computadora para resolver modelos de programación entera.


METODOLOGÍA

El profesor, con la participación activa de los estudiantes, construirá en el aula un modelo matemático de algunos problemas con características típicas, con el fin de que los estudiantes infieran el proceso lógico de la construcción de un modelo y reconozcan cuando este es lineal, a diferencia de los de otros tipos. Simultáneamente, el alumno debe practicar mucho por fuera del aula, contando con la asesoria del profesor. Este propondrá problemas adicionales para los cuales los estudiantes deben escribir el modelo ya sea de manera individual o en grupos.

Las actividades sobre el conocimiento y utilización de los algoritmos para resolver los modelos, se enfocarán en una forma comprensiva, sin enfatizar el trabajo mecánico de los estudiantes, pues la solución se obtendrá mediante un programa de computadora.

Después de que el alumno conozca el método simplex y lo comprenda y aplique correctamente, se hará énfasis en la eficiente utilización de un software especializado, en la interpretación de sus resultados y en el análisis de las variaciones en los parámetros y en otras características estructurales del modelo.

PROGRAMA RESUMIDO

1. Conocimientos generales de la programación lineal ( 2 horas)
2. Construcción de modelos de programación lineal (16 horas)
3. Solución grafica ( 2 horas)
4. Solución algebraica ( 4 horas)
5. Solución mediante algoritmo simplex tabular ( 6 horas)
6. Solución mediante un programa de computadora ( 2 horas)
7. Variables artificiales ( 2 horas)
8. Problema dual ( 4 horas)
9. Análisis de sensibilidad ( 6 horas)
10. Problema del transporte ( 2 horas)
11. Problema de la asignación ( 2 horas)
12. Programación lineal Entera ( 4 horas)


PROGRAMA DETALLADO

1. CONOCIMIENTOS GENERALES DE LA PROGRAMACIÓN LINEAL

Clase No 1

Actividades del Estudiante

· Leer algunos textos de la bibliografía sugerida y responder por escrito las preguntas formuladas por el profesor en el taller 1.

Conocimientos Específicos

· La investigación de operaciones y los modelos cuantitativos
· Formulación y modelación.
· Tipos de modelos
· El modelo matemático
· Qué es la programación lineal: Deducción del modelo de un problema sencillo.
· El modelo general de programación lineal
· Otros tipos de modelo
· Ventajas y limitaciones de los modelos cuantitativos
· Limitaciones de los modelos de programación lineal
· Consideraciones y supuestos del modelo de programación lineal.

2. CONSTRUCCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL

Clases 2 a 9

Actividades del Estudiante

· Participar activamente durante la clase en la construcción de un modelo para los problemas propuestos por el profesor.
· Trabajar, individualmente o en grupo, para escribir por fuera de la clase un modelo de los problemas asignados por el profesor o de otros que el propio estudiante elija del taller 2.

Conocimientos Específicos

· Pasos recomendados para construir un modelo cuantitativo de un problema
· Construcción de un modelo para problemas de algunos casos típicos, tales como:


o Programación de la producción (Mezcla optima de productos)
o Composición o Mezcla (Dietas)
o Planes de inversión
o Asignación de recursos (Administración de granjas)
o Programación de personal (Asignación de Turnos de trabajo)
o Programación de actividades
o Programas de corte
o Programas de transporte y asignación.


EVALUACIÓN No 1 Clase No 10 Prueba escrita [20%] Tarea [5%]

Actividades del estudiante

· Comprobar durante un examen individual por escrito, la competencia para la construcción de un modelo de dos problemas propuestos por el profesor
· Construir por fuera del aula, un modelo para el problema asignado por el profesor.


SOLUCIÓN DE UN MODELO DE PROGRAMACIÓN LINEAL

Clase 11

3. Solución grafica (Los fundamentos del método simplex)

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 3


Conocimientos específicos

· Región de Factibilidad: Infinito números de soluciones factibles
· Solución Optima
· Teorema Solución optima - punto extremo
· Conjunto de soluciones en los puntos extremos
· Restricciones activas y pasivas
· Tipo de solución que puede obtenerse

Clase 12

4. Solución Algebraica (Los fundamentos del método simplex)

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 4

Conocimientos específicos

· Tipo de la solución obtenida al resolver en forma algebraica un sistema de ecuaciones
· Formatos de presentación del modelo de programación lineal: General, estándar y canónico
· Las variables de holgura y su significado
· Soluciones básicas
· Algoritmo simplex para encontrar en forma algebraica la solución de un modelo de programación lineal, solo con restricciones de la forma menor o igual. Solución del modelo ya resuelto en forma gráfica.

Solución básica factible inicial
Variable de entrada --------------Criterio de mejorabilidad
Variable de salida -------------Criterio de Factibilidad
Solución óptima ------------ Criterio de inmejorabilidad

Clase 13

Paralelo entre la solución grafica y la algebraica

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 5

Conocimientos específicos

· Identificación del tipo de solución obtenida y equivalencia con lo aprendido en el método grafico.
· Los coeficientes de intercambio o sustitución
· El efecto neto.
· Solución de otro ejemplo


Clase 14

5. Simplex mediante tableros

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 6

Conocimientos específicos

· Reconocer que cada solución básica mejor (Sistemas de ecuaciones modificado) se obtiene de efectuar pivoteo en la solución anterior.
· Organizar cada solución básica en un tablero que presenta el sistema de ecuaciones modificado y otra información necesaria, a una forma más entendible y fácil de manipular o procesar.
· Identificar, comprender el significado y efectuar cálculos con los elementos del tablero simplex, tales como: efecto neto, coeficiente de intercambio o sustitución, base, inversa de la base, etc.

Clase 15

El simplex en forma matricial

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 7

Conocimientos específicos

· Expresión matricial y vectorial del modelo de programación lineal
· Principales relaciones matriciales - Deducción y comprensión
· Solución de un modelo utilizando las relaciones matriciales

Clase 16

6. Solución mediante un programa de computadora ( software WINQSB)

Actividades del estudiante

· Practicar el uso del software winqsb al resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 8


Conocimientos específicos
· Utilización del programa WINQSB para obtener la solución optima de modelos de: programación lineal general y entera, de redes de transporte y de redes de asignación.

 

 

EVALUACIÓN No 2 Clase No 17 [15%]


Actividades del estudiante

· Comprobar durante un examen individual por escrito, la competencia para la construcción de un modelo de los problemas propuestos por el profesor

Clase 18

7. Variables Artificiales

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 9

Conocimientos específicos

· Inclusión de variables artificiales para solucionar modelos con restricciones
de la forma ³ e =.
· Método de la gran M
· Método de las dos fases


ANALISIS DE VARIACIONES

Clase 19

8. PROBLEMA DUAL

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 10

Conocimientos específicos

· Concepto de dualidad - Utilidad marginal de los recursos - precio sombra
· El enfoque dual de un modelo de maximización y de un modelo de minimización
· Significado económico de las variables duales

Clase 20

Relaciones entre el modelo dual y el modelo primal

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 11

Conocimientos específicos

· Relaciones estructurales (Forma) y funcionales (Significado), entre los modelos primal y dual y sus tableros óptimos.
· Obtención del modelo dual a partir del modelo primal


9. ANÁLISIS DE SENSIBILIDAD

Clase 21
11
Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 12

Conocimientos específicos

· Necesidad de analizar la sensibilidad de la solución optima
· Cambio en los coeficientes objetivo
· Utilización del WIN QSB para el análisis.

Clase 22

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 13

Conocimientos específicos

· Cambios en los coeficientes del lado derecho
(Cantidad de los recursos disponibles o valores exigidos de algún componente)
· Utilización del WINQSB para el análisis.

Clase 23

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 14

Conocimientos específicos

· Adición de una variable
· Adición de una nueva restricción
· El algoritmo simplex - dual
· Utilización del WINQSB para el análisis.

 

Clase 24

Taller de Dualidad y sensibilidad

Actividades del estudiante

· Estudiar bien los temas correspondientes para participar en forma activa durante la clase, en la solución de algunos ejercicios de dualidad y sensibilidad.
Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija

Conocimientos específicos

· Responder las preguntas más frecuentes encontrados en el análisis de dualidad y sensibilidad.


EVALUACIÓN No 3 Clase No 25 Prueba[25%] Tarea[10%]

Conocimientos específicos

· Comprobar durante un examen individual por escrito, la competencia para la construcción y el análisis de un modelo de los problemas propuestos por el profesor
· Construir y analizar, por fuera del aula, un modelo para el problema asignado por el profesor.

PROBLEMAS ESPECIALES DE PROGRAMACIÓN LINEAL

Clase 26

10. Problema del transporte

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 15

Conocimientos específicos

· Formulación de un problema como problema del transporte
· Construcción del tablero inicial del problema del transporte
· Solución inicial - Métodos para obtenerla
· Solución optima - Algoritmo para obtenerla
· Utilización del WINQSB para resolver un problema del transporte

Clase 27

11. Problema de asignación

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 16

Conocimientos específicos

· Formulación de un problema como problema de asignación
· Construcción del tablero inicial del problema de asignación
· Solución de un problema de asignación - Algoritmo Húngaro
· Utilización del WINQSB para resolver un problema de asignación

PROGRAMACIÓN LINEAL ENTERA

Clase 28

Introducción a la programación lineal entera

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 17

Conocimientos específicos

· Introducción a la programación lineal entera
· Interpretación grafica de los modelos de programación lineal entera
· El algoritmo de ramificación y acotamiento


Clase 29

Caso practico

Actividades del estudiante

· Resolver por fuera de clase el ejercicio asignado por el profesor y otros que elija y responder las preguntas del taller 18

Conocimientos específicos

Utilización del WINQSB para analizar un caso practico que utilice la programación lineal entera.


EVALUACIÓN FINAL [25%]

Clase 30

***ACUMULATIVO

BIBLIOGRAFÍA

1. Anderson/Sweeney/Williams. Métodos cuantitativos para los negocios. Internacional Thomson editores, 7a edición, 1999.
2. Bonini/Hausman/Bierman. Análisis cuantitativo para los negocios. McGraw Hill. 9ª edición 2000.
3. Davis/Mckeown. Modelos cuantitativos para la administración. Grupo editorial Iberoamerica 1984.
4. Eppen/Gould/Schmidt/Jeffrey/Larry. Investigación de operaciones en la ciencia administrativa. 5a edición. Pearson 2000.
5. Taha. Investigación de operaciones, una introducción. 6ª edición .Prentice Hall 1998.
6. Mathur/Solow. Investigación de operaciones el arte en la toma de decisiones. ¡a edición. Prentice Hall Hispanoamericana. 1996.
7. Winston. Investigación de operaciones, aplicaciones y algoritmos. 1ª edición. Grupo editorial Iberoamerica. 1994.