METODO SIMPLEX

METODO SIMPLEX

Fundamento Básico.

Simplex.

En geometría, un simplex o n-simplex es el análogo en n dimensiones de un triángulo. Es la envoltura convexa de un conjunto de (n + 1) puntos independientes afines en un espacio euclídeo de dimensión n o mayor, es decir, el conjunto de puntos tal que ningún m-plano contiene más que (m + 1) de ellos. Se dice de estos puntos que están en posición general. Un 0-símplex es un punto; un 1-símplex un segmento de una línea; un 2-símplex un triángulo; un 3-símplex es un tetraedro; y un 4-símplex es un pentácoron (en cada caso, con su interior).

El método simplex es un método que sirve para resolver problemas de programación lineal. Este método fue inventado por George Dantzig en el 1947. La primera formulación del método simplex fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.

Método Simplex

Es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Es un método numérico para optimización de problemas libres multidimensionales perteneciente a la clase más general de algoritmos de búsqueda. Según Rodríguez (2009) este Método “…comienza con alguna solución factible, y sucesivamente obtiene soluciones en las intersecciones que ofrecen mejores funciones de la función objetivo. Finalmente, este método proporciona un indicador que determina el punto en el cual se logra la solución óptima...” (p. 1)

Permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono. Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

Se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

El método simplex es muy eficiente en la práctica, en general, teniendo 2m a 3m iteraciones en la mayor parte (donde m es el número de restricciones de igualdad), y que convergen en la hora prevista para el polinomio de ciertas distribuciones de insumos al azar.

La aplicación del método del Simplex, se utiliza cuando el problema es de un tamaño suficientemente grande.

Está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación (el número de no-cero es pequeño).

Hay implementaciones del método simple para la solución de problemas de programación lineal con las matrices de restricción escasa.

Se han desarrollado diversas variantes del método simplex que tienen en cuenta las particularidades de las diversas clases especiales de problemas de programación lineal (problemas de bloque, los problemas de transporte y otros).

Formulación.

La representación matemática de un modelo de programación lineal (llamada Forma General de representación) es:

1. Max (ó Min) Z = C1 X1 + C2 X2 + . . . + Cj Xj

2. sa: a11 x1 + a12 x2 + . . . + a1j xj <= (>= ó =) b1

a21 x1 + a22 x2 + . . . + a2j xj <= (>= ó =) b2

. . . . . . . .

. . . . . . . .

. . . . . . . .

ai1 x1 + ai2 x2 + . . . + aij xj <= (>= ó =) bi

3. X1 , X2 , … , Xj >= 0 j = 1, 2, 3, ... n

Fuente: http://mathworld.wolfram.com/SimplexMethod.html (2010)

Como podemos ver, el Modelo consta de las TRES partes fundamentales que son:

1. Función Objetivo (FO).

2. Matriz de Restricciones Funcionales ó Tecnológicas.

3. Restricción de Factibilidad o de No-Negatividad.

Para en el que:

Z = valor de la medida global de efectividad (objetivo por lograr).

Xj = nivel de la actividad j (para j = 1,2,...,n).

Cj = incremento (o decremento) en Z que resulta al aumentar (o disminuir) una unidad en el nivel de la actividad j.

bi = cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,...,m).

aij = cantidad del recurso i consumido por cada unidad de la actividad j

En la representación de ambos Modelos, Canónico y Estándar, hay que hacer notar que los coeficientes de la función objetivo cambiarán de signo pues dicha función se iguala con cero antes de proceder a su solución por medio del método Simplex, es decir, de su representación clásica en Forma General:

Max (ó Min) Z = C1 X1 + C2 X2 + . . . + Cj Xj

Pasaríamos a su representación en Canónico o Estándar de la siguiente manera:

Max (ó Min) Z – C1 X1 – C2 X2 – . . . – Cj Xj = 0

Condiciones

• El objetivo es de la forma de maximización o de minimización.

• Todas las restricciones son de igualdad.

• Todas las variables son no negativas.

• Las constantes a la derecha de las restricciones son no negativas.

Proceso

El sistema es típicamente no determinado (el número de variables excede el número de ecuaciones)

La diferencia entre el número de variables y el número de ecuaciones nos da los grados de libertad asociados con el problema. Cualquier solución, óptima o no, incluirá un número de variables de valor arbitrario. El algoritmo simplex usa cero como valor arbitrario, y el número de variables con valor cero es igual a los grados de libertad.

Valores diferentes de cero son llamados variables básicas, y valores de cero son llamadas variables no básicas en el algoritmo simplex.

Esta forma simplifica encontrar la solución factible básica inicial, dado que todas las variables de la forma estándar pueden ser elegidas para ser no básicas (cero), mientras que todas las nuevas variables introducidas en la forma aumentada, son básicas (diferentes de cero), dado que su valor puede ser calculado trivialmente (para ellas, dado que la matriz problema aumentada en diagonal es su lado derecho)

En cada una de las desigualdades que se plantean en el modelo matemático de programación lineal, se plantean desigualdades de <, >, ≤, ≥, ó =

Estas desigualdades se convierten en igualdades completando con variables de holgura si se trata de <, >; en el caso de que sea ≤, ó ≥, se completa con variables de excedente , estas con signo negativo ya que como su nombre lo indica, es una cantidad que esta de excedente y hay que quitar para convertirla en igualdad, en caso se maneje el =, se manejan las variables artificiales.

Los pasos método simplex son: (Fuente: http://www.investigacion-operaciones.com/Metodos_Solucion_PL.htm)

1. Determinar una solución básica factible inicial.

2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nueva solución básica factible inicial.

3. Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.

4. Seleccionar las variables de holgura como las variables básicas de inicio.

5. Selecciona una variable que entra de entre las variables no básicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.

6. Realizar el paso iterativo.

a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote.

b) Se determina la variable básica que sale; para esta, se toma cada coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación.

c) Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces

renglón pivote nuevo = renglón pivote antiguo/ numero pivote

para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente fórmula:

renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivote nuevo)

cuando el coeficiente es negativo se utiliza la fórmula:

renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivote nuevo)

Ejemplo (fuente: http://www.slideshare.net/eileen017/el-metodo-simplex

...