1. Ciencia

ASIGNATURA
PROGRAMACIÓN LINEAL
El Problema del Transporte
Maestro
Ing. Julio Rito Vargas Avilés
Octubre 2014
1
Problema de Transporte
Es un caso especial de problema
de programación lineal (PPL), para
el cual se ha desarrollado una
versión
distinta
del método
Simplex.
2
Principales características
Suponga que se dispone de n fábricas y de m centros de
consumo, ambos localizados en distintos puntos. Cada fábrica i
posee una capacidad de producción Oi, y cada centro de consumo
j posee una demanda Dj. El costo de producir una unidad en la
fábrica i es de CPi, y el costo de transportar cada unidad desde la
fábrica i al centro de consumo j es de CTij.
El problema es determinar la cantidad a producir en cada fábrica
y las cantidades a transportar, al mínimo costo. Luego xij es la
cantidad a producir en la fábrica i para ser llevado al centro de
consumo j.
3
Red de distribución
Fábrica
RAAN
Centro de consumo
RAAS
4
RED DE TRANSPORTE
5
D1
D2
D3
D4
F1
10
F2
12
F3
F4
25
D5
13
D6
D7
600
15
350
20
150
OF
12
15
DEM 500 300 200 200
D8
400
17
900
15
18
650
150
600
6
7
Modelo
de Programación Lineal
Se utilizará el siguiente modelo de programación
lineal (PPL)
n
m
  (CP  x
MIN costo =
s.a.
n
x
i 1
ij
m
i 1
 Dj
 x ij  Oi
j1
xij  0
j1
i
ij
 CTij  x ij )
Se satisface toda la
Demanda
No se puede producir más allá de
la capacidad de la fábrica.
con i:1.. n y j:1..m
8
Modelo
de Programación Lineal
m
D
Suponiendo que:
j1
j

n
O
i 1
i
Cap. de Producción
igual a la Demanda.
y reemplazando Cij=CPi+CTij queda el siguiente modelo:
n
m
 C
MIN costo =
s.a.
i 1
n
x
ij
 Dj
x
ij
 Oi
i 1
m
j1
xij  0
j1
ij
 x ij
con i:1.. n y j:1..m
9
Modelo
de Programación Lineal
m
Si
D
j1
j

n
O
i 1
i
Cap. de Prod. mayor a la
demanda.
entonces se genera un nuevo centro de consumo ficticio.
Lo que consuma ese centro no es real, por tanto queda
como capacidad de producción ociosa.
n
m
i 1
j1
D F   Oi   D j
10
Modelo
de Programación Lineal
m
Si
D
j1
j

