• Author / Uploaded
• Sulpick Barbella

• Categories
• Programación lineal
• Matemática aplicada
• Áreas de la informática
• Conceptos matemáticos
• Física y matemáticas

Citation preview

Segunda Técnica Técnica de las Dos Fases

Definición En el método M, el uso de la penalización M puede conducir a un error de redondeo. El método de dos fases elimina el uso de la constante M, como su nombre lo indica, el método resuelve problemas de programación lineal en dos fases; en la fase I se trata de encontrar la solución factible básica inicial y, si se halla una, se invoca la fase II para resolver el problema original. Las dos fases que se aplican son las siguientes: Fase I. Se pone el problema en forma de ecuación y se agregan las variables artificiales necesarias a las restricciones (exactamente como en el método M), para tener la certeza de una solución básica. A continuación, se determina una solución básica de la ecuación resultante que siempre minimice la suma de las variables artificiales, independientemente de si el objetivo del problema es de maximización o minimización. Si el valor mínimo de la suma es positivo, el problema de programación lineal no tiene una solución factible. De lo contrario, si el valor mínimo es cero, prosiga con la fase II. Fase II. Use la solución factible de la fase I como una solución factible básica inicial para el problema original.

Objetivos que se persiguen al aplicar la técnica:

Esta técnica elimina el uso de la constante M, que puede provocar problemas en el redondeo de cifras, la cual es una de las desventajas que tiene la técnica M, ya que un posible error de cómputo que podría resultar de asignar un valor muy grande a la constante M. Para evitar esta dificultad el problema se puede resolver en 2 fases. Éste 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.

Requerimientos para aplicar la Técnico

Esta técnica se utiliza en la solución de problemas de Programación Lineal, que presentan los siguientes requerimientos.

Modificar las restricciones para que el lado derecho sea no negativo Convertir las desigualdades a su forma estándar. Añadir una variable artificial no negativa (a) a las restricciones que en el paso 1 fueran = 0

Procedimiento para aplicar la técnica de las Dos Fases Esta técnica resuelve un problema de Programación Lineal, de la siguiente forma:

Se formula el problema inicial reemplazando X0 (La función objetivo) por la suma de las variables artificiales únicamente (R1, R2, etc.). Las restricciones quedan igual que las del problema original. Si el problema tiene un espacio factible, el valor mínimo de la nueva función objetivo (R 0) indica que todas las variables artificiales son cero. Si lo anterior no se cumple, el problema termina concluyendo que no existe solución factible. Si el valor mínimo fue cero en la anterior (R0 = 0) se utiliza la solución final como inicio de esta fase colocando únicamente la X0 del problema original con valor de solución cero. A partir de aquí se sustituyen los valores de las casillas de X0 correspondientes a las columnas pivotes considerando además, el tipo de objetivo que este (PL) tenga.

Ejemplo de Aplicación

Maximizar la siguiente función:

2X1 – 3X2 Restricciones: -X1 + X2 >= 10 X1 >= 0, X2 >= 0

Fase I Al agregar S1 como variable de exceso en la restricción 1 resulta evidente que no se dispone de una solución básica factible inicial, por tanto utilizaremos una variable auxiliar "y" que incluiremos en el lado izquierdo de la restricción y que servirá como variable básica inicial. Esto define el problema inicial de la Fase 1 junto a su tabla.

Minimizar: Y (Nuestra R0, explicada en la teoría anterior)

Restricciones: -X1 + X2 – S1 + Y= 10

(Se mantienen la restricciones)

X1, X2, S1, Y >= 0

Luego la variable X2 entra a la base (costo reducido negativo) y claramente "y" deja la base. Se actualiza la tabla utilizando el método simplex:

Con esta tabla finaliza la Fase 1. Notar que el valor de la función objetivo al finalizar la Fase 1 es cero, por tanto podemos continuar la Fase 2.

Fase II Se elimina la columna asociada a la variable artificial "y" y se actualiza el vector de costos reducidos considerando la función objetivo original. De esta forma se obtiene la tabla inicial de la Fase 2.

Dado que X2 es variable básica al finalizar la Fase 1 buscamos dejar esta misma variable como básica al iniciar la Fase 2. Para ello multiplicamos por -3 la fila 1 y luego la sumamos a la fila 2.

En este sencillo ejemplo se llega inmediatamente a la tabla final de la Fase 2, con solución óptima X1=0 y X2=10. El valor óptimo V (P)=-30.