metodo de dos fases

5/13/2018 Metodo de Dos Fases - slidepdf.com

http://slidepdf.com/reader/full/metodo-de-dos-fases-55a7512a3acdd 1/12

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 locontrario 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 derestricció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 lafunció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, empiezael proceso de resolución convirtiendo el modelo original propuesto a su formaestándar y luego para conseguir una base artificial.

Primera fase.- Se construye una función objetivo Z con la suma de las variablesartificiales y se arregla al formato de restricción, tal como se muestra antes de lastablas de la primera fase. Se construye la tabla a partir de las variables básicas: laholgura 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 X j, las holguras Hi y lassuperávit Si; en el mismo renglón Z se ubican los coeficientes -1, característico delas variables artificiales con el método de dos fases. El resto de los coeficientes deesta primera tabla, corresponde a la forma estándar ya obtenida. Note la diferenciarespecto al simplex penal: los coeficientes M de las variables artificiales en renglónZ no se usan, pero sí coeficientes -1 en la primera fase; además, las artificialesdeben aportar el vector columna unitario para la base I; aunque no cumplen paravariable básica, pues el -1 en el renglón Z debe anularse para el inicio. Con estepropósito se hacen operaciones fila de Gauss-Jordan para conseguir ceros quesustituyan los coeficientes mencionados. En el lado izquierdo de la primera tablase 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 estaprimera fase y se procede a la aplicación de los criterios del simplex conel objetivo de mínimo; para optimalidad, se observa que X1 es la única variable nobá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 sedeclara a X1 como VE a la base. En factibilidad, según los cocientes a la derechade la tabla, se identifica a la variable artificial W2 como saliente (VS) de la base, letoca actuar como pivote al coeficiente 2 colocado en el cruce de la columna X 1 y elrenglón W2, recién elegidos con los dos criterios.

Entonces se procede al cambio de base calculando la segunda tabla de la primerafase, empezando por establecer a las variables básicas: H1 que se mantienedentro, la nueva X1 que se hace básica, sustituye a W2 que se convierte en nobásica, W3 que también permanece en la base. Se comienza el cálculo de lasegunda tabla con el renglón RE que se fija como pivote para calcular el resto delos coeficientes mediante operaciones fila elementales de Gauss-Jordan; en ellado izquierdo de la tabla se anotan, como guía de cálculo, las fórmulas para cadafila.

Los coeficientes indicadores en la fila Z, muestran todavía números positivos paralas variables no básicas X2 y S2, lo cual significa que son candidatas para entrar ala base y la necesidad de continuar la aplicación del algoritmo; además, aún existeuna variable artificial dentro de la base. Los coeficientes de X2 y S2 estánempatados con valor de 1/2, de acuerdo a la recomendación dada antes, depreferir 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 latabla; aquí se elige a la variable W3 como saliente VS, pues ya se mencionó enpárrafo anterior, la procuración del método para que las artificiales salgan lo máspronto posible de la base. Con la definición del pivote 1/2 y las fórmulas a laizquierda, se tiene lo suficiente para calcular la siguiente solución en la última tablade la primera fase la cual muestra el valor cero en la columna solución, estosignifica, que al sacar todas las variables artificiales de la base se anulan y conello Z = 0. El resultado confirma que el problema sí tiene solución factible yprocede la segunda fase.

Segunda fase.- La última tabla de la primera fase sirve para iniciar la primeratabla 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 sesustituyen 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 elrequisito de tener su vector columna unitario para formar la base I, pero nocumplen con el coeficiente cero en el renglón Z para una básica, porque seacaban de escribir los coeficientes de la ecuación original. Con el propósito decorregir el planteamiento tabular de esta primera tabla se hacen las operacionesfila necesarias, las que se definen según las fórmulas construidas a la izquierda dela segunda tabla de esta fase, resultando un renglón Z' para conseguir elcoeficiente cero en la variable X1 y un renglón Z'' para conseguir el cero en lavariable 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 puedeaplicar para elegir variable entrante, los indicadores cero para las variables dedecisió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 estasegunda fase, ya se tiene la solución óptima en el punto extremo:

Este ejemplo, se puede aprovechar para comprobar el potencial del método dedos fases, pues la tabla óptima de la segunda fase mostrando la solución demáximo, también sirve para el cálculo de la solución mínima. Los indicadores delrenglón Z sólo tienen coeficientes cero y uno positivo (2), éste último coeficientemuestra que es candidata a entrar a la base, la variable no básica S2 que sedeclara VE; con el criterio de factibilidad resulta que debe salir de la base lavariable 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 mismoproblema con el punto extremo:

2. Aplica método Simplex Dos Fases, PL mínimo y máximo, 3 tipos derestricción (MINMAX2F).

Se presenta este nuevo ejemplo con el método simplex de dos fases y la solucióncontenida 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 haycoeficientes indicadores positivos para el objetivo de mínimo, por lo tanto lasolució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 laobtenció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 haciauna 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 tablasseparadas el progreso del cálculo. Como las variables W2 y W3 son básicas, esnecesario calcularles el coeficiente de valor cero en el renglón Z con lasoperaciones 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 W 2 y W3; elrengló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 elnuevo renglón Z deben calcularse para el valor cero.

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

Se procede con operaciones fila para conseguir que los coeficientes de X1 y X2 enel renglón Z se anulen: Z'=RX1(3)+RZ; Z''= RX2(2)+ RZ'; resulta la tabla siguientecon el coeficiente indicador negativo (-7) en S3 de Z. En 2ª fase es aplicable elobjetivo original de máximo, por lo que S3 debe ir a la base (VE) para sustituir aH1 (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, paradeterminar 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 nobá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.

metodo de dos fases

Documents