jueves, 28 de febrero de 2008

Metodo Simplex

El método gráfico demuestra que la PL óptima está siempre asociada con un punto extremo o de esquina, del espacio de soluciones. Esta idea conduce precisamente a la creación del método simplex. Básicamente, lo que hace el método simplex es trasladar la definición geométrica del punto extremo a una definición algebraica. Durante la presentación del método simplex, deberá tenerse en mente este detalle.

¿Cómo identifica el método simplex los puntos extremos en forma algebraica? Como paso inicial, el método simplex necesita que cada una de las restricciones esté en una forma estándar especial, en la que todas las restricciones se expresan como ecuaciones, mediante la adición de variables de holgura o de exceso, según sea necesario. Este tipo de conversión conduce normalmente a un conjunto de ecuaciones simultáneas donde el número de variables excede al número de ecuaciones, lo que generalmente significa que las ecuaciones dan un número infinito de puntos solución (compárese con el espacio de soluciones gráficas). Los puntos extremos de este espacio pueden identificarse algebraicamente por medio de las soluciones básicas del sistema de ecuaciones simultáneas. De acuerdo con la teoría del álgebra lineal, una solución básica se obtiene igualando a cero las variables necesarias con el fin de igualar el número total de variables y el número total de ecuaciones para que la solución sea única, y luego se resuelve el sistema con las variables restantes. Fundamentalmente, la transición del procedimiento gráfico al algebraico se basa en la validez de la siguiente relación importante:

puntos extremos = soluciones básicas

Al no tener un espacio de soluciones gráficas que nos guie hacia el punto óptimo, necesitamos un procedimiento que identifique en forma inteligente las soluciones básicas promisorias. Lo que hace el método simplex, es identificar una solución inicial y luego moverse sistemáticamente a otras soluciones básicas que tengan el potencial de mejorar el valor de la función objetivo. Finalmente, la solución básica correspondiente a la óptima será identificada, con lo que termina el proceso de cálculo. En efecto, el método símplex es un procedimiento de cálculo iterativo donde cada iteración está asociada con una solución básica.
La determinación de una solución básica en el método símplex, implica detalles tediosos de cálculo. Tales detalles no deben distraernos de la idea fundamental del método: generar soluciones básicas sucesivas, de manera que nos conduzcan al punto
- extremo óptimo. Todos los detalles de cálculo son secundarios a esta idea básica, y así es como debemos tratarlos.