• Author / Uploaded
• Matias Caporale

Citation preview

INGENIERÍA EN SISTEMAS DE INFORMACIÓN - INVESTIGACIÓN OPERATIVA

Investigación Operativa – Segundo Parcial – 25/09/2017 Apellido y nombre: ….......................................................................................................................... 1) Una compañía dispone de cuatro fábricas Fi, con i = 1, …, 4 con capacidades de producción de 240, 190, 250 y 175 unidades respectivamente, y debe suministrar 185, 110, 125, 180 y 170 unidades a sus cinco clientes Cj, j = 1, …, 5. Estudia la apertura de, a lo sumo, tres centros de distribución, con cinco posibles localizaciones Dk, k = 1, …, 5. Se dispone de 180 000 euros, siendo los costos de construcción en cada localización 100 000, 70 000, 120 000, 100 000 y 80 000 euros, respectivamente. Los costos por unidad de producto envasado por el centro de distribución k son 200, 300, 200, 200 y 300 euros. Los costos de transporte c ikj por unidad, en euros, de la fábrica F i al cliente Cj a través del centro Dk son cikj k = 1, 2 k=3 k = 4, 5 j

j

j

i

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

30

50

20

40

30

60

40

70

80

30

40

50

80

10

60

2

30

20

40

20

30

40

60

20

70

30

60

30

90

30

40

3

50

10

60

30

10

60

50

10

80

20

20

80

40

20

10

4 40 30 20 60 20 30 40 20 10 20 70 30 10 30 20 Si se supone que se sirve a cada cliente desde un solo centro, formular un modelo de programación entera que determine el plan de localización y distribución más económico. Solución: Variables de decisión xikj: cantidad a enviar desde la fábrica i al cliente j a través del centro de distribución k yk: 1 si se construye el centro de distribución k, 0 si no wkj: 1 si se abastece al cliente j desde el centro de distribución k Parámetros c’ikj: costo de transporte cikj + costo de envasado del centro k uk: costo de localización del centro k ai: oferta en la fábrica i bj: demanda del cliente j Modelo

4

5

5

5

min Z=∑ ∑ ∑ c ' ikj x ikj +∑ uk y k i=1 k=1 j=1

k=1

s.a. 100 000 y₁ + 70 000 y₂ + 120 000 y₃ + 100 000 y₄ + 80 000 y₅ ≤ 180 000 5

∑ y k≤3 k=1 5

5

∑ ∑ x ikj≤ai , ∀ i=1,…, 4 k=1 j=1 4 5

∑ ∑ x ikj≥b j , ∀ j=1,… , 5 i=1 k=1 4

∑ xikj ≤b j wkj , ∀ k , ∀ j i=1

w kj ≤ y k , ∀ k ,∀ j 5

∑ wkj=1, ∀ j k=1

xikj ≥0 ; y k ∈{0,1}, w kj ∈{0,1}

2) Los Hatfields, los Montagues, los McCoys y los Capulets se van a su día de campo familiar anual. Se dispone de cuatro automóviles para transportar las familias. En los automóviles caben los siguientes números de personas: automóvil 1, cuatro; automóvil 2, tres; automóvil 3, tres; y automóvil 4, cuatro. Hay cuatro personas en cada familia, y ningún automóvil puede llevar más de dos personas de cualquier familia. Formule el problema de transportar el número máximo posible de personas al día de campo como un problema de flujo máximo. Red

H

2 2

4 4 I

4

A1

M

2

4 A2

2 Mc

2

4

A3

2

A4

Figura 1: Red del día de campo Variables de decisión xij: flujo en la dirección i-j Parámetros uij: capacidad máxima de flujo en la dirección i-j aij: elemento i-j de la matriz de adyacencia de la red Modelo max x I , H +x I , M + x I , Mc +x I ,C s.a. x ij ≤uij , ∀(i , j) F

F

k=I

k =I

∑ a jk x jk – ∑ akj xkj=0, ∀ j≠I , j≠F

3 4

2 C

3 F

3) La compañía aérea Canary se dedica al transporte Vuelos de pasajeros. La compañía divide este transporte en interinsular o peninsular, con aviones o helicópteros, Características V1 V2 V3 V4 V5 V6 y de día o de noche. En un determinado día, la Interinsular × × × compañía quiere cubrir 6 vuelos Vj, j = 1, …, 6, con × × × las características que se indican en la tabla de la Peninsular derecha. Avión × × × × Piloto

Condicionante

Helicóptero

P1

No puede pilotar aviones

De día

P2

Sólo puede realizar el vuelo V3

De noche

P3

Sólo puede realizar los vuelos V1 o V6

P4

No puede realizar vuelo interinsular

P5

Sólo puede volar de día

P6

No puede realizar los vuelos V2, V4 o V5

Variables de decisión xij: 1 si el piloto i se asigna al vuelo j Parámetros Matriz de condicionantes PxV 0 0 1 M= 0 1 1

(

0 0 0 1 0 0

1 1 0 0 0 1

0 0 0 1 1 0

0 0 0 0 1 0

1 0 1 1 1 1

)

Modelo max Z= ∑ ∑ m ij x ij i

j

s.a. 6

∑ xij=1 i=1 6

∑ xij=1 j =1

x ij ∈{0,1}

Resuelto con LINGO SETS: PILOTOS /1..6/; VUELOS /1..6/; PXV(PILOTOS,VUELOS): X, M; ENDSETS DATA: M = 0 0 1 0 0 1 0 0 1 0 0 0

× ×

× ×

×

×

×

×

Las características de cada vuelo restringen los posibles pilotos que pueden cubrirlos. En ese día, los 6 pilotos disponibles Pi, i = 1, …, 6, tienen los condicionantes mostrados en la tabla correspondiente. Determinar, utilizando programación matemática, si la compañía puede realizar los seis vuelos.

1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1; ENDDATA MAX = @SUM(PXV(i,j): M(i,j)*X(i,j)); @FOR(PILOTOS(i): @SUM(VUELOS(j): X(i,j)) = 1; ); @FOR(VUELOS(j): @SUM(PILOTOS(i): X(i,j)) = 1; ); La solución óptima es: x 14 =x 23 =x36 =x42 =x55 =x 61 =1 , con un valor de Z = 5. En forma tabular: V1 V2 V3 V4 V5 V6 P1

×

P2

×

P3 P4 P5

× × ×

P6 × Puede verse que el piloto 1 no puede ser asignado al vuelo 4 (V 4 es un vuelo en avión y P 1 no puede pilotar aviones), sin embargo no hay otra solución mejor que esta. Si se buscara asignar el vuelo 4, por ejemplo, al piloto 4, nadie podría realizar el vuelo 2. De la misma manera, si se asignara el vuelo 4 al piloto 5, el vuelo 5 no podría realizarse. Nadie más que P 4 y P5 pueden pilotar en V4, por lo tanto, Canary no puede realizar los 6 vuelos, pudiendo realizar un máximo de 5.