En esta sección presentamos los detalles del método símplex. Comenzamos con la elaboración de la forma estándar necesaria para representar el espacio de soluciones de la PL, por medio de un Sistema de ecuaciones simultáneas. El resto de la exposición muestra cómo se determinan selectivamente las soluciones básicas sucesivas, con el fin de alcanzar el punto de solución óptima en un número finito de iteraciones.
Conforme se estudie el resto de este capitulo, el lector se relacionará con dos variantes del método símplex: los algoritmos del método símplex primal y los del símplex dual. En apariencia los dos métodos parecen ser diferentes. Esto no es el caso y, de hecho, lo fundamental de los dos algoritmos se basa en la idea que los puntos extremos del espacio de soluciones son completamente identificables por las soluciones básicas del modelo de PL. Básicamente, los dos algoritmos parecen ser diferentes porque están diseñados para sacar ventaja de la estructuración inicial especial del modelo de PL. Este punto se enfatizará conforme presentemos los detalles de los dos procedimientos.
FORMA ESTANDAR DEL MODELO DE PL
Un modelo de PL puede incluir restricciones de los tipos <-, = y >- Además, las variables pueden ser no negativas o irrestrictas (no restringidas) en signo. Para desarrollar un método de solución general, el problema de programación lineal debe ponerse en un formato común, al que llamamos la forma estándar. Las propiedades de la forma de PL estándar son
1. Todas las restricciones son ecuaciones (con los segundos miembros no negativos, si el modelo se resuelve por medio del método símplex primal)
2. Todas las variables son no negativas.
3. La función objetivo puede ser la maximización o la minimización.
Como se explicará después, la segunda propiedad que exige que todas las variables sean no negativas, es crucial en el desarrollo de los métodos símplex (primal y dual).
Ahora demostremos cómo se puede poner cualquier modelo de PL en el formato estándar.
A. Restricciones
1. Una restricción del tipo <- (>-) puede convertirse en una ecuación mediante la suma de una variable de holgura a (o restando una variable de exceso de) el primer miembro de la restricción.
Por ejemplo, en la restricción
x1 + 2x2 <- 6
Conforme se estudie el resto de este capitulo, el lector se relacionará con dos variantes del método símplex: los algoritmos del método símplex primal y los del símplex dual. En apariencia los dos métodos parecen ser diferentes. Esto no es el caso y, de hecho, lo fundamental de los dos algoritmos se basa en la idea que los puntos extremos del espacio de soluciones son completamente identificables por las soluciones básicas del modelo de PL. Básicamente, los dos algoritmos parecen ser diferentes porque están diseñados para sacar ventaja de la estructuración inicial especial del modelo de PL. Este punto se enfatizará conforme presentemos los detalles de los dos procedimientos.
FORMA ESTANDAR DEL MODELO DE PL
Un modelo de PL puede incluir restricciones de los tipos <-, = y >- Además, las variables pueden ser no negativas o irrestrictas (no restringidas) en signo. Para desarrollar un método de solución general, el problema de programación lineal debe ponerse en un formato común, al que llamamos la forma estándar. Las propiedades de la forma de PL estándar son
1. Todas las restricciones son ecuaciones (con los segundos miembros no negativos, si el modelo se resuelve por medio del método símplex primal)
2. Todas las variables son no negativas.
3. La función objetivo puede ser la maximización o la minimización.
Como se explicará después, la segunda propiedad que exige que todas las variables sean no negativas, es crucial en el desarrollo de los métodos símplex (primal y dual).
Ahora demostremos cómo se puede poner cualquier modelo de PL en el formato estándar.
A. Restricciones
1. Una restricción del tipo <- (>-) puede convertirse en una ecuación mediante la suma de una variable de holgura a (o restando una variable de exceso de) el primer miembro de la restricción.
Por ejemplo, en la restricción
x1 + 2x2 <- 6
No hay comentarios:
Publicar un comentario