El mtodo Simplex
Los pasos que debemos seguir para encontrar la
solucin de un modelo de programacin lineal a travs
del Mtodo Simplex, son:
oEstandarizacin del modelo.
oConstruir la tabla inicial Simplex
oResolver el modelo
1.- Estandarizacin del modelo de PL
El proceso de estandarizacin del modelo de PL
consiste en la construccin de un conjunto de
ecuaciones, necesarias para el anlisis que har el
mtodo Simplex.
Caso 1: Restricciones de exigencias
Corresponden a inecuaciones de la forma , las que se convierten en
igualdades mediante la adicin de una variable suelta, llamada de
Holgura, y que representa la cantidad de insumo que queda ocioso en
un sistema de produccin.
Ejemplo:
0.05X1 + 0.05 X2 + S1 = 1100; donde S1 0
Caso 2: Restricciones de exigencias
Corresponden a inecuaciones de la forma y que se convierten en
ecuaciones mediante la sustraccin de una variables suelta, llamada
de excedente, y representa la cantidad de sobrecumplimiento a un
mnimo exigido.
Ejemplo:
X1 - S4 = 6000; donde tambin S4 0
FO (Max) Z = 18.50 X1 + 20 X2 (Utilidad)
s.a 0.05 X1 + 0.05 X2 1100 (tn. de Nitrato)
0.05 X1 + 0.10 X2 1800 (tn. de Fosfato)
0.10 X1 + 0.05 X2 2000 (tn. de Potasio)
X1 6000 (demanda mnima H-25)
X 1, X 2 0
FO (Max) Z = 18.50 X1 + 20 X2 +0S1 + 0S2 + 0S3 + 0S4 - MXa (Utilidad)
s.a 0.05 X1 + 0.05 X2 + S1 = 1100
0.05 X1 + 0.10 X2 + S2 = 1800
0.10 X1 + 0.05 X2 + S3 = 2000
X1 - S4 + Xa = 6000
X1, X2, S1, S2, S3, S4, Xa 0
2.- La tabla Simplex
El algoritmo Simplex hace uso del lgebra matricial para
desarrollar la solucin a un problema de PL.
Para ello necesitamos el uso de una tabla donde se acondicionan
los valores constantes del modelo.
Usaremos una tabla simplificada, la cual permitir mayor
agilidad en los clculos. Dicha tabla tiene el siguiente esquema.
Cj
X1
X2
bi
S1
0.05
0.05
1100
S2
0.05
0.10
1800
S3
0.10
0.05
2000
18.50
20
3.- Solucin del Modelo
Variable Entrante y Variable Saliente
En caso de no ser ptima la solucin que plantea la tabla, la base de la
solucin (conjunto de VB) deber transformarse, haciendo que una de las
VNB entre en la base y una de las VB salga de ella. La primera se llamar
variable entrante y la segunda variable saliente.
El proceso que suele utilizarse para determinar que variable habr que incluir
en la base, se resume as:
Paso 1: Seleccin de la variable entrante
La seleccin de la variable entrante a la base parte de los valores de la fila
de indicadores en la tabla. Suponiendo que se ha examinado ese rengln y se
encuentran valores no negativos, se elige la variable que tenga el mayor valor
positivo.
La columna asociada con esta variable se denomina columna pivote (columna
entrante). La variable elegida es la variable entrante.
Si en la fila de indicadores se presentan valores iguales, no negativos, el
empate se rompe arbitrariamente.
Paso 2: Seleccin de la variable que sale
La variable que sale de la base se elige dividiendo las
cantidades de la columna solucin (bi) entre los coeficientes
positivos de la columna pivote, fila a fila. Se elige la fila que
tenga el menor cociente no negativo y esa fila se llamar fila
pivote y su VB asociada ser la que salga de la base.
El elemento situado en la interseccin de la columna pivote y la
fila pivote se llama elemento pivote.
Paso 3: Bsqueda de la nueva solucin (Operacin Pivote)
La operacin pivote es un procedimiento que permite encontrar
cuando es posible, una solucin bsica ms atractiva a partir de
la que presenta la tabla. Por este procedimiento se obtiene una
nueva tabla en la que se puede leer la nueva solucin y el valor
posiblemente mejorado de la FO.
Los cuatro pasos del proceso son:
1. Invertir el elemento pivote (1/pivote).
2. Dividir los otros elementos de la fila pivote entre el pivote.
3. Dividir los otros elementos de la columna pivote entre el
pivote cambindole de signo al cociente.
4. Calcular el resto de los elementos de la tabla mediante la
siguiente frmula:
Nuevo Valor
(viejo valor) (pivote) - (elemement o de columna pivote)(elemento de fila pivote)
pivote
a11
(0.05)(0.10) (0.05)(0.05)
0.025
0.10
a31
(0.10)(0.10) (0.05)(0.05)
0.075
0.10
b1
(1,100)(0.10) (0.05)(1,800)
200
0.10
b3
(2,000)(0.10) (0.05)(1,800)
1,100
0.10
I1
(18.50)(0.10) (0.05)(20)
8.5
0.10
Variable
entrante
Variabl
e
salient
e
X1
X2
X2
S1
S2
S3
S4
Soluci
n
18.5
20.0
S1
0.05
0.05
1100
S2
S2
0.05
0.05
0.10
0.10
0.10
00
0
0
1800
1800
S3
0.10
0.05
2000
S4
1.00
0.00
-1
6000
0
Pivote
1
1
Variable
entrante
Variabl
e
salient
e
S2
S3
S4
Soluci
n
-200
360000
0.5
0.5
0.00
0.00
0.00
0.00
200
8000
18000
0.00
0.5
1100
-1
6000
X1
X1
X2
8.50
0.00
S1
S1
0.025
0.025
X2
0.05
0.10
S3
0.075
S4
1.00
1
S1
0
Pivote
0.00
1
0.00
1
Cj
S1
S2
bi
18.5
X1
40
-20
8000
20
X2
-20
20
14000
S3
-3
500
-340
-30
428000
La nueva tabla representa la solucin ptima al
problema pues sus indicadores son todos negativos, lo
que informa que la solucin encontrada no puede ser
mejorada.
Paso 4: Interpretacin de la tabla
La solucin en una tabla Simplex se encuentra en la
columna bi.