1

UNIVERSIDAD NACIONAL ABIERTA

VICERRECTORADO ACADEMICO
SUBPROGRAMA DE DISEÑO ACADÉMICO
AREA: INGENIERÍA / CARRERA: INGENIERÍA DE
SISTEMAS

PLAN DE CURSO
I. Identificación

Nombre: APLICACIONES DE PROGRAMACIÓN ENTERA Y DINÁMICA

Código: 359

U.C: 4

Carrera: Ingeniería de Sistemas

Código: 236

Semestre: Formación Profesional (Electiva)

Prelaciones: Ninguna

Requisito: 93 U.C. aprobadas, se recomienda haber cursado

Investigación de Operaciones II (348)

Autor: Lic. Jesús Espinal (Especialista de contenido)

Teléfono: (0212) -555 -2087
Correo electrónico: jespinal@una.edu.ve
Msc. María Eugenia Mazzei (Especialista de contenido)
Teléfono: (0212) –555 -2376
Correo electrónico: mmazzei@una.edu.ve
Asesores: Lic. Carmen Velásquez (Evaluadora de la carrera)
Msc. Carmen Maldonado (Coordinadora de la carrera)
Dr. Antonio Alfonzo (Diseño Instruccional)

Nivel Central
Caracas, Abril 2012
 2

II. FUNDAMENTACIÓN

La Investigación de Operaciones (IO), es un enfoque científico en la toma de

decisiones que requiere el uso de uno o más modelos matemáticos, la
Programación Lineal es una herramienta para la toma de decisiones en problemas
de optimización. En 1947 George Dantzig desarrolló un método efectivo,
denominado el algoritmo simplex, para resolver problemas de Programación Lineal
con dos o más variables. En este curso se van a tocar dos tópicos de interés de la
IO como son la Programación Lineal Entera y la Programación Dinámica.

En muchos problemas prácticos, las variables de decisión sólo tienen un sentido

real si su valor es entero, como por ejemplo el hecho de asignar personas,
máquinas o vehículos a las actividades, en cantidades enteras, entonces se trata
de problemas de Programación Lineal Entera. El modelo matemático para
programación entera es sencillamente el modelo de programación lineal con la
restricción adicional de que las variables deben tener valores enteros.
La investigación de operaciones tiene muchas ramas una de ellas es la
Programación Dinámica la cuál es de gran utilidad en la toma de decisiones, es
un procedimiento sistemático para determinar la combinación óptima. La
Programación Dinámica comúnmente resuelve el problema en etapas, donde en
cada etapa interviene exactamente una variable de optimización, y los cálculos en
las diferentes etapas se enlazan a través de cálculos recursivos de manera que se
genere una solución óptima factible.
A través de este curso se pretende proporcionar a los estudiantes herramientas
para la toma de decisiones, así como también capacidad analítica y creatividad
para plantear, formular, proponer soluciones y conclusiones sobre la base del
análisis de resultados representativos de situaciones del mundo real, lo cual
fortalecerá al egresado en su formación y posterior desempeño profesional.

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

desarrollo profesional del estudiante en el área de Ingeniería y es por ello que la
base conceptual se refuerza con ejercicios y un trabajo práctico, de esta forma se
desarrolla el curso de una manera teórico - práctico.
Para la administración del curso se concibe el siguiente paquete instruccional:
 Texto UNA: Aplicaciones de Programación Entera y Dinámica código 359
 Texto Complementario: Hamdy Taha Investigación de Operaciones 7°
Edición Edit. Pearson 7 edición (Incluye CD-ROM)
 Paquetes de Software de Optimización, tales como: TORA, WINQSB,
DYNAMIC PROGRAMMING SOLVER u otros, éstos constituyen
herramientas de apoyo para resolver problemas de programación lineal, y
dinámica, los cuales serán útiles para la ejercitación y consecución del
trabajo práctico, además pueden ser descargados gratis por Internet en
http://cidia.unsa.edu.ar/iolas/software .

Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359

Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2012
 3
III. PLAN DE EVALUACION
Orientaciones Generales MODALIDAD OBJETIVO CONTENIDO
Módulo: I
 Las pruebas son de modalidad presencial y de desarrollo. PRIMERA Unidades: 1 y 2
1, 2, 5 y 6
 Ponderación de los objetivos: La ponderación consiste en la PRUEBA Módulo: II
asignación de pesos a los objetivos evaluables de la asignatura, de INTEGRAL Unidades: 5y6
acuerdo con la importancia y/o complejidad que tienen. La escala de Módulo: I
ponderación de esta asignatura es de 1 a 5 puntos. Esta SEGUNDA Unidades: 1 y 2
1, 2, 5 y 6
ponderación está determinada por la incidencia de los objetivos PRUEBA Módulo: II
evaluables en: el perfil de la carrera, el objetivo terminal de la INTEGRAL Unidades: 5y6
asignatura y los objetivos de las asignaturas sobre las que existe
prelación.
 Las especificaciones del trabajo práctico se publican la primera Módulo: I
