Algoritmo simplex revisado

INTRODUCCIÓN: PROGRAMACIÓN LINEAL
La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función esténsujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.
Las restricciones pueden ser de la forma:
Tipo 1:
Tipo 2:
Tipo 3:
Donde:
* A = valor conocido a ser respetado estrictamente;
* B = valor conocido que debe ser respetado o puede ser superado;
* C = valor conocido que no debe ser superado;
* j = número de la ecuación, variable de1 a M (número total de restricciones);
* a; b; y, c = coeficientes técnicos conocidos;
* X = Incógnitas, de 1 a N;
* i = número de la incógnita, variable de 1 a N.
En general no hay restricciones en cuanto a los valores de N y M. Puede ser N = M; N > M; ó, N < M.
Sin embargo si las restricciones del Tipo 1 son N, el problema puede ser determinado, y puede no tener sentido unaoptimización.
Los tres tipos de restricciones pueden darse simultáneamente en el mismo problema.

La función objetivo puede ser:

ó
Donde:
* f = coeficientes son relativamente iguales a cero.
Formulación estándar
Un programa lineal puede formularse de muy diferentes formas, pero dentro de la Programación Lineal se adopta como estándar la siguiente:
minc1x1+c2x2+...+cnxn
a11x1+a12x2+...+a1nxn = b1
a21x1+a22x2+...+a2nxn = b2
................................
am1x1+am2x2+...+amnxn = bm
xk >= 0 k=1,2,...,n
Se supone además que el número de variables es mayor o igual que el número de restricciones de igualdad (n>=m). Sin ninguna pérdida de generalidad puedesuponerse también que bk >= 0 para todo k=1,2,...,m.
Las principales características de esta formulación de problemas lineales son:
* Se trata de minimizar una función lineal homogénea.
* Todas las restricciones son de igualdad, siendo el término independiente mayor o igual que cero.
* Las variables de decisión solo pueden tomar valores no negativos.
Transformación de unprograma lineal a su forma estándar
Todo programa lineal, independientemente de la forma en la que esté dado, puede plantearse en la forma estándar; para ello es necesario efectuar una serie de manipulaciones sobre el programa.
* En primer lugar, ya se ha comentado el hecho de que maximizar una función es equivalente a minimizar su opuesta. La primera manipulación es por tanto convertir el problemaa uno de minimización.
* Si la función objetivo fuera de la forma f(X1,X2,...,Xn)=c1X1+c2X2+...+cnXn+d, evidentemente alcanzaría el mínimo en el mismo punto que la función g(X1,X2,...,Xn)=c1X1+c2X2+...+cnXn. El punto donde ambas funciones alcanzan el mínimo es el mismo, la única diferencia sería el valor de las funciones sobre ese punto.
* Las restricciones de desigualdad puedentransformarse en igualdades introduciendo unas nuevas variables que se conocen como variables de holgura:
* ak1X1+ak2X2+...+aknXn <= bk entonces existe y >= 0 tal que: ak1X1+ak2X2+...+aknXn+y = bk
* De igual forma, si ak1X1+ak2X2+...+aknXn >= bk, existe y >= 0 tal que: ak1X1+ak2X2+...+aknXn-y = bk
* Si alguna de las variables xk del problema no estuviera sujeta a lacondición de no negatividad, bastaría sustituirla por una diferencia de dos variables no negativas; es decir: Xk=yk-zk con yk,zk >= 0.
* Por último, para conseguir que bk >= 0 para todo k, se multiplicaría por -1 la correspondiente ecuación si fuese necesario.
Con todas estas manipulaciones, cualquier programa lineal puede expresarse en la forma estándar, clasificándose sus variables en:...