Programaci´ on Lineal Entera Los modelos de programaci´ on entera son una extensi´ on de los modelos lineales en los que algunas variables toman valores enteros. Con frecuencia las variables enteras s´ olo toman valores en 0-1, ya que este tipo de variables permiten representar condiciones l´ ogicas. Este tipo de modelos permite representar sistemas mucho m´ as complejos. on de los mismos se complica excesivamente. No se A cambio, la resoluci´ puede utilizar la suavidad de las funciones para inferir el comportamiento de las mismas cerca del ´ optimo. Problemas con unas solas decenas de variables pueden ser casi imposibles de resolver.

1

Programaci´ on Entera: contenidos

1. Introducci´ on 2. Algunos modelos b´ asicos y Modelizaci´ on con variables binarias a) El problema del transporte b) Problema de la mochila c) Problema del viajante (opt. combinatoria) d) Problema de asignaci´ on, asignaci´ on generalizada y asignaci´ on cuadr´ atica e) Problema del cubrimiento, empaquetado y partici´ on f ) Problema del emparejamiento (opt. combinatoria) g) Otros problemas 3. Resoluci´ on del problema. a) Planos de corte b) Ramificaci´ on y acotaci´ on (Branch and Bound).

2

Programaci´ on Entera: ejemplos m´ın ctx Ax ≤ b x≥0 xi entera para i ∈ I ⊆ {1, . . . , n}

X Si I = {1, . . . , n} ⇒ Programaci´ on Lineal Entera Pura. X Si I 6= {1, . . . , n} ⇒ Programaci´ on Lineal Entera Mixta. X Si xi ∈ {0, 1}, ∀ i ∈ I ⇒ Programaci´ on Binaria o 0–1.

3

Programaci´ on Entera: ejemplos En general, un problema de Programaci´ on Lineal Entera puede surgir por varios motivos:

Directos: las variables que se utilizan son cuantitativas y enteras. Codificados: Se utilizan variables enteras para representar el cumplimiento o no de ciertas condiciones (normalmente son variables 0 − 1). Transformados: Las variables enteras aparecen para facilitar la modelizaci´ on de algunas condiciones (implicaciones, disyunciones, etc.)

4

Problemas directos: ejemplo Una empresa de autom´ oviles dispone de tres factor´ıas, A, B y C y de dos centros de distribuci´ on, D1 y D2. Las capacidades de producci´ on de las 3 factor´ıas durante un a˜ no son 1000, 1500 y 1200 veh´ıculos, respectivamente. Las demandas en los centros de producci´ on son de 2300 y 1400 veh´ıculos respectivamente. El coste de transporte en tren es de 10 pesetas por kil´ ometro y veh´ıculo. Si la matriz de distancias entre las factor´ıas y los centros de distribuci´ on vienen dada por la siguiente tabla, ¿cu´ antos veh´ıculos deben fabricarse en cada factor´ıa para que el transporte desde cada una de las factor´ıas a cada uno de los centros de distribuci´ on sea m´ınimo?

A B C

D1 1000 1250 1275

D2 2690 1350 850 5

Problemas directos: ejemplo Modelo: problema del transporte en el que la mercanc´ıa que debe ser transportada es un bien indivisible

minimizar

3 X 2 X

(10dij )xij

i=1 j=1

sujeto a x11 + x12 ≤ 1000 x21 + x22 ≤ 1500 x31 + x32 ≤ 1200 x11 + x21 + x31 ≥ 2300 x12 + x22 + x32 ≥ 1400 xij ∈ Z+, i = 1, 2, j = 1, 2, 3 donde xij =

cantidad de veh´ıculos a transportar de la factor´ıa i, i = 1, 2 hasta el centro de distribuci´ on j, j = 1, 2, 3 6

Problemas codificados: ejemplo Un ingeniero inform´ atico aut´ onomo quiere optar a realizar un proyecto inform´ atico de entre 5 que salen a concurso. S´ olo tiene presupuesto para pagar las tasas de solicitud en 3 proyectos. ¿A qu´ e 3 proyectos optar? Beneficio esperado (en miles de euros) que puede obtener a los 3 a˜ nos con cada uno de los proyectos. Estimaci´ on de la probabilidad de que no le concedan cada uno de los proyectos Proyecto Beneficio (miles euros) Probabilidad de rechazo

1 90 0.4

2 150 0.7

