Metodo Simplex

ENFOQUE ALGEBRAICO DEL
METODO SIMPLEX

Métodos de solución

Símplex

Dos fases

Algebraico

M grande

Programación
lineal
Gráfico

Karmarkar

Símplex
revisado
Dual
Símplex

El método algebraico es una forma de trabajar con el método simplex
pero sin usar las tablas,
utiliza únicamente álgebra y lógica matemática para  hallar la solución
optima. Consta de los siguientes pasos:
1.Determinar siexiste una básica factible inicial
2.Determinar si existe una solución básica factible mejor. Si es así 
realizar el siguiente paso, de otro modo, la solución actual es optima
3.Pasar a la siguiente solución básica factible, cambiando una variable
básica por una no básica, haciendo que todas las variables sean no
negativas y regresamos al paso 2
Este método es poco aplicado porque llega a ser muytardado y poco
practico, a diferencia del simplex donde toda la información se
almacena en tablas y las operaciones  de estas tablas son rápidas. Pero
este método trabaja muy rápido cuando los sistemas de restricciones es
muy pequeño y no hay que hacer tantos movimientos entre los
extremos de la región factible. A continuación se muestra un ejemplo
resuelto con el método algebraico .
Se tiene lossiguientes pasos :

PASOS :
Consta de los siguientes pasos :
1.-Identificar una solución básica factible inicial.
2.-Determinar si existe una solución básica factible
mejor. Si es así, llevar a cabo el siguiente paso . Sino la
solución actual es la óptima .
3.- Pasar a la siguiente solución básica factible,
cambiando una variable no básica por una variable
básica, haciendo que todas las variablessigan siendo
no-negativas y regresar al paso 2.

Ejemplo:
Suponga el siguiente modelo :
max. z= 3x1 + 2x2
S.A. : 2X1 + X2 < 100

x1 + x2 < 80
x1 < 40
con : X1, X2 > 0
Podemos encontrar la solución sin hacer uso de la
gráfica.

X2
90
80

440

50

60

X1

r

max. z= 3x1 + 2x2

max. z= 3x1 + 2x2

S.A. : 2X1 + X2 < 100

S.A. : 2X1 + X2 + X3 =100

x1 + x2 < 80
x1 < 40

x1 + x2 + X4 = 80
x1 + X5 = 40con : X1, X2 > 0

con : X1, X2 , X3, X4 X5 > 0

Forma
Estándar

max. z= 3x1 + 2x2
S.A. : 2X1 + X2 + X3 =100

x1 + x2 + X4 = 80
x1 + X5 = 40
con : X1, X2 , X3, X4 X5 > 0

5 variables
3 restricciones
3 variables básicas
2 variables no básicas

X2
90
80

Una primera
solución será el
origen

440

50

60

X1

max. z= 3x1 + 2x2
S.A. : 2X1 + X2 + X3 =100

x1 + x2 + X4 = 80
x1 + X5 = 40
con : X1, X2 ,X3, X4 X5 > 0

X1 = 0 X2 =0
X3 =100
X4 = 80
X5 = 40
Z = 0

x1

y

x2

v. no básicas

X3, X4 X5 v. básicas

z = 3x1 + 2x2
X3 = 100 – (2X1 + X2 )
X4 = 80 – (x1 + x2 )
X5 = 40 - x1

Despejando el modelo las
variables básicas
X3, X4 X5 y lo dejamos en
función a x1 y
básicas )

x2

(v. no

Elegimos el coeficiente mayor de la función
objetivo porque el ejercicio es de maximizar

z = 3x1 + 2x2
X3 =100 – (2X1 + X2 )
X4 = 80 – (x1 + x2 )
X5 = 40 - x1

rPara la nueva
solución se
debe
intercambiar
una variable no
básica por una
variable básica

Que variable no básica se debe elegir para convertir en básica ?

X1 sera v. básica y X2 sera v.no básica
X2 = 0

z = 3x1 + 2x2
X3 = 100 – (2X1 + X2 )
X4 = 80 – (x1 + x2 )
X5 = 40 - x1

Ahora debemos elegir
entre X3, X4 X5
para convertir en
variable nobásica

DOS PREGUNTAS :
Cuál sera el nuevo valor de X1 ?
Cuál sera la nueva variable no básica ?

z = 3x1 + 2x2
X3 = 100 – (2X1 + X2 )
X4 = 80 – (x1 + x2 )

Se sabe que todas
las variables tienen
que ser mayores e
iguales a cero.

X5 = 40 - x1
Si X1, toma un valor
muy grande entonces
alguna de las variables
X3, X4 y X5 se
volverá negativa

X3, X4 X5

pueden tomar valores negativos lo que
trataremosde evitar

z = 3x1 + 2x2
X3 = 100 – (2X1 + X2 )
X4 = 80 – (x1 + x2 )

Se sabe que
X2 es una v.
no básica y
vale cero

X5 = 40 - x1

X3 = 100 – 2X1
X4 = 80 – x1
X5 = 40 - x1
X3 = 100 – 2X1

Lo máximo que puede X1 es hasta
que X3 = 0

Conforme x1 aumenta
x3 disminuye

Posibles valores

X3 = 100 – 2X1
X4 = 80 – x1
X5 = 40 - x1

0 = 100 – 2X1

X1 = 50 y X3= 0

0 = 80 – x1

X1 = 80 y x4 =0

0 = 40...