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

...