3 80 0.4

4 100 0.5

5 120 0.6

Problema: qu´ e proyectos deber´ıa solicitar para obtener un beneficio mayor y asegurarse de que la suma de las probabilidades de rechazo no sea superior a 1.5 7

Problemas codificados: ejemplo (cont.)

Variables de decisi´ on: xi =

 1, 0,

si se solicita el proyecto i, si no se soliciota el proyecto i.

i = 1, 2, 3, 4, 5

Restricciones:

• L´ımite presupuestario: x1 + x2 + x3 + x4 + x5 ≤ 3

• Suma de las probabilidades de rechazo no exceda 1.5 0,4x1 + 0,7x2 + 0,4x3 + 0,5x4 + 0,6x5 ≤ 1,5

• Condici´ on de variables binarias: xi ∈ {0, 1}, i = 1, 2, 3, 4, 5

8

Problemas codificados: ejemplo (cont.)

Objetivo: maximizar el beneficio esperado 90x1 + 150x2 + 80x3 + 100x4 + 120x5 ¿C´ omo cambiar´ıas el modelo anterior si se hubiera pedido que la probabilidad de no obtener ning´ un proyecto fuese, a lo sumo, del 10 %? Si seleccionamos, por ejemplo, los proyectos 1, 2 y 3: P {no obtener ning´ un proyecto} = P {rechazan P1 y P2 y P3 } = (0,4)(0,7)(0,4) =⇒ P {no obtener ning´ un proyecto} ≤ 0,1 ⇐⇒ (0,4)(0,7)(0,4) ≤ 0,1 ⇐⇒ log((0,4)(0,7)(0,4)) ≤ log(0,1) ⇐⇒ log(0,4) + log(0,7) + log(0,4) ≤ log(0,1)

− log(0,4)x1 − log(0,7)x2 − log(0,4)x3 − log(0,5)x4 − log(0,6)x5 ≥ 1

9

Problema de la Mochila Se dispone de n objetos para llenar una mochila. El objeto j tiene un peso pj y tiene una utilidad (valor) cj . La mochila admite un peso m´ aximo de b. El problema consiste en decidir qu´ e objetos se introducen en la mochila de forma que se maximice la utilidad de los objetos seleccionados.

Variables: xj =

 1

0



si el objeto j es seleccionado, en otro caso.

∀j = 1, . . . , n

10

Problema de la Mochila

Restricciones:

• L´ımite de peso de la mochila:

n X

pj xj ≤ b

j=1

• Condici´ on de variables binarias: xj ∈ {0, 1} Funci´ on objetivo: m´ ax

n X

∀j = 1, . . . , n

cj xj

j=1

Se pueden considerar variantes en las que se incluya tambi´ en el volumen, etc. O la posibilidad de que haya m´ as de una unidad de cada objeto. Entonces, las variables ser´ıan xj igual al n´ umero de unidades del objeto j seleccionadas.

11

Problema de asignaci´ on El modelo de asignaci´ on permite asignar eficientemente un conjunto de personas a un conjunto de trabajos, m´ aquinas a tareas, coches de polic´ıa a sectores de una ciudad, vendedores a zonas, etc. El objetivo es minimizar los costes, tiempos de desplazamiento, o maximizar la efectividad. Es un modelo muy frecuente como submodelo en otros m´ as complejos.

12

Problema de asignaci´ on. Ejemplo Juan es el jefe de un bufete de j´ ovenes abogados y est´ a interesado en la utilizaci´ on m´ as efectiva de sus recursos de personal buscando la forma de hacer las mejores asignaciones de abogado-cliente. El 1 de Marzo le llegan 4 nuevos clientes. Revisando a su personal encuentra que 4 abogados: Ana, Bruno, Carmen y Domingo. Todos pueden ser asignados a los casos. Cada uno de ellos s´ olo se puede hacer cargo de un caso.

13

Problema de asignaci´ on. Ejemplo (cont.) Para decidir la mejor asignaci´ on Juan tiene en cuenta una tasa de efectividad (de 1 a 9) construida sobre actuaciones anteriores de dichos abogados, ya que no todos son igual de buenos (especialistas) en todo tipo de procesos:

Abogado ana (1) bruno (2) carmen (3) domingo (4)

tasa de efectividad seg´ un caso de cliente divorcio (1) fusi´ on desfalco (3) herencias (4) empresarial (2) 6 2 8 5 9 3 5 8 4 8 3 4 6 7 6 4

