pc 359 marzo 2015_1

1

UNIVERSIDAD NACIONAL ABIERTA

VICERRECTORADO ACADMICO

SUBPROGRAMA DISEO ACADMICO

REA: INGENIERA

CARRERA: INGENIERA DE SISTEMAS

PLAN DE CURSO

I. Identificacin Nombre: APLICACIONES DE PROGRAMACIN ENTERA Y DINMICA Cdigo: 359 U.C: 4 Carrera: Ingeniera de Sistemas Cdigo: 236 Semestre: Formacin Profesional (Electiva) Prelaciones: Ninguna Requisito: 93 U.C. aprobadas, se recomienda haber cursado

Investigacin de Operaciones II (348) Autor: Lic. Jess Espinal (Especialista de contenido) Msc. Mara Eugenia Mazzei (Especialista de contenido) Asesores: Lic. Carmen Velsquez (Evaluadora de la carrera) Msc. Carmen Maldonado (Coordinadora de la carrera) Dr. Antonio Alfonzo (Diseo Instruccional) Prof. Mara Martn (Diseo Instruccional)

Nivel Central Caracas, abril 2015

Plan de curso: Aplicaciones de Programacin Entera y Dinmica cdigo 359

Elaborado por Prof. Jess Espinal y Prof.(a) Mara Eugenia Mazzei, UNA 2015

2

II. FUNDAMENTACIN

La Investigacin de Operaciones (IO) es un enfoque cientfico en la toma de decisiones que requiere el uso de uno o ms modelos matemticos. En este curso, se van a tocar dos tpicos de inters de la IO como son la Programacin Lineal Entera y la Programacin Dinmica. La Programacin Lineal es una herramienta para la toma de decisiones en problemas de optimizacin.

En muchos problemas prcticos, las variables de decisin slo tienen un sentido real si su valor es entero, como por ejemplo el hecho de asignar personas, mquinas o vehculos a las actividades, en cantidades enteras, entonces se trata de problemas de Programacin Lineal Entera.

El modelo matemtico para programacin entera es sencillamente el modelo de programacin lineal con la restriccin adicional de que las variables deben tener valores enteros.

La investigacin de operaciones tiene muchas ramas, una de ellas es la Programacin Dinmica, la cual es de gran utilidad en la toma de decisiones, es un procedimiento sistemtico para determinar la combinacin ptima. La Programacin Dinmica comnmente resuelve el problema en etapas, en cada una de las cuales interviene exactamente una variable de optimizacin, y los clculos en las diferentes etapas se enlazan a travs de clculos recursivos de manera que se genere una solucin ptima factible.

A travs de este curso, se pretende proporcionar a los estudiantes herramientas para la toma de decisiones, as como tambin potenciar la capacidad analtica y creatividad para plantear, formular, proponer soluciones y conclusiones sobre la base del anlisis de resultados representativos de situaciones del mundo real, lo cual fortalecer al egresado en su formacin y posterior desempeo profesional.

Esta asignatura est ubicada en el grupo de materias electivas, para completar

el desarrollo profesional del estudiante en el rea de Ingeniera y es por ello que la base conceptual se refuerza con ejercicios y un trabajo prctico, de esta forma se desarrolla el curso de una manera terico - prctico.

Para la administracin del curso, se dispondr del siguiente paquete instruccional:

1. Seleccin de lecturas: Aplicaciones de Programacin Entera y Dinmica, cdigo 359.

2. Texto Complementario: Hamdy Taha Investigacin de Operaciones 7 Edicin Edit. Pearson 7 edicin (Incluye CD-ROM)

3. Paquetes de Software de Optimizacin, tales como: TORA, WINQSB, DYNAMIC PROGRAMMING SOLVER u otros, estos constituyen herramientas de apoyo para resolver problemas de programacin lineal y dinmica, los cuales sern tiles para la ejercitacin y consecucin del trabajo prctico, adems pueden ser descargados gratis por Internet en http://cidia.unsa.edu.ar/iolas/software.



3

III. PLAN DE EVALUACION Orientaciones Generales

Las pruebas son de modalidad presencial y de desarrollo. Ponderacin de los objetivos: consiste en la asignacin de pesos a

los objetivos evaluables de la asignatura, de acuerdo con la importancia o complejidad que tienen. La escala de ponderacin de esta asignatura es de 1 a 5 puntos. Esta ponderacin est determinada por la incidencia de los objetivos evaluables en: el perfil de la carrera, el objetivo terminal de la asignatura y los objetivos de las asignaturas sobre las que existe prelacin.

Las especificaciones del trabajo prctico se suministran con la primera prueba parcial. Si el estudiante no va a presentar esta prueba, debe retirar un ejemplar de las especificaciones del trabajo prctico en el lugar de presentacin. El estudiante consignar el trabajo resuelto con la prueba integral.

