M_simplex

Método Simplex

Capítulo 5
Método Simplex

Cj

Î
V.B.
b
5 X1
13/9
3 X3
14/9
-2 X2
1/3
Zj - Cj 101/9

5
X1
1
0
0
0

-2
X2
0
0
1
0

3
0
-M
0
0
b/a
X3
X4
X5
X6
X7
0 -4/15
4/15 7/45 4/45
NO
1/15
1
-1/15 2/45 14/45 70/3
0 -3/15
3/15 -2/15 1/15
NO
0 -11/15 M+11/15 53/45 56/45

Introducción
El método algebraico es muy dispendioso, en razón a que trabaja con todos los datos de las
ecuaciones, paramejorar éste aspecto se creó el método simplex cuya gran virtud es su
sencillez, método muy práctico, ya que solo trabaja con los coeficientes de la función
objetivo y de las restricciones. Ilustraremos su funcionamiento mediante un ejemplo, pero
previamente mostraremos las reglas de decisión para determinar la variable que entra, la
que sale, la gran M, y cómo determinar que estamos en el óptimo; Todaséstas reglas de
decisión fueron deducidas del método algebraico, solamente que aquí se han acomodado
para ser usadas en el tipo de tablero simplex que se usará.
Criterio de decisión

Maximizar

Minimizar

Gran M en la función objetivo

- MXj

+MXj

Variable que entra

La más negativa de los Zj - Cj La más positiva de los Zj - Cj

Variable que sale

La menos positiva de los b/a , La menos positivade los b/a ,
Siendo a > 0 , de lo contrario Siendo a > 0 , de lo contrario
no restringe
no restringe a la variable que
entra

Solución óptima

Cuando todos los Zj – Cj > 0

Cuando todos los Zj – Cj < 0

Adicionalmente se presentan las siguientes notas a tener en cuanta:

83

Método Simplex
•

•

•

Si en el tablero simplex de la solución óptima queda al menos una variable de Super avit
óartificial dentro de las variables básicas, con un valor > 0 , el problema no tiene
solución, esto quiere decir que al menos existen dos restricciones excluyentes, por lo
tanto no existe área de soluciones factible y menos una solución , en éste caso se debe
revisar la formulación del problema.
Si al escoger la variable que sale, ninguna de las variables básicas restringe el
crecimiento de la variable nobásica escogida para entrar, el problema tiene solución
indeterminada y se debe revisar la formulación en busca de una nueva restricción que no
se tuvo en cuenta en la formulación inicial.
Si en el tablero simplex del óptimo, al menos una de las variables no básicas tiene
coeficiente cero (0) en la función objetivo, esto es su Zj – Cj = 0, el problema tiene
múltiples soluciones y se nos estáofreciendo una de ellas.

Ejemplo 1
Maximizar Z = X1 + X2
C.S.R.
5X1 + 3X2 < 15
3X1 + 5X2 < 15
Xj > 0 ; j = 1, 2

Todo problema de programación lineal que
se formule de la forma Maximice, con todas
sus restricciones < y con la condición de no
negatividad, se le llama Forma Estándar ó
Forma Normal

Aquí, al igual que en el método algebraico, debemos conseguir una solución básica factible,
empleando lasvariables de holgura y/o artificiales, quedando el sistema de ecuaciones así:
Maximizar Z = X1 + X2
C.S.R.
5X1 + 3X2 + X3
= 15
3X1 + 5X2
+ X4 = 15
Xj > 0 ; j = 1,2,3,4

Las variables básicas son X3 y X4 y por su
puesto en la función objetivo Z.
Este ejercicio es el ejemplo 1 del capitulo
de método algebraico. Compare los
resultados entre los dos métodos.

A continuación construimos la siguientetabla:
Cj →
1 1 0 0
b/a
↓ V.B. b X1 X2 X3 X4
0 X3 15 5 3 1 0
0 X4 15 3 5 0 1
Zj - Cj

0 -1 -1

0

0

El valor de la función objetiva Z, se encuentra frente a la casilla de Zj – Cj , en éste caso
vale cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna
inmediatamente anterior a la de las variables básica V.B.) que contiene los coeficientes de
84

Método Simplex
lasvariables básicas en la función objetiva original por el vector columna de los términos
independientes b
CXB = Vector fila de los coeficientes en la función objetivo original de las variables básicas
actuales, sus valores se encuentran en la primera columna del tablero.
b = Vector columna de los términos independientes de las restricciones, que al mismo
tiempo son los valores de las variables básicas...