08_ind2209_alumno_15

7/23/2019 08_IND2209_Alumno_15

http://slidepdf.com/reader/full/08ind2209alumno15 1/30

Investigación

de

OperacionesIND2209

Profesor: Pamela Álvarez M.

Facultad de Ingeniería

Departamento de Ciencias de la Ingeniería

Unidad Nº 5

7/23/2019 08_IND2209_Alumno_15


• Unidad 5: Programación lineal entera y mixta (15%)

• Definiciones y Conceptos Fundamentales

• Modelación de Problemas Enteros y Mixtos

• Método de Ramificación y Acotamiento

2

Programación Lineal Entera y Mixta

IND2209. Prof.: Pamela Álvarez M.

7/23/2019 08_IND2209_Alumno_15


• Unidad 5: Programación lineal entera y mixta (15%)

• Definiciones y Conceptos Fundamentales

• Modelación de Problemas Enteros y Mixtos Ya lo vimos

• Método de Ramificación y Acotamiento

3



REPASAR

7/23/2019 08_IND2209_Alumno_15


• Ventajas de restringir variables a tomar valores enteros

• Más realista

• Desventajas

• Más difícil de modelar

• Puede se mucho más difícil de resolver

• Algunos problemas son fáciles Podemos resolver problemas con

millones de variables

• Algunos problemas son difíciles Incluso 100 variables puede ser un

gran desafío

• Se requiere de conocimientos y experiencia para poder identificarlos.

4



7/23/2019 08_IND2209_Alumno_15


• Nuestro problema original es:

• Opciones:

• Problema entero puro: Todas las variables son enteras

• Problema entero binario: Todas las variables deben tomar valores 0 ó 1

• Problema entero mixto: Algunas variables son enteras y otras soncontinuas

5



) s.a.

0 entero

T

min c xPE Ax b

x

7/23/2019 08_IND2209_Alumno_15


• ¿Cómo resolver un PE?

• Veamos los siguientes ejemplos:

• Resolver el problema sin considerar la restricción de integralidad

• Resolver el problema entero gráficamente

6



1 2

1 2

1 2

1 2

21 11

. . 7 4 13

, 0

, enteros

PE Max z x x

s a x x

x x

x x

1 2

1 2

1 2

1 2

1 2

4

. . 2 3 5

2 3 5

, 0

, enteros

PE Max z x x

s a x x

x x

x x

x x

1 2

1

2

1 2

1 2

4. . 5

3

, 0

, enteros

PE Max z x xs a x

x

x x

x x

7/23/2019 08_IND2209_Alumno_15


7



1 2

1 2

1 2

21 11

. . 7 4 13

, 0

P Max z x x

s a x x

x x

1,9

3,3

x1

x2

1,9

3,3

x1

x2

1 2

1 2

1 2

1 2

21 11

. . 7 4 13

, 0

, enteros

PE Max z x x

s a x x

x x

x x

7/23/2019 08_IND2209_Alumno_15


8



1 2

1 2

1 2

1 2

4

. . 2 3 5

2 3 5

, 0

P Max z x x

s a x x

x x

x x

1 2

1 2

1 2

1 2

1 2

4

. . 2 3 5

2 3 5

, 0

, enteros

PE Max z x x

s a x x

x x

x x

x x

2,5

0,6

x1

x2

2,5

0,6

x1

x2

7/23/2019 08_IND2209_Alumno_15


9



1 2

1

2

1 2

4

. . 5

3, 0

P Max z x x

s a x

x x x

1 2

1

2

1 2

1 2

4

. . 5

3, 0

, enteros

PE Max z x x

s a x

x x x

x x

5

3

x1

x2

5

3

x1

x2

7/23/2019 08_IND2209_Alumno_15


• ¿Conclusiones?

• Una primera idea intuitiva era resolver la relajación lineal y luego aproximar o redondear No sirve!!!!

• Entonces … ¿cómo resolver PE?

• Técnicas para resolver problemas enteros

• Técnicas de enumeración

1. Enumeración completa• Lista con todas las soluciones… elegir la mejor ¿Es posible hacer esto?

2. Branch & Bound