14

Problema de asignaci´ on. Ejemplo (cont.) Para determinar la asignaci´ on m´ as efectiva Juan debe resolver el siguiente problema de asignaci´ on m´ ax 6x11 + 2x12 + 8x13 + 5x14 + 9x21 + 3x22 + 5x33 + 8x44+ 4x31 + 8x32 + 3x33 + 4x34 + 6x41 + 7x42 + 6x43 + 4x44 s.a. 4 X

i=1 4 X

xij = 1,

∀ j = 1, . . . , 4,

xij = 1,

∀ i = 1, . . . , 4,

j=1

xij ∈ {0, 1},

∀ i = 1, . . . , 4, ∀j = 1, . . . , 4.

donde las variables xij , i = 1, . . . , 4, j = 1, . . . , 4, se definen como xij =

 1, 0,

si el abogado i lleva el caso del cliente j, en otro caso. 15

Problema de Asignaci´ on Generalizada. Ejemplo Es una generalizaci´ on del modelo anterior. Cada abogado puede hacerse cargo de m´ as de un cliente simult´ aneamente, siempre y cuando no supere su capacidad Un sistema de procesamiento compartido tiene 3 ordenadores diferentes (Oj , j = 1, 2, 3) y tiene que procesar 6 tareas (Ti i = 1, . . . , 6) Todas las tareas se pueden realizar en cualquier ordenador, pero no pueden fraccionarse (se deben completar en el ordenador en que se inician) Los tiempos de procesamiento de cada tarea i en cada ordenador j, tij , var´ıa seg´ un el ordenador El tiempo disponible de cada ordenador para ejecutar las tareas est´ a limitado

16

Problema de Asignaci´ on Generalizada. Ejemplo (cont.)

Tarea T1 T2 T3 T4 T5 T6 T. disp. (Cj )

Ordenador O1 O2 O3 18 16 12 14 21 19 23 27 33 16 24 23 17 24 24 25 28 30 47 41 46

¿A qu´ e ordenador debemos mandar cada tarea si queremos minimizar el tiempo total de procesamiento? Variables xij =

 1, 0,

si la tarea i se asigna al ordenador j, , en otro caso.

i = 1, . . . , 6, j = 1, 2, 3. 17

Problema de Asignaci´ on Generalizada. Ejemplo (cont.) Funci´ on objetivo T = 18x11 + 16x12 + 12x13 + 14x21 + 21x22 + 19x23+ + 23x31 + 27x32 + 33x33 + 16x41 + 24x42 + 23x43+ + 17x51 + 24x52 + 24x53 + 25x61 + 28x62 + 30x63 Restricciones olo ordenador: X Cada tarea se procesa en un s´ 3 X

xij = 1,

i = 1, . . . , 6.

j=1

X Limitaci´ on de tiempo disponible en cada ordenador: 18x11 + 14x21 + 23x31 + 16x41 + 17x51 + 25x61 ≤ 47 16x12 + 21x22 + 27x32 + 24x42 + 24x52 + 28x62 ≤ 41 12x13 + 19x23 + 33x33 + 23x43 + 24x53 + 30x63 ≤ 46 18

Problema de Asignaci´ on Generalizada. Ejemplo (cont.)

T = m´ın

6 X 3 X

tij xij

i=1 j=1 3 X

xij = 1,

6 X

tij xij ≤ Cj ,

i = 1, . . . , 6

j=1

j = 1, 2, 3

i=1

xij ∈ {0, 1} ¿C´ omo cambiar´ıas el modelo para que el tiempo de procesamiento total fuese el tiempo que tardan en completarse todas las tareas que se procesan en paralelo en los 3 ordenadores?

19

Problema de Asignaci´ on Generalizada. Ejemplo (cont.) Funci´ on objetivo n

T = m´ ax 18x11 + 14x21 + 23x31 + 16x41 + 17x51 + 25x61, 16x12 + 21x22 + 27x32 + 24x42 + 24x52 + 28x62, 12x13 + 19x23 + 33x33 + 23x43 + 24x53 + 30x63

T = m´ın m´ ax

 6 X

6 X

6 X

o

 

ti1xi1, ti2xi2, ti3xi3 ,   i=1 i=1 i=1

3 X

xij = 1,

6 X

tij xij ≤ Cj ,