Los objetivos N 3, 4 y 7, correspondientes a la realizacin del trabajo prctico, son requisito para aprobar la asignatura.

Nivel corrector: Nivel Central

MODALIDAD OBJETIVO CONTENIDO

PRIMERA PARCIAL

1 y 2 Mdulo I

SEGUNDA PARCIAL

5 y 6 Mdulo II

PRUEBA

INTEGRAL 1, 2, 5 y 6 Mdulo I y II

TRABAJO PRCTICO

3, 4 y 7 Mdulo I y II

M U O OBJETIVOS I

1 1 Formular problemas de Programacin Entera. 2 2 Resolver problemas de Programacin Entera a travs de los Mtodos de Ramificacin Acotamiento y/o el de Corte.

3 3 Implementar soluciones a situaciones de la vida real en problemas de costo fijo o ubicacin de planta. 4 4 Implementar soluciones a situaciones de la vida real a travs de algoritmos de reduccin de enumeracin y/o de corte.

II

5 5 Resolver problemas de Programacin Dinmica Determinstica, con un nmero finito de etapas. 6 6 Resolver problemas de Programacin Dinmica Probabilstica con un nmero finito de etapas. 7 7 Implementar Soluciones a problemas de la vida real bajo el enfoque de la Programacin Dinmica con un nmero infinito de etapas.

Peso mximo: 22 puntos Criterio de dominio: 17 Objetivo 1 2 3 4 5 6 7 Pesos 1-11 12-13 14 15 16 17 18 19-20 21 22 Peso 1 2 5 4 2 3 5 Calificaciones 1 2 3 4 5 6 7 8 9 10



4

ORIENTACIONES GENERALES En el almacn del Centro Local le entregarn el texto recomendado para este curso, previa presentacin del

comprobante de inscripcin de la asignatura. Se le recomienda resolver los ejercicios y autoevaluacin incorporados en cada unidad del texto UNA,

seguidamente verifique sus respuestas con las del texto; si estas fueron exitosas, siga adelante; en caso contrario, o de existir dudas, disponga de un cuaderno donde anote las dificultades presentadas en cada unidad, de manera que sean clarificadas con el profesor asesor de su Centro Local.

A fin de ampliar sus conocimientos, consulte en Internet los temas relacionados con Programacin Lineal Entera y

Programacin Dinmica Determinstica y Probabilstica. Se recomienda consultar la direccin: http://investigacion.operaciones.

Consulte con los asesores las dudas pertinentes a cada unidad, bien sea a travs del correo electrnico o de

manera presencial. Utilice Paquetes de Software de Optimizacin, tales como, TORAX, WINQSB, DYNAMIC PROGRAMMING

SOLVER u otros disponibles en el laboratorio de computacin de su centro local, para hallar la solucin a los problemas planteados o por la Pg. Web http://cidia.unsa.edu.ar/iolas/software. htm.

Si desea hacer algn comentario o sugerencia acerca del curso, comunquese con el profesor que administra la

asignatura, a travs de la direccin de correo electrnico [email protected] Interacte con sus compaeros; contrasten los resultados de los problemas, discutan acerca de sus dudas para una

mejora en su aprendizaje.



5

Objetivo

Contenido

1 Planteamiento del problema de Programacin Entera. Formulacin matemtica del problema de Programacin Entera. Resolucin del problema por redondeo.

2

Problemas de Programacin Entera a travs de los Mtodos de Enumeracin Implcita o Parcial. Algoritmo Aditivo. Mtodos de Corte. Mtodos de Ramificacin y Acotamiento.

3 Problemas de Costo Fijo y Ubicacin de Planta. Algoritmo exacto de Efroymson.

4 Problemas de Cubrimiento. Algoritmo de Reduccin. Algoritmo de Enumeracin Implcita. Algoritmo de Corte.

5 Programacin Dinmica Determinstica con un nmero finito de etapas. Principio de Optimalidad de Bellman. Ecuaciones Recursivas. Anlisis Retrospectivo.

6

Programacin Dinmica probabilstica con un nmero finito de etapas. Criterio de la esperanza matemtica, del valor actualizado y del valor medio. Procesos de decisin de Markov.

7

Problemas con una infinidad de etapas mediante Programacin Dinmica Determinstica. Criterio de la Esperanza Matemtica del valor actualizado y del valor medio y problemas de Programacin Dinmica Probabilstica.



6

IV. DISEO DE LA INSTRUCCIN DEL CURSO

OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIN

1

Lea la Unidad 1 del texto UNA planteamiento del problema de Programacin Entera. Esta unidad le proporcionar una visin general de la Programacin Entera.

Consulte en los libros recomendados el tema y resuelva los ejemplos de programacin entera.

