Investigacin de Operaciones I

Ejemplo Problema de Transbordo

Formulacin Explcita y Formulacin
Compacta

1
Componentes de un Problema de Optimizacin

Decisiones Variables de Decisin

Informacin Parmetros

Condiciones Restricciones

Propsito Funcin Objetivo

2
 Ejemplo
Problema de Transbordo

Thomas Industries (TH) y Washburn Corporation (WH) son dos empresas

dedicadas a la distribucin de muebles para oficina, actualmente estas dos
empresas cuentan con 3 clientes: Zerox (Z), Hewes (H) y Rockwright (R).

Por otra parte, se sabe que ninguna de las dos empresas de distribucin (TH y
WH) fabrican dichos muebles, los fabricantes de estos muebles son Arnold
Manufacturers (AM) y Supershelf Inc (SI)

Se sabe que actualmente la Demanda semanal por parte de sus tres

CLIENTES es la siguiente:
- Zerox 50 unidades.
- Hewes 60 unidades.
- Rockwright 40 unidades.

3
 Ejemplo
Problema de Transbordo

Tambin se sabe que la capacidad de produccin mxima de ambos

FABRICANTES es la siguiente:
- Arnold Manufacturers 75 unidades.
- Supershelf Inc 80 unidades.

Los DISTRIBUIDORES solo juegan el papel de intermediarios para transportar

los muebles de oficina entre los FABRICANTES y los CLIENTES.

Debido a los largos contratos, basados en acuerdos especiales, los costos

unitarios para cada mueble varan dependiendo del distribuidor y del
fabricante, as:
Thomas Washburn
Arnold 5 8
Supershelf 7 4

4
 Ejemplo
Problema de Transbordo

Por otra parte el costo de instalacin que cobran los distribuidores a los
clientes tambin es diferente entre ellos, as:

Zerox Hewes Rockwriht

Thomas 1 5 8
Washburn 3 4 4

Teniendo en cuenta la informacin anterior se debe:

- Construir la red que representa el contexto del problema
- Plantear el problema lineal de forma explcita, asegurndose de definir
todas las variables, las restricciones y la funcin objetivo
- Plantear el problema lineal utilizando formulacin a gran escala (empleando
ndices, sumatorias y para todos), asegurndose de definir variables,
restricciones y funcin objetivo

5
 Ejemplo
Problema de Transbordo - Red

Fabricantes Distribuidores Clientes

Demanda
Capacidad de Costos Costos
Fabricante - Distribuidor Distribuidor - Cliente
Produccin
Zerox 50

5 1
75 Arnold Thomas 5
8 8
Hewes 60
3 4
7
Super Wash
80 Burn
Shelf 4 4
Rock 40
Wright

6
 Ejemplo
Problema de Transbordo Formulacin Explcita

Decisiones Variables de Decisin

Qu debe decidirse?

Cantidad de muebles de oficina a enviar desde cada FABRICANTE a cada

DISTRIBUIDOR.

Cantidad de muebles de oficina a enviar desde cada DISTRIBUIDOR a

cada CLIENTE..

7
 Ejemplo
Problema de Transbordo Formulacin explcita

Decisiones Variables de Decisin

Qu debe decidirse?

x1,1 : Cantidad de muebles a enviar desde Arnold hasta Thomas

x1, 2 : Cantidad de muebles a enviar desde Arnold hasta Washburn
x2,1 : Cantidad de muebles a enviar desde Supershelf hasta Thomas
x2, 2 : Cantidad de muebles a enviar desde Supershelf hasta Washburn
Sub ndice asociado al
fabricante
8
 Ejemplo
Problema de Transbordo Formulacin explcita

Decisiones Variables de Decisin

Qu debe decidirse?

x1,1 : Cantidad de muebles a enviar desde Arnold hasta Thomas

