Metodo simplex

simplex
Introducción al Método Simplex

El método simplex, es el método algebraico para resolver problemas de programación lineal que involucran dos o más variables, fue creado en el año de 1947. 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 dietacon 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, QSB, etcétera) es fácil resolver problemas de PL con muchas variables ymuchas restricciones.

FORMAS EQUIVALENTES DE LOS PROBLEMAS DE PL Y POSTULADOS

Después de la formulación de un modelo de programación lineal (PL), el siguiente paso es determinar su solución, como hemos visto los modelos de PL son formulados en una variedad de formas (maximización ó minimización para la función objetivo y {} para las restricciones). Es necesario modificar estas formas antesde aplicar el método simplex de solución del modelo, dos formas serán presentadas para ese fin: la forma Canónica y la forma Estándar. La primera es útil para la teoría de dualidad, que se vera posteriormente, y la segunda es especialmente útil para la presentación de la información del modelo y como preparación en forma de tabla para desarrollar el procedimiento algebraico para la solución decualquier problema de PL los detalles de las dos formas son los siguientes:

Forma canónica:

Características: 1.- La función objetivo es del tipo Maximizar
2.- Todas las restricciones son del tipo <
3.- Todas las variables de Decisión son no negativas.

Matemáticamente la forma canónica se representa como:

|Maximizar Z = | n |CjXj |
||∑ | |
| |j=1 | |

Sujeta a:
| m |n |aij Xj < bj |
|∑ |∑ | |
|I=1 |j=1 | |

Xj > 0  i = 1,2, 3,…..…m; j = 1,2,3, ………n

Forma estándar:

Características: 1. La función objetivo puede ser de maximizar ó biende minimizar
2. Todas las restricciones son ecuaciones, es decir, del tipo =.
3. El lado derecho de cada ecuación de restricción es no negativo ( > 0 ), es decir, vector b positivo
4. Todas las variables de decisión son no negativas (Xj > 0)  

Matemáticamente la forma Estándar se representa como:

| | n |CjXj|
|Maximizar o Minimizar Z = |∑ | |
| |j=1 | |

Sujeta a:
| m |n |aij Xj = bj |
|∑ |∑ | |
|I=1 |j=1 | |

Xj > 0  i = 1,2, 3,…..…m; j = 1,2,3, ………n

Un modelo de PLpuede ser convertido a la forma canónica o a la forma estándar mediante la aplicación de las siguientes reglas de equivalencia:

1. Sobre la Función Objetivo
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
a) Una desigualdad con dirección < puede cambiarse a la dirección opuesta > multiplicando ambos...