Investigación de Operaciones I

INGENIERÍA INDUSTRIAL Y DE SISTEMAS 2021-I

Tema 5
Programación Entera

1. Introducción
Un problema de Programación Entera (P.E.) es un P.L. con la característica adicional de que
algunas o todas las variables deben ser números enteros. A estas variables se les denomina
variables enteras.
Existe un tipo de variable entera que sólo puede tomar los valores 0 ó 1, llamada variable binaria.
Este tipo de variable es muy útil para el planteamiento de problemas complejos.
Un problema de P.E. puede contener sólo variables enteras, o sólo variables binarias, o puede
contener algunas variables enteras y/o algunas variables binarias, además de las variables que sí
pueden tomar valores no enteros.
Para resolver estos problemas no basta redondear la solución obtenida mediante el método
Simplex, pues esto puede conducir a soluciones no factibles, y puede resultar muy complejo tratar
de evitar caer en este error. Existen muchos algoritmos para resolver problemas de P.E.; pero
cuando se trata de resolver problemas con muchas variables y restricciones, muchos requieren de
demasiado tiempo de computadora para llegar a la solución óptima. La mayoría de estos
algoritmos son variantes de los siguientes métodos: el método de ramificación y acotamiento
(Branch and Bound) y el método de los planos de corte (Cutting plane). En este texto sólo nos
limitaremos a estudiar algunos algoritmos de ramificación y acotamiento.

2. Resolución de problemas de Programación Entera por el método

de Ramificación y Acotamiento.
El método de ramificación y acotamiento va redondeando poco a poco las soluciones no enteras
obtenidas para las variables enteras, acotando de manera sistemática las posibilidades que se van
presentando. Este procedimiento se puede aplicar a problemas donde algunas o todas las variables
son enteras; e incluso a problemas que incluyen variables binarias.
Existen varios algoritmos que se basan en este método, que difieren únicamente en el
procedimiento de ramificación.

Página 1 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

Algoritmo de Land-Doig

Paso 1. Resuelva el problema entero aplicando el método Simplex, sin tener en cuenta que las
variables deben ser enteras (P.L. relajado). Si la solución óptima es entera, se ha
encontrado la solución óptima; en caso contrario continúe con el paso 2.
Paso 2. Escoja arbitrariamente una variable entera xj cuyo resultado en el paso 1 no sea entero e
igual a xBj.
Paso 3. Resuelva dos nuevos problemas similares al P.L. relajado: el primero con una restricción
adicional al P.L. relajado xj  [xBj]; y el segundo con una restricción adicional xj  [xBj] +
1.
Paso 4. De los P.L. resueltos en el paso anterior, sólo incluya en el análisis posterior aquellos
cuya solución (entera o no) sea mejor que cualquiera de las soluciones enteras ya
obtenidas.
Paso 5. Seleccione aquel P.L. que tenga el mejor valor de la F.O. Si las variables enteras tienen
valores enteros, se ha encontrado la solución óptima; en caso contrario regrese al paso 2
considerando la estructura del P.L. resuelto en este paso.
Ejemplo de aplicación: resolver el siguiente P.L. entero:
Max 8x1 + 5x2
s.t. x1 + x2  6
9x1 + 5x2  45
x1, x2  0 ; x1, x2 enteros

Subproblema 1
Z = 41.25
X1 = 3.75
X2 = 2.25

x1>=4 x1<=3

Subproblema 3
Subproblema 2
Z = 39 < L.I.
Z = 41
X1 = 3
X1 = 4.0
X2 = 3
X2 = 1.8
X

x2>=2 x2<=1

Subproblema 4 Subproblema 5
Z = 40.555
No factible X1 = 4.444
X X2 = 1.000

x1>=5 x1<=4

Subproblema 7
Subproblema 6
Z = 37 < L.I.
Z = 40 = L.I.
X1 = 4
X1 = 5
X2 = 1
X2 = 0
X

Si en un problema hay variables binarias, en el paso 3 se añaden xj = 1 y xj = 0.

Página 2 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

3. Planteamiento de problemas de P.E. con variables binarias

En esta sección se presentan distintos tipos de problemas que necesitan de las variables binarias
para poder formular un modelo matemático.

Problema de presupuesto de capital

Se trata de un problema en donde un inversionista debe decidir dónde colocar su dinero, entre
varias posibilidades que se presentan, cada una de las cuales viene definida por un monto fijo y
una utilidad.

