Solucion de Problemas PLE

Solucin grfica
Por tipo de variables:

Enteros puros: son aquellos en que todas las
variables nicamente pueden tomar valores
enteros.
Mixtos: son aquellos en los que hay al mismo

tiempo variables continuas y variables que slo
pueden tomar valores enteros.
Binarios: las variables slo pueden tomar los

valores cero o uno.
VARIA SOLUCIONES
BLES
Cuando el conjunto de 1 2
soluciones est 2 4
4 16
acotado, es finito. Los
5 32
nmeros finitos suelen
10 1.024
ser grandes. 15 32.768
(en un problema 20 1.048.576
binario con n 25 33.554.432
variables el nmero 50 1,1259E+15
de soluciones 100 1,2677E+30
factibles a verificar 200 1,6069E+60

500 3,2734E+150
es 2 )
1000 1,0715E+301
1,000,000,000,000: 1E+12
1 SEGUNDO 1 1E+12
1 MINUTO 60 6E+13
1 HORA 60 3,6E+15
1 DA 24 8,64E+16
1 MES 30 2,592E+18
1 AO 12 3,1104E+19
1 SIGLO 100 3,1104E+21
100 SIGLOS 100 3,1104E+23
1000 SIGLOS 10 3,1104E+24
MILLON DE SIGLOS 1000 3,1104E+27
100 MILLONES SIGLOS 100 3,1104E+29 1,2675E+30
1000 MILLONES SIGLOS 10 3,1104E+30
Problema con 100 variables requiere 1,2677E+30 ,

o sea, 408 Millones de siglos
Con el redondeo no se garantizan la
factibilidad y optimalidad de la solucin
GLP\GLP.EXE
Ejemplo violacin de la factibilidad

glp1_noredondeo.glp
Ejemplo violacin de la optimalidad

glp2_noredondeo.glp
Mtodo de ramificacin y acotamiento
(Branch and Bound)
Mtodo de plano cortante
(algoritmo fraccional de Gomory)
Mtodo de enumeracin explicita
Mtodos heuristicos
Observaremos utilizando el mtodo grfico la
solucin del modelo siguiente:
Z 5 X 1 4 X 2 max
X1 X 2 5
10 X 1 6 X 2 45
X 1 , X 2 0, enteros
9
6 Payoff: 5.0 X1 + 4.0 X2 = 23.7

Valor de X1=3,8 est entre 3 y 4.
Para excluir todos valores
5
fraccionarios ms cercanos se
4
debe excluir todos los valores
3X14 de la solucin del
3
problema.
Para esto se plantean las
2 restricciones adicionales: X14 y
X13. Se obtienen dos
1 problemas separados
: 10.0 X1 + 6.0 X2 = 45.0
0 : 1.0 X1 + 1.0 X2 = 5.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Optimal Decisions(X1,X2): ( 3.8, 1.3)

: 1.0X1 + 1.0X2 <= 5.0
: 10.0X1 + 6.0X2 <= 45.0
8
6
Payoff: 5.0 X1 + 4.0 X2 = 23.0
: 1.0 X1 + 0.0 X2 = 3.0
: 10.0 X1 + 6.0 X2 = 45.0
0 : 1.0 X1 + 1.0 X2 = 5.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

: 1.0X1 + 1.0X2 <= 5.0
: 10.0X1 + 6.0X2 <= 45.0
: 1.0X1 + 0.0X2 <= 3.0

9
6
Payoff: 5.0 X1 + 4.0 X2 = 23.3
1 : 1.0 X1 + 0.0 X2 = 4.0
: 10.0 X1 + 6.0 X2 = 45.0
0 : 1.0 X1 + 1.0 X2 = 5.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

: 1.0X1 + 1.0X2 <= 5.0
: 10.0X1 + 6.0X2 <= 45.0
: 1.0X1 + 0.0X2 >= 4.0
10
6
Payoff: 5.0 X1 + 4.0 X2 = 22.5
: 0.0 X1 + 1.0 X2 = 0.0
1 : 1.0 X1 + 0.0 X2 = 4.0
: 10.0 X1 + 6.0 X2 = 45.0
0 : 1.0 X1 + 1.0 X2 = 5.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

: 1.0X1 + 1.0X2 <= 5.0
: 10.0X1 + 6.0X2 <= 45.0
: 1.0X1 + 0.0X2 >= 4.0
: 0.0X1 + 1.0X2 <= 0.0
10
6
Payoff: 5.0 X1 + 4.0 X2 = 23.3
NO EXISTE EL ESPACIO DE
5
SOLUCIONES FACTIBLES !!!
: 0.0 X1 + 1.0 X2 = 1.0
1 : 1.0 X1 + 0.0 X2 = 4.0
: 10.0 X1 + 6.0 X2 = 45.0
0 : 1.0 X1 + 1.0 X2 = 5.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
: 1.0X1 + 1.0X2 <= 5.0

