Método Simplex
Introducción
El método Simplex o algebraico, se basa en la metodología de Gauss
Jordan para resolver ecuaciones lineales simultáneas.
Fue desarrollado por George Dantzig en 1947 y desde entonces ha
encontrado numerosas aplicaciones para la solución de problemas de
programación lineal.
Parte de colocar la solución inicial en el origen y de ahí en cada
iteración se va moviendo a otro de los vértices del problema, hasta
llegar al punto que es la solución del mismo, donde la función objetivo
se haya optimizado.
Etapas del método Simplex Consta de las siguientes etapas
• Etapa inicial: En esta fase se inicia el problema hasta tener
completa la primera tabla Simplex, la cual coloca la solución inicial en
el origen, donde todas las variables de decisión valen cero.
• Etapa iterativa: En esta etapa se obtiene una solución diferente en
cada iteración, la cual debe ser mejor que la anterior. Lo que hace el
método Simplex es pasar de un vértice a otro adyacente, hasta llegar
a la solución óptima.
• Etapa de optimalidad: En esta se verifica si se ha logrado la solución
óptima, lo cual se dará cuando la solución encontrada sea mejor que
la de los vértices adyacentes al del punto óptimo.
Izar Landeta, J. M. (2019). Modelos matemáticos para la toma de
decisiones: ( ed.). México, Instituto Mexicano de Contadores Públicos.
Recuperado de https://elibro.net/es/ereader/umecit/123841?page=77.
Procedimiento del métoo Simplex.
A continuación, se presenta un procedimiento para la metodología
Simplex, que consta de los pasos siguientes:
1. Incorporar en las ecuaciones de las restricciones variables de
holgura (representadas por Hi) y ficticias (denotadas por Fi),
según el tipo de cada restricción, conforme a la tabla 3.3:
Tabla 3.3 : Coeficientes de las variables de holgura y ficticias
Tipo de restricción Coeficiente de la Coeficiente de
variable de la variable
holgura ficticia
Menor o igual que (≤) +1 0
Igualdad (=) 0 +1
Mayor o igual que (≥) -1 +1
Aproximadamente igual +1 y -1 0
(≈)
En las restricciones de tipo menor o igual que (≤), se supone
que al lado izquierdo de la desigualdad le falta algo para
hacerse igual al lado derecho. Eso que falta es justamente la
variable de holgura Hi; mientras que para las restricciones del
tipo mayor o igual que (≥), se supone lo contrario, que al lado
izquierdo le sobra algo para igualarse al lado derecho, y lo que
sobra es precisamente la variable de holgura H que en este
caso va restando.
En cambio, en las restricciones de igualdad (=), no se agrega
ninguna variable de holgura, pero sí una ficticia con coeficiente
+1, para completar la parte identidad de la tabla inicial.
2. Incluir las variables de holgura y ficticias en la ecuación de la
función objetivo. Las variables de holgura llevan un coeficiente
cero y las ficticias +M o -M, dependiendo si se trata de un caso
de maximización (-M) o minimización (+M).
3. Armar la primera tabla Simplex, la cual debe contener un
renglón por cada restricción, además de los renglones de
variables, objetivo e índice; así como la parte básica de la tabla,
que es donde se presenta cada solución de la iteración
respectiva.
Izar Landeta, J. M. (2019). Modelos matemáticos para la toma de
decisiones: ( ed.). México, Instituto Mexicano de Contadores Públicos.
Recuperado de https://elibro.net/es/ereader/umecit/123841?page=78.
Para la parte básica van las constantes de las restricciones en la
columna de constantes y en la columna de variables, van aquellas
que tengan en cada renglón un coeficiente +1, sin considerar a las
variables de decisión, solo a las de holgura y ficticias.
Por otra parte, para obtener el renglón índice, se utiliza la siguiente
ecuación:
Dónde: EIj = Elemento índice de la columna j Cij = Elemento del
renglón i y columna j COi = Elemento de la columna objetivo y el
renglón i ROj = Elemento del renglón objetivo y la columna j
Esta fórmula aplica para casos de maximización, aunque en caso de
que el problema sea de minimización, la fórmula es la misma pero
con los signos cambiados, es decir: Cabe mencionar que cuando hay
variables ficticias incorporadas en las restricciones, habrá dos partes
del renglón índice, una numérica y otra de términos en M, que han
sido introducidos al problema con las variables ficticias, lo cual no
representa ningún problema, ya que más adelante, al transcurrir las
iteraciones, el método tenderá a eliminar las variables ficticias y con
ello también la parte con términos en M del renglón índice.
4. Pasar a otra iteración. En la primera tabla la solución es el origen,
por lo cual nunca será la óptima y por lo tanto, comienza en este paso
la etapa iterativa, al definir la columna clave, que será aquella que
tenga el número índice más negativo. Para aquellos casos en que
haya dos partes del renglón índice, se toma primero la parte M y
luego se sigue con la numérica. Una vez identificada la columna
clave, sigue definir el renglón clave, que será aquel de las
restricciones que tenga el menor cociente, al dividir el elemento de la
columna de constantes entre el de la columna clave.
5. Es la prueba de optimalidad. La tabla será óptima si al terminar la
iteración anterior, ya no hay números negativos en el renglón índice.
En caso de ser así, la tabla ya contiene la solución óptima, la cual
puede verse en su parte básica, pero si no, deberá irse a otra
iteración, volviendo a repetir el paso 4 hasta llegar a la tabla óptima.
Izar Landeta, J. M. (2019). Modelos matemáticos para la toma de
decisiones: ( ed.). México, Instituto Mexicano de Contadores Públicos.
Recuperado de https://elibro.net/es/ereader/umecit/123841?page=80.
Documento del profe
Programación lineal método Simplex
Conversión de desigualdades a ecuaciones
En términos generales, se puede decir que cualquier fenómeno en que interviene un
número determinado de variables no negativas (es decir, variables cuyo valor es
positivo o cero), que se pueden ligar entre sí mediante relaciones de desigualdad o
igualdad y que reflejen las limitaciones o restricciones que el fenómeno presenta con
miras a optimizar un objetivo, puede ser formulado como un modelo de programación
matemática. Como ya explicamos anteriormente, si las restricciones como la función
objetivo se pueden enunciar mediante expresiones lineales, estamos frente a un
campo particular de la programación matemática denominada “programación lineal”.
La tabla Simplex
De entre todos los algoritmos destaca por su importancia histórica y práctica el
método Simplex.
Dicho método fue desarrollado por Dantzig en 1947, alcanzando un éxito inusitado en
las décadas posteriores con el desarrollo de los computadores. El conocimiento básico
de dicho método ayuda a la comprensión de las diferentes formas de resolución de
programas lineales.
El método simplex es para uso computacional debido a la complejidad de los caculos
que en el intervienen. Pero como forma general se puede decir que la programación
lineal trata de convertir desigualdades del tipo = (=) en una ecuación para facilitar el
resultado en la toma de decisiones. En este apartado veremos la forma básica de la
transformación de una desigualdad en una ecuación.
