PUCESA

El Metodo Simplex
INTEGRANTES:
Aldas Eduardo
Cspedes Josu
Meja Cristian
Salazar Byron
Sisalema Andres

PROGRAMACION LINEAL MTODO SIMPLEX

Los problemas reales de programacin lineal
generalmente tienen variables de decisin y muchas
restricciones. Tales problemas no pueden ser resueltos
grficamente. Se usan algoritmos tales como el simples.
El mtodo simplex es un procedimiento iterativo que
progresivamente permite obtener una solucin ptima
para los problemas de programacin lineal.
Existen numerosos programas tanto para computadoras
centrales como para personales. Aunque el mtodo
simples es especialmente til en problemas de gran
escala (resueltos con una computadora).

Conversin de modelos de PL a la
Forma Estndar
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 no restringida, x2 0, x3 0

Conversin de modelos de PL a la
Forma Estndar
Maximizar Z = 2x1 + 3x2 + x3

Maximizar Z = 2x1 + 3x2 + x3

Sujeto a: x1 + x2 + x3 = 10

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 no restringida, x2 0, x3 0

x1 no restringida, x2 0, x3 0

2
Maximizar Z = 2x1 3x2 + x3
Sujeto a: x1 x2 + x3 = 10

Maximizar Z = 2x1 + 3x2 + x3

3a

Sujeto a: x1 + x2 + x3 = 10

2x1 + 3x2 - 2x3 S1 = 5

2x1 - 3x2 - 2x3 S1 = 5

7x1 + 4x2 + 5x3 + S2 = 6

7x1 - 4x2 + 5x3 + S2 = 6

x1 - 4x2 + 3x3 S3 = 8
x1 no restringida, x2 0, x3 0, S10,
S20, S30

x2=-x2

x1 +Juan
4x2Jos
+ 3x
[Link].
3 B.,
3 = 8
Bravo
x1 no restringida, x2 0, x3 0, S10,
S20, S30

Conversin de modelos de PL a la
Forma Estndar

/3

Maximizar Z = 2x1 3x2 + x3

Sujeto a: x1 x2 + x3 = 10
2x1 + 3x2 - 2x3 S1 = 5
7x1 + 4x2 + 5x3 + S2 = 6

x1 - 4x2 + 3x3 S3 = 8
x1 no restringida, x2 0, x3 0, S10,
S20, S30

3b

x1= x1 x1
Maximizar Z = 2x1 2x1 - 3x2 + x3

Forma Estndar donde:

S1 y S3 Variables de Exceso

S2 Variable de Holgura

Sujeto a: x1 x1 x2 + x3 = 10

2x1 2x1 + 3x2 - 2x3 S1 = 5

7x1 7x1 + 4x2 + 5x3 + S2 = 6
x1 x1 - 4x2 + 3x3 S3 = 8
x1 0, x1 0, x2Juan
0,Jos
x3 Bravo
0, SB.,
S 0,
10,
[Link].2
S30

Soluciones Bsicas
EJEMPLO: Minimizar Z = -3x1 - 5x2
Sujeto a:

Minimizar Z = -3x1 - 5x2

Forma

x1 4

Estndar

2x2 12

Sujeto a: x1 + S1 = 4
2x2 + S2 = 12

3x1 + 2x2 18

3x1 + 2x2 + S3 = 18

x1 , x2 0

x1 , x2 , S1, S2, S3 0

x1

x2

s1

s2

s3

12

18

-9

-6

-2

12

12

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
Juan Jos
B., [Link]. que
consistentes.
LasBravo
soluciones
logra de esta manera se llaman
Soluciones Bsicas.

Soluciones Bsicas Factibles (SBF)

x1

x2

s1

s2

s3

P1

12

18

Fact

P2

Fact

P3

-9

NO

P4

-6

NO

P5

Fact

P6

Fact

P7

-2

12

NO

P8

12

Fact

Los puntos resaltados con verde representan

Soluciones Bsicas Factibles ya que cumplen con
todas las restricciones. Los dems puntos violan
restricciones de no-negatividad. El Mtodo
Simplex nicamente considera para su anlisis las
SBF.

Simplex Tabular
Minimizar Z = -3x1 - 5x2

/1

El Mtodo Simplex inicia en el punto

P1, que corresponde a la Tabla 1.

Sujeto a: x1 + S1 = 4
2x2 + S2 = 12
3x1 + 2x2 + S3 = 18

P1

x1 , x2 , S1, S2, S3 0

x1

x2

s1

s2

s3

12

18

Variables
No Bsicas

Variables
Bsicas

Tabla 1
Variables
Bsicas

Coeficientes en la
Funcin Objetivo
(Cj)

x1

x2

S1

S2

S3

Solucin
(R.H.S.)

S1

S2

12

S3

18

Zj - Cj

Coeficientes de
las restricciones

Juan Jos Bravo B., [Link].

Valor Objetivo

Simplex Tabular
Ya obtenida la Tabla 1, el
Mtodo Simplex se pregunta:
La Tabla 1 es ptima? (es
decir, el punto P1 es
ptimo?).
Criterio de Parada
Si todos los valores del
rengln (Zj Cj) 0
entonces la Tabla es
ptima

Debe ingresar a la
solucin la Variable
No Basica que tenga
el mayor valor positivo
en el rengln (Zj Cj)

/2

Para ello observamos el

