MATEMATICA

MÉTODO GRÁFICO

Algoritmo simplex

En optimización matemática, el término algoritmo Simplex habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo Simplex primal fue desarrollado por el matemático norteamericano George Danzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. Un algoritmo Simplex es un algoritmo de pivote.

Un método llamado de manera similar, pero no relacionado al anterior, es el método Nelder-Mead (1965) o método de descenso (o ascenso) simplex; un método numérico que busca un mínimo (o máximo) local de una función cualquiera examinando en cada paso los vértices de un simplex.

El algoritmo del método Simplex fue elegido como uno de los 10 algoritmos más importantes del s. xx (SIAM News, Volumen 33, Numero 4).

Tipos de soluciones al problema de programación lineal

Los principales tipos de solución: Óptima Única: este tipo de solución es la más común una vez que el modelo ha sido formulado como un problema real de programación lineal. Se da cuando sólo existe un punto extremo del conjunto de soluciones factibles que hace posible encontrar el valor óptimo de Z. Optima Múltiple (Alterna): esto ocurre cuando la recta de la función objetivo es paralela a alguna de las restricciones; entonces todos los puntos que están sobre la recta son soluciones óptimas del modelo. Como una recta tiene un número infinito de puntos, hemos encontrado un número infinito de soluciones óptimas equivalentes. De otra manera se dice que el modelo tiene soluciones óptimas alternativas. No Acotada (ilimitada o Indeterminada): se presenta cuando una o más variables y la función objetivo toman un valor ilimitado, cumpliendo con las restricciones estructurales. Cuando se obtiene solución ilimitada es debido a una de las siguientes causas:

a. Omisión de una o más restricciones

b. Fallas en la formulación

c. Errores en el valor de los parámetros.

Lo que indica que ningún problema real de programación lineal tiene este tipo de solución y cuando se presenta es porque se ha cometido alguno de los errores descritos.

Infectable (sin solución): esto ocurre cuando no pueden encontrarse soluciones que, además de cumplir con las restricciones estructurales, cumplan con la condición de no negatividad de las variables (cuando en el tablero óptimo queda una variable artificial en la base). Geométricamente, esto implica que la región de los puntos que cumplen todas las restricciones se halla fuera del primer cuadrante. Cuando se obtiene solución infactible se ha cometido alguno de los errores descritos en soluciones no acotadas.

Degenerada (Degradada): se da cuando en un tablero del Simplex una variable básica toma el cero en lugar de un valor positivo; este caso se presenta normalmente cuando se escoge arbitrariamente

...