UNIVERSIDAD NACIONAL AUTÓNOMA

DE HONDURAS EN EL VALLE DE SULA

Carrera de Ingeniería Industrial

Asignatura de Investigación de Operaciones II

Programación Entera

Alejandro Tejeda Andino

Número de Cuenta:20152001741
Sección:1700

SPS, Julio de 2019.

Programación Entera UNAH-VS

Contenido
Introducción...........................................................................................................................................3
Programación Entera..............................................................................................................................4
Métodos de Resolución en Programación Entera..............................................................................4
Método de Ramificación y Acotamiento............................................................................................5
Tipos de planteamiento......................................................................................................................6
Herramientas......................................................................................................................................6
Desarrollo de Ejercicio............................................................................................................................7
Conclusión............................................................................................................................................20
Bibliografía...........................................................................................................................................21
Anexos.................................................................................................................................................22

Alejandro Tejeda 2
Programación Entera UNAH-VS

Introducción

En el siguiente informe se estará dando a conocer lo que es la Programación Lineal Entera.

Esta rama de la Programación Lineal que nos convierte los valores de las variables de
decisión y de la función objetivo en números enteros. En otras ocasiones envés de ser
números enteros se les da valores de “0” y “1” para tomar decisiones de “Sí” y “No”. A ese
tipo se le da otro nombre que veremos adelante. Además de los tipos de Programación Lineal
Entera, veremos los algoritmos de resolución más conocidos y un ejemplo del algoritmo
Ramificación y Acotamiento.

Alejandro Tejeda 3
Programación Entera UNAH-VS

Programación Entera

El campo de la programación lineal está compuesto por una rama llamada programación
entera. El concepto de <<entero>> significa que los valores de la solución óptima de las
variables de decisión y de sus restricciones deben ser números enteros.

En la Programación Entera existen 3 tipos de modelos:

Pura: Este tipo trata los problemas donde todas las variables de decisión deben ser enteras.

Binaria: Este tipo de modelo trata problemas donde los valores de las variables de decisión
deben ser 1 o 0. En otras palabras tomar una decisión en base a las opciones “Sí” y “No”.

Mixto: Este tipo trata de problemas donde puede haber variables enteras y continuas.

Métodos de Resolución en Programación Entera

Los algoritmos de resolución de Programación Entera se dieron en los años 50s. El pionero de
la Programación Entera es Ralph Gomory (Ver Imagen 1.1) que en 1958 en la Universidad de
Princeton formuló el primer algoritmo de plano de corte. Los tres tipos de Programación
entera pueden resolverse con varios tipos de algoritmos. A continuación, se mostrarán
algunos.

Pura: La programación entera pura es Utiliza los siguientes algoritmos

 Método Plano de Corte

 Método de Ramificación y Acotamiento
 Algoritmo Fraccional Entero de Gomory
 Algoritmo Entero Puro de Gomory

Alejandro Tejeda 4
Programación Entera UNAH-VS

Binaria: Utiliza los siguientes algoritmos:

 Método de Ramificación y Acotamiento

 Método Aditivo de Egon Balas
 Método Lexicográfico
 Método de Trubin

Mixta: Utiliza los siguientes algoritmos:

 Algoritmo Entero Mixto de Gomory

 Algoritmo de Land-Doig
 Método de Benders

Método de Ramificación y Acotamiento

El algoritmo de Ramificación y Acotamiento es uno de los métodos de resolución de

Programación Lineal entera más conocidos y usados. Este consiste en ir resolver el modelo de
programación lineal de la forma normal (Métodos Simplex o Método Gráfico), y al obtener
los valores óptimos de las variables de decisión y de la función objetivo, se va armando un
árbol de soluciones (Ver Imagen 1.2). Este árbol de decisiones está conformado por
restricciones nuevas que se van añadiendo (Variables de Ramificación) que hagan al
problema cumplir con las condiciones de la Programación Lineal Entera. (Ver Imagen 1.3)

Alejandro Tejeda 5
Programación Entera UNAH-VS

Tipos de planteamiento

 Planeación y Programación de Personal

 Problema del Viajero
 Problema de Gestión de Presupuesto
 Problema de Ubicación
 Carga Fija
 Problemas de Asignación

Herramientas

A continuación, se darán algunas herramientas que pueden hacer fácil la resolución de

problemas de la Programación Lineal Entera

Lingo

QB para Windows

TORA

Solver (Microsoft Excel)

Alejandro Tejeda 6
Programación Entera UNAH-VS

Desarrollo de Ejercicio

El siguiente ejercicio es un ejemplo de Programación Lineal Entera Pura.

