EL MTODO SIMPLEX.
El Mtodo Simplex es un mtodo analtico de solucin de problemas de
programacin lineal capaz de resolver modelos ms complejos que los resueltos
mediante el mtodo grfico sin restriccin en el nmero de variables.
El Mtodo Simplex es un mtodo iterativo que permite ir mejorando la solucin en
cada paso. La razn matemtica de esta mejora radica en que el mtodo consiste
en caminar del vrtice de un poliedro a un vrtice vecino de manera que aumente o
disminuya (segn el contexto de la funcin objetivo, sea maximizar o minimizar),
dado que el nmero de vrtices que presenta un poliedro solucin es finito siempre
se hallar solucin.
El Mtodo Simplex hace uso de la propiedad de que la solucin ptima de un
problema de Programacin Lineal se encuentra en un vrtice o frontera del dominio
de puntos factibles (esto ltimo en casos muy especiales), por lo cual, la bsqueda
secuencial del algoritmo se basa en la evaluacin progresiva de estos vrtices hasta
encontrar el ptimo. Cabe destacar que, para aplicar el Mtodo Simplex a un modelo
lineal, este debe estar en un formato especial conocido como formato estndar.
Este famossimo mtodo fue creado en el ao de 1947 por el estadounidense
George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el nimo de
crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.
QUE ES UNA MATRIZ IDENTIDAD?
Una matriz puede definirse como una ordenacin rectangular de elementos, (o
listado finito de elementos), los cuales pueden ser nmeros reales o
complejos, dispuestos en forma de filas y de columnas.
La matriz idntica o identidad es una matriz cuadrada (que posee el mismo
nmero tanto de columnas como de filas) de orden n que tiene todos los
elementos diagonales iguales a uno (1) y todos los dems componentes iguales
a cero (0), se denomina matriz idntica o identidad de orden n, y se denota por:
La importancia de la teora de matrices en el Mtodo Simplex es fundamental,
dado que el algoritmo se basa en dicha teora para la resolucin de sus
problemas.
OBSERVACIONES IMPORTANTES AL UTILIZAR MTODO SIMPLEX.
VARIABLES DE HOLGURA Y EXCESO.
El Mtodo Simplex trabaja basndose en ecuaciones y las restricciones iniciales
que se modelan mediante programacin lineal no lo son, para ello hay que
convertir estas inecuaciones en ecuaciones utilizando unas variables
denominadas de holgura y exceso relacionadas con el recurso al cual hace
referencia la restriccin y que en el tabulado final representa el "Slack or surplus"
al que hacen referencia los famosos programas de resolucin de investigacin
de operaciones, estas variables adquieren un gran valor en el anlisis de
sensibilidad y juegan un rol fundamental en la creacin de la matriz identidad
base del Simplex.
Estas variables suelen estar representadas por la letra "S", se suman si la
restriccin es de signo "<= " y se restan si la restriccin es de signo ">=".
VARIABLE ARTIFICIAL / MTODO DE LA "M"
Una variable artificial es un truco matemtico para convertir inecuaciones ">="
en ecuaciones, o cuando aparecen igualdades en el problema original, la
caracterstica principal de estas variables es que no deben formar parte de la
solucin, dado que no representan recursos. El objetivo fundamental de estas
variables es la formacin de la matriz identidad.
Estas variables se representan por la letra "A", siempre se suman a las
restricciones, su coeficiente es M (por esto se le denomina Mtodo de la M
grande, donde M significa un nmero demasiado grande muy poco atractivo
para la funcin objetivo), y el signo en la funcin objetivo va en contra del sentido
de la misma, es decir, en problemas de Maximizacin su signo es menos (-) y en
problemas de Minimizacin su signo es (+), repetimos con el objetivo de que su
valor en la solucin sea cero (0).
PASOS DEL MTODO SIMPLEX.
Paso 1: modelacin mediante programacin lineal.
Paso 2: convertir las inecuaciones en ecuaciones.
Paso 3: definir la solucin bsica inicial.
Paso 4: definir la tabla simplex inicial.
Paso 5: realizar las iteraciones necesarias.
Mtodo Algebraico.
El mtodo algebraico es una forma de trabajar con el mtodo simplex, pero sin usar
las tablas, utiliza nicamente lgebra y lgica matemtica para hallar la solucin
ptima. Consta de los siguientes pasos:
1.
Determinar si existe una bsica factible inicial
2.
Determinar si existe una solucin bsica factible mejor. Si es as realizar el
siguiente paso, de otro modo, la solucin actual es optima
3.
Pasar a la siguiente solucin bsica factible, cambiando una variable bsica
por una no bsica, haciendo que todas las variables sean no negativas y
regresamos al paso 2
Este mtodo es poco aplicado porque llega a ser muy tardado y poco prctico, a
diferencia del simplex donde toda la informacin se almacena en tablas y las
operaciones de estas tablas son rpidas. Pero este mtodo trabaja muy rpido
cuando los sistemas de restricciones son muy pequeos y no hay que hacer tantos
movimientos entre los extremos de la regin factible.
El mtodo algebraico es un procedimiento con el que hemos estado relacionados
antes que conociramos siquiera las implicaciones del trmino optimizacin en la
vida de todo ingeniero industrial.
Cuando se estudian asignaturas, especialmente en carreras como las ingenieras,
los estudiantes muestran un particular inters en saber el Para qu? es necesario
dicho aprendizaje. Por medio del estudio del mtodo grfico se va a poder resolver
la inquietud de porque en cierta medida es importante manejar el lgebra.
Con el mtodo algebraico se va a hacer uso de todas las herramientas que utilizaste
para resolver sistemas de ecuaciones lineales, en algebra bsica vista en 9 hasta
la eliminacin de Gauss Jordn vista en los primeros semestres del ciclo bsico en
carreras relacionadas con el estudio de los nmeros.
Ahora bien, la mejor manera de dominar este mtodo es tener un buen dominio del
algebra y un pensamiento lgico matemtico, y obviamente mucha prctica, puesto
que como dice el adagio popular: La prctica hace al maestro
De acuerdo a consultas realizadas especficamente en el libro investigacin de
operaciones I de francisco Chediak, el cual recomiendo dado su terminologa y la
facilidad con la que se ejemplifican las temticas, tenemos los siguientes pasos para
resolver problemas de programacin lineal por medio del mtodo aqu citado:
Pasos para desarrollar el mtodo algebraico segn Chediak:
* Hallar una solucin bsica y factible (solucin inicial) * Expresar las inecuaciones
como ecuaciones.
* Hallar una variable bsica para cada ecuacin:
* Organizar el sistema de ecuaciones lineales
* Escoger la variable que entra.
* Escoger la variable que sale.
* Reorganizar el sistema de ecuaciones.
* Repetir los pasos 2,3, y 4 hasta encontrar la solucin.
Cuando se estudie el mtodo simplex se darn cuenta que no es ms que una
aplicacin iterada del mtodo algebraico y si dominan este ltimo les ser de mucha
ayuda a la hora de resolver problemas con el mtodo simplex.
La mejor manera de entender todos los mtodos relacionados en este caso con la
programacin lineal es llevndolos a la prctica, es por ello que mostrare diferentes
ejercicios obtenido de introduccin a la programacin lineal donde se relaciona el
mtodo grfico con el mtodo algebraico:
Ejemplos:
Bibliografa.
[Link]
[Link]
[Link]
[Link]
[Link]