n
O
i 1
i
Cap. de Producción
menor a la Demanda.
entonces se genera una nueva fábrica ficticia. Lo que
produzca esa fábrica no es real. Por tanto queda como
demanda insatisfecha. m
n
O F   D j   Oi
j1
i 1
11
Modelo
de Programación Lineal
Ejemplo: Suponga que se dispone de 3 bodegas con capacidades de 15,000,
25,000 y 5,000 unidades. Por otra parte, se tienen 4 centros de
consumo con demandas de 5000, 15,000, 15,000, y 10,000
unidades respectivamente. Encuentre las cantidades óptimas a
producir y transportar, tal de minimizar los costos que se muestran
a continuación:
B1
B2
B3
Dem
C1
C2
C3
C4
10
0
20
11
12
7
9
20
0
4
16
18
5000 15000 15000 10000
Bodega
15000
25000
5000
12
C1
10 X11
B1
12 X21
B2
B3
0 X31
Demanda
5000
C2
0 X12
7 X22
4 X32
15000
C3
20 X13
9 X23
16 X33
15000
C4
11 X14
20 X24
18 X34
10000
Bodega
15000
25000
5000
13
𝑀𝑖𝑛 𝑧 = 10𝑋11 + 0𝑋12 + 20𝑋13 + 11𝑋14 +12𝑋21 + 7𝑋22 + 9𝑋23 + 20𝑋24 +
0𝑋31 + 4𝑋32 + 16𝑋33 + 18𝑋34
Sujeto a:
Ecuaciones de Oferta:
Ecuaciones de Demanda:
𝑋11 + 𝑋12 + 𝑋13 + 𝑋14 =15,000
Bodega 1
𝑋21 + 𝑋22 + 𝑋23 + 𝑋24 = 25,000
Bodega 2
𝑋31 + 𝑋32 + 𝑋33 + 𝑋34 = 5,000
Bodega 3
𝑋11 + 𝑋21 + 𝑋31 =5,000
𝑋12 + 𝑋22 + 𝑋32 =15,000
𝑋13 + 𝑋23 + 𝑋33 =15,000
𝑋14 + 𝑋24 + 𝑋34 =10,000
𝑋𝑖𝑗 ≥0
i=1..3;
j=1..4
14
Solución usando Módulo de PL de POM-QM
Variable
X11
X12
X13
X14
X21
X22
X23
X24
X31
X32
X33
X34
Optimal Value (Z)
Value
0
5000
0
10000
0
10000
15000
0
5000
0
0
0
315,000
15
Usando Módulo de Transporte POM-QM
16
Solución factible inicial
Al igual que en el método Simplex tradicional, el problema de
transporte requiere partir de una solución inicial factible. Para ello
se necesita asignar las cantidades xij de manera de cumplir con las
restricciones. Para ello existen al menos 4 posibilidades:
•
•
•
•
Método de la esquina Noroeste.
Método de Vogel.
MODELO DE COSTO MÍNIMO
Método Simplex –Programación Lineal
17
Método de la esquina Noroeste
Este método no considera los costos, por eso puede que su solución
quede alejada del óptimo. Consiste en asignar la máxima cantidad
factible al casillero superior izquierdo que no posea ninguna asignación
o marca. La cantidad a asignar es el mínimo entre la oferta disponible
y la demanda en dicho momento.
Hecha la asignación, se descuenta la cantidad tanto a la oferta como a
la demanda. Con esto, una de las dos quedará en cero (fila o
columna). Por tanto se marcan todos los casilleros vacíos de ella.
18
Método de la esquina Noroeste
Ejemplo:
C1
B1
B2
B3
D
C2
10
5000
C3
0
10000
12
-
C4
0
11
20
-
-
7
5000
20
9
15000
4
O
5000
18
16
-
-
-
5000
5000
15000
15000
10000
15000
25000
5000
C=410
19
Método de la esquina Noroeste
En caso de que al realizar una asignación simultáneamente ambas se
hagan cero (fila y columna), entonces se asigna una nueva variable con
valor cero en el casillero de la fila o columna que tenga un menor
costo. Se producen entonces 2 asignaciones: Una con el valor mínimo y
la otra con cero. Esto se debe a que el sistema debe tener n+m-1
variables básicas definidas.
Esto se muestra en el siguiente ejemplo:
20
Método de la esquina Noroeste
1
Ejemplo 2:
1
2
3
4
5
D
2
7
15
3
20
10
-
-
20
12
10
15
3
12
15
10
-
-
10
2
7
8
9
8
0
12
O
0
0
20
-
5
12
11
5
-
-
-
-
13
15
8
4
15
20
20
10
10
10
25
11
-
-
-
15
10
15
20
30
15
10
C=950
21
Método de Aproximación a Vogel
Este método si considera los costos, por tanto entrega una mejor
solución factible inicial que la esquina noroeste. El método consiste en la
realización de un algoritmo que consta de 3 pasos fundamentales y 1
más que asegura el ciclo hasta la culminación del método.
PASO 1
Determinar para cada fila y columna una medida de penalización
restando los dos costos menores en filas y columnas.
PASO 2
Escoger la fila o columna con la mayor penalización, es decir que de la
resta realizada en el "Paso 1" se debe escoger el número mayor. En caso
de haber empate, se debe escoger arbitrariamente (a juicio personal).
22
Método Aproximación a Vogel
PASO 3
De la fila o columna de mayor penalización determinada en el paso anterior
debemos de escoger la celda con el menor costo, y en esta asignar la mayor
cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda
quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo
se tachará 1, la restante quedará con oferta o demanda igual a cero (0).
PASO 4: DE CICLO Y EXCEPCIONES
- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda,
detenerse.
- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine
las variables básicas en la fila o columna con el método de costos mínimos,
detenerse.
- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda,
determine las variables básicas cero por el método del costo mínimo, detenerse.
- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las
23
ofertas y las demandas se hayan agotado.
Ejemplo: Método de Aproximación a Vogel
EL PROBLEMA
Una empresa energética colombiana dispone de cuatro
plantas de generación para satisfacer la demanda diaria
eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y
Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30,
60 y 45 millones de KW al día respectivamente. Las
necesidades de las ciudades de Cali, Bogotá, Medellín y
Barranquilla son de 70, 40, 70 y 35 millones de Kw al día
respectivamente.
24
Los costos asociados al envío de suministro energético
por cada millón de KW entre cada planta y cada ciudad
son
los
registrados
en
la
siguiente
tabla.

Formule un modelo de programación lineal que permita satisfacer las
necesidades de todas las ciudades al tiempo que minimice los costos
asociados al transporte.
25
SOLUCIÓN PASO A PASO
Paso 1: determinar las medidas de penalización y consignarlas en la tabla
de costos, tal como se muestra a continuación.
26
Paso 2: escoger la fila o columna con la mayor
penalización:
Paso 3: escoger de esta columna el menor valor, y se le asigna la mayor cantidad
posible de unidades, podemos observar como el menor costo es "2" y que a esa
celda se le pueden asignar como máximo 60 unidades "que es la capacidad de la
27
planta 3".
Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60
unidades) esta debe desaparecer.
Se ha llegado al final del ciclo, por ende se repite el proceso
28
Iniciamos una nueva iteración:
29
30
Iniciamos una nueva iteración
31
Iniciamos una nueva iteración
32
Iniciamos una nueva iteración
6
33
Al finalizar esta iteración podemos observar como la tabla queda una fila sin
tachar y con valores positivos, por ende asignamos las variables básicas y
hemos concluido el método.
34
35
Los costos asociados a la distribución son:
Costo = 5*25 + 2*40
+ 7*10 + 3*5 + 1*30
+ 2*60 + 4*45 =125
+ 80 + 70 + 15 + 30
+ 120 + 180 = $620
36