• Búsqueda implícita de todas las soluciones, pero eliminando

inteligentemente muchas de ellas antes de haberlas evaluado

• Técnicas de planos cortantes

• Usar programación lineal (PL) para resolver problemas enteros, agregando restricciones que eliminan las soluciones fraccionales (o

continuas) 10



7/23/2019 08_IND2209_Alumno_15


• Entonces … nos quedan 2 opciones:

1. Técnicas de enumeración Branch & Bound

2. Técnicas de planos cortantes

• En ambos casos usaremos el siguiente concepto:

Relajación lineal

11



min

. :0 entero

T PE z c x

s a Ax b x

min

. :0

T PR z c x

s a Ax b x

7/23/2019 08_IND2209_Alumno_15


• ¿Hay alguna relación entre el problema entero y el problema relajado?

12



. .

0,

T

E PE Min z c x

s a Ax b

x enteros

. .

0

T

RPR Min z c x

s a Ax b

x

* * E R z z

Entrega una cota

inferior para problemas de minimización

Pregunta:¿Cuál sería una cota superior?

7/23/2019 08_IND2209_Alumno_15


• Sea el problema entero:

• Y su relajación lineal

• Sea R0 = {x: Ax ≤b, x≥0} Región factible

• Sea x0 una solución óptima de PR, es decir, z0 = cTx0.

13

Branch and Bound


min

. :

0 entero

T PE z c x

s a Ax b

x

min

. : , 0

T PR z c x

s a Ax b x

7/23/2019 08_IND2209_Alumno_15


• ¿Qué pasa si x 0 es entero…?

• ¿Qué pasa si x 0 no es entero…?

• Existe al menos un índice k tal que x 0k es fraccionario.

• Idea Básica de B&B:

Dada una solución óptima fraccional x 0 del problema relajadoPR, dividir el problema relajado en dos sub‐problemas que NOcontengan esa dicha solución fraccional.

14

Branch and Bound


7/23/2019 08_IND2209_Alumno_15


15

Branch and Bound


x

y

x 0

Solución óptima problema relajado.

x

y

Creación de dos problemas independientes.

7/23/2019 08_IND2209_Alumno_15


• ¿Cómo se hace esta división de problemas?

• Generando dos regiones factibles independientes incorporando 2 restricciones:

• Luego resolver cada subproblema y seguir ……

16

Branch and Bound


0 0

0 0

: 1

:

k k

k k

R R x x x

R R x x x

7/23/2019 08_IND2209_Alumno_15


• La idea es repetir este proceso, obtener sucesivamentesubproblemas para regiones más y más acotadas.

• De esta forma se construye un “árbol”, donde cada nodo es un

subproblema que contiene las restricciones que se van incorporando.

• ¿Qué puede ocurrir?

• Alguna rama es un problema infactible, entonces se termina o se“poda” dicha rama.

• Alguna rama es un problema cuya solución es automáticamenteentera. Esto entrega una cota para el valor óptimo del problema.

• No es necesario seguir explorando dicho árbol.

17

Branch and Bound


7/23/2019 08_IND2209_Alumno_15


• Debemos ir guardando los valores óptimos de cada problema ya quenos sirven como cotas.

• DEFINICION: El valor de la MEJOR solución entera disponible en cadaiteración se llama INCUMBENTE.

Algoritmo de Ramificación y Acotamiento

(Branch and Bound ‐ B&B)

• Si el problema original es de tipo BINARIO, entonces algunas cosas sesimplifican un poco…

18

Branch and Bound


7/23/2019 08_IND2209_Alumno_15


1. Inicialización:

• Establecer cota superior (∞) e inferior (‐∞)

• Resolver el PR

• Casos posibles

• Actualizar cota inferior o superior (según si el problema es deminimizar o de maximizar)

2. Ramificación:

• Variable x k no entera (y debiera serlo)

• Si x k =a,b se generan 2 subproblemas a los que se le agregan las

siguientes restricciones respectivamente:

• x k ≤ a

• x k ≥ a + 1

19

Branch and Bound - Algoritmo


7/23/2019 08_IND2209_Alumno_15


