pe02 (19-03-15) [modo de compatibilidad] entera/clases magistrales... · programación entera josé...

Programación Entera José Luis Quintero 1

FORMULACIÓN DE MODELOS DE PROGRAMACIÓN

ENTERAPROBLEMAS DE REDES

Postgrado de Investigación de Operaciones

Facultad de Ingeniería

Universidad Central de Venezuela

19 de Marzo de 2015


1. Problemas de redes

2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta

6. Flujo con costo mínimo

7. Flujo máximo

8. Red PERT

Puntos a tratar


• Una red consiste en una serie de nodos conectadospor arcos que también se denominan conexiones olíneas.

• Existen redes físicas (carreteras, comunicaciones,oleoductos, etc.) y sistemas que puedenrepresentarse como redes:

– Los nodos representan estados de un sistema,finalización de una operación, un período detiempo,…

– Los arcos representan órdenes de precedenciaentre operaciones,…

• Gráficamente, las redes se representan:

– Nodos mediante círculos.

– Arcos mediante líneas.

– Dirección del arco mediante puntas de flecha.

Modelos de redes


Nodos Arcos

10

Funciones en los arcos

Problemas de redes


Muchos problemas comerciales pueden ser resueltos através de modelos de redes.

Dadas ciertas condiciones en los datos, el resultado deun problema de redes garantiza una solución entera,dada su estructura matemática. No se necesitanrestricciones adicionales para obtener este tipo desolución.

Problemas de redes pueden ser resueltos por pequeñosalgoritmos , no importando el tamaño del problema,dada su estructura matemática.

Importancia de los problemas de redes


Formulación general de un problema de redes

Programación Entera José Luis Quintero

¿Por qué un experimento?

Problema de Transporte

Problema de Transbordo

Problema de Asignación

Problema de la Ruta más Corta

Problema del Flujo con Costo

Mínimo

Problema del Flujo Máximo

Problemas de Redes



2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta


7. Flujo máximo

8. Red PERT

Puntos a tratar


Un problema de transporte surge cuando se necesitaun modelo costo-efectividad que permita transportarciertos bienes desde un lugar de origen a un destinoque necesita aquellos bienes, con ciertas restriccionesen la cantidad que se puede transportar.

Se tienen m lugares de origen. Cada lugar de origentiene una capacidad de producción Si . Se tienen ndestinos. Cada destino j demanda Dj.

OBJETIVO. Minimizar el costo de transporte de la cargaal lugar de destino cumpliendo con las restricciones delos lugares de origen.

Problema de transporte


1 2 … n Recursos1 c11 c12 … c1n s1

Origen 2 c21 c22 … c2n s2… … … … …

m cm1 cm2 … cmn smDemanda d1 d2 … dn

DestinoCosto por unidad distribuida

⋮

Modelo general del problema de transporte


S1[s1]

S2[s2]

Sm[sm]

D1 [-d1]

D2 [-d2]

Dm [-dm]

c11

c12

c1nc21 c22

c2n

cm1cm2

cmn

Modelo de red del problema de transporte


.y para,0

,,...,2,1 para

,,...,2,1 para

a sujeta

min

1

1

1 1

jix

njdx

misx

xcZ

ij

m

jjij

n

jjij

m

i

n

jijij

≥

==

==

=

∑

∑

∑∑

=

=

= =

.y para,0

,,...,2,1 para

,,...,2,1 para

a sujeta

min

1

1

1 1

jix

njdx

misx

xcZ

ij

m

jjij

n

jjij

m

i

n

jijij

≥

==

==

=

∑

∑

∑∑

=

=

= =

Modelo matemático del problema de transporte


1. La oferta total no es igual a la demandatotal

2. Maximización en lugar de minimización

3. Capacidades en las rutas o mínimos en lasrutas

4. Rutas inaceptables

Algunas variantes del problema de transporte


