Modelo de transporte

El modelo de transporte es una clase especial de programación lineal que tiene que ver con transportar un artículo
desde sus fuentes (es decir, fábricas) hasta sus destinos (es decir, bodegas).
El objetivo es determinar el programa de transporte que minimice el costo total del transporte y que al mismo tiempo
satisfaga los límites de la oferta y la demanda. En el modelo se supone que el costo de transporte es proporcional a la
cantidad de unidades transportadas en determinada ruta.

Modelo básico

El objetivo del modelo es determinar las incógnitas 𝑥𝑖𝑗 que minimicen el costo total de transporte, y que al mismo
tiempo satisfagan las restricciones de oferta y demanda.

 Hay m fuentes y n destinos  La cantidad ofertada en la fuente i es ai

 Cij es el costo del transporte por unidad
 La cantidad demandada en el destino j es bj
 Xij es la cantidad transportada

Supuestos:

1. Se desea distribuir un solo producto.

2. Cada origen tiene un conjunto de unidades a distribuir y cada destino requiere una cierta cantidad de unidades.
La cantidad total de unidades a distribuir que ofrecen los orígenes es igual a las cantidades totales de unidades
que requieren los destinos.

3. Es posible transportar entre todos los orígenes y todos los destinos pero debe incurrirse en un costo unitario.
Este costo es el costo de transportar una unidad entre el origen i y el destino j.
4. Además por fila y columna de la matriz debe cumplirse que:

Ej:

Función objetivo [Z] es la que queremos maximizar 

Matriz de costos

D1 D2 D3 # ai = Oi bj = Dj
01 C11 C12 C13
O2 C21 C22 C33
O3 C31 C32 C33
O4 C41 C42 C43

Matriz de cantidad a transportar

D1 D2 D3 # Siempre entro por la oferta, y salgo por la demanda para averiguar los X.
01 X11 X12 X13
O2 X21 X22 X33 # Se cumple en todas que ∑ X i1 = D1
O3 X31 X32 X33
O4 X41 X42 X43

Ejemplo práctico de Aplicación

Una empresa energética dispone de tres plantas de generación para satisfacer la demanda eléctrica de cuatro ciudades.
Las plantas 1, 2 y 3 pueden satisfacer 30, 50 y 45 millones de [kWh] respectivamente. El valor máximo de consumo ocurre
a las 2 PM y es de 35, 20, 40 y 30 millones de [kWh] en las ciudades 1, 2, 3 y 4 respectivamente. El costo de enviar 1 [kWh]
depende de la distancia que deba recorrer la energía. La siguiente tabla muestra los costos de envío unitario desde cada
planta a cada ciudad. Formule un modelo de programación lineal que permita minimizar los costos de satisfacción de la
demanda máxima en todas las ciudades.

Halle el programa óptimo de distribución y su costo asociado.

Metodología de resolución
Paso 0 - Lo primero que tenemos que observar es si existe un equilibrio entre la oferta y la demanda.

Como existe un equilibrio, podemos continuar con la resolución del problema sin la necesidad de realizar ninguna
actividad adicional. En caso contrario, debemos agregar una demanda ficticia, con costos de transporte mayores al más
alto de los de la matriz actual.

Paso 1 - Definir cuál es la problemática que necesitamos solucionar.

Normalmente nuestro principal problema es lograr una distribución al costo más bajo.
Paso 2 - Definir el/los método/s a utilizar

Es común la utilización de más de un método en simultáneo para poder obtener distintas alternativas y corroborar los
resultados obtenidos.
Los métodos que desarrollaremos son:
 Método del Noroeste
o Sencillo y fácil de hacer
o No tiene en cuenta los costos para hacer las asignaciones
o Generalmente nos deja lejos del óptimo
 Costos Mínimos
o Es más elaborado que el método de la esquina noroeste
o Tiene en cuenta los costos para hacer las asignaciones
o Generalmente nos deja próximo del óptimo
 Método de Aproximación de Vogel
o Es más elaborado que los anteriores y más técnico.
o Tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones.
o Generalmente nos deja cerca al óptimo.
En nuestro caso particular hemos decidido operar con el Método de Costos Mínimos.

Método de costes mínimos

Construir la tabla de disponibilidades, requerimientos y costos

1. Seleccionar la celda que tenga el menor costo de toda la tabla.

Si nos encontráramos con que más de una celda tienen los menores costos, elegimos la celda a la que se le
pueda asignar la mayor cantidad de recursos posibles.
2. Le asignamos lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos).

3. Rellenar con ceros (0) la fila o columna satisfecha

