Investigación de Operaciones

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 aun proceso 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 elmétodo algebraico.
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 elvalor de la función
objetivo 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 lainecuació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 unainecuación en una ecuación,
esto es, igualar el lado izquierdo 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 variablesreales. Entonces, las variables de holgura o relleno (si las hay), 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 elrecurso 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...