PROGRAMACIÓN ENTERA ITESRC
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.
En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren
a los utilizados en los modelos de Programación Lineal, destacándose entre ellos
el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos
Cortantes, Relajación Lagrangeana, entre otros.
Los modelos de Programación Entera se pueden clasificar en 2 grandes
áreas: Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).
Programación Entera Mixta (PEM)
A esta categoría pertenecen aquellos problemas de optimización que consideran variables de
decisión enteras o binarias pero no de forma exclusiva. De esta forma un problema de PEM
puede considerarse como un híbrido entre distintas categorías de modelamiento, siendo un
caso típico aquel que considera la mezcla de variables enteras y variables continuas (estas
últimas características de los modelos de Programación Lineal). A modo de ejemplo los
siguientes artículos que hemos abordado en el Blog dan cuenta de modelos de
Programación Entera Mixta:
1. Incorporación de Costos Fijos
2. Problemas de Localización y Transporte
3. Problema de Generación Eléctrica
INVESTIGACIÓN DE OPERACIONES I M.C. CLAUDIA SÁNCHEZ IBARRA
PROGRAMACIÓN ENTERA ITESRC
Programación Entera Pura (PEP)
En esta categoría encontramos aquellos modelos de Programación Entera que consideran
exclusivamente variables de decisión que adoptan valores enteros o binarios. Un ejemplo de
ello son las siguientes aplicaciones:
1. Problema de Asignación
2. Problema de Corte de Rollos
3. Selección de Invitados a una Boda
4. Programación de la Explotación Forestal
5. Problema de la Mochila
Notar que en los problemas anteriores (PEP) el conjunto de las soluciones factibles (o
dominio de soluciones factibles) es finito. Esto ocurrirá generalmente con los problemas de
Programación Entera (puros).
Adicionalmente resulta interesante hacer un contraste entre las propiedades de un modelo de
Programación Lineal (PL) y uno de Programación Entera (PE). A continuación se presentan 2
modelos de optimización que se diferencian únicamente en que al segundo de ellos (PE) se
le exige que las variables de decisión adopten valores enteros.
PL: MAX Z = 10X1 + 16X2 PE: MAX Z = 10X1 + 16X2
SUJETO A SUJETO A
2X1 + 2X2 ≤ 8 2X1 + 2X2 ≤ 8
X1 + 2X2 ≤ 6 X1 + 2X2 ≤ 6
X1, X2 ≥ 0 X1, X2 ≥ 0, ENTEROS
EJEMPLO:
Un joyero puede disponer semanalmente de 800 gramos de oro, 2.4 kilogramos de plata y 14
kilogramos de cobre. Actualmente fabrica dos dijes que tienen gran demanda. Se llevan 10
gramos de oro en cualquier dije que fabrique, pero el dije 1 lleva también 40 gramos de plata
y 150 de cobre mientras que el dije 2 requiere de 250 gramos de cobre y 20 de plata. Se
tiene una utilidad total de $90 y $70 para el dije 1 y 2 respectivamente.
SOLUCIÓN:
X1: Dijes tipo 1
X2: Dijes tipo 2
MAX Z = 90 X1 + 70 X2
SUJETO A
10X1 + 10X2 ≤ 800
40X1 + 20X2 ≤ 2400
150X1 + 250 X2 ≤ 14000
X1, X2 ≥ 0
INVESTIGACIÓN DE OPERACIONES I M.C. CLAUDIA SÁNCHEZ IBARRA
PROGRAMACIÓN ENTERA ITESRC
1. 10X1 + 10X2 = 800 2. 40X1 + 20X2 = 2400 3. 150X1 + 250 X2 = 14000
X1 = 0 X2 = 80 X1 = 0 X2 = 120 X1 = 0 X2 = 56
X1 = 80 X2 = 0 X1 = 60 X2 = 0 X1 = 93.33 X2 = 0
120
110
100
90
80
70
60
50
40
30
20
10
0 10 20 30 40 50 60 70 80 90 100
VÉRTICE X1 X2 Z
A 0 0 0
B 0 56 3,920
C 45.71 28.57 6,113.80***
D 60 0 5,400
VÉRTICE “C”:
40X1 + 20X2 = 2,400 (150)
150X1 + 250 X2 = 14,000 (– 40)
6000X1 + 3000X2 = 360,000
– 6000X1 – 10,000X2 = – 560,000
– 7,000X2 = – 200,000
X2 = – 200,000/ – 7,000
X2 = 28.57
INVESTIGACIÓN DE OPERACIONES I M.C. CLAUDIA SÁNCHEZ IBARRA
PROGRAMACIÓN ENTERA ITESRC
40X1 + 20X2 = 2400
40X1 + 20(28.57) = 2400
40X1 = 2400 – 571.4
X1 = 1828.6 / 40
X1 = 45.71
SOLUCIÓN ÓPTIMA:
X1 = 45.71 Dijes tipo 1
X2 = 28.57 Dijes tipo 2
Z = 6,113.80 u.m.
SOLUCIÓN ENTERA (Suponiendo que se fabrican lotes de 10 unidades)
120
110
100
90
80
70
60
50
40
30
20
10
0 10 20 30 40 50 60 70 80 90 100
INVESTIGACIÓN DE OPERACIONES I M.C. CLAUDIA SÁNCHEZ IBARRA
PROGRAMACIÓN ENTERA ITESRC
VÉRTICE VÉRTICE
Z Z
(X1, X2) (X1, X2)
(0, 0) 0 (20, 30) 3900
(0, 10) 700 (20, 40) 4600
(0, 20) 1400 (30, 0) 2700
(0, 30) 2100 (30, 10) 3400
(0, 40) 2800 (30, 20) 4100
(0, 50) 3500 (30, 30) 4800
(10, 0) 900 (40, 0) 3600
(10, 10) 1600 (40, 10) 4300
(10, 20) 2300 (40, 20) 5000
(10, 30) 3000 (40, 30) 5700
(10, 40) 3700 (50, 0) 4500
(10, 50) 4400 (50, 10) 5200
(20, 0) 1800 (50, 20) 5900*
(20, 10) 2500 (60, 0) 5400
(20, 20) 3200
SOLUCIÓN ÓPTIMA ENTERA (En lotes de 10 unidades)
X1 = 50 Dijes tipo 1
X2 = 20 Dijes tipo 2
Z = 5,900 u.m.
INVESTIGACIÓN DE OPERACIONES I M.C. CLAUDIA SÁNCHEZ IBARRA
