PL4 METODO SIMPLEX

Vista previa del material en texto

Gestión de 
Investigación de 
Operaciones
Profesor: Pedro Peña Carter
Ingeniero Comercial UTFSM
MBA IEDE España
MFC Universitat de Barcelona
Método Simplex
En lo que sigue consideremos el siguiente problema de 
programación lineal en su forma estándar.
Min C1 x1 + C2 x2 + ... + Cn xn
sa A11 x1 + A12 x2 + ... + A1n xn = b1
A21 x1 + A22 x2 + ... + A2n xn = b2
... ... ...
Am1 x1 + Am2 x2 + ... + Amn xn = bm
xi  0, i = 1, 2, ..., n y m  n
Método Simplex
Matricialmente escrito como:
Min cTx
s.a. A x = b
x  0
No existe pérdida de la generalidad al suponer que 
un problema viene dado en la forma estándar. En 
efecto, si tuviésemos el siguiente problema:
Método Simplex
P) Max 9X1 + 2X2 + 5X3
s.a. 4X1 + 3X2 + 6X3  50
X1 + 2X2 - 3X3  8
2X1 – 4X2 + X3 = 5
X1 , X2 , X3  0
Es posible reformular de manera equivalente el 
problema anterior usando que:
Método Simplex
Siempre es posible llevar un problema de maximización a
uno de minimización.
Cada restricción del tipo  puede ser llevada a una
ecuación de igualdad usando una (nueva) variable de
holgura no negativa, con un coeficiente nulo en la función
objetivo.
De igual modo, cada restricción del tipo  puede ser
llevada a una ecuación de igualdad usando una (nueva)
variable de exceso no negativa.
En el caso de igualdades asumir variable libre positiva.
Método Simplex
El problema P) puede ser escrito de
manera equivalente como (Formato
Estándar):
Min - 9x1 - 2x2 - 5x3 + 0S4 + 0S5 + 0S6
sa: 4x1 + 3x2 + 6x3 +S4 = 50
x1 + 2x2 - 3x3 + S5 = 8
2x1 - 4x2 + x3 +S6 = 5
xi  0, i=1,2,3,4,5,6.
Método Simplex
La búsqueda de la solución óptima se 
restringe a encontrar un vértice óptimo. Cada 
vértice del conjunto de las restricciones del 
problema, esto es del conjunto 
{ x / A x = b, x  0 }, corresponde en 
términos algebraicos a una solución básica 
factible del sistema Ax = b.
Método Simplex
Esta solución básica factible, corresponde 
a su vez a aquellas soluciones que resultan 
de resolver el sistema para exactamente m 
variables, fijando las restantes n - m en cero, 
llamadas respectivamente variables básicas y 
no-básicas, que además deben satisfacer 
condiciones de no-negatividad.
Método Simplex
Teorema Fundamental de la Programación 
Lineal:
Cada problema de PL en su forma estándar cumple con
las siguientes tres propiedades:
Si el problema no tiene solución óptima entonces es
no-acotado o infactible.
Si tiene una solución factible, tiene una solución
básica factible.
Si el problema tiene solución óptima, tiene una
solución básica factible óptima.
Método Simplex
En lo que sigue suponemos que Ran(A) = m
y que por lo tanto existe una matriz invertible 
B de m x m, que sin pérdida de la generalidad 
asumimos corresponde a aquella que definen 
las m primeras columnas de A 
Lo anterior induce una partición de las 
variables y parámetros del modelo como lo 
muestra la siguiente diapositiva:
Método Simplex
mB DA =
n
m n - m
B : Es llamada una 
matriz de base
XB : Variables básicas.
XD : Variables no básicas.
CB : Costos básicos.
CD : Costos no básicos.
X = 
X1
Xn
= 
XB
XD
m
n - m
CB
CD
m
n - m
C = 
Método Simplex
De este modo, el sistema AX = b equivale a:
Donde esta última expresión da el valor de la 
solución básica asociado a la actual base B, en 
este caso asociada a las m primeras variables
DB
DB
DB
xDBbBx
xDbBx
bxDBx
11  


Método Simplex
Criterio de optimalidad:
 
  DTBTDTB
D
T
DD
T
B
D
T
DB
T
B
T
xDBccbBc
xcxDBbBc
xcxcxc
11
11





valor 
actual 
función 
objetivo
vector de 
costos 
reducidos.
Método Simplex
La ecuación que define cada uno de los costos 
reducidos es: 
Donde j es el índice de variable no-básica y Aj la 
respectiva columna en A de esa variable.
La actual solución básica factible es óptima 
ssi rj  0 j, En caso contrario, existe una variable 
no básica XP con costo reducido negativo, que entra 
a la nueva base y que permite reducir el valor de la 
función objetivo respecto de la actual solución.
j
1T
Bjj ABccr