Tenemos el modelo de programación lineal. Ahora debemos resolverlo sin tomar en

consideración la integralidad. En este caso lo resolveremos por método Simplex.

Alejandro Tejeda 7
Programación Entera UNAH-VS

Alejandro Tejeda 8
Programación Entera UNAH-VS

El resultado nos da X1=2.22 X2=1.55 y Zmax=391.11 Como los números deben ser enteros y
no decimales ahora empezamos con el algoritmo de Ramificación y Acotamiento.

Alejandro Tejeda 9
Programación Entera UNAH-VS

Hacemos nuestro árbol de soluciones empezando con P0. En ambas restricciones hay un valor
decimal, así que escogemos cualquier variable. En este caso escogeremos la variable X1 para
trabajar. En ella aplicamos una parte del algoritmo que dice que las nuevas restricciones a
añadir serán Xj ≤ N y Xj ≥ N +1 donde N es el número entero del valor óptimo de la variable
con la que estamos trabajado. Con esas nuevas restricciones se crean los nodos P1 y P2. Se
soluciona el modelo de programación lineal en ambos nodos con sus respectivas nuevas

restricciones.

Alejandro Tejeda 10
Programación Entera UNAH-VS

Terminamos con P1. Ahora vamos con P2.

Alejandro Tejeda 11
Programación Entera UNAH-VS

Alejandro Tejeda 12
Programación Entera UNAH-VS

En P2 todos los valores son enteros, por ende, dejamos de iterar en ese nodo. En P1 hay un
valor decimal y el Z es mayor que en P2 por es debemos seguir iterando en ese nodo.

Alejandro Tejeda 13
Programación Entera UNAH-VS

Alejandro Tejeda 14
Programación Entera UNAH-VS

Alejandro Tejeda 15
Programación Entera UNAH-VS

En P11 todos los valores son enteros así que terminamos en ese. Seguimos en P12 con X1 y
sus nodos P121 y P122

Alejandro Tejeda 16
Programación Entera UNAH-VS

Alejandro Tejeda 17
Programación Entera UNAH-VS

En P121 tenemos un valor de Z menor que el que ya teníamos en P2, así que paramos en ese
nodo. Mientras que en P122 la solución es infactible. Haciendo nuestra solución la P2. X1= 3
X2=0 y Z=360

Alejandro Tejeda 18
Programación Entera UNAH-VS

Alejandro Tejeda 19
Programación Entera UNAH-VS

Conclusión

Los algoritmos más utilizados según la investigación son los de Ramificación y Acotamiento
y está el de Plano de Corte. Se resolvió un ejemplo con Ramificación y Acotamiento al ser el
más conocido. Espero el informe haya podido enseñar cómo funciona ese algoritmo.

Como conclusión diría que la Programación Entera es casi igual a la Programación Lineal con
la diferencia que para hallar la solución óptima toma más pasos, por ende, lleva más tiempo
resolver. Es recomendable usar alguna de las herramientas antes mencionadas para que el
problema no lleve mucho tiempo.

Alejandro Tejeda 20
Programación Entera UNAH-VS

Bibliografía

Huffpost. (s.f.). Obtenido de https://www.huffpost.com/author/ralph-gomory

Taha, H. (2012). Investigación de Operaciones 9na Edición.

Lieberman, F. S. (2010). Introducción a la Investigación de Operaciones 9na Edición.

Investigación de Operaciones. (s.f.). Obtenido de

http://www.investigaciondeoperaciones.net/branch_and_bound.html

Alejandro Tejeda 21
Programación Entera UNAH-VS

Anexos

Imagen 1.1 Ralph Gomory pionero de la Programación Lineal Entera. Pg.4

IBM. (s.f.). Obtenido de https://researcher.watson.ibm.com/researcher/view_page.php?id=6922

Imagen 1.2 Ejemplo de un árbol de soluciones. En ella se puede observar que es un

problema de Programación Entera Binaria, ya que las restricciones que se van añadiendo
son “0” y “1”. Pg.5
SmartGrid. (s.f.). Obtenido de https://smart--grid.net/cours-lessons-theory/combinatorial-
optimization/branch-bound-english/

Alejandro Tejeda 22
Programación Entera UNAH-VS

Imagen 1.3 En estas tres imágenes se muestra lo que hace el algoritmo de Ramificación y
acotamiento con sus nuevas restricciones. Pg.5
Obtenido de MathWorks: https://la.mathworks.com/videos/mathematical-modeling-with-
optimization-part-3-problem-based-mixed-integer-linear-programming-1504298693853.html

Alejandro Tejeda 23