30119_MetodoSimplex

Vista previa del material en texto

UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 1 
 
MÉTODO SIMPLEX. 
 
 
 
 
 
El método simplex es un método algebraico y algorítmico diseñado para la solución de 
programas lineales, este se caracteriza por ser un algoritmo iterativo en el que cada 
iteración contribuye a mejorar la solución anterior. 
 
 
 
 
 
La aplicación del método simplex requiere de una solución de partida la que se denomina 
solución básica inicial sobre la cual comienzan a realizarse las iteraciones, las que se 
detienen cuando se alcanza a la solución optima. 
 
 
El algoritmo del simplex esta diseñado sobre la base que el objetivo del programa es la 
maximización y su estructura esta diseñada de manera tal que este utilizara la menor 
cantidad de iteraciones requeridas para obtener una solución optima. 
 Este método esta generado sobre la base del álgebra matricial (asociada a la solución de 
sistema de ecuaciones lineales) razón por la cual la aplicación del método requiere como 
primer requisito que todas las restricciones asociadas al programa estén expresadas como 
igualdades, es decir, que el programa lineal sea estandarizado. 
 
La estandarización de un programa lineal es el proceso de transformación de las 
restricciones expresadas como desigualdades a igualdades, tal proceso requiere de la 
incorporación de las nuevas variables al programa, tanto en las restricciones como en la 
función objetivo, estas variables incorporadas en el programa como nuevas variables de 
decisión pueden ser holguras o superfluas. 
 
Variable de Holgura: es la variable de decisión que se incorpora al programa con el objeto 
de transformar en igual aquella restricción dada por la relación ≤ . 
 
jkk bxaxaxa ≤+++ 1212111 ....................
jkk bxaxaxa
 
 
=Η++++ 1212111 .................... 
 
 
La variable de holgura cuantifica el desperdicio del recurso es decir aquella parte del 
recurso no utilizada (recurso ocioso), las variables de holgura están relacionada a las 
restricciones de recursos. 
 
Variable Superfluas: es la variable de decisión que se incorpora al programa con el objeto 
de transformar en igualdad a una restricción dada por la relación . ≥
 
jkk bxaxaxa ≥+++ 1212111 .................... 
jkk bSxaxaxa =−+++ 1212111 .................... 
La variable superflua cuantifica la escasez de un recurso, o bien el excedente producido por 
las actividades, asimismo las variables superfluas están asociadas a las restricciones de 
beneficios. 
 
El obtener información de los recursos no utilizados o de la magnitud de la escasez, no 
aporta valor económico al beneficio, por lo que la incorporación de las variables de holgura 
y superfluas en el resultado económico, considera una contribución económica unitaria 
nula. 
 
OPT Z = SXCXCXC KK 00...........2211 +Η++++ 
 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 2 
 
 
 
 
 
Además, es imposible que el desperdicio sea una magnitud negativa, puesto que no se 
puede utilizar más que el disponible de un recurso, por lo tanto, las variables de holgura 
deben satisfacer el principio de no negatividad. 
 
 
 
H 0 ≥
 
Sin embargo, la utilización de variables superfluas podría transgredir el principio de no 
negatividad en algunos puntos, situación que obliga a considerar otro tipo de variables en el 
programa, éstas son las variables artificiales. 
 
 
 
Variables artificiales: como su nombre lo indica las variables artificiales son variables que 
no tienen ninguna connotación real dentro del programa, es decir, carecen de sentido 
práctico y por lo tanto de interpretación. 
 
La incorporación de variables artificiales en un programa lineal persigue dos objetivos: 
 
1. Salvaguardar el principio de no negatividad cuando se han utilizado variables 
superfluas. 
 
2. Facilitar la búsqueda de una solución básica inicial. 
 
