PE05 (16-04-15) [Modo de compatibilidad] Entera/Clases... · Jugador 1 2 3 4 5 6 7 8 9 10 11 12 1 * * * * ... realiza el viaje j y 0 en caso contrario. Min (z)= 5 y1 + 3 y2 + 4 y3

Programación Entera José Luis Quintero 1

FORMULACIÓN DE MODELOS DE PROGRAMACIÓN

ENTERAPROBLEMAS CLÁSICOS

Postgrado de Investigación de Operaciones

Facultad de Ingeniería

Universidad Central de Venezuela

16 de Abril de 2015


1. Problema de la mochila (knapsack)

2. Problema de recubrimiento (set covering)

3. Problema de empaquetado (set packing)

4. Problema de partición (set partitioning)

5. Problema del agente viajero (TSP)

Puntos a tratar


Planteamiento general del problema

{ }1,0yj

bya

:a Sujeto

yp (z)Max

j

n

1jjj

n

1jjj

∈→∀

≤

=

∑

∑

=

=

Problema de la mochila


Un contrabandista desea pasar objetos a través deuna frontera en un depósito oculto que es capaz decontener un máximo de 91kg. Los artículos que sepueden transportar, su peso y su ganancia asociadaa cada uno de ellos de detallan en la tabla:

Elemento Peso(kg.) Valor (u.m.)

1 36 54

2 24 18

3 30 60

4 32 32

5 26 13

Máximo 91 ----

Ejemplo 1. El contrabandista


El modelo de optimización sería:yj: Variable binaria que toma valor 1 si seincluye el artículo j en la mochila y 0 en casocontrario.

Max (z)= 54 y1 + 18 y2 + 60 y3 + 32 y4 + 13 y5

Sujeto a las restricciones:36 y1 + 24 y2 + 30 y3 + 32 y4 + 26 y5 ≤≤≤≤ 91y1 ,y2 , y3 , y4 , y5 ∈{∈{∈{∈{0,1}}}}

Ejemplo 1. El contrabandista


Ejemplo 2. Inversión de capital


Ejemplo 2. Inversión de capital


Ejemplo 3. Programación de pacientes











Puntos a tratar


El planteamiento general del problema:

{ }1,0yj

1yai

:a Sujeto

yc (z) Min

j

n

1jjij

n

1jjj

∈→∀

≥→∀

=

∑

∑

=

=

Problema de recubrimiento


1 2 3 4COSTE (mill) 300 410 380 637

Zona 1 1 0 1 1Zona 2 1 1 0 0Zona 3 0 1 1 1Zona 4 0 1 0 1Zona 5 0 0 1 1Zona 6 0 0 1 1

HOSPITAL

Ejemplo 4. Hospitales y zonas


El modelo de optimización sería:

yj: Variable binaria que toma valor 1 si se construye elhospital j y 0 en caso contrario.

Min (z)= 300 y1 + 410 y2 + 380 y3 + 637 y4

Sujeto a las restricciones:

Zona 1) y1 + y3 + y4 ≥≥≥≥ 1

Zona 2) y1 + y2 ≥≥≥≥ 1

Zona 3) y2 + y3 + y4 ≥≥≥≥ 1

Zona 4) y2 + y4 ≥≥≥≥ 1

Zona 5) y3 + y4 ≥≥≥≥ 1

Zona 6) y3 + y4 ≥≥≥≥ 1

y1 ,y2 , y3 , y4 ∈{∈{∈{∈{0,1}}}}

Ejemplo 4. Hospitales y zonas


Ejemplo 5. Estaciones de bomberos











Puntos a tratar



{ }1,0yj

1yai

:a Sujeto

yc (z)Max

j

n

1jjij

n

1jjj

∈→∀

≤→∀

=

∑

∑

=

=

Problema de empaquetado


Un conocido equipo de fútbol tieneestablecido en el contrato de seis jugadoresque de llegar estos a los 30 juegos disputadospor temporada, recibirían una importantesuma de dinero de bonificación. Cadajugador ha participado en 28 juegos y ladirección de finanzas del equipo no está enposibilidades de pagar el dinero.

Ejemplo 6. Equipo de fútbol


Quedando dos juegos para finalizar latemporada, se le pide al director técnico queelija una combinación de jugadores en lospróximos dos juegos sin que cada jugadorjuegue dos veces tales que se maximice laposibilidad de goles. El asistente del directortécnico planteó las diferentes combinacionesde jugadores que se pueden tener y los golespromedio que han tenido estos grupos en lasprácticas de la temporada.



CombinaciónJugador 1 2 3 4 5 6 7 8 9 10 11 12

1 * * * *2 * * * * * *3 * * * * * * * *4 * * * * * *5 * * * * * * *6 * * * *

Goles Promedio 5 6 2 4 3 2 4 5 2 1 3 2



