Método Simplex Primal de investigación operativa/operacional/de operaciones

Forma estándar del modelo de programación lineal

Para desarrollar el modelo de solución general el problema de programación lineal debe ponerse en un formato común al que denominamos formato estándar, las propiedades de la forma/formato estándar son:

1. Todas las restricciones son ecuaciones con los segundos miembros no negativos
   
2. Todas las variables deben ser no negativas
   
3. La función objetivo puede ser de maximización o minimización y estar igualada a cero
   

Restricciones

Las inecuaciones pueden volverse igualdades mediante la suma de una variable holgura o resta de una variable exceso, dentro el primer miembro de la restricción.

Variables

Existen casos en los que la variable puede ser irrestricta (Adquiere cualquier valor), esta puede expresarse en términos de dos variables no negativas mediante el uso de una sustitución.

Función objetivo

La maximización de una función equivale a la minimización del negativo de la misma función y viceversa.

Soluciones básicas

Considerando un modelo estándar de programación lineal con "m" ecuaciones y "n" incógnitas, una solución básica asociada se determina haciendo n-m variables iguales a cero, y resolviendo las ecuaciones con las variables restantes.

Método Simplex Primal

Forma Estándar

Todas las restricciones deben ser del tipo menor o igual que, con el lado derecho positivo, la función objetivo debe ser de maximización y todas las variables son no negativas.

Se introducen las variables holgura se seleccionan las variables de decisión como las variables no básicas iníciales, y as variables holgura como las variables básicas iníciales.

Prueba de optimidad

La solución básica es optima si y solo si los coeficientes de la función objetivo son no negativos, si es así el proceso se detiene de otra manera sigue a una nueva iteración para obtener la siguiente solución básica.

Determinar la variable básica entrante

Se escoge la variable no básica con el coeficiente negativo de mayor valor absoluto (el más negativo) de la ecuación objetivo. Esta será la columna pivote.

Determinar la variable básica saliente

Esto se realiza con la prueba del cociente mínimo:

1. Elija los cocientes estrictamente positivos y diferentes de cero, de la columna correspondiente al pivote
   
2. Divida cada coeficiente entre el elemento del lado derecho de la misma fila
   
3. Identifique la fila que tenga el menor de estos cocientes
   
4. La variable básica de esta fila es la variable básica que sale, sustitúyala por la variable básica entrante en la columna de la variable básica de la siguiente tabla
   

Despejar la nueva solución básica mediante eliminación Gaussiana

1. Divida la fila del pivote entre el pivote
   
2. En la siguiente tabla copie la fila del pivote y llene su columna de ceros
   
3. El nuevo elemento = elemento – (coef. Fila del pivote) (coef. Columna del pivote).