PRESENTACIÓN

MÉTODO SIMPLEX

José David Arroyo Montero

Alba Liseth Mendoza Lerma

José David Mestre López

Yusmaira Rangel Laguna

DEFINICIÓN

MÉTODO SIMPLEX

El método Simplex es un procedimiento general para resolver problemas de programación lineal. Desarrollado por George Dantzig en 1947, esta comprobada su extraordinaria eficiencia, y se usa en forma rutinaria para resolver problemas grandes en computadoras actuales. También se usan extensiones y variaciones del método Simplex para realizar análisis posoptimo (que incluye el análisis de sensibilidad) sobre el modelo. 

El método Simplex es un procedimiento algebraico, Sin embargo, sus conceptos fundamentales son geométricos, por lo que la comprensión de estos conceptos geométricos nos proporciona una fuerte intuición sobre como opera el método Simplex y porque es tan eficiente. 

Este método se emplea con un proceso interactivo, o sea, que se usa sucesivamente la misma rutina básica de cálculo, lo que da por resultado una serie de soluciones sucesivas hasta que se encuentra la mejor. Una característica básica del método Simplex es que la última solución produce una contribución tan grande o mayor que la solución previa en un problema de maximización, lo que da la seguridad de llegar finalmente a la respuesta óptima. 

¿PARA QUÉ SIRVE EL MÉTODO SIMPLEX?

El método Simplex nos sirve para solucionar problemas en donde debemos de optimizar nuestros recursos de la manera más eficiente. Se utiliza para resolver problemas de programación lineal en los que intervienen tres o más variables. 


IMPORTANCIA DEL MÉTODO SIMPLEX

El método simplex permite localizar de manera eficiente la óptima solución entre los puntos extremos de un problema de programación lineal. La gran virtud del método simplex es su sencillez, método muy práctico, ya que solo trabaja con los coeficientes de la función objetivo y de las restricciones. 

Es muy importante en el área empresarial ya que lo utilizan para obtener solución a los problemas de las empresas en cuanto a inventario, ganancias y pérdidas. Este método permite visualizar cuanto se debe vender, cuanto se debe producir o cuanto se debe comprar según sea el caso para que la empresa obtenga las ganancias optimas y suficientes para competir en el mercado. 

En Base a esta importancia El método simplex ha tenido diversas aplicaciones en las industrias especialmente en el área de transporte, en la parte de inventarios y en lo empresarial en general.


VENTAJAS DEL MÉTODO SIMPLEX

1) Es un Método heurístico. Se basa en consideraciones geometricas y no requiere el uso de derivadas de la función objetivo.   

2) Es de gran eficiencia incluso para ajustar gran número de parámetros. 

3) Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente.

4) Es fácil implementar y usar, y sin embargo tiene un alta eficacia.

DESVENTAJAS DEL MÉTODO SIMPLEX

Converge más lentamente que otros métodos, pues requiere más número de iteraciones. 

En el caso de que la función tenga todas sus variables básicas positivas, y además las restricciones sean de desigualdad "≤", al hacer el cambio se quedan negativas y en la fila del valor de la función objetivo se quedan positivos, por lo que se cumple la condición de parada, y por defecto el valor óptimo que se obtendría es 0.


VARIABLES DE HOLGURA Y EXCESO

    Aplica para las restricciones del tipo (≥ y ≤), donde el lado derecho de la desigualdad representa el limite sobre la disponibilidad de un recurso y el lado izquierdo representa la utilización de ese recurso limitado que hacen las variables del modelo. Esto quiere decir que una holgura representa la cantidad disponible del recurso que excede a la utilización que se le da. En la conversión de este tipo de desigualdad se añade una variable de ajuste (Si) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: 3X1 + 2X2 ≥ 6, su equivalente seria, 3X1 + 2X2 + S1 = 6.

VARIABLE ARTIFICIAL / MÉTODO DE LA "M"

