• Author / Uploaded
• Sara Marcela

Citation preview

METODO DE DOS FASES

Este método difiere del Simplex en que primero hay que resolver un problema auxiliar que trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar el método Simplex normal. PRIMERA FASE: En este método siempre se minimiza una función objetivo constituida por la suma de las variables artificiales utilizadas para completar la matriz I: Mínimo Z = ΣWi Las variables artificiales son útiles para formar la primera base del simplex, pero si se logra que toda Wi=0, entonces Z=0 representa lo deseable u optimo, pues lo contrario significa un problema que no tiene solución factible, en tal caso no aplica la segunda fase. Si todo va bien, las variables artificiales Wi deben salir de la base, excepto en algún caso degenerado en que Wi=cero. SEGUNDA FASE: Se continua con esta solo si ocurre la optimización del problema en la fase anterior. Para ello sirve la tabla simplex optima de la primera, que se ajusta eliminando las columnas de las variables artificiales Wi; además, el renglón Z se cambia a los coeficientes de la función Z original. El procedimiento continua con el arreglo de la tabla simplex inicial para cumplir los requisitos necesarios de una solución básica factible; es decir, coeficientes cero para las variables básicas en el renglón Z de la tabla. A veces esto es suficiente para lograr el optimo del problema; si no es así, se aplican los criterios del simplex para el objetivo original del problema. En resumen, la fase1 intenta lograr un punto extremo factible; la fase 2, el punto extremo optimo: OBJETIVO DE: ↓

PRIMERA FASE

SEGUNDA FASE

Maximizar

Minimizar

Maximizar

Minimizar

Minimizar

Minimizar

1. Aplica método Simplex Dos Fases, PL máximo y mínimo, 3 tipos de restricción (MAXMIN2F1). Aquí se aprovecha la circunstancia de que en el método simplex de dos fases, la primera fase es igual con ambos objetivos; por lo tanto, sólo para mayor conocimiento, la tabla óptima de la 2a fase que contiene el valor máximo de la función, se utiliza para obtener el mínimo.

Figura 1.Tablas simplex 1a y 2a fase del ejemplo MAXMIN2F1.

Este ejemplo MAXMIN2F de aplicación del método simplex de dos fases, empieza el proceso de resolución convirtiendo el modelo original propuesto a su forma estándar y luego para conseguir una base artificial. Primera fase.- Se construye una función objetivo Z con la suma de las variables artificiales y se arregla al formato de restricción, tal como se muestra antes de las tablas de la primera fase. Se construye la tabla a partir de las variables básicas: la holgura H1 y las artificiales W2 y W3, ordenadas de arriba hacia abajo en la base; el

