Casos sobre los Algoritmos de Planos

de Corte

Algoritmo Fraccional (Entero Puro)

CASO 1:

Tomamos el PL:

Ya que todos los coeficientes y las constantes del segundo miembro son enteros, desarrollamos el problema por el método simplex hasta obtener la tabla óptima.

0 1 7/22 1/22 7/21 0 -1/22 3/22 9/20 0 28/11 15/11 63

Ahora que tenemos la tabla, agregamos un corte fraccionario:

Ya que ambas ecuaciones tienen el mismo valor de , podemos utilizar cualquiera.

Tomando la ecuación :

Entonces el corte fraccional será:

Ahora lo agregamos a la última tabla:

0 1 7/22 1/22 0 7/21 0 -1/22 3/22 0 9/20 0 -7/22 -1/22 1 -1/20 0 28/11 15/11 0 63

Resolvemos por el método simplex:

0 1 0 0 1 31 0 0 1/7 -1/7 32/70 0 1 1/7 -22/7 11/70 0 0 1 8 59

Ya que la solución todavía no es entera, se elabora un nuevo corte. Tomamos la ecuación :

Entonces el corte fraccional será: 

Agregando esto a la última tabla:

Resolvemos por el método simplex:

Es así como obtenemos la solución óptima entera:

0 1 0 0 1 0 31 0 0 1/7 -1/7 0 32/7

0 0 1 1/7-

22/70 11/7

0 0 0 -1/7 -6/7 1 -4/70 0 0 1 8 0 59

0 1 0 0 1 0 31 0 0 0 -1 1 40 0 1 0 -4 1 10 0 0 1 6 -7 40 0 0 0 2 7 55

Estos cortes se pueden comprobar gráficamente, expresando las ecuaciones de los cortes fraccionarios en función de y .

La ecuación del primer corte es: 

Lo cual es equivalente a:

La ecuación del segundo corte es: 

 

Lo cual es equivalente a: 

Entonces la adición de estas 2 restricciones proporcionará el nuevo punto extremo (óptimo):

Algoritmo Mixto

CASO 2:

Consideramos el ejemplo anterior, pero ahora suponemos que está únicamente restringida a valores enteros. La ecuación es:

Analizamos los coeficientes de cada variable para hacer el corte mixto de acuerdo a la teoría, y tenemos:

Entonces el corte fraccional será:

Este corte se agrega a la última tabla:

Resolvemos por el método simplex y obtenemos:

Esta tabla nos proporciona la solución óptima (donde solo requiere ser entero):

0 1 7/22 1/22 0 7/21 0 -1/22 3/22 0 9/20 0 -1/22 -3/22 1 -1/20 0 28/11 15/11 0 63

0 1 10/33 0 -1/3 10/31 0 -1/11 0 1 40 0 1/3 1 -22/3 11/30 0 23/11 0 10 58

Caso de ejemplo 3:

 

Max. Z= 4x1+5x2+x3 Sujeto a;

3x1 + 2x2 ≤ 10

1x1 + 4x2 ≤ 11

3x1 + 3x2 + x3 ≤ 13

x1 , x2 ,x3 ≥ 0 , enteros

 

Tabla inicial

Tabla optima

1a. Restricción

x1+4/10 x4+8/10 x5 = 1 + 8/10 a [a] f= a -[a]

x1=1 1 1 0

4/10 x4+8/10 x5 ≥8/10 4/10 0 4/10

s1 = 4/10 x4+8/10 x5-8/10 -2/10 -1 +8/10

s1 - 4/10 x4-8/10 x5 =-8/10

2da. Restricción

x2 + 9/10 x4 + 3/10 x5 = 2 + 3/10 a [a] f= a -[a]

x2 =2 2 2 0

+9/10 x4 + 3/10 x5 ≥3/10 -1/10 -1 + 9/10

s1=+9/10 x4 +3/10 x5-3/10 3/10 0 3/10

s1-9/10 x4-3/10 x5 =-3/10

 

3a. Restricción

x3 + 1/10 x4 + 7/10 x5 =7/10 a [a] f= a -[a]

x3=1

1/10 x4 + 7/10 x5 ≥7/10 1 1 0

