problemas de transporte

PROBLEMA DE TRANSPORTE
EJEMPLO

PROBLEMA DE TRANSPORTE
La compañía azucarera DIAMANTE tiene dos
ingenios localizados en Córdoba, Ver. y Ciudad
Valles, SLP. La compañía surte el azúcar que
requiere una compañía productora de refrescos con
plantas en Río Blanco, Ver., San Luis Potosí, SLP y
Tehuacán, Pue. La compañía Diamante produce 5 y
8 toneladas de azúcar por semana en los ingeniosde
Córdoba y Ciudad Valles, respectivamente, mientras
que las embotelladoras requieren de 3, 5 y 4
toneladas de azúcar por semana en Río Blanco, San
Luis Potosí, y Tehuacán, respectivamente.

PROBLEMA DE TRANSPORTE
El azúcar puede ser enviada de cualquier ingenio a
cualquier embotelladora, pero el costo de transporte
difiere según la trayectoria. Los costos cij de enviar
una tonelada deazúcar del ingenio i a la
embotelladora j se muestran en la matriz (c ) siguiente:
ij

 2 6 3
(cij ) = 
5 3 7




donde
i = 1, 2 corresponde a Córdoba y Ciudad Valles,
respectivamente, y
j = 1, 2, 3 corresponde a Río Blanco, San Luis Potosí
y Tehuacán, respectivamente.

PROBLEMA DE TRANSPORTE
Se desea determinar la manera de transportar el
azúcar de los ingenios a lasembotelladoras que
tenga un mínimo costo.
1

3

2

5

3

4

2
5

6

1
3
5

8

3

2
7

PROBLEMA DE TRANSPORTE
a. Definir las variables de decisión.
Sea xij la cantidad en toneladas de
azúcar a enviar por semana del
ingenio i a la embotelladora j,
i = 1, 2; j = 1, 2, 3.

PROBLEMA DE TRANSPORTE
b. Establecer la función objetivo.

min Z = 2 x11 + 6 x12 + 3 x13+ 5 x21 + 3 x22 + 7 x23

PROBLEMA DE TRANSPORTE
c. Identificar las restricciones.
Restricciones de límite en la capacidad de
producción de los ingenios

x11 + x12 + x13 ≤ 5

x21 + x22 + x23 ≤ 8

PROBLEMA DE TRANSPORTE
c. Identificar las restricciones.
Restricciones de demanda de las embotelladoras

x11 + x21 ≥ 3
x12 + x22 ≥ 5
x13 + x23 ≥ 4

PROBLEMA DE TRANSPORTE
c.Identificar las restricciones.
Restricciones de no negatividad

xij ≥ 0 , i = 1, 2,

j = 1, 2, 3

PROBLEMA DE TRANSPORTE
d. Presentar el programa lineal.
min Z = 2 x11 + 6 x12 + 3 x13 + 5 x21 + 3 x22 + 7 x23
s. a
x11 + x12 +

≤5

x13
x21 +

x11 +

x22 +

≥3

x21
x12 +

x22
x13 +

x23 ≤ 8
≥5
x23 ≥ 4
xij ≥ 0, i = 1, 2, j = 1, 2, 3

PROBLEMA DE TRANSPORTE
GENERALIZACIÓNPROBLEMA DE TRANSPORTE
Generalización:
En una instancia del problema de
transporte se tiene:
Un producto a transportar entre m
fuentes y n destinos, para los cuales se
conoce:

PROBLEMA DE TRANSPORTE
Datos (variables no controlables)
Sea

ai la oferta del producto en la fuente i, i = 1,2,…,m
b j la demanda del producto en el destino j, j = 1,2,…,n

cij el costo de transportaruna unidad del producto de
la fuente i al destino j; i = 1,2,…,m, j = 1,2,…,n

PROBLEMA DE TRANSPORTE
y se definen las variables de decisión siguientes:
Sea

xij la cantidad de producto a enviar de la fuente i al
destino j; i = 1, 2, …, n, j = 1,2,…,n

PROBLEMA DE TRANSPORTE
Programa lineal asociado:
m

n

min z = ∑∑ cij xij
i =1 j =1

s. a
n

∑x
j =1

ij

m

∑x
i =1ij

≤ ai , i = 1, 2, , m
≥ bj ,

j = 1, 2, , n

xij ≥ 0 , i = 1, 2, , m, j = 1, 2, , n

PROBLEMA DE ASIGNACIÓN
EJEMPLO

PROBLEMA DE ASIGNACIÓN
Cuatro trabajos deben realizarse
simultáneamente y se dispone de
cuatro máquinas diferentes para ello, en
las cuales es posible realizar cualquiera
de los trabajos, pero con diferente
costo.

PROBLEMA DE ASIGNACIÓN
Los costoscij de realizar el trabajo i en la
máquina j, para cada pareja (i,j);
i,j = 1,2,…,m, se muestran en la matriz
(cij ) siguiente:
3

4
(cij ) = 
5

6


4
6
3
7

2
3
3
4

7

8
9

6


PROBLEMA DE ASIGNACIÓN
Se desea determinar la asignación de los trabajos a
las máquinas que permita realizar los trabajos con el
menor costo posible.

PROBLEMA DE...