semana de presentación de las pruebas. El estudiante consignará el Unidades: 3y4
TRABAJO
trabajo resuelto con la segunda prueba integral. 3, 4 y 7 Módulo: II
PRÁCTICO Unidad: 7
 Los objetivos 3, 4 y 7, correspondientes a la realización del trabajo
práctico, son requisito para aprobar la asignatura.

M UO OBJETIVOS
11 Formular problemas de Programación Entera.
I
22 Resolver problemas de Programación Entera utilizando los Métodos de Ramificación – Acotamiento y/o el de
Corte.
3 3 Implementar Soluciones a situaciones de la vida real en problemas de costo fijo o ubicación de planta.
4 4 Implementar Soluciones a situaciones de la vida real aplicando algoritmos de reducción de enumeración y/o de
corte.
5 5 Resolver problemas de Programación Dinámica Determinística, con un número finito de etapas.
6 6 Resolver problemas de Programación Dinámica Probabilística con un número finito de etapas.
II
7 7 Implementar Soluciones a problemas de la vida real bajo el enfoque de la Programación Dinámica con un
número infinito de etapas.
Peso máximo: 22 puntos Criterio de dominio: 17
Obje 1 2 3 4 5 6 7 Pesos 1-11 12-13 14 15 16 17 18 19-20 21 22
tivo
Peso 1 2 5 4 2 3 5 Calificacione 1 2 3 4 5 6 7 8 9 10
Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359
Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 4
s

ORIENTACIONES GENERALES

 El texto recomendado para este curso, lo entregarán en el almacén del Centro Local, previa presentación
del comprobante de inscripción de la asignatura.

 Resuelva los ejercicios y autoevaluación 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 Programación
Lineal Entera y Programación Dinámica Determinística y Probabilística.

 Consulte con los asesores las dudas pertinentes a cada unidad, bien sea a través del correo electrónico o
de manera presencial.

 Utilice Paquetes de Software de Optimización, tales como, TORAX, WINQSB, DYNAMIC PROGRAMMING
SOLVER u otros disponibles en el Laboratorio de Computación de su centro local, para hallar la solución a
los problemas planteados.

 Si desea hacer algún comentario o sugerencia acerca del curso, comuníquese con el profesor que
administra la asignatura, a través de la dirección de correo electrónico lparraga@una.edu.ve

 Interactúe con sus compañeros; contrasten los resultados de los problemas, discutan acerca de sus dudas
para una mejora en su aprendizaje.

Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359

Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 5

Objetivo Contenido
Planteamiento del problema de Programación Entera. Formulación matemática del
1
problema de Programación Entera. Resolución del problema por redondeo.
Problemas de Programación Entera utilizando los Métodos de Enumeración Implícita
2 o Parcial. Algoritmo Aditivo. Métodos de Corte. Métodos de Ramificación y
Acotamiento.
Problemas de Costo Fijo y Ubicación de Planta. Algoritmo exacto de Efroymson.
3

Problemas de Cubrimiento. Algoritmo de Reducción. Algoritmo de Enumeración

4
Implícita. Algoritmo de Corte.
Programación Dinámica Determinística con un número finito de etapas. Principio de
5
Optimalidad de Bellman. Ecuaciones Recursivas. Análisis Retrospectivo.
Programación Dinámica probabilística con un número finito de etapas. Criterio de la
6 esperanza matemática, del valor actualizado y del valor medio. Procesos de decisión
de Markov.
Problemas con una infinidad de etapas mediante Programación Dinámica
7 Determinística. Criterio de la Esperanza Matemática del valor actualizado y del valor
medio y problemas de Programación Dinámica Probabilística.
IV. DISEÑO DE LA INSTRUCCIÓN DEL CURSO

Objetivo del curso: Implementar de manera lógica, modelos determinísticos y probabilísticos en el ámbito de la
Programación Dinámica, así como modelos de Programación Entera, aplicándolos en la resolución de problemas.
Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359
Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 6

OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIÓN

 Lea la Unidad 1 del texto UNA “planteamiento del problema Producto: Formulación Matemática de
de Programación Entera”. Esta unidad le proporcionará una un problema de Programación Entera.
visión general de la Programación Entera. Procedimiento: Se valorará la correcta
 Consulte en los libros recomendados, el tema y resuelva los formulación de problemas de
