Metodo Simplex
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...
Regístrate para leer el documento completo.