x1, 2 : Cantidad de muebles a enviar desde Arnold hasta Washburn
x2,1 : Cantidad de muebles a enviar desde Supershelf hasta Thomas
x2, 2 : Cantidad de muebles a enviar desde Supershelf hasta Washburn
Sub ndice asociado al
distribuidor
9
 Ejemplo
Problema de Transbordo Formulacin explcita

Decisiones Variables de Decisin

Qu debe decidirse?
y1,1 : Cantidad de muebles a enviar desde Thomas hasta Zerox
y1, 2 : Cantidad de muebles a enviar desde Thomas hasta Hewes
y1,3 : Cantidad de muebles a enviar desde Thomas hasta Rockwright
y2,1 : Cantidad de muebles a enviar desde Washburn hasta Zerox
y2, 2 : Cantidad de muebles a enviar desde Washburn hasta Hewes
y2,3 : Cantidad de muebles a enviar desde Washburn hasta Rockwright
Sub ndice asociado al
distribuidor
10
 Ejemplo
Problema de Transbordo Formulacin explcita

Decisiones Variables de Decisin

Qu debe decidirse?
y1,1 : Cantidad de muebles a enviar desde Thomas hasta Zerox
y1, 2 : Cantidad de muebles a enviar desde Thomas hasta Hewes
y1,3 : Cantidad de muebles a enviar desde Thomas hasta Rockwright
y2,1 : Cantidad de muebles a enviar desde Washburn hasta Zerox
y2, 2 : Cantidad de muebles a enviar desde Washburn hasta Hewes
y2,3 : Cantidad de muebles a enviar desde Washburn hasta Rockwright
Sub ndice asociado al
cliente
11
 Ejemplo
Problema de Transbordo Formulacin explcita

Informacin Parmetros
Qu informacin est disponible para tomar la decisin?
La empresa ha recolectado informacin sobre:
- Costo de enviar un mueble desde cualquier fabricante a
cualquier distribuidor
- Costo de enviar un mueble desde cualquier distribuidor a
cualquier cliente
- Cantidad mxima de muebles que es capaz de producir cada
fabricante
-Demanda estimada por cada uno de los clientes

12
 Ejemplo
Problema de Transbordo Formulacin explcita

Informacin Parmetros
Qu informacin est disponible para tomar la decisin?

c1,1 : Costo de enviar un mueble desde Arnold hasta Thomas

c1, 2 : Costo de enviar un mueble desde Arnold hasta Washburn
c2,1 : Costo de enviar un mueble desde Supershelf hasta Thomas
c2, 2 : Costo de enviar un mueble desde Supershelf hasta Whasburn
Sub ndice asociado al
fabricante
13
 Ejemplo
Problema de Transbordo Formulacin explcita

Informacin Parmetros
Qu informacin est disponible para tomar la decisin?

c1,1 : Costo de enviar un mueble desde Arnold hasta Thomas

c1, 2 : Costo de enviar un mueble desde Arnold hasta Washburn
c2,1 : Costo de enviar un mueble desde Supershelf hasta Thomas
c2, 2 : Costo de enviar un mueble desde Supershelf hasta Whasburn
Sub ndice asociado a
cada distribuidor
14
 Ejemplo
Problema de Transbordo Formulacin explcita

Informacin Parmetros
Qu informacin est disponible para tomar la decisin?
g1,1 : Costo de enviar un mueble desde Thomas hasta Zerox
g1, 2 : Costo de enviar un mueble desde Thomas hasta Hewes
g1,3 : Costo de enviar un mueble desde Thomas hasta Rockwright
g 2,1 : Costo de enviar un mueble desde Supershelf hasta Thomas
g 2, 2 : Costo de enviar un mueble desde Supershelf hasta Hewes
g 2, 2 : Costo de enviar un mueble desde Supershelf hasta Rockwright
Sub ndice asociado a
cada distribuidor 15
 Ejemplo
Problema de Transbordo Formulacin explcita