Actualizar la disponibilidad y el requerimiento, restándoles lo asignado.
 4. Continuar seleccionando la celda que tenga el costo mínimo de la tabla resultante (Sin tener en cuenta la
fila o columna satisfecha), y asignamos el mayor valor que nos sea posible asignar.
Volver a repetir los pasos hasta completar con todas las distribuciones requeridas.

Tener cuidado:

Al efectuar esta distribución, estamos eliminando la posibilidad de distribuir energía eléctrica desde la planta 1 hacia la
cuidad 3 el cual tiene un costo menor (10) a la que estamos asignando al distribuir Energía de esta planta hacia la ciudad
1 (12). A su vez, estamos reduciendo la cantidad a distribuir de energía de la planta 2 a la ciudad 1 el cual también posee
un costo más bajo (9) con respecto a la distribución que podríamos realizar si continuamos con esta decisión (12).
Por lo tanto es lógico pensar que podríamos realizar algunos cambios en nuestra distribución por costos mínimos, por
ejemplo:
Continúo con la distribución:

5. Calculo los costos totales:

Costo total = 20.(9) + 15.(11) + 20.(6) + 10.(10) + 30.(8) + 30.(5) = 955

Ejercicio 2 (de carpeta):

Tiene 2 partes:

 Costos mínimos
 Reajuste de costes mínimos

Suponga que Brasil, Argentina y Uruguay producen todo el trigo, cebada y avena en el mundo. La demanda mundial de
trigo requiere que se dediquen 125 millones de acres a la producción de este cereal. De igual manera, se necesitan 60
millones de acres para cebada y 70 millones de acres para avena. La cantidad total de tierra disponible en Brasil, Argentina
y Uruguay es 80, 110 y 70 millones de acres. El número de horas de mano de obra necesarias para producir un acre de
trigo en los respectivos países es 18, 13 y 16 horas. La producción de un acre de cebada requiere 15, 12 y 12 horas de
mano de obra y la producción de un acre de avena requiere 12, 10 y 16 horas de mano de obra en Brasil, Argentina y
Uruguay. El costo de mano de obra por hora en cada país es $9, $7 y $10 para la producción de trigo, $8, $9 y $8,50 para
la de cebada y $7, $8 y $6,50 para la de avena. El problema es asignar la tierra de cada país de manera que se cumpla con
los requerimientos de alimentación en el mundo y se minimice el costo total de mano de obra.

a) Formule este problema como un problema de transporte construyendo la tabla de parámetros apropiada.

b) Obtenga una solución óptima para este problema.

C11 = 18 hs * $9 = 162 Hago lo mismo con los demás.

Construimos la Matriz de Costos indicando las capacidades de Oferta de cada país y las demandas de cada producto:

Paso 0 - Lo primero que tenemos que observar es si existe un equilibrio entre la oferta y la demanda.

Hay que agregar una Demanda 4 (ficticia) que vamos a llamar Df4 .

Los costos de la distribución y transporte de productos desde cualquier Origen hacia este Destino deben ser mayores al
más alto de la matriz actual (por ej. 200) de manera que sean las últimas unidades en ser asignadas:

Paso 1 - Definir cuál es la problemática que necesitamos solucionar.

Asignar la tierra de cada país de manera que se cumpla con los requerimientos de alimentación en el mundo y se
minimice el costo total de mano de obra.

Paso 2 - Definir el/los método/s a utilizar

Utilizamos el Método de los Costos Mínimos:

 1. Seleccionar la celda que tenga el menor costo de toda la tabla.
Si nos encontráramos con que más de una celda tienen los menores costos, elegimos la celda a la que se le
pueda asignar la mayor cantidad de recursos posibles.

2. Le asignamos lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos).

Por lo tanto distribuyo a D3 las 70 unidades que demanda y que provienen de O2, quedándole 110 - 70 = 40 a O2 para
ofrecer.

3. Rellenar con ceros (0) la fila o columna satisfecha

Actualizar la disponibilidad y el requerimiento, restándoles lo asignado.

Como ese destino ya está totalmente cubierto tachamos todas las celdas porque sus costos ya no nos interesan.

La matriz con las cantidades a distribuir va quedando de la siguiente forma:

4. Continuar seleccionando la celda que tenga el costo mínimo de la tabla resultante (Sin tener en cuenta la
fila o columna satisfecha), y asignamos el mayor valor que nos sea posible asignar.
Volver a repetir los pasos hasta completar con todas las distribuciones requeridas.