3. Solución subproblema correspondiente.

4. Actualización de cotas:

• Casos posibles

5. Poda:

• Criterios:• Por integralidad

• Por cotas

• Por infactibilidad

6. Optimalidad:

• ¿Quedan subproblemas por resolver?

20



7/23/2019 08_IND2209_Alumno_15


21

Branch and Bound – Ejemplo 1


enteros y x

y

y xas

y x Max

,0,

8,2

4..

2

1) 2

. 4

2,8

, 0

P Max x y

s a x y

y

x y

x

y

• La solución óptima del problema

relajado lineal es x=1,2; y=2,8

• El valor de la función objetivo en este

caso es 6,8

• Claramente la solución no es entera

• Para encontrar una solución entera, se

procede a “aislar” la solución obtenida

7/23/2019 08_IND2209_Alumno_15


22



1) 2

. 4

2,8

, 0

P Max x y

s a x y

y

x y

2) 2

. 4

2,8

1

, 0

P Max x y

s a x y

y

x

x y

3) 2

. 4

2,8

2

, 0

P Max x y

s a x y

y

x

x y

• La solución óptima del problema relajado lineal es x=1,2; y=2,8

• Se escoge una de las variables fraccionarias para crear los 2 subproblemas.

7/23/2019 08_IND2209_Alumno_15


23



x

y

2) 2

. 4

2,8

1

, 0

P Max x y

s a x y

y

x

x y

3) 2

. 4

2,8

2

, 0

P Max x y

s a x y

y

x

x y

P2)P3)

7/23/2019 08_IND2209_Alumno_15


24



• La solución óptima del P2 es x=1, y=2,8.

el valor de la función objetivo es 6,6

• ¿Cómo varió la función objetivo

respecto a P1? ¿Por qué?

2) 2. 4

2,8

1

, 0

P Max x ys a x y

y

x

x y

x

y

7/23/2019 08_IND2209_Alumno_15


25



• La solución óptima del P3 es x=2, y=2 el

valor de la función objetivo es 6

• ¿Cómo varió la función objetivo

respecto a P1? ¿Por qué?

• ¿Hasta cuándo se debe acotar?

3) 2. 4

2,8

2

, 0

P Max x ys a x y

y

x

x y

x

y

7/23/2019 08_IND2209_Alumno_15


26



x=1,2

y=2,8

F.O.:6,8

x=1

y=2,8

F.O.:6,6

x =2y=2

F.O.:6

x<=1 x>=2

x=1

y=2

F.O.:5

Infactible

y<=2 y>=3

ÓPTIMO

7/23/2019 08_IND2209_Alumno_15


27



• Y se sigue así…… formando un árbol:

• Veamos las cotas e incumbente

x=1,2

y=2,8

F.O.:6,8

x=1y=2,8

F.O.:6,6

x =2y=2

F.O.:6

x<=1 x>=2

x=1y=2

F.O.:5

Infactible

y<=2 y>=3

¿Cotas?¿Es incumbente o no?¿Se poda?




¿Cotas?¿Es incumbente o no?

¿Se poda?

7/23/2019 08_IND2209_Alumno_15


28



) 7 9

. 8

6 11 66, 0

, enteros

P Max x y

s a x y

x y x y

x y

7/23/2019 08_IND2209_Alumno_15


29Prof.: Pamela Álvarez M.

• Ejemplo2:

• El problema analizado quedaría de la siguiente forma:

• Por lo tanto, la solución óptima al problema será: (x,y)=(5,3)

• El valor óptimo es 62

x=4,4

y=3,6

F.O.:63,2

x=4

y=3,8F.O.:62,4

x=5

y=3F.O.:62

x<=4 x>=5

y<=3 y>=4

x=4

y=3F.O.:55

x=3,7

y=4F.O.:61,7


7/23/2019 08_IND2209_Alumno_15


30Prof.: Pamela Álvarez M.

• ¿Por qué dijimos que si las variables son binarias el método de resolución

se simplifica?

• ¿Y si el problema es mixto?

, 0,1 x y

0

0,1

x

y enteros

z


08_ind2209_alumno_15

Documents