Ejemplo:

Inversores Piuranos es una empresa que está considerando la posibilidad de invertir en cuatro
proyectos. En la siguiente tabla se muestran los posibles montos de inversión y sus
correspondientes beneficios (ambos en miles de dólares):

Proyecto 1 Proyecto 2 Proyecto 3 Proyecto 4

Inversión 9 6 7 5
Utilidad 20 13 14 9

Si Inversores Piuranos dispone de 21 000 dólares, ¿en qué proyectos le conviene invertir?
Se debe decidir si conviene o no invertir en el proyecto j (j = 1, 2, 3, 4), para lo cual se definen las
variables de decisión xj de la siguiente manera:
1, si se realizala inversión j
xj =
0, en caso contrario
Para esto se definen xj como variables binarias, donde el valor 1 indica que sí se realiza la inversión
y el valor 0 que no se realiza la inversión. El modelo de P.E. resulta:
max Z = 20x1 + 13x2 + 14x3 + 9x4
s.a: 9x1 + 6x2 + 7x3 + 5x4  21
x1; x2; x3; x4; x5; x6 = 0 ó 1

Página 3 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

Problema de costo fijo

En problemas de planeación de la producción de N productos, el costo de la producción de un

producto j está formado por dos costos: un costo cj por cada unidad producida (costo variable), y
un costo Fj independiente de la cantidad producida (costo fijo) (j = 1, 2, ..., N). Este costo fijo Fj
es nulo si no se produce ninguna unidad del producto j.
Para plantear este tipo de problema se tiene el inconveniente de que en la función objetivo sólo
deben incluirse los costos fijos de aquellos productos que sí se producen (xj > 0). ¿Cómo le
indicaremos al programa matemático esta condición?

Ejemplo:

Gandhi es una fábrica que puede confeccionar tres tipos de ropa: camisas, shorts y pantalones. La
confección de cada tipo de ropa requiere que Gandhi tenga disponibles distintos tipos de
maquinaria. La maquinaria necesaria para confeccionar cada tipo de ropa puede ser alquilada a los
siguientes precios:
Maquinaria para camisas: $ 200 por semana
Maquinaria para shorts: $ 150 por semana
Maquinaria para pantalones: $ 100 por semana
La confección de cada tipo de ropa requiere además de las cantidades de tela y de horas de trabajo
que se especifican en la siguiente tabla:
Horas de trabajo Tela necesaria (m2)
Camisa 3 4
Shorts 2 3
Pantalones 6 4

Cada semana se dispone de 150 horas de trabajo y de 160 m 2 de tela. Los costos y precios de venta
para cada tipo de ropa se muestran en la siguiente tabla:
Precio de venta Costo
Camisa $12 $6
Shorts $8 $4
Pantalones $15 $8

¿Cuál es el plan de producción que maximiza los beneficios de Ghandi?

Se definen en primer lugar las siguientes variables de decisión:
x1 = cantidad de camisas que conviene producir
x2 = cantidad de shorts que conviene producir
x3 = cantidad de pantalones que conviene producir

Si no se tuviera en cuenta el alquiler de la maquinaria, se plantearía el siguiente P.L.:

Max Z = 6x1 + 4x2 + 7x3
s.a: 3x1 + 2x2 + 6x3  150
4x1 + 3x2 + 4x3  160
x1, x2, x3  0, entero.

Página 4 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

Considerando los costos fijos de alquiler (Fj), éstos sólo deben tenerse en cuenta en la F.O. cuando
convenga se produzca al menos una unidad del producto j. Para esto conviene definir las variables
binarias yj, de tal manera que se cumpla:
1, si x j  0
yj =
0, si x j = 0
La F.O. sería:
Max Z = 6x1 + 4x2 + 7x3 – 200y1 – 150y2 – 100y3
Las condiciones de yj pueden expresarse en forma lineal mediante la siguiente inecuación:
xj  Myj

