OPERACIONES
Simplex Revisado
Profesor: Pablo Diez Bennewitz
Escuela Ingeniera - U. del Mar
METODO SIMPLEX
Es un mtodo iterativo para la solucin de un PPL
basado en tcnicas de resolucin de un sistema de
ecuaciones lineales y criterios propios del mtodo
Es un mtodo matemtico para la resolucin
numrica de problemas de programacin lineal,
que consiste en traducir los conceptos
geomtricos de vrtices y conjunto convexo a un
concepto algebraico que se pueda llevar a
algoritmo para resolver problemas de 2, 3 o ms
variables
METODO SIMPLEX
Opera con un algoritmo eficiente, que trabaja con
una cierta cantidad de vrtices de una manera
inteligente: sus iteraciones van optimizando
sucesivamente el valor de la funcin objetivo
El mtodo cuenta con criterios para:
1) Elegir el o los vrtices a evaluar, de tal forma
de acortar el camino para alcanzar el ptimo
2) Determinar cundo se est en una solucin
ptima, de forma tal que un cambio de vrtice no
sea conveniente
METODO SIMPLEX
El mtodo simplex tiene dos modalidades
equivalentes para resolver los PPL
Mtodo
Simplex
Simplex Revisado o Matricial
Cuadro o Tableau Simplex
Observacin: todo PPL con funcin objetivo de
maximizacin se puede transformar a un PPL con
funcin objetivo de minimizacin y viceversa
Mx Z = CX
Mn Z = CX
Mn (-Z) = (-CX)
Mx (-Z) = (-CX)
PPL ESTANDAR
Para utilizar el mtodo simplex, es imprescindible
pasar del PPL original al PPL estndar
PPL Original
PPL Estndar
Optimizar Z = CX
Optimizar Z = CX
s.a. AX
X
donde:
>
=
<
>
b
0
X, C, b : vectores
Z : escalar
s.a. AX = b
X >0
b >0
A : matriz
PPL ESTANDAR
Optimizar Z = CX
s.a. AX = b
X >0
b >0
Z : escalar
X : vector de
variables de
decisin
X=
X1
X2
IR n
Xn
C : vector de coeficientes en la funcin objetivo
C = C1 C2 C3
Cn IR n
A : matriz de los coeficientes tcnicos
en
A = aij m x n
las restricciones lineales,
incluyendo
las variables de holgura
PPL ESTANDAR
Optimizar Z = CX
s.a. AX = b
X >0
b >0
A : matriz de los coeficientes
tcnicos
A = aij
mxn
n: n de variables de decisin
m: n de restricciones del PPL
b : vector de recursos, lmites
en las restricciones,
capacidad o demanda mxima
b=
b1
b2
IR m
AX = b : sistema ecuaciones lineales
bm
A b : matriz ampliada define si el SEL tiene nica
solucin, infinitas soluciones o no tiene solucin
CONSTRUCCION DE UN
PPL ESTANDAR
Implica aadir variables de holgura o de exceso,
en caso que las restricciones del PPL original
sean menor que o mayor que respectivamente
Adems, si es que el PPL original
dispone en su planteamiento de
variables no restringidas,
entonces deben incorporarse
nuevas variables, por efecto del
cambio de variable requerido
VARIABLES DE HOLGURA
Se usan cuando en el PPL original hay restricciones
en trminos < b
PPL Estndar
PPL Original
Mx Z = CX
Mx Z = CX
s.a. A[X + y] = b
s.a. AX < b
X >0
y >0
y1
b > 0
y2
IR m
y=
donde y : variables de holgura
y
VARIABLES DE EXCESO
Se usan cuando en el PPL original hay restricciones
en trminos > b
PPL Estndar
PPL Original
Mx Z = CX
Mx Z = CX
s.a. A[X w] = b
s.a. AX > b
X >0
w>0
w1
b >0
w2
IR m
w=
donde w : variables de exceso
w
VARIABLES NO RESTRINGIDAS
Se usan cuando en el PPL original hay variables no
restringidas (X IR), las que mediante un cambio
de variable se restringen a > 0
PPL Original
PPL Estndar
Mx Z = CX
s.a. AX = b
X IR
Mx Z = CX
s.a. A[ u - v ] = b
u >0
v >0
b >0
donde
u, v : variables restringidas
cambio de
variable
X=u-v
EJEMPLO
Transformar el siguiente PPL original en su
respectiva forma estndar
Mn
Z = 2X1 - 3X2 + 4X3 - X4
s.a.
3X1 + 2X2 + 6X3 + X4
- X1 + 2X2 - 3X3 - 2X4
X1 + X2 -
X3 + 2X4
3X1 + 3X2 + 5X3 + 4X4
X1, X2, X3
X
<
<
>
>
>
25
- 16
15
36
0
EJEMPLO
Solucin:
Mx -Z = -2X1 + 3X2 - 4X3 + (X4- X4) + 0X5 + 0X6 + 0X7 + 0X8
s.a.
3X1 + 2X2 + 6X3 + (X4- X4) + X5
= 25
X1 - 2X2 + 3X3 + 2(X4- X4)
- X6= 16
X1 + X2 - X3 + 2(X4- X4)
- X7
3X1 + 3X2 + 5X3 + 4(X4- X4)
= 15
- X8 = 36
X6, X7
X1, X2, X3, X4, X4, X5, X8
>
0
>
0
SOLUCION DEL SISTEMA
DE ECUACIONES LINEALES
1)
Si
Rg(A) < Rg(A b)
No Existe Solucin
No existe regin de puntos factibles de solucin
Hay un conjunto convexo vaco
SOLUCION DEL SISTEMA
DE ECUACIONES LINEALES
2) T : n de variables activas en la solucin ptima
Si Rg(A) = Rg(A b) = T
La Solucin es nica
Se asume que la matriz A es de rango mximo, es
decir que no tiene filas linealmente dependientes
Solucin
-1
X* = A b
Dem:
AX = b
A- 1AX = A- 1b
X = A- 1b
/ A- 1
SOLUCION DEL SISTEMA
DE ECUACIONES LINEALES
3) T : n de variables activas en la solucin ptima
Si Rg(A) = Rg(A b) < T
Solucin
General
donde:
X* =
XJ
XJ
Infinitas Soluciones
-1
-1
(AJ) b - (AJ) AJ XJ
XJ
XJ : vector de variables bsicas
XJ : vector de variables no bsicas
SOLUCION DEL SISTEMA
DE ECUACIONES LINEALES
Adems:
AJ : matriz de los coeficientes que acompaan a las
variables bsicas en las restricciones lineales
AJ : matriz de los coeficientes que acompaan a las
variables no bsicas en las restricciones lineales
Soluciones
Particulares
Infinitas
Soluciones
INFINITAS SOLUCIONES
Solucin Particular Factible
XJ > 0
Solucin Particular Infactible
XJ
<0
Las infinitas soluciones particulares se obtienen
a partir de los distintos valores que adoptan las
variables no bsicas
BASE
El mtodo simplex requiere trabajar con una base
de vectores en su algoritmo. As hay un vector de
variables bsicas (XJ) y un vector de variables no
bsicas (XJ )
Cada base es un vrtice
del poliedro de la regin
de puntos factibles del
PPL. El vector de
variables bsicas debe
tener m-componentes
BASE
Luego, se puede hacer la siguiente particin del
vector de variables X :
X =
XJ
m variables quedan en la base
(n - m) variables o componentes
quedan afuera de la base
XJ
donde:
XJ
X1
X2
Xm
Xm+1
XJ
=
Xn-1
REQUISITOS DEL METODO SIMPLEX
Cada combinacin de m-variables constituye una
base, la cual debe cumplir dos requisitos para ser
un vrtice del conjunto convexo subyacente
1) Que exista (AJ) - 1
>0
2) (AJ) - 1 b
O sea, que la matriz AJ
posea su inversa
XJ
Cada solucin bsica
debe ser factible
Cumplidos ambos requisitos, entonces el
vector XJ es una solucin bsica factible,
aunque no necesariamente ptima
PARTICION DEL VECTOR C
A su vez, la base de J componentes, tambin hace
una particin en el vector C
C =
Coeficientes que
acompaan a las
variables bsicas en
la funcin objetivo
CJ CJ
Coeficientes que
acompaan a las
variables no bsicas
en la funcin objetivo
PARTICION DE LA MATRIZ A
A =
A = a 1 a2 a3
AJ AJ
an-2 an-1 an
n
A es una matriz de orden m x n
A = a1 a2
A =
A =
aij m x n
am-1 am am+1 am+2
an-1 an
AJ
AJ
n-m
COTA SUPERIOR DE VERTICES
Ntese que el nmero mximo de combinaciones
para formar una base est dado por:
n
m
n
m
n!
(n - m)! m!
Es solo una cota superior: el nmero
mximo de vrtices que podra tener el
conjunto convexo de un PPL.
No obstante, no tienen por qu ser todas
bases ni soluciones del problema
SOLUCION GENERAL
Cuando el sistema de ecuaciones lineales AX = b
tiene que Rg (A) = Rg (A b) = t, donde t es el
nmero de ecuaciones lineales (l.i.), se tiene que:
Solucin
General
X =
XJ
XJ
(AJ)- 1 b - (AJ)- 1AJ XJ
XJ
La solucin general es una expresin vlida para
todos los vrtices posibles que se obtengan del
PPL, sean o no pertenecientes al conjunto convexo
SOLUCION GENERAL
X1
X3
Solo algunos de los
vrtices generados por
las intersecciones de
las restricciones ( )
pertenecen al conjunto
convexo. En cambio,
otros vrtices ()
X2
sencillamente no
pertenecen al conjunto
convexo del PPL
SOLUCION BASICA
Solucin
Bsica
X =
XJ
(AJ)- 1b
XJ
Es la misma expresin de la solucin general,
slo que en la base quedan excluidas ( n - m )
variables, en XJ, las que automticamente
adoptan un valor igual a cero
>0
Si adems ( XJ ) j
la solucin bsica
tambin es factible
METODOLOGIA DEL SIMPLEX
1) Determinar una base (de m-variables)
2) Determinar la solucin bsica
3) Verificar si la solucin bsica es o no es factible
Si es factible, pasar a 4)
Si no es factible, volver a 1) con otra base
4) Verificar si la solucin factible es o no es ptima
Si no es ptima, volver a 1) con otra base
Si es ptima, entonces se hall la solucin
CRITERIO DE OPTIMALIDAD
Z
XJ
Derivada parcial de las variables no
bsicas respecto a la funcin objetivo
Determina cunto aportaran cada una
de las variables no bsicas (XJ ) en caso
de que se incluyeran en la base
Si se establece que al menos
una variable no bsica aportara
a la funcin objetivo, entonces
debera incluirse en la base,
debera cambiarse la base
CRITERIO DE OPTIMALIDAD
EN PPL DE MAXIMIZACION
Si algn
Z
0
>
XJ j
La variable Xj s aporta
a la funcin objetivo
Por lo tanto, la solucin bsica factible no es ptima
Se debe cambiar la base, incluyendo a aquella
variable Xj que permite (
Z/
XJ ) j > 0
CRITERIO DE OPTIMALIDAD
EN PPL DE MAXIMIZACION
Si todos
Z
0
<
XJ j
Por lo tanto, la solucin
bsica factible actual es
la solucin ptima
Ninguna variable Xj
aporta a la funcin
objetivo
CRITERIO DE OPTIMALIDAD
EN PPL DE MINIMIZACION
Si todos
Z
0
>
XJ j
Por ende, la solucin
bsica factible es
tambin ptima
Ninguna variable Xj
aporta a la funcin
objetivo
CRITERIO DE OPTIMALIDAD
EN PPL DE MINIMIZACION
Si algn
Z
0
<
XJ j
La variable Xj s aporta
a la funcin objetivo
Por lo tanto, la solucin bsica factible no es ptima
Se debe cambiar la base, incluyendo a aquella
variable Xj que permite (
Z/
XJ ) j < 0 , y volver
a iterar
METODO SIMPLEX REVISADO
Resuelve un PPL a travs de operaciones
matriciales, verificando condiciones de
factibilidad y optimalidad, junto con criterios
propios para el cambio de bases
donde
XJ = (AJ)
-1
Condicin de Factibilidad: ( XJ ) > 0 ,
j
j J
La verificacin de la factibilidad es visual,
observando el vector resultante de XJ
comprobando el cumplimiento de la no negatividad
METODO SIMPLEX REVISADO
Condicin de Optimalidad:
Z = CX
Z = CJXJ + CJXJ
Z = CJ (AJ)- 1b - (AJ) - 1AJXJ + CJXJ
-1
-1
Z = CJ (AJ) b + CJXJ - CJ (AJ) AJXJ
Z
XJ
= CJ - CJ (AJ)- 1 AJ
Z
XJ
Necesariamente hay
que hacer todas las
multiplicaciones de
matrices
CRITERIO DE ENTRADA A LA BASE
METODO SIMPLEX REVISADO
Mx
Z
XJ j
jJ
ssi
Z
XJ
>0
En problemas con funcin objetivo de maximizacin
CRITERIO DE SALIDA A LA BASE
METODO SIMPLEX REVISADO
Mn
( (AJ)- 1 b )j
( (AJ)- 1a (e) )
>0
En problemas con funcin objetivo de maximizacin
donde:
(e) Vector columna de los coeficientes en
A de la variable que entra a la base
Simplex revisado requiere realizar primero el criterio
de entrada y, a continuacin, el criterio de salida
TEOREMA FUNDAMENTAL
DE LA PROGRAMACION LINEAL
Si el PPL Maximizar Z = CX admite a lo menos una
solucin factible, luego
s.a. AX = b dicho problema admite
X >0
a lo menos una
solucin bsica factible
Si adems, el anterior PPL admite solucin ptima,
entonces hay al menos una solucin bsica factible
Conclusin: hay que concentrarse slo en las soluciones bsicas factibles, ya que encontrando entre
ellas el ptimo, la solucin ptima es inmediata
