EL MÉTODO SIMPLEX
Enviado por ariakynerak • 7 de Noviembre de 2017 • Apuntes • 11.792 Palabras (48 Páginas) • 267 Visitas
2.2 EL MÉTODO SIMPLEX
El método simplex, es el método analítico para resolver modelos de programación lineal que involucran más de dos variables. La primera aplicación importante de este método ocurrió poco después del verano de 1947, cuando J. Laderman resolvió, en la National Bureau of Standards, un programa lineal de planeación de una dieta con nueve restricciones y 27 variables. Usando calculadoras de escritorio, para resolver este problema se requirieron 120 días-hombre, y cuando con dificultad las hojas de datos fueron unidas entre sí, semejaban un "mantel". Actualmente, usando la computadora y un programa del método Simplex (TORA, MICROMANAGER, LINDO, PROLIN, WIN QSB, entre otros) es fácil y rápido resolver los modelos de programación lineal con muchas variables y muchas restricciones.
Como hemos visto los modelos de programación lineal (PL) son formulados en una variedad de formas: Su objetivo puede ser de maximizar o minimizar; puede tener restricciones de igualdad o de desigualdad (menor o igual que, mayor o igual que); las variables pueden ser no negativas (≥ 0), no positivas (≤ 0) o libres. Es necesario estandarizar estas formas antes de aplicar el método simplex de solución del modelo.
La forma estándares especialmente útil para la presentación de la información del modelo y como preparación en forma de tabla para desarrollar el procedimiento analítico del algoritmo del método simplex para la solución de los modelos de P.L. de más de dos variables, las propiedades de la forma estándar son las siguientes:
Propiedades de la forma estándar
- La función objetivo puede ser de maximizar o bien de minimizar
- Todas las restricciones son ecuaciones, es decir, del tipo =
- El lado derecho de cada ecuación de restricción es positivo (vector b positivo)
- Todas las variables de decisión son no negativas, es decir, Xj≥0
Matemáticamente la forma estándar se representa como:
[pic 1]
Un modelo de P.L. puede ser convertido a la forma estándar mediante la aplicación de las siguientes reglas de equivalencia:
|
a) | Minimizar una función Z, es matemáticamente equivalente a maximizar la expresión negativa de la función objetivo. |
Minimizar Z = C1X1 + C2X2 +…..+ CnXn |
Es equivalente a: |
Maximizar –Z = -C1X1 -C2X2 -.... ...-CnXn |
b) | Maximizar una función Z, es matemáticamente equivalente a minimizar la expresión negativa de la función objetivo. |
Maximizar Z = C1X1 + C2X2 +…..+ CnXn |
Es equivalente a: |
Minimizar -Z = -C1X1 -C2X2 -.......-CnXn |
2. | Sobre las restricciones |
| |
a1X1 + a2x2 + ............ + anXn ≤ bi |
Es equivalente a: |
- a1X1 - a2X2 - ............ - anXn≥ - bi |
Una desigualdad con dirección≥puede cambiarse a la dirección opuesta ≤ multiplicando ambos lados por -1. |
a1X1 + a2X2 + .......... + anXn≥ bi |
Es equivalente a: |
- a1X1 - a2X2 - ............ - anXn ≤ - bi |
Una igualdad = puede ser reemplazada por dos desigualdades en dirección opuesta. |
...