Metodo simplex

Solo disponible en BuenasTareas
  • Páginas : 12 (2810 palabras )
  • Descarga(s) : 4
  • Publicado : 26 de mayo de 2010
Leer documento completo
Vista previa del texto
El método del simplex fue creado en 1947 por el matemático George Dantzig .
El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables. Está basado fundamentalmente en que la solución óptima está asociada siempre con un punto extremo del espacio de soluciones.
El álgebra matricial y el proceso de eliminación deGauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.
Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso interativo que principia en un punto extremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega porúltimo al punto óptimo.
Existen reglas que rigen la selección del siguiente punto extremo del método simplex:
1. El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad.
El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremoadyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.
El método Simplex es un procedimiento repetido 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 enbuscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono. Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución. El método Simplex 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 faumenta.
Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más común el método de las DosFases.
Se deben cumplir las siguientes condiciones:
1. El objetivo es de la forma de maximización o de minimización.
2. Todas las restricciones son de igualdad.
3. Todas las variables son no negativas.
4. Las constantes a la derecha de las restricciones son no negativas.
Si en el modelo deseamos minimizar, podemos dejarlo tal y como está, pero deberemos tener en cuenta nuevoscriterios para la condición de parada (deberemos parar de realizar iteraciones cuando en la fila del valor de la función objetivo sean todos menores o iguales a 0), así como para la condición de salida de la fila. Con objeto de no cambiar criterios, se puede convertir el objetivo de minimizar la función F por el de maximizar F·(-1).
Ventajas: No deberemos preocuparnos por los criterios de parada, ocondición de salida de filas, ya que se mantienen.
Inconvenientes: 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.Solución: En la realidad no existen este tipo de problemas, ya que para que la solución quedara por encima de 0, alguna restricción debería tener la condición "≥", y entonces entraríamos en otro modelo.
Deberemos preparar nuestro modelo de forma que los términos independientes de las restricciones sean mayores o iguales a 0, sino no se puede emplear el método Simplex. Lo único que habría que...
tracking img