i = 1, . . . , 6

j=1

j = 1, 2, 3

i=1

xij ∈ {0, 1} 20

Problema de Asignaci´ on Generalizada. Ejemplo (cont.)

T = m´ın z 6 X

ti1xi1 ≤ z

6 X

ti2xi2 ≤ z

6 X

ti3xi3 ≤ z

3 X

xij = 1,

6 X

tij xij ≤ Cj ,

i=1

i=1

i=1

i = 1, . . . , 6

j=1

j = 1, 2, 3

i=1

xij ∈ {0, 1} 21

Problema de Cubrimiento. Ejemplo Un t´ ecnico de sistemas del laboratorio de c´ alculo de la Escuela Polit´ ecnica Superior quiere acceder a cinco archivos distintos. Hay copia de estos archivos en distintas cintas de backup:

f1 f2 f3 f4 f5

C1, C1, C2, C3, C1,

CINTAS C2, C5, C6, C8, C9, C10 C3 C5, C7, C10 C6, C8 C2, C4, C6, C7, C9, C10

Los tama˜ nos de las cintas de backup C1, . . . ,C10 son: (30, 50, 10, 20, 10, 40, 30, 10, 20, 20) Para poder recuperar los archivos, primero hay que hacer un volcado de ´ ste tiene que ser de la cinta completa, no puede las cintas al disco duro. E copiarse s´ olo una parte. ¿C´ omo determinar el conjunto de cintas a volcar de forma que se ocupe el menor espacio de disco posible y se puedan recuperar todos los archivos? 26

Problema de Cubrimiento. Ejemplo (cont.) Variables xi =

 1 0

si volcamos la cinta i al disco duro, si no la volcamos.

∀i = 1, . . . , 10.

Restricciones El archivo 1 tiene que ser accesible ⇒ al menos 1 de las cintas de backup que tiene copia del archivo 1 se debe volcar: x1 + x2 + x5 + x6 + x8 + x9 + x10 ≥ 1 El resto de archivos debe ser tambi´ en accesible: x1 + x3 > 1 x2 + x5 + x7 + x10 > 1 x3 + x6 + x8 > 1 x1 + x2 + x4 + x6 + x7 + x9 + x10 > 1 Condici´ on de variables binarias: xij ∈ {0, 1}, ∀i = 1, . . . , n. 27

Implicaciones entre variables binarias ¿C´ omo le a˜ nadir´ıas al modelo las siguientes condiciones?

X Si se vuelca la cinta 4, debe volcarse la 6: x4 ≤ x6

X Si no se vuelca la cinta 3, debe volcarse la 1: x3 + x1 ≥ 1

(⇔ 1 − x3 ≤ x1)

X Si se vuelca la cinta 2, no se puede volcar la cinta 6: x2 + x6 ≤ 1

(⇔ x6 ≤ 1 − x2)

X No se pueden volcar a la vez las cintas 1, 9 y 10: x1 + x9 + x10 ≤ 2

29

Implicaciones entre variables binarias (cont.)

X Si se vuelca la cinta 2 o la 5, no pueden volcarse ni la 6, ni la 9. Existen varias alternativas: Si se vuelca la cinta 2, no se puede volcar la cinta 6, y si se vuelca la cinta 5 tampoco: x2 + x6 6 1

x5 + x6 6 1

Lo mismo para la cintas 9: x2 + x9 6 1

x5 + x9 6 1

Otra posibilidad es modelar esta condici´ on como: x6 + x9 6 2 − 2x2

x6 + x9 6 2 − 2x5

30

Implicaciones entre variables binarias En general, cuando un valor concreto de una variable binaria condiciona el valor que han de tomar otras variables binarias.

X La condici´ on (y = 0 ⇒ x = 0), es equivalente a x ≤ y. Si no se vuelca la cinta y, entonces tampoco se puede volcar la cinta x.

X La condici´ on (y = 0 ⇒ x = 1), es equivalente a x ≥ 1 − y. Si no se vuelca la cinta y, entonces se debe volcar la cinta x.

X La condici´ on (y = 1 ⇒ x = 0), es equivalente a x ≤ 1 − y. Si se vuelca la cinta y, entonces no se puede volcar la cinta x.

X La condici´ on (y = 1 ⇒ x = 1), es equivalente a x ≥ y. Si se vuelca la cinta y, entonces tambi´ en hay que volcar la cinta x.