La farmacéutica Carlton abastece dedrogas y otros suministros médicos. Estatiene tres plantas en: Cleveland, Detroit,Greensboro. Tiene cuatro centros dedistribución en: Boston, Richmond,Atlanta, St Louis. La gerencia de Carltondesea realizar el transporte de susproductos de la manera más económicaposible.

Ejemplo 1. Farmacéutica Carlton


Boston

Richmond

Atlanta

St.Louis

Origenes

Cleveland

Detroit

Greensboro

S1=1200

S2=1000

S3= 800

D1=1100

D2=400

D3=750

D4=750

Ejemplo 1. Red del problema

Destinos


La estructura del modelo es la siguiente:

Minimizar <Costo total de transporte>

sujeto a :

cantidad a transportar desde la fabrica = oferta de la fábrica

cantidad a recibir por la distribuidora = demanda de la distribuidora.

Variables de decisión:

Xij = cantidad a transportar desde la fábrica i a ladistribuidora j

donde i = 1 (Cleveland), 2 (Detroit), 3 (Greensboro)

j = 1 (Boston), 2 (Richmond), 3 (Atlanta),

4 (St,Louis)

Ejemplo 1. Modelo matemático


Boston

Richmond

Atlanta

St.Louis

D1=1100

D2=400

D3=750

D4=750

Cleveland

O1=1200

X11

X12

X13

X14

Detroit

O2=1000

X21

X22

X23

X24

Greensboro

O3= 800

X31

X32

X33

X34



Minimizar 35X11+30X12+40X13+ 32X14 +37X21+40X22+42X23+25X24+ 40X31+15X32+20X33+38X34

ST

Restricciones de la ofertaX11+ X12+ X13+ X14 1200

X21+ X22+ X23+ X24 1000X31+ X32+ X33+ X34 800

Restricciones de la demanda:X11+ X21+ X31 1100

X12+ X22+ X32 400X13+ X23+ X33 750

X14+ X24+ X34 750

Todos los Xij mayores que cero

===

=

===

Ejemplo 1. Modelo matemático completo


Se transporta un producto desde 3 plantas hasta

4 centros de distribución:

Origen Planta Capacidad deProducción en 3meses (unidades)

1 Cleveland 50002 Bedford 60003 York 2500

Total 13 500

DestinoCentro deDistribución

Pronóstico de lademanda a 3meses (unidades)

1 Boston 60002 Chicago 40003 St. Louis 20004 Lexigton 1500

Total 13 500

Ejemplo 2. Problema de la Foster Generators


Origen Boston Chicago St Louis Lexigton ProducciónCleveland 3 2 7 6 5000Bedford 7 5 2 3 6000

York 2 5 4 5 2500Demanda 6000 4000 2000 1500

13500

13500

Costo por unidad distribuidaDestino

Ejemplo 2. Problema de la Foster Generators


O1[5000]

O2[6000]

O3[2500]

D1 [6000]

[4000]

[2000]

[1500]

D2

D3

D4

2

45

Plantas

Nodos de Origen

Centros de Dist.

Nodos de DestinoRutas de Distribución

Arcos

Ejemplo 2. Modelo de red


Sea Z el costo total de transporte y sea xij (i=1,2,3;j=1,2,3,4) elnúmero de unidades transportadas de la enlatadora i al almacén j.

Max

Sujeta a las restricciones

11 12 13 14 21 22 23 24 31 32 33 34

11 12 13 14

21 22 23 24

31 32 33 34

11 21 31

12 22 32

13 23 33

Z 3x 2x 7x 6x 7x 5x 2x 3x 2x 5x 4x 5x

x x x x 5000

x x x x 6000

x x x x 2500

x x x 6000

x x x 4000

x x x

= + + + + + + + + + + +

+ + + =+ + + =

+ + + =+ + =

+ + =+ + =

14 24 34

ij

2000

x x x 1500

x 0 (i 1,2,3;j 1,2,3,4)