: 10.0X1 + 6.0X2 <= 45.0
: 1.0X1 + 0.0X2 >= 4.0
: 0.0X1 + 1.0X2 >= 1.0
Paso inicial: se establece
Z*= - (max)
[Z*= + (min)].
Se aplica el paso de acotamiento, el paso
de sondeo y la prueba de optimalidad que
se describen despus al problema inicial.
Si no queda sondeado, se clasifica este
problema como el nico subproblema
restante para realizar la primera iteracin
completa.
Ramificacin: entre los subproblema restantes (no
sondeados), se selecciona el de ms reciente creacin. (Los
empates se rompen con la mejor cota). Entre las variables
restringidas a enteros, que tienen valores no enteros en la
solucin ptima de la soltura de PL del subproblema, se elige
la primera en el orden natural, como la variable de
ramificacin. Sea Xj esta variable y Xj* su valor en esta
solucin. Se ramifica desde el nodo del subproblema para
crear dos nuevos subproblemas agregando las restricciones
respectivas Xj<= [Xj*] y Xj >=[Xj*]+1.
Acotamiento: Para cada subproblema se obtiene su cota
aplicando el mtodo simplex (o el mtodo simplex dual si se
reoptimiza) a su soltura de PL y utilizando el valor de Z para
la solucin ptima resultante.
Sondeo : para cada nuevo subproblema se aplican las
pruebas de sondeo que se dan en seguida y se descartan
aquellos subproblemas que quedan sondeados por cualquiera
de las pruebas.
Prueba 1: su cota <=Z*(max) [ >=Z*(min) ],
donde Z* es el valor de Z en la solucin de
apoyo actual.
Prueba2: su soltura de PL no tiene soluciones
factibles.
Prueba 3: la solucin ptima para su soltura
de PL tiene valores enteros para todas sus
variables restringidas a enteros. (Si esta
solucin es mejor que la de apoyo, se
convierte en la nueva solucin de apoyo y se
vuelve a aplicar la prueba 1 con la nueva Z* a
todos los subproblemas no sondeados.)
El proceso se detiene cuando no hay
subproblemas restantes. Observacin final del rbol
de solucin del problema puede identificar los casos
siguientes:
la solucin correspondiente a la de apoyo actual
es nica y es ptima.
si hay varias soluciones con el valor de Z
correspondientes a la de apoyo actual, se
seleccionan todas estas soluciones identificando el
caso de ptimas alternativas.
si el valor de referencia de Z* no se ha cambiado
desde el paso inicial, se concluye que el problema
no tiene soluciones factibles con enteros
De otra manera, se realiza otra iteracin.

Z 5 X 1 4 X 2 max
X1 X 2 5 Z*=- (cota inferior)
10 X 1 6 X 2 45
X 1 , X 2 0, enteros
SP0
X1=
X2=
Z=

Solucion de Problemas PLE

Cargado por

Copyright:

Formatos disponibles

Solucion de Problemas PLE

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Solucion de Problemas PLE

Cargado por

Copyright:

Formatos disponibles

Solucin grfica

Por tipo de variables:

Mixtos: son aquellos en los que hay al mismo

Binarios: las variables slo pueden tomar los

factibles a verificar 200 1,6069E+60

Problema con 100 variables requiere 1,2677E+30 ,

Ejemplo violacin de la factibilidad

Ejemplo violacin de la optimalidad

6 Payoff: 5.0 X1 + 4.0 X2 = 23.7

0 : 1.0 X1 + 1.0 X2 = 5.0

Optimal Decisions(X1,X2): ( 3.8, 1.3)

: 1.0 X1 + 0.0 X2 = 3.0

: 10.0 X1 + 6.0 X2 = 45.0

0 : 1.0 X1 + 1.0 X2 = 5.0

Optimal Decisions(X1,X2): ( 3.0, 2.0)

: 1.0X1 + 0.0X2 <= 3.0

1 : 1.0 X1 + 0.0 X2 = 4.0

: 10.0 X1 + 6.0 X2 = 45.0

0 : 1.0 X1 + 1.0 X2 = 5.0

Optimal Decisions(X1,X2): ( 4.0, 0.8)

: 0.0 X1 + 1.0 X2 = 0.0

1 : 1.0 X1 + 0.0 X2 = 4.0

: 10.0 X1 + 6.0 X2 = 45.0

0 : 1.0 X1 + 1.0 X2 = 5.0

Optimal Decisions(X1,X2): ( 4.5, 0.0)

: 0.0 X1 + 1.0 X2 = 1.0

1 : 1.0 X1 + 0.0 X2 = 4.0

: 10.0 X1 + 6.0 X2 = 45.0

0 : 1.0 X1 + 1.0 X2 = 5.0

: 1.0X1 + 1.0X2 <= 5.0

De otra manera, se realiza otra iteracin.

También podría gustarte