rengln (Zj Cj), que da
slo informacion de las
Variables No Basicas

Para Minimizacin
Si un valor del rengln (Zj Cj) es positivo,
indica que al darle valores a la variable no
basica respectiva, mejora la funcion
objetivo.
Si un valor del rengln (Zj Cj) es negativo,
indica que al darle valores a la variable no
basica respectiva empeora la funcion
objetivo.

Criterio de Entrada

Simplex Tabular

/3

Columna entrante

Tabla 1
Variables
Bsicas

Coeficientes en la
Funcin Objetivo
(Cj)

x1

x2

S1

S2

S3

Solucin
(R.H.S.)

Razn
Mnima
()

S1

S2

12

12/2 = 6

S3

18

18/2 = 9

Zj - Cj

sale S2

Para darle valores a 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 ()

Se calcula dividiendo
el elemento de la
columna R.H.S con el
elemento de la
columna entrante,
siempre que el
elemento de esta
ltima columna sea
positivo.

Simplex Tabular /5

Tabla 2
Variable
s Bsicas

Coeficientes en la
Funcin Objetivo
(Cj)

x1

X2

S1

S2

S3

Solucin
(R.H.S.)

Razn

S1

4/1 =4

x2

-5

1/2

S3

-1

6/3 =2

-5/2

-30

Zj - Cj

P2

x1

x2

s1

s2

s3

Fact

Tabla 3
Variables
Bsicas

Coeficientes en la
Funcin Objetivo (Cj)

x1

X2

S1

S2

S3

Solucin
(R.H.S.)

S1

1/3

-1/3

x2

-5

1/2

x1

-3

-1/3

1-3

-3/2

-1

-36

Zj - Cj

P5

x1

x2

s1

s2

s3

Fact

Tabla
OPTIMA

El Simplex y las Variables Artificiales

Minimizar Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 3

Estandarizacion
Tradicional

/1

Minimizar Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 3

4x1 + 3x2 6

4x1 + 3x2 S2 = 6

x1 + 2x2 4

x1 + 2x2 + S3 = 4

x1 , x2 0

x1 , x2,S2, S3 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 iniciar sin problemas
con las variables de holgura.

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 .
Jos Bravo estos
B., [Link].
El SimplexJuan
soluciona
inconvenientes de arranque creando
Variables Artificiales.

El Simplex y las Variables Artificiales

/2

Min Z = 4x1 + x2

Min Z = 4x1 + x2

Min Z = 4x1 + x2 + MR1+ MR2

Sujeto a: 3x1 + x2 = 3

Sujeto a:

Sujeto a:

4x1 + 3x2 6

3x1 + x2 = 3

3x1 + x2 + R1 = 3

x1 + 2x2 4

4x1 + 3x2 S2 = 6

4x1 + 3x2 S2 + R2 = 6

x1 , x2 0

x1 + 2x2 + S3 = 4

x1 + 2x2 + S3 = 4

x1 , x2,S2, S3 0

x1 , x2, S2, S3, R1, R2 0

La Tabla Simplex Inicial se construye teniendo

en cuenta que en el rengln (Zj Cj) las
variables bsicas tienen necesariamente valores
de cero.

Tenga en cuenta que en la Tabla 1:

- Variables No Bsicas: x1, x2, s2

- Variables Bsicas: R1, R2, S3

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
Jos Bravo B., [Link].
x1, xJuan
2, s2].

El Simplex y las Variables Artificiales

/3

De la primera y segunda restriccin:

Min Z = 4x1 + x2 + MR1+ MR2

R1 = 3 - 3x1 - x2

Sujeto a:

R2 = 6 - 4x1 - 3x2 + S2

3x1 + x2 + R1 = 3
4x1 + 3x2 S2 + R2 = 6

Transformacin necesaria en la Funcin

Objetivo:

x1 + 2x2 + S3 = 4
x1 , x2, S2, S3, R1, R2 0

Min Z = 4x1 + x2 + M(3 - 3x1 - x2) +

M(6 - 4x1 - 3x2 + S2)
Min Z = (4 - 7M) x1 - (4M - 1)x2 + MS2 + 9M

Variables
Bsicas

Coeficientes en la
Funcin Objetivo
(Cj)

x1

x2

S2

S3

R1

R2

Solucin
(R.H.S.)

R1

R2

-1

S3

- (4-7M)

(4M -1)

-M

9M

Zj - Cj

Juan Jos Bravo B., [Link].

El Simplex y las Variables Artificiales

/4

Tabla 1
Variables
Bsicas

Coeficientes en la
Funcin Objetivo
(Cj)

x1

x2

S2

S3

R1

R2

Solucin
(R.H.S.)

R1

R2

-1

S3

- (4-7M)

(4M -1)

-M

9M

Zj - Cj

Tabla OPTIMA

Tabla 4
Variables
Bsicas

Coeficientes en la
Funcin Objetivo
(Cj)

X1

x2

S2

S3

R1

R2

Solucin
(R.H.S.)

X1

-1/5

2/5

2/5

X2

3/5

-1/5

9/5

S2

-1

-1/5

7/5-M

-M

17/5

Zj - Cj

Juan Jos Bravo B., [Link].

NOTA: Las variables artificiales siempre deben ser al final No Bsicas, o tener valor de
cero, ya que solo fueron creadas para arrancar el procedimiento.