Descripción clara del Método de la Gran M
araguiro380Apuntes28 de Agosto de 2015
3.023 Palabras (13 Páginas)150 Visitas
Contenido
Descripción clara del Método de la Gran M
1. Convertir al Modelo Estándar:
2. Escribir en formato de Tabla Simplex.
Descripción clara del Método de la Gran M
Mientras que los Programas Lineales que solo tienen restricciones de <= se pueden resolver sólo usando variables de holgura, para aquellos programas lineales que involucren restricciones de tipo >= e = es necesario como ya lo habíamos comentado, usar variables artificiales. Dijimos también que las variables de holgura tenían un significado físico real que correspondía a las disponibilidades o requerimientos no usados en las restricciones, pero que las variables artificiales no tenían ninguna representación física y que sólo eran usadas como un comodín matemático para ayudar en la solución del problema. Pues bien, cuando tenemos que usar variables artificiales al tener restricciones de >= e = debemos usar uno de las siguientes variantes del simplex:
- El Método de la Gran M
- El Método de las dos fases
Aquí detallaremos el Método de la Gran M.
Definimos la letra M como un número muy grande pero finito para usarlo como coeficiente de las variables artificiales en la función objetivo y con sentido contrario a la misma para penalizar de manera muy grande la existencia de las mismas en la solución. Si el objetivo es minimizar las variables artirficiales entraran con M positivo y si es maximizar las variables artificiales se usaran como -M.
Ejemplo:
Min Z = 2X1 + X2 + 3X3
Sujeto a:
3X1 + X2 + 2X3 <= 10
X1 - 2X2 + 3X3 >= 6
2X1 + 3X2 - X3 <= 9
X1 + X2 +2X3 = 7
C.N.N
1. Convertir al Modelo Estándar:
Cada restricción debe ser convertida de inecuación a una igualdad, agregando variables como se requiera. Con las restricciones de tipo <=, es supremamente fácil. Simplemente se agrega una en cada restricción con coeficiente 1 en la misma restricción y con coeficiente cero en la función objetivo. Por ejemplo:
3X1 + X2 + 2X3 <= 10 queda:
3X1 + X2 + 2X3 + S1 = 10
Se puede leer así: el uso de la primera restricción no puede superar la disponibilidad de 10 unidades, lo que equivale a decir que lo usado mas lo que sobre (s1) es igual a 10. Para las restricciones de tipo mayor o igual, la lógica es la misma, de esta manera decir:
X1 - 2X2 + 3X3 >= 6
Se puede leer como: el uso de la restricción 2 debe ser como mínimo 6 unidades. Eso significa que el uso podría ser 6.1 o tal vez 7 u 8... etc. Podríamos escribirlo también como 6+0.1 o 6+1 o 6+2 ... o en términos generales:
X1 - 2X2 + 3X3 = 6 + S2 que es equivalente a decir: lo usado en la restricción2es igual al mínimo requerido que es 6 más el adicional que está en S2. Esto lo podemos reescribir como:
X1 - 2X2 + 3X3 - S2 = 6
Sin embargo para el método simplex, cuando aparece esta restricción tipo >= es necesario adicionar una variable comodín, llamada Variable Artificial, sin ningún significado físico, sólo como artificio matemático. Lo sumamos al lado izquierdo de la restricción como se muestra a continuación:
X1 - 2X2 + 3X3 - S2 + A1 = 6
Al usar una variable artificial debemos penalizar la función objetivo allí la vamos a incluir con un coeficiente muy grande, llamado M, al estar minimizando la sumamos + .MA1.
La tercera restricción es de tipo <=, por lo que no tenemos ningún problema con ella:
2X1 + 3X2 - X3 <= 9 queda
2X1 + 3X2 - X3 + S3 = 9
La cuarta restricción es de tipo =. Para este tipo de restricción simplemente adicionamos una variable artificial al lado izquierdo:
X1 + X2 +2X3 = 7 queda:
X1 + X2 +2X3 + A2 = 7
Recordemos: las variables de holgura quedan con coeficiente 0 en la función objetivo y las variables artificiales con coeficiente M. Positiva si es minimizando o negativa si es maximizando.
En resumen el modelo queda de la siguiente manera:
Min Z = 2X1 + X2 + 3X3 + 0S1 + 0S2 + MA1 + 0S3 + MA2
Sujeto a:
3X1 + X2 + 2X3 + S1 = 10
X1 - 2X2 + 3X3 - S2 + A1 = 6
2X1 + 3X2 - X3 + S3 = 9
X1 + X2 + 2X3 + A2 = 7
2. Escribir en formato de Tabla Simplex.
Si lo escribimos como una matriz, indicando los nombres de las variables en negro queda asi:
Fig 1
| X1 | X2 | X3 | S1 | S2 | A1 | S3 | A2 |
|
Min Z | 2 | 1 | 3 | 0 | 0 | M | 0 | M | RHS |
R1 | 3 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 10 |
R2 | 1 | -2 | 3 | 0 | -1 | 1 | 0 | 0 | 6 |
R3 | 2 | 3 | -1 | 0 | 0 | 0 | 1 | 0 | 9 |
R4 | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 1 | 7 |
Dónde X1, X2, X3 son las variables de decisión, S1, S2 y S3 son las variables de Holgura. R1, R2, R3, R4 son las restricciones y RHS son las disponibilidades o Requerimientos de las restricciones, (RHS= Right Hand Side: "el lado derecho" es decir los valores numéricos).
...