El Metodo Simplex. Un Resumen - 1

Solucin de Modelos de Programacin Lineal,
un resumen
El Metodo Simplex
Que el estudiante sea capaz de
conocer los elementos del Mtodo
Simplex y resuelva problemas
PROF: CRISTELA
FUENTES
EL MTODO SIMPLEX
Es un mtodo genrico de solucin de problemas
lineales, desarrollado por George Dantzig en 1947.
Como tal, el mtodo simplex es un procedimiento
algebraico, pero puede entenderse ms fcilmente
como un mtodo geomtrico.
Antes de
Simplex,
hacerse a
el Mtodo
explicar los aspectos geomtricos del

veremos el tratamiento que debe
cualquier modelo de PL antes de aplicar
Simplex sobre l para solucionarlo.
Conversin de modelos de PL a la
Forma Estndar
/1
Todo modelo de PL, para efectos de resolverse con el Mtodo

Simplex, debe llevarse a una Forma Estndar con las siguientes
caractersticas:
1. El lado derecho de las ecuaciones debe ser no-negativo
2. Todas las restricciones deben convertirse a Ecuaciones
3. Todas las variables deben ser no-negativas
EJEMPLO: Maximizar Z = 2x1 + 3x2 + x3
Sujeto a:
x1 + x2 + x3 = 10
-2x1 + 3x2 + 2x3 -5
7x1 - 4x2 + 5x3 6
x1 + 4x2 + 3x3 8
x1 , x2 , x3 0
Conversin de modelos de PL a la
Forma Estndar
Maximizar Z = 2x1 + 3x2 + x3
Sujeto a: x1 + x2 + x3 = 10
Maximizar Z = 2x1 + 3x2 + x3
Sujeto a: x1 + x2 + x3 = 10
-2x1 + 3x2 + 2x3 -5
2x1 - 3x2 - 2x3 5
7x1 - 4x2 + 5x3 6
7x1 - 4x2 + 5x3 6
x1 + 4x2 + 3x3 8
x1 + 4x2 + 3x3 8
x1 , x2 , x3 0
x1 , x2, x3 0
/2
Maximizar Z = 2x1 3x2 + x3

Sujeto a: x1 + x2 + x3 = 10
2x1 - 3x2 - 2x3 h1 = 5
7x1 - 4x2 + 5x3 + h2 = 6
x1 + 4x2 + 3x3 h3 = 8
x1 , x2 , x3 0, h10, h20, h30
Soluciones Bsicas
EJEMPLO: Minimizar Z = -3x1 - 5x2
Sujeto a:
x1 4
2x2 12
Forma
Estnda
r
Minimizar Z = -3x1 - 5x2

Sujeto a: x1 + h1 = 4
2x2 + h2 = 12
3x1 + 2x2 18
3x1 + 2x2 + h3 = 18
x1 , x2 0
x1 , x2 , h1, h2, h3 0
El Mtodo Simplex observa el conjunto de

ecuaciones resultantes en la forma estndar, y dado
que hayan m ecuaciones y n incognitas (en este
caso m = 3 y n = 5) le corresponde hacer (n-m)
variables iguales a cero para poder tener
soluciones consistentes. Las soluciones que logra de
esta manera se llaman Soluciones Bsicas.
/1
Simplex Tabular
Minimizar Z = -3x1 - 5x2
El Mtodo Simplex inicia en el punto

P1, que corresponde a la Tabla 1.
Sujeto a: x1 + h1 = 4
2x2 + h2 = 12
3x1 + 2x2 + h3 = 18
x1 , x2 , h1, h2, h3 0
Tabla 1
P1
x1
x2
h1
h2
h3
12
18
Variables
No
Bsicas
Variable
s
Bsicas
Variables
Bsicas
Coeficientes en la
Funcin Objetivo
(Cj)
x1
x2
h1
h2
h3
Solucin
(LD)
h1
h2
12
h3
18
Coeficientes de
las
Valor Objetivo
Simplex Tabular
/2
Ya obtenida la Tabla 1, el
Para ello observamos el
Mtodo Simplex se pregunta:
rengln (Zj ), que da
La Tabla 1 es ptima? (es
slo informacin de las
decir, el punto P1 es
Variables No Bsicas
ptimo?).
Criterio de
Parada
Si todos los valores
Para Minimizacin
del rengln (Zj) 0
Si un valor del rengln (Zj) es positivo,
entonces la Tabla es
indica que al darle valores a la variable no
ptima
bsica respectiva, mejora la funcin
objetivo.
Si un valor del rengln (Zj) es negativo,