Utilice el paquete de software de Optimizacin TORA o Excel Solver u otro que conozca, para probar los ejemplos formulados y analice los resultados obtenidos.

Realice los ejercicios propuestos, tanto en el Texto UNA como en el texto complementario.

Resuelva los ejercicios del texto de la UNA como de la bibliografa recomendada, para que obtenga un mayor dominio de la Programacin Entera y su Formulacin Matemtica.

Conforme un grupo de estudio, discuta con sus compaeros el contenido, los problemas y las vas de resultados.

Producto: Formulacin Matemtica de un problema de Programacin Entera. Procedimiento: Se valorar la correcta formulacin de problemas de Programacin Entera y la eleccin de las variables de decisin. Instrumento: Una prueba presencial donde se requerir la aplicacin de la formulacin matemtica y su resolucin por redondeo del problema planteado. Momento: Primera prueba parcial y la prueba integral.

2

Estudie la Unidad 2 del texto UNA Mtodos para resolver problemas de Programacin Entera, le permitir tener dominio en la solucin de problemas.

Resuelva los ejercicios propuestos en el texto UNA, los cuales le ayudarn en su fase de aprendizaje.

Pruebe los ejemplos resueltos con el paquete de software de Optimizacin TORA o cualquier otro que usted domine y compare los resultados.

Resuelva los ejercicios del texto de la UNA y los de la

Producto: Resolucin de problemas de Programacin Entera utilizando los mtodos de Ramificacin y Acotamiento y/o Corte. Procedimiento: Se valorar la correcta aplicacin de los Mtodos de:

Enumeracin. Algoritmos de ramificacin

acotamiento.

Objetivo del curso: Implementar, de manera lgica, modelos determinsticos y probabilsticos en el mbito de la Programacin Dinmica, as como modelos de Programacin Entera, aplicndolos en la resolucin de problemas.



7

OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIN bibliografa recomendada, con problemas de la Programacin Entera a travs de los mtodos de Ramificacin y Acotamiento y/o Corte.

Algoritmo de plano de corte. Instrumento: Una prueba presencial donde se requerirn los conocimientos bsicos de Programacin Entera. Momento: Primera prueba parcial y la prueba integral.

3

Estudie del texto UNA la Unidad 3: Aplicaciones de la Programacin Entera

Consulte en los libros recomendados los temas de esta unidad y resuelva los ejercicios.

Ejercite algunos de los problemas resueltos y propuestos en el texto, le permitirn afianzar los algoritmos presentados en las unidades.

Ponga en prctica los paquetes de optimizacin como el Torax o Excel Solver u otros que usted conozca o domine y compare los resultados con los ejercicios resueltos en los libros.

Consulte en Internet problemas que puedan resolver a travs del enfoque de la Programacin Entera.

Resuelva los ejercicios del texto UNA y los de la bibliografa recomendada, y adptelos a problemas cotidianos donde se aplique problemas de costo fijo y ubicacin de planta.

Producto: Obtencin de la solucin de problemas de la vida real, donde se aplique Costo Fijo y Ubicacin de Planta. Procedimiento: Se valorar la correcta implementacin de problemas de Costo Fijo y Ubicacin de Planta, empleando paquetes de optimizacin, para el anlisis de los resultados. Instrumento: Un trabajo prctico donde se requerir la aplicacin de los conocimientos tericos adquiridos en las unidad 3 de Programacin Entera en problemas de la vida real. Momento: Entregar el trabajo practico adjunto a la Prueba Integral.

4

Estudie del texto UNA la Unidad 4 Aplicaciones de la Programacin Entera

Consulte en los libros recomendados los temas de esta unidad y resuelva los ejercicios.

Ejercite algunos de los problemas resueltos y propuestos en el texto, los cuales le permitirn afianzar los algoritmos presentados en las unidades.

Ponga en prctica los paquetes de optimizacin como el Torax o Excel Solver u otros que usted conozca o domine y

Producto: Obtencin de la solucin de problemas de la vida real, donde se aplique los Algoritmos de Reduccin, Enumeracin Implcita y/o de Corte. Procedimiento: Se valorar la correcta implementacin de los Algoritmos, de Reduccin, Enumeracin Implcita y/o de Corte. Instrumento: Un trabajo prctico donde



8

OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIN compare los resultados con los ejercicios resueltos en los libros.

Consulte en Internet problemas que puedan resolver a travs del enfoque de la Programacin Entera.

Resuelva los ejercicios del texto UNA como de la bibliografa recomendada, y adptelos a problemas cotidianos donde se aplique los algoritmos de reduccin, enumeracin o de corte.

se requerir la aplicacin de los conocimientos tericos adquiridos en las unidad 3 de Programacin Entera en problemas de la vida real. Momento: Entregar el trabajo prctico adjunto a la prueba integral.