Una variable artificial es un truco matemático para convertir inecuaciones ">=" en ecuaciones, o cuando aparecen igualdades en el problema original, la característica principal de estas variables es que no deben formar parte de la solución, dado que no representan recursos. El objetivo fundamental de estas variables es la formación de la matriz identidad.

Estas variables se representa por la letra "A", siempre se suman a las restricciones, su coeficiente es M (por esto se le denomina Método de la M grande, donde M significa un número demasiado grande muy poco atractivo para la función objetivo), y el signo en la función objetivo va en contra del sentido de la misma, es decir, en problemas de Maximización su signo es menos (-) y en problemas de Minimización su signo es (+), repetimos con el objetivo de que su valor en la solución sea cero (0).


A modo general, el método Símplex consta de los pasos siguientes:

• Determinar una solución básica factible inicial.
• Definir una variable de entrada empleando la condición de factibilidad. El algoritmo se detiene cuando ya no hay una variable de entrada.
• Seleccionar una variable de salida empleando la condición de factibilidad.
• Determinar las nuevas soluciones básicas factibles aplicando los cálculos apropiados a través de la metodología Gauss-Jordan.

TIPO DE OPTIMIZACIÓN

El algoritmo Simplex para resolver modelos de programación lineal requiere que el modelo este en su forma estándar. Lo que se hace es convertir el modelo a la forma estándar. Esto se logra introduciendo nuevas variables, algunas de las cuales reemplazaran a las variables originales.

• Para cada restricción del tipo ≤ se introduce una nueva variable de holgura (slack variable) Si que se suma al primer miembro y la desigualdad se convierte en igualdad; se añade la restricción de signo a la nueva variable si ≥ 0.

• Para cada restricción del tipo ≥ se introduce una nueva variable de exceso (excess variable) ei que se resta al primer miembro y la desigualdad se convierte en igualdad; se añade la restricción de signo a la nueva variable ei ≥ 0

El objetivo del método consistirá en optimizar el valor de la función objetivo. Sin embargo se presentan dos opciones: obtener el valor óptimo mayor (maximizar) u obtener el valor óptimo menor (minimizar).

Además existen diferencias en el algoritmo entre el objetivo de maximización y el de minimización en cuanto al criterio de condición de parada para finalizar las iteraciones y a las condiciones de entrada y salida de la base. Así:

1. Objetivo de maximización

• Condición de parada: cuando en la fila Z no aparece ningún valor negativo.

• Condición de entrada a la base: el menor valor negativo en la fila Z (o el de mayor valor absoluto entre los negativos) indica la variable Pj que entra a la base.

• Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale se determina mediante el menor cociente P0/Pj de los estrictamente positivos.

2. Objetivo de minimización

• Condición de parada: cuando en la fila Z no aparece ningún valor positivo.

• Condición de entrada a la base: el mayor valor positivo en la fila Z indica la variable Pj que entra a la base.

• Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale se determina mediante el menor cociente P0/Pj de los estrictamente negativos.

FORMATO ESTÁNDAR

RESTRICCIONES ( ≥ ; ≤ )

Las inecuaciones deben convertirse en ecuaciones, o sea, convertir las desigualdades en igualdades.

Sumar o restar una variable de holgura o supuesta (Si) teniendo en cuenta el sentido de la inecuación; las restricciones del tipo (≤) se le suma una variable de holgura; las del tipo (≥) se le resta.

Todas las variables son no negativas, si una variable es irrestricta se usa la sustitución Yi = Y ´i – Y´´i. Una variable negativa se hace no negativa multiplicando por -1 a la variable en la función objetivo y las restricciones.

FUNCIÓN OBJETIVO

Se debe agrupar las variables de un solo lado de la ecuación y sumarle las variables de holgura de las restricciones, pero en este caso tendrán un valor de cero (0S).

Ejemplo: 

MÉTODO DE LA GRAN M

a) Convertir las restricciones a ecuaciones: 

• A todas y cada una de las restricciones del tipo “≤” se les suma una variable de “holgura” ( Si ).

• A todas y cada una de las restricciones del tipo “=” se les suma una variable “artificial” ( Ai ).