s1 =+1/10 x4+7/10 x5 -7/10 -9/10 -1 +1/10

s1-1/10 x4-7/10 x5 = -7/10 -3/10 -1 +7/10

 

como f1 (8/10) > f2 (3/10) y f1(8/10) > f3 (7/10) ( f1 tiene la mayor fracción) se trabaja con la ecuación un 1ª ecuación

Utilizando el Dual-Simplex para determinar la variable que entra en solución: Max {(z4-c4 )/y44 , (z5 -c5 )/y45 } = Max {(2/10)/(- 4/10) , (4/10)/(- 8/10)} = Max {-1/2 , -1/2} (empate), entra (arbitrariamente) x4 en solución.

2da. Ecuación

x2 +1/2 x5 +3/4 x1 = 2 + 5/10 a [a] f=a -[a]

x2 = 2 1/2 0 1/2

s2 = 1/2 x5 +3/4 s1-1/2 -1/4 -1 3/4

s2-1/2x5-3/4 s1=-1/2

 

3a. Ecuación

x3 +1/2 x5 +x6 +3/4 s1 = 2 + 5/10 a [a] f =a -[a]

1/2 x5 +3/4 s1 ≥ 5/10

x3 +x6 = 2 (1 1 /2 ) 3/2 1 1/2

s2=1/2 x5+3/4 s1-1/2 (-21 /4 ) -9/4 -3 3/4

s2 -1/2 x5 -3/4 s1 =-1/2.

 

como son iguales sus partes fraccionales, se elige la ecuación que corresponda a la variable básica con la mayor contribución en la función objetivo (la ecuación 2).

Utilizando Dual-Simplex para determinar la variable que entra en solución Max {(0/-1/2) , (1/2/- 3/4)} = Max {0 , -2/3)} entra x5 en solución.

Solución Óptima:

Por

Programación lineal Programación entera

x1= 1.8 x1= 2

x2= 2.3 x2= 2

x3= .7 x3= 1

x4= 0

x5= 1

Z* = 19.4 Z* =19

 Si el sistema de ecuaciones fuera:

3x1+ 2x2 ≤ 10

x1+ 4x2 ≤ 11

3x1+ 3x2+ x3 ≤ 13

x1+ 2x2 ≤ 6 ← Corresponde al 1er corte

5x1+14x2 ≤ 38 ← Corresponde al 2do corte

y su función objetivo

Max Z = 4x1 +5x2 +x3

La solución óptima sería:

x1 = 2

x2 = 2

x3 = 1

z = 19

Obtención de las ecuaciones de los cortes

1er Corte

Dado que inicialmente 3x1+2x2 ≤ 10 y que 3x1+2x2 +x4 = 10, así x4 = 10- 3x1-2x2

Y dado que inicialmente x1+4x2 ≤ 11 y que x1+4x2 + x5 = 11, así x5 = 11- x1- 4x2

Del primer corte, tenemos;

s1-4/10x4 -8/10x5 = -8/10

sustituyendo el valor de x4 y de x5 tenemos;

s1-4/10 (10-3x1-2x2) - 8/10 (11-x1-4x2) = -8/10

s1-128/10 +2x1+4x2= -8/10 ; s1+2x1+4x2= 12

Reduciendo, tenemos;

2x1+4x2 ≤ 12

x1+2x2 ≤ 6

 2do Corte

Dado que inicialmente x1+2x2 ≤ 6 y que x1+2x2 + s1 = 6, así s1 = 6- x1- 2x2

Del 2do. Corte tenemos que;

s2 -1/2 x5-3/4 s1 = -1/2

Sustituyendo el valor de s2, tenemos que;

s2 -1/2(11-x1-4x2) -3/4(6-x1-2x2) = -1/2

s2-11/2+1/2 x1+2x2-9/2+3/4 x1+3/2 x2 = -1/2

s2-10+5/4 x1+7/2 x2 = 19/2

Reduciendo, tenemos;

5/4 x1+7/2 x2 ≤ 19/2

5/2 x1+7 x2 ≤ 19

5x1+ 14x2 ≤ 38

