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.
La programación entera es el método empleado para resolver problemas
que tienen variables de decisión enteras. Estos modelos se han
considerado submodelos de la programación lineal con la característica
de enteridad.
Objetivo general: Resolver problemas en los que se empleen variables
enteras, utilizando los algoritmos de solución que se ajusten a las
características de dichos problemas.
Objetivos específicos
• Definir las características de un problema, enfocando su algoritmo
de solución.
• Formular un problema específico utilizando el método de
programación entera.
• Manejar algunas de las técnicas básicas utilizadas en la solución de
problemas de programación entera.
Los modelos de programación entera se pueden clasificar
en: programación entera mixta (PEM), programación entera pura (PEP) y
programación entera binaria (PEB).
¿Cómo resolver un caso de programación entera?
Para la resolución de problemas relacionados con programación entera,
existen varios métodos para generar las restricciones especiales que
conducen la solución óptima del problema, pero también hacia la
solución óptima entera deseada. Se requiere que una solución factible
tenga valores enteros para alguna o todas las variables de decisión. La
región factible no es una región continua, sino que está formada por
puntos separados.
Un modelo de programación entera recibe el nombre de relajado si no se
toma en cuenta la restricción de soluciones enteras. El modelo de
programación entera relajado es el modelo de programación lineal.
Algunos de los métodos más empleados son:
• Método de redondeo de la solución de programación lineal.
• Método de enumeración completa.
• Método de ramificación y acotación (Branch and Bound)
• Método planos cortantes o algoritmo fraccional de Gomory
Ejemplo Método de redondeo de la solución de programación lineal.
Máx. Z = x1 + 5x2
Sujeto a: +x1 + 10x2 ≤ 20x1 ≤ 2
• Solución modelo relajado (PL): x1 =2 x2 =1.8 Z=11
• Solución con redondeo: x1 =2x2 =1 Z=7
• Solución óptima de PE: x1=0 x2 =2 Z=10
Al redondear se debe tener en cuenta la magnitud de las variables
• Si la solución es: Z = 5,207
x1 = 11.6
X2 = 6.8 NO es conveniente redondear
• Si en cambio: Z=5,207
x1 = 3,208.4 redondear puede ser
X2 = 7,055.3 aceptable.
Siempre se debe verificar que la solución redondeada se mantenga
factible.
Análisis de sensibilidad
Es un análisis que busca determinar los efectos producidos en la solución
óptima por un cambio en cualquier parámetro de un modelo de
programación lineal. Se investiga cómo afectará una modificación en los
coeficientes de las variables básicas y no básicas, en los recursos
disponibles o si se introduce una nueva restricción.
El objetivo es el de determinar hasta qué punto es fiable la solución óptima
según las alteraciones que puedan darse. Hay que tener en cuenta que la
solución se basa en que los datos de partida se mantendrán constantes, lo
cual solo se da en periodos de tiempo cortos. Por tanto, al utilizar este
análisis, se puede prever cómo se comportará ante los cambios que
posiblemente surjan.
También contribuye a determinar qué parámetros o variables pueden
fluctuar sin que estos afecten a la solución óptima.
Principales beneficios:
• Facilita la toma de decisiones: El análisis de sensibilidad da como
resultados pronósticos respaldados por datos. Cuando se consideran
todas las variables y se analizan todos los resultados, le resulta más
sencillo a la gerencia tomar decisiones de inversión. Por lo tanto, es
una herramienta extremadamente útil para la planificación futura de
la empresa.
• Asegura el control de calidad: Con el análisis de la sensibilidad, las
compañías pueden determinar aquellos procesos que no están
permitiendo la creación de un producto útil e impiden el alcance de
objetivos. Determinar aquellos errores a tiempo ayudará a crear
mejores productos y a menor tiempo, lo que puede generar en el
futuro una mayor diversificación.
• Mejor asignación de recursos: El análisis de sensibilidad permite
identificar las áreas fuertes y débiles de la planificación de un
proyecto, a su vez que mide su posible impacto en los resultados.
Esto permite a las organizaciones dirigir los recursos a las variables
que más apoyo necesitan.
¿Cómo se resuelve un caso de programación lineal?
El análisis de sensibilidad se realiza después de obtener la solución optima de un
modelo lineal para determinar como afectan los cambios en los parámetros del
modelo a la solución optima calculada. Los cambios se pueden producir en la
matriz de coeficientes A, en el vector de recursos b y en el vector de precios c.
También se puede analizar cómo afectaría a la solución optima añadir nuevas
restricciones o nuevas variables al modelo.
Los métodos de análisis de sensibilidad ahorran un número considerable de
iteraciones ya que parten de la solución ´optima del modelo inicial para analizar
el efecto de los cambios
En los cambios discretos que vamos a analizar utilizaremos el siguiente problema
de producción para hacer ejemplos prácticos en cada caso.
En una empresa se quieren utilizar los recursos 1 y 2 en la producción de los
productos A, B y C. La cantidad unitaria necesaria de cada recurso para cada
tipo de producto, la cantidad disponible de cada recurso y el beneficio unitario
de cada producto.
recursos Productos
1
A B C Disponibilidad de recursos
2
4 2 3 40
2 2 1 30
Beneficio 3 2 1
Para maximizar el beneficio obtenido por el uso de los recursos en la producción
planteamos el siguiente modelo lineal, en el que ya se han sumado las variables
de holgura para obtener la forma estándar.
máx. z = 3x1 + 2x2 + x3 + 0x4 + 0x5
sujeto a
4x1 + 2x2 + 3x3 + x4 = 40
2x1 + 2x2 + x3 + +x5 = 30
x1, x2, x3, x4, x5 ≥ 0
Las variables del modelo xj, j = 1, 2, 3, indican la cantidad de unidades de
productos A, B y C que se deben producir. Las variables x4 y x5 son las variables
de holgura. Resolviendo el modelo, la tabla optima del problema es la siguiente:
x1 x2 x3 x4 x5
0 0 1 1/2 1/2 35
a1 1 0 1 1/2 -1/2 5
a2 0 1 -1/2 -1/2 1 10
La solución optima es x∗1 = 5, x∗2 = 10, x∗3 = 0 y el beneficio optimo z∗ = 35.
Este beneficio se consigue produciendo 5 unidades de producto A y 10 unidades
de B, es decir, la asignación optima es dedicar todos los recursos disponibles a la
producción de A y B.