ejemplos de programación entera. Programación Entera y la elección de las
 Utilice el paquete de software de Optimización TORA o Excel variables de decisión.
Solver u otro que conozca, para probar los ejemplos Instrumento: Una prueba presencial
1 formulados y analice los resultados obtenidos. donde se requerirá la aplicación de la
formulación matemática y su resolución
 Realice los ejercicios propuestos tanto en el Texto UNA como
por redondeo del problema planteado.
en el texto complementario.
 Resuelva los ejercicios del texto de la UNA como de la Momento: Primera y segunda prueba
bibliografía recomendada, para que obtenga un mayor integral.
dominio de la Programación Entera y su Formulación
Matemática.
 Conforme un grupo de estudio, discuta con sus compañeros
el contenido, los problemas y las vías de resultados.
2  Estudie la Unidad 2 del texto UNA “Métodos para resolver Producto: Resolución de problemas de
problemas de Programación Entera”. Dicha unidad le Programación Entera utilizando los
permitirá tener dominio en la solución de problemas. métodos de Ramificación y Acotamiento
 Resuelva los ejercicios propuestos en el texto UNA, los y/o Corte.
cuales le ayudaran en su fase de aprendizaje. Procedimiento: Se valorará la correcta
 Pruebe los ejemplos resueltos con el paquete de software de aplicación de los Métodos de:
Optimización TORA o cualquier otro que usted domine y  Enumeración.
compare los resultados.  Algoritmos de ramificación –
 Resuelva los ejercicios del texto de la UNA como de la acotamiento.
bibliografía recomendada, con problemas de la Programación  Algoritmo de plano de corte.
Entera utilizando los métodos de Ramificación y Acotamiento Instrumento: Una prueba presencial
y/o Corte. donde se requiriera los conocimientos
básicos de Programación Entera.

Momento: Primera y segunda prueba

integral.
Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359
Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 7
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIÓN

 Estudie del texto UNA la Unidad 3 “Aplicaciones de la Producto: Obtención de la solución de

Programación Entera” problemas de la vida real, donde se
 Consulte en los libros recomendados los temas de esta aplique Costo Fijo y Ubicación de Planta.
unidad y resuelva los ejercicios. Procedimiento: Se valorará la correcta
 Ejercite algunos de los problemas resueltos y propuestos en implementación de problemas de Costo
el texto, los cuales le permitirán afianzar los algoritmos Fijo y Ubicación de Planta, empleando
presentados en las unidades. paquetes de optimización, para el
análisis de los resultados.
 Ponga en práctica los paquetes de optimización como el
3 Instrumento: Un trabajo práctico donde
Torax o Excel Solver u otros que usted conozca o domine y
se requerirá la aplicación de los
compare los resultados con los ejercicios resueltos en los
conocimientos teóricos adquiridos en las
libros.
unidad 3 de Programación Entera en
 Consulte en Internet problemas que puedan resolver a través problemas de la vida real.
del enfoque de la Programación Entera.
 Resuelva los ejercicios del texto UNA como de la bibliografía Momento: Entregar el trabajo practico
recomendada, y adáptelos a problemas cotidianos donde se adjunto a la segunda Prueba Integral.
aplique problemas de costo fijo y ubicación de planta.

4  Estudie del texto UNA la Unidad 4 “Problemas de Producto: Obtención de la solución de

Cubrimiento” problemas de la vida real, donde se
 Consulte en los libros recomendados los temas de esta aplique los Algoritmos de Reducción,
unidad y resuelva los ejercicios. Enumeración Implícita y/o de Corte.
 Ejercite algunos de los problemas resueltos y propuestos en Procedimiento: Se valorará la correcta
el texto, los cuales le permitirán afianzar los algoritmos implementación de los Algoritmos, de
presentados en las unidades. Reducción, Enumeración Implícita y/o de
Corte.
 Ponga en práctica los paquetes de optimización como el
Instrumento: Un trabajo práctico donde
Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359
Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 8
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIÓN
Torax o Excel Solver u otros que usted conozca o domine y se requerirá la aplicación de los
compare los resultados con los ejercicios resueltos en los conocimientos teóricos adquiridos en las
libros. unidad 4 en problemas de cubrimiento y
 Consulte en Internet problemas que puedan resolver a través de corte en situaciones de la vida real.
del enfoque de la Programación Entera.
 Resuelva los ejercicios del texto UNA como de la bibliografía Momento: Entregar el trabajo practico
recomendada, y adáptelos a problemas cotidianos donde se adjunto a la Segunda Prueba Integral.
aplique los algoritmos de reducción, enumeración o de corte.

 Lea la Unidad 5 del texto UNA “Bases Teóricas para Modelos Producto: Obtención de la solución de
