Optimización

Transporte Y Asignación

ING 3105

Docente : José Agüero G



Problema de Transporte Balanceado
◦ Introducción
◦ Modelamiento
◦ Solución Básica Inicial

 Método de la esquina noroeste
 Método de costo Mínimo

◦ Método del Ciclo

 Prueba de Optimalidad
 iteración



Problema de Asignación
◦ Método Hungaro





Existen dos tipos particularmente importantes deP.P.L.; los
problemas de transporte y los problemas de asignación. El primero
trata de determinar la manera óptima de transportar bienes (entre
otras cosas); y el segundo incluye aplicaciones como la asignación
de personas a tareas.
Las aplicaciones de los problemas de transporte y asignación
tienden a requerir un número muy grande de restricciones y
variables por lo que el método Simplexpuede necesitar mucho
esfuerzo.





Por fortuna, una característica clave de estos problemas es que la
mayor parte de los coeficientes de las restricciones son igual a cero.
Como resultado, se han desarrollado algoritmos simplificados
especiales que ahorran mucho tiempo.
Para describir las estructuras especiales se introducirá la tabla o
matriz de coeficientes.

Uno de losproductos más importantes de la P&T Company es el
chícharo enlatado. Se preparan en 3 enlatadoras y se envían por
camión a 4 almacenes de distribución. La administración ha iniciado
un estudio para reducir los costos de embarque. Se ha estimado la
producción de cada enlatadora durante la próxima temporada y se
ha asignado a cada almacén cierta cantidad de la producción.


Hay un total de 300cargas de camión que se deben transportar. El
problema es determinar el plan de asignación de estos embarques a
las distintas combinaciones de enlatadora-almacén que minimice el
costo total de transporte.

Enlatadora
Asignación

1
2
3

1
464
352
995
80

Costo de embarque por carga
Almacén
2
3
513
654
416
690
682
388
65
70

Producción
4
867
791
685
85

75
125100
300/300

������������ ���� = 464����11 + 513����12 + 654����13 + 867����14 + 352����21 + 416����22 + 690����23 + 791����24
+ 995����31 + 682����32 + 388����33 + 685����34
S/a: ( Oferta ; Demanda )
(1) ����11 + ����12 + ����13 + ����14
(2)
(3)

(4) ����11
(5)
(6)
(7)

����12

����13

����21 + ����22 + ����23 + ����24

+ ����21
����14

+ ����22

+ ����23

+ ����24����31 + ����32 + ����33 + ����34

+ ����31

+ ����32

������������ ≥ 0 (���� = ��,�� ; ���� = ��,��)
13
14

+ ����33

+ ����34

= 75

= 125
= 100
= 80

= 65

= 70

= 85



En particular, el problema general de transporte se refiere a la
distribución de cualquier mercancía desde cualquier grupo de
centros de suministro llamados orígenes a cualquier grupo decentros de recepción, llamados destinos de tal manera que se
minimicen los costos totales de distribución.
Ejemplo Prototipo

Problema General

Cargas de camión de chícharos
3 enlatadoras
4 almacenes
Producción de enlatadora i
Asignación de almacén j
Costo de envío por carga de
enlatadora i al almacén j

Unidades de un bien
m orígenes
n destinos
 recursos (oferta) en origen iDemanda del destino j
Costo por unidad distribuida
desde origen i al destino j





Supuesto de requerimientos
Cada origen tiene un suministro fijo de unidades el cual debe
distribuirse completo entre los destinos. De manera similar el
destino tiene una demanda fija de unidades y debe satisfacerse por
los orígenes. El supuesto de que no hay margen en las cantidades
que debenenviarse o recibirse significa que es necesario un balance
entre el suministro total de todos los orígenes y la demanda total de
todos los destinos.





Un problema de transporte tiene soluciones factibles si y sólo si:

En algunos problemas, los suministros y demandas son cantidades
máximas que deben enviarse y/o recibirse. Estos problemas violan
el supuesto de requerimientos por...