Buscamos el siguiente mínimo costo: 91 → como O2 sólo puede ofrecer 40 unidades y la demanda es de 125,
satisfacemos esa cantidad pero quedan pendientes 125 - 40 = 85 unidades para distribuirle a D1. Por otro lado, O2 ya no
puede ofrecer más unidades con los cual tachamos esa fila:
Ahora empezamos a repetir el proceso de buscar el mínimo costo de lo que van quedando y asignar las unidades a
distribuir posible:

Voy al siguiente:

Otro más:
Importante:

 Comprobamos que las últimas 5 unidades sobrantes se distribuirán al destino ficticio.

 Verificamos que se satisfagan todas las demandas (sumatoria de columnas) y que se puedan proveer desde todos
los orígenes (sumatoria de filas).

5. Calculamos los costos totales

PARTE 2: Se puede realizar un reajuste de costos mínimos, para obtener un costo total aún más bajo.

Mirar el apunte PDF en caso de estar interesado, pero es muy complicado.

Debemos agregar una demanda ficticia, con costos de transporte mayores al más alto de los de la matriz costo actual.

Los costos de la distribución y transporte de productos desde cualquier Origen hacia este Destino ficticio deben ser
mayores al más alto de la matriz actual de manera que sean las últimas unidades en ser asignadas.
 Modelo de asignación
“La mejor persona para el puesto” es una buena descripción del modelo de asignación. El caso se puede ilustrar con la
asignación de trabajadores de diversos niveles de capacitación a los puestos. Un puesto que coincide con los
conocimientos de un trabajador cuesta menos que uno en que el trabajador no es tan hábil. El objetivo del modelo es
determinar la asignación óptima (de costo mínimo) de trabajadores a puestos.

El elemento 𝑐𝑖𝑗 representa el costo de asignar al trabajador i al puesto j (i, j = 1, 2,..., n).

El modelo de asignación es en realidad un caso especial del modelo de transporte, en el cual los trabajadores representan
las fuentes y los puestos representan los destinos. La cantidad de oferta en cada fuente, y la cantidad de demanda en cada
destino son exactamente iguales a 1. El costo de “transportar” el trabajador i al puesto j es 𝑐𝑖𝑗. De hecho, se puede resolver
el modelo de asignación en forma directa como modelo normal de transporte. Sin embargo, el hecho de que todas las
ofertas y las demandas son iguales a 1, condujo al desarrollo de un algoritmo sencillo de solución llamado método
húngaro. Aunque parezca que el nuevo método es totalmente ajeno al modelo de transporte, en realidad el algoritmo
tiene su raíz en el método símplex, igual que el modelo de transporte.

La asignación de personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los asignados no
tienen que ser personas. También, pueden ser máquinas, vehículos, plantas a los que se asignan tareas.

Importante: la matriz debe ser cuadrada siempre. Sino, se deben agregar filas o columnas ficticias para obtener esta
condición.

Condiciones:

Supuestos:

1. El número de asignados es igual al número de tareas (este número se denota por n).
2. Cada asignado se asigna a una tarea.
𝑥𝑖𝑗 = 1, si el asignado i realiza la asignación j 𝑥𝑖𝑗 = 0, en caso contrario,
3. Cada tarea debe realizarla exactamente un asignado.
4. Existe un costo 𝑐𝑖𝑗 asociado con el asignado i (i =1,2..., n) que realiza la tarea j (j=1,2...n).
5. El objetivo es determinar cómo deben hacerse las “n” asignaciones para minimizar los costos totales.
Método húngaro

Ejemplo 1 de aplicación:

Se trata de asignar cuatro personas a la realización de cuatro tareas diferentes. La puntuación relativa de cada persona a
cada tarea se podría determinar mediante puntuaciones de prueba, intentos u opiniones subjetivas. Esas puntuaciones
se disponen en forma de matriz como la que se muestra a continuación:

1. Obtener los costos de oportunidad para cada fila y columna, mediante la resta en filas y columnas.
Esto se hace restando el número más pequeño que aparezca en cada renglón, a los restantes valores del renglón
respectivo.

Observemos que en cada renglón aparece un cero. Los otros valores distintos de cero son los costos de oportunidad que
resultarían al no asignar la persona con la mejor puntuación al puesto más adecuado. Después de cada operación
efectuada en la matriz, hay que verificar si se ha logrado la solución óptima. Cuando hay un solo cero en cada fila y
columna, se tiene la mejor combinación posible.
 2. Como en la matriz que realizamos no hay ceros en las columnas de las tareas 2 y 4, se debe continuar aplicando