Método Simplex
Para decidir quién deja la base, es necesario calcular el 
mayor valor que puede tomar la variable entrante que 
garantiza la factibilidad de la nueva solución básica. Con:
y se debe calcular:





























 
pm
p
p
p
m y
y
y
AB
y
y
y
bB
2
1
1
0
02
01
1
baseladejax0y/
y
y
Min
y
y
kip
ip
0i
kp
0k 







Método Simplex
Ejemplo. 
Resolver el siguiente problema de P.L.
Máx 40x + 60y
S.A.: 2x + y  70
x + y  40
x + 3y  90
x , y  0
Método Simplex
Primeramente, se deben agregar 3 variables de
holgura ( introducimos S1 , S2 , S3)
Min - 40x – 60y
sa: 2x + y + S1 = 70
x + y + S2 = 40
x + 3y + S3 = 90
x , y  0 , Si  0, i = 1, 2 y 3.
Método Simplex
X Y S1 S2 S3 REC
2 1 1 0 0 70
1 1 0 1 0 40
1 3 0 0 1 90
-40 -60 0 0 0 0
30
3
90
,
1
40
,
1
70






Min













0
0
Y
X
X D
Primero llevo la información del formato estándar al
tablau inicial
Entra Y a la base, sale el
esto nos indica que sale S3. En este caso el 3, que es la
intersección de fila y columna es el pivote. Se debe
multiplicar por 1/3 dicha fila.






