+ + =≥ = =

Max

Sujeta a las restricciones

11 12 13 14 21 22 23 24 31 32 33 34

11 12 13 14

21 22 23 24

31 32 33 34

11 21 31

12 22 32

13 23 33

Z 3x 2x 7x 6x 7x 5x 2x 3x 2x 5x 4x 5x

x x x x 5000

x x x x 6000

x x x x 2500

x x x 6000

x x x 4000

x x x

= + + + + + + + + + + +

+ + + =+ + + =

+ + + =+ + =

+ + =+ + =

14 24 34

ij

2000

x x x 1500

x 0 (i 1,2,3;j 1,2,3,4)

+ + =≥ = =




York 2500 0 0 0 2500Demanda 6000 4000 2000 1500 39500

Unidades que se envíanDestino


York 2500 0 0 0 2500Demanda 6000 4000 2000 1500 39500

Unidades que se envíanDestino

COSTO

Ejemplo 2. Solución óptima


La corporación Versatech producirá tresproductos nuevos. En este momento, cinco desus plantas tienen exceso de capacidad deproducción. El costo unitario respectivo defabricación del primer producto será de $31,$29, $32, $28 y $29, en las plantas 1, 2, 3, 4 y 5.El costo unitario respectivo de fabricación delsegundo producto será de $45, $41, $46, $42 y$43 en las plantas respectivas 1, 2, 3, 4 y 5; ypara el tercer producto será de $38, $35 y $40en las plantas respectivas 1, 2 y 3, pero lasplantas 4 y 5 no pueden fabricar este producto.

Ejemplo 3. Problema Versatech


Los pronósticos de ventas indican que laproducción diaria debe ser 600, 1000 y 800unidades de los productos 1, 2 y 3,respectivamente. Las plantas 1, 2, 3, 4 y 5tienen capacidades para producir 400, 600,400, 600 y 1000 unidades diarias; sin importarel producto o combinación de productos.Suponga que cualquier planta que tienecapacidad y posibilidad de fabricarlos podráproducir cualquier combinación deproductos en cualquier cantidad.



La gerencia desea asignar losnuevos productos a las plantas conel mínimo costo total defabricación.



1 2 3Planta 1 $31 $45 $38 400Planta 2 $29 $41 $35 600Planta 3 $32 $46 $40 400Planta 4 $28 $42 - 600Planta 5 $29 $43 - 1000

Pr Diaria 600 1000 800

3000

Capacidad

2400

OrigenTipo de Producto

Tabla de Costos

Destino1 2 3

Planta 1 $31 $45 $38 400Planta 2 $29 $41 $35 600Planta 3 $32 $46 $40 400Planta 4 $28 $42 - 600Planta 5 $29 $43 - 1000

Pr Diaria 600 1000 800

3000

Capacidad

2400

OrigenTipo de Producto

Tabla de Costos

Destino

Ejemplo 3. Datos problema Versatech


1 2 3Planta 1 0 0 200 200 <= 400Planta 2 0 0 600 600 <= 600Planta 3 0 0 0 0 <= 400Planta 4 600 0 0 600 <= 600Planta 5 0 1000 0 1000 <= 1000

Pr Diaria 600 1000 800 $88,400.00= = =

600 1000 800

Costo Mínimo

DestinoOrigen

CapacidadTipo de Producto

Tabla Cantidades (asignaciones a cada planta)

Ejemplo 3. Solución óptima problema Versatech


La compañía Move-It tiene dos plantas que producenmontacargas que se mandan a tres centros dedistribución. Los costos de producción unitarios son losmismos para las dos plantas y los costos de transporte(en cientos de dólares) por unidad para todas lascombinaciones de planta y centro de distribución semuestran en la tabla anexa. Se debe producir y mandarun total de 60 unidades por semana. Cada plantapuede producir y mandar cualquier cantidad hasta unmáximo de 50 unidades a la semana, de manera quehay una gran flexibilidad para dividir la producción totalentre las dos plantas y reducir los costos de transporte.

