METODO SIMPLEX EN UN SISTEMA DE PROGRAMACION


El método simplex es un método algebraico interactivo que permite ir mejorando la solución a cada paso del procedimiento comenzando con una solución basica (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, el cual 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 algebra matricial y el proceso de eliminación de Gauss- Jordan.

Es un proceso de búsqueda que se vuelve sorprendentemente eficiente para solucionar problemas 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 area de soluciones factibles. Cada restricción matematicamente se representa como una inecuación  de desigualdad (=) y se representa graficamente como un area. Cada area esta delimitada por los ejes y por una recta extrema que resulta de tomar la desigualdad como una igualdad.
El método simplex requiere trabajar no coninecuaciones 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 estandar; en este modelo, 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 matematico requerido por el método para estos dos tipos de restricciones.
De allí que al analizar la forma estandar en un modelo de PL se dice que esta en su forma estandar 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 esta en la forma estandar:
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 la restricción de signo a la nueva variable ei >=0.
Cuando tengamos restricciones de tipo >= o =, y por lo tanto aparezcan variables artificiales,  sera 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 mas modernamente el método empujar y halar
Cuando ya se tiene el programa lineal en formato de modelo estandar es posible usar el algebra de matrices para encontrar los puntos extremos que permiten hallar la solución óptima. Para esto, se añadevariables 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 este efecto se define dos grupos en cada iteración, uno llamado variables basicas y otro llamado no basicas. Las variables no basicas son las que se les da valor de cero y las variables basicas 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-Jordan se encuentra el valor del punto extremo. Para mejorar la solución encontrada es necesario desplazar a otro punto modificando la base: sacando una variable de ella y metiendo otra. Por lógica se escoge para la variable que entra aquella que mejore en mayor proporción a la función objetivo y para salir aquella variable que mas restrinja el modelo a la intersección entre la columna de la variable que entra y la de la fila de la variable que sale, lo cual se llamara pivote. Se debe convertir por operaciones entre filas y columnas a este pivote en 1 y basandose en este pivote se aplica Gauss-Jordan para convertir en cero los demas miembros de la columna.  En cada iteración se hace una verificación de optimalidad, y se pregunta si hemos llegado al óptimo: si ya ninguna variable que entre va a mejorar mas el resultado, si es así terminamos con el problema, de lo contrario, se hace una nueva iteración. En esta verificación también se examina la factibilidad del problema, tal vez se encuentre con que el problema no esta acotado, o que tenga infinito número de soluciones. Pero enconclusión, el método simplex consiste en incrementar el valor de las variables no basicas y estudiar como varía el funcional Z con dicho incremento.
TIPOS DE METODOS SIMPLEX.
Los tipos de métodos simplex son
Método simplex primal. Parte de una solución basica factible (punto externo del polígono de soluciones) y se continúa iterando a través de soluciones basicas factibles sucesivas hasta alcanzar el óptimo valor.
Método simplex dual. Trata con soluciones basicas infactibles hasta la última interacción, donde la solución basica asociada debe ser factible.
Pero cualquiera que sea el método simplex utilizado, finalmente obtendra soluciones basicas factibles como lo estimula la condición de no negatividad.
PASOS PARA DESARROLLAR EL METODO SIMPLEX
Para desarrollar un problema de programación lineal a través del método simplex deben seguirse los siguientes pasos

PASO 1: Poner el problema en forma estandar:
La función objetivo se minimiza y las restricciones son de igualdad.

PASO 2: Encontrar una solución basica factible (SBF).

PASO 3: Testar la optimalidad.

PASO 4: Elegir una variable de entrada.

PASO 5: Elegir la variable de salida.

PASO 6: Actualizar la base y la solución basica factible.

PASO 7: Volver al PASO 3.


PASO 1. Poner el problema en forma estandar
Supongamos que tenemos el siguiente problema de programación lineal (PPL):
Maximizar
Sujeto a


Necesitamos que la función objetivo N°1 sea de minimización y que todas las restricciones sean iguales N°2, N°3
La restricción se denomina restricción no negativa N°4 y no cambia.
EstePPL no esta en forma estandar, entonces hay 2 pasos a realizar.
1. Cambiar de maximización a minimización. Para esto multiplicamos la función objetivo N°1 por -1. Y se obtendra

Maximizar
Sujeto a


2. Convertir las inecuaciones en ecuaciones, para esto añadimos variables de holgura
Consideremos la desigualdad N°2. Tenemos la desigualdad ≤. Como x1 + x2 tiene que ser menor que 50, podemos añadir una variable x3 positiva que nos hace alcanzar el 50.

Ahora tenemos:

Cuando añadimos variables a las restricciones, tenemos que tener en cuenta la función objetivo, el coste asociado a estas nuevas variables sera 0
Maximizar
Sujeto a



La siguiente desigualdad es del tipo ≥ y actuaremos de forma similar: x1 + x2 es mayor que 25, necesitamos restar una variable positiva x4 para obtener 25. Su coste asociado sera 0.

Maximizar
Sujeto a


Donde x3 y x4 son variables de holgura

PASO 2: Encontrar una solución basica factible (SBF).

El método del simplex empieza en un vértice de la región factible, es decir, un punto extremo. Después, en cada iteración, el método se mueve a lo largo de una arista hacia otro punto extremo. Con este método, moviéndonos de vértice en vértice, hay que encontrar un punto extremo inicial de la región factible. Los puntos extremos se corresponden con las soluciones basicas factibles.
Un PPL dado en forma estandar se puede escribir en forma matricial.

Minimizar

Sujeto aEn el ejemplo que estamos considerando. Tendremos







Tenemos 2 ecuaciones y 4 variables, mas variables que ecuaciones. Como resultado tenemos infinitas soluciones para estas restricciones. De hecho, cada punto de la región factible es una solución del sistema.
Nosotros solamente necesitamos los vértices de la región factible, y estos puntos se corresponden con las soluciones basicas factibles del sistema.
Cuando un sistema Ax = b tiene m ecuaciones y n incógnitas con m ≤ n, debemos seleccionar, B, una submatriz de A no singular m * m (det(A) ≠ 0).
Esta submatriz B se denomina matriz basica.
Las variables que generan la matriz B (sus columnas estan en B), se denominan variables basicas y se denotan por XB

Las otras n - m variables seran variables no basicas, XN, y siempre se le asociara el valor 0.

En nuestro ejemplo podemos escoger como matriz basica a



Las variables basicas seran x1; x3 y las no basicas x2; x4.

El valor de las variables basicas se obtiene con el sistema



La solución obtenida se denomina solución basica.
Una solución basica es una solución basica factible si xB ≥ 0.
El valor de la solución basica interior sera




También podríamos escoger como matriz basica a pero no es factible pues



X4 = −25 < 0, no est´a dentro de la región factible


PASO 3: Testar la optimalidad.

Tomaremos x otra solución basica. Veamos la relación existente con nuestra solución



Multiplicando por B−1 a la izquierda y despejando xB tenemos:

Si comparamos el valor de la función objetivo de la soluciónbasica factible inicial, Z0, con la nueva, z, tenemos:





Entonces



Donde es la columna de en A y
La solución basica factible tiene el costo ´optimo cuando no existe un costo mejor. Es decir, cuando
zj − cj ≤ 0 para todo xj variable no basica.
Comprobaremos si la solución obtenida en el apartado anterior es ´optima. Para ello calcularemos z2 − c2 y z4 − c4



Son los coeficientes de costes de las variables basicas. Es decir

Es la columna de A correspondiente a la variable
Y
Es el coeficiente de coste de
Y


La solución no es óptima tanto como son positivos

PASO 4: Elegir una variable de entrada.
Si la solución que tenemos no es óptima significa que tenemos alguna variable no basica xj que verifica que zj − cj > 0. Queremos buscar una nueva solución basica factible, y su coste asociado es

El método del simplex consiste en modificar la solución obtenida cambiando una variable basica por una no basica. Si queremos mejorar el coste, la variable no basica elegida debera cumplir que zj − cj > 0. Tomaremos xk variable no basica cuyo valor zk − ck sea mayor.
En el ejemplo tenemos que z2 − c2, z4 − c4 > 0.
Escogeremos el valor mayor, por lo tanto la variable que entra es x4.

PASO 5: Elegir la variable de salida.
Una vez elegida la variable de entrada xk, sabemos que el resto de las variables no basicas seguiran siendo no basicas y su valor asociado sera 0.
Ademas tenemos que


Teniendo en cuenta que las variables basicas tienen que ser positivas

Si yik ≤ 0, xBi crece si xk crece. Por lo tanto xBisigue siendo positivo.

Si todos los yik ≤ 0, las variables xB crecen si xk crece. La solución es no acotada.

Si yik < 0, xBi decrece si xk crece.

Necesitamos que las xB ≥ 0; así que aumentaremos xk hasta que la primera xB sea 0. Esta sera la variable que salga


La variable que sale Xr, es la que hace que se alcance el mínimo

Siguiendo con el ejemplo tenemos que



Entonces tenemos que . La variable que sale es

PASO 6: Actualizar la base y la solución basica factible.

La nueva base es basicamente la base inicial, solamente se permutan dos variables, una basica se convierte en no basica y viceversa.

La variable xk era no basica y ahora es basica.

La variable xr era basica y ahora es no basica.

Luego nosotros tenemos como variables basicas a x1; x4 y las no basicas son x2; x3.
Los nuevos valores son






Y los valores de la nueva solución son x4 = 25, x2 = x3 = 0 (por ser no basicas) y x1 se calcula por la fórmula:






PASO 7: Volver al PASO 3

Ahora tenemos una solución basica factible mejor que la inicial. Necesitamos saber si esta es la óptima.
Para ello necesitamos aplicar el test de optimalidad, el paso 3.