Ejercicios de ramificación y acotamiento

Problema 4:

Se tiene el siguiente problema de programación entera:

Maximizar z = 3x1 + x2

s.a.

2x1 - x2  =< 6

x1 + x2 =< 4

x1,x2 Є Z+

 (Z+= enteros positivos)

Resuelva este problema usando los criterios del algoritmo de Ramificación y Acotamiento. Para cada sub-problema se debe presentar la formulación matemática, la solución óptima y el valor óptimo. Indique los límites inferior y superior encontrados durante el proceso. Al final del algoritmo indique cuál es la solución óptima y su respectivo valor óptimo. Obs. Para resolver cada sub-problema puede utilizar el solver o Lindo.

Solución Método R&R

Resolvemos primero como un problema de PL Relajado (RL)

P0:

Maximizar z = 3x1 + x2 (RL)

s.a.

2x1 - x2  =< 6

x1 + x2 =< 4

x1,x2 >=0

Resolviendo con LINDO queda:

[pic 1]

Solución relajada para P0:

z=10,67

x1= 3,33 y x2=0,67

[pic 2][pic 3][pic 4]

[pic 5]

[pic 6]

[pic 7][pic 8][pic 9]

[pic 10][pic 11][pic 12][pic 13]

[pic 14][pic 15]

[pic 16][pic 17][pic 18]

[pic 19]

[pic 20][pic 21][pic 22][pic 23]

[pic 24][pic 25][pic 26][pic 27]

[pic 28][pic 29][pic 30][pic 31][pic 32]

[pic 33]

[pic 34]

                    _        Lim inferior    _        Lim Superior

Inicialmente        -oo                         +oo

P0                               -oo                10,66= 10 2/3

[pic 35]

P1

Maximizar z = 3x1 + x2 (RL)

s.a.

2x1 - x2  =< 6

x1 + x2 =< 4

x1=< 3

x1,x2 >=0

Resolviendo con LINDO queda:

[pic 36]

P1:

Solución óptima x1= 3, x2=1

Valor óptimo z=10

No tiene sentido seguir explorando por cualquiera otra solución dará menor que z=10

[pic 37]

[pic 38]

                    _        Lim inferior    _        Lim Superior

Inicialmente        -oo                         +oo

P0                               -oo                10,66= 10 2/3

...