Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Método de las Dos Fases

Investigación de Operaciones 1
by

Byron Garcia

on 14 June 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Método de las Dos Fases

Método de las dos Fases
Investigación de Operaciones 1
Requerimientos
Convertir las desigualdades en su forma estándar
Añadir una variable artificial no negativa (a) a las restricciones que en el paso 1 fueran = 0
Modificar las restricciones para el lado derecho sea no negativo.
(cc) photo by theaucitron on Flickr
Es una técnica utilizada en la solución de problemas de Programación Lineal.
Que es la Técnica de las dos Fases?
Que requerimientos
debe de cumplir?
Grupo #8
Pasos para resolver problemas de programación linea......!
Paso 1:
Se formula el problema inicial reemplazando Xo por la suma de las variables artificiales únicamente (R1, R2, etc.).
Las restricciones quedan igual que las del problema original.
Introducción
Este método es sumamente sencillo. Se usa ante la presencia de variables artificiales en el modelo a solucionar y su objetivo es eludir el uso de la constante M, aquella que definimos como un número muy grande aunque finito, supuestamente por problemas de redondeo o de escala.
Como desarrollador de software, sé que el algoritmo puede tratar a la M como una constante si se le asigna un valor, o como una variable a la que se le asigne el valor requerido (que respete la definición) en cada comparación, como lo hacen las personas que resuelven a mano.
Habría más bien que comparar la eficiencia de los algoritmos a nivel de volumen de cálculos, de número de tableros, etc., para decantarse por uno u otro.
Objetivos
Conclusiones
El método de dos fases, se conforma efectivamente valga redundancia de dos fases, de un modelo de programa lineal a solucionar por la minimización de la suma de las variables artificiales encontradas en la normalización del modelo.
Defiende una manera más compacta al momento de resolver el método simplex, incluye dos fases que describe la pronta solución de unas formas más prácticas y efectivas.
 Para la comprensión de éste algoritmo es preferible entender primero el Método M, aunque no es estrictamente necesario.
 El método de dos fases, se usa ante la presencia de variables artificiales en el modelo a solucionar y después eludir el uso de la constante M.
Cada restricción debe ser convertida de inecuación a una igualdad, agregando variables como se requiera.
Si el problema tiene un espacio factible, el valor mínimo de la nueva función objetivo (Ro), lo cual 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 (Ro = 0) se utiliza la solución final com33o inicio de esta fase colocando únicamente la Xo del problema original con valor de solución cero.
A partir de aquí se sustituyen los valores de las casillas de Xo correspondintes a las columnas pivotes considerando además, el tipo de objetivo que este (PL) tenga. 
Paso 2:
Resolver un problema LP cuya función objetivo (w) sea minimizar la suma de las variables artificiales (FASE 1)
Si el valor óptimo de w es positivo el problema original no tiene solución factible
Si el valor óptimo de w es 0 y no hay variables artificiales en la solución básica se eliminan las columnas de la tabla óptima de la fase 1 que corresponden a las variables artificiales y se combinan la función objetivo original con las restricciones de dicha tabla.(Fase 2).
Otras Aplicaciones del Método
de Dos fases
Y llevando este resultado a las otras expresiones:







En la expresión a maximizar vemos que cuanto más pequeño sea el valor de las variables sin llegar a ser negativo, mas se optimiza esta. Puesto que tiene que cumplirse la inecuación, es trivial que tomemos x1 = 0. De ahí x3 = 10.

Considerando de nuevo la restricción igualdad se deduce inmediatamente x2 = 46/3 y, en consecuencia, F máx = - 14.
El pivote para este caso es v13 y la tercera tabla es:








Hemos llegado a una solución óptima en la que la función objetivo, G(x) es nula; por lo tanto, el problema original tiene solución finita que podemos obtener aplicando nuevamente el algoritmo. Para la tabla siguiente hemos de cambiar la función objetivo y, por tanto, los Cq – Fq:
Para la siguiente tabla el pivote es v22 y tenemos:







Puesto que todos los Cq – Fq son positivos hemos llegado a la solución óptima que es:



Este problema puede también resolverse de otro modo. Si consideramos la restricción que es igualdad, podemos despejar de ella una de las variables en función de las otras y rebajar el problema en una dimensión. En principio podemos suponer que la variable despejada no será nula al final por lo que nos interesa separar aquella que favorezca la optimización. En este caso tomaremos x2. De ese modo:

3•x2 = x1 + 5•x3 – 4
La primera tabla del algoritmo para el método de las dos fases es:








El pivote de la transformación es v21 y la segunda tabla queda:
El problema es idéntico al de minimizar la función:
Z' = 8x1 -3x2 + 6x3

Aplicaremos el método simplex y para ello buscamos una solución básica por el método de las dos fases:

Min : G(x) = x5 + x6

Sujeto a:



Para el problema ampliado una solución básica es:
Ejemplo 1
Min. Xo = 5X1 – 6X2 – 7X3
 
s.a.

5X1 – 6X2 + 10X3  20
X1 + 5X2 – 3X3  15
X1 + X2 + X3 = 5
Xi  0
 

EJEMPLO No.2
SOLUCION
 
Fase 1
 
Forma Estándar
 
5X1 – 6X2 + 10X3 + S1 = 20
X1 + 5X2 – 3X3 – S2 + R1 = 15
X1 + X2 + X3 + R2 = 5

Min.

Ro = R1 + R2
Ro – R1 –R2 = 0
Tablero Inicial
El tablero anterior, se vuelve tablero inicial, por lo que se suman R1 y R2 al valor de la fila Ro
Al haber llegado a Ro = 0, se continua en la siguiente fase, copiando el tablero final de la primera fase, pero sustituyendo la función objetivo con los valores de la original, y ya no se trabajan con las columnas de las penalizaciones (R1 y R2); y se sigue trabajando con el método SIMPLEX
TABLERO FINAL
R/
Xo = -125/4
X2 = 15/4
X3 = 5/4
S1 = 30

SOLUCIÓN FINAL
Gracias
por su Atención..!

Conocer la decisión del método de Dos Fases, los pasos para resolver el problema de Programación Lineal por medio de dos fases y comprender cuando es más efectivo utilizarlo.
1. Definir si el método de Dos Fases es una manera más compacta de resolver el método simplex.
2. Comprender si el uso de este método requiere de una previa comprensión de la técnica M para solucionar problemas de programación lineal.
4.Conocer las variables matemáticas que permiten dar solución al problema de programación lineal por medio de la técnica de Dos Fases.
3. Conocer la manera de convertir las inecuaciones para dar solución por medio de la técnica de Dos Fases.
Objetivo General
Objetivos Específicos
Full transcript