el método una vez más por lo menos.
La resta en columnas se hace en forma similar. El valor más bajo que aparezca en cada columna de la matriz,
(resultante de las diferencias en las filas), se resta de todos los demás valores de la columna.

Las columnas 1 y 3 no han variado, ya que contenían ceros. Los ceros revelan ahora los costos de oportunidad de las
interacciones empleado-puesto.

3. Se hará una nueva verificación de la solución óptima.

A primera vista parece que podría haber un cero para cada combinación empleado puesto, pero una inspección más
rigurosa indica que el empleado 2 tiene tres de los costos cero de oportunidad disponibles. Por lo tanto se requiere otra
operación en la matriz:

Paso 1: Cruzar todos los ceros que hay en la matriz resultante del paso anterior con el menor número posible de líneas
rectas horizontales o verticales. Si el número de líneas es igual al número de renglones (o columnas), se ha obtenido ya
una solución en el paso anterior.

Como podemos observar, el problema tiene tres líneas para cruzar todos los ceros. Como hay cuatro renglones quiere
decir que no se ha obtenido una solución y se confirman las conclusiones obtenidas al inspeccionar en forma
independiente los ceros. Esta verificación de la optimización es la primera finalidad de las líneas.

Tendré que entonces ir al paso 2.

Paso 2: modificar la matriz. El procedimiento consiste en elegir el número más pequeño no cruzado por las líneas que se
trazaron. Ese número se suma a todos los valores que se encuentran en las intersecciones de las líneas y se resta de
todos los numero no cruzados.
En este caso, el número más pequeño no cruzado es el 1, en las celdas del empleado 1, puesto 4; y del empleado 3
puesto 2.
Se suma al valor de cada celda en la intersección de líneas:
 Empleado 2, puesto 1: 0 + 1 = 1
 Empleado 2, puesto 3: 4 + 1 = 5
Luego se resta el 1 de las celdas no cruzadas y obtenemos la siguiente matriz

Paso 3: la matriz se somete nuevamente al trazado de líneas que crucen los ceros.

En este caso vemos que no hay manera de cruzar todos los ceros con menos de cuatro líneas rectas, por lo tanto se ha
encontrado la solución.
Las asignaciones específicas se identifican localizando cualquier cero que aparezca solo en una fila o columna.
El único cero de la columna 1 está en la fila 1. Por lo tanto el empleado 1 se asigna al puesto 1.

Nos queda ahora una matriz de 3 x 3: la fila 1 y la columna 1 fueron tomados ya por la primera asignación.
En la fila 4, la única asignación posible es el empleado 4 al puesto 3.

Las dos asignaciones restantes son el empleado 2 al puesto 4, y el empleado 3 al puesto 2.

Las combinaciones y las puntuaciones son las siguientes:
Combinación empleado-puesto: E1 a P1, E2 a P4, E3 a P2, E4 a P3
Puntuación empleado-puesto: 2 - 3 - 3 - 1 (mirar tabla inicial)
Ejemplo 2 (de carpeta):

Preg de parcial:
Debo agregar una columna ficticia, porque la matriz no es
cuadrada.

Restar el número más pequeño que aparezca en cada renglón.

(11 , 13 y 5)

Restar el más pequeño en cada columna. (en todas hay 0, así

que queda igual)

Cuando hay un solo cero en cada fila y columna, se tiene la mejor combinación posible (como en este caso).

Cruzar todos los ceros que hay en la matriz resultante del paso
anterior con el menor número posible de líneas rectas
horizontales o verticales. Si el número de líneas es igual al
número de renglones (o columnas), se ha obtenido ya una
solución en el paso anterior (como en este caso).

Para hacer menos cantidad de pasos, primero identificamos

los ceros esenciales absolutos: aquellos en los que no hay
otros 0 en la misma fila y en la misma columna; si no hay
buscamos los ceros esenciales por fila (o por columna, es indistinto): aquellos en los que no hay otros 0 en la misma fila
pero sí en la misma columna, con lo cual tachamos el/los excedente/s de la columna. En este caso no hay cero esencial
absoluto, entonces buscamos uno por fila o columna.

Para ello, localizo cualquier cero que aparezca solo en una fila o
columna.
M1 – L4

Nos queda ahora una matriz de 3 x 3: la fila 1 y la columna 4

fueron tomados ya por la primera asignación.

En la fila 2, la única asignación posible es la localidad 3.

M2 – L3
Y finalmente: M3 – L1
Los costos son:

Z = 11 + 13 + 5 = $ 29 costo mínimo total.