Dado que las variables artificiales no tienen representación física en el programa, estas no 
pueden formar parte del conjunto solución (BASE), ya que no es posible realizar una 
actividad que no existe. En consecuencia, para evitar que la solución contenga variables 
artificiales, es decir, para que las variables artificiales que son básicas dejen de serlo y por 
lo tanto dejen de pertenecer al conjunto solución, su uso es penalizado a través de una 
cantidad positiva muy grande (genéricamente llamada M) si el objetivo es minimizar o una 
cantidad negativa muy grande (-M) si el objetivo es maximizar. Estas multas tienen por 
objetivo asegurar que mientras la solución contenga una variable artificial, el objetivo no 
será logrado, por lo que la incorporación de las variables artificiales debe considerar estas 
multas como contribución económica al ser incorporadas en la función objetivo, lo que 
asegura su pronta eliminación de la base. 
Por lo tanto, las variables artificiales deben ser utilizadas en restricciones de la forma ≥ 
(donde cumple con los 2 roles anteriormente identificados) y en restricciones de igualdad, 
donde sólo cumple el segundo rol. 
 
Las variables artificiales se asumen siempre como no negativas y su utilización asegura que 
las variables superfluas también satisfagan el principio de no negatividad, para cualquier 
combinación de valores particulares de las variables de decisión. 
 
A 0 ≥
S 0 ≥
 
Así por ejemplo para el programa: 
 
OPT Z = 1
1
* XC
k
i
i∑
=
 S.T.: 
1
1
1 bxa i
k
i
i ≤∑
=
 
2
1
2 bxa i
k
i
i =∑
=
 
3
1
3 bxa i
k
i
i ≥∑
=
 
0≥ix 
 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 3 
 
 
 
 
Su forma estándar si el óptimo se refiere a maximizar es: 
 
MÁX. Z = 3321
1
00* MASMAXC i
k
i
i −+−Η+∑
=
 
S.T.: 
11
1
1 bxa i
k
i
i =Η+∑
=
 
 
22
1
2 bAxa i
k
i
i =+∑
=
 
333
1
3 bASxa i
k
i
i =+−∑
=
 
0A;A;S;H;X 3231i ≥
3321
1
00 MASMAHXC i
k
i
i ++++∑
=
⎟⎟
⎠
⎞
⎝Ca
C
 
 
Sin embargo, si el óptimo se refiere a minimizar, entonces la forma estándar del P.L. 
mantiene las restricciones como en el caso anterior, pero la función objetivo queda 
expresada por: 
 
MIN Z = 
 
 
Así entonces, un programa lineal estándar representado matricialmente queda: 
 
OPT Z = (C’) t * X’ 
S.T. 
A’ * X’ = B 
X’ 0≥
Donde: 
 A’, C’, X’ son las matrices ampliadas1, mientras que B es la matriz de 
disponibilidades. 
C’ = ⎜⎜
⎛
 A’= ( )AaA ⎟⎟
⎠
⎞
⎝ ax
x
 X’= ⎜⎜
