metodo simplex











METODO SIMPLEX EN UN SISTEMA DE PROGRAMACION






















2013
METODO SIMPLEX EN UN SISTEMA DE PROGRAMACION













2013







TABLA DE CONTENIDO
















INTRODUCCION























METODO SIMPLEX EN UN SISTEMA DE PROGRAMACION


El método simplex es unmétodo algebraico interactivo que permite ir mejorando la solución a cada paso del procedimiento comenzando con una solución básica (punto externo) y modificando esto a lo largo del proceso, a través de la inclusión y exclusión de una variable; siempre aumentando la utilidad (o reduciendo el costo) hasta encontrar una solución óptima. Este método fue desarrollado por George Bernard Dantzig en 1947, elcual la conversión del problema con restricciones con desigualdades en un problema presenta restricciones que son ecuaciones lineales.

CARACTERISTICAS:
Es aplicable a los problemas de programación lineal multidimensionales.
Tiene como base el álgebra matricial y el proceso de eliminación de Gauss- Jordán.
Es un proceso de búsqueda que se vuelve sorprendentemente eficiente para solucionarproblemas muy grandes.
El método simplex se basa en una premisa supremamente lógica: la solución tiene que encontrarse en un punto extremo del área de soluciones factibles. Cada restricción matemáticamente se representa como una inecuación  de desigualdad (=) y se representa gráficamente como un área. Cada área está delimitada por los ejes y por una recta extrema que resulta de tomar la desigualdadcomo una igualdad.
El método simplex requiere trabajar no con inecuaciones o desigualdades si no con igualdades para ignorar, si se puede decir así, todas aquellas soluciones en el volumen interno e irse desplazando por los puntos realmente extremos. Cuando se convierten estas inecuaciones en ecuaciones para preparlas para el método, se dice que lo convertimos en el modelo estándar; en estemodelo, por ejemplo,  en vez de expresar una restricción de la siguiente manera: 
Material usado en el producto a + material usado en el producto b = e =, y son llamadas variables artificiales. Estas variables no tienen ningún significado físico, sino que son un artificio matemático requerido por el método para estos dos tipos de restricciones.
De allí que al analizar la forma estándar en un modelode PL se dice que está en su forma estándar si cada restricción es una igualdad y las restricciones de signo para cada variable son del tipo mayor o igual que cero.
Ejemplo:
No está en la forma estándar:
Max Z = 3x + 2y
Sujeto a:
2x + y = se introduce una nueva variable de exceso (excess variable) ei que se resta al primer miembro y la desigualdad se convierte en igualdad; se añade larestricción de signo a la nueva variable ei >=0.
Cuando tengamos restricciones de tipo >= o =, y por lo tanto aparezcan variables artificiales,  será necesario usar una variante del simplex llamado: método de la gran m.  En este tipo de situación también se puede usar el método de las dos fases y más modernamente el método empujar y halar
Cuando ya se tiene el programa lineal en formato de modeloestándar es posible usar el álgebra de matrices para encontrar los puntos extremos que permiten hallar la solución óptima. Para esto, se añade variables tanto de holgura como artificiales haciendo que el número de variables sea mayor que el número de restricciones, por lo que se tiene que para hallar una solución (un punto extremo)  hacer cierto número de estas variables iguales a cero. Para esteefecto se define dos grupos en cada iteración, uno llamado variables básicas y otro llamado no básicas. Las variables no básicas son las que se les da valor de cero y las variables básicas son las que se usan con valor dentro de las iteraciones.
Luego, en cada iteración se define la base y usando el método de Gauss-Jordán se encuentra el valor del punto extremo. Para mejorar la solución...