INVESTIGACIÓN DE OPERACIONES 1

Programación Lineal

El Método Simplex

El método simplex es una herramienta algebraica que permite localizar de manera eficiente el óptimo entre los puntos extremos de una solución a un problema de programación lineal.

Forma estándar de programación lineal (PL) y sus soluciones básicas

El empleo de las soluciones básicas para resolver el modelo de PL requiere poner el problema en una forma estándar, cuyas propiedades son:
1. Todas las restricciones (con excepción de las restricciones de no negatividad sobre las variables) son ecuaciones con un lado derecho no negativo.
2. Todas las variables son no negativas.
3. La función objetivo puede ser del tipo de maximización o de minimización.
a. Conversión de desigualdades a ecuaciones
Una desigualdad del tipo = (=) se convierte a una ecuación aumentando su lado izquierdo con una variable de holgura (superávit)
Ejemplos:
1) x1 + 2x2 = 3 es equivalente a x1 + 2x2 + S1 = 3
2) x1 + 2x2 = 3 es equivalente a x1 + 2x2 - S1 = 3
donde S1 = 0

b. Conversión de una variable no restringida a variables no negativas
Una variable xj no restringida se puede expresar en términos de dos variables no negativas, utilizando la sustitución
xj = xj+- xj-, donde xj+,xj-= 0
Ejemplo:
xj = -5 es equivalente a xj +  = 0 y  xj - = 5; donde xj + ,xj - = 0
c. Conversión de maximización a minimización
La maximización de una función f(x1, x2, … , xn) es equivalente a la minimización de  -f(x1, x2,  … , xn), en el sentido que ambos problemas producen los mismos valores óptimos x1, x2, … , xn.