Informacin Parmetros
Qu informacin est disponible para tomar la decisin?
g1,1 : Costo de enviar un mueble desde Thomas hasta Zerox
g1, 2 : Costo de enviar un mueble desde Thomas hasta Hewes
g1,3 : Costo de enviar un mueble desde Thomas hasta Rockwright
g 2,1 : Costo de enviar un mueble desde Supershelf hasta Thomas
g 2, 2 : Costo de enviar un mueble desde Supershelf hasta Hewes
g 2, 2 : Costo de enviar un mueble desde Supershelf hasta Rockwright
Sub ndice asociado a
cada cliente 16
 Ejemplo
Problema de Transbordo Formulacin explcita

Informacin Parmetros
Qu informacin est disponible para tomar la decisin?

u1 : Capacidad de produccin de Arnold

u2 : Capacidad de produccin de Supershelf
d1 : Demanda de muebles por parte de Zerox
d 2 : Demanda de muebles por parte de Hewes
d 3 : Demanda de muebles por parte de Rockwright

17
 Ejemplo
Problema de Transbordo Formulacin explcita

Condiciones Restricciones
Qu limita la decisin?
La empresa debe cumplir con las siguientes condiciones:
- Lo que enve desde cada fabricante a cada distribuidor no podr
ser mayor a lo que son capaces de producir
- La cantidad enviada desde los fabricantes a los distribuidores y
desde stos a los clientes debe estar balanceada (lo que sale
debe ser menor o igual a lo que entra)
-Lo que se enve desde los distribuidores a los clientes debe ser
suficiente para cubrir la demanda
-No se pueden producir ni enviar cantidades negativas de
muebles de oficina
18
 Ejemplo
Problema de Transbordo Formulacin explcita

Condiciones Restricciones
Qu limita la decisin?
Restriccin 1: Lo que enve desde cada fabricante a cada
distribuidor no podr ser mayor a lo que son capaces de producir

Arnold: x1,1 x1, 2 u1

Supershelf: x2,1 x2, 2 u2

Cmo se pueden escribir estas restricciones de una manera ms compacta?

19
 Ejemplo
Problema de Transbordo Formulacin Compacta

Condiciones Restricciones
Restriccin 1: Lo que enve desde cada fabricante (i) a cada
distribuidor (j) no podr ser mayor a lo que son capaces de
producir 2

Sumatoria sobre x
j 1
1, j u1 Contraccin horizontal
los fabricantes de la restriccin
2

x
j 1
2, j u2

20
 Ejemplo
Problema de Transbordo Formulacin Compacta

Condiciones Restricciones
Restriccin 1: Lo que enve desde cada fabricante (i) a cada
distribuidor (j) no podr ser mayor a lo que son capaces de
producir
2

x i, j uj i 1,2
j 1

Contraccin vertical de
la restriccin Para todos los
fabricantes

21
 Ejemplo
Problema de Transbordo Formulacin explcita

Condiciones Restricciones
Qu limita la decisin?
-Restriccin 2: La cantidad enviada desde los fabricantes a los distribuidores y
desde estos a los clientes debe estar balanceada (lo que sale debe ser menor
o igual a lo que entra)
Lo que se enva de todos los fabricantes a Thomas es igual a lo que Thomas
enva a todos los clientes x1,1 x2,1 y1,1 y1, 2 y1,3
Lo que se enva de todos los fabricantes a Washburn es igual a lo que
Washburn enva a todos los clientes
x1, 2 x2, 2 y2,1 y2, 2 y2,3
Cmo se pueden escribir estas restricciones de una manera ms compacta?
22
 Ejemplo
Problema de Transbordo Formulacin Compacta

Condiciones Restricciones
-Restriccin 2: La cantidad enviada desde los fabricantes a los distribuidores y
desde estos a los clientes debe estar balanceada (lo que sale debe ser menor
o igual a lo que entra)

Sumatoria sobre Sumatoria sobre

2 3
los fabricantes
x y
los clientes
i ,1 1, k
i 1 k 1
2 3

x
i 1
i,2 y2,k
k 1