⎛
 B = 
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
mb
b
b
..
..
2
1
La forma estándar de un programa lineal da origen a una tabla de trabajo denominada 
Tableau simplex inicial 
 
 
Variables de decisión )( jX Variables 
básicas 
Contribuciones 
unitarias 
(V.B.) Vector de costos )( jC 
 
0X 0C 
 
Matriz de coeficientes 
tecnológicos 
Vector de 
Disponibilidades
jZ Vector de perdida de oportunidad Valor de la 
 
1 Matrices ampliadas en el sentido de considerar los coeficientes de las variables de decisión propias de la 
situación (C, A y X) y los coeficientes proporcionados por las variables agregadas en el proceso de 
estandarización (Ca, Aa, Xa). 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 4 
 
( )jj ZC −± Vector de decisión simplex (Contribución unitaria neta) FunciónObjetivo
 
 
 
Donde: 
 
 
 
 
 
0X
0C
jii
m
1i
0j a*)C(Z ∑
=
= 0
: Vector de variables básicas 
: Vector de las contribuciones unitarias de las variables básicas 
 
 Producto escalar entre los vectores c y el vector aj que corresponde 
al vector asociado a la j-ésima columna de la matriz de coeficientes 
tecnológicos, es decir, (En EXCEL corresponde a la 
función SUMA PRODUCTO)
j
t
0 aC ∗
Ejemplo: 
 Dado el programa lineal 
 MAX Z = 21 1030 XX + 
S.T. 
16084 21 ≤+ XX
5022 21
 
≤+ XX
6034 21 ≥
 
+ XX 
404 21 ≥+ XX 
021 ≥∧ XX 
La correspondiente estandarización es: 
 
MAX Z= 30 43432121 000010 MAMASSHHXX −−+++++
121 84 HXX ++
 
 S.T. 
 =160 
21 22 XX + 2H+ = 50 
21 34 XX + 33 AS +− = 60 
214 XX + 44 AS +− = 40 
0;;;;;;; 43432121 ≥AASSHHXX
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
−
−
11000014
00110034
00001022
00000184
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
4
4
3
3
2
1
2
1
A
S
A
S
H
H
X
X
 
 
Lo que matricialmente permite expresar al conjunto de restricciones mediante la siguiente 
ecuación: 
 * ⎜ = 
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
40
60
50
160
 
Mientras que la función objetivo queda dada por la expresión: 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 5 
 
 
Max Z = 
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
∗
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
−
−
4
4
3
3
2
1
2
1
T
A
S
A
S
H
H
X
X
M
M
0
0
0
0
10
30
Que es equivalente a: 
( )MM −−00001030
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
4
3
4
3
2
1
2
1
A
A
S
S
H
H
X
X
3S
 * MAX Z= 
 
Situación que representado a través del tablero simplex, conduce al siguiente tableau, que 
se denomina tableau inicial: 
 
 
1X 2X 1H 2H 3A 4S 4A Variables 
Básicas C 0 30 10 0 0 0 -M 0 -M 
 Disponibilidades
1H 0 4 8 1 0 0 0 0 0 160 
2H 0 2 2 0 1 0 0 0 0 50 
3A -M 4 3 0 0 -1 1 0 0 60 
4A -M 4 1 0 0 0 0 -1 1 40 
JZ -8M -4M 0 0 M -M M -M 
JJ ZC − 30+8M 10+4M 0 0 -M 0 -M 0 
-100M 
 
De donde se visualiza la solución básica inicial, dada por: 
 
1H =160 = 0 1X
2H = 50 = 0 2X
3A = 60 = 0 3S
4A = 40 = 0 4S
Con un resultado económico dado por: 
Z= -100M 
 
Obs.: 
 Tal como lo establecen los criterios establecidos para la solución de sistemas de 
ecuaciones, se puede observar que las variables básicas, son aquellas cuyas 
columnas están asociadas a la matriz identidad, en este caso de orden 4, ya que el 
programa tiene 4 restricciones. 
 De igual forma y tal como se señaló anteriormente, los valores del vector Zj, se 
obtienen del producto escalar entre el vector de contribuciones unitarias asociado a 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 6 
 
las variables básicas y cada uno de los respectivos vectores columna de la matriz de 
coeficientes tecnológicos. 
 
 
 
 
 Así por ejemplo: Z1 es el producto escalar entre los vectores: 
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
−
−
=
4
4
2
4
ay
M
M
0
0
C 1o , dado por ( ) M8
4
4
2
4
MM00aC 1
t
0 −=
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
•−−=⋅
 
 
 
 
 
 
ALGORITMO DEL MÉTODO 
 
El algoritmo del método simplex desarrollado para modelos de maximización, es el 
siguiente: 
 
1. Determinar la solución básica inicial 
2. Verificar si esta solución es óptima mediante la prueba de optimalidad, que se 
define más adelante. 
3. Si la solución propuesta satisface la prueba de optimalidad, entonces se tiene la 
solución óptima para el programa. En caso contrario, se debe proceder a mejorar 
esta solución, es decir, realizar la siguiente iteración. 
4. Identificar la variable que pasa a tomar parte del conjunto de variables básicas -
VARIABLE QUE ENTRA-, esta variable corresponde a aquella que en el vector 
de decisión simplex, posee la mayor contribución unitaria neta, es decir, es aquella 
variable de decisión, cuya incorporación a la base produce la mayor contribución al 
resultado económico. La columna asociada a la variable que entra se denomina 
columna pivote o columna de trabajo. 
5. Identificar a la variable que deja de formar parte del conjunto de variables básicas, 
la que se denomina VARIABLE QUE SALE, para esto se divide cada uno de los 
elementos del vector de disponibilidades por el termino correspondiente (homólogo) 
de la columna pivote, seleccionándose como variable que sale aquella que tenga 
asociado el menor cuociente, la fila identificada por esta variable se denomina fila 
pivote o fila de trabajo. Es importante tener presente que en la obtención de estas 
razones, sólo se consideran aquellas en las que el termino correspondiente en la 
columna pivote es positivo, es decir, se descartan aquellos casos en los que el 
término de la columna pivote son nulos o negativos. 
 La fila asociada a la variable que sale se denomina fila pivote o fila de trabajo. 
 
Observación 1: La intersección entre la fila y la columna pivote corresponde al 
elemento pivote o elemento de trabajo. 
 
Observación 2: Tanto en la identificación de la variable que entra como de la variable 
que sale es posible que se produzcan empates; frente a la ocurrencia de 
esta situación es importante tener presente que no existen criterios 
formales para dirimir los empates, por lo tanto éstos se rompen de 
manera arbitraria. 
 
6. Mediante la operación elemental fila “Multiplicar todos los términos de una fila por 
un escalar”, se convierte el elemento pivote en la unidad. (Esto deja en evidencia 
que el escalar que se debe utilizar es el recíproco del elemento pivote). 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 7 
 
7. Mediante operaciones elementales fila se deben convertir en cero los restantes 
elementos de la columna pivote. 
Realizada esta secuencia se ha encontrado una nueva solución para el programa la 
que obviamente mejora la anterior y cuya optimalidad debe ser verificada por lo que 
se debe volver al paso 2. 
 
 
Prueba de Optimalidad. 
 
 
La solución encontrada es óptima si ninguna de las variables de decisión contribuye a 
mejorar el valor de la función objetivo, esto significa que todas las variables tienen que 
tener una contribución unitaria neta nula o negativa. Si así no fuere, es decir, si alguna 
variable presenta una contribución unitaria neta positiva entonces la solución obtenida no es 
optima ya que existe al menos una variable no básica cuya incorporación a la base 
contribuye a mejorar el resultado económico, por lo que se debe realizar una nueva 
iteración. 
Observación: En un programa lineal en el que participan variables artificiales, estas pueden 
eliminarse del programa en la misma iteración en las que dejan de ser 
básicas. 
Observación: Si bien el método simplex fue diseñado sobre la base de la maximización 
este también puede utilizarse en problemas de minimización, para esto debe 
considerarse el principio matemático que establece que el mínimo de una 
función corresponde al máximo de su opuesto. 
 
MIN Z = MAX -Z 
Tal relación deja en evidencia que el método simplex para minimizar se 
desarrolla exactamente igual que para maximizar produciéndose el cambio 
únicamente en el vector de decisión simplex (contribuciones unitarias netas) 
dado por ( ) JJjj CZZC −=−− 
Ejemplo: 
Al considerar el problema anterior: 
MAX Z = 21 1030 XX + 
S.T. 
1608421 ≤+ XX
5022 21
 
≤+ XX
6034 21 ≥
 
+ XX
404 21 ≥
 
+ XX 
021 ≥∧ XX 
Cuyo tableau inicial está dado por: 
1X 2X 1H 2H 3S 3A 4S 4A Variables 
Básicas C 0 30 10 0 0 0 -M 0 -M 
 Disponibilidades
1H 0 4 8 1 0 0 0 0 0 160 
2H 0 2 2 0 1 0 0 0 0 50 
3A -M 4 3 0 0 -1 1 0 0 60 
4A -M 4 1 0 0 0 0 -1 1 40 
JZ -8M -4M 0 0 M -M M -M 
JJ ZC − 30+8M 10+4M 0 0 -M 0 -M 0 
-100M 
 
Que conduce a la solución básica inicial dada por: 
1H =160 = 0 = 50 = 0 1X 2H 2X
3A = 60 = 0 = 40 = 0 3S 4A 4S
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 8 
 
 
 
 
 
 
 
Que produce como resultado económico Z = -100M, se tiene que al aplicar la prueba de 
optimalidad, las variables X1 y X2 tienen una contribución unitaria neta positiva (30 + 8M y 
10 + 4M respectivamente), por lo que existen variables no básicas, cuya incorporación a la 
base produce un mejoramiento del resultado económico, por lo que debe realizarse una 
nueva iteración: 
 
 
Primera iteración: 
 
 
La mayor contribución unitaria neta en el tableau inicial es 30+8M, por lo que la variable 
que entra es X1 y la columna pivote es la primera columna de la tabla. 
 
Al realizar los cuocientes entre los elementos de vector de disponibilidades y su homólogo 
de la columna se tiene: 
160 : 4 = 40 
50 : 2 = 25 
60 : 4 = 15 
40 : 4 = 10 
Al ser 10 el menor cuociente, se tiene que la variable A4 deja de formar parte de la base, es 
decir, es la variable que sale y la fila asociada es la fila pivote. 
De la intersección entre la fila pivote y la columna pivote, se tiene que a41= 4 es el elemento 
pivote, así el nuevo tableau es: 
Primera Iteración: 
1X 2X 1H 2H 3S 3A 4S Variables 
Básicas 0C 30 10 0 0 0 -M 0 
 Disponibilidades 
1H 0 0 7 1 0 0 0 1 120 
2H 0 0 3/2 0 1 0 0 1/2 30 
3A -M 0 2 0 0 -1 1 1 20 
1X 30 1 1/4 0 0 0 0 -1/4 10 
JZ 30 7,5 - 2M 0 0 M -M -M - 7,5 
JJ ZC − 0 2M + 2,5 0 0 -M 0 M + 7,5 
300-20M 
 
Iteración que conduce a una nueva solución, dada por: 
 
=120 = 30 = 0 = 20 2H 2X 3A1H
3S = 0 =10 = 0 1X 4S
 
Que produce como resultado económico Z= 300 – 20M 
 
Solución en la que al evaluar la optimalidad, se puede verificar que no es óptima, puesto 
que existen dos variables (X2 y S4), que poseen una contribución unitaria neta positiva, es 
decir, la incorporación de alguna de éstas variables a la base, produce una mejoría de la 
función objetivo, lo que conduce a una nueva iteración. 
 
Observaciones: 
1. Nótese que en la solución inicial el resultado económico era –100M, mientras que 
en la solución actual, el resultado económico es 300-20M, es decir, se produjo una 
mejoría de 300 + 80M, valor que corresponde a la contribución unitaria nata 
(30+8M) por el nivel de la variable que en este caso es 10. 
2. Nótese además que la variable artificial A4, dejó de formar parte de la base, por lo 
tanto fue eliminada del programa. (su presencia ya no se justifica). 
3. El algoritmo del método simplex considera como primera instancia transformar el 
elemento pivote en la unidad, para esto se utilizó la operación elemental fila que 
multiplica la cuarta fila por ¼. 4/1ff 44 ⋅→ 
4. Para hacer ceros al resto de los elementos de la columna pivote, se utilizaron las 
siguientes operaciones elementales fila: 
( ) 11441 ff4f4f →+−⋅=− 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 9 
 
( ) 22442 ff2f2f →+−⋅=− 
( ) 33443 ff4f4f →+−⋅=− 
5. Para la siguiente iteración, se tiene que la mayor contribución unitaria neta entre 
2M+2,5 y M+7,5 es 2M+2,5, por lo tanto, la variable que entra es X2 y la columna 
correspondiente (segunda) es la columna pivote, luego para determinar la variable 
que sale, se evalúan las razones entre los elementos que componen la nueva matriz 
de disponibilidades y el correspondiente elemento de la columna pivote, así: 
120 : 7 = 17,14285 
30 : 3/2 = 20 
20 : 2 = 10 
10 : ¼ =40 Donde el menor valor es 10 y por lo tanto, la variable que sale es A3 y el correspondiente elemento pivote es a32=2 
Segunda Iteración: 
1X 2X 1H 2H 3S 4S Variables 
Básicas C 0 30 10 0 0 0 0 
 Disponibilidades 
1H 0 0 0 1 0 7/2 -5/2 50 
2H 0 0 0 0 1 3/4 -1/4 15 
2X 10 0 1 0 0 -1/2 1/2 10 
1X 30 1 0 0 0 1/8 -3/8 15/2 
JZ 30 10 0 0 -5/4 -25/4 
JJ ZC − 0 0 0 0 5/4 25/4 
325 
 
Iteración que conduce a una nueva solución, dada por: 
 
1H =50 = 15 = 10 = 0 =15/2 = 0 2H 2X 3S 1X 4S
 
Que produce como resultado económico Z= 325 
 
Solución en la que al evaluar la optimalidad, se puede verificar que no es óptima, puesto 
que existen dos variables (S3 y S4), que poseen una contribución unitaria neta positiva, es 
decir, la incorporación de alguna de éstas variables a la base, produce una mejoría de la 
función objetivo, lo que conduce a una nueva iteración. 
 
Observaciones: 
6. Nótese que en la solución actual registra una mejora significativa respecto de la 
anterior de 25 + 20M que corresponde a la diferencia 325 – (300 – 20M), que 
coincide con la contribución unitaria neta 2M+2,5 multiplicada por el nivel de la 
variable que en este caso es 10. 
7. Nótese además que la variable artificial A3, dejó de formar parte de la base, por lo 
tanto, también fue eliminada del programa. (su presencia ya no se justifica). 
8. Las iteraciones realizadas dejan a la vista que cada una de ellas conduce a un 
desplazamiento de la correspondiente columna asociada a la matriz identidad desde 
la variable que sale a la variable que entra. 
9. Para la nueva iteración la variable que entra es S4, puesto que es la que presenta la 
mayor contribución unitaria neta, determinando con esto que la sexta columna del 
tableau es la columna pivote. 
10. Luego para identificar a la variable que sale, se evalúan las razones entre los 
elementos de la nueva columna de disponibilidades y el correspondiente término 
homólogo de la columna pivote, así: 
 50 : -5/2 No aplica 
15 : -1/4 No aplica 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 10 
 
10 : 1/2 = 20 
15/2 = -3/8 No aplica 
Lo que deja a la vista que la variable que sale es X2 
 
 
 
Tercera Iteración: 
 
 
1X 2X 1H 2H 3S 4S Variables 
Básicas C 0 30 10 0 0 0 0 
 Disponibilidades 
1H 0 0 5 1 0 1 0 100 
2H 0 0 1/2 0 1 1/2 0 20 
4S 0 0 2 0 0 -1 1 20 
1X 30 1 3/4 0 0 -1/4 0 15 
JZ 30 45/2 0 0 -15/2 0 
JJ ZC − 0 -25/2 0 0 15/2 0 
450 
 
Iteración que conduce a una nueva solución, dada por: 
 
1H =100 = 20 = 0 = 0 =15 = 20 2H 2X 3S 1X 4S
 
Que produce como resultado económico Z= 450 
 
Solución en la que al evaluar la optimalidad, se puede verificar que no es óptima, puesto 
que existe una variable (S4), que posee una contribución unitaria neta positiva, es decir, la 
incorporación de esta variable a la base, produce una mejoría de la función objetivo, lo que 
conduce a una nueva iteración. 
 
Observaciones: 
11. Nótese que en la solución actual registra una mejora respecto de la anterior de 125 
que corresponde a la diferencia 450 – 325, que coincide con la contribución unitaria 
neta 25/4 multiplicada por el nivel de la variable que en este caso es 20. 
12. Para la nueva iteración la variable que entra es S3, puesto que es la que única con 
una contribución unitaria neta positiva, determinando con esto que la quinta 
columna del tableau es la columna pivote. 
13. Luego para identificar a la variable que sale, se evalúan las razonesentre los 
elementos de la nueva columna de disponibilidades y el correspondiente término 
homólogo de la columna pivote, así: 
100 : 1 = 100 
20 : 1/2 = 40 
20 : -1 No aplica 
15 : -1/4 No aplica 
Lo que deja a la vista que la variable que sale es H2, siendo a25 = 1/2 el elemento 
pivote. 
 
Cuarta Iteración: 
1X 2X 1H 2H 3S 4S Variables 
Básicas C 0 30 10 0 0 0 0 
 Disponibilidades 
1H 0 0 4 1 -2 0 0 60 
3S 0 0 1 0 2 1 0 40 
4S 0 0 3 0 2 0 1 60 
1X 30 1 1 0 1/2 0 0 25 
JZ 30 30 0 15 0 0 
JJ ZC − 0 -20 0 -15 0 0 
750 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 11 
 
 
Iteración que conduce a una nueva solución, dada por: 
 
1H =60 = 0 = 0 = 40 =25 = 60 2H 2X 3S 1X 4S
 
Que produce como resultado económico Z= 750 
 
 
Solución en la que al evaluar la optimalidad, se puede verificar que es óptima, puesto que 
no existe ninguna variable que tenga una contribución neta positiva. Por lo tanto, el proceso 
de búsqueda de lsa solución óptima ha finalizado. 
 
Observaciones: 
 
14. Nótese que en la solución actual registra una mejora respecto de la anterior de 300 
que corresponde a la diferencia 750 – 450, que coincide con la contribución unitaria 
neta 15/2 multiplicada por el nivel de la variable que en este caso es 40. 
 
COMPARACIÓN MÉTODO SIMPLEX V/S MÉTODO GRÁFICO 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Al Observar el gráfico, se puede verificar, como el método simplex, “va saltando” de un 
punto a otro, hasta llegar al óptimo que se ubica en una de los puntos extremos. Nótese que 
en este caso en particular, los primeros “saltos”, no fueron de un punto extremo a otro 
punto extremo, esto debido a la presencia de variables artificiales. 
Lo anterior, deja en vista que cuando el programa no incluye variables artificiales, los saltos 
van de un punto extremo a otro punto extremo. 
 
Ejercicio: Para cada uno de los siguientes casos y considerando cada una de las iteraciones: 
1. Determine cada una de las soluciones. 
2. Evalúe la optimalidad. 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 12 
 
3. Evalúe en mejoramiento económico, relacionándolo con la variable que fue 
incorporada a la base y su contribución unitaria neta. 
 
 
 
CASO 1: 
 
MAX Z = 4321 406050160 XXXX +++ 
 S.T. 
304424 4321 ≤+++ XXXX 
 
10328 4321 ≤+++ XXXX 
0,,, 4321 ≥XXXX 
 
 
 
1X 2X 3X 4X 1H 2H VB 0C 
160 50 60 40 0 0 
Disponibilidades 
1H 0 4 2 4 4 1 0 30 
2H 0 8 2 3 1 0 1 10 
JZ 0 0 0 0 0 0 
jj ZC − 160 50 60 40 0 0 
0 
 
 
 
 1X 2X 3X 4X 1H 2H 
 VB 
 
0C 160 50 60 40 0 0 
 Disponibilidades 
 
 1H 0 0 1 5/2 7/2 1 -1/2 25 
 1X 160 1 1/4 3/8 1/8 0 1/8 5/4 
 JZ 160 40 60 20 0 20
 C jj Z− 0 10 0 20 0 -20
200 
 
 
 
 
 1X 2X 4X 1H 3X 2H 
 VB 
 
 0C 160 50 60 40 0 0 
 Disponibilidades 
 
 4X 40 0 2/7 5/7 1 2/7 -1/7 50/7 
 1X 160 1 3/14 2/7 0 -1/28 1/7 5/14 
 JZ 160 320/7 520/7 40 40/7 120/7
 C jj Z− 0 30/7 -100/7 0 -40/7 -120/7
2400/7 
 
 
 
 
 1X 2X 3X 4X 1H 2H 
 VB 
 0C
 160 50 60 40 0 0 Disponibilidades 
 4X 40 -4/3 0 1/3 1 1/3 -1/3 20/3 
 2X 50 14/3 1 4/3 0 -1/6 2/3
 5/3 
 
 JZ 180 50 80 40 5 20
 C jj Z− -20 0 20 0 -5 -20 350 
 
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 13 
 
 
 
 
 
 
CASO 2: 
 
MIN Z = 21 1030 XX + 
 
 
 S.T. 
 
16084 21 ≥+ XX 
 
5022 21 ≥+ XX 
6034 21 ≥+ XX 
404 21 ≥+ XX 
021 ≥∧ XX 
 
 
 
1X 2X 1S 1A 2S 2A 3S 3A 4S 4A 
VB 
 
0C 30 10 0 M 0 M 0 M 0 M 
Disp. 
 
 1A M 4 8 -1 1 0 0 0 0 0 0 160
 2A M 2 2 0 0 -1 1 0 0 0 0 50
 3A M 4 3 0 0 0 0 -1 1 0 0 60
 4A M 4 1 0 0 0 0 0 0 -1 1 40
 jZ 14M 14M -M M -M M -M M -M M
 jj CZ − 14M-30 14M-10 -M 0 -M 0 -M 0 -M 0
310M
 
 
 
 
 
1X 2X 1S 2S 2A 3S 3A 4S 4A 
VB 
 
0C 30 10 0 0 M 0 M 0 M 
Disp. 
 
2X 10 1/2 1 -1/8 0 0 0 0 0 0 20 
2A M 1 0 1/4 -1 1 0 0 0 0 10 
3A M 5/2 0 3/8 0 0 -1 1 0 0 0 
4A M 7/2 0 1/8 0 0 0 0 -1 1 20 
jZ 7M+5 10 -5/4+3/4M -M M -M M -M M 
jj CZ − -25+7M 0 -5/4+3/4M -M 0 -M 0 -M 0 
200+30M
 
 
 
 
 
1X 2X 1S 2S 2A 3S 4S 4A 
VB 
 
0C 30 10 0 0 M 0 0 M 
Disp. 
 
2X 10 0 1 -1/5 0 0 1/5 0 0 20 
2A M 0 0 1/10 -1 1 2/5 0 0 10 
1X 30 1 0 3/20 0 0 -2/5 0 0 0 
4A M 0 0 -2/5 0 0 7/5 -1 1 20 
jZ 30 10 5/2-3/10M -M M -10+9/5M -M M 
jj CZ − 0 0 5/2-3/10M -M 0 -10+9/5M -M 0 
200+30M
UNIVERSIDAD TECNOLÓGICA METROPOLITANA 
FACULTAD DE ADMINISTRACIÓN Y ECONOMÍA 
DEPARTAMENTO DE ESTADÍSTICA Y ECONOMETRÍA 
 
 
 
 
 
Métodos Cuantitativos/Investigación de Operaciones PROFESOR HUGO GONZÁLEZ A. 
Página Nº 14 
 
 
 
 
 
 
 
 
 
1X 2X 1S 2S 2A 3S 4S 
VB 
 
0C 30 10 0 0 M 0 0 
 
Disp. 
2X 10 0 1 -1/7 0 0 0 1/7 120/7 
2A M 0 0 3/14 -1 1 0 2/7 30/7 
1X 30 1 0 1/28 0 0 0 -2/7 40/7 
3S 0 0 0 -2/7 0 0 1 -5/7 100/7 
jZ 30 10 -5/14+3/14M -M M 0 -50/7+2/7M 
jj CZ − 0 0 -5/14+3/14M -M 0 0 -50/7+2/7M 
2400/7 
 
 
 
1X 2X 1S 2S 3S 4S 
VB 
 
0C 30 10 0 0 0 0 
Disp. 
 
2X 10 0 1 -1/4 1/2 0 0 15 
2A M 0 0 3/4 -7/2 0 1 15 
1X 30 1 0 1/4 -1 0 0 10 
3S 0 0 0 1/4 -5/2 0 0 25 
jZ 30 10 5 -25 0 0 
jj CZ − 0 0 5 -25 0 0 
450 
 
 
 
 
1X 2X 1S 2S 3S 4S 
VB 
 
0C 30 10 0 0 0 0 
 
Disp. 
2X 10 0 1 0 -2/3 0 1/3 20 
2A M 0 0 1 -14/3 0 4/3 20 
1X 30 1 0 0 1/6 0 -1/3 5 
3S 0 0 0 0 -4/3 0 1/3 20 
jZ 30 10 0 -5/3 0 -20/3 
jj CZ − 0 0 0 -5/3 0 -20/3 
350 
 
 
	MÉTODO SIMPLEX.
	ALGORITMO DEL MÉTODO
	Prueba de Optimalidad.
	COMPARACIÓN MÉTODO SIMPLEX V/S MÉTODO GRÁFICO