Las combinaciones atienden a que losjugadores 1, 2 y 3 son delanteros, y los tresrestantes volantes. Se puede jugar con dosdelanteros y un volante o dos volantes y undelantero. En los casos en los que hay cuatrojugadores, (combinación 3) se debe a que eljugador 6 no se entiende bien con losdelanteros 1 y 3 por lo cual necesita la ayudadel volante 5. Adicionalmente el jugador 1funciona bien con el volante 4 sin necesidadde otro jugador. Diversas alternativasproporcionan la misma cantidad promedio degoles.



• Planteamiento del problema:

• Sujeto a

• Xi binaria {0,1} con i = 1,2,,,,,6

121110987654321 3254234265max xxxxxxxxxxxx +++++++++++

17321 ≤+++ xxxx

1986541 ≤+++++ xxxxxx112111065432 ≤+++++++ xxxxxxxx

111108741 ≤+++++ xxxxxx1121096532 ≤++++++ xxxxxxx

1121193 ≤+++ xxxx








Puntos a tratar



{ }1,0yj

1yai

:a Sujeto

yc (z) Opt

j

n

1jjij

n

1jjj

∈→∀

=→∀

=

∑

∑

=

=

Problema de partición


Suponga que deben repartirse seis pedidos en dos tipos decamiones, pero no todos los pedidos son compatibles contodos los camiones. En la tabla se codifican lascompatibilidades de pedidos y camiones, así como el coste decada viaje.

41435Coste por viaje

116

115

114

113

112

111

54321

Camión 2Camión 1

Viajes

Pedidos

41435Coste por viaje

116

115

114

113

112

111

54321

Camión 2Camión 1

Viajes

Pedidos

Ejemplo 7. Plan de viajes


Se desea obtener un plan de viajes que atienda todos lospedidos de una sola vez, a un coste mínimo.

PEDIDOS 1 2 3 4 51 1 0 0 1 02 1 1 0 0 03 0 1 0 0 14 1 0 1 0 05 0 0 1 0 16 0 0 0 1 1

Coste por viaje 5 3 4 1 4

CAMIÓN 2CAMIÓN 1VIAJES



El modelo de optimización sería:

yj: Variable binaria que toma valor 1 si realiza el viaje j y 0 en caso contrario.

Min (z)= 5 y1 + 3 y2 + 4 y3 + 1 y4 + 4 y5



Sujeto a las restricciones:Pedido 1) y1 + y4 = 1Pedido 2) y1 + y2 = 1Pedido 3) y2 + y5 = 1Pedido 4) y1 + y3 = 1Pedido 5) y3 + y5 = 1Pedido 6) y4 + y5 = 1y1 ,y2 , y3 , y4 , y5 ∈{∈{∈{∈{0,1}}}}








Puntos a tratar


El problema del agente viajero (TravellingSalesman Problem – TSP) consiste en visitar nciudades, una detrás de otra, de forma que nose repita la visita a ninguna ciudad. Estas visitasdeben planificarse de forma que el número dekm. recorridos sea el mínimo posible.

El número de posibles recorridos (tours) entre nciudades que cumplen las anteriorescondiciones es: (n-1)!

El problema del agente viajero


Si se tuviera que enumerar todas las posiblesmetas se tendría:

2! = 2

5! = 120

10! = 3.628.000

20! = 2,43 x 1018 (aproximadamente)

50! = 3,04 x 1064 (aproximadamente)



Genéricamente se plantea:yij: Variable binaria que toma valor 1 si elrecorrido del viajante va directamente de ia j, y 0 en caso contrario.

{ }

= =

=≠

=≠

=

∀ → =

∀ → = ∈

∑∑

∑

∑

n n

ij iji 1 j 1

n

ijj 1i j

n

ij iji 1i j

Min (z) c y

Sujeto a:

i y 1

j y 1 y 0,1





Si existen subtours entre m ciudades entrantes, seañade:

Subtour entre 2 ciudades (m=2)

Subtour entre 3 ciudades (m=3)


{ } { }ij jiy y 1 i 1,...,n j 1,...,n i j+ ≤ ∀ ∈ ∀ ∈ ≠

{ } { } { }ij jk kiy y y 2 i 1,...,n j 1,...,n j 1,...,n i j j k+ + ≤ ∀ ∈ ∀ ∈ ∀ ∈ ≠ ≠


Recorridos con cuatro ciudades


Recorridos con cinco ciudades


Solución record (2001) de 15112 ciudades en Alemania


Solución record (2004) de 24978 ciudades en Suecia


Solución record actual (2005)


LC ST BI VA ZA BA MA VL SV MGLa Coruña LC - 535 644 455 822 1.120 606 962 948 1.162Santander ST - 112 248 400 706 395 668 839 936Bilbao BI - 280 320 594 394 623 866 935Valladolid VA - 368 666 193 545 591 732Zaragoza ZA - 296 322 325 863 863Barcelona BA - 620 349 1.023 620Madrid MA - 356 541 541Valencia VL - 668 643Sevilla SV - 214Málaga MG -