23
 Ejemplo
Problema de Transbordo Formulacin Compacta

Condiciones Restricciones
-Restriccin 2: La cantidad enviada desde los fabricantes a los distribuidores y
desde estos a los clientes debe estar balanceada (lo que sale debe ser menor
o igual a lo que entra)
2 3

x i, j y j ,k j 1,2
i 1 k 1

Para todos los

distribuidores

24
 Ejemplo
Problema de Transbordo Formulacin Explcita

Condiciones Restricciones
Qu limita la decisin?
-Restriccin 3: Lo que se enve desde los distribuidores a los clientes debe ser
suficiente para cubrir la demanda
y1,1 y2,1 d1
y1, 2 y2, 2 d 2
y1,3 y2,3 d 3
Cmo se pueden escribir estas restricciones de una manera ms compacta?

25
 Ejemplo
Problema de Transbordo Formulacin Compacta

Condiciones Restricciones
-Restriccin 3: Lo que se enve desde los distribuidores a los clientes debe ser
suficiente para cubrir la demanda
2
Sumatoria sobre y
j 1
j ,1 d1
los distribuidores
2

y
j 1
j,2 d2

y
j 1
j ,3 d3

26
 Ejemplo
Problema de Transbordo Formulacin Compacta

Condiciones Restricciones
-Restriccin 3: Lo que se enve desde los distribuidores a los clientes debe ser
suficiente para cubrir la demanda
2

y j ,k d k k 1,2,3
j 1

Para todos los clientes

27
 Ejemplo
Problema de Transbordo Formulacin Compacta

Condiciones Restricciones
Restriccin 4: No se pueden producir ni enviar cantidades negativas de
muebles

xi , j 0 i 1,2; j 1,2
y j ,k 0 j 1,2; k 1,2,3

28
 Ejemplo
Problema de Transbordo Formulacin Explicita

Propsito Funcin Objetivo

Cmo cuantificar el impacto de una decisin?

Costo de enviar Costo de instalar

min (fabricante distribuidor) + (distribuidor cliente)

29
 Ejemplo
Problema de Transbordo Formulacin Explicita

Propsito Funcin Objetivo

Cmo cuantificar el impacto de una decisin?

min Z 5 x1,1 8 x1, 2 7 x2,1 4 x2, 2 1 y1,1 5 y1, 2 8 y1,3 3 y2,1 4 y2, 2 4 y2,3

Costo de envo Costo de instalacin

Fabricante - Distribuidor Distribuidor- Cliente

30
 Ejemplo
Problema de Transbordo Formulacin Compacta

Propsito Funcin Objetivo

Cmo cuantificar el impacto de una decisin?

2 2 2 3
min Z ci , j xi , j g j ,k y j ,k
i 1 j 1 j 1 k 1

31
 Ejemplo
Problema de Transbordo Formulacin Explicita y Compacta

min Z 5 x1,1 8 x1, 2 7 x2,1 4 x2, 2 2 2 2 3

min Z ci , j xi , j g i , j y j ,k
1x1,1 5 x1, 2 8 x1,3 3 x2,1 4 x2, 2 4 x2,3 i 1 j 1 j 1 k 1
s.a s.a
x1,1 x1, 2 u1 2

x uj i 1,2
x2,1 x2, 2 u2 j 1
i, j

x1,1 x2,1 y1,1 y1, 2 y1,3 2 3

x1, 2 x2, 2 y2,1 y2, 2 y2,3 x i, j y j ,k j 1,2

i 1 k 1
y1,1 y2,1 d1 2

y1, 2 y2, 2 d 2 y j ,k d k k 1,2,3

j 1
y1,3 y2,3 d 3
xi , j 0 i 1,2; j 1,2
x1,1 , x1, 2 , x2,1 , x2, 2 0
y j ,k 0 j 1,2; k 1,2,3
y1,1 , y1, 2 , y1,3 , y2,1 , y2, 2 , y2,3 0

32