Movl

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 > 2 XJ > 0 ; J = 1,2 X2 > 2 X2 < 1 X1 Z = 5X1 + 2X2 = 10 2X1 + 2X2 < 9 3X1 + X2 < 11

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

Introducción Muchos de los problemas de la vida real exigen soluciones con números entero, por lo tantolas 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 software WinQsb para atender éstetipo 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 3X1 + 5X2 < 15 3X1 + 5X2 = 15 X1 = 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

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

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 la función objetivo, es la solución óptima. Éste método es eficazsó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étodosimplex. 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 y Binaria Nueva restricción a partir de la restricción actual que tenga la variablecuyo 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 y enteros para toda j Max: C.S.R. Xj > 0 Z = X1 + 5X2 X1 + 10X2 + X3 = 20 X1 + X4 = 2 yenteros 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

1 b X1 20 1 2 1 0 -1

5 X2 10 0 -5 ↑

0 X3 1 0 0

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

Variable que entra X2 Variable que sale X3

Cj VB 5 X2 0 X4 Zj - Cj

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

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

b a
20 2 →

Variable que entra X1 Variable que sale X4

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/2 Solució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 valoren 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 no negativa menor que uno (1). (1+0)X2 + (0+1/10)X3 + (-1+9/10)X4 = (1+4/5) Simplificando

X2 + 1/10X3 – X4 + 9/10X4 = 4/5 + 1 ;Trasladamos los términos con coeficiente entero, al...