donde M es un valor muy grande, mayor que cualquier valor que pudiera tomar xj. Podría
determinarse el máximo valor que puede tomar cada xj; pero más cómodo sería determinar,
observando las restricciones de los recursos (horas de trabajo y cantidad de tela disponible), un
valor que con seguridad nunca alcanzará ningún xj, por ejemplo M = 150.
Se puede verificar fácilmente que yj toma los valores adecuados, de acuerdo al valor que convenga
para xj. Por ejemplo, si xj > 1, necesariamente yj = 1. Si xj = 0, yj = 0 ó 1, pero como yj = aparece
en la F.O con signo negativo, y se trata de maximizar dicha F.O., yj tomará el valor 0.
Resumiendo, el modelo de P.E. para este problema es el siguiente:
Max Z = 6x1 + 4x2 + 7x3 – 200y1 – 150y2 – 100y3
s.a: 3x1 + 2x2 + 6x3  150
4x1 + 3x2 + 4x3  160
x1  150y1
x2  150y2
x3  150y3
x1, x2, x3  0, entero.
y1, y2, y3 = 0 ó 1.

Página 5 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

Problemas de cobertura de conjuntos

Se trata de problemas en donde se definen dos conjuntos: el primero, conformado por elementos
que deben ser cubiertos por los elementos que podrían conformar el segundo. Como ejemplos de
problemas de cobertura de conjuntos se puede mencionar: localización de estaciones de bomberos,
programación de las tripulaciones de aerolíneas, programación de rutas de camiones, etc.

Ejemplo 1:

Hay seis distritos en una provincia. Se debe determinar en qué distritos construir estaciones de
bomberos, de tal manera que, con el mínimo de estaciones necesario, se asegure que cada distrito
tendrá al menos una estación de bomberos a 15 minutos, como máximo. En la siguiente tabla se
muestran los tiempos de viaje entre los distintos distritos de la provincia:

Distrito 1 Distrito 2 Distrito 3 Distrito 4 Distrito 5 Distrito 6

Distrito 1 0 10 20 30 40 20
Distrito 2 10 0 25 35 20 10
Distrito 3 20 25 0 15 30 20
Distrito 4 30 35 15 0 15 25
Distrito 5 30 20 30 15 0 14
Distrito 6 20 10 20 25 14 0

¿Cuántas estaciones de bomberos deben construirse? ¿En qué distritos?

Para cada distrito j, se debe determinar si se construye una estación de bomberos, para lo cual se
definen las siguientes variables binarias:
1, si se construyeen la ciudad j
xj =
 0, en caso contrario
Entonces el objetivo (F.O.) será minimizar xj.
Para determinar las restricciones de este problema, se debe tener en cuenta, para cada distrito, qué
distritos están a un máximo de 15 minutos, lo cual se muestra en la segunda columna de la siguiente
tabla. En la tercera columna se expresan las restricciones correspondientes a cada distrito. Por
ejemplo, por lo menos debe haber una estación de bomberos en los distritos 1 y 2.

Distritos a un máximo de 15 minutos Restricción

Distrito 1 Distrito 2 x1 + x2  1
Distrito 2 Distrito 1, distrito 6 x1 + x2 + x6  1
Distrito 3 Distrito 4 x3 + x4  1
Distrito 4 Distrito 3, distrito 5 x3 + x4 + x5  1
Distrito 5 Distrito 4, distrito 6 x4 + x5 + x6  1
Distrito 6 Distrito 2, distrito 5 x2 + x5 + x6  1

Página 6 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

Resumiendo, el modelo de P.E. para este problema es el siguiente:

Min Z = x1 + x2 + x3 + x4 + x5 + x6
s.a: x1 + x2  1
x1 + x2 + x6  1
x3 + x4  1
x3 + x4 + x5  1
x4 + x5 + x6  1
x2 + x5 + x6  1
x1; x2; x3; x4; x5; x6 = 0 ó 1.

Ejemplo 2:

La Sayre-Priors Airline and Stormdoor Company es una compañía de aviación que opera con los
siguientes vuelos:

Número de vuelo Origen Destino Horario

101 Chicago Los Angeles Tarde
410 New York Chicago Tarde
220 New York Miami Noche
17 Miami Chicago Mañana
7 Los Angeles Chicago Tarde
13 Chicago New York Noche
11 Miami New York Mañana
19 Chicago Miami Noche
23 Los Angeles Miami Noche
3 Miami Los Angeles Tarde

A la dirección de operaciones de vuelo le gustaría establecer un programa de asignación de la flota

