Programacion Lineal

Introducción |
Hasta el momento hemos analizado la solución de modelos de Programación Lineal en los cuales todas las restricciones son del tipo y además todos los coeficientes recurso son positivos o cero. Hicimos tal simplificación para hacer más fácil la determinación de una solución básica factible inicial. Efectivamente, al pasar el modelo a formato estándar obtenemos una base unitaria,tomando a las variables de holgura como variables básicas Iniciales, con lo cual se garantiza que el modelo tiene al menos esta solución inicial trivial.
Ahora omitiremos la simplificación mencionada y analizaremos el algoritmo de solución para modelos con restricciones de cualquier tipo (, =,) y con coeficientes recurso positivos, negativos o cero. Para este tipo de modelos la determinación deuna SBFI no es inmediata con solo tomar a las variables de holgura como variables básicas, pues como veremos los vectores asociados a las variables de holgura ya no conforman una matriz básica, pudiendo presentarse el caso de solución infactible o de inexistencia de una solución.
Aprenderemos enseguida que para este tipo de modelos, la mejor alternativa para determinar una solución básica factibleinicial es la inclusión de unas variables artificiales, con las cuales podemos construir “artificialmente" una SBFI, correspondiente al origen de coordenadas, similar a lo que obteníamos en los modelos resueltos hasta el momento.
Analicemos el siguiente modelo para entender el concepto y uso de las variables artificiales.
Minimizar Z = | 5X1 | - 7X2 | + 4X3 | |
Sujeta a | 1X1 | + 2X2 | +4X3 | 120 |
| 6X1 | + 4X2 | + 1X3 | 80 |
| 3X1 | + 3X2 | + 2X3 | = 90 |
con | X1, X2, X3  0 |

El modelo en formato estándar es:
Minimizar: Z = | 5X1 | - 7X2 | + 4X3 | + 0H1 | + 0E2 | |
Sujeta a: | 1X1 | + 2X2 | + 4X3 | + 1H1 | | = 120 |
| 6X1 | + 4X2 | + 1X3 | - 1E2 | | = 80 |
| 3X1 | + 3X2 | + 2X3 | | | = 90 |
con: | X1,X2,X3 0 |
| H1,E2 0 |
En este modelo no podemos formar una SBFI con las variables de holgura, por varios motivos. Primero porque solo contamos con dos variables de holgura y sabemos que toda solución básica de este modelo debe estar compuesta exactamente por tres variables (recuerda por qué?). Además, la variable E2 se está restando y no sumando como la H1, motivo por el cual su vector asociado no es un vectorunitario y por ende no puede hacer parte de una matriz básica factible.
Podemos determinar una SBFl, seleccionando intuitivamente (por tanteo y error) una matriz básica factible y aplicando luego el algoritmo simplex, tal como lo hemos hecho antes. Pero recordemos que aun para modelos pequeños, el numero de soluciones básicas es relativamente grande; por ejemplo para este modelo con tresrestricciones y cinco variables tendríamos diez soluciones básicas (factibles + infactibles), mientras que para un modelo con diez restricciones y veinte variables (originales + holgura) tendríamos 184756 soluciones básicas y fácilmente seria necesario efectuar 10.000 intentos antes de encontrar una solución básica factible para iniciar el algoritmo simplex.
De esta manera el enfoque intuitivo detanteo y error pierde su atractivo, y es necesario recurrir a un "artificio" para generar una solución básica factible inicial artificial (SBFIA).Veamos como se amplía un modelo al agregarle las variables artificiales.Si en la segunda ecuación se adiciona la variable artificial A2 y en la tercera la variable artificial A3 ambas no negativas, obtenemos el siguiente modelo:
Minimizar:Z = | 5X1 | -7X2 | + 4X3 | + 0H1 | + 0E2 | |
Sujeta a: | 1X1 | + 2X2 | + 4X3 | + 1H1 | | | = 120 |
| 6X1 | + 4X2 | + 1X3 | - 1E2 | + 1A2 | | = 80 |
| 3X1 | + 3X2 | + 2X3 | | | + 1A3 | = 90 |
| X1,X2,X3 0 |
con: | H1,E2 0 A2,A3 0 |
Tenemos ahora un modelo aumentado (MA) que difiere del modelo original (MO) en las variables artificiales.
En este modelo aumentado, ya podemos...