Instituto Tecnológico Nacional de México
Tecnológico de Mexicali
Grupo A
Trabajo de exposición
Programación entera
Melanie Paola Lopez Montoya No. Control 23490513
Héctor Serrano Echeverria No. Control 23490513
Mtro. Daniel Diaz Sotuyo
Mexicali, Baja California. 2 de mayo del 2025.
Introducción y casos de aplicación.
La programación entera (PE) es una rama de la optimización matemática que se
encarga de resolver problemas en los que algunas o todas las variables deben
tomar valores enteros. Es una extensión de la programación lineal (PL), pero con
una restricción clave: las soluciones deben cumplir con condiciones de integridad, lo
cual introduce una gran complejidad computacional.
Introducción a la Programación Entera
Según las variables que se restringen a ser enteras, se clasifican los modelos en:
• Programación Entera Pura (PEP): Todas las variables deben ser enteras.
• Programación Entera Mixta (PEM o MILP): Solo algunas variables deben
ser enteras, el resto puede ser continua.
• Programación Binaria (0-1): Las variables enteras solo pueden tomar los
valores 0 o 1. Muy usada en problemas de decisión.
Casos de Aplicación
La programación entera se aplica en problemas reales donde las soluciones deben
ser discretas. Algunos ejemplos:
1. Problemas de asignación
Asignar recursos, tareas o personas a actividades de manera óptima, por ejemplo:
• Asignación de trabajadores a turnos.
• Asignación de máquinas a trabajos.
2. Problemas de planificación de producción
• Cuántas unidades producir de cada producto, considerando restricciones de
capacidad y demanda.
3. Problemas de ruteo y transporte
• Problema del Viajante (TSP): Encontrar la ruta más corta que visita una
serie de ciudades exactamente una vez y vuelve al origen.
• Problema del Vehículo (VRP): Determinar las rutas óptimas para una flota
de vehículos.
4. Problemas de corte y empaquetado
• Cortar materiales (como rollos de papel, madera, tela) en tamaños
específicos minimizando desperdicio.
5. Optimización de redes
• Flujo máximo, diseño de redes, selección de caminos óptimos.
6. Problemas de localización
• Determinar la ubicación óptima de instalaciones (almacenes, hospitales, etc.)
para minimizar costos o tiempos.
7. Problemas financieros y de inversión
• Selección de portafolios con decisiones binarias (invertir o no invertir en cierto
activo).
Definición y modelos de programación entera.
Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido
solamente si una parte o todas las variables de decisión toman valores restringidos
a números enteros, permitiendo incorporar en el modelamiento matemático algunos
aspectos que quedan fuera del alcance de los modelos de Programación Lineal.
Modelos de programación entera.
Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas:
Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).
Programación Entera Mixta (PEM) A esta categoría pertenecen aquellos problemas
de optimización que consideran variables de decisión enteras o binarias pero no de
forma exclusiva. De esta forma un problema de PEM puede considerarse como un
híbrido entre distintas categorías de modelamiento, siendo un caso típico aquel que
considera la mezcla de variables enteras y variables continuas (estas últimas
características de los modelos de Programación Lineal).
Programación Entera Pura (PEP) En esta categoría encontramos aquellos modelos
de Programación Entera que consideran exclusivamente variables de decisión que
adoptan valores enteros o binarios. Un ejemplo de ello son las siguientes
aplicaciones:
Método grafico de programación entera
Este método nos permite graficar las rectas correspondientes a las restricciones de
tal modo que delimita la región factible de solución. Posteriormente se identifican los
puntos enteros más próximos al límite de la zona de solución y se unen por medio
de una línea de modo que se habrá generado una nueva zona de solución formada
por esta y los ejes, estando la solución del problema de programación entera en uno
de los vértices, que será aquel que optimice la función objetivo. A continuación, se
muestra un ejemplo de un caso.
Pasos del método gráfico.
1. Formular el modelo matemático:
a. Definir la función objetivo.
b. Establecer las restricciones del problema.
c. Especificar que las variables deben ser enteras: x,y∈Z+x (enteros
positivos).
2. Graficar las restricciones:
a. Dibujar cada restricción como una línea recta en el plano x−yx-yx−y.
b. Determinar la región factible sombreando el área que satisface todas
las desigualdades.
3. Identificar los puntos enteros dentro de la región factible:
a. Estos son los pares ordenados (x,y)(x, y)(x,y) que están dentro o sobre
los límites de la región factible y cuyas coordenadas son enteras.
4. Evaluar la función objetivo en los puntos enteros:
a. Sustituir cada punto entero factible en la función objetivo.
b. Elegir el punto que maximiza o minimiza el valor de la función, según
sea el caso.
5. Seleccionar la mejor solución entera:
a. La solución óptima será el punto entero factible que da el mejor valor
de la función objetivo.
El método gráfico es una forma didáctica y visual de entender cómo se comportan
los modelos de programación entera con dos variables. A pesar de sus limitaciones,
es útil para el análisis manual de problemas pequeños, así como para enseñar la
diferencia entre soluciones continuas y enteras. Para problemas reales y más
complejos, se utilizan algoritmos computacionales más avanzados.
Método de ramificación y acotación.
El método comienza con una solución inicial del modelo de programación entera, la
cual puede ser encontrada a través del método de Gomory o de otro método similar.
Luego, se toma un subproblema de la solución, es decir, se selecciona una variable
que se encuentra en una fracción en la solución óptima. Se crea una nueva solución
que fija una cota inferior (floor) para la variable seleccionada, y se extiende la
solución anterior añadiendo la restricción creada.
Si la nueva solución aún no es entera, se divide en dos subproblemas: uno en el
que se fija la variable seleccionada en su cota inferior y otro en el que se fija en la
cota superior (ceiling). El proceso se repite para ambos subproblemas hasta que se
obtiene una solución entera. En cada iteración se genera una nueva cota superior
basada en la media de la cota inferior y superior.
Es una técnica que permite ir eliminando ciertos conjuntos de soluciones bajo
consideraciones. Esta consiste en una enumeración en árbol en el cual el espacio
de las variables enteras se divide de forma sucesiva dando lugar a problemas
lineales que se resuelven en cada nodo del árbol.
Cuyos problemas lineales se obtienen relajando las restricciones de integralidad y
añadiendo restricciones adicionales.
La idea básica en la que se apoya la técnica de ramificación y acotamiento es
divide y conquistaras. Cómo es demasiado complicado resolver en forma directa el
problema original “grande”, se divide en subproblemas cada vez más pequeños
hasta que éstos se puedan vencer. La división (ramificación) se hace mediante una
partición del conjunto completo de soluciones factibles en subconjuntos más
pequeños.
Método heurístico para problemas binarios
Reciben el nombre de algoritmos heurísticos, meta heurística o sencillamente
heurística. Este término deriva de la palabra griega heuriskein que significa
encontrar o descubrir y se usa en el ámbito de la optimización para describir una
clase de algoritmos de resolución de problemas. En el lenguaje coloquial,
optimizar significa poco más que mejorar; sin embargo, en el contexto científico la
optimización es el proceso de tratar de encontrar la mejor solución posible para un
determinado problema. En un problema de optimización existen diferentes
soluciones, un criterio para discriminar entre ellas y el objetivo es encontrar la
mejor. De forma más precisa, estos problemas se pueden expresar como
encontrar el valor de unas variables de decisión para los que una determinada
función objetivo alcanza su valor máximo o mínimo. El valor de las variables en
ocasiones está sujeto a unas restricciones. Podemos encontrar una gran cantidad
de problemas de optimización, tanto en la industria como en la ciencia. Desde los
clásicos problemas de diseño de redes de telecomunicación u organización de la
producción hasta los más actuales en ingeniería y re-ingeniería de software, existe
una infinidad de problemas teóricos y prácticos que involucran a la optimización.
Algunas clases de problemas de optimización son relativamente fáciles de
resolver. Este es el caso, por ejemplo, de los problemas lineales, en los que tanto
la función objetivo como las restricciones son expresiones lineales.
Uso de software (WIN QSB, TORA, DS for windows)
El uso de software en investigación de operaciones y optimización tiene como
objetivo principal facilitar la resolución de problemas matemáticos complejos, que
serían difíciles o lentos de resolver manualmente. Estos programas permiten ahorrar
tiempo, aumentar la precisión y visualizar resultados de forma clara, especialmente
en entornos educativos, empresariales e industriales.
Software
Tipo de problema Aplicación práctica
usado
WinQSB, Maximizar utilidad con recursos
Programación lineal
TORA limitados
Programación WinQSB, Selección de proyectos, asignación de
entera/binaria TORA tareas
WinQSB,
Redes (CPM/PERT) Planificación de proyectos
TORA
Árboles de decisión, DS for Evaluación de inversiones o
AHP Windows alternativas
WinQSB, Distribución de productos entre
Transporte y asignación
TORA plantas
Fuentes de consulta.
Tutoriales, G. (2016, 11 febrero). Qué es la Programación Entera. Gestión de Operaciones.
[Link]
entera/
López, B. S. (2022, 8 diciembre). Método gráfico. Ingenieria Industrial Online.
[Link]
grafico/
Faqsensei. (2024, 14 abril). ¿Qué es el método de ramificación y acotamiento? FAQSensei.
[Link]
El uso de software en investigación de operaciones y optimización tiene como objetivo
principal facilitar la resolución de problemas matemáticos complejos, que serían
difíciles o lentos de resolver manualmente.- Bing. (s. f.). Bing.
[Link]
%C3%B3n%20de%20operaciones%20y%20optimiza