Ejemplo 4. Problema Move-It


El objetivo de la gerencia es determinar cuánto sedebe producir en cada planta y después, cuál debeser el patrón de embarque de manera que seminimice el costo total de transporte

Ejemplo 4. Problema Move-It

1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50

Dist. Sem. ? ? ?Suma

DestinoCentro de Distribución

Tabla de Costos de Transporte

Origen

100

Capacidad

60

1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50




Origen

100

Capacidad

60


1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50




Origen

100

Capacidad

60

1 2 3Planta A 0 0 50 50 <= 50Planta B 0 0 10 10 <= 50

Dist. Sem. 0 0 60 $25,000.0Suma COSTO Min.

=60

60

OrigenDestino

CapacidadCentro de Distribución

Cantidades por planta

Ejemplo 4. Datos y solución óptima problema Move-It


Resolver el problema de Move-It sicualquier centro de distribución puederecibir cualquier cantidad entre 10 y 30montacargas por semana para reducirmás el costo total de envío, siempre queel envío total a los tres centros sea iguala 60 montacargas por semana.

Ejemplo 5. Problema Move-It modificado


1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50

Dist. Sem. 10-30 10-30 10-30Suma



Origen

100

Capacidad

60

1 2 3Planta A 0 10 30 40 <= 50Planta B 20 0 0 20 <= 50

Dist. Sem. 20 10 30 $31,000.0>=10 >=10 >=10 COSTO Min.<=30 <=30 <=30

Suma=60

60

OrigenDestino

CapacidadCentro de Distribución

Cantidades por planta

Ejemplo 5. Datos y solución óptima problema Move-It modificado


El modelo matemático clásico de transporte hacevarias suposiciones simplificatorias. Entre las másimportantes están:

• Supone que los costos de envío son proporcionales alas cantidades que se envían.

• Supone que se puede enviar cualquier cantidad demercancía de cada fábrica a cada tienda sujetasolamente a satisfacer las demandas y no exceder lascapacidades de producción, no poniéndolerestricciones a las capacidades de las rutas de envío.

• Solamente se considera un tipo de mercancía en todoel problema.

• Se suponen nulas las pérdidas de mercancía en cadaruta del transporte.

Problema de transporte capacitado


Una generalización que se le puede hacer almodelo es ponerle restricciones de capacidada las rutas de envío para modelar, porejemplo, la cantidad de vehículos detransporte con que se cuenta, o la capacidadde la infraestructura del transporte (porejemplo el ancho de la carretera que limita elnúmero de vehículos que pueden transitar porhora en transporte carretero.) Es así que unmodelo llamado de Transporte Capacitadosatisface las siguientes expresionesmatemáticas:



M N

Minimizar ΣΣΣΣ ΣΣΣΣ Cij xij

j=1 i=1

M

sujeto a: ΣΣΣΣ xij = bj , j = 1, 2, ..., N

i=1

N

ΣΣΣΣ xij = ai , i = 1, 2, ..., Mj=1

kij ≥≥≥≥ xij ≥≥≥≥ 0, i = 1, 2, ..., M; j = 1, 2, ..., N

donde kij es la capacidad de transporte de laruta de envío que va de la fábrica i a latienda j.




2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta


7. Flujo máximo

8. Red PERT

Puntos a tratar


• El problema de transbordo es un problema de transporte en el que lamercancía, en lugar de ir directamente de origen a destino, puedepasar por unas zonas de trasbordo intermedias.

• El planteamiento general es:

Sujeto a:

Restricciones de oferta:

Restricciones de demanda:

Balance en zonas de transbordo:

m n n K m K

ij i j jk jk ik iki 1 j 1 j 1 k 1 i 1 k 1

M in (z ) c x c x c x= = = = = =

