programación entera

PROGRAMACIÓN LINEAL
ENTERA

08/10/2013

PROGRAMACIÓN LINEAL ENTERA
 En este capitulo veremos problemas que se podrían formular y resolver como problemas de
programación lineal, excepto por la desagradable circunstancia de que se requiere que algunas
o todas las variables tomen valores enteros.
 Dichos problemas se llaman PE (Programación Entera).
 La programación entera ha llegadoa ser un área muy especializada de la ciencia de la
administración.
 En este curso sólo la tocaremos en forma superficial, veremos la importancia del tema y algunos
métodos de resolución más útiles.
 Vimos en los capítulos anteriores que las variables podían tomar valores fraccionados, tales
como 6.34. Pero hay casos en el mundo real que no es posible esto y deben ser enteros.
 En elfondo es que existen muchos problemas administrativos importantes que serian de
programación lineal si no fuera por el requerimiento de que sean enteros los valores de algunas
variables de decisión, en los que no se pueden encontrar una buena solución mediante el uso del
método simplex seguido del redondeo de los valores óptimos resultantes para las variables de
decisión. Estos problemas debenser resueltos mediante algoritmos especialmente diseñados
para resolver problemas de programación entera.
1

TIPOS DE MODELOS PARA PROGRAMACION LINEAL ENTERA
Programación entera es un término general para los modelos de programación matemática
que presentan condiciones de ser enteros (condiciones que estipulan que algunas o todas las
variables de decisión deben tener valores enteros).Existen diversas clasificaciones de esta
categoría de modelos.
 Un modelo entero puro (PEP) es, como su nombre lo indica, un problema en el que se exige que
todas las variables de decisión tengan valores enteros. Por ejemplo
Minimizar

Sujeto a

6X1 + 5X2 + 4X3

108X1 + 92X2 + 58X3  576
7X1 + 18X2 + 22X3  83
X1, X2, X3  0 enteros

es un modelo entero puro.

2

Un problema enel que sólo se requiere que algunas variables tengan valores enteros mientras
que otras pueden asumir cualquier número no negativos (es decir, cualquier valor continuo)
se llama programación lineal entera-mixta (PLEM)
Por ejemplo, supóngase que en el problema anterior solo X1 y X2 deben ser enteros y X3 no.
El problema resultante es
Minimizar

Sujeto a

6X1 + 5X2 + 4X3

108X1 + 92X2 +58X3  576
7X1 + 18X2 + 22X3  83
X1, X2, X3  0

; X1 y X2 enteros.


3

En algunos casos se restringe el valor de las variables a 0 o 1. Dichos problemas se llaman
binarios o programación lineal entera 0-1. Son de interés debido a que se pueden usar las
variables 0-1 para representar decisiones dicotómicas (sí o no).
Diversos problemas de asignación, ubicación de planta, planes deproducción y de construcción,
son de programación lineal entera 0-1. Las variables 0-1 se pueden encontrar tanto en
problemas de PEP como PLEM.
A menudo se consideran problemas de programación lineal (PL) que se comienzan como PEP o
PLEM, ignorando las restricciones enteras. A estos problemas de PL se les llama
aproximaciones en las PEP o PLEM correspondientes.

4

INTERPRETACIONGRAFICA

Considérese el siguiente problema

Maximizar
Sujeto a

18E +
E+

6F
F5

(1)

42.8E + 100F  800 (2)
20E +

6F  142 (3)

30E + 10F  132 (4)
E–

3F  0

(5)

E y F  0 enteros

5

En el análisis, E es el numero de los E-9 y F el de los F-9 que la empresa Protrac produce, la
Protrac produce equipo pesado para la construcción.
Para resolver este problema con eltratamiento gráfico, prescribimos tres pasos:
1.-

Encuéntrese el conjunto factible para la aproximación de la PL del problema de PLE.

2.-

Identifique los puntos enteros del inferior del conjunto determinado en el paso 1.

3.-

Encuéntrese, entre los puntos determinados en el paso 2, el que optimiza la función objetivo.

6

7

La región demarcada es el conjunto factible de...