Metodo Simplex

Método simplex:
El método simplex fue creado en 1947 por el matemático George Dantzing.
El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.
El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.
El métodosimplex se basa en la siguiente 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-
Variables: de holgura o exceso, y que hacer en caso < > =
Si en nuestro modelo aparece una inecuación con una desigualdad del tipo "≥", deberemos añadir una nueva variable, llamada variable de exceso si, con larestricción si ≥ 0. La nueva variable aparece con coeficiente cero en la función objetivo, y restando en las inecuaciones.
Surge ahora un problema, veamos cómo queda una de nuestras inecuaciones que contenga una desigualdad "≥" :
a11·x1 + a12·x2 ≥ b1  a11·x1 + a12·x2 - 1·xs = b1
Como todo nuestro modelo, está basado en que todas sus variables sean mayores o iguales que cero, cuando hagamos la primeraiteración con el método Simplex, las variables básicas no estarán en la base y tomarán valor cero, y el resto el valor que tengan. En este caso nuestra variable xs, tras hacer cero a x1 y x2, tomará el valor -b1. No cumpliría la condición de no negatividad, por lo que habrá que añadir una nueva variable, xr, que aparecerá con coeficiente cero en la función objetivo, y sumando en la inecuación dela restricción correspondiente. Quedaría entonces de la siguiente manera:
a11·x1 + a12·x2 ≥ b1  a11·x1 + a12·x2 - 1·xs + 1 ·xr = b1
Este tipo de variables se les llama variables artificiales, y aparecerán cuando haya inecuaciones con desigualdad ("=","≥"). Esto nos llevará obligadamente a realizar el método de las Dos Fases
Del mismo modo, si la inecuación tiene una desigualdad del tipo "≤",deberemos añadir una nueva variable, llamada variable de holgura si, con la restricción si "≥" 0 . La nueva variable aparece con coeficiente cero en la función objetivo, y sumando en las inecuaciones.
A modo resumen podemos dejar esta tabla, según la desigualdad que aparezca, y con el valor que deben estar las nuevas variables.
Tipo de desigualdad | Tipo de variable que aparece |
≥ | - exceso +artificial |
= | + artificial |
≤ | + holgura |
Pasos:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones 2. Igualar la función objetivo a cero
3. Escribir la tabla inicial simplex
Tabla I . Iteración nº 1  |
Base | Variable de decisión | Variable deholgura | Valores solución |
  | x | y | h | s | d |   |
h | 2 | 1 | 1 | 0 | 0 | 18 |
s | 2 | 3 | 0 | 1 | 0 | 42 |
d | 3 | 1 | 0 | 0 | 1 | 24 |
Z | -3 | -2 | 0 | 0 | 0 | 0 |
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de loscoeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).

La columna de la variable que entra en la base se llama columna pivote (En color azulado). 
 
B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote,siempre que estos últimos sean mayores que cero. Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.
C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
5. Encontrar los coeficientes...