a mínimo coste. El problema básico consiste en determinar el siguiente vuelo que le corresponde
a una flota después de finalizado un vuelo. Un concepto básico para entender este problema es el
de recorrido. Un recorrido tiene las siguientes características:
• Consta de 1, 2 ó 3 vuelos conectados.
• Tiene un costo de $2000 si termina en la ciudad origen.
• Tiene un costo de $3000 si no termina en la ciudad de origen.
Los siguientes son ejemplos aceptables de recorridos:
Recorrido Costo
17, 101, 23 $2000
220, 17, 101 $3000
410, 13 $2000

Nótese que dos o más vuelos consecutivos son factibles si corresponden al orden natural: mañana
– tarde – noche.

Página 7 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

En primer lugar, para resolver este problema, conviene enumerar todos los recorridos factibles,
como se indica en la siguiente tabla:

De un vuelo Costo De dos vuelos Costo De tres vuelos Costo

1. 101 3000 11. 101,23 3000 25. 101,23,17 2000
2. 410 3000 12. 410,13 2000 26. 101,23,11 3000
3. 220 3000 13. 410,19 3000 27. 410,19,17 3000
4. 17 3000 14. 220,17 3000 28. 410,19,11 2000
5. 7 3000 15. 220,11 2000 29. 220,17,101 3000
6. 13 3000 16. 17,101 3000 30. 220,11,410 3000
7. 11 3000 17. 7,13 3000 31. 7,19,17 3000
8. 19 3000 18. 7,19 3000 32. 7,19,11 3000
9. 23 3000 19. 11,410 3000 33. 11,417,13 3000
10. 3 3000 20. 19,17 2000 34. 19,17,101 3000
21. 19,11 3000 35. 23,11,410 3000
22. 23,17 3000 36. 3,23,17 3000
23. 23,11 3000 37. 3,23,11 3000
24. 3,23 2000

Luego, se definen las variables de decisión xj:

1, si se usa el recorrido j
xj = ... (j = 1,..., 37)
 0, en caso contrario
Entonces la F.O. será (en unidades de $1000):
Min Z = 3x1 + 3x2 + 3x3 + 3x4 + 3x5 + 3x6 + 3x7 + 3x8 + 3x9 + 3x10 + 3x11 + 2x12 + 3x13 + 3x14 +
2x15 + 3x16 + 3x17 + 3x18 + 3x19 + 2x20 + 3x21 + 3x22 + 3x23 + 2x24 + 2x25 + 3x26 + 3x27 +
2x28 + 3x29 + 3x30 + 3x31 + 3x32 + 3x33 + 3x34 + 3x35 + 3x36 + 3x37

Las restricciones siguientes indican que debe existir cada uno de los 10 vuelos. Por ejemplo, de
todos los recorridos en los que está el vuelo 101, debe escogerse uno.
s.a: x1 + x11 + x16 + x25 + x26 + x29 + x34 = 1
x2 + x12 + x13 + x19 + x27 + x28 + x30 + x33 + x35 = 1
x3 + x14 + x15 + x29 + x30 = 1
x4 +x14+ x16 + x20 + x22 + x25 + x27 + x29 + x31 + x34 + x36 = 1
x5 + x17 + x18 + x31 + x32 = 1
x6 + x12 + x17 + x33 = 1
x7 + x15 + x19 + x21 + x23 + x26 + x28 + x30 + x32 + x33 + x35 + x37 = 1
x8 + x13 + x18 + x20 + x21 + x27 + x28 + x31 + x32 + x34 = 1
x9 + x11 + x22 + x23 + x24 + x25 + x26 + x35 + x36 + x37 = 1
x10 + x24 + x36 + x37 = 1

Página 8 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

Problemas con restricciones alternativas

En muchas ocasiones una situación puede ser representada mediante una u otra restricción, y se
quiere que por lo menos una de estas restricciones se cumpla, por ejemplo:
f1(x1, x2, x3, ..., xn)  0
f2(x1, x2, x3, ..., xn)  0

Para que se cumpla la primera o bien la segunda restricción se puede plantear las siguientes dos
restricciones:
f1(x1, x2, x3, ..., xn)  My
f2(x1, x2, x3, ..., xn)  M(1 – y)

