algoritmo simplex

FORMATO TABLEAU

Base
xB1
…
…
xBm

cB
cB1
…
…
CBm

c1
valor x1
hB1
y11
…
…
…
…
hBm ym1
Z
z1-c1

…
…
…
…
…
…
…

PASOS SIMPLEX EN LA TABLA
…
…
…
…
…
…
…

cn
xn
y1n
…
…
ymn
zn-cn

Donde:

∀ ∈{1 m y ∀ ∈{1 n} siendo m< n:
i ,..., } j ,...,

xBi VB que está en la fila i-ésima
cBi Coef en la FO de la VB de la fila i-ésima
cB Vector de coef en laFO de las VB
hBi Valor de la VB de la fila i-ésima
yij Componente i-ésima del vector de coef asociados a la
vble j-ésima en la base definida por los vectores
asociados a las VB
Z valor de la FO en el vértice: Z = m c h

∑

Bi

Bi

i =1

P0: ESTANDARIZACIÓN
P1: CONDICIONES INICIALES
P2: POSIBILIDAD DE MEJORAR LA FO
P3: OPTIMALIDAD - INFACTIBILIDAD
P4: ELECCIÓN DE LA VBLE DEENTRADA
P5: ELECCIÓN DE LA VBLE DE SALIDA
P6: SOLUCIÓN IMPROPIA-INFACTIBLE
P7: CÁLCULO DE LA NUEVA TABLA

z −cj Cambio (signo cambiado) en la FO al pasar del valor de
j
la VNB j-ésima de 0 a 1

1

2

PASOS DETALLADOS

P2: POSIBILIDAD DE MEJORAR LA FO

P0: ESTANDARIZACIÓN
- Restricciones expresadas en igualdad

En PL
de Max

- Lado derecho ≥ 0
- Vbles artificiales para basecanónica

En PL
de Min

P1: CONDICIONES INICIALES

∃ algún z j − c j < 0

ir P4

Todos los z j − c j ≥ 0

ir P3

∃ algún z j − c j > 0

ir P4

Todos los z j − c j ≤ 0

ir P3

- Elegir xBi vble según vector canónico
- Hacer hBi =bi ∀i ∈ {1,..., m}
- Fijar yij=aij ∀i ∈ {1
,...,m} y ∀j ∈{1 n}
,...,

3

4

P3: OPTIMALIDAD - INFACTIBILIDAD
P4: ELECCIÓN DE LA VBLE DEENTRADA

∃ alguna vble
artificial con valor
≠ 0 en la base
NO

Problema
infactible

SI

En PL
de Max:

En PL
de Min:

Solución propia

zj − cj
más
negativa
zj − cj
más
positiva

¿Hay alguna VNB con z j − c j = 0 ?
SI

NO

Empate
deshacerlo
arbitrariamente

Única

Múltiple
¿Tiene algún yij>0?
NO

SI
Acotada

No acotada

5

6

P6: SOLUCIÓNIMPROPIA-INFACTIBLE
P5: ELECCIÓN DE LA VBLE DE SALIDA
Si entra vble k:

¿ ∃ ninguna variable artificial
con valor ≠ 0 en la base?

Candidatas a
salir:

vbles con
yik >0

∃ ninguna
/

NO

Ir P6

Solución
impropia

SI
Problema
infactible

∃ alguna
elegir
la
de
menor hBi/yik

Si hay empates
deshacerlos
arbitrariamente

Ir P7

7

8

P7: CÁLCULO DE LA NUEVA TABLAEJEMPLO EJERCICIO 21.1

Entra vble de la
columna k-ésima

Paso 0: ESTANDARIZACIÓN

Sale vble de la
fila r-ésima

Elemento
pivote yrk

Max f (x) = 7 x1 + 10 x 2 + 0 x 3 + 0 x 4
x

sa

4 x1 + 3x 2 + x 3 = 12

Calculo nueva tabla en la que:

2 x1 + 5x 2 + x 4 = 10

Figure xK en base en vez de xBr, con
su coef en la FO

Calcular los
nuevos hBi e
yij

x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0,x 4 ≥ 0

 hBj
 y si i = r

º
rk
hBi = 
h − hBi yik si i ≠ r
 Bi yrk


Las dos restricciones transformadas se pueden
escribir también como la siguiente matriz
 x1 
 
 4 3 1 0   x 2  12 
2 5 0 1  x  = 10 

 3
 
 
x4 

y ij

si i = r
 y

rk
º
y ij = 
y − y rj y ik si i ≠ r
 ij
y rk


Ahora hay 4 variables todas condicionadas aser NO NEGATIVAS.

Calcular los nuevos z j − c j y Z
Con a nueva tabla volver al P2
9

10

Paso 2: POSIBILIDAD DE MEJORAR LA FO

Paso 1: CONDICIONES INICIALES
- Elegir xBi vble según vector canónico
- Hacer hBi =bi ∀i ∈ {1,..., m}
- Fijar yij=aij ∀i ∈ {1
,...,m} y ∀j ∈{1 n}
,...,

∃ algún z j − c j < 0
Todos los z j − c j ≥ 0

En PL
de Max

 x1 
 
 4 3 1 0   x 2 12 
2 5 0 1  x  = 10 

 3
 
 
x4 

ir P4
ir P3

7
Base

10

0

0

CB Valor

x1

x2

x3

x4

7

10

0

0

x3

0

12

4

3

1

0

CB Valor

x1

x2

x3

x4

x4

0

10

2

5

0

1

x3

0

12

4

3

1

0

0

-7

-10

0

0

x4

0

10

2

5

0

1

Base

0

-7

-10...