5

Lea la Unidad 4 del texto UNA Bases Tericas para Modelos Determinsticos con un nmero finito de etapas. Dicha unidad le permitir un dominio de las ecuaciones recursivas de la Programacin Dinmica referente a modelos determinsticos.

Enfatice su estudio en el principio de optimalidad de Bellman y su importancia en la obtencin de la solucin ptima del Problema de Programacin Dinmica.

Resuelva los ejercicios del texto UNA referentes al tema y los propuestos para poder manejar las ecuaciones recursivas en la resolucin numrica de los problemas.

Haga un anlisis retrospectivo de los problemas relacionados con la Programacin Dinmica.

Resuelva los ejercicios del texto UNA y los de la bibliografa recomendada, para que obtenga la destreza necesaria para la solucin de problemas de Programacin Dinmica.

Producto: Obtencin de la solucin de problemas aplicando Programacin Dinmica Determinstica. Procedimiento: Se valorar la correcta formulacin de las ecuaciones recursivas con un nmero finito de etapas. Instrumento: Una prueba presencial de desarrollo donde se resolvern problemas aplicando las tcnicas de la Programacin Dinmica Determinstica con un nmero finito de etapas.

Momento: Segunda prueba parcial y la prueba integral.



9

OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIN

6

Estudie la Unidad 5 del texto UNA Programacin Dinmica en Porvenir Aleatorio con un conjunto Finito de Etapas. Esta unidad le permitir utilizar las ecuaciones recursivas de la Programacin Dinmica para Modelos Probabilsticos.

Resuelva problemas mediante las ecuaciones recursivas de la Programacin Dinmica para modelos probabilsticos.

Realice ejercicios con las ecuaciones recursivas para la resolucin numrica de problemas.

Resuelva los ejercicios del texto de la UNA y los de la bibliografa recomendada, para que obtenga un mayor dominio de la Programacin Dinmica Probabilstica.

Producto: Obtencin de la solucin de un problema dado, aplicando Programacin Dinmica Probabilstica Procedimiento: Se valorar la correcta aplicacin de la Programacin Dinmica Probabilstica, a travs de las ecuaciones recursivas a fin de obtener la solucin a un problema dado. Instrumento: Una prueba presencial de desarrollo donde se resolvern problemas de Programacin Dinmica Probabilstica con un nmero finito de etapas. Momento: Segunda prueba parcial y la prueba integral.

7

Estudie la unidad 6 del texto UNA Aplicaciones de Modelos Determinsticos con un nmero infinito de etapas, le permitir utilizar las ecuaciones recursivas de la Programacin Dinmica para Modelos Determinsticos y Probabilsticos en la resolucin del trabajo practico.

Ponga en prctica los paquetes de optimizacin con los ejercicios resueltos encontrados en los libros y compare los resultados.

Analice la convergencia de la funcin objetivo cuando el nmero de etapas es infinito.

Resuelva los ejercicios del texto UNA y de los recomendados referentes al tema, as como los propuestos.

Consulte en Internet problemas que puedan resolverse a travs del enfoque de la Programacin Dinmica.

Resuelva los ejercicios del texto UNA y los de la bibliografa recomendada, y adptelos a problemas cotidianos donde se aplique la Programacin Dinmica.

Producto: Obtencin de la solucin a problemas aplicando Programacin Dinmica Determinstica y Probabilstica con infinidad de etapas. Procedimiento: Se valorar la correcta aplicacin de la Programacin Dinmica a problemas con infinidad de Etapas, utilizando el paquete de optimizacin para el anlisis del resultado. Instrumento: trabajo prctico. Momento: Entregar el trabajo prctico adjunto a la prueba integral.

10

V. BIBLIOGRAFA

Obligatoria Seleccin de lecturas (2015) Espinal, J. Aplicaciones de Programacin Entera y Dinmica cdigo 359 Caracas UNA. Complementaria Daz M, Rubn (1987) Investigacin de Operaciones I. 1era edicin. Caracas. UNA. Hillier F., y Lieberman G., (2001) Investigacin de Operaciones. 7 edicin. Mxico.

McGraw Hill. Moskowitz H., y Wright G., (1982) Investigacin de Operaciones. Mxico. Prentice-Hall. Prawda Juan, (1976) Mtodos y Modelos de Investigacin de Operaciones. 1era edicin.

Mxico. Limusa. Ros S., Ros D., Mateos A., y Martn J. (1998) Programacin Lineal y Aplicaciones. Ejercicios resueltos. Mxico Rama.

Taha, Hamdy A., (1998) Investigacin de Operaciones, una introduccin. 7ma edicin.

Mxico. Educacin Pearson.



pc 359 marzo 2015_1

Documents