Debe ingresar a la
bsica respectiva empeora la funcin
solucin la Variable
objetivo.
No Basica que tenga
el mayor valor
positivo en el rengln
(Zj)
Si un valor del rengln (Zj) es cero,

Criterio
de
bsica respectiva,
no hay cambio en la
Entrada
/3
Simplex Tabular
Columna
entrante
Tabla 1
Variables
Bsicas
Coeficientes en la
Funcin Objetivo
(Cj)
x1
x2
h1
h2
h3
Solucin
(R.H.S.)
Zj
h1
h2
12
12/2 = 6
h3
18
18/2 = 9
sale
Para darle valores ah2
la
variable X2 (es decir,
volver bsica a X2),
debe
salir
de
la
solucin actual una de
las variables bsicas
(es decir, una de ellas
deber
volverse
no
basica cero).
Para saber cual

variable
bsica
actual sale, el
Criterio
de
Salida es con
base en la Razn
Mnima ()
Razn
Mnima
()
Se calcula dividiendo
el elemento de la
columna LD con el
elemento
de
la
columna
entrante,
siempre
que
el
elemento de esta
ltima columna sea
positivo.
Simplex Tabular/4
Tabla 1
Variables
Bsicas
Coeficientes en la
Funcin Objetivo (Cj)
x1
x2
h1
h2
h3
Solucin
(LD)
Zj
h1
h2
12
h3
18
3 5 0 0 0 0
0 2 0 1 0 12
3 2 0 0 1 18
1 0 1 0 0
f2 / 2
3 5 0 0 0 0
0 1 0 1 / 2 0 6 -5f2+ f4
3 2 0 0 1 18 -2f f
2+ 3
1
0
1
0
0
4
3
0
0
1
0
0
0 5/ 2
0 1/ 2
0
1
1
0
Tabla 2
Variables
Bsicas
Coeficientes en la
x1
X2
h1
h2
h3
Solucin
(LD)
Zj
-5/2
-30
h1
x2
-5
1/2
h3
-1
0 30
0
6
1
6
0
4
Simplex Tabular/5
Tabla 2
Variables
Bsicas
Coeficientes en la
x1
X2
h1
h2
h3
Solucin
(LD)
Zj
-5/2
-30
h1
4/1 =4
x2
-5
1/2
h3
-1
6/3 =2
X2
h1
h2
h3
Razn
()
Tabla 3
Variables
Bsicas
Coeficientes en la
x1
Solucin
(LD)
Zj
-3/2
-1
-36
h1
1/3
-1/3
x2
-5
1/2
x1
-3
-1/3
1/3
Tabla
OPTIMA
El Simplex y las Variables Artificiales/1

Minimizar Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 3
Estandarizacion
Tradicional
Minimizar Z = 4x1 + x2
4x1 + 3x2 6
x1 + 2x2 4
x1 , x2 0
4x1 + 3x2 h1 =
6
x1 + 2x2 + h2 = 4
x1 , x2,h1, h2 0
Puede Lograrlo con este

ejemplo?
En general, las restricciones de
= y de generan problemas
al Simplex al momento de
construir la tabla inicial que
arranca el procedimiento.
En
cambio cuando las restricciones
son de no existen estos
inconvenientes y el metodo puede
Como n=4 y m=3, el Simplex

hace n-m variables cero
(en este caso una) para crear
un sistema de ecuaciones
consistente que arroje una
Solucion Inicial Inmediata
y Factible .
El Simplex soluciona estos
inconvenientes
de
inicio
creando Variables Artificiales.

Min Z = 4x1 + x2
Min Z = 4x1 + x2
Sujeto a:
4x1 + 3x2 6
3x1 + x2 = 3
x1 + 2x2 4
4x1 + 3x2 h1 = 6
x1 , x2 0
x1 + 2x2 + h2 = 4
x1 , x2,h1, h2 0
La Tabla Simplex Inicial se construye

teniendo en cuenta que en el rengln (Zj)
las variables bsicas tienen
necesariamente valores de cero.
Tenga en cuenta que en la Tabla 1:

- Variables No Bsicas: x1, x2, h1
- Variables Bsicas: A1, A2, h2
Min Z = 4x1 + x2 + MA1+

MA2
Sujeto a:
3x1 + x2 + A1 = 3
4x1 + 3x2 h1 + A2 = 6
x1 + 2x2 + h2 = 4
x1 , x2, h1, h2, A1, A2 0
Aqu n = 6 y m = 3,
siendo (n-m) = 3. Es
decir, al hacer 3
variables iguales a
cero sale una
Solucion Inicial
Inmediata Factible.
[Puede observar que
estas 3 variables no
bsicas iniciales deben
ser x1, x2, h1].

