MÉTODO ALGORITMO DE SIMPLEX- SOLUCIÓN DE MAXIMIZACIÓN Y MINIMIZACIÓN

...

Como se trata de maximización para que pueda ser una solución óptima la fila Zj-Cj deben ser ceros o positivos. En este caso todavía no hay solución óptima. Se tendrá que escoger la variable que debe entrar en el 2do tablero.

Se escoge en la fila Zj-Cj cuando se trata de maximización el menor negativo, o sea (-2) en esta columna se encuentra la variable x2 para que pueda entrar esta variable, debe salir, x3 ó x4 según sea el caso, para ello es necesario hacer:

[pic 23] 1=4/1 y [pic 24] 2=6/-10 -6

La variable que debe salir será x3 porque es el menor positivo. No se toma en cuenta los negativos. Por lo tanto el 2do tablero es el siguiente:

Cj →

1 2 0 0

Ck

XK

Bi

x1 x2 3 x4

2

X2

4

2 1 1 0

0

X4

10

3 0 1 1

Zj

8

4 2 2 0

Zj-Cj

0 2 0

La intersección de la variable que entra y sale es Pivote y los demás de la misma columna semi pivote [pic 25] [pic 26] Semi pivote[pic 27]

Cálculos para el 2do tablero

1ra fila: coeficientes pilótales son: 4 , 2, 1, 1 , 0 , = 4, 2, 1, 1, 0

1 1 1 1 1

2da fila: CI – CPxSP regla

CI= coeficientes iniciales (del tablero anterior)

CP= Coeficientes pilótales (de lo que se ha hallado)[pic 28]

SP= semi-pivote en este caso -1

Aplicando la regla tenemos:

6 – 4x – 1 = 6 + 4 = 10

1 – 2x – 1 = 1 + 2 = 3

-1 – 1X – 1 = -1 + 1 = 0

0 – 1x – 1 = 0 + 1 = 1

1 – 0x – 1 = 1 + 0 = 1

Observando la fila Zj – Cj en el segundo tablero todos son ceros y positivos, por lo tanto se ha llegado a la solución óptima.

Intervienen en la solución óptima

X2 = 4 y x4 =6; y todos aquellos que no intervienen x1, x3 toman valores cero.

→ Zmax=x1 + 2x2 + 0x3 + 0x4

= 0 + 2(4) + 0 + 0(6)

Z max = 8

EJEMPLO 2:

Sea el siguiente programa lineal

Zmin= 3x1 + x2

S.A. x1 + 2x2 [pic 29] 5

X1 + x2 [pic 30] 2

Solución por el método de algoritmo de simples

- Se establece el sistema de ecuaciones

x1 + 2x2 – x3 + [pic 31]1 = 5

x1 + x2 - x4 +[pic 32]2 = 2

Zmin = 3x1 + x2 + 0x3 + 0x4 + M[pic 33]1+[pic 34]M2

Aquí la base sera: I1 y I2 variables artificiales con su respectivo coeficiente: M

Tablero 1:

Cj →

3

1

0

0

M

M

Ck

Xk

Bi

x1

x2

x3

x4

[pic 35] 1

[pic 36] 2

M

M

[pic 37]1

[pic 38]2

5

2

1

1

2

1

-1

0

0

-1

1

0

0

1

Zj

7M

2M

3M

-M

-M

M

M

Zj-Cj

2M-3

3M-1

-M

-M

0

0

Cálculos de Zj y Zj-Cj tenemos:

Se determina Zj multiplicando el valor de Ck por cada una de los coeficientes de las filas y sumando en columna así:

...