31

Coste fijo. Ejemplo ´ vende ordenadores y debe hacer una planificaci´ La empresa PECE on de la producci´ on durante la pr´ oxima semana. La compa˜ n´ıa produce 3 tipos de ordenadores: de mesa (A), port´ atil normal (B) y port´ atil de lujo (C) Todos los ordenadores que se montan en una semana, se venden en esa semana. El beneficio neto por la venta de uno de estos ordenadores es 350, 470 y 610 euros, respectivamente Los ordenadores A y B pasan un control de calidad y la empresa dispone de 120 h. para realizar estos controles. Los ordenadores de tipo C pasan otro control distinto y la empresa dispone de 48 h. a la semana para realizarlos. Cada control requiere 1 h. El resto de operaciones de montaje requieren 10, 15 y 20 h. para los ordenadores de tipo A, B y C, respectivamente. La empresa dispone de una capacidad de 2000 horas/semana ¿Cu´ anto debe producir de cada ordenador para maximizar el beneficio? Ejemplo tomado de Modelling the Supply Chain (Shapiro) 32

Coste fijo. Ejemplo (cont.) Variables: xA, xB y xC , cantidad a producir de cada tipo de ordenador, de mesa, port´ atil y de lujo. Modelo z = m´ ax 350xA + 470xB + 610x1 C s.a. xA + xB ≤ 120 (test 1) xC ≤ 48 (test 2) 10xA + 15xB + 20xC ≤ 2000 (montaje) xA , xB , xC ∈ Z+ Soluci´ on: xA = 120,

xB = 0,

xC = 40

Este producci´ on requiere de las 120 h. disponibles de test 1 y de las 2000 de montaje, mientras que sobran 8 de las 48 h. disponibles de test 2 Ejemplo tomado de Modelling the Supply Chain (Shapiro) 33

Coste fijo. Ejemplo (cont.) ´ no considera ninguna El problema inicial planteado por la empresa PECE relaci´ on entre los costes de producci´ on y los beneficios. Simplemente se trata de una asignaci´ on de recursos. Si quieren tratar estos costes, deben ser incluidos en la funci´ on objetivo: beneficio neto = ingreso por ventas – gasto en producci´ on El precio de venta es de 400, 520 y 686 euros para cada tipo de ordenador, respectivamente.

Ejemplo tomado de Modelling the Supply Chain (Shapiro)

34

Coste fijo. Ejemplo (cont.) La compa˜ n´ıa ha estimado que pasar los test de tipo 1 y 2, implica: Un coste fijo de 2016 euros, independientemente del n´ umero de ordenadores que lo pasen.

Un coste fijo de 1200 euros, independientemente del n´ umero de ordenadores que lo pasen.

Un coste variable, por hora, de 32 euros.

Un coste variable, por hora, de 38.5 euros.

5856 2740

Costes test 1

Costes T2 1200 2016

120

40

¿C´ omo incluir el coste fijo en el modelo? (funci´ on de coste con un salto) Ejemplo tomado de Modelling the Supply Chain (Shapiro) 35

Coste fijo. Ejemplo (cont.) Para incluir este coste fijo se recurre a variables binarias: δ1 =

 1 0

si se utiliza el test 1 en otro caso

Hay que garantizar que si no utiliza este test, no se haga uso de ninguna de las horas disponibles: xA + xB ≤ 120δ1 Para el test de tipo 2 se define una variable δ2 de la misma forma.

Ejemplo tomado de Modelling the Supply Chain (Shapiro)

36

Ejemplo (cont.) La funci´ on objetivo resulta: m´ ax 400xA + 520xB + 686xC − 2016δ1 − 1200δ2 − 32xA − 32xB − 38,5xC Modelo z = m´ ax 400xA + 520xB + 686xC − 2016δ1 − 1200δ2 − 32xA − 32xB − 38,5xC s.a. xA + xB xC 10xA + 15xB + 20xC xA , xB , xC

≤ 120δ1 ≤ 48δ2 ≤ 2000 ∈

(test 1) (test 2) (montaje)

Z+, δ1, δ1 ∈ {0, 1}

La soluci´ on ´ optima es xA = 120, xB = 0 y xC = 40. En este caso, el plan de producci´ on ´ optimo no ha cambiado. S´ olo cambia el beneficio, que es de 66844 euros, en lugar de los 66400 euros del modelo original. Se ha mejorado la estimaci´ on de costes. Ejemplo tomado de Modelling the Supply Chain (Shapiro) 37

