Investigacion Operativa PLEntera

PROGRAMACIÓN LINEAL ENTERA

Investigación Operativa
ISI – FRT.UTN

Programación Lineal Entera
Los problemas de programación con enteros se formulan de
la misma manera que los problemas de programación lineal,
pero agregando la condición de que
Todas las variables
de decisión deben
tomar valores
enteros
(Programación
entera pura)

Sólo algunas de las
Todas las variables
variables de
de decisióndeben
decisión deben
tomar los valores
tomar valores
enteros 0 ó 1
enteros
(Programación
(Programación
Entera Binaria)
Entera Mixta)

Definiciones
El PL obtenido cuando se omiten todos los enteros o las restricciones 0 –
1 en las variables se llama relajación del PL de la PE.
Cualquier PE se podría considerar como la relajación del PL +
restricciones adicionales (las restricciones que establecencuáles
variables tienen que ser enteros o ser 0 ó 1).
De aquí que la relajación del PL es una versión de la PE con menos
restricciones.
Esto significa que la región factible para cualquier PE debe estar
contenida en la región factible para la relajación del PL
correspondiente.

Definiciones
Por la afirmación anterior “región factible para cualquier PE debe estar
contenida en la región factiblepara la relajación del PL correspondiente” se
infiere que

Para cualquier PE que es un problema de maximización
Valor óptimo de Z para la relajación del PL  valor óptimo de Z para PE

Para cualquier PE que es un problema de minimización
Valor óptimo de Z para la relajación del PL  valor óptimo de Z para PE

Problema de Programación Lineal
Modelo matemático
Maximizar

Z = 6 x 1 + 7 x2

Sujeto a lasrestricciones:
x1 + 2 x2 ≤ 8
x1 - x2 ≤ 4
x1 ≥ 0 y x 2 ≥ 0

Resolver el Problema anterior con la condición (x1 y x2
enteras)
Modelo matemático
Maximizar

Z = 6 x 1 + 7 x2

Sujeto a las restricciones:
x1 + 2 x2 ≤ 8
x1 - x2 ≤ 4
x1 ≥ 0 y x 2 ≥ 0

y

x1 , x2 enteros

Uso del GLP para la representación
gráfica

PROCEDIMIENTOS para solucionar problemas de
programación entera

MÉTODO DEL PLANO DECORTE

MÉTODO DE RAMIFICACI
RAMIFICACIÓ
ÓN Y ACOTE

MÉTODO DEL PLANO DE CORTE

1.- Es una variante
del método
simplex.
• Resolver el
problema como si
fuera un problema
ordinario de PL,
ignorando las
restricciones
enteras.

2.- Agregar las
nuevas restricciones
al problema, las
cuales:
• Hacen no factible
la solución óptima
no entera previa;
y
• No excluyen
cualesquiera de
las soluciones
enterasfactibles
• Las nuevas
restricciones
agregadas son
llamadas planos
de corte.

3.- Obtener una
nueva solución por
el método simplex

4.- Repetir el
proceso (desde el
punto 2) hasta
obtener una
solución entera

MÉTODO DEL PLANO DE CORTE

Maximizar

Resolver el
siguiente
problema
entero puro:

•Z = 5x1 + 3x2 + x3

Sujeto a
•x1 + x2 + x3 ≤ 6
•3 x1 + x2 + 4 x3 ≤ 9
•x1 ≤1
•x2 ≤ 1
•x3 ≤ 4

Por ser un
problemaentero
puro
•x1 y x2 pueden
tomar valor 0 ó 1; y
•x3 puede valer 0,
1, 2, 3 ó 4

Diagrama de árbol, enumeración de las 20 soluciones posibles, del
problema anterior
X1=0

X2=0

X3= 0

1

2

X1=1

X2=0

X2=1

3

4

0

1

2

3

4

0

1

2

3

X2=1

4

0

1

2

3

4

Resolución de problemas enteros por
el método de Ramificación y Acotamiento

En un problema con
enteros existe un número
finito desoluciones
posibles (no todas son
factibles) que pueden
representarse mediante un
diagrama de árbol.

No hace falta enumerar
todas las soluciones
posibles si se pueden
eliminar “ramas
dominadas”.

Una rama puede
eliminarse si puede
demostrarse que no
contiene una solución
factible que sea mejor que
una ya obtenida.

Pasos en el método de Ramificación y
Acotamiento
: Resolver el problema como sifuera un problema ordinario de PL
(relajación de enteros). La solución obtenida se toma como cota máxima y base para el
procedimiento de búsqueda de una solución factible.

: A partir de la solución de PL designar una variable como entera y
seleccionar, a partir de los posibles valores enteros que pueda tomar, una rama para
investigarla.

: Encontrar un límite para el problema definido por la rama...