= + +∑ ∑ ∑ ∑ ∑ ∑

i j k

n K

ij ik ij 1 k 1

i x x O= =

∀ → + ≤∑ ∑

= =

∀ → + ≥∑ ∑m n

ik jk ki 1 j 1

k x x D

m K

ij jki 1 k 1

j x x= =

∀ → =∑ ∑

Problema de transbordo


Se debe minimizar el coste entre los orígenes 1 y 2 y losdestinos finales 5,6 y 7; satisfaciendo la demanda.

Oferta máxima Demanda

1 5

6

72

3

4

100.000

200.000

65.000

60.000

40.000

Origen 3 4 5 6 71 900 2400 - - -2 1200 2700 - - -3 - - 2107 1223 13434 - - 1095 1833 1348

DestinosCostes de transporte entre los puntos

Ejemplo 6. Problema de transbordo


Definición de variables

xij Cantidad de producto transportado de i a j donde i = (1, 2), j = (3, 4)

xjk Cantidad de producto transportado de j a k donde j = (3, 4), k = (5, 6, 7)

• Función Objetivo

• Restricciones

Oferta

Transbordo

Demanda

Negatividad: xij, , xjk ≥ 0

3 5 4 5

3 6 4 6

3 7 4 7

6 0 . 0 0 0

4 0 . 0 0 0

6 5 . 0 0 0

x x

x x

x x

+ =+ =+ =

1 3 2 3 3 5 3 6 3 7

1 4 2 4 4 5 4 6 4 7

x x x x x

x x x x x

+ = + ++ = + +

13 23 14 24 35

45 36 46 37 47

( ) 900 1200 2400 2700 2107

1095 1226 1833 1343 1348

M in z x x x x x

x x x x x

= + + + ++ + + + +

1 3 1 4

2 3 2 4

2 0 0 . 0 0 0

1 0 0 . 0 0 0

x x

x x

+ ≤+ ≤

Ejemplo 6. Problema de transbordo



2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta


7. Flujo máximo

8. Red PERT

Puntos a tratar


n trabajadores deben ser asignados a ntrabajos. Un costo unitario (o ganancia) Cij esasociado al trabajador i que realizará eltrabajo j.

Minimizar el costo total (o maximizar laganancia total) de la asignación detrabajadores a sus respectivos empleos que lecorresponde a cada uno, tratando de que estaasignación sea la óptima posible.

Problema de asignación


1. El número de asignados es igual al número detareas (se denota por n). (esto puede variar)

2. Cada asignado se asigna exactamente a unatarea.

3. Cada tarea debe realizarla exactamente unasignado.

4. Existe un costo cij asociado con el asignado i(i=1,2,…,n).

5. El objetivo es determinar cómo deben hacerse lasasignaciones para minimizar los costos totales.

Suposiciones del problema de asignación


S1[1]

S2[1]

Sm[1]

D1 [1]

D2[1]

Dm [1]

c11c12

c1nc21 c22

c2n

cm1 cm2

cmn

