Metodo simplex algebraico

UNIVERSIDAD DE ANTIOQUIA
FACULTAD DE INGENIERÍA

DEPARTAMENTO DE INGENIERÍA INDUSTRIAL

APUNTES DEL CURSO DE PROGRAMACIÓN LINEAL

Profesor: Hugo García Jiménez

EL MÉTODO SIMPLEX ALGEBRAICO

Noviembre de 2003

METODO SIMPLEX ALGEBRAICO

INTRODUCCIÓN

Vamos a conocer en este capítulo la primera de las dos formas como podemos entender matemáticamente el MétodoSimplex para la solución de modelos de Programación Lineal. Veremos que un requisito inicial para aplicar este enfoque es organizar el modelo, de tal forma que todas las restricciones sean del tipo < y todos los términos del lado derecho sean no negativos.

Al cumplirse lo anterior, tendremos la garantía de que escribiendo el modelo en formato estándar, el sistema de ecuaciones resultante tendríauna solución básica de inicio trivial, la cual obviamente estará compuesta por las variables de holgura.

A pesar de que con este procedimiento pueden resolverse modelos con cualquier número de variables y de ecuaciones, no es el método utilizado en la practica para resolver los modelos reales de P.L. Los nuevos conocimientos que se adquirirán al estudiar este método serán la base paracomprender otras formas de utilizarlo, como son el enfoque tabular y el enfoque matricial que presentaremos en capítulos siguientes.

Al final se aprenderá la forma analítica de identificar el tipo de la solución obtenida y su equivalencia con las conclusiones en este sentido obtenidas en el análisis gráfico.

ALGORITMO DE SOLUCIÓN

Paso inicial: Hallar una solución básica factible inicial.Después de escribir el modelo en formato estándar, se escoge, por comodidad en los cálculos, a las variables de holgura como variables básicas iniciales. Las variables originales quedarán como variables no básicas. Hecho lo anterior se procede a obtener la solución básica factible inicial, así:

a. Expresar las variables básicas en términos de las no básicas, en cada una de las ecuaciones del modelo.b. Reemplazar el valor (cero) de las variables no básicas en las expresiones del paso a, obteniendo así que las variables de holgura son iguales a los términos del lado derecho de cada ecuación.

Igualmente remplazar los valores de las variables no básicas, en la función objetivo obteniendo que esta es igual a cero.

Paso 1: Determinar si la solución básica factible actual puede mejorarseo si ya es la óptima.

Prueba de mejorabilidad

(para un problema de maximización de la función objetivo)
Consiste en verificar si en la función objetivo hay alguna variable no básica que tenga coeficiente positivo. Si la respuesta es afirmativa esto indica que al aumentar el valor de esa variable se incrementará proporcionalmente el valor de la función objetivo, motivo por el cual nosinteresa darle a esa variable el mayor valor posible.

Cuando hay más de una variable no básica con coeficiente objetivo positivo, al incrementar el valor de cualquiera de ellas se incrementará el valor de la función objetivo. En este algoritmo incrementaremos el valor de la variable no básica que tenga el mayor coeficiente, aunque debe tenerse en cuenta que no siempre esto garantiza quearribemos con mayor rapidez a la solución óptima. La variable seleccionada para aumentarle su valor se conoce como variable de entrada a la solución básica.

Si hay dos o más variables empatadas como variable de entrada, podemos romper el empate arbitrariamente.

Prueba de optimalidad:

Si en la prueba de mejorabilidad la respuesta es negativa, es decir, si todas las variables no básicas tienencoeficiente objetivo negativo o cero, la solución básica actual es inmejorable, o sea que es la solución óptima y se termina el algoritmo.

Paso 2: Obtener la nueva solución básica factible mejor.

a. Identificar la variable de salida:

Se toma como variable de salida de la solución básica actual a aquella que primero llegue a valer cero al aumentar el valor de la variable de entrada...