Resoluci´ on del problema

38

La resoluci´ on se complica: el redondeo La primera tentaci´ on a la hora de abordar la resoluci´ on de un problema de programaci´ on entera es redondear la soluci´ on obtenida al relajar la condici´ on de integralidad. Esta no es una buena estrategia ya que:

1. No siempre proporciona la soluci´ on ´ optima. 2. No garantiza la obtenci´ on de soluciones factibles. 3. La selecci´ on del redondeo adecuado es un problema exponencial.

39

El redondeo: ejemplo Consideremos el siguiente problema de programaci´ on lineal entera z = m´ınx1 − 11x2 − x1 + 10x2 ≤ 40 10x1 + 10x2 ≤ 205 x1, x2 ≥ 0 y enteras

Soluci´ on ´ optima sin considerar las condiciones de integralidad: x1 = 15 y x2 = 5,5

40

El redondeo: ejemplo La regi´ on factible del modelo es: (15, 11 ) 2 (15, 6) r

r

r r

(10, 5)

(15, 5)

Posibles redondeos: x1 = 15 y x2 = 6: no verifica la primera restricci´ on. x1 = 15 y x2 = 5: es factible y z = −40. La soluci´ on x1 = 10 y x2 = 5 es factible y z = −45 41

Resoluci´ on de un problema entero Idea: Un problema lineal continuo es “muy sencillo” de resolver ⇒ ¿por qu´ e no desarrollar m´ etodos de resoluci´ on que empleen la programaci´ on lineal continua como una herramienta para resolver el problema entero? ¿c´ omo desarrollar estos m´ etodos?

a partir de las propiedades de la soluci´ on de un problema continuo y de las del m´ etodo de resoluci´ on del mismo, y a partir de las caracter´ısticas de un problema entero (c´ omo se modele el problema ser´ a muy importante)

42

Resoluci´ on del problema Los m´ etodos m´ as usados parten de la relajaci´ on del problema Idea: sustituir el problema entero original por un problema m´ as sencillo, que pueda ser resuelto m´ as f´ acilmente y, por tanto, que pueda ser utilizado para obtener cotas. La m´ as usada es la relajaci´ on lineal que consiste en eliminar la condici´ on de que las variables tomen valores enteros. Pero, no es la ´ unica

r

r

r

r

r

r

r

r

r

r

r

43

Resoluci´ on del problema Problema: Los puntos extremos no tienen por qu´ e ser enteros Si fueran enteros no habr´ıa problema ⇒ ¿por qu´ e no obtener la envoltura convexa? demasiado costoso Hay unas formulaciones “mejores” que otras: m´ as fuertes

r

r

r

r

r

r

r

r

r

r

r

44

Resoluci´ on del problema Soluci´ on: los m´ etodos m´ as extendidos son 1. M´ etodos de Planos de Corte: se introducen nuevas restricciones al problema relajado, hasta lograr que la soluci´ on ´ optima del nuevo problema sea entera. Se eliminan algunas soluciones continuas sin eliminar ninguna soluci´ on entera. 2. M´ etodos enumerativos: consisten en enumerar de forma impl´ıcita las soluciones y mediante test o cotas para la funci´ on objetivo, descartarlas antes de conocerlas expl´ıcitamente. El m´ etodo Branch and Bound (Ramificaci´ on y Acotaci´ on): divide en problemas menores: ramificaci´ on y descarta algunos de ellos: acotaci´ on 3. M´ etodos h´ıbridos: combinan las 2 estrategias anteriores El m´ etodo Branch and Cut (Ramificaci´ on y Corte) 45

Resoluci´ on: Branch and Bound M´ etodo de enumeraci´ on impl´ıcita: divide en problemas menores: ramificaci´ on y descarta algunos de ellos: acotaci´ on A veces puede usarse como heur´ıstico, si no se exploran todos los nodos. Si se exploran todos s´ı se garantiza el ´ optimo.

52

Ejemplo 1 m´ ax 2x1 + 3x2 5x1 + 7x2 ≤ 35 4x1 + 9x2 ≤ 36 x1 , x2 ∈ Z+

s

´ Optimo lineal: (63/17, 40/17), z = 14,4707

5x1 + 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36

