Administrador

MSc. Ruth Quispe Condori

ruthqc2@gmail.com

Los modelos de Programación Lineal Entera ( PLE ) son aquellos donde la totalidad o un subconjunto de las variables de decisión toman valoresenteros.

Por ejemplo:
Un modelo de PLE podría escribirse como:
Max. o Min.

Función Objetivo: Sujeta a:

z  3 x1 x2 2 x3

2 x 1 x 2  28 x2  x3  20 x1  x2  x3  15

x1  0, x2  0 y x2 Z, x3   0, 1 

❶

Caso de fabricación de automóviles en una determinada compañía Xi es cantidad de automóviles Caso de asistencia de una persona a una determinada reunión 1, si la persona iasiste a la
reunión j

❷

Xij=

0, en caso contrario

Consideraremos los siguientes
cuando

❶

Modelo de PLE Pura

Todas las variables de decisión son enteros

❷

Modelo de PLEMixta

cuando

Algunas de las variables de decisión son enteros

❸

Modelo de PLE Binaria

cuando

Las variables de decisión solo toman los valores binarios de 0 y 1

La PLE se presenta enmuchos problema típicos tales como:
❶ Problema de Transporte ❷ Problema de Flujo con Costo Mínimo ❸ Problema de Asignación ❹ Problema de la Mochila ❺ Problema del Emparejamiento ❻ Problema delRecubrimiento

❼ Problema del Empaquetado
❽ Problema de Partición ❾ Problema del Costo Fijo ❿ Problema del Viajante ⓫ Problema de Rutas Óptimas

EN UN MODELO DE

P L E

los métodos más empleadospara su solución son el

Método de la Ramificación y Acotamiento

Método de los Planos de Corte

Método Enumerativos para Problemas Binarios

Llamado también el método de Branch and Bound.El método consiste en “linealizar” el modelo de
programación entera, es decir, resolver éste como si fuese un modelo de programación lineal y luego generar cotas en caso que al menos una variable dedecisión adopte un valor fraccionario.

El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que
favorecen la obtención de valores enteros para las variables de decisión....