Ejemplo 8. Planificación viajera


El planteamiento del problema sería:

Min (z)= 535 LCST + 644 LCBI +455 LCVA + 822 LCZA + 1.120 LCBA + 606 LCMA + … + 214 SVMG



Sujeto a las restricciones:

Debe salirse una vez de cada ciudad:

LC) LCST + LCBI + LCVA + LCZA + LCBA + LCMA+ +LCVL + LCSV + LCMG = 1

ST) STLC + STBI + STVA + STZA + STBA + + STMA+ +STVL + STSV + STMG = 1…

MG) MGST + MGBI + MGVA + MGZA + MGBA + MGMA + MGVL + MGSV + MGLC = 1



Debe entrarse una vez en cada ciudad:

LC) STLC + BILC + VALC + ZALC + BALC ++ MALC+ VLLC + SVLC + MGLC = 1

ST) LCST + BIST + VAST + ZAST + BAST ++ MAST+ VLST + SVST + MGST = 1…

MG) STMG + BIMG + VAMG + ZAMG + BAMG+ MAMG + VLMG + SVMG + LCMG = 1No negatividad e integralidad: yij ∈{∈{∈{∈{0,1}}}}



Se resuelve así planteado el problema.

Si en la solución aparecen subtours seañaden las restricciones necesariaspara romperlos y se vuelve a resolverel problema.



Tras la resolución aparecerían 5 subtours, así quedeberíamos añadir más restricciones para romperlos.



Debe entrarse una vez en cada ciudaddentro del subtour:

LC-VA) LCVA + VALC ≤≤≤≤ 1ST-BI) STBI + BIST ≤≤≤≤ 1ZA-BA) ZABA + BAZA ≤≤≤≤ 1MA-VL) MAVL + VLMA ≤≤≤≤ 1SV-MG) SVMG + MGSV ≤≤≤≤ 1



Se resuelve así planteado el problemapero en la solución vuelven aaparecen subtours por lo que seañaden las restricciones necesariaspara romperlos y se vuelve a resolver elproblema.





Debe entrarse una vez en cada ciudaddentro del subtour:

LC-VA-BI-ST) LCVA + VABI + BIST + STLC ≤≤≤≤ 3ZA-VL-BA) ZAVL + VLBA + BAZA ≤≤≤≤ 2MA-MG-SV ) MAMG + MGSV+ SVMA ≤≤≤≤ 2



Se resuelve así planteado el problemapero en la solución vuelven aaparecen subtours por lo que seañaden las restricciones necesariaspara romperlos y se vuelve a resolverel problema.





Se debe realizar una visita a cuatro oficinas locales dela AGE, partiendo de la oficina principal y volviendo ala misma, la cual esta ubicada en Northridge, SouthernCalifornia.

Tiempo en minutos para trasladarse de una oficina aotra

Hacia la oficinaH 1 2 3 4

F Of. Princ 30 45 65 80

r Of. 1 30 25 50 50

o Of. 2 45 25 40 40

m Of. 3 65 50 40 35

Of. 4 80 50 40 35

Ejemplo 9. El vendedor viajero


30

25

40

35

80

6545

50

50

40

Oficina

Principal

1

2 3

4

Ejemplo 9. Red del problema


Ciclo Costo Total

1. H-O1-O2-O3-O4-H 210

2. H-O1-O2-O4-O3-H 195

3. H-O1-O3-O2-O3-H 240

4. H-O1-O3-O4-O2-H 200

5. H-O1-O4-O2-O3-H 225

6. H-O1-O4-O3-O2-H 200

7. H-O2-O3-O1-O4-H 265

8. H-O2-O1-O3-O4-H 235

9. H-O2-O4-O1-O3-H 250

10. H-O2-O1-O4-O3-H 220

11. H-O3-O1-O2-O4-H 260

12. H-O3-O1-O2-O4-H 260

Ejemplo 9. Identificación de posibles ciclos


Datos de entrada para el problema de vendedor viajero en WINQSB

Ejemplo 9. Datos del problema


Solución de WINQSB -Una combinación

de

problema de asignación y la técnica

Branch and Bound

Ejemplo 9. Solución óptima del problema


30

25

40

35

80

6545

50

50

40

Oficina

Principal

1

2 3

4

Ejemplo 9. Solución óptima del problema


Pensamiento de hoy

“A medida que la complejidadcrece, los planteamientos precisospierden significado y losplanteamientos llenos de significadopierden precisión”.

Lofti Zadeh

Documents

PE05 (16-04-15) [Modo de compatibilidad] Entera/Clases... · Jugador 1 2 3 4 5 6 7 8 9 10 11 12 1 * * * * ... realiza el viaje j y 0 en caso contrario. Min (z)= 5 y1 + 3 y2 + 4 y3