90
40
70
3
2
1
S
S
S
X B
Método Simplex
X Y S1 S2 S3 REC
5/3 0 1 0 -1/3 40
2/3 0 0 1 -1/3 10
1/3 1 0 0 1/3 30
-20 0 0 0 20 1,800
Lo que resulta será:
Luego se debe dejar ceros sobre el 1 y bajo el. Por lo cual, se
utilizarán operaciones elementales de matrices para lograr el
objetivo. En este caso, se debe multiplicar la Fila 3 por -1 y sumar a
la Fila 2 y 1 respectivamente, además se debe multiplicar la Fila 3
por 60 y sumar a la fila 4
X Y S1 S2 S3 REC
- 1 - - - -
- 1 - - - -
1/3 1 0 0 1/3 30
- -60 - - - -
Método Simplex
15
)3/1(
30
,
)3/2(
10
,
)3/5(
40







Min
Luego debo continuar porque aún hay un costos
reducido negativo.
Entra X a la base, sale el
esto nos indica que sale S2. En este caso el 2/3, que es
la intersección de fila y columna es el pivote. Se debe
multiplicar por 3/2 dicha fila.
X Y S1 S2 S3 REC
5/3 0 1 0 -1/3 40
2/3 0 0 1 -1/3 10
1/3 1 0 0 1/3 30
-20 0 0 0 20 1,800













0
0
3S
X
X D






















30
10
40
2
1
Y
S
S
X B
Método Simplex
X Y S1 S2 S3 REC
5/3 - - - - -
1 0 0 3/2 -1/2 15
1/3 - - - - -
-20 - - - - -
Lo que resulta será:
Luego se debe dejar ceros sobre el 1 y bajo el. Por lo cual, se
utilizarán operaciones elementales de matrices para lograr el
objetivo. En este caso, se debe multiplicar la Fila 2 por -5/3 y sumar
a la Fila 1, luego se debe multiplicar la Fila 2 por -1/3 y sumar a la
Fila 3, además se debe multiplicar la Fila 2 por 20 y sumar a la fila 4
X Y S1 S2 S3 REC
0 0 1 -5/2 1/2 15
1 0 0 3/2 -1/2 15
0 1 0 -1/2 1/2 25
0 0 0 30 10 2,100













0
0
3
2
S
S
X D






















25
15
151
Y
X
S
X B
Método Simplex
Resumen del Método Simplex:
Paso 0 : Escribir el problema de programación lineal
en su forma estándar.
Paso 1 : Escoger una solución básica factible inicial.
Paso 2 : Escoger una variable no-básica con costo
reducido negativo que determina la variable entrante
y seguir al Paso 3. Si todos los costos reducidos son
mayores o iguales que cero , parar ya que la actual
solución básica factible es óptima.
Método Simplex
Resumen del Método Simplex:
Paso 3 : Calcular el criterio de factibilidad que
determina que variable deja la base. Si todos los
cuocientes son negativos el problema es no-
acotado, parar.
Paso 4 : Actualizar la tabla de modo de despejar el
valorde las nuevas variables básicas, los costos
reducidos y el valor de la función objetivo. Volver al
Paso 2.
Método Simplex
Método Simplex de dos Fases.
Fase 1: Se considera un problema auxiliar que
resulta de agregar tantas variables auxiliares a las
restricciones del problema, de modo de obtener una
solución básica factible. Resolver por Simplex un
nuevo problema que considera como función
objetivo la suma de las variables auxiliares. Si el
valor óptimo es cero ir a la Fase 2. En caso
contrario, no existe solución factible.
Método Simplex
Método Simplex de dos Fases.
Fase 2: Resolver por Simplex el problema original a
partir de la solución básica factible inicial hallada en
la Fase1.
Ejemplo: Máx 2x1 + x2
s.a.: 10x1 + 10x2  9
10x1 + 5x2  1
x1,x2  0
Método Simplex
Método Simplex de dos Fases.
Se debe agregar una variable de holgura (S1) y
una variable de exceso (S2), y llevarlo a su
forma estándar.
Min -2x1 - x2
s.a.: 10x1 + 10x2 +S1 = 9
10x1 + 5x2 - S2 = 1
x1,x2, S1, S2  0
Método Simplex
Método Simplex de dos Fases.
Aplicamos Simplex de dos Fases :
Fase 1: Min S3
s.a.: 10x1 + 10x2 + S1 = 9
10x1 + 5x2 - S2 + S3 = 1
x1,x2, S1, S2, S3 0
Método Simplex
X1 X2 S1 S2 S3 REC
10 10 1 0 0 9
10 5 0 -1 1 1
0 0 0 0 1 1
X1 X2 S1 S2 S3 REC
10 10 1 0 0 9
10 5 0 -1 1 1
-10 -5 0 1 0 -1
En este caso, la variable que esta en la base tiene un 1 (Color Calipso) 
cuando debería haber un cero, por lo cual, se debe multiplicar la fila 2 
por -1 y sumar a la tercera fila. Con esto la tabla quedará:
Entra X a la base, sale el
esto nos indica que sale S3. En este caso el 10, que es la
intersección de fila y columna es el pivote. Se debe multiplicar por
1/10 dicha fila.
10/1
10
1
,
10
9






Min
Método Simplex
X1 X2 S1 S2 S3 REC
10 - - - - -
1 1/2 0 -1/10 1/10 1/10
-10 -5 - - - -
Lo que resulta será:
Luego se debe dejar ceros sobre el 1 y bajo el. Por lo cual, se
utilizarán operaciones elementales de matrices para lograr el
objetivo. En este caso, se debe multiplicar la Fila 2 por -10 y sumar a
la Fila 1 respectivamente, además se debe multiplicar la Fila 2 por
10 y sumar a la fila 3
X1 X2 S1 S2 S3 REC
0 5 1 1 -1 8
1 1/2 0 -1/10 1/10 1/10
0 0 0 0 1 0
Método Simplex
X1 X2 S1 S2 S3
0 5 1 1 8
1 1/2 0 -1/10 1/10
-2 -1 0 0 0
Una vez obtenida la solución óptima del problema en la Fase 1, con 
valor óptimo 0, tomamos X1 y S1 como variables básicas iniciales para 
la Fase 2.
En este caso, la variable que esta en la base tiene un -2 (Color Calipso) cuando 
debería haber un cero, por lo cual, se debe multiplicar la fila 2 por 1 y sumar a 
la tercera fila. Con esto la tabla quedará:
X1 X2 S1 S2 REC
0 5 1 1 8
1 1/2 0 -1/10 1/10
0 0 0 -1/5 1/5
Método Simplex
X1 X2 S1 S2 REC
0 5 1 1 8
1 1/2 0 -1/10 1/10
0 0 0 -1/5 1/5
8
)10/1(
)10/1(
,
1
8








MinEntra Y a la base, sale el
esto nos indica que sale S2. En este caso el 1, que es la intersección
de fila y columna es el pivote.
Lo que resulta será:
X1 X2 S1 S2 REC
0 5 1 1 8
- - - -1/10 -
- - - -1/5 -
Método Simplex
Luego se debe dejar ceros sobre el 1 y bajo el. Por lo
cual, se utilizarán operaciones elementales de matrices
para lograr el objetivo. En este caso, se debe multiplicar
la Fila 1 por 1/10 y sumar a la Fila 2 respectivamente,
además se debe multiplicar la Fila 1 por 1/5 y sumar a la
fila 3.
X1 X2 S1 S2 REC
0 5 1 1 8
1 1 1/10 0 9/10
0 1 1/5 0 9/5













0
0
1
2
S
X
X D













8
10/9
2
1
S
X
X B