Dado un sistema de ecuaciones lineales cuyas variables deben adoptar valores no negativos (esencialmente lo mismo que un sistema de inecuaciones lineales), se busca la mejor de entre muchas soluciones alternativas, es decir, una solución óptima del sistema.Este formato especifica que se busca valores para las incógnitasAl pasar de una iteración a la siguiente se intercambia una variable independiente por una dependiente; tales pares de variables se denominan pivotes.En caso de que se cumplan las siguientes dos condiciones de optimalidad, podemos obtener una solución al problema anterior, asignando a las variables independientes del sistema los valoresPor otro lado, toda solución alternativa al problema debe satisfacer la relación, ya que en ella las variables independientes también deben tomar valores nonegativos.En cada iteración, los coeficientes del sistema así modificado vuelven a examinarse para ver si satisfacen las condiciones de optimalidad y de este modo generan una posible solución al problema.del sistema de ecuaciones se llama elemento pivote, porque permite despejar la variable independienteNo obstante, debe imponerse que el algoritmo termine en un número finito de pasos, lo que no sucede con una elección de pivotes inadecuada.Fukuda & Terlaky demostraron[5] en 1999 que para todo problema con solución y para toda base inicial existe una secuencia de a lo másLamentablemente, esa demostración no es constructiva en el sentido de que indique cuál pivote deba elegirse en cada paso.Como se puede observar de las definiciones anteriores, una base optimal no tiene pivotes admisibles, por lo que el algoritmo no puede ser continuado a partir de una base optimal.Por otro lado, es fácil demostrar con argumentos similares a los expuestos que una base no optimal sin pivotes admisibles siempre pertenece a un problema sin solución; sea esto, porque el sistema de ecuaciones e inecuaciones no tiene solución alguna (problema infactible), o porque existen soluciones con un valor objetivoPara evitar errores de redondeo se trabaja en lo que sigue con números racionales, eligiendo un único denominador común para todo el sistema de ecuaciones.Para encontrar un denominador así en cada paso del algoritmo no hace falta analizar los coeficientes del sistema; en caso de un sistema inicial con coeficientes enteros, en cada iteración se cumplirá que Al evaluar los coeficientes de un nuevo sistema el denominador común del sistema anterior quedará obsoleto, por lo que se procede a dividir los coeficientes del sistema nuevo por el denominador antiguo, con resultados que siempre serán enteros.designa al denominador común del sistema de ecuaciones, el símbolodesigna cualquier coeficiente restante en la misma fila del elemento pivote,designa cualquier coeficiente restante en la misma columna del elemento pivote, yEn cada paso, el pivote admisible se elegirá de acuerdo a la siguiente regla (el mínimo de un conjunto vacío se considera igual a infinito): Se puede demostrar[3] que este criterio simple (aunque no siempre eficiente) conduce siempre a una base optimal en un sistema que tenga solución.En el siguiente ejemplo se busca valores no negativos para las variablessatisfaciendo el siguiente conjunto de ecuaciones lineales: En el sistema inicial del ejemplo, los coeficientes no optimales sonEl criterio de selección, sin embargo, prescribe que despejemos: (para animar con Firefox, pulsar aquí y luego en la imagen, manteniendo presionado) Con ello obtenemos: Ahora los coeficientes no optimales sonA todo problema de programación lineal llevado a la forma básica arriba descrita se le puede asociar un problema dual de programación lineal.Como se muestra a continuación, el máximo obtenido en el problema dual (si es que existe) es igual al negativo del máximo obtenido en el problema primal.De esta relación de dualidad se concluye que toda base optimal para el problema primal provee también una base optimal para el problema dual.Al ejemplo anteriormente desarrollado le corresponde el problema dualEn el problema original, la variable a maximizarse toma el valor óptimoEsto es así porque las relaciones de dualidad implican que toda base optimal para el problema primal también provee una base optimal para el problema dual, donde el valor óptimo de la variablePara evitar redondeo, los coeficientes del sistema pueden también verse en forma de fracciones, aunque éstas no adoptan un denominador común.
