investigacion operacional

Programación Lineal Entera y Binaria

Capítulo 12
Programación Lineal Entera y Binaria
X2

Max Z = 5X1+2X2
C.S.R. 2X1 + 2X2 < 9
3X1 + X2 < 11
X2 < 1

Max Z = 5X1+2X2
C.S.R. 2X1 + 2X2 < 9
3X1 + X2 < 11
X2 > 2
XJ > 0 ; J = 1,2
X2 > 2
X2 < 1
X1

Z = 5X1 + 2X2 = 10

2X1 + 2X2 < 9
3X1 + X2 < 11

Introducción
Muchos de los problemas de la vida real exigen soluciones connúmeros entero, por lo tanto
las variables de dicho problema deben ser definidas como variables enteras. Los métodos
de solución que contemplaremos en éste capitulo son: Método gráfico, Método de los planos
cortantes de Gomory, Método de Bifurcación y Acotación (Branch And Bound), el Método
de Egon Balas en donde las variables son de carácter binario (0,1). Por último se ilustra el
uso del softwareWinQsb para atender éste tipo de problema.

Método Gráfico
Es idéntico al método gráfico de programación lineal continua, solo que aquí, se seleccionan
solo las soluciones enteras dentro del área de soluciones factibles.

205

Programación Lineal Entera y Binaria
Ejemplo
Max

Z = 5X1 + 3X2

C.S.R. 3X1 + 5X2 < 15
5X1 + 2X2 < 10
Xj > 0 y Enteras ∀j

3X1 + 5X2 < 15
3X1 + 5X2 = 15X1 = 0 X2 = 0
X2 = 3 X1 = 5
P(0,0) ⇒ 0 < 15
Verdad

5X1 + 2X2 < 10
5X1 + 2X2 = 10
X1 = 0 X2 = 0
X2 = 5 X1 = 2
P(0,0) ⇒ 0 < 10
Verdad

Z = 5X1 + 3X2 = 15
X1 = 0
X2 = 5

X2 = 0
X1 = 3

Aquí, las intersecciones de la cuadrícula, contenida en el
área sombreada, conforma las soluciones factibles.
Entonces, el punto más a la derecha del área, que se
intercepte con el barrido de lafunción objetivo, es la
solución óptima.
Éste método es eficaz sólo para problemas de dos (2)
variables ó menos. para problemas de más de 2
variables, estudiaremos el Método de los planos
cortantes de Gomory y el Método de Bifurcación ý
acotación, denominado también Branch And Bound.

Método de los planos cortantes de Gomory
Éste método sirve para solucionar problemas de más de dos (2)variables.
Algoritmo
1. Encontrar la solución, empleando el método simplex.
2. Si la solución es entera, entonces estamos en el óptimo.
3. Si no es entera, introducir una restricción nueva para la variable no entera, que tenga la
mayor parte fraccional (Quebrar empates arbitrariamente) y resolver el nuevo problema
mediante el método dual simplex.

206

Programación Lineal Entera yBinaria
Nueva restricción a partir de la restricción actual que tenga la variable cuyo valor en su
parte fraccional sea mayor.
a) Escriba cada constante como la suma de: Un número entero de cualquier signo y una
fracción no negativa, menor que uno (1).
b) Cambiar la ecuación trasladando los coeficientes enteros al lado derecho.
Ejemplo
Max: Z = X1 + 5X2
C.S.R. X1 + 10X2 < 20
X1
< 2
Xj > 0 yenteros para toda j

Max:
C.S.R.
Xj > 0

Z = X1 + 5X2
X1 + 10X2 + X3
= 20
X1
+ X4 = 2
y enteros para toda j

A continuación solucionamos el problema por el método simplex, tal como se haría si el
problema fuese de programación lineal continua.

Cj
VB
0 X3
0 X4
Zj - Cj

Cj
VB
5 X2
0 X4
Zj - Cj

1
b X1
20 1
2 1
0 -1

5
X2
10
0
-5
↑

1
X1
b
2 1/10
2
1
10-5/10
↑

0
X3
1
0
0

0 b
X4 a
0 2 (1/10)
1 NO
0

5
0
0
X2 X3 X4
1 1/10 0
0
0
1
0 5/10 0

b
a

Variable que entra X2
Variable que sale X3

Variable que entra X1
Variable que sale X4

20
2 →

207

Programación Lineal Entera y Binaria
Cj

1
VB b X1
5 X2 9/5 0
1 X1
2
1
Zj - Cj 11 0

5
0
0
X2 X3
X4
1 1/10 -1/10 →
0
0
1
-1/10
0 1/2 1/2Solución óptima pero no entera: X1 = 2 ; X2 = 9/5 ;
X3 = 0 ; X4 = 0 ; Z* = 11
Ecuación 1 (Fila 1) para construir la nueva
restricción; ya que tiene la variable (X2), cuyo valor
en su parte fraccional es mayor.

Cálculo de la nueva restricción, a partir de la ecuación 2.
X2 + 1/10X3 – 1/10X4 = 9/5
Remplazamos cada constante por la suma de un número entero de cualquier signo y una
fracción...