05_ind2209_alumno_15
Post on 29-Jan-2016
225 Views
Preview:
DESCRIPTION
TRANSCRIPT
Investigación de OperacionesIND2209
Profesor: Pamela Álvarez M.
Facultad de IngenieríaDepartamento de Ciencias de la Ingeniería
Unidad Nº 3
IND2209. Prof.: Pamela Álvarez M.
• Algunas preguntas que debemos responder:
• ¿Cómo encontrar una base factible inicial si no es evidente?:
• Método de las dos fases• Método de la Big‐M
• ¿Cómo identificar?:
• Múltiples soluciones• Problemas no acotados• Problemas degenerados
2
MÉTODO SIMPLEX
IND2209. Prof.: Pamela Álvarez M.
• Dado el problema:
3
MÚLTIPLES SOLUCIONES
1 2
1 2
1 2
1 2
2. . 3 9
2 6, 0
Max x xs a x x
x xx x
-1 3 1 0 92 1 0 1 6-2 -1 0 0 0
x1 x2 x3 x4 b
0 7/2 1 1/2 121 1/2 0 1/2 30 0 0 1 6
x1 x2 x3 x4 b
Solución óptima, pero veamos qué pasa si entramos x2a la base.
IND2209. Prof.: Pamela Álvarez M. 4
MÚLTIPLES SOLUCIONES
1 2
1 2
1 2
1 2
2. . 3 9
2 6, 0
Max x xs a x x
x xx x
0 7/2 1 1/2 121 1/2 0 1/2 30 0 0 1 6
x1 x2 x3 x4 b
También solución óptima. Veamos qué pasa si entramos x3 a la base.
0 1 2/7 1/7 24/71 0 -1/7 6/14 9/70 0 0 1 6
x1 x2 x3 x4 b
IND2209. Prof.: Pamela Álvarez M. 5
MÚLTIPLES SOLUCIONES
1 2
1 2
1 2
1 2
2. . 3 9
2 6, 0
Max x xs a x x
x xx x
También solución óptima. 0 7/2 1 1/2 121 1/2 0 1/2 30 0 0 1 6
x1 x2 x3 x4 b
0 1 2/7 1/7 24/71 0 -1/7 6/14 9/70 0 0 1 6
x1 x2 x3 x4 b
Existe solución múltiple si los costos reducidos de las variables no básicas son
iguales a cero.
IND2209. Prof.: Pamela Álvarez M.
Es decir, cualquier combinación
convexa de los 2 vértices es una
solución óptima también.
6
MÚLTIPLES SOLUCIONES
1 2
1 2
1 2
1 2
2. . 3 9
2 6, 0
Max x xs a x x
x xx x
x2
x1
*
3 9 / 7 9 12 / 70 24 / 7 24 1 / 7
1 , 0,112 0 120 0 0
x
IND2209. Prof.: Pamela Álvarez M.
• Dado el problema:
7
PROBLEMAS NO ACOTADOS
-1 1 1 0 2-1 2 0 1 6-2 -1 0 0 0
x1 x2 x3 x4 b
Problema no acotado
1 2
1 2
1 2
1 2
2. . 2
2 6, 0
Max z x xs a x x
x xx x
?
x2
x1
IND2209. Prof.: Pamela Álvarez M.
• Dado el problema:
8
SOLUCIONES DEGENERADAS
1 2
1 2
1
2
1 2
. 4 5 4054
, 0
Max x xs a x x
xxx x
4 5 1 0 0 401 0 0 1 0 50 1 0 0 1 4-1 -1 0 0 0 0
x1 x2 x3 x4 x5 b
Empate, pero veamos qué pasa si sale x5 de la base.
0 5 1 -4 0 201 0 0 1 0 50 1 0 0 1 40 -1 0 1 0 5
x1 x2 x3 x4 x5 b
IND2209. Prof.: Pamela Álvarez M. 9
SOLUCIONES DEGENERADAS
1 2
1 2
1
2
1 2
. 4 5 4054
, 0
Max x xs a x x
xxx x
Solución óptima
0 5 1 -4 0 201 0 0 1 0 50 1 0 0 1 40 -1 0 1 0 5
x1 x2 x3 x4 x5 b
0 0 1 -4 -5 01 0 0 1 0 50 1 0 0 1 40 0 0 1 1 9
x1 x2 x3 x4 x5 b
Existe solución degenerada el valor de una variable básica es igual a cero.
IND2209. Prof.: Pamela Álvarez M.
• Dado el problema:
• Vamos a ver las iteraciones de este ejemplo:
10
SOLUCIONES DEGENERADAS
1
0350190
21
0925160
41..
501150
43min
3
4321
4321
321
x
xxxx
xxxxas
xxx
IND2209. Prof.: Pamela Álvarez M. 11
SOLUCIONES DEGENERADAS
1
0350190
21
0925160
41..
501150
43min
3
4321
4321
321
x
xxxx
xxxxas
xxx
IND2209. Prof.: Pamela Álvarez M. 12
SOLUCIONES DEGENERADAS
• Y en esta iteración entra x6 y sale x4.• Nueva base: {5,6,7}
IND2209. Prof.: Pamela Álvarez M.
• Definición:
• Una solución degenerada es tal que hay variables básicas con valor cero
• ¿Cómo se forman soluciones degeneradas?
• Ocurre cuando se produce un “empate” en:
• Cuando eso ocurre, una variables básica quedará con valor = 0.
• También significa que el punto está sobredeterminado.
13
SOLUCIONES DEGENERADAS
0:min ijij
i aab
IND2209. Prof.: Pamela Álvarez M.
• Un punto puede estar sobredeterminado.....
• Pero eso no implica que haya restricciones redundantes.....
• ¿Qué pasa en el punto (0,0,1)?
14
SOLUCIONES DEGENERADAS
0,,11
321
32
31
xxxxxxx
IND2209. Prof.: Pamela Álvarez M.
• Es importante detectar que una solución es degenerada,
podríamos estar iterando eternamente.
• Un vértice degenerado puede ser óptimo o no.
15
SOLUCIONES DEGENERADAS
IND2209. Prof.: Pamela Álvarez M.
• Si tenemos el siguiente problema:
• Al llevarlo a su forma estándar tenemos inmediatamente una base
factible inicial
16
¿CÓMO ENCONTRAR UNA BASE FACTIBLE INICIAL?:
1 2
1 2
1 2
4 1002 60
500 1,2j
x xx xx x
x j
21 3min xxz
5,...,10500060002100004
521
421
321
jxxxx
xxxxxx
j
21 3min xxz
IND2209. Prof.: Pamela Álvarez M.
• Pero si tenemos:
• Aquí no se ve una “identidad” que genere solución factible en
forma evidente
17
¿CÓMO ENCONTRAR UNA BASE FACTIBLE INICIAL?:
0,,,6293..
22min
4321
421
321
21
xxxxxxx
xxxasxx
IND2209. Prof.: Pamela Álvarez M.
• Ordenándolo:
• Re‐escribiéndolo:
18
¿CÓMO ENCONTRAR UNA BASE FACTIBLE INICIAL?:
4,...,106293..
22min
421
321
21
jxxxx
xxxasxxz
j
4,...,106293..
22min
421
321
21
jxxxx
xxxasxxz
j
IND2209. Prof.: Pamela Álvarez M.
• Vamos a agregar “variables artificiales”:
• ¿Es el mismo problema original?
• ¿Realmente necesito la 2 variables artificiales?
19
¿CÓMO ENCONTRAR UNA BASE FACTIBLE INICIAL?:
2,1,04,...,1,0
6293..
22min
2421
1321
21
itjx
txxxtxxxas
xxz
i
j
IND2209. Prof.: Pamela Álvarez M.
• Cambiemos la función objetivo:
• Minimizar la suma de las variables artificiales
• (y olvidaremos momentáneamente la FO original)
• ¿Qué significa esta FO?
20
¿CÓMO ENCONTRAR UNA BASE FACTIBLE INICIAL?:
2,1,04,...,1,0
6293..
0000min
2421
1321
214321
itjx
txxxtxxxas
ttxxxxw
i
j
IND2209. Prof.: Pamela Álvarez M.
• Esto se conoce como problema de FASE I
• Y lo que ya habíamos visto como SIMPLEX es la FASE II
• En general:
• Se transforma en:
21
FASE I
. .0
TMin c xs a Ax b
x
1
. ., 0
m
ii
Min t
s a Ax t bx t
IND2209. Prof.: Pamela Álvarez M.
• Ejemplo 1:
22
FASE I
2,1,04,...,1,0
6293..
0000min
2421
1321
214321
itjx
txxxtxxxas
ttxxxxw
i
j1 3 1 0 1 0 9
2 1 0 ‐1 0 1 6
0 0 0 0 1 1 0
‐2 ‐2 0 0 0 0 0
x1 x2 x3 x4 t1 t2
1 3 1 0 1 0 9
2 1 0 ‐1 0 1 6
‐3 ‐4 ‐1 1 0 0 ‐15
‐2 ‐2 0 0 0 0 0
x1 x2 x3 x4 t1 t2
Tableau inicial
IND2209. Prof.: Pamela Álvarez M.
• Se aplica el Simplex como sabemos
23
FASE I
2,1,04,...,1,0
6293..
0000min
2421
1321
214321
itjx
txxxtxxxas
ttxxxxw
i
j
0 1 2/5 1/5 2/5 ‐1/5 12/5
1 0 ‐1/5 ‐3/5 ‐1/5 3/5 9/5
0 0 0 0 1 1 0
0 0 2/5 ‐4/5 1 1 42/5
x1 x2 x3 x4 t1 t2
Tableau final
Solución óptima Fase I
IND2209. Prof.: Pamela Álvarez M.
• Con esa base inicial optimizamos en Fase II:
• Eliminar las variables artificiales del problema
• El tableau de inicio de fase II es:
• Iterar…….
24
FASE II
0 1 2/5 1/5 12/5
1 0 ‐1/5 ‐3/5 9/5
0 0 2/5 ‐4/5 42/5
x1 x2 x3 x4
IND2209. Prof.: Pamela Álvarez M.
• Ejemplo 2:
• Dado el problema inicial:
• El problema Fase I es:
25
MÉTODO DE LAS DOS FASES
1 2
1 2
1 2
1 2
2 2. . 2 2 9
8, 0
Min x xs a x x
x xx x
1 2
1 2 3 1
1 2 4 2
. . 2 2 980, 1,.., 40, 1,2
j
i
Min w t ts a x x x t
x x x tx jt i
IND2209. Prof.: Pamela Álvarez M.
• Tableau final (Fase I):
• ¿Qué significa esto...?
26
MÉTODO DE LAS DOS FASES
1 1 1/2 0 1/2 0 3
‐1 0 ‐1 ‐1 ‐1 1 2
1 0 1 0 1 0 ‐2
x1 x2 x3 x4 t1 t2
IND2209. Prof.: Pamela Álvarez M.
• Ejemplo 3:
• Dado el problema inicial:
• El problema Fase I es:
27
MÉTODO DE LAS DOS FASES
1 2
1 2 3
1 2
1 2 3
. . 11
2 2 20, 1,.., 4j
Max z x xs a x x x
x xx x x
x j
1 2 3
1 2 3 1
1 2 2
1 2 3 3
. . 11
2 2 2, 0, 1,.., 4; 1,..,3j i
Min w t t ts a x x x t
x x tx x x t
x t j i
IND2209. Prof.: Pamela Álvarez M.
• Tableau final (Fase I):
• ¿Qué significa esto...?
28
MÉTODO DE LAS DOS FASES
1 1 0 1 0 0 1
0 0 1 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
x1 x2 x3 t1 t2 t3
IND2209. Prof.: Pamela Álvarez M.
• El algoritmo SIMPLEX se aplica de la siguiente forma:• Se reduce el problema a forma estándar• Si no hay una base factible inicial evidente, se formula el problema
de FASE I• Se resuelve el problema de FASE I
• El resultado de FASE I puede ser:• El problema es infactible• El problema es factible, tiene filas redundantes y se eliminan• El problema es factible y tengo una base inicial
• Si el problema es factible, se rescata la base factible inicial y se inicia la
FASE II:
• Se resuelve el problema hasta que:• Se llegue a una solución óptima• Se detecte que el problema es no acotado 29
MÉTODO DE LAS DOS FASES
IND2209. Prof.: Pamela Álvarez M.
• Consideración final:
30
MATRIZ/TABLEAU
top related