investigacion de operaciones
Páginas: 6 (1467 palabras)
Publicado: 27 de octubre de 2013
EL MÉTODO DE LAS
DOS FASES
OBJETIVO: PRESENTAR LA FORMA DE
INICIALIZACIÓN POR EL MÉTODO DE LAS
DOS FASES
TEMAS:
MÉTODO DE LAS DOS FASES
CONCLUSIONES
17/04/2007 04:48 p.m.
1
MÉTODO DE LAS DOS FASES
Un segundo método para solucionar problemas con
variables artificiales es el método de las dos fases; tal
como su nombre lo dice, resolverá el problema en dos
etapas:
Una paraminimizar el valor de las variables artificiales y
dar una solución inicial básica factible.
La segunda, si es que se logra obtener una solución
básica factible, para optimizar el problema original.
17/04/2007 04:48 p.m.
2
MÉTODO DE LAS DOS FASES
FASE I.
Se realiza la minimización de una función que está
compuesta por la suma de los valores de la variables
artificiales; para elsistema aumentado del problema
original. (Independientemente de qué función objetivo
tenga el problema original).
Si en la solución óptima de la FASE I, el valor de las
variables artificiales es de cero, se procede con la
FASE II tomando la solución básica factible resultante.
Si alguna de las variables artificiales tiene un valor
distinto a cero, el problema original es infactible.
17/04/200704:48 p.m.
3
MÉTODO DE LAS DOS FASES
FASE II.
Utilizando la solución básica factible final de la FASE I,
se resuelve el problema original, esto es, se resuelve
para la función objetivo del problema original; si se
desea, se pueden eliminar las columnas artificiales.
Nótese que primeramente debe actualizarse
correctamente el renglón cero para el conjunto de
variables básicas quedefinió la FASE I.
Con la tabla en forma correcta se procede a optimizar de
forma habitual siguiendo el algoritmo Simplex.
17/04/2007 04:48 p.m.
4
MÉTODO DE LAS DOS FASES
Ejercicio 18
Considere el siguiente problema de
maximización
max z = 4 x1 + 2 x2 + 3 x3 + 5 x4
sujeta a
2 x1 + 3 x2 + 4 x3 + 2 x4 = 300
8 x1 + x2 + x3 + 5 x4 = 300
x2, x3, x4 ≥ 0
x1,
17/04/2007 04:48 p.m.
5 MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
min f = A1 + A2
sujeta a
2 x1 + 3 x2 + 4 x3 + 2 x4 + A1
= 300
+ A2 = 300
8 x1 + x2 + x3 + 5 x4
x1,
x2, x3, x4 , A1 , A2 ≥ 0
17/04/2007 04:48 p.m.
6
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Ahora para resolver como un problema de
maximización:
max -f = -A1 - A2
sujeta a
2 x1 + 3 x2 + 4 x3 + 2 x4 + A1
= 300
8 x1+ x2 + x3 + 5 x4
+ A2 = 300
x2, x3, x4 , A1 , A2 ≥ 0
x1,
17/04/2007 04:48 p.m.
7
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Tabla Simplex
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1
0
0
0
0
1
1
0
A1
(1)
0
2
3
4
2
1
0
300
A2
(2)
0
8
1
1
5
0
1
300
V.B17/04/2007 04:48 p.m.
Lado
derecho
8
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1
0
0
0
0
1
1
0
A1
(1)
0
2
3
4
2
1
0
300
A2
(2)
0
8
11
5
0
1
300
V.B
17/04/2007 04:48 p.m.
Lado
derecho
9
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1
-2
-3
-4
-2
0
1
-300
A1
(1)
0
2
3
4
2
10
300
A2
(2)
0
8
1
1
5
0
1
300
V.B
Lado
derecho
-1 (renglón 1) + (renglón 0)
17/04/2007 04:48 p.m.
10
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1...
DOS FASES
OBJETIVO: PRESENTAR LA FORMA DE
INICIALIZACIÓN POR EL MÉTODO DE LAS
DOS FASES
TEMAS:
MÉTODO DE LAS DOS FASES
CONCLUSIONES
17/04/2007 04:48 p.m.
1
MÉTODO DE LAS DOS FASES
Un segundo método para solucionar problemas con
variables artificiales es el método de las dos fases; tal
como su nombre lo dice, resolverá el problema en dos
etapas:
Una paraminimizar el valor de las variables artificiales y
dar una solución inicial básica factible.
La segunda, si es que se logra obtener una solución
básica factible, para optimizar el problema original.
17/04/2007 04:48 p.m.
2
MÉTODO DE LAS DOS FASES
FASE I.
Se realiza la minimización de una función que está
compuesta por la suma de los valores de la variables
artificiales; para elsistema aumentado del problema
original. (Independientemente de qué función objetivo
tenga el problema original).
Si en la solución óptima de la FASE I, el valor de las
variables artificiales es de cero, se procede con la
FASE II tomando la solución básica factible resultante.
Si alguna de las variables artificiales tiene un valor
distinto a cero, el problema original es infactible.
17/04/200704:48 p.m.
3
MÉTODO DE LAS DOS FASES
FASE II.
Utilizando la solución básica factible final de la FASE I,
se resuelve el problema original, esto es, se resuelve
para la función objetivo del problema original; si se
desea, se pueden eliminar las columnas artificiales.
Nótese que primeramente debe actualizarse
correctamente el renglón cero para el conjunto de
variables básicas quedefinió la FASE I.
Con la tabla en forma correcta se procede a optimizar de
forma habitual siguiendo el algoritmo Simplex.
17/04/2007 04:48 p.m.
4
MÉTODO DE LAS DOS FASES
Ejercicio 18
Considere el siguiente problema de
maximización
max z = 4 x1 + 2 x2 + 3 x3 + 5 x4
sujeta a
2 x1 + 3 x2 + 4 x3 + 2 x4 = 300
8 x1 + x2 + x3 + 5 x4 = 300
x2, x3, x4 ≥ 0
x1,
17/04/2007 04:48 p.m.
5 MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
min f = A1 + A2
sujeta a
2 x1 + 3 x2 + 4 x3 + 2 x4 + A1
= 300
+ A2 = 300
8 x1 + x2 + x3 + 5 x4
x1,
x2, x3, x4 , A1 , A2 ≥ 0
17/04/2007 04:48 p.m.
6
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Ahora para resolver como un problema de
maximización:
max -f = -A1 - A2
sujeta a
2 x1 + 3 x2 + 4 x3 + 2 x4 + A1
= 300
8 x1+ x2 + x3 + 5 x4
+ A2 = 300
x2, x3, x4 , A1 , A2 ≥ 0
x1,
17/04/2007 04:48 p.m.
7
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Tabla Simplex
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1
0
0
0
0
1
1
0
A1
(1)
0
2
3
4
2
1
0
300
A2
(2)
0
8
1
1
5
0
1
300
V.B17/04/2007 04:48 p.m.
Lado
derecho
8
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1
0
0
0
0
1
1
0
A1
(1)
0
2
3
4
2
1
0
300
A2
(2)
0
8
11
5
0
1
300
V.B
17/04/2007 04:48 p.m.
Lado
derecho
9
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1
-2
-3
-4
-2
0
1
-300
A1
(1)
0
2
3
4
2
10
300
A2
(2)
0
8
1
1
5
0
1
300
V.B
Lado
derecho
-1 (renglón 1) + (renglón 0)
17/04/2007 04:48 p.m.
10
MÉTODO DE LAS DOS FASES
FASE I: min f = A1 + A2
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes
Ec
(R)
f
x1
x2
x3
x4
A1
A2
f
(0)
-1...
Leer documento completo
Regístrate para leer el documento completo.