Metodo Simplex

Método Simplex

El método Simplex nace a fines de la década del 40 como herramienta para resolver a los cada vez más complejos planteos de programación lineal que se fueron encontrando, más que nada en la industria bélica, que con la creciente carrera armamentística y el avance exponencial de la tecnología generaba planteos con una excesiva cantidad de variables, haciendo imposible suresolución en forma gráfica.
El Simplex es un método iterativo, lo cual quiere decir que consiste en un conjunto de pasos iguales que se repiten hasta lograr un resultado.
A su vez, es un método algebraico basado en las consideraciones geométricas antes vistas.

Como requisitos, el Simplex precisa:

1. Un sistema de inecuaciones. Si llegara a haber una ecuación dentro del sistema, es precisodesdoblarla en dos inecuaciones.
2. Los términos independientes de las inecuaciones no deben ser negativos. De ser así, se debe multiplicar a la inecuación por –1.
3. Las variables participantes nunca deben ser negativas.
4. Una función económica a optimizar.

Sólo va a considerar a los vértices del polígono, o lo que es lo mismo, los puntos donde dos ecuaciones son iguales. Para hallarestos puntos utiliza el método algebraico Gauss – Jordan para resolución de ecuaciones.

Variables auxiliares

En principio, el método Gauss – Jordan no puede trabajar con inecuaciones, sino con ecuaciones. Para ello, el método Simplex debe transformar a las inecuaciones en ecuaciones, utilizando variables auxiliares de holgura o superávit[1] (+[pic] ó – [pic]).
Ahora bien, el método Gauss– Jordan precisa tener una matriz unidad[2] como parte del sistema para comenzar a operar. Si todas las variables auxiliares del sistema son de holgura (++[pic]), entonces no hay problema, ya que la matriz unidad está conformada por las variables +[pic]i, pero si llegara a aparecer al menos una variable de superávit (–[pic]), es preciso el uso de otra variable auxiliar para obtener la matriz unidad.Dicha variable (+μ) es llamada variable artificial[3].
Ambas modificaciones a las inecuaciones deben ser presentadas dentro del funcional.
Así, las variables de holgura o superávit no producen modificaciones dentro del funcional (no generan ni beneficios ni pérdidas), por ello van multiplicadas por CERO.
Las variables artificiales, al no representar nada real sino ser un artificio algebraicopor método, deberán estar multiplicadas por un valor M (que tiende a ∞) de forma tal que evite que +μi sean consideradas óptimas como soluciones.

En resumen

• Para inecuaciones ≤, +[pic]
• Para inecuaciones ≥, –[pic] +μ
• Para maximizar beneficios, [pic]
• Para minimizar costos, [pic]

Una vez que todos estos requisitos fueron alcanzados, se conforma una matriz de lasiguiente manera:

|Cj | | | | | | | | | | |Ck |Xk |Bi |X1 |… |Xn |[pic]1 |… |[pic]n |μ |… |Bi/ai | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |Zj | | | | | | | | | | | |Zj – Cj | | | | | | | | | | | |
• Xk: Vector base. Es donde figuran todas las variables que conforman la solución actual. A dichas variables se las denomina variables básicas.
• Ck:Contiene los coeficientes que aparecen en el funcional de las variables básicas.
• Cj: Contiene los coeficientes que aparecen en el funcional de todas las variables participantes en el problema.
• Bi: Vector de disponibilidades. Este vector no puede tener nunca valores negativos. En cada iteración indica la cantidad de cada elemento que se produce para obtener el valor del funcional actual.• X1 … Xn: Procesos competidores, los cuales son representados por una variable Xi cada uno.
• [pic] 1 … [pic] n: Variables de holgura o superávit participantes en el problema. Debe haber tantas variables de holgura o superávit como inecuaciones haya en el problema.
• μ: Variables artificiales participantes en el problema. Puede no haber ninguna. Debe haber tantas variables...