Modelo de red del problema de asignación


).y todapara binarias, (y para,0

,,...,2,1 para1

,,...,2,1 para1

a sujeta

min

1

1

1 1

jixjix

njx

mix

xcZ

ijij

m

jij

n

jij

ij

m

i

n

jij

≥

==

==

=

∑

∑

∑∑

=

=

= =

).y todapara binarias, (y para,0

,,...,2,1 para1

,,...,2,1 para1

a sujeta

min

1

1

1 1

jixjix

njx

mix

xcZ

ijij

m

jij

n

jij

ij

m

i

n

jij

≥

==

==

=

∑

∑

∑∑

=

=

= =

Modelo matemático del problema de asignación


Existen 5 diferentes proyectos eléctricos sobre 5 líneasde producción que necesitan ser inspeccionadas. Eltiempo para realizar una buena inspección de un áreadepende de la línea de producción y del área deinspección. La gerencia desea asignar diferentes áreasde inspección a inspectores de productos tal que eltiempo total utilizado sea mínimo.

Tiempo de inspección en minutos para la línea de ensamble de cada área de inspección.

Area de InspecciónA B C D E

1 10 4 6 10 12 Linea 2 11 7 7 9 14Ensamble 3 13 8 12 14 15

4 14 16 13 17 175 19 17 11 20 19

Ejemplo 7. Electrónica Ballston


1

2

3

4

5

Línea de ensamble Área de Inspección

A

B

C

D

E

S1=1

S2=1

S3=1

S4=1

S5=1

D1=1

D2=1

D3=1

D4=1

D5=1



1 2 31. Terry 10 15 92. Carla 9 18 53. Roberto 6 14 3

Jefe deProyecto

Cliente

Tiempos estimados de terminación delproyecto (días)

Ejemplo 8. Fowle Marketing Research


J1[1]

J2[1]

J3[1]

C1 [1]

[1]

[1]

C2

C3

18

3

Jefes de Proyecto

Nodos de Origen

Clientes

Nodos de DestinoAsignaciones Posibles

Arcos

Ejemplo 8. Modelo de red


Sea Z el tiempo total de terminación

)4,3,2,1;3,2,1(0

1

1

1

1

1

1

3146518991510

332313

322212

312111

333231

232221

131211

333231232221131211

==≥=++=++=++=++

=++=++

++++++++=

jix

xxx

xxx

xxx

xxx

xxx

xxx

xxxxxxxxxZ

ij

nesrestriccio las a Sujeta

Max

)4,3,2,1;3,2,1(0

1

1

1

1

1

1

3146518991510

332313

322212

312111

333231

232221

131211

333231232221131211

==≥=++=++=++=++

=++=++

++++++++=

jix

xxx

xxx

xxx

xxx

xxx

xxx

xxxxxxxxxZ

ij

nesrestriccio las a Sujeta

Max


=así es no si

cliente al proyecto de jefe el asigna se si

0

1 jixij


1 2 31. Terry 0 1 0 1 = 12. Carla 0 0 1 1 = 13. Roberto 1 0 0 1 = 1

1 1 1= = = Costo 261 1 1

AsignacionesJefe deProyecto

Cliente

Ejemplo 8. Solución óptima


El entrenador de un equipo de natación debe asignarcompetidores para la prueba de 200 metros de relevocombinado que irán a las Olimpiadas Juveniles. Comomuchos de sus mejores nadadores son rápidos en másde un estilo, no es fácil decidir qué nadador asignarcada uno de los cuatro estilos. Los cinco mejoresnadadores y sus mejores tiempos (en segundos) encada estilo son los siguientes.

Carlos Cristy David Antony JoséDorso 37.7 32.9 33.8 37 35.4Pecho 43.4 33.1 42.2 34.7 41.8Mariposa 33.3 28.5 38.9 30.4 33.6Libre 29.2 26.4 29.6 28.5 31.1

Tiempo de Nado

Ejemplo 9. Problema natación


Carlos Cristy David Antony JoséDorso 0 0 1 0 0 1 = 1Pecho 0 0 0 1 0 1 = 1Mariposa 0 1 0 0 0 1 = 1Libre 1 0 0 0 0 1 = 1

1 1 1 1 0<= <= <= <= <=1 1 1 1 1

TIEMPO Min.

Tiempo de Nado

126.2

Ejemplo 9. Solución óptima problema natación


GENERALIZED ASSIGNMENT PROBLEM.

Se tiene un conjunto J={1,2,..,n} de índices de lostrabajos a realizar y otro conjunto I={1,2,..,m} depersonas para realizarlos. El coste (o valor) de asignarla persona i al trabajo j viene dado por cij. Además setiene una disponibilidad bi de recursos de la persona i(como por ejemplo horas de trabajo) y una cantidadaij de recursos de la persona i necesarias para realizarel trabajo j. Con todo esto, el problema consiste enasignar las personas a los trabajos con el mínimo coste(o el máximo valor).

Al igual que en los otros modelos de asignaciónvistos, se introducen variables xij que valen 1 si lapersona i se asigna al trabajo j y 0 en otro caso.

Problema de la asignación generalizada (GAP)


Problema de la asignación generalizada

{ }

m n

ij iji 1 j 1

n

ij ij ij 1

m

iji 1

ij

min c x s.a.

a x b i 1,...,m

x 1 j 1,...,n

x 0,1 , i 1,...,m j 1,...,n

= =

=

=

≤ =

= =

∈ = =

∑∑

∑

∑


En este modelo de asignación se puede asignaruna persona a más de un trabajo, respetandoobviamente las limitaciones en los recursos.

Algunas de las aplicaciones mas relevantes son:

– • Asignación de clientes a camiones (de reparto o

recogida) de mercancías.

– • Asignación de tareas a programadores.

– • Asignación de trabajos a una red de

computadores.

Problema de la asignación generalizada



2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta


7. Flujo máximo

8. Red PERT

Puntos a tratar


Se trata de encontrar la ruta de menor distancia, ocosto, entre el punto de partida o nodo inicial y eldestino o nodo terminal.

Se tienen n nodos, partiendo del nodo inicial 1 yterminando en el nodo final n.

Arcos bi-direccionales conectan los nodos i y j condistancias mayores que cero, dij . Se desea encontrarla ruta de mínima distancia que conecta el nodo 1 conel nodo n.

LINEAS FAIRWAY VAN

Determine la ruta mas corta entre Seattle y El Paso parala siguiente red de carreteras.

Problema de la ruta más corta


Salt Lake City

1 2

3 4

5 6

7

8

9

1011

12

1314

15

1617 18 19

El Paso

Seattle

Boise

Portland

Butte

Cheyenne

Reno

Sac.

Bakersfield

Las Vegas

Denver

Albuque.

KingmanBarstow

Los Angeles

San DiegoTucson

Phoenix

599

691497180

432 345 440

102

452

621

420

526138

291

280

432

108

469207

155114

386 403

118

425 314



Solución - Analogía de un problema deprogramación lineal

Variables de decisión

Xij = 1 si un transporte debe viajar por la carretera que une la ciudad i con la ciudad j. 0 En cualquier otro caso

Objetivo = Minimizar S dijXij

Ejemplo 10. Problema de la ruta más corta


7

2

Salt Lake City

1

3 4

Seattle

Boise

Portland

599

497180

432 345

Butte

[El numero de carreteras para salir de Seattle (Nodo de inicio)] = 1 X12 + X13 + X14 = 1

De una forma similar:[El número de carreteras para llegar a El Paso (Nodo final)] = 1 X12,19 + X16,19 + X18,19 = 1

[El número de carreteras para entrar a la cuidad] = [El número de carreteras para salir de la ciudad]. Por ejemplo, en Boise (Ciudad 4): X14 + X34 +X74 = X41 + X43 + X47.

Sujeto a las siguientes restricciones

Ejemplo 10. Problema de la ruta más corta



2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta


7. Flujo máximo

8. Red PERT

Puntos a tratar


• Son una generalización de los problemasde transporte y transbordo.

• Consiste en “transportar” una ciertacantidad de “producto” de unos orígenes aunos destinos. El paso por cada arcoorigina un costo. Se debe minimizar lasuma de los costos.

Problema del flujo con costo mínimo


• Se debe minimizar el costo entre los orígenes 1 y 2y los destinos 9,8 y 10

1 3 9

5 6 8

2 4 7 10

50

67

20

52

45

6

3

10

8

4

53

22

3

7

6

Ejemplo 11. Problema del flujo con costo mínimo


• El planteamiento sería:

• Sujeto a:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

No negatividad: xij ≥0

1 3 2 4 3 9 3 6

4 5 4 7 5 6 6 8

6 9 6 1 0 7 5 7 6

M i n ( z ) = 6 x + 3 x + 1 0 x + 8 x

+ 5 x + 3 x + 4 x + 7 x

+ 3 x + 6 x + 2 x + 2 x

1 3

2 4

1 3 3 9 3 6

2 4 4 5 4 7

4 5 7 5 5 6

3 6 5 6 7 6 6 8 6 9 6 1 0

4 7 7 5 7 6

6 8

3 9 6 9

6 1 0

- x = - 5 0

- x = - 6 7

x - x - x = 0

x - x - x = 0

x + x - x = 0

x + x + x - x - x - x = 0

x - x - x = 0

x = 5 2

x + x = 2 0

x = 4 5

Ejemplo 11. Problema del flujo con costo mínimo



2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta


7. Flujo máximo

8. Red PERT

Puntos a tratar


Consiste en planificar los flujos a través de una red de manera que semaximice el volumen de mercancía en circulación, teniendo en cuentaque existen restricciones de flujo máximo y, posiblemente de flujo mínimoen cada uno de los arcos.

2 5 7

1 3 9

4 6 8

Placa Principal Inst. Opciones Test

Grafo del problema

Capacidades máximasNodo Capacidad

1 302 203 154 105 186 257 108 129 ∞

Ejemplo 12. Problema del flujo máximo con limitación en los arcos


• La formulación del problema sería:Max (z) = x79 + x89

• Sujeto a:Balance de flujos:

2) x12 – x25 = 03) x13 – x35 – x36 = 04) x14 – x46 = 05) x25 + x35 – x57 = 06) x36 + x46 – x67 – x68 = 07) x57 + x67 – x79 = 08) x68 – x89 = 0

