Metodo Simplex

| 2011 |
| |

METODO SIMPLEX
ASIGNATURA: MODELOS CUANTITATIVOS

SECCIÓN:

CATEDRÁTICO: Ing.
Realizado por:

Tegucigalpa, M. D. C., 18 de Febrero 2011

INTRODUCCION.
Partiendo de aquellos problemas simples de programación lineal, los que tienen solamente 2 variables o llamados también problemas bidimensionales, se encuentran sistemas de mas variables el método no es tan sencilloy se resuelven por el llamado método simplex.
Un simplex o n simplex es el análogo en n dimensiones de un triangulo, es la envoltura convexa de un conjunto de puntos independientes afines en un espacio euclideo de dimensión n o mayor, es decir conjunto de puntos tal que ningún plano contiene mas de ellos.
El método simplex es un algoritmo iterativo para resolver de una forma eficiente losproblemas de la programación lineal de gran tamaño, se han realizado algunas revisiones en el método para conseguir incrementar su eficiencia de calculo, el método se ha programado y codificado para todos los tipos y tamaños de ordenadores, es el primer método formal para encontrar soluciones optimas.
Hay algunas situaciones especiales de programación lineal que requieren ajustes del método simplexcomo: degeneración, soluciones no acotadas, soluciones múltiples etc.
El método requiere que las restricciones sean ecuaciones en lugar de inecuaciones lo cual se logra añadiendo variables de holgura a cada inecuación del modelo.

EL METODO SIMPLEX

El método del simplex fue creado en 1947 por el matemático George Dantzig. El método del simplex se utiliza, sobre todo, para resolver problemasde programación lineal en los que intervienen tres o más variables. La base del método simplex lo componen el álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales.

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo delvalor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
El método del simplex se basa en lasiguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

Pasos para el desarrollo del método simplex.
1. Hallar una solución básica factible inicial.
a. Convertir las desigualdades en igualdades.
b. Igualar la función objetivo a cero
c. Escribir la tabla inicial simplex
2.Prueba de optimidad: determinar si la solución básica factible inicial es optima, esto ocurre si todos los coeficientes de la ecuación son no negativos.
3. Para escoger la variable de decisión que entra en la base, nos fijamos en la primera fila, le de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor.
4. Para todo los problemas de maximizacióny minimización, la variable que sale es la variable básica que tiene la razón mas pequeña(positiva)
5. En la intersección de la fila pivote y columna pivote se encuentra el elemento pivote.
6. Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de gauss.
7. Para el resto de las filas.
8. Si en los elementos de laprimera fila hay un coeficiente negativo significa que no hemos llegado todavía a la solución optima, se repite el proceso
9. Si todos los coeficientes de la fila de la función obejetivo son positivos hemos llegado a la solución optima viene dada por el valor Z en la columna de los valores solución.
PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX
Esta es la forma estándar del modelo:...