Clase9 Simplex revisado

Clase # 9

TEORÍA DEL MÉTODO
SIMPLEX

EL MÉTODO SIMPLEX
REVISADO
9-1

El MÉTODO SIMPLEX REVISADO
9.1 El Modelo Matricial
9.2 El Modelo Matricial Aumentado

9.3 El modelo matricial aumentado incluyendo
el renglón (0)
9.4 Solución
9.5 Cálculo de una nueva solución
9.6 El Tablero Simplex Revisado
9.7 Ejemplo Prototipo: La Wyndor Glass Co.

9-2

Coeficientes
Iter
0

V.B

Ec #

Z

X1

X2

X3

X5X4

L.D

Z

(0)

1

-3

-5

0

0

0

0

X3

(1)

0

1

0

1

0

0

4

X4

(2)

0

0

2

0

1

0

12

X5

(3)

0

3

2

0

0

1

18

Iter

V.B

Ec #

1

Z

(0)

1

-3

0

X3

(1)

0

1

X2

(2)

0

X5

(3)

0

Iter

V.B

Ec #

2

Z

(0)

1

0

0

0

X3

(1)

0

0

0

1

1/3

-1/3

2

X2

(2)

0

0

1

0

1/2

0

6

X1

(3)

0

1

0

0

-1/3

1/3

2

Razón

Coeficientes
Z

X1

X2

L.D

X4

X5

0

5/20

0

1

0

0

4

0

1

0

1/2

0

6

3

0

0

-1

1

6

X3

Razón

30

Coeficientes
Z

X1

X2

X3

X4

X5

3/2

1

L.D
36

Razón

9.1 EL MODELO MATRICIAL
Variables y parámetros:
C: Vector fila de coeficientes de costo
X: Vector columna de variables de decisión
A: Matriz de coeficientes tecnológicos
b: Vector columna de recursos o requerimientos
0: Vector columna de ceros

Max Z = c x
Sujeto aA x  b
x  0
9-4

9.2 EL MODELO MATRICIAL AUMENTADO

Sea Xs: Vector columna de variables de holgura
x n+1
x n+2

El modelo aumentado:

Maximizar CX
S.a
A x + I Xs = b
x  0 xs  0

xn+m

(n-m)x1

puede escribirse así:

Maximizar Z = CX
Sujeto a:

A I

x
xs

=b
9-5

9.3 El MODELO MATRICIAL AUMENTADO
INCLUYENDO EL RENGLÓN (0)
El sistema
Maximizar Z = CX
Sujeto a [A I]

x
xs

b

=

Puedeescribirse como:

1
0

-c

A

0

I

Z
x
xs

=

0

b
9-6

9.4 SOLUCIÓN
9.4.1 Sistema a resolver:
m ecuaciones (lineales simultáneas)
m: variables básicas

n variables (de decisión, de holgura, excedencia y
artificiales)
Donde n > m
n-m variable no básicas (iguales a cero, por
definición)
9-7

9.4.2

Descomponiendo el sistema en variables básicas
XB y No básicas XNB, se obtiene un sistema de m
variables ym ecuaciones, así:

N XNB+ B xB =
b
0

De donde:

B xB = b

Y premultiplicando por B-1, se tiene:
B-1 B xB = B-1 b
xB = B-1 b

9-8

9.4.3 Valor de la F.O.
Sea cB el vector de coeficientes de costos de
las V.B (inicialmente pueden ser ceros).
Z = cB X B
Como

xB = B-1 b

Z = cB B-1 b
9-9

9.5 CÁLCULO DE UNA NUEVA SOLUCIÓN

Pasar de la solución inicial a otra solución es
equivalente apremultiplicar, ambos lados de
la ecuación matricial, por
1

cB B-1

0

B-1

Entonces:
Cómo queda el sistema?

9-10

9.5.1 Coeficientes del lado izquierdo
Premultiplicando por la citada matriz, los
coeficientes del lado izquierdo quedan así:

1

cB B-1

0

B-1

1

-c

0

0

A

I

=

1

0

(cB B-1A - c) cB B-1
B-1A

B-1

9-11

9.5.2 Coeficientes del lado derecho:
Premultiplicando por la matriz anterior, ellado
derecho de la ecuación matricial será:
-1
c
B
1 B

0

B-1

0
b

=

cB B-1 b
B-1 b

Lado derecho
original 9-12

9.5.3 El sistema de ecuaciones
El sistema de ecuaciones después de cualquier
iteración puede escribirse de la forma:

1

cB B-1A - c

0

B-1A

cB B-1
B-1

Z
x
xs

=

cB B-1b
B-1b

9-13

9.6 EL TABLERO SIMPLEX REVISADO

El tablero simplex revisado, después de
cualquier iteración,tiene la siguiente forma:
1

cB B-1A - c

0

B-1A

cBB-1

cB B-1b

B-1

B-1b

Sólo es necesario obtener B-1 para calcular toda
la tabla a partir de los parámetros iniciales.
OJO: Al pasar de un tablero a otro,
Cambia la Base B y por lo tanto su inversa B-1

9-14

9.7 EJEMPLO PROTOTIPO:
La Wyndor Glass Co.
c= 3 5

A I

=

x = x1
x2

1

0

1 0

0

0

2

0 1

0

3

2

0 0

1

x3
xs =
x4
x5

1

0

A= 02

3

2

b =

4
12
18
9-15

9.7.0 Iteración 0. Solución inicial?
Toda solución se puede escribir como XB = B-1b

Variables básicas? B-1 = ?
x3 x4 x5

xB

x3
=
x4
x5

1

0

0

B= 0

1

0

0

0

1

= B-1
9-16

Solución inicial: XB = B-1b
x3
x4
x5

=

1
0
0

0 0
1 0
0 1

4
12
18

=

4
12
18

Valor de la FO. ?

Z = CBXB = CBB-1b

cB = 0 0 0
Z = c B B-1 b

=

0 0 0

4
12
18

= 0
9-17

9.7.1...