Cota: z opt ≤ 14,4707 43

Ejemplo 1 (3.7059,2.3529) z=14.4706

s

´ Optimo lineal: (63/17, 40/17), z = 14,4707

5x1 + 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36

Cota: z opt ≤ 14,4707 44

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43

s

Nuevo o ´ptimo: (4, 2,14), z = 14,43

5x1 + 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36

Cota: z opt ≤ 14,4707 45

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 3 ≤ x2 ≤ +∞ no factible

s

5x1 + 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36

Cota: z opt ≤ 14,4707 46

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

3 ≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible

s

Nuevo o ´ptimo: (4,19, 2), z = 14,40

5x1 + 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36

Cota: z opt ≤ 14,4707 47

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

3 ≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible 5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

Cota: z opt ≤ 14,4707

Nuevo o ´ptimo: (5, 1,43), z = 14,29

s 5x1

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36

48

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

3 ≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible 5 ≤ x1 ≤ +∞ (5,1.43) z=14.29 2 ≤ x2 ≤ +∞ no factible

Cota: z opt ≤ 14,4707

s 5x1

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36

49

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible 5 ≤ x1 ≤ +∞ (5,1.43) z=14.29 2 ≤ x2 ≤ +∞ no factible

Cota: z opt ≤ 14,4707

0 ≤ x2 ≤ 1 (5.59,1) z=14.2

Nuevo o ´ptimo: (5,59, 1), z = 14,2

s 5x1

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36 50

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible 5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

0 ≤ x2 ≤ 1

2 ≤ x2 ≤ +∞

(5.59,1) z=14.2

no factible 6 ≤ x1 ≤ +∞ (6,0.71) z=14.13

Cota: z opt ≤ 14,4707

Nuevo o ´ptimo: (6, 0,71), z = 14,13

s 5x1

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

4x1 + 9x2 = 36 51

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible 5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

0 ≤ x2 ≤ 1

2 ≤ x2 ≤ +∞

(5.59,1) z=14.2

no factible 6 ≤ x1 ≤ +∞ (6,0.71) z=14.13

s 5x1

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

≤ x2 ≤ +∞ no factible

Cota: z opt ≤ 14,4707

4x1 + 9x2 = 36 52

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible 5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

0 ≤ x2 ≤ 1

2 ≤ x2 ≤ +∞

(5.59,1) z=14.2

no factible 6 ≤ x1 ≤ +∞ (6,0.71) z=14.13

ta: z opt ≤ 14,4707

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

0 ≤ x2 ≤ 0

≤ x2 ≤ +∞ no factible

Nuevo o ´ptimo: (7, 0), z = 14

s 5x1

(7,0) z=14

Incumbent: 14 ≤ z opt

4x1 + 9x2 = 36 53

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible 5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

0 ≤ x2 ≤ 1

2 ≤ x2 ≤ +∞

(5.59,1) z=14.2

no factible

0 ≤ x1 ≤ 5

6 ≤ x1 ≤ +∞ (6,0.71) z=14.13

(5,1) z=13

ta: z opt ≤ 14,4707

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

0 ≤ x2 ≤ 0

≤ x2 ≤ +∞ no factible

Nuevo o ´ptimo: (5, 1), z = 13

s 5x1

(7,0) z=14

Incumbent: 14 ≤ z opt

4x1 + 9x2 = 36 54

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞ (4,2.14) z=14.43 0 ≤ x2 ≤ 2

≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible

0 ≤ x1 ≤ 4

5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

(4,2) z=14 0 ≤ x2 ≤ 1

2 ≤ x2 ≤ +∞

(5.59,1) z=14.2

no factible

0 ≤ x1 ≤ 5

6 ≤ x1 ≤ +∞ (6,0.71) z=14.13

(5,1) z=13

ta: z opt ≤ 14,4707

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

0 ≤ x2 ≤ 0

≤ x2 ≤ +∞ no factible

Nuevo o ´ptimo: (4, 2), z = 14

s 5x1

(7,0) z=14

Incumbent: 14 ≤ z opt

4x1 + 9x2 = 36 55

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞

0 ≤ x1 ≤ 3

(4,2.14) z=14.43

(3,2.67) z=14 0 ≤ x2 ≤ 2

≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible

0 ≤ x1 ≤ 4

5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

(4,2) z=14 0 ≤ x2 ≤ 1

