PRESENTACION

Todas las personas toman decisiones de manera diaria y rutinaria, más aún aquellos quienes encabezan alguna empresa; sin embargo, trátese del ámbito que se trate, tomar una decisión es más complejo de lo que pudiera parecer ya que su efecto o consecuencia en ocasiones no es la que se espera. 

El Método Simplex es una herramienta matemática básica en la toma de decisiones pero requiere de entender cada uno de sus pasos y la constancia de practicarlos. Minimizar costos o maximizar ganancias dependerá de las necesidades de cada empresa o sujeto, los caminos para tomarlos son infinitos pero cuando se trata de más de dos variables, el camino realmente óptimo se encuentra justo en este momento en sus manos.

INTRODUCCION
El Método Simplex, como parte de la programación lineal, es un método analítico capaz de resolver aquellos modelos que se vuelven complejos en el uso del método gráfico por el número de variables empleadas, por ejemplo: Si usted se traslada a su Universidad ¿cuántas opciones tiene para llegar? ¿se va caminando o en carro? Si decide irse en transporte ¿automóvil particular, transporte público, bicicleta, patines, de aventó? ¿Qué implica que usted opte por viajar en alguno de estos? ¿Cuántos recursos será necesario invertir? ¿Cuál es la ruta más corta?

¿Se da cuenta?... Son varios los factores a considerar, muchas las variables que contemplar y los resultados diferentes. Una pregunta clave: ¿Con cuántos recursos cuenta usted?, porque hasta el hombre más rico desea optimizar sus recursos sabiéndolos escasos, ¿a qué estamos limitados?

Ante este panorama que en las empresas se vuelve más complejo por el uso de materia prima, recursos implicados y productos fabricados, de ahí la importancia de éste método que facilitará el camino en el proceso de tomar una decisión.

METODO SIMPLEX

El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.

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 del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

El algoritmo del método Símplex fue elegido como uno de los 10 algoritmos más importantes del siglo XX.

MATRIZ DE IDENTIDAD

Una matriz puede definirse como una ordenación rectangular de elementos, (o listado finito de elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de filas y de columnas.

La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo número tanto de columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a uno (1) y todos los demás componentes iguales a cero (0), se denomina matriz idéntica o identidad de orden n, y se denota por:

La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el algoritmo se basa en dicha teoría para la resolución de sus problemas.

FORMULACION DEL METODO SIMPLEX

Utilizando el siguiente ejemplo estableceremos la formulación inicial símplex y demostraremos la mecánica del método y su interpretación. 

El gerente de la Relojería la Torre desea conocer la ganancia máxima que se puede obtener de la producción y venta de dos clases de relojes económicos digitales de pulsera. La ganancia que se obtiene por la producción y venta de un reloj de hombre es de $4 y de $6 para un reloj de mujer. La empresa cuenta con 120 horas semanales para la producción de los relojes y 100 horas para la inspección y empaque de estos. La fabricación de un reloj de hombre requiere 2 horas de producción y 2 horas de inspección y empaque. Mientras que un reloj de mujer requiere 4 horas de producción y 3 horas de inspección y empaque. 

La formulación del problema para esta situación es la siguiente:

Maximizar Z = $4X1 + $6X2
Sujeto a:            2X1 + 4X2 ≤ 120 (horas de producción) 

                          2X1 + 3X2 ≤ 100 (horas de inspección y empaque) 

                          (X1, X2 ≥ 0)

Donde X1 = cantidad de relojes de hombre que se producen semanalmente. 

            X2 = cantidad de relojes de mujer que se producen semanalmente.

Luego de formular el problema procedemos a trabajar primero con las restricciones y luego con la función objetivo. Comenzamos cambiando los signos de las restricciones de desigualdades a igualdades. El método símplex requiere la conversión de las restricciones con signos de desiguales a igualdades estrictas. Esto se debe a que el método usa álgebra de matrices en donde todas las relaciones matemáticas serán a base de ecuaciones lineales y que a su vez deben contener todas las variables. Llamaremos a este procedimiento como aumento de las restricciones y de la función objetivo.  

EJEMPLO DE MAXIMIZACION

Maximizar	Z = f(x,y) = 3x + 2y
sujeto a:	2x + y ≤ 18
	2x + 3y ≤ 42
	3x + y ≤ 24
	x ≥ 0 , y ≥ 0 Se consideran las siguientes fases:1)-.Realizar un cambio de variables y normalizar el signo de los términos independientes. Se realiza un cambio en la nomenclatura de las variables. Estableciéndose la correspondencia siguiente: x pasa a ser X1 y pasa a ser X2 Como los términos independientes de todas las restricciones son positivos no es necesario hacer nada. En caso contrario habría que multiplicar por "-1" en ambos lados de la inecuación (teniendo en cuenta que esta operación también afecta al tipo de restricción). 2)-.Normalizar las restricciones. Se convierten las inecuaciones en ecuaciones agregando variables de holgura, exceso y artificiales según la tabla siguiente: Tipo de desigualdad Tipo de variable que aparece ≥ - exceso + artificial = + artificial ≤ + holgura En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 2·X1 + X2 + X3 = 18 2·X1 + 3·X2 + X4 = 42 3·X1 + X2 + X5 = 24

            3)-.Igualar la función objetivo a cero.

                         Z - 3·X1 - 2·X2 - 0·X3 - 0·X4 - 0·X5 =0

           4)-Escribir la tabla inicial del método Simplex.

