Metodo Simplex

HISTORIA DEL METODO SIMPLEX
El método simplex , fue creado en el año de 1947 por el matemático George

Dantzing, con el fin de resolver problemas de programación lineal, en los cuales
intervienen tres o mas variables.
este procedimiento permite mejorar las respuestas paso a paso, con el fin de
alcanzar la solución optima de un problema.
La primera aplicación importante de este método ocurrió poco después del verano
de 1947, cuando J. Laderman resolvió, en la National Bureau of Standards, un
programa lineal de plantación de una dieta con nueve restricciones y 27 variables.
Usando calculadoras de escritorio, para resolver este problema se requirieron 120
días-hombre, y cuando con dificultad las hojas de datos fueron unidas entre sí,
semejaban un "mantel". Actualmente, usando la computadora y un programa del
método Simplex (TORA, MICROMANAGER, LINDO, PROLIN, QSB, otro) es fácil
resolver problemas de PL con muchas variables y muchas restricciones.
El problema de la resolución de un
sistema lineal de inecuaciones se
remonta, al menos, a Fourier,
después de quien nace el método de
eliminación de Fourier-Motzkin. La
programación lineal se plantea como
un modelo matemático desarrollado
durante la Segunda Guerra Mundial
para planificar los gastos y los
retornos, a fin de reducir los costos
al ejército y aumentar las pérdidas
del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas
industrias lo usaron en su planificación diaria. Los fundadores de la técnica
son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von
Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid
Kantoróvich, un matemático ruso, que utiliza técnicas similares en la economía
antes de Dantzig y ganó el premio Nobel en economía en1975. En 1979, otro
matemático ruso, Leonid Khachiyan, demostró que el problema de la
programación lineal era resoluble en tiempo polinomial. Más tarde, en
1984, Narendra Karmarkar introduce un nuevo método del punto interior para
resolver problemas de programación lineal, lo que constituiría un enorme avance en
los principios teóricos y prácticos en el área.
CONCEPTOS BÁSICOS DEL MÉTODO SIMPLEX
 La aplicación del método simplex presupone que se tiene un sistema de

restricciones lineales formado sólo por ecuaciones lineales. Esta
transformación puede ser llevada a cabo de una forma muy simple
introduciendo algunas variables adicionales, las cuales se denominan
variables de holgura. Estas variables se definen una para cada restricción y
si la misma tiene el signo ≤ la variable de holgura se adiciona y el signo fuera
≥ la variable de holgura se restara.
 Luego que se tiene un problema de Programación Lineal estándar, es decir,
todas las restricciones tienen signos de igualdad es necesario determinar la
solución básica factible inicial (S.B.F.I).
 Dado un sistema de m ecuaciones lineales con n variables (AX=b) con m<n
y rango r(A)=m. Si escogemos cualquier matriz no singular de orden mxm y
si todas las (n-m) variables no asociadas con estas columnas de la matriz
son iguales a cero, entonces la solución al sistema de ecuaciones resultante
es llamada una solución básica. Como la matriz A consta de n columnas se
puede definir la matriz B formada por m columnas linealmente
independientes de A, esta matriz la llamaremos matriz básica. Con las (n-m)
columnas restantes de A se puede construir otra matriz que se denominará
matriz no básica y la denotaremos por W. Entonces puede escribirse la matriz
A de la siguiente manera: A = (B, W).
 Las variables que forman parte de la matriz B se llaman variables básicas
(XB) y las que forman parte de la matriz W se llaman variables no
básica.( XW ), entonces el vector X está conformado por el conjunto de
variables básicas y no básicas, es decir, X = (XB, XW).
 Entonces el sistema de restricciones del problema de Programación
Lineal AX=b puede escribirse de la forma siguiente: AX=BXB + WXW = b. Si
asumimos que las variables no básicas tomarán valor cero, la expresión
anterior quedaría BXB =b. La expresión XB = B-1 b que se obtiene a partir
de la anterior, permitiría calcular la solución básica factible inicial.
PARA REALIZAR LA TABLA DEL MÉTODO SIMPLEX
El método simplex se desarrolla en la tabla simplex. Cada iteración requiere de una

tabla.
En la primera columna se escribirán los coeficientes de la función objetivo
correspondiente a las variables básicas, escribiendo en la segunda columna dichas
variables. La tercera columna indica los valores que toman las variables básicas en
la solución que se está representando mediante la tabla simplex. El resto de la
columnas representan los vectores Pj correspondientes a cada uno de los vectores
aj de la matriz A (Pj es el vector coordenado de cada vector aj respecto a la base
considerada). En la última fila de la tabla aparecen los valores Zj -Cj correspondiente
a cada vector aj. Los coeficientes Zj se determinan utilizando la siguiente expresión:
Zj =CBPj
PROCEDIMIENTO COMPUTACIONAL DEL MÉTODO SIMPLEX
El procedimiento iterativo en que se basa el método simplex puede resumirse en los

siguientes pasos:
 Paso1: Convertir las inecuaciones en ecuaciones con la utilización de las
variables de holgura.
 Paso 2: Determinar la solución básica factible inicial XB*, los valores Z*, Pj y
Zj - Cj y construir la tabla simplex que resuma toda la información sobre esta
solución inicial. La solución básica inicial debe tener la característica de que
la matriz básica debe ser unitaria. Esto facilita el cálculo de la matriz inversa.
 Paso 3: Examinar en la tabla simplex los valores de los coeficientes Zj – Cj.
Pueden presentarse las siguientes situaciones: Caso Máximo y Caso Mínimo.
VENTAJAS DEL MÉTODO SIMPLEX
 Es un método heurístico. Se basa en consideraciones geométricas y

no requiere el uso de derivadas de la función objetivo.
 Es de gran eficacia incluso para ajustar gran número de parámetros.
 Es fácil de implementar y usar, y sin embargo tiene una alta eficacia.
 Se puede usar con funciones objetivo muy sinuosas pues en las primeras
iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales
fácilmente.
DESVENTAJAS DEL METODO SIMPLEX
 Converge más lentamente que otros métodos pues requiere mayor número
de iteraciones.
CARACTERISTICAS DEL METODO SIMPLEX

Es aplicable a problemas de programación lineal multidimensionales
Tiene como base el algebra matricial y el proceso de eliminación de Gauss- Jordan
Es un proceso de búsqueda, se vuelve sorprendentemente eficiente para soluciona
problemas muy grandes
Puede aplicarse con eficiencia a la diversidad de paquetes de software que facilitan
el proceso de calculo
TABLA DEL METODO SIMPLEX

Metodo Simplex

Cargado por

Copyright:

Formatos disponibles

Metodo Simplex

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Metodo Simplex

Cargado por

Copyright:

Formatos disponibles

HISTORIA DEL METODO SIMPLEX

El método simplex , fue creado en el año de 1947 por el matemático George

 La aplicación del método simplex presupone que se tiene un sistema de

PARA REALIZAR LA TABLA DEL MÉTODO SIMPLEX

El método simplex se desarrolla en la tabla simplex. Cada iteración requiere de una

El procedimiento iterativo en que se basa el método simplex puede resumirse en los

VENTAJAS DEL MÉTODO SIMPLEX

 Es un método heurístico. Se basa en consideraciones geométricas y

DESVENTAJAS DEL METODO SIMPLEX

CARACTERISTICAS DEL METODO SIMPLEX

También podría gustarte