Investigacion de operaciones

Universidad Nacional Mayor de San Marcos
Facultad de Ingeniería de Sistemas e Informática
Investigación Operativa I

Problema
de
Transporte
p

Docente : Lic. Gabriel Solari Carbajal

Problema de Transporte
En este problema se estudia el envío de productos
desde p
puntos de origen
g hacia p
puntos de destino.
El problema esta sujeto a la oferta de los puntos de
origen, la demandade los puntos de destino y los
costos de transporte.

2

1

Problema de Transporte
Puntos de
origen

Unidades
de
oferta

o1

1

o2

Puntos de
destino

c11

1

d1

2

2

d2

om m

n

dn

Unidades
de
demanda

3

Problema de Transporte
Problema balanceado.Un problema esta balanceado cuando se cumple:

∑o = ∑d
m

n

i

i =1

j

j =1

encaso contrario se dice que esta desbalanceado,
algunos autores mencionan desequilibrado.
Objetivo del Problema de Transporte.El objetivo de este problema es determinar el mínimo
costo para satisfacer la demanda con la oferta
disponible.
4

2

Problema de Transporte
Planteando el problema como un P.P.L. (problema
balanceado).)
Variables de decisión.-

x ij :

Cantidad de productosque se envían del origen i
al destino j

cij :

Costo de enviar una unidad del producto del
origen
g i al destino j

5

Problema de Transporte

O
Origenes

Destinos
1

2

3

j

1

c 11

c12

c 13

c 1j

c 1 n-1 c1n

o1

2

c 21

c22

c 23

c 2j

c 2 n-1 c2n

o2

3

c 31

c32

c 33

c 3j

c 3 n-1 c3n

o3

i

ci1

c i2

ci3c ijj

c i n-1

oi

m-1 c m-1 1 cm-1 2 c m-1 3
m

n-1

n

cin

c m-1 j

cm-1 n-1 c m-1 n

om-1
om

cm1

cm2

c m3

cmj

c m n-1 c mn

d1

d2

d3

dj

dn-1

dn

6

3

Problema de Transporte

O
Origenes

Destinos
1

2

3

j

1

x11

x12

x13

x1j

x1 n-1 x1n

o1

2

x21

x22

x23

x2j

x2 n-1 x2n

o2

3x31

x32

x33

x3j

x3 n-1 x3n

o3

i

xi1

xi2

xi3

xijj

xi n-1

oi

m-1 xm-1 1 xm-1 2 xm-1 3
m

n-1

n

xin

xm-1 j

xm-1 n-1 xm-1 n

om-1
om

xm1

xm2

xm3

xmj

xm n-1 xmn

d1

d2

d3

dj

dn-1

dn

7

Problema de Transporte
Restricciones.P ofertas
Por
f
(
(equilibrio
ilib i de
d las
l salidas)
lid )

x 11 + x 12 + L+ x 1n = o1

(lo que sale del origen 1)

x 21 + x 22 + L + x 2n = o 2

(lo que sale del origen 2)

M
x m1 + x m2 + L + x mn = o m

(lo que sale del origen m)

8

4

Problema de Transporte
Por demandas (equilibrio de las llegadas)

x 11 + x 21 + L + x m1 = d1

(lo que llega al destino 1)

x 12 + x 22 + L + x m2 = d 2

(lo que llega al destino 2)

M
x 1n + x 2n + L + xmn = d n

(lo que llega al destino n)

Por no negatividad

x ij ≥ 0

i = 1, 2, K, m
j = 1, 2, K, n

9

Problema de Transporte
Función Objetivo.Mi i i
Minimizar
ell costo de
d envío
í

Min Z = c11x 11 + c12 x 12 + L + c ij x ij + L + c mn x mn

10

5

Problema de Transporte
El modelo queda:

Mi Z = c11x 11 + c12 x 12 + L + c ij x ij + L + c mn x mn
Min
Sujeto a:
Poroferta

Por demanda

x 11 + x 12 + L + x 1n = o1
x 21 + x 22 + L + x 2n = o 2
M
x m1 + x m2 + L + x mn = o m

x 11 + x 21 + L + x m1 = d1
x 12 + x 22 + L + x m2 = d 2
M
x 1n + x 2n + L + x mn = d n

x ij ≥ 0

i = 1, 2, K, m
j = 1, 2, K, n

11

Problema de Transporte
Como cada variable se encuentra dos (2) veces en el
sistema de ecuaciones, entonces se tiene m+n-1 g
gradosde libertad y el número de variables básicas debe ser
igual al número de grados de libertad del sistema.
SOLUCION BÁSICA FACTIBLE NO DEGENERADA.Es una solución factible con exactamente m+n–1
variables no nulas en la base.
SO UCION BÁSICA FACTIBLE
SOLUCION
FACTIB E DEGENERADA.DEGENERADA
Es una solución factible con menos de m+n–1 variables
no nulas en la base.
12

6

Problema de...