UNIVERSIDAD NACIONAL DEL
ALTIPLANO PUNO.
CURSO:INVESTIGACION DE
OPERACIONES
DOCENTE: MARITZA MAGDALENA JALLO SANGA
TEMA: Programación
Lineal Entera (PLE)
Programación lineal entera (PLE)
• Por lo general, las aplicaciones de programación lineal entera (PLE) caen dentro
de dos categorías:
Directa y transformada.
• En la categoría directa, la naturaleza de la situación impide la asignación de
valores fraccionarios a las variables del modelo. Por ejemplo, el problema puede
implicar la determinación de si se emprende o no un proyecto (variable binaria), o
la determinación del número óptimo de máquinas necesarias para realizar una
tarea (variable general entera).
En la categoría transformada
• Se utilizan variables enteras auxiliares para convertir analíticamente situaciones
insolubles en modelos que pueden resolverse por medio de algoritmos de
optimización disponibles. Por ejemplo, en la secuencia de dos trabajos, A y B, en
una sola máquina, el trabajo A puede preceder al trabajo B o viceversa. La
naturaleza “o” de las restricciones es lo que hace al problema analíticamente
insoluble, porque todos los algoritmos de programación matemáticos tratan con
sólo restricciones “y”.
Programación Entera Pura
Programación entera mixta
Programación entera binaria
Modelos de programación entera
• Son aquellos donde la totalidad o un subconjunto de las
variables de decisión toman valores enteros.
• En este sentido la forma estandar de un modelo de
Programación Entera queda definido de la siguiente forma:
• Existen múltiples aplicaciones de modelos de Programación
Entera como apoyo a la toma de decisiones.
• Ejemplo: Los problemas de localización de instalaciones,
inclusión de costos fijos, problemas de asignación, problemas
de ruteo vehicular, etc.
Modelos de Programación Entera
Problema Asignación:
• Una universidad está programando las clases para el próximo semestre
académico y requiere buscar la mejor asignación posible de profesores a los
distintos cursos que se deben dictar. Considere que existen 5 profesores: A, B, C,
D, E y 5 cursos (asignaturas): C1, C2, C3, C4, C5. Adicionalmente, los profesores
han manifestado sus preferencias por dictar los distintos cursos en una escala de 1
a 10, donde 10 es la máxima puntuación y 1 la mínima puntuación o preferencia.
Se asume que cada profesor es apto para dictar cualquier curso, independiente
del puntaje de su preferencia. La siguiente tabla resume las puntuaciones que
asigna cada profesor a cada curso:
Solución de un modelo de maximización
• Se ha establecido como criterio que cada profesor debe dictar sólo un curso y a la vez que
cada curso obviamente debe tener un profesor. En base a lo anterior se desea encontrar la
asignación de profesores que maximize el total de las preferencias.
• Variables de Decisión:
• La solución óptima de este problema es asignar el profesor A a C3, B a C5, C a C4, D a C1 y E
a C2. Valor Óptimo = 44.(Solver)
Problema Inclusión Costos Fijos:
• Usted ha sido designado por el gerente de su empresa para decidir cómo
distribuirá su tráfico telefónico en el próximo mes, seleccionando entre 3
proveedores posibles y asignando la cantidad de tráfico (minutos) que desee en
cada caso, es decir, puede repartir el tráfico en 1, 2 o 3 proveedores a su antojo y
su decisión sólo dependerá de los costos de cada alternativa.
• El proveedor 1 cobra un cargo fijo mensual de US$50 y el costo por minuto a red
fija es de US$0,02 y a celular de US$0,12. El proveedor 2 tiene un cargo fijo
mensual de US$60, con un costo por minuto de US$0,015 y US$0,15 a red fija y
celular respectivamente. Finalmente el proveedor 3 tiene un cargo fijo mensual de
US$40 con un costo por minuto a red fija de US$0,03 y a celular de US$0,14. Si
usted llama por uno de estos proveedores (aunque hable sólo un minuto) deberá
pagar el cargo fijo. Asuma que la cantidad de minutos que la empresa consume
mensualmente es de 30.000 para red fija y 18.000 para celular.
MÉTODO DE REPRESENTACIÓN GRÁFICA
Formule y resuelva un modelo de Programación Entera que
permita decidir cómo distribuir el tráfico telefónico mensual
de la forma más económica para la empresa.
ALGORITMOS DE PROGRAMACIÓN ENTERA
Los algoritmos de PLE se basan en la explotación del tremendo éxito computacional de la PL. La
estrategia de estos algoritmos implica tres pasos:
• Paso 1. Desahogue el espacio de soluciones del PLE al eliminar la restricción entera en todas las
variables enteras y reemplazar cualquier variable binaria y con el intervalo continuo 0 # y # 1. El
resultado del desahogo es una programación lineal.
• Paso 2. Resuelva la PL, e identifique su óptimo continuo.
• Paso 3. Comenzando desde el punto óptimo continuo, agregue restricciones especiales que
modifiquen iterativamente el espacio de soluciones de PL de modo que finalmente dé un punto
extremo óptimo que satisfaga los requerimientos enteros.
• Se desarrollaron dos métodos generales para generar las restricciones especiales en el paso 3.
• 1. Método de ramificación y acotación (B&B)
• 2. Método de plano de corte
Ninguno de los dos métodos es computacionalmente efectivo de forma consistente. Sin embargo, la
experiencia muestra que el método B&B (de ramificación y acotamiento) es mucho más exitoso que el
método del plano de corte.