donde y es una variable binaria, y M es un valor más grande que cualquiera de los valores que
pueden tomar x1, x2, x3, ..., xn. De esta manera, para cualquier valor que tome y, siempre se
impondrá una de las dos restricciones originales, la otra simplemente no restringirá.
Ejemplo 1
Un fabricante de autos puede producir tres modelos: compacto, mediano y grande. La fabricación
de estos modelos está limitada por los siguientes recursos: acero y mano de obra. En la siguiente
tabla se muestra los recursos que requiere cada modelo, y sus respectivas utilidades marginales:
Compacto Mediano Grande
Acero (TM) 1.5 3 5
Mano de obra (horas) 30 25 40
Utilidad ($) 2000 3000 4000

Se cuenta con 6 000 TM de acero y 60 000 horas de mano de obra. Para que la producción de un
modelo sea rentable, se deben fabricar por lo menos 1 000 unidades. ¿Cuántos autos de cada
modelo le conviene fabricar?
Se definen las siguientes variables de decisión:
x1 = n de autos compactos que conviene fabricar.
x2 = n de autos medianos que conviene fabricar
x3 = n de autos grandes que conviene fabricar

La F.O. será:
Max Z = 2000x1 + 3000x2 + 4000x3
Las restricciones de disponibilidad de acero y mano de obra serán:
1.5x1 + 3x2 + 5x3  6000
30x1 + 25x2 + 40x3  60000

Ahora se debe expresar que se cumpla una de las siguientes restricciones:

xj  0
xj  1000 que equivale a: 1000 – xj  0
Esto se plantea mediante las siguientes restricciones:
xj  Myj
1000 – xj  M(1 – yj)

Página 9 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

En conclusión, el modelo de P.E. será:

Max Z = 2000x1 + 3000x2 + 4000x3
s.a: 1.5x1 + 3x2 + 5x3  6000
30x1 + 25x2 + 40x3  60000
x1  6000y1
1000 – x1  6000(1 – y1)
x2  6000y2
1000 – x2  6000(1 – y2)
x3  6000y3
1000 – x3  6000(1 – y3)
x1; x2; x3  0, enteros
y1; y2; y3 = 0 ó 1.

En algunas ocasiones se debe elegir una entre más de dos restricciones, la que convenga según las
condiciones que se presenten.

Ejemplo 2:

Supóngase que se desea construir una planta cuya capacidad puede ser 1000, 2000 ó 3000
unidades. Sea x la variable que define el nivel de producción de dicha planta. La restricción de la
capacidad de la planta tendría que ser una de las siguientes:
x  1000
x  2000
x  3000
Para modelar esta situación, se definen las siguientes variables binarias:
1, si se escoge1000
y1 = 
 0, en caso contrario
1, si se escoge2000
y2 = 
 0, en caso contrario
1, si se escoge3000
y3 = 
 0, en caso contrario
Para asegurarse que sólo se escoja una de las tres restricciones se plantea la restricción:
y1 + y2 + y3 = 1
Para restringir la capacidad de la fábrica se podrían plantear las siguientes restricciones:
x  1000y1 + M(1 – y1)
x  2000y2 + M(1 – y2)
x  3000y3 + M(1 – y3)

Se puede probar fácilmente que si y1 = 1, entonces y2 = 0; y3 = 0, y, de las últimas tres restricciones,

sólo la primera restringe a x.

Página 10 de 11 Programación Entera

Universidad de Piura Investigación de Operaciones I

En lugar de las últimas tres restricciones, se podría plantear la siguiente restricción:

x  1000y1 + 2000y2 + 3000y3

Relaciones lógicas entre alternativas

▪ Si existen dos alternativas, j y k, y se puede elegir una u otra, o ninguna; pero no ambas, se
puede plantear la siguiente restricción, empleando las variables binarias xj y xk:
xj + xk  1
▪ Si existen dos alternativas, j y k, y se debe elegir una u otra; pero no ambas, se puede plantear
la siguiente restricción, empleando las variables binarias xj y xk:
xj + xk = 1
▪ Si la alternativa i se escogiese si y sólo si al menos una de ambas alternativas j o k es elegida,
se pueden plantear las siguientes restricciones, empleando las variables binarias xi, xj y xk:
xj + xk  2xi
2xi – xj – xk  1
▪ Si la alternativa i se escogiese si y sólo si las tres alternativas j, k y l son elegidas, se pueden
plantear las siguientes restricciones, empleando las variables binarias xj, xk y xl:
xj + xk + xl – 3xi  2
3xi – xj – xk – xl  0

Página 11 de 11 Programación Entera