Min Z = 4x1 + x2 + MA1+ MA2
Sujeto a:
3x1 + x2 + A1 = 3
4x1 + 3x2 h1 + A2 = 6
x1 + 2x2 + h2 = 4
x1 , x2, h1, h2, A1, A2 0
Tabla 0 ?
Variables
Bsicas
Coeficientes en
la Funcin
Objetivo (Cj)
x1
x2
h1
h2
A1
A2
Solucin
(LD)
Zj
(7M-4)
(4M -1)
-M
-M
-M
9M
A1
A2
-1
h2

Tabla 0
Variables
Bsicas
Coeficientes en
la Funcin
Objetivo (Cj)
x1
x2
h1
h2
A1
A2
Solucin
(LD)
Zj
(7M-4)
(4M -1)
-M
9M
A1
A2
-1
h2
Tabla OPTIMA
Tabla 3
Coeficientes en
la Funcin
Objetivo (Cj)
X1
x2
h1
h2
A1
A2
Solucin
(LD)
-1/5
7/5-M
-M
17/5
X1
-1/5
2/5
2/5
X2
3/5
-1/5
9/5
h1
-1
Variables
Bsicas
Zj
NOTA: Las variables artificiales siempre deben ser al final No Bsicas, o

tener valor de cero, ya que solo fueron creadas para iniciar el
El Mtodo Simplex _ CASOS

ESPECIALES Observe que una Tabla
Problema de
mltiples
soluciones
Maximice Z = (5/2)X1 + X2
Sujeto a:
3X1 + 5X2
15
5X1 + 2X2 10
Tabla Final OPTIMA
Xj > 0 ; j = 1, 2
Optima de
MAXIMIZACION tiene
todos los valores del
rengln (Zj ) 0. Es
decir, el criterio funciona
a la inversa de la
Minimizacin.
Variables
Bsicas
Coeficientes en la
x1
X2
h1
h2
Solucin
(LD)
Zj
0.5
h1
3.8
-0.6
X1
0.4
0.2
Entonces aqu la variable que entra es la que variable no-bsica que

tenga el valor (Zj ) ms negativo. Observe la variable No Bsica x2 con
un valor de 0. Si esta variable entra, la funcin objetivo permanece
inmodificable.
Mltiples Soluciones
Puede encontrarse otra
solucin con el mismo valor
Problema de solucin infinita ( No

Acotada)
Minimice Z = - X1 + X2
Sujeto a:
- X1 + X2 0
- 0,5X1 + X2 1
Xj > 0 ; j = 1, 2
Tabla Inicial
Variables
Bsicas
Coeficientes en la
x1
X2
h1
h2
Solucin
(LD)
Zj
-1
h1
-1
h2
5/2
-0.5
Entra x1 pero:
Cul variable sale?
Problema sin solucin
Cuando en la Tabla Final no existe acotacin para la Variable.

El Metodo Simplex. Un Resumen - 1

Cargado por

Copyright:

Formatos disponibles

El Metodo Simplex. Un Resumen - 1

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

El Metodo Simplex. Un Resumen - 1

Cargado por

Copyright:

Formatos disponibles

Solucin de Modelos de Programacin Lineal,

explicar los aspectos geomtricos del

Todo modelo de PL, para efectos de resolverse con el Mtodo

Maximizar Z = 2x1 + 3x2 + x3

-2x1 + 3x2 + 2x3 -5

2x1 - 3x2 - 2x3 5

7x1 - 4x2 + 5x3 6

7x1 - 4x2 + 5x3 6

Maximizar Z = 2x1 3x2 + x3

Minimizar Z = -3x1 - 5x2

El Mtodo Simplex observa el conjunto de

El Mtodo Simplex inicia en el punto

Si un valor del rengln (Zj) es negativo,

Si un valor del rengln (Zj) es cero,

Para saber cual

El Simplex y las Variables Artificiales/1

Puede Lograrlo con este

Como n=4 y m=3, el Simplex

El Simplex y las Variables Artificiales/2

La Tabla Simplex Inicial se construye

Tenga en cuenta que en la Tabla 1:

Min Z = 4x1 + x2 + MA1+

El Simplex y las Variables Artificiales/3

El Simplex y las Variables Artificiales/4

NOTA: Las variables artificiales siempre deben ser al final No Bsicas, o

El Mtodo Simplex _ CASOS

Entonces aqu la variable que entra es la que variable no-bsica que

Problema de solucin infinita ( No

También podría gustarte