•  A todas y cada una de las restricciones del tipo “≥” se les resta una variable de “exceso” ( Si ) y además se les suma una variable “artificial” ( Ai ).

b) Todas las variables de “holgura” y de “exceso” se suman a la Función Objetivo con coeficiente cero. 

c) Todas las variables de “artificiales” ( Ai ) se suman a la Función Objetivo con un coeficiente diferente de cero.

	V/b que aparece	Función objetivo
≥	-S+A	Min = +M
=	+A	Max = -M
≤	+S

Ejemplo:

          

PROCEDIMIENTO PASO A PASO

Consideraciones Generales:

1. En general se recurre a las variables artificiales cuando al menos una de las restricciones en el modelo matemático original es del tipo mayor o igual (≥), esto con el fin de obtener la solución básica factible inicial.

2. Las variables artificiales proporcionan un artificio matemático para obtener una primera solución básica. Estas variables son ficticias y no tienen una interpretación física directa en términos del problema original (costos).

3. Se debe expresar el modelo original en la forma estándar (llevar las desigualdades a igualdades).

4. Sumar del lado izquierdo de cada ecuación, correspondiente a las restricciones del tipo mayor o igual (≥) una variable (artificial) no negativa. Dicha adición no causa una alteración en las restricciones.

5. Los indicadores de las variables artificiales son todos negativos o iguales a cero(0) en la tabla final. Esto siempre debe ser válido para una solución óptima(factible).

6. Una vez, conocidas las consideraciones generales procedemos con los pasos normales del método simplex.

Algoritmo del Método de la Técnica de la Gran M.

1. ARMAR LA TABLA SIMPLEX

• Pasar a la forma estándar el modelo matemático, restando las variables de excedente (holgura o flojas) por cada restricción.

• Agregar variables artificiales en cada restricción.

• Penalizar las variables artificiales en la funcion objetivo asignando coeficiente "M" (minimizar = +M, maximizar= -M), los coeficientes para las variables de holgura son nulos y M para las variables artificiales, en donde M es un numero imposiblemente elevado para asegurar que las variables artificiales se excluirán dela solución óptima. 

• TABLA PARA CÁLCULOS: En las columnas aparecerán todas las variables del problema  y en las filas, los coeficientes de las ecuaciones obtenidas.

• En la Función objetivo no deben aparecer variables básicas, por lo que se hace necesario eliminar las variables artificiales de la F.O. (Quitas las M de las Columnas Artificiales). Para retirar las M de las columnas de variables artificiales se suman M veces (coeficientes de la fila1 + fila 2 + fila 3+… fila n ) a la fila de la función objetivo. Esto da como resultado la tabla inicial.

2. 1ra ITERACIÓN:

• Determinar cuál variable debe entrar a la solución. Se reemplaza el valor de M en las variables no básicas. En un caso de maximización será la variable con el coeficiente mas negativo, mientras en un caso de minimización será la variable con el coeficiente mas positivo. Se le denomina columna pivote.

• Determinar cuál variable debe salir de la solución. Para encontrar la variable de holgura que tiene que salir de la solución, se divide cada término de la columna solución (valores constantes) entre el término correspondiente de la columna pivote, siempre que  estos últimos sean mayores que cero. El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo,  indica la fila de la variable  de holgura que sale de la base. Se le denomina fila pivote.

• 1ra operación sobre las fila pivote. Los nuevos coeficientes de la fila pivote se obtienen dividiendo todos los coeficientes de la fila pivote entre el elemento pivote, y se pasa a una nueva plantilla.

• Se buscan los nuevos valores de las filas de Z y de las variables básicas restantes usando la formula: FV-(CP*FN). FV representa la fila vieja, o sea la fila que se desea cambiar; CP es el coeficiente pivote, que son los valores en la columna pivote; FN es la fila nueva, donde se encuentran los nuevos coeficientes de la fila pivote.

3. El proceso termina una vez se hayan eliminado los valores negativos en Z, encontrando de este modo una solución al problema. En caso contrario, se debe repetir cada uno de los pasos expresados en la primera iteración hasta encontrar una solución. 

EJEMPLO

	VARIABLE QUE APARECE	FUNCIÓN OBJETIVO
≥	-S+A	MIN= +M
=	+A	MAX= -M
≤	+S

ARMAR LA TABLA SIMPLEX

convertir las inecuaciones en ecuaciones agregando variables de holgura y/o artificiales según el sentido de la restricción, e igualar la función objetivo a cero.

En las columnas aparecerán todas las variables del problema  y en las filas, los coeficientes de las ecuaciones obtenidas:

v. básicas	Z	X1	X2	S1	S2	A1	SOLUCIÓN
Z	1	-5	-6	0	0	M	0
A1	0	-2	3	0	0	1	3
S1	0	1	2	1	0	0	5
S2	0	6	7	0	1	0	3

En la Función objetivo no deben aparecer variables básicas, por lo que se hace necesario eliminar las variables artificiales de la F.O.

(-M) A1	0	-2	3	0	0	1	3
(0) S1	0	1	2	1	0	0	5
(0) S2	0	6	7	0	1	0	3

A1 =  0       2M            -3M           0              0             -M                -3M

Z   =   1         -5               -6            0              0             M                     0

Z   =   1     -5+2M       -6-3M          0              0             0                 -3M 

v. básicas	Z	X1	X2	S1	S2	A1	SOLUCIÓN
Z	1	-5+2M	-6-3M	0	0	0	-3M
A1	0	-2	3	0	0	1	3
S1	0	1	2	1	0	0	5
S2	0	6	7	0	1	0	3

Determinar cuál variable debe entrar y cual debe salir de la solución. 

Se reemplaza el valor de M en las variables no básicas y se escoge la variable con el coeficiente mas negativo. Esta será la columna pivote:

X1=  -5+2(1000)= 1995

X2=   -6-3(1000)= -3006

Se dividen los coeficientes de la columna solución entre los coeficientes pivote. El de menor valor positivo será la variable que sale. Esta será la fila pivote:

A1= 3/3=1

S1 = 5/2 = 2,5

S2 = 3/7= 0,4

v. básicas	Z	X1	c. pivote  X2	S1	S2	A1	SOLUCIÓN
Z	1	-5+2M	-6-3M	0	0	0	-3M
A1	0	-2	3	0	0	1	3
S1	0	1	2	1	0	0	5
f. pivote  S2	0	6	7	0	1	0	3

Determinar el valor de la nueva fila, dividiendo la fila que sale entre su coeficiente pivote:

0 /7          6/7          7/7            0/7             1/7              0/7               3/7

   0          0,86           1               0             0,14               0               0,43

X2	0	0,86	1	0	0,14	0	0,43

Se buscan los nuevos valores de las filas de Z y de las variables básicas restantes usando la formula: FV-(CP*FN)

Z = FV:    1            -5+2M          -6-3M            0                0                  0              -3M

       CP:-6-3M          -6-3M        -6-3M       -6-3M        -6-3M          -6-3M        -6-3M

       FN:    0               0,86               1                0               0,4               0               0,43 

                  1        0,16+4,58M         0             0        0,84+0,42M       0         2,58-1,71M

El procedimiento se repite para A1 y S1.

v. básicas	Z	X1	X2	S1	S2	A1	SOLUCIÓN
Z	1	0,16+4,58M	0	0	0,84+0,42M	0	2,58-1,71M
A1	0	-4,58	0	0	-1,2	1	1,71
S1	0	-0,72	0	1	-0,8	0	4,14
X2	0	0,86	1	0	0,14	0	0,43

Una vez eliminados los valores negativos en Z, se ha encontrado respuesta al problema.

PRUEBA: 2,58-1,71M

Por se M un número muy grande, no se toma, quedando solo 2,58. Se toma la función objetivo y reemplazamos X2 por 0,43:

Z= 5X1+6X2

2,58=5(0)+6(0,43)

2,58=2,58