Metodo algebraico

Método Algebraico

Capítulo 4 Método Algebraico

Introducción En la necesidad de desarrollar un método para resolver problemas de programación lineal de más de dos variables, los matemáticos implementaron el método algebraico, el que más tarde se convertiría en el tan afamado método simplex. Como su nombre lo indica, el método usa como su principal herramienta, el álgebra, que ligada a unproceso de lógica matemática dio como resultado el método algebraico. Con el siguiente ejemplo se ilustra el algoritmo del método algebraico; El ejercicio que se usa para ello es de dos variables X1 , X2 , con el propósito de observar lo que el método realiza sobre la gráfica en el plano cartesiano, ofreciéndonos ésta metodología la ventaja de comparar paso a paso el método gráfico con el métodoalgebraico. Ejemplo 1 Maximizar Z = X1 + X2 C.S.R. 5X1 + 3X2 < 15 3X1 + 5X2 < 15 Xj > 0 ; j = 1, 2 Todo problema de programación lineal que se formule de la forma Maximice, con todas sus restricciones < y con la condición de no negatividad, se le llama Forma Estándar ó Forma Normal 65

Método Algebraico El área de soluciones factible, las coordenadas de cada esquina y el valor de la funciónobjetivo Z en cada una de ellas, se muestra en la gráfica siguiente:

Algoritmo del Método Algebraico

1) Hallar una solución básica y factible (Solución inicial) a) Expresar las inecuaciones (desigualdades) como ecuaciones (igualdades) b) Hallar una variable básica para cada ecuación c) Organizar el sistema de ecuaciones lineales 2) Escoger la variable que entra 3) Escoger la variable que sale 4)Reorganizar el sistema de ecuaciones 5) Repetir los pasos 2, 3 y 4 hasta encontrar la solución

66

Método Algebraico 1) Hallar una solución básica factible a) Expresar todas la inecuaciones como ecuaciones lineales, para ello y en éste caso usamos variables de relleno, también llamadas de holgura, para igualar el lado izquierdo al lado derecho de la inecuación; así: 5X1 + 3X2 < 15 5X1 + 3X2 +X3 = 15 3X1 + 5X2 < 15 3X1 + 5X2 + X4 = 15

Aquí X3 y X4 son las variables de holgura o relleno, que al adicionarlas al lado izquierdo, establecen la igualdad con el lado derecho de la inecuación lineal. La variables X1 y X2 se denominan variables de decisión o variables reales, las variables de relleno o holgura, se usan para convertir una inecuación en una ecuación, esto es, igualar el ladoizquierdo al lado derecho. Las variables de holgura o de relleno, se suman o restan al lado izquierdo de la inecuación, según convenga para establecer la igualdad. b) Escoger en cada ecuación una variable que sirva como solución inicial al problema y que tome un valor positivo ( > 0), NO son elegibles las variables de decisión o variables reales. Entonces, las variables de holgura o relleno (si lashay), son las primeras opcionadas a ser escogidas como variables básicas y factibles, lo que significa que deben tomar un valor mayor o igual a cero ( > 0), dicho de otra forma, las variable básicas factibles, deben cumplir con la condición de no negatividad. De no conseguirse una variable de holgura que sea factible, se utiliza el recurso de las variables de súper-avit o artificiales, pero deéste caso nos ocuparemos en el segundo ejemplo, para el que usaremos el denominado método de la gran M. Aquí tanto X3 como X4 , variables de holgura, son escogidas como variables básicas factibles, ya que ambas asumen valores positivos al ser X1 y X2 variables no básicas e iguales a cero (0), esto es: 5X1 + 3X2 + X3 = 15 X1 = X2 = 0 , entonces X3 = 15 , valor > 0 3X1 + 5X2 + X4 = 15 X1 = X2 = 0 ,entonces X4 = 15 , valor > 0

c) Organizamos el sistema de ecuaciones de la siguiente manera: En la ecuación ( 0 ) siempre Z es la variable básica. Fíjese que en cada ecuación existe una y solo una variable básica con coeficiente ( 1 ), lo que permite leer su valor de manera automática al lado derecho; esto es: 67

Método Algebraico Z = 0 ; X3 = 15 y X4 = 15 ; esto es una SOLUCIÓN BÁSICA...