INVESTIGACION OPERATIVA PROGRAMACION LINEAL

APLICACIÓN DE LA VARIABLE AUXILIAR

El Método Simplex es un método iterativo que permite ir mejorando la solución en

cada paso. La razón matemática de esta mejora radica en que el método consiste en
caminar de un vértice del poliedro de soluciones a un vértice vecino de manera que
aumente o disminuya (según el contexto de la función objetivo, sea maximizar o
minimizar).
De los vértices vecinos, el método indica cual elegir para hacer menos pasos. Dado
que el número de vértices que presenta un poliedro solución es finito siempre se
hallará la solución.
Además, el sistema de ecuaciones debe cumplir con la condición de NO negatividad
(x2>= 0 ), condición necesaria para poder trabajar gráfica y analíticamente con el
sistema.

Sea un problema (Ejercicio N°5 de la guía) donde las restricciones están

representadas por el siguiente sistema de inecuaciones:

6x1 + 5x2 <= 30

x2 >= 1
-2x1 + 2x2 <= 6

Y con la siguiente ecuación del Funcional: Z= 5x1 + 8x2 (Max)

Cabe aclarar que con estas condiciones de contar con 2 variables, podríamos aplicar
el método gráfico y determinar sus valores óptimos en uno de los vértices del
polígono de soluciones.

Encontrar la solución es determinar los valores de las incógnitas reales que optimizan
al Funcional. El Funcional es la expresión matemática que permite adoptar la mejor
decisión o determinar el valor óptimo, según sea el caso.
Estamos en un caso de Maximización.

Para resolver el problema, tenemos que transformar las inecuaciones (desigualdades)

en ecuaciones (igualdades)
El modelo matemático que nos describe las restricciones del caso a resolver es un
sistema de inecuaciones y necesitamos de las variables Slack o de holgura, para poder
transformarlas en ecuaciones, lo que nos genera una matriz identidad, condición

pág. 1
INVESTIGACION OPERATIVA PROGRAMACION LINEAL

previa para poder trabajar en el método Simplex, que está basado en el Método de
Gauss Jordan.

Si la desigualdad es del tipo ">=", caso de la segunda ecuación, la slack será negativa:

6x1+5x2 + x3 = 30
x2 -x4 = 1
-2x1+ 2x2 +x5 = 6

Y en el Simplex no tendremos la Matriz Identidad completa.

Para tener la Matriz Identidad completa, agregamos una variable auxiliar, que
llamamos µ (letra griega mu) y que es un truco ó artificio matemático.
En la formulación ampliada de las restricciones, se pone µ en una columna adosada
en la fila de la inecuación con ">=".

6x1+5x2 + x3 = 30
x2 -x4 +µ = 1
-2x1+ 2x2 +x5 = 6

De la misma forma esta variable auxiliar µ, debe estar presente en la ecuación del
Funcional a optimizar, precedida por un valor llamado M, que es un valor finito,
suficientemente grande. En comparación M debe ser 1.000 veces el valor del mayor
coeficiente de costo que precede a las variables reales.
Este valor hace salir lo más rápido posible del sistema a la variable artificial µ.

Al ser este problema un caso de Maximización, en la ecuación del funcional el valor M

debe ser negativo. En un caso de Minimización el M debe ser Positivo.

La ecuación del funcional quedará de la siguiente manera:

Z = 5 x1 + 8 x2 + 0 x3 + 0 x4 + 0 x5 - M µ (Max)

Los coeficientes de las variables Slag o de holgura que conforman la matriz identidad
en el primer paso, serán los de x3 y x5 y una variable auxiliar llamada, en este caso µ, y
en la solución óptima µ debe ser igual a cero. Es decir, este valor debe salir lo más
rápido posible del sistema para no comprometer el resultado final en la aplicación del
SIMPLEX.
pág. 2
INVESTIGACION OPERATIVA PROGRAMACION LINEAL

Reiterando, el objetivo fundamental de esta variable artificial es la formación de la

matriz identidad completa para operar correctamente en el Simplex. La característica
principal de estas variables es que no deben formar parte de la solución, dado que no
representan productos o elementos reales.

En un caso de Maximización, en cada paso, los valores del ( zj-cj ) con el mayor valor
negativo, identificaran la columna del pívot y en la fila donde tengamos el menor
cociente b/a tendremos el coeficiente que usaremos como pivot.

Resolviendo el problema por el Método Simplex, planteamos la solución inicial y

calculamos los valores de zj-cj a fin de definir las variables de entrada y salida de la
solución. Como es un caso de maximización, los valores de zj-cj con el mayor valor
negativo identificaran la variable que ingresa a la solución (columna del pivot) y el
menor cociente b/a identificará la variable que sale (fila del pivot).

PRIMER PASO Cj 5 8 0 0 0 -M b/a

C2 X2 B a1 a2 a3 a4 a5 a6
0 X3 30 6 5 1 0 0 0 6
-M µ 1 0 1 0 -1 0 1 1
0 X5 6 -2 2 0 0 1 0 3
Zj-Cj -M -5 -M-8 0 M 0 0

En este ejemplo, el mayor ( zj - cj ) negativo del primer paso será el de la columna