2 ≤ x2 ≤ +∞

(5.59,1) z=14.2

no factible

0 ≤ x1 ≤ 5

6 ≤ x1 ≤ +∞ (6,0.71) z=14.13

(5,1) z=13

ta: z opt ≤ 14,4707

+ 7x2 = 35

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

s

0 ≤ x2 ≤ 0

≤ x2 ≤ +∞ no factible

Nuevo o ´ptimo: (3, 2, 67), z = 1

s 5x1

(7,0) z=14

Incumbent: 14 ≤ z opt

4x1 + 9x2 = 36 56

Ejemplo 1 (3.7059,2.3529) z=14.4706 4 ≤ x1 ≤ +∞

0 ≤ x1 ≤ 3

(4,2.14) z=14.43

(3,2.67) z=14 0 ≤ x2 ≤ 2

3 ≤ x2 ≤ +∞

(4.19,2) z=14.4

no factible

0 ≤ x1 ≤ 4

5 ≤ x1 ≤ +∞ (5,1.43) z=14.29

(4,2) z=14 0 ≤ x2 ≤ 1

2 ≤ x2 ≤ +∞

(5.59,1) z=14.2

no factible

0 ≤ x1 ≤ 5

6 ≤ x1 ≤ +∞ (6,0.71) z=14.13

(5,1) z=13 0 ≤ x2 ≤ 0

1 ≤ x2 ≤ +∞ no factible

(7,0) z=14 57

Ramificaci´ on y acotaci´ on

1. Resolver el problema lineal relajado asociado, si la soluci´ on es entera: soluci´ on ´ optima, si no es entera, inicializar la cota (best bound), inicializar valor “mejor sol. entera”(best integer) e ir al paso 2. 2. Ramificaci´ on: Crear dos subproblemas a partir de una variable entera x que tome un valor fraccional x, a˜ nadiendo una nueva restricci´ on: Binaria: x = 0 y x = 1. Entera: x ≤ [x] y x ≥ [x + 1]. 3. Acotaci´ on: en cada subproblema, determinar una cota de la funci´ on objetivo.

53

Ramificaci´ on y acotaci´ on

4. Descarte: Se deja de desarrollar una rama si: la soluci´ on es entera: ¿su valor mejora el valor “mejor sol. entera´´? actualizar best integer y comparar con la best bound. la cota de la funci´ on objetivo es peor que el valor incumbente, descartar por acotaci´ on. el problema lineal asociado es infactible. 5. Si se ha obtenido una soluci´ on entera cuyo valor alcanza la best bound, parar, se ha obtenido una soluci´ on ´ optima. Si se ha llegado al final de todas las ramas, parar y escoger como optima la soluci´ ´ on con mejor funci´ on objetivo.

54

Ramificaci´ on y acotaci´ on. Comentarios

X Obtenci´ on de buenas cotas. Formulaciones m´ as fuertes dan lugar a mejores cotas Ir aprovechando la informaci´ on que se va obteniendo al desarrollar el ´ arbol para actualizar la best bound Criterios para obtener cotas: relajaci´ on lineal, relajaci´ on lagrangiana.

X Criterios de ramificaci´ on: ¿por qu´ e nodo seguir? Escoger el ´ ultimo nodo generado (f´ acil reoptimizar). Escoger el nodo m´ as prometedor (mejor cota).

X Criterios de ramificaci´ on: ¿por qu´ e variable ramificar? No es una decisi´ on trivial. Depende de la estructura del problema. 55

Ramificaci´ on y acotaci´ on. Comentarios Branch and Bound como heur´ıstico La diferencia entre la mejor cota y el valor de la soluci´ on incumbente nos da una idea de la calidad de la soluci´ on incumbente. ¿C´ omo medir la calidad a partir de esa diferencia?

Diferencia absoluta: ¿cu´ anto es de grande? Diferencia relativa: |incumbente − cota| |cota|

56

Comentarios finales

Si el tama˜ no del problema es muy grande y la estructura es compleja de manejar se pueden utilizar procedimientos heur´ısticos. Estos procedimientos devuelven una soluci´ on cercana al ´ optimo en un tiempo razonable.

Solvers para Programaci´ on Entera: CPLEX, LAMPS, OSL, SBB, XA, XPRESS, et.

M´ as informaci´ on en: http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/intprog.html http://plato.asu.edu/guide.html

57