Ingenieria

Investigacion de Operaciones
Anterior Siguiente
2.5.1. Método Simplex penal o de la M grande.

El simplex penal es una variante del método simplex aplicable en los casos en que las variables artificiales son necesarias en el problema, ya sea de maximizar o también de minimizar. El nombre de simplex penal se explica porque se penaliza con un coeficiente M, que representa un valor muy grande(mayor que cualquier otro coeficiente del problema), a cada variable artificial W i que se incluya en la función objetivo del problema. Para máximo se utiliza la penalización con signo menos (- M), por otro lado para mínimo se utiliza signo más (+ M).

Las variables artificiales se usan para la primera solución básica del simplex, pero el valor muy grande del coeficiente M, procura su rápidasalida de la base cuando el problema tiene solución factible. Aunque algún caso degenerado puede tener una variable artificial en la base con valor cero; vea ejemplos Artbás0deg3v4r(16), Artabás02f(2), Ciclodeg(27) en programa CAVA (próximo a liberarse). Por el contrario, si no es posible anular las variables artificiales (W i >0), significa que no hay solución factible al problema; vea ejemploArtinofac en programa CAVA.

El siguiente Ejemplo 2-2 es un problema de PL que requiere variables artificiales para intentar resolverlo y corresponde al Ejemplo 1-16 utilizado con método gráfico, también incluidos en el programa CAVA (próximo a liberarse):

Ejemplo 2-2. Aplica método Simplex Penal, PL en máximo con 3 tipos de restricción (FACTIRECTA).

Figura 2-8. Tablas del método simplex penalaplicado al ejemplo FACTIRECTA.

Solución óptima en vértice C de la analogía geométrica en (Figura 1-45): máximo Zc = 14 y el programa en última tabla: X1 = 2, X2 = 4, H1=S2=W2=W3 = 0.

El ejemplo FACTIRECTA mostrado contiene la aplicación del método simplex penal; como ya se mencionó, hay necesidad de utilizar variables artificiales para resolverlo. Primero se prepara el problema convirtiendoa igualdades para forma estándar del modelo propuesto, sumando una variable de holgura H1 en la restricción (1), después se resta una variable S2 de superávit en la (2), la restricción (3) es de tipo = por lo que se deja como está; se condiciona toda variable X j >= 0 y con la función objetivo original ya se tiene este modelo como estándar. Pero así no se completa la matriz cuadrada unitaria I quedebe ser de orden m = 3 restricciones, pues sólo se tiene el vector unitario de la variable de holgura H1 que sí aporta el coeficiente +1, faltando dos vectores unitarios. Aquí surge la necesidad de utilizar el artificio matemático ya referido. En las restricciones (2) y (3) que son de >= e =; se suman variables artificiales W2 y W3, aportando cada una de ellas el necesario coeficiente +1, con loque se completa la matriz I mostrada antes de la tabla simplex, quedando el modelo que se presenta con base artificial. Esta variante del simplex, incluye a las variables artificiales en la función objetivo, pero penalizadas con un coeficiente M, que representa un valor mayor que cualquier otro coeficiente presente en el modelo; para este ejemplo se le asigna -M como coeficiente a las variablesartificiales W2 y W3, cumpliendo así con la penalización de la función objetivo la cual se arregla al formato de las restricciones, restando el lado derecho a la variable Z, consiguiendo el término independiente cero en el lado derecho.

En segundo lugar debe prepararse la tabla simplex con la primera solución básica "factible", la que se consigue con las variables artificiales W2 y W3,procurando su pronta anulación con los cambios de la base. Se inicia con los renglones y columnas y los encabezados necesarios para copiar ordenadamente los coeficientes del modelo, tal como se presentan en la forma con base artificial y la función Z arreglada con término independiente; los lugares vacíos se llenan con cero. Aquí anote que la matriz I, no necesariamente se forma con sus vectores...