Simplex Investigacion Operativa
-
Upload
diego-salinas-flores -
Category
Documents
-
view
67 -
download
10
description
Transcript of Simplex Investigacion Operativa
-
Modelo PROTRAC
)(.................5
)(.................03
)(.............1351030
)(.............1601020
)(.............1501510:.
40005000
5
4
3
2
1
orDistribuidLFE
PolticaLFE
CalidadLFE
BLFE
ALFEas
FEZMax
-
16 14 10 8 4 2 6
12
2
E
16
14
12
10
8
6
4
F
(6.857, 2.286)
(4.05 , 1.35)
(4.5 , 7.0)
(0.9 , 9)
1.35
2.286
0.75
Solucin Optima:
E = 4.5; F = 7.0
1601020:2 FEL
1501510:1 FEL
1351030:3 FEL03:4 FEL
5:5 FEL
FEZMax 40005000
-
Caso Protrac (Enunciado extra)
7.-Que tanto conviene si aumentamos la disponibilidad de las horas del Departamento B .
-
16 14 10 8 4 2 6
12
2
E
16
14
12
10
8
6
4
F
(6.857, 2.286)
(4.05 , 1.35)
(4.5 , 7.0)
(0.9 , 9)
1.35
2.286
0.75
Solucin Optima:
E = ; F =
1601020:2 FEL
1501510:1 FEL
1351030:3 FEL03:4 FEL
5:5 FEL
FEZMax 40005000
Capacidad Dpto B= 161 Hrs
-
16 14 10 8 4 2 6
12
2
E
16
14
12
10
8
6
4
F
(6.857, 2.286)
(4.05 , 1.35)
(4.5 , 7.0)
(0.9 , 9)
1.35
2.286
0.75
Solucin Optima:
E = F =
1601020:2 FEL
1501510:1 FEL
1351030:3 FEL03:4 FEL
5:5 FEL
FEZMax 40005000
Capacidad Dpto A= 151 Hrs
-
16 14 10 8 4 2 6
12
2
E
16
14
12
10
8
6
4
F
(6.857, 2.286)
(4.05 , 1.35)
(4.5 , 7.0)
(0.9 , 9)
1.35
2.286
0.75
Solucin Optima:
E = 4.5; F = 7.0
1601020:2 FEL
1501510:1 FEL
1351030:3 FEL03:4 FEL
5:5 FEL
FEZMax 40005000
Capacidad Dpto Calidad 135 Hrs
-
16 14 10 8 4 2 6
12
2
E
16
14
12
10
8
6
4
F
(6.857, 2.286)
(4.05 , 1.35)
(4.5 , 7.0)
(0.9 , 9)
1.35
2.286
0.75
Solucin Optima:
E = F =
1601020:2 FEL
1501510:1 FEL
1351030:3 FEL03:4 FEL
5:5 FEL
40004000
5000
40005000
ZEF
FEZMax
-
Solucin Grfica
Solucin Factible
Regin Factible
Solucin ptima
Valor ptimo
Construccin de grficos: Graficar c/restriccin, Regin Factible
Fijar Z, Graficar F.O, Desplazar y encontrar
-
Solucin Grfica; Casos Especiales
Soluciones Alternativas
Solucin no acotada
Sin solucin
Si existe Sol. ptima, ella se encuentra en un punto esquina
Y en el plano como se ven estos casos ESPECIALES?
-
Solucin Grfica
0,
63
1.
26
21
21
21
21
xx
xx
xxas
xxzMax
0,
232
22.
65
21
21
21
21
xx
xx
xxas
xxzMax
0,
1243
22.
23
21
21
21
21
xx
xx
xxas
xxzMax
0,
5
10.
25
21
1
21
21
xx
x
xxas
xxzMax
Ejercicio n 1
Ejercicio n 2
Ejercicio n 3
Ejercicio n 4
Ejercicio n 5: Cambiar en Ejercicio n 3 Max Z por Min z
-
16 14 10 8 4 2 6
12
2
E
16
14
12
10
8
6
4
F
(6.857, 2.286)
(4.05 , 1.35)
(4.5 , 7.0)
(0.9 , 9)
1.35
2.286
0.75
Solucin Optima:
E = 4.5; F = 7.0
1601020:2 FEL
1501510:1 FEL
1351030:3 FEL03:4 FEL
5:5 FEL
FEZMax 40005000
-
4.- Representacin Estndar de un PPL (segn Mtodo de Solucin a Conocer)
F.O. es Max o Min
Restricciones como ecuaciones
Variables no negativas
Lado derecho, constantes no negativas
-
:.
...)( 2211
as
xcxcxczMinMax nn
Modelo Estndar de un PPL Desagregado (1)
,0,...,0,0
0,...,0,0
...
...
...
21
21
2211
22222121
11212111
m
n
mnmnmm
n
n
bbb
xxx
bxaxaxa
bxaxaxa
bxaxaxa
-
njmi
bx
bxaas
xczMinMax
ij
n
j
ijij
n
j
jj
,...1;,...1
0;0
:.
)(
1
1
Modelo Estndar de un PPL Desagregado (2)
-
Modelo Estndar de un PPL MATRICIAL
Estndar
0
0
b
x
bAx
Matrices:
:.
)(
as
cxzMinMax
n
mnmnm
n
ccc
b
b
b
x
x
x
aa
aa
A
....
..
...
...
...
1
11
1
111
A: Matriz de coeficientes Tecnolgicos
B: Vector de restricciones, vector lado derecho
c: Vector fila beneficios, costos o rendimientos
X: Vector de decisiones
SISTEMA DE ECUACIONES
-
Transformar a Forma Estndar
Lado derecho no negativo
Reducir Desigualdades
Variables negativas
Variables no restringidas en signo
Ejercitar los casos
-
Ejercicios Estandarizacin
0,0,
523
2
7.
32
321
321
321
321
321
xxx
xxx
xxx
xxxas
xxxzMax
0,0,0,
2232
143
224.
5243
4321
4321
4321
4321
4321
xxxx
xxxx
xxxx
xxxxas
xxxxzMax
Ejercicio n 1 Ejercicio n 2
0,0,
523
2
7.
,32
321
321
321
321
3221
xxx
xxx
xxx
xxxas
xxMinxxzMaxEjercicio n 3
Que pasa si en el N 3 cambiamos en la F.O a 3max{x2,x3}
-
5.- Resolviendo Sistemas de Ecuaciones Lineales
Sistema de Ecuaciones Cualquiera ESTANDAR
Sistema de Ecuaciones Equivalente
Cannico
Base, Solucin Bsica
Solucin Factible (Todas las Var >= 0)
Solucin Infactible (Algunas Var
-
Variables Bsicas
Una variable xi se dice bsica si le acompaa un factor +1 en una ecuacin y un cero en las dems.
Solucin Bsica y Factible: SB y factible (XB0)
Solucin Bsica:
Solucin obtenida de un sistema cannico, haciendo las variables NO bsicas cero.
En cada punto esquina encontramos una SB
!)!(
!
mmn
n
m
n
-
S1
Encontrar las combinaciones de VB que conforman
todas las SB: Factible, Infactible? Generar nuevo sistema cannico equivalente y concluir.
Nuevo sistema cannico equivalente: Operaciones Fila (Objetivo: Despejar Variables):
* una ecuacin. por un nmero + o - Sumar a una ec. Un mltiplo de otra ec.
Evaluar sus variables
43
2242
54321
54321
xxxxx
xxxxx
-
Objetivo: Despejar x1 y x2
S2
S3
S3: Sistema Cannico
Solucin Bsica: x1 y x2 son bsicas
232
2242
5432
54321
xxxx
xxxxx
232
6423
5432
5431
xxxx
xxxx
-
1. Comenzar con una solucin bsica inicial cannica
y factible. se podr mejorar?
2. Es factible, Mejorarla?
3. Determinar la siguiente
Cuando no es factible encontrar soluciones mejores, la bsqueda termina
6.- SIMPLEX
Principios del Mtodo Simplex
-
Ejemplo. Es factible mejorarla? Max Z = 5X1 + 2X2 + 3X3 - X4 + X5 Sujeto a: X1 + 2X2 + 2X3 + X4 = 8 ( 2.7 ) 3X1 + 4X2 + X3 + X5 = 7 ( 2.8 ) Solucin bsica X1 = X2 = X3 = 0, X4 = 8, X5 = 7. Z = 5*(0) + 2*(0) + 3*(0) - 1*(8) + 1*(7) = -1
Ve usted otras soluciones bsicas en este sistema equivalente, cuales?
-
Es factible mejorarla?
Debemos pensar en un cambio de base
conveniente
Calculemos un
Indicador para esto:
Ganancia/Beneficio Relativo
jc Ganancia Relativa de la Variable xj
-
a) Primero se examina si la presente es ptima.
b) Si no la es. El Simplex examina una: Solucin
bsica factible Adyacente con un mejor valor
de Z.
Mejorando la Solucin
Definicin. Una Solucin bsica factible Adyacente difiere de la solucin bsica factible actual, en solo una variable bsica.
-
Solucin bsica factible Adyacente
1. Definir una variable bsica como no bsica.
2. Definir una no bsica de reemplazo de la bsica
saliente.
Siempre y Cuando mejore el valor de Z.
Observe que:
1. Variables bsicas asumen valores positivos y las no
bsicas cero.
2. Una no bsica se convierte en bsica aumentando
su valor de cero a una cantidad positiva.
-
Beneficio Relativo: (Referido a una variable no bsica j).
Para la base actual, la optimalidad es chequeada calculando los beneficios relativos de todas las variables no bsica y en caso de no cumplirse; la nueva base se empieza a formar eligiendo aquella de mejor aporte.
Chequeo de optimalidad
j
jx
zc
Hacer estas operaciones calculando el indicador de optimalidad:
-
Resumen del Mtodo Simplex
Paso 1. Comenzar con una S. B. F. cannica
.
Paso 2. Optimalidad?
Paso 3 Seleccionar VNB que ingresa a la base
Paso 4 Determinar VB. Que abandona la base
Aplicar regla razn mnima
Paso 5 Generar nuevo sistema. Y volver a Paso 2.
-
Mtodo Simplex en Forma de Tableu
(4) (3)
(2) (1)
0
743
822
..
325
5321
4321
54321
jx
xxxx
xxxx
as
xxxxxzMax
(5)
-
Resumen de pasos. (Max z, Min z)
1. Expresar el problema en forma estndar.
2. Comenzar con una solucin factible bsica inicial en forma cannica y
plantear la Tabla inicial.
3. Usar producto interno para encontrar los beneficios relativos
4. Si todos los no aportan al objetivo la solucin actual es ptima. De otro
modo seleccionar la no bsica para que entre a la base.
5. Aplicar razn mnima para determinar la variable que deja la base.
6. Ejecutar operacin pivote para obtener la nueva tabla.
7. Calcular beneficios relativos. Retorne al paso 4.
jc
jc
-
Resolver por el mtodo Simplex el siguiente problema (Caso 1):
0;3
1423
42..
23
21
21
21
21
jxxx
xx
xxas
xxzMax
(1)
(3) (4)
(2)
-
0;;
40322
3033.
634
321
321
321
321
xxx
xxx
xxxas
xxxzMax
EJERCICIO
(Caso 2)
-
0;;
722
84
1053.
42
321
31
321
321
321
xxx
xx
xxx
xxxas
xxxzMax
EJERCICIO (Caso 3)
-
Max Z = -3X1 + X2 + X3 X1 - 2X2 + X3 = 3 2X1 - X3 = -1 Convertir a forma estndar. Max Z = -3X1 + X2 + X3 Sujeto a: X1 - 2X2 + X3 + X4 = 11 -4X1 + X2 + 2X3 - X5 = 3 -2X1 + X3 = 1 Xi >= 0 , i=1,5
7.- Uso de Variables Artificiales en el SIMPLEX
Cul es la Base XB?
-
Que Hacemos, No tenemos una Solucin Bsica, Inmediata?
Agregamos Dos V. Artificiales, Variables que no son parte del Problema, esto
no es un cambio en la forma si no un cambio en el fondo. El modelo que
resulta representa una realidad que no es nuestro problema
Este es un Modelo Artificial
X1 - 2X2 + X3 + X4 = 11 - 4X1 + X2 + 2X3 - X5 + X6 = 3 -2X1 + X3 + X7 = 1 Xi >= 0 , i=1,7 XB = (X4 , X6 , X7 ) X6 y X7 son V. Artificiales
Cual es la Funcin Objetivo que se usar?
Podemos inventarla?
Qu se persigue que nos oriente para inventarla?
-
Se asigna un valor M muy grande a cada coeficiente de V.a. presente en la funcin objetivo. -M si es maximizacin y M si es minimizacin. En el ejemplo anterior se asigna un valor M grande como costo a la variables X6 y X7. Luego Min W = -3X1 + X2 + X3 + MX6 + MX7
7.1.- Mtodo de la M grande.
X1 - 2X2 + X3 + X4 = 11 - 4X1 + X2 + 2X3 - X5 + X6 = 3 -2X1 + X3 + X7 = 1 Xi >= 0 , i=1,7
S.a
-
cj
Cte. CB XB X1 X2 X3 X4 X5 X6 X7 X
X
X
jc
cj
Cte. CB XB X1 X2 X3 X4 X5 X6 X7 X
X
X
jc
X1 - 2X2 + X3 + X4 = 11 - 4X1 + X2 + 2X3 - X5 + X6 = 3 -2X1 + X3 + X7 = 1 Xi >= 0 , i=1,7
Min Z = -3X1 + X2 + X3 + MX6 + MX7
-
cjCB XB X1 X2 X3 X4 X5 X6 X7 Cte.
X
X
X
jc
cjCB XB X1 X2 X3 X4 X5 X6 X7 Cte.
X
X
X
jc
-
Fase 1. Usando un modelo artificial, encontrar una solucin bsica inicial al problema original. Fase 2. La solucin bsica encontrada se optimiza con respecto a la funcin objetivo original. La Tabla final de la fase 1 es la Tabla inicial para la fase 2.
7.2.- El Mtodo de las Dos Fases.
X1 - 2X2 + X3 + X4 = 11 - 4X1 + X2 + 2X3 - X5 + X6 = 3 -2X1 + X3 + X7 = 1 Xi >= 0 , i=1,7
Min W = X6 + X7
S.a:
-
cj
Cte. CB XB X1 X2 X3 X4 X5 X6 X7 X
X
X
jc
cj
Cte. CB XB X1 X2 X3 X4 X5 X6 X7 X
X
X
jc
X1 - 2X2 + X3 + X4 = 11 - 4X1 + X2 + 2X3 - X5 + X6 = 3 -2X1 + X3 + X7 = 1 Xi >= 0 , i=1,7
Min W = X6 + X7
-
cjCB XB X1 X2 X3 X4 X5 X6 X7 Cte.
X
X
X
jc
cjCB XB X1 X2 X3 X4 X5 X6 X7 Cte.
X
X
X
jc