Determinísticos con un número finito de etapas”. Dicha unidad problemas aplicando Programación
le permitirá un dominio de las ecuaciones recursivas de la Dinámica Determinística.
Programación Dinámica referente a modelos determinísticos. Procedimiento: Se valorará la correcta
 Enfatice su estudio en el principio de optimalidad de Bellman formulación de las ecuaciones recursivas
y su importancia en la obtención de la solución óptima del con un número finito de etapas.
Problema de Programación Dinámica. Instrumento: Una prueba presencial de
 Resuelva los ejercicios del texto UNA referentes al tema así desarrollo donde se resolverán
5 problemas aplicando las técnicas de la
como los propuestos para poder manejar las ecuaciones
recursivas en la resolución numérica de los problemas. Programación Dinámica Determinística
con un número finito de etapas.
 Haga un análisis retrospectivo de los problemas relacionados
con la Programación Dinámica. Momento: Primera y segunda prueba
 Resuelva los ejercicios del texto UNA como de la bibliografía integral.
recomendada, para que obtenga la destreza necesaria para la
solución de problemas de Programación Dinámica.

Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359

Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 9
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIÓN
 Estudie la Unidad 6 del texto UNA “Programación Dinámica Producto: Obtención de la solución de
en Porvenir Aleatorio con un conjunto Finito de Etapas”. Esta un problema dado, aplicando
unidad le permitirá utilizar las ecuaciones recursivas de la Programación Dinámica Probabilística
Programación Dinámica para Modelos Probabilísticos. Procedimiento:
 Resuelva problemas mediante las ecuaciones recursivas de Se valorará la correcta aplicación de la
la Programación Dinámica para modelos probabilísticos. Programación Dinámica Probabilística, a
 Realice ejercicios con las ecuaciones recursivas para la través de las ecuaciones recursivas a fin
resolución numérica de problemas. de obtener la solución a un problema
6 dado.
 Resuelva los ejercicios del texto de la UNA como de la
Instrumento: Una prueba presencial de
bibliografía recomendada, para que obtenga un mayor
desarrollo donde se resolverán
dominio de la Programación Dinámica Probabilística.
problemas de Programación Dinámica
Probabilística con un número finito de
etapas.
Momento: Primera y segunda prueba
integral.

7  Estudie la unidad 7 del texto UNA “Aplicaciones de Modelos Producto: Obtención de la solución a
Determinísticos con un número infinito de etapas”. Esta problemas aplicando Programación
unidad le permitirá utilizar las ecuaciones recursivas de la Dinámica Determinística y Probabilística
Programación Dinámica para Modelos Determinísticos y con infinidad de etapas.
Probabilísticos en la resolución del trabajo practico. Procedimiento:
 Ponga en práctica los paquetes de optimización con los Se valorará la correcta aplicación de la
ejercicios resueltos encontrados en los libros y compare los Programación Dinámica a problemas con
resultados. infinidad de Etapas, utilizando el
 Analice la convergencia de la función objetivo cuando el paquete de optimización para el análisis
número de etapas es infinito. del resultado.
 Resuelva los ejercicios del texto UNA y de los recomendados Instrumento: Trabajo práctico.
referentes al tema, así como los propuestos. Momento: Entregar el Trabajo práctico
 Consulte en Internet problemas que puedan resolverse a adjunto a la Segunda Prueba Integral
través del enfoque de la Programación Dinámica.
 Resuelva los ejercicios del texto UNA como de la bibliografía
recomendada, y adáptelos a problemas cotidianos donde se
Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359
Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 10
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIÓN
aplique la Programación Dinámica

Plan de curso: Aplicaciones de Programación Entera y Dinámica código 359

Elaborado por Prof. Jesús Espinal y Prof.(a) María Eugenia Mazzei UNA 2018
 11

V. BIBLIOGRAFÍA

Obligatoria

González, J. Juricek, L. Ortiz R. (1984) Aplicaciones de Programación Entera y Dinámica

código 359 Caracas UNA.

Complementaria

Díaz M, Rubén (1987) Investigación de Operaciones I. 1era edición. Caracas. UNA.

Hillier F., y Lieberman G., (2001) Investigación de Operaciones. 7° edición. México. McGraw
Hill.

Moskowitz H., y Wright G., (1982) Investigación de Operaciones. México. Prentice-Hall.

Prawda Juan, (1976) Métodos y Modelos de Investigación de Operaciones. 1era edición.

México. Limusa.

Ríos S., Ríos D., Mateos A., y Martín J. (1998) Programación Lineal y Aplicaciones.
Ejercicios resueltos. México Rama.

Taha, Hamdy A., (1998) Investigación de Operaciones, una introducción. 7ma edición.
México. Educación Pearson.