La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables de decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 2 (en las columnas, siendo P0 el término independiente y el resto de variables Pi coinciden con Xi), y las restricciones (en las filas). La columna Cb contiene los coeficientes de las variables que se encuentran en la base.

La primera fila está formada por los coeficientes de la función objetivo, mientras que la última fila contiene el valor la función objetivo y los costes reducidos Zj - Cj.

La última fila se calcula como sigue: Zj = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método Simplex y ser todos los Cb nulos se puede simplificar el cálculo, y por esta vez disponer Zj = -Cj.

1. 
   
                   

   Tabla I . Iteración nº 1
   			3	2	0	0	0
   Base	Cb	P0	P1	P2	P3	P4	P5
   P3	0	18	2	1	1	0	0
   P4	0	42	2	3	0	1	0
   P5	0	24	3	1	0	0	1
   Z		0	-3	-2	0	0	0

5)-.Condición de parada.

Si el objetivo es la maximización, cuando en la última fila (fila indicadora) no existe ningún valor negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condición de parada.

En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z (columna P0) es la solución óptima del problema.

Otro caso posible es que en la columna de la variable entrante a la base todos los valores son negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución siempre resultará mejorable. Ante esta situación no es necesario continuar iterando indefinidamente y también se puede dar por finalizado el algoritmo.

De no ser así, se ejecutan los siguientes pasos de forma iterativa.

6)-.Elección de la variable entrante y saliente de la base.

Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sería la variable X1 (P1) de coeficiente -3.

Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate), entonces se optará por aquella variable que sea básica.

La columna de la variable que entra en la base se llama columna pivote (en color verde).

Una vez obtenida la variable que entra en la base, se procede a determina cual será la variable que sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir cada término independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre que ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado haya resultado mínimo.

Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente. En caso de que todos los elementos de la columna pivote fueran de ésta condición se habría cumplido la condición de parada y el problema tendría una solución no acotada (ver teoría del método Simplex).

En este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]

El término de la columna pivote que en la división anterior dio lugar al menor cociente positivo indica la fila de la variable de holgura que sale de la base. En este caso resulta ser X5 (P5), de coeficiente 3. Esta fila se llama fila pivote (en color verde).

Si al calcular los cocientes, dos o más resultados cumplen la condición para elegir el elemento saliente de la base (caso de empate), se escoge aquella que no sea variable básica (siempre que sea es posible).

La intersección de la fila pivote y columna pivote marca el elemento pivote, en este caso el 3.

7)-.Actualizar la tabla.

Los nuevos coeficientes de la tabla se calculan de la siguiente manera:

• En la fila del elemento pivote cada nuevo elemento se calcula como:
  Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote
• En el resto de las filas cada elemento se calcula:
  Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote)

Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de elementos de la columna pivote se anulan (análogo al método de Gauss-Jordan).

Se muestran a continuación los cálculos para la fila P4:

Anterior fila P4	42	2	3	0	1	0
	-	-	-	-	-	-
Anterior Elemento Fila en Columna Pivote	2	2	2	2	2	2
	x	x	x	x	x	x
Nueva fila pivote	8	1	1/3	0	0	1/3
	=	=	=	=	=	=
Nueva fila P4	26	0	7/3	0	1	-2/3

La tabla correspondiente a esta segunda iteración es:

Tabla II . Iteración nº 2
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P3	0	2	0	1/3	1	0	-2/3
P4	0	26	0	7/3	0	1	-2/3
P1	3	8	1	1/3	0	0	1/3
Z		24	0	-1	0	0	1

2. Al comprobar la condición de parada se observa que no se cumple ya que entre los elementos de la última fila hay uno negativo, -1. Se continúa iterando nuevamente los pasos 6 y 7.
   • 6.1. La variable que entra en la base es X2 (P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1.
   • 6.2. Para calcular la variable que sale, se dividen los términos de la columna P0 entre los términos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el menor cociente positivo es 6, la variable que sale de la base es X3 (P3).
   • 6.3. El elemento pivote es 1/3.
   • 7. Actualizando nuevamente los valores de la tabla se obtiene:
     
     

     Tabla III . Iteración nº 3
     			3	2	0	0	0
     Base	Cb	P0	P1	P2	P3	P4	P5
     P2	2	6	0	1	3	0	-2
     P4	0	12	0	0	-7	1	4
     P1	3	6	1	0	-1	0	1
     Z		30	0	0	3	0	-1

3. Una nueva comprobación de la condición de parada revela que entre los elementos de la fila indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha llegado a la solución óptima y hay que seguir iterando (pasos 6 y 7):
   • 6.1. La variable que entra en la base es X5 (P5), por ser la variable que corresponde al coeficiente -1.
   • 6.2. Se escoge la variable que sale calculando el cociente entre los términos de la columna de términos independientes y los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]. En esta ocasión es X4 (P4).
   • 6.3. El elemento pivote es 4.
   • 7. Después de actualizar todas las filas, se obtiene la tabla siguiente:
     
     

     Tabla IV . Iteración nº 4
     			3	2	0	0	0
     Base	Cb	P0	P1	P2	P3	P4	P5
     P2	2	12	0	1	-1/2	1/2	0
     P5	0	3	0	0	-7/4	1/4	1
     P1	3	3	1	0	3/4	-1/4	0
     Z		33	0	0	5/4	1/4	0

8)-.Fin del algoritmo.

Se observa que en la última fila todos los coeficientes son positivos cumpliéndose, por tanto la condición de parada.

La solución óptima viene dada por el valor de Z en la columna de los términos independientes (P0), en este ejemplo: 33. En la misma columna se puede ver el punto donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: X1 = 3 y X2 = 12.

Deshaciendo el cambio de variables se obtiene x = 3 e y = 12.

EJEMPLO DE MINIMIZACION

Con ello construimos la tabla inicial del Método Simplex donde las variables de holgura previamente identificadas definen una solución básica factible inicial (no óptima):

Por el criterio del costo reducido más negativo la variable que ingresa a la base es x₁. Luego calculamos en dicha columna el mínimo cuociente que esta dado por: .

En consecuencia el pivote se encuentra en la fila 4 y por tanto la variable x₆ deja la base. (Notar que para el cálculo del mínimo cuociente o criterio de factibilidad sólo se consideran denominadores que sean estrictamente mayores a cero).

Ahora la variable no básica que ingresa a la base es x₂. Calculamos nuevamente el mínimo cuociente sobre dicha columna obteniendo: .

Por tanto x₅ abandona la base. Con ello realizamos una nueva iteración del Método Simplex:

La solución óptima es x₁=200 y x₂=600, donde el valor de las holguras x₃ y x₄ corresponde a 600 y 100, respectivamente. Notar adicionalmente que las variables x₅ y x₆ son no básicas en el óptimo, por tanto su valor es cero, lo que indica que las restricciones 3 y 4 son activas. El valor óptimo del problema es V(P)=2.600.

CONCLUSIÓN

Si bien el método simplex se puede resolver de forma algebraica la forma mas apropiada seria por el método de la tabla para adquirir conocimientos de matrices, y para incorporarnos un poquito mas en el funcionamiento del mercado y de la toma de decisiones.

BIBLIOGRÁFICA

11:22

http://cicia.uprrp.edu/publicaciones/docentes/metodosimplexdePL.pdfcicia.uprrp.edu

11:22

secme-16318.pdf                                                                                      ri.uaemex.mx

11:21

Método Simplex - Ingeniería Industrial                   www.ingenieriaindustrialonline.com

11:05

Teoría del Método Simplex                                                            www.phpsimplex.com

11:01

2 SIMPLEX.DOC                                                                                allman.rhon.itam.mx