Restricciones de flujo máximo:1) x12 + x13 + x14 ≤ 302) x25 ≤ 203) x36 + x35 ≤ 154) x46 ≤ 105) x57 ≤ 186) x67 + x68 ≤ 257) x79 ≤ 108) x89 ≤ 12

No negatividad: xij ≥0

Ejemplo 12. Problema del flujo máximo con limitación en los arcos



2. Transporte

3. Transbordo

4. Asignación

5. Ruta más corta


7. Flujo máximo

8. Red PERT

Puntos a tratar


• Los proyectos se descomponen en un conjunto de actividadesque deben realizarse en un orden determinado.

• El proyecto puede representarse como un grafo, donde cadanodo representa una tarea y cada arco representa una relaciónde precedencia entre dos trabajos. La distancia entre los nodosserá el tiempo previsto que se empleará en pasar de una tarea aotra.

• Un problema de gran interés es determinar el camino crítico queconsiste en calcular el camino más largo que permite atravesarla red o completar el proyecto.

• Esto permitirá calcular cuál va a ser la duración total delproyecto y detectar las fases críticas (aquellas que condicionanla duración del mismo).

• El planteamiento es idéntico al de camino más corto, sólo que lafunción objetivo será una de maximización.

Red PERT


• El planteamiento sería:

Max (z) = 5x12 + 4x13 + 6x24 + 3x25 + 2x32+ 4x35 +4x46 + 2x56

• Sujeto a:

1) - x12 – x13 = -1

2) x12 + x32 – x24 – x25 = 0

3) x13 – x32 – x35 = 0

4) x24 – x45 – x46 = 0

5) x25 + x45 + x35 – x56 =0

6) x46 + x56 =1

xij ≥0

2 4

5

6

3

64

5

4 4

213

2

Ejemplo 13. Red PERT


Pensamiento de hoy

“Los gerentes no controlan larealidad, sino los modelos orepresentaciones de ésta”.

Robert D. Gilbreath

pe02 (19-03-15) [modo de compatibilidad] entera/clases magistrales... · programación entera josé...

Documents