del vector a2 y el menor cociente (b/a) en la fila de µ, o sea que se desanula x2 y se
anula µ. O sea que µ sale de la matriz A2 de las variables no nulas en el primer paso.
Entra x2 y sale µ.

SEGUNDO PASO Cj 5 8 0 0 0 -M b/a

C2 X2 B a1 a2 a3 a4 a5 a6
0 X3 25 6 0 1 5 0 25/5
8 X2 1 0 1 0 -1 0 -1
0 X5 4 -2 0 0 2 1 4/2
Zj-Cj 8 -5 0 0 -8 0

pág. 3
INVESTIGACION OPERATIVA PROGRAMACION LINEAL

En el paso siguiente, ya no se utiliza la columna de los valores correspondientes al µ.

Fijando condiciones de simplificación del método SIMPLEX para poder seguir
operando manualmente, la columna de la variable µ puede ser eliminada del sistema
y no operamos más en esa columna.

TERCER PASO Cj 5 8 0 0 0 b/a

C2 X2 B a1 a2 a3 a4 a5
0 X3 15 11 0 1 0 -2,5 15/11
8 X2 3 -1 1 0 0 0,5 -3
0 X4 2 -1 0 0 1 0,5 -1/2
Zj-Cj 24 -13 0 0 4 0

CUARTO PASO Cj 5 8 0 0 0 b/a

C2 X2 B a1 a2 a3 a4 a5
5 X1 1,36 1 0 o,09 0 -0,23
8 X2 4,36 0 1 o,09 0 0,27
0 X4 3,36 0 0 o,09 1 0,27
Zj-Cj 43,55 0 0 1,18 0 1,05

Si tenemos varias inecuaciones con el ">=", tendremos igual cantidad de variables

auxiliares (µ1, µ2, etc. ), y todas estarán en el Funcional precedidas por M y el método
eliminará de la solución a todas ellas antes de llegar al óptimo.

También se usa este artificio cuando aparecen igualdades en el problema original, ya

que no habría necesidad de agregar una slag y necesitaríamos la auxiliar para
completar la matriz identidad.

En los ejercicios/ejemplos vistos con dos variables, los resolvimos tanto gráfica como
analíticamente. Ello nos permite ubicar en qué punto del gráfico estábamos en cada
paso.
Cuando las restricciones son todas del tipo “<=”, en el primer paso estamos en el
origen de coordenadas.

pág. 4
INVESTIGACION OPERATIVA PROGRAMACION LINEAL

En este caso en el primer paso no estamos en el gráfico. Es como si estuviésemos en

el espacio, y en el segundo paso “caemos” en el punto ó vértice (B), donde x2 = 1 .

En el segundo paso estamos en el punto (C) ( x2= 3 ).

En el 3º paso estamos en el óptimo que sería el punto (D) ( x1= 15/11 y x2= 48/11 ).

Se observa que el primer paso del Simplex (que incluye a la variable auxiliar) no tiene
representación gráfica, estaríamos “en el espacio”. De igual forma, en el caso de
tener varias restricciones de mayor o igual, tendremos varias variables µ y no se
tendrá una representación gráfica mientras estas variables no salgan del sistema.

Gráficamente la representación del polígono será:

pág. 5
INVESTIGACION OPERATIVA PROGRAMACION LINEAL

Los cuadros completos del SIMPLEX, aplicando el método desarrollado, quedan de la

siguiente manera:

Cj 5 8 0 0 0 -M
C2 X2 B a1 a2 a3 a4 a5 µ b/a Paso 1
0 x3 30 6 5 1 0 0 0 6 x1+x2+x4=0
-M µ 1 0 1 0 -1 0 1 1
0 x5 6 -2 2 0 0 1 0 3
Zj -M 0 -M 0 M 0 -M
Zj - Cj -5 -M-8 0 M 0 0

Cj 5 8 0 0 0 -M
C2 X2 B a1 a2 a3 a4 a5 µ b/a Paso 2
0 x3 25 6 0 1 5 0 5 x1+x4+µ=0
8 x2 1 0 1 0 -1 0 -1 (B)
0 x5 4 -2 0 0 2 1 2
Zj 8 0 8 0 -8 0
Zj - Cj -5 0 0 -8 0

Cj 5 8 0 0 0 -M
C2 X2 B a1 a2 a3 a4 a5 µ b/a Paso 3
0 x3 15 11 0 1 0 5 /2 15 /11 x1+x5+µ=0
8 x2 3 -1 1 0 0 1/2 -3 (C)
0 x4 2 -1 0 0 1 1/2 -2
Zj 24 -8 8 0 0 4
Zj - Cj -13 0 0 0 4

Cj 5 8 0 0 0 -M
C2 X2 B a1 a2 a3 a4 a5 µ b/a Paso 4
5 x1 15 /11 1 0 1 /11 0 -5 /22 x3+x5+µ=0
8 x2 48 /11 0 1 1 /11 0 6 /22 (D)
0 x4 37 /11 0 0 1 /11 1 6 /22
Zj 459 /11 5 8 13 /11 0 23 / 22
Zj - Cj 0 0 13 /11 0 23 / 22

pág. 6