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óngeneral. 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 elverano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.
Método Simplex
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 siguientepropiedad: 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 deinsumos 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.
Fuente: http://mathworld.wolfram.com/SimplexMethod.html (2010)
Como podemos ver, el Modelo consta de las TRES partes fundamentales queson:
Función Objetivo (FO).
Matriz de Restricciones Funcionales ó Tecnológicas.
Para en el que:
aij = cantidad del recurso i consumido por cada unidad de la actividad j
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 laderecha 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 usacero 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…