Caso de Ejemplo 4:

 Max. Z = 2x1+ x2

Sujeto a;

x1 + x2 ≤ 5

-x1 + x2 ≤ 0

6x1 + 2x2 ≤ 21

x1 , x2 ≥ 0 , enteros

Max. Z = 2x1+ x2

Sujeto a;

x1 + x2 +x3 ≤ 5

-x1 + x2 + x4 ≤ 0

6x1 + 2x2 + x5 ≤ 21

x1 , x2 ≥ 0 , enteros

 

Tabla inicial

Tabla optima

La 3a. Ecuación es la que tiene la mayor parte fraccional en el lado derecho

 

3a. Restricción

x1 + 1/2x3 + 1/4x5 = 2 3/4 a [a] f= a-[a]

x1 = 2 11/4 2 3/4

1/2x3 + 1/4x5≥ ¾ -1/2 -1 1/2

s1 = 1/2 x3 + 1/4 x5 – 3/4 1/4 0 1/4

 

 Tenemos el 1er. Corte y se añade la ecuación

-1/2x3- 1/4x5 + s1= -3/4

Utilizando el Dual-Simplex para determinar la variable que entra en solución:

Max {(z4-c4 )/y44 , (z5 -c5 )/y45 } = Max {(1/2)/(-1/2) , (1/4)/(-1/4)} = Max {1 , 1} (empate), entra (arbitrariamente) x3 en solución.

Las ecuaciones 1, 2 y 3 tienen la mayor parte fraccional

 1da. Ecuación

x3 -1/2x5 -2s1 = 1 ½ a [a] f=a -[a]

x3 -2s1 = 1 1 1/2 1 1/2

s2 =1/2x5 + 1/2 -1/2 -1 1/2

 2a. Ecuación

x4 +3/2x5 -4s1 = 3 1/2 a [a] f =a-[a]

x4 -4s1 = 3 (3 1 /2 ) 1/2 3 1/2

s2=1/2 x5+1/2 ( 1 1/2 ) 1/2 0 1/2

 3a. Ecuación

x1 +1/2x5 -1s1 = 3 1/2 a [a] f =a-[a]

x1 -1s1 = 3 (3 1 /2 ) 1/2 3 1/2

s2=1/2 x5+1/2 ( 1/2 ) 1/2 0 1/2

Existe un empate, por lo que se elige la ecuación que corresponda a la variable básica con la mayor contribución en la función objetivo (la ecuación 1). Tenemos el 2do. Corte y se añade la ecuación s2 -1/2 x5 = -1/2

Utilizando Dual-Simplex para determinar la variable que entra en solución Max {(0/-1/2) = Max {0} entra x5 en solución.

Solución Óptima:

Por

Programación lineal Programación entera

x1= 2.75 x1= 3

x2= 2.25 x2= 1

x4= .5 x3= 1

x4= 2

x5= 1

Z* = 7.75 Z* =7

Determinación de las ecuaciones correspondientes a los cortes y que deberán ser añadidas a las ecuaciones del problema original, que al ser resuelto se obtenga una solución entera.

 

1er. Corte

Tenemos que s1-1/2x3- 1/4x5 = -3/4 que equivale a 1/2x3 + 1/4x5 ≥ 3/4y como x3 en la 1ª restricción

x1 + x2 + x3 =5 es igual a x3= 5 -x1 - x2

y x5 en la 3ª restricción 6x1 + 2x2 +x5 = 21 es igual a x5= 21 -6x1 - 2x2

sustituyéndolas en el 1er. Corte, tenemos que

1/2(5 -x1 -x2) + ¼(-6x1 - 2x2 +21 ) ≥ 3/4, reduciendo encontramos que: 2x1+x2≤ 7

 

2do. Corte

Tenemos que s2 -1/2 x5 = -1/2 que equivale a 1/2 x5 ≥ 1/2 y como en la 1ª restricción 6x1 + 2x2 + x5≤ 21 es igual a x5 = -6x1 - 2x2 +21

sustituyéndolas en el 2do Corte, tenemos que

-1/2(-6x1 - 2x2 +21) ≥-1/2, reduciendo encontramos que: 3x1+x2≤ 10