Scribd
Cargar
352 vistas9 páginas

Ejercicio Algoritmo de Gomory

Este documento presenta la solución de un problema de programación lineal mediante el método simplex. Se maximiza la función objetivo Z = 8X1 + 5X2 sujeto a las restricciones X1 + 6S1 = 6 y X1 + 5S2 = 45. Tras aplicar el método simplex se obtiene la solución óptima continua X1 = 15/4, X2 = 9/4, S1 = 0, S2 = 0, Z = 165/4. Posteriormente, se aplica el algoritmo de Gomory para obtener una solución entera,

Cargado por

Alejando
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
352 vistas9 páginas

Ejercicio Algoritmo de Gomory

Este documento presenta la solución de un problema de programación lineal mediante el método simplex. Se maximiza la función objetivo Z = 8X1 + 5X2 sujeto a las restricciones X1 + 6S1 = 6 y X1 + 5S2 = 45. Tras aplicar el método simplex se obtiene la solución óptima continua X1 = 15/4, X2 = 9/4, S1 = 0, S2 = 0, Z = 165/4. Posteriormente, se aplica el algoritmo de Gomory para obtener una solución entera,

Cargado por

Alejando
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

ALGORIT

MO DE
GOMORY

EJERCICIO

MAX Z = 8 X1+ 5 X2
Con sus restricciones:

MAX Z = 8 X1+ 5 X2
Con sus restricciones:

A continuacin solucionamos el problema por el mtodo simplex,


tal como se hara si el problema fuese de programacin lineal continua

PRIMERA TABLA SIMPLEX

Cj

CB

VB

X1

X2

S1

S2

S1

b/a
6

S2

45

Zj
Cj-Zj

Variable que entra a la base:X1


Variable que sale de la base:S2

SEGUNDA TABLA
SIMPLEX

0
CB
0
8

0
VB
S1
X1
Zj
Cj-Zj

Cj
b
1
5
40

8
X1
0
1
8

5
X2
4/9
5/9
40/9

0
S1
1
0
0

0
S2
- 1/9
1/9
8/9

5/9

- 8/9

Variable que entra a la


base:X2 Variable que sale
de la base:S1

b/a
9/4
9

ULTIMA TABLA SIMPLEX

0
CB
5
8

0
Cj
VB
b
X2 9/4
X1 15/4
165/
Zj
4
Cj-Zj

8
X1
0
1

5
X2
1
0

0
S1
9/4
-5/4

0
S2
-1/4
1/4

5/4

3/4

-5/4

- 3/4

Ecuaci
n
(1)

Solucin ptima Continua (No Entera): X1= 15/4;X2= 9/4;S1= 0;S2=0;


Z= 165/4

X1=
15/4=1+11/4
X2= 9/4=1+5/4

Realizamos el mtodo Gomory


ECUACION 1 (Fila 2) .-Para construir la nueva restriccin; ya que tiene la Variable
(X1), cuyo valor de su parte fraccional es Mayor

Clculo de la nueva restriccin, a partir de la Ecuacin 1


X1 - 5/4S1 + 1/4S2 = 8

Remplazamos cada constante por la suma de un nmero entero de


signo y una fraccin no negativa menor que uno (1).
X1- 5/4 S1+ 1/4S2= 15/4
(1 + 0)X1+ ( 2 + 3/4)S1 + (0 + 1/4)S2=
(3 + 3/4)
X1 - 2S1 + 3/4S1 + 1/4S2 = 3 + 3/4

cualquier

Trasladamos los trminos con coeficiente entero, al lado derecho.


3/4S1 + 1/4S2 = 3/4 +3 + X1 + 2S1
POSITIVO
ENTERO

Fjese que el lado izquierdo subrayado debe ser positivo y el lado


derecho subrayado, debe ser entero, luego podemos asegurar que:
3/4S1 + 1/4S2 > 3/4

; Multiplicando por (-1)

-3/4S1 - 1/4S2 < -3/4


ADICIONANDO UNA VARIABLE DE HOLGURA (S3):
-3/4S1 - 1/4S2 + S3 < -3/4

Esta restriccin se aade como una restriccin secundaria a la tabla


simplex ptima de la PL, como sigue a Continuacin

PRIMERA TABLA SIMPLEX DUAL

0
CB
5
8
0

0
Cj
8
VB b
X1
X2 9/4 0
X1 15/4 1
S3 -3/4 0
165/
Zj
8
4
Cj-Zj
0

(Cj - Zj)/arj

No

5
X2
1
0
0

0
S1
9/4
-5/4
-3/4

0
S2
-1/4
1/4
-1/4

0
S3
0
0
1

5/4

3/4

-5/4

- 3/4

No

5/3

b/a
1
-3
3

arj = son los coeficientes de las variables de la nueva restriccin insertada.

NOTA: Para hallar el elemento pivote en esta tabla Simplex Dual se toma en cuenta El
valor fraccional de la fila [(Cj - Zj)/arj]. Por ello tomamos la columna de -3/4

ULTIMA TABLA SIMPLEX DUAL

0 0
CB VB
5 X2
8 X1
0 S1
Zj

Cj
b
0
5
1
40

8
X1
0
1
0
0

5
X2
1
0
0
0

0
S1
0
0
1
0

0
S2
-1
2/3
1/3
1/3

X1=5
X2=0
S1=1
Z=40

Solucin factible, ptima y ENTERA

0
S3
3
-5/3
-4/3
5/3

También podría gustarte