Explicaci N Del Tema 4

14/9/2014

Explicación del tema

Explicación del tema 4
Investigación de operaciones I
Tema 4. Introducción al Método Simplex
El método simplex es una herramienta muy poderosa para resolver
problemas de programación lineal. Fue desarrollado en el año de 1947
y desde entonces se ha seguido utilizando debido a su gran utilidad y
eficiencia.
Básicamente el simplex trabaja mediante procedimientosalgebraicos,
sin embargo, la lógica de su operación está basada en fundamentos
geométricos, por lo que antes de aprender a utilizarlo es necesario
conocer algunos conceptos clave que nos ayuden a comprender el
procedimiento tanto geométrico como algebraico que desarrolla la herramienta.
Para comprender la lógica geométrica, es necesario que repasemos el método gráfico. Recuerda que tal y
como loaprendimos en el tema anterior, al graficar las restricciones del modelo de PL, obtenemos una región
factible. La intersección o cruce entre las líneas de estas ecuaciones dan como resultado una serie de
vértices, y es en estos vértices donde se encuentra la solución óptima del modelo, es decir, son las
soluciones factibles en los vértices (FEV).
Repasemos el ejemplo que estudiamos con el métodográfico.
Cada una de las soluciones FEV se encuentra en la intersección
de 2 restricciones. Ahora bien, para cualquier problema de PL con
n variables de decisión, 2 soluciones FEV son ADYACENTES
entre sí cuando comparten n-1 restricciones. La recta que
conecta a 2 soluciones FEV ADYACENTES se conoce como
ARISTA de la región factible.
En la siguiente gráfica podemos observar las FEV marcadas con
unaestrella. La recta que una a dos soluciones FEV es la
ARISTA. Cada FEV tiene dos rectas ARISTAS que la unen a otra FEV, de manera que cada FEV tendrá dos
FEV Adyacentes.

http://bbsistema.tecmilenio.edu.mx/bbcswebdav/institution/UTM/tetramestre/profesional/in/in09305/anexos/explica4.htm

1/4

14/9/2014

Explicación del tema

Punto de
Intersección

Solución FEV

FEV Adyacentes

A

(0,0)

(8,0) y(0,14)

B

(0,14)

(0,0) y (3,12)

C

(3,12)

(0,14) y (6,6)

D

(6,6)

(8,0) y (3,12)

E

(8,0)

(0,0) y (6,6)

El motivo por el cual es importante que analicemos las FEV Adyacentes se debe a una propiedad muy
importante que nos ayuda a verificar si una solución FEV es la óptima; esta prueba se conoce como Prueba
de Optimalidad.
De acuerdo a la prueba de optimalidad, si una solución FEV no tienesoluciones FEV Adyacentes que
mejoren el valor de la función objetivo, esto quiere decir que la FEV analizada es la óptima. Por el contrario, si
la FEV analizada tiene FEV Adyacentes que al sustituir sus valores en Z se obtiene un resultado mejor, la
FEV analizada no es la óptima.
La prueba de optimalidad es una parte muy importante de la lógica que utiliza el método simplex para
determinar cuándo hallegado a una solución óptima para el modelo de PL.
Desde el punto de vista geométrico, el simplex realiza el siguiente procedimiento:
1. Seleccionar el origen (0,0) con FEV inicial para comenzar con el análisis.
2. Realizar la prueba de optimalidad, es decir, se analizan las soluciones FEV Adyacentes. Si alguna de
ellas mejora el valor de Z, quiere decir que la FEV inicial (0,0) no es la soluciónóptima.
3. Moverse a lo largo de la ARISTA hacia la FEV ADYACENTE cuya razón de mejoramiento de Z sea
mayor, es decir, que al aumentar el valor de la variable de decisión Xi, el valor de Z aumenta más
rápido.
4. Seleccionar la nueva solución FEV para analizar.
5. Realizar la prueba de optimalidad a FEV nueva. Si tiene una solución FEV ADYACENTE mejor, repetir
el procedimiento.
6. Finalizar hastaverificar que la FEV analizada no tiene ninguna FEV ADYACENTE mejor, es decir, que
es la óptima solución al modelo.
Una vez comprendidos los conceptos geométricos del método simplex es necesario traducir nuestro modelo a
una forma algebraica para poder solucionar los sistemas de ecuaciones del modelo.
Primero que nada, es necesario convertir las desigualdades de las restricciones en igualdades...