El algoritmo del simplex precisa para su utilización disponer de una solución inicial posible que permita iniciar los cálculos, por ello, según el caso que se presente será necesario introducir variables de holgura y variables artificiales.

• Variable de holgura: Permite convertir una desigualdad en igualdad.
• Variable artificial: Permite iniciar el cómputo, en caso de no disponer de una solución inicial posible básica.
Mediante las variables de holgura, el problema general de programación consiste en encontrar un vector (x1,x2,...,xn) que optimice una función objetivo:
• c1 . x1 c2 . x2 ... cn . xn
Sujeta a las restricciones
• a11x1 a12x2 ... ainxn = b1
am1x1 am2x2 ... amnxn = bm
• xi >=0 para una i cualquiera

• Solución posible: Es un vector (x1, x2, ..., xn) que satisface las condiciones (a y b).
• Solución básica: Solución obtenida al hacer (n-m) variables iguales a cero, siempre que el determinante de los coeficientes de estas m variables no sea cero.
• Solución posible básica: Es una solución básica que satisface (c).
• Solución posible básica no degenerada: Es una solución posible básica con exactamente m xi positivas.

Pasos del algoritmo del simplex

• Pj = Vector de coeficientes de la variable j.
• cj = Contribución de la variable j a la solución. (Rendimientos directos).
• ci = Coeficientes en la función objetivo de las variables en solución.
• zj = Coste de introducir la variable j en solución:
• zj = sum (ici . aij) (Rendimientos indirectos)
• b = Exigencias o vectores solución.
• cj - zj = Rendimientos marginales.
Øi = bi/aij

Suponiendo que ya se ha encontrado una solución básica posible a un problema de máximo, en el momento que se inician las interacciones del algoritmo, los pasos son los siguientes:

• Calculamos cj - zj para cada variable que no está presente en la solución:
• Si para al menos un cj - zj es positivo y si al menos un para este es positivo, existe un mejor programa posible.
• Si para un cj - zj es positivo, pero los para este son no positivos, la función objetivo no está acotada.
• Si cj - zj es no positivo para toda j, el programa óptimo se ha encontrado.

• Dado un problema, al identificar la variable que da mayor cj - zj (supongamos que es xk) y el elemento que da menor Ø = br/ark, sea el ark, este elemento se denomina pivote.
• Se divide la r-esima fila por para obtener el correspondiente elemento en la tabla siguiente. Se efectuaran las operaciones fila que reducirán a cero todos los otros elementos.
• Se repiten los pasos 1,2 y 3 hasta que en alguna tabla se cumpla la condición 1.3 entonces se ha obtenido la solución óptima.

Existen tres casos posibles, al realizar el algoritmo de un problema que contiene variables artificiales:

• Caso1. Antes de obtener la tabla en la cual todos los cj - zj < 0, las variables artificiales han sido reemplazadas por otras variables. Tenemos entonces una solución básica posible y podemos continuar las interacciones hasta determinar el programa óptimo posible.
• Caso 2. En la tabla final en la cual todos los cj - zj < 0 alguna variable artificial permanece en la solución pero con valor 0. La solución del problema es óptima y posible.
• Caso 3. Se obtiene una tabla en la cual todos los cj - zj