renglón Z, se llena conforme a los coeficientes de la ecuación Z - W 2 - W3 = 0, escribiendo ceros en los espacios vacíos de las variables Xj, las holguras Hi y las superávit Si; en el mismo renglón Z se ubican los coeficientes -1, característico de las variables artificiales con el método de dos fases. El resto de los coeficientes de esta primera tabla, corresponde a la forma estándar ya obtenida. Note la diferencia respecto al simplex penal: los coeficientes M de las variables artificiales en renglón Z no se usan, pero sí coeficientes -1 en la primera fase; además, las artificiales deben aportar el vector columna unitario para la base I; aunque no cumplen para variable básica, pues el -1 en el renglón Z debe anularse para el inicio. Con este propósito se hacen operaciones fila de Gauss-Jordan para conseguir ceros que sustituyan los coeficientes mencionados. En el lado izquierdo de la primera tabla se escriben las fórmulas que se usan para el cálculo de los renglones Z' y Z''; en el último se pueden ver los ceros sustituyendo los -1. Con el cálculo del renglón Z'' se completa la primera solución básica de esta primera fase y se procede a la aplicación de los criterios del simplex con el objetivo de mínimo; para optimalidad, se observa que X1 es la única variable no básica con coeficiente + en el renglón Z, (recuerde que con objetivo de mínimo, debe elegirse para VE la que tenga el coeficiente más positivo), entonces se declara a X1 como VE a la base. En factibilidad, según los cocientes a la derecha de la tabla, se identifica a la variable artificial W2 como saliente (VS) de la base, le toca actuar como pivote al coeficiente 2 colocado en el cruce de la columna X1 y el renglón W2, recién elegidos con los dos criterios. Entonces se procede al cambio de base calculando la segunda tabla de la primera fase, empezando por establecer a las variables básicas: H1 que se mantiene dentro, la nueva X1 que se hace básica, sustituye a W2 que se convierte en no básica, W3 que también permanece en la base. Se comienza el cálculo de la segunda tabla con el renglón RE que se fija como pivote para calcular el resto de los coeficientes mediante operaciones fila elementales de Gauss-Jordan; en el lado izquierdo de la tabla se anotan, como guía de cálculo, las fórmulas para cada fila. Los coeficientes indicadores en la fila Z, muestran todavía números positivos para las variables no básicas X2 y S2, lo cual significa que son candidatas para entrar a la base y la necesidad de continuar la aplicación del algoritmo; además, aún existe una variable artificial dentro de la base. Los coeficientes de X2 y S2 están empatados con valor de 1/2, de acuerdo a la recomendación dada antes, de preferir como entrante variables de decisión, así X2 = VE. Aplicando la factibilidad, también se tiene un empate en los cocientes que se presentan a la derecha de la tabla; aquí se elige a la variable W3 como saliente VS, pues ya se mencionó en párrafo anterior, la procuración del método para que las artificiales salgan lo más pronto posible de la base. Con la definición del pivote 1/2 y las fórmulas a la izquierda, se tiene lo suficiente para calcular la siguiente solución en la última tabla de la primera fase la cual muestra el valor cero en la columna solución, esto significa, que al sacar todas las variables artificiales de la base se anulan y con ello Z = 0. El resultado confirma que el problema sí tiene solución factible y procede la segunda fase. Segunda fase.- La última tabla de la primera fase sirve para iniciar la primera tabla simplex de la segunda fase, pero se eliminan las columnas de las variables

artificiales W2 y W3; también se eliminan los coeficientes del renglón Z y se sustituyen con los coeficientes de la función objetivo original: La primera tabla muestra el arreglo de coeficientes mencionado, pero se observa que las variables básicas H1, X1, X2, así ordenadas en la columna base, cumplen el requisito de tener su vector columna unitario para formar la base I, pero no cumplen con el coeficiente cero en el renglón Z para una básica, porque se acaban de escribir los coeficientes de la ecuación original. Con el propósito de corregir el planteamiento tabular de esta primera tabla se hacen las operaciones fila necesarias, las que se definen según las fórmulas construidas a la izquierda de la segunda tabla de esta fase, resultando un renglón Z' para conseguir el coeficiente cero en la variable X1 y un renglón Z'' para conseguir el cero en la variable X2. Como este renglón Z'' muestra coeficientes indicadores no negativos, el criterio de optimalidad para máximo que es el objetivo original, ya no se puede aplicar para elegir variable entrante, los indicadores cero para las variables de decisión X1 y X2, significan que tales variables ya no pueden aportar más al valor de Z. En consecuencia, sin necesidad de aplicar los criterios del simplex en esta segunda fase, ya se tiene la solución óptima en el punto extremo:

Este ejemplo, se puede aprovechar para comprobar el potencial del método de dos fases, pues la tabla óptima de la segunda fase mostrando la solución de máximo, también sirve para el cálculo de la solución mínima. Los indicadores del renglón Z sólo tienen coeficientes cero y uno positivo (2), éste último coeficiente muestra que es candidata a entrar a la base, la variable no básica S2 que se declara VE; con el criterio de factibilidad resulta que debe salir de la base la variable X2, que se define VS; con el coeficiente pivote 1 se procede al cálculo de la solución de la última tabla que muestra la solución óptima mínima para el mismo problema con el punto extremo:

2. Aplica método Simplex Dos Fases, PL mínimo y máximo, 3 tipos de restricción (MINMAX2F). Se presenta este nuevo ejemplo con el método simplex de dos fases y la solución contenida en las tablas.

Figura 2. Tablas simplex de la 1ª y 2ª fase para mínimo del ejemplo MINMAX2F.

En el renglón Z de la última tabla simplex de la segunda fase, ya no hay coeficientes indicadores positivos para el objetivo de mínimo, por lo tanto la solución óptima es: Z mínimo = 9, X1 = 1, X2 = 3, H1 = 2, H4 = 8 Como ya se mencionó, el método simplex de dos fases se presta para la obtención de los objetivos mínimo y máximo. Con tal propósito, en la misma tabla

óptima de solución mínima, se aplican los criterios para el cambio de base hacia una solución máxima como se aprecia en la tabla de la Figura 3:

Figura 3. Tabla simplex de la 2ª fase para máximo del ejemplo MINMAX2F.

3. Aplica método Simplex Dos Fases, PL mínimo y máximo (MAXMIN2F2).

Figura 4. Tabla simplex inicial para 1a fase del ejemplo MAXMIN2F2.

Se presenta ahora la aplicación del simplex dos fases mostrando en tablas separadas el progreso del cálculo. Como las variables W2 y W3 son básicas, es necesario calcularles el coeficiente de valor cero en el renglón Z con las operaciones fila: RW2(1)+RZ; RW3(1)+RZ.

Figura 5. Tablas simplex de 1a fase del ejemplo MAXMIN2F2.

2ª fase.- En la tabla óptima de primera fase se eliminan las columnas W2 y W3; el renglón Z se sustituye con los coeficientes de la función objetivo original. La base contiene a X1 y X2, pero sus coeficientes indicadores Z1-C1=-3 y Z2-C2=-2 en el nuevo renglón Z deben calcularse para el valor cero.

Figura 6. Simplex inicial 2a fase, eliminar columna Wi sustituir coeficientes en fila Z en ejemplo MAXMIN2F2.

Se procede con operaciones fila para conseguir que los coeficientes de X1 y X2 en el renglón Z se anulen: Z'=RX1(3)+RZ; Z''= RX2(2)+ RZ'; resulta la tabla siguiente con el coeficiente indicador negativo (-7) en S3 de Z. En 2ª fase es aplicable el objetivo original de máximo, por lo que S3 debe ir a la base (VE) para sustituir a H1 (VS), la única variable básica que puede dejar su lugar.

Figura 7.Tablas Simplex 2a fase del ejemplo MAXMIN2F2.

Se aprovecha la oportunidad con la flexibilidad del simplex de dos fases, para determinar también la solución mínima del mismo problema. Entonces con el objetivo de mínimo, se declara VE a la base, la variable no básica H1 y la básica S3 sale, para dejarle ese lugar.

Figura 8. Tabla simplex óptima de 2ª fase, para mínimo, ejemplo MAXMIN2F2.

VENTAJAS:

Desde el punto de vista computacional, este método presenta varias ventajas sobre el método de las M. Básicamente, las ventajas están relacionadas con la selección del valor numérico de M: 1. Si M es muy grande. Dado que cualquier computadora maneja un muero de

dígitos limitado, la gran diferencia, surgida al escoger una M muy grande, entre los términos de los efectos neto que contienen a M y los que no la contienen, puede causar errores de redondeo. Por ejemplo, podemos observar que hay VA en la base, los efectos netos de las variables no básicas son del tipo ɸj= k1 M+ k2

Si la computadora tuviera solamente cuatro dígitos y si para la variable no básica xi , k1 M=1230 y k2 =2.4996, entonces el efecto neto quedaría como ɸj= 1230+2.4996=1232

Perdiéndose en el redondeo cuatro dígitos significativos. Sin embargo, si las VA dejan la base, los términos k1 M desaparecen con lo que resultaría ɸj= 2

Lo cual es incorrecto. Ante esta primer desventaja, la única opción consistiría en recalcular todos los ɸj desde su definición para evitar el error de redondeo, lo cual, operacionalmente, es prohibitivo. 2. Si M es muy pequeña. Bajo esta posibilidad podríamos obtener una

respuesta incorrecta al no establecerse realmente una penalización al valor de x0 por darle valores positivos a las VA. Por ejemplo, si en una iteración dada k1 resulta ser muy pequeña, podría suceder que k2 no sea tan despreciable comparada con k1 M y concluirse que el PO es inconsistente cuando en realidad no lo es. Por tanto, considerando las desventajas computacionales del método de la M, el método de las dos fases se constituye en el más utilizado en la actualidad para resolver problemas reales de PL.