• Author / Uploaded
• Joaquín Rodrigo

Citation preview

1. Modelos de Transporte, Asignación y Transbordo Tomado de: Anderson/Sweeney/Williams, [1999], Métodos Cuantitativos para los Negocios, capítulo 10, 7ma edición.

Los problemas de transporte, asignación y transbordo corresponden a una clase especial de problemas de programación lineal conocida como problemas de flujo de red. Estos problemas tienen una estructura matemática que ha permitido que los científicos de la administración desarrollen para su solución eficientes procedimientos especializados; como resultado, incluso problemas grandes pueden resolver con apenas unos cuantos segundo de tiempo de computadora.

1.1 Modelo de Transporte EL MODELO DE RED Y UNA FORMULACION DE PROGRAMACION LINEAL El problema de transporte frecuentemente se presenta al planear la distribución de bienes y servicios desde varias localizaciones hacia varas ubicaciones de la demanda. Típicamente, la cantidad de los bienes disponibles en cada localización de suministro (origen) es limitada, y la cantidad de los bienes necesarios en cada una de las localizaciones de demanda (Destino) es conocida. Por lo general, en un problema de transporte, el objetivo es minimizar el costo de embarcar los bienes desde los orígenes hasta los destinos. Ilustremos lo anterior, considerando un problema de transporte al que se enfrenta la corporación XYZ. Este problema involucra el transporte de un producto desde tres plantas hasta cuatro centros de distribución. XYZ tiene plantas en Quito, Lima y Santiago. La capacidad de producción para el siguiente período de tres meses de planeación para un tipo específico de generador es como sigue: Origen 1 2 3

Planta Quito Lima Santiago Total

Capacidad de producción de tres meses (unidades) 5 000 6 000 2 500 13 500

La empresa distribuye sus generadores a través de cuatro regionales de distribución, localizados en Buenos Aires, Río de Janeiro, Bogotá y Caracas; el pronóstico de la demanda de tres meses de los centros de distribución es como sigue: Pronóstico de demanda Destino Mercado a tres meses (unidades) 1 Buenos Aires 6 000 2 Río de Janeiro 4 000 3 Bogotá 2 000 4 Caracas 1 500 Total 13 500 La administración desearía determinar cuánto de su producción deberá embarcarse desde cada una de las plantas hasta cada uno de los centros de distribución. La figura siguiente muestra de manera gráfica las 12 rutas de distribución que XYZ puede utilizar. Esta gráfica se conoce como una red; los círculos son los nodos y las líneas que los conectan, los arcos. Cada origen y destino queda representado por un nodo y cada ruta de embarque posible por un arco. La oferta o suministro se escribe al lado de cada nodo origen y la demanda se escribe al lado de cada nodo destino.

Investigación de Operaciones

2

Representación en Red del problema de transporte de XYZ Los bienes embarcados de los orígenes hacia los destinos representan el flujo en la red. Note que la dirección de flujo (de origen a destino) queda representada por las flechas. Para el problema de transporte de XYZ, el objetivo es determinar las rutas a usar y la cantidad a embarcar en cada una de ellas, y que den el mínimo costo de transporte total. El costo de cada unidad embarcada en cada una de las rutas aparece en la tabla siguiente y se muestra en cada uno de los arcos de la figura anterior. Buenos Aires Quito 3 Lima 7 Santiago 2

Río de Janeiro 2 5 5

Bogotá Caracas 7 6 2 3 4 5

Para resolver este problema de transporte se puede utilizar un modelo de programación lineal. Utilizaremos variables de decisión con dobles subíndices, indicando con X11 el número de unidades que se embarcan del origen 1 (Quito) al destino 1 (Buenos Aires), con X12 el número de unidades embarcadas del origen 1 (Quito) al destino 2 (Río de Janeiro), y así sucesivamente. En general, para un problema de transporte con m orígenes y n destinos, las variables de decisión se escriben como sigue: xij=número de unidades embarcadas del origen i hasta el destino j Donde i = 1,2,…,m y j = 1,2,…,n En vista de que el objetivo del problema de transporte es minimizar el costo total del transporte, podemos utilizar, para desarrollar las siguientes expresiones de costo, los datos de costo de la tabla anterior o que aparecen sobre los arcos de la Red anterior. Costo de transporte para unidades embarcadas desde Quito = 3x11 + 2x12 + 7x13 + 6x14 Costo de transporte para unidades embarcadas desde Lima = 7x21 + 5x22 + 2x23 + 3x24 Costo de transporte para unidades embarcadas desde Santiago = 2x31 + 5x32 + 4x33 + 5x34 La suma de estas expresiones nos da la función objetivo que nos muestra el costo total de transporte de XYZ.

Ing. Efraín Murillo Msc.

Investigación de Operaciones

3

Los problemas de transporte necesitan restricciones, dado que cada uno de los orígenes tiene un suministro limitado y cada destino tiene una demanda específica. Veremos que en primer término las restricciones de suministro. La capacidad de la planta de Quito es de 5 000 unidades. Con el número total de unidades que se embarcan desde la planta de Quito expresado de la forma x 11+x12+x13+x14, la restricción de suministro de la planta de Quito será: x11 + x12 + x13 + x14 ≤ 5000 Suministro de Quito Con tres orígenes (plantas), el problema de transporte de Foster tiene tres restricciones de suministro. Dada la capacidad de 6 000 unidades en la planta de Lima y de 2500 unidades en Santiago, las dos restricciones de suministro adicionales son: x21 + x22 + x23 + x24 ≤ 5 000 Suministro de Lima x31 + x32+ x33 + x34 ≤ 5 000 Suministro de Santiago Con los cuatro centros de distribución como destino se requiere de cuatro restricciones de demanda para asegurar que se satisfarán las demandas en los destinos: x11 + x21 + x31 = 6 000 Demanda de Buenos Aires x12 + x22 + x32 = 4 000 Demanda de Río de Janeiro x13 + x23 + x33 = 2 000 Demanda de Bogotá x14 + x24 + x34 = 1 500 Demanda de Caracas Combinando la función objetivo y las restricciones en un modelo, obtenemos una formulación de programación lineal, con 12 variables y siete restricciones del problema de transporte de XYZ: Min. 3x11 + 2x12+ 7x13 + 6x14 + 7x21 + 5x22 + 2x23 + 3x24 + 2x31 + 5x32 + 4x33 + 5x34 Sujeto a x11 + x12 + x13 + x14 ≤ 5000 x21 + x22 + x23 + x24 ≤ 6000 x31 + x32 + x33 + x34 ≤ 2500 x11 + x21 + x31 = 6000 x12 + x22 + x32 = 4000 x13 + x23 + x33 =2000 x14 + x24 + x34 =1500 xij ≥ 0 para i = 1,2,3 y j = 1,2,3,4 Comparando la formulación de programación lineal con la figura de la Red de este problema nos lleva a varias observaciones. Toda la información necesaria para la formulación de la programación lineal aparece en la red. Cada nodo tiene una restricción y cada arco tiene una variable. La suma de las variables correspondientes a los arcos desde el nodo origen debe ser menor que o igual al suministro de dicho origen, y la suma de las variables que corresponden a los arcos que llegan a un nodo destino debe ser igual a la demanda de dicho destino.

Solución de Lindo 6.0 al problema de transporte de XYZ

Ing. Efraín Murillo Msc.

Investigación de Operaciones

4

Resolvimos el problema de XYZ utilizando el software LINDO 6.0. La solución por computadora mostrada en el cuadro siguiente muestra que el costo total de transporte mínimo es de 39 500 dólares. Los valores de las variables de decisión muestran los valores óptimos a embarcar en cada ruta. Por ejemplo, con x 11 = 3500, deberán embarcarse 3500 unidades de Quito hacia Buenos Aires, y con x 12 = 1500, deberán embarcarse 1500 unidades de Quito a Río de Janeiro. Otros valores de las variables de decisión indican las cantidades y rutas de los embarques restantes La siguiente tabla muestra el programa de transporte de costo mínimo y la figura resume la solución óptima en la red.

Variantes al problema El problema de XYZ ilustra el uso del modelo de trasporte básico. Las variantes al problema de transporte básico pueden implicar una o más de las siguientes situaciones: 1. 2. 3. 4.

Oferta o suministro total no igual a la demanda total Maximización de la función objetivo Rutas con capacidad limitada Rutas no aceptables

Ing. Efraín Murillo Msc.

Investigación de Operaciones

5

Con ligeras modificaciones en el modelo de programación lineal estas situaciones se pueden tomar en cuenta fácilmente.

Suministro total no igual a la demanda total.

A menudo el suministro total no es igual a la demanda total. Si el suministro total es mayor a la demanda total, no es necesaria ninguna modificación a la formulación de la programación lineal. Aparecerá en la solución de la programación lineal un suministro excedente, como una holgura. La holgura correspondiente a cualquier origen en particular se puede interpretar como suministro u oferta sin utilizar, es decir, una cantidad que no se ha embarcado desde el origen. Si el suministro total es inferior a la demanda total, el modelo de programación lineal de un problema de transporte no tendrá una solución factible. En este caso, se intercambia la dirección de las restricciones, así las restricciones de oferta serán del tipo igual y las de demanda del tipo menor o igual. En este caso quedarán destinos no satisfechos en sus requerimientos.

Función objetivo de maximización.

En algunos problemas de transporte, el objetivo es encontrar una solución que maximice la utilidad o los ingresos. Empleando valores de la utilidad o de ingresos unitarios como coeficientes de la función objetivo, simplemente resolvemos un programa lineal de maximización en vez de uno de minimización. Este cambio no afecta a las restricciones.

Rutas con capacidad limitada.

La formulación de programación lineal del problema de transporte también puede tomar en consideración capacidades o cantidades mínimas para una o más de las rutas. Por ejemplo, suponga que en el problema de XYZ, la ruta Santiago-Buenos Aires (del origen 3 al destino 1) tiene una capacidad de 1000 unidades debido a la disponibilidad limitada de espacio en su modo de transporte normal. Siendo x31 las cantidades embarcadas de Santiago hasta Buenos Aires, la restricción por capacidad de la ruta Santiago-Buenos Aires sería: x31 ≤ 1000 De manera similar, se pueden definir montos mínimos de ruta. Por ejemplo x22 ≥ 2000 Garantizaría que un pedido, previamente comprometido, para entregar por lo menos 2000 unidades desde Lima a Río de Janeiro se conservaría dentro de la solución óptima.

Rutas no aceptables. Finalmente, quizás no pueda ser aceptable establecer una ruta desde cualquiera de los orígenes hasta cualquiera de los destinos. A fin de manejar esta situación simplemente hacemos desaparecer el arco correspondiente de la red y eliminamos la variable correspondiente en la formulación de la programación lineal. Por ejemplo, si la ruta Lima-Caracas fuera inaceptable o no utilizable, se eliminaría el arco Lima a Caracas de la red respectiva y x24 podría eliminarse de la formulación de programación lineal. La resolución del modelo resultante, con 11 variables y 7 restricciones, nos daría la solución óptima, garantizando al mismo tiempo que la ruta Lima-Caracas no se utilizaría.

Un Modelo general de programación lineal para el problema de transporte. Para mostrar el modelo general de programación lineal del problema de transporte, utilizamos las siguientes notaciones: i = índice de los orígenes, i=1,2,…,m j = índice para los destinos, j=1,2,…,n xij = número de unidades embarcadas del origen i hasta el destino j cij =Costo unitario de embarcar del origen i al destino j si = Suministro o capacidad en unidades en el origen i dj = Demanda en unidades en el destino j El modelo general de programación lineal para un problema de transporte, con m orígenes y n destinos, es

Ing. Efraín Murillo Msc.

Investigación de Operaciones m

Min i 1

n

c x

ij ij

j 1

n

Sujeto a:

6

x

 si

ij

j 1

m

x

ij

i = 1,2,…,m Suministro

 dj

j = 1,2,…, n Demanda

i 1

x ij  0

para todas las i y j

x  Lij Como se mencionó con anterioridad, podemos agregar restricciones adicionales de la forma ij , si la ruta del origen i al destino j tiene una capacidad Lij. Un problema de transporte que incluya restricciones de este tipo se conoce como un problema de transporte con capacidades. De manera similar, podemos agregar restricciones mínimas de ruta de la forma xij ≥ Mij, si la ruta del origen i al destino j debe manejar por lo menos Mij unidades.

1.2 Modelo de Asignación EL MODELO DE RED Y UNA FORMULACION DE PROGRAMACION LINEAL En una diversidad de situaciones de toma de decisiones se presenta un problema de asignación, los problemas típicos de asignación implican asignar tareas a maquinaria, agentes a trabajos especiales, personal de ventas a territorios, contratos a licitantes y así sucesivamente, Una característica que distingue los problemas de asignaciones que un agente se asigna a una solamente a una tarea. Específicamente, buscamos el conjunto de asignaciones que optimizaran un objetivo dado, como minimizar el costo, minimizar el tiempo o maximizar la utilidad. Para ilustrar el problema de asignación, veamos el caso de ABC, que acaba de recibir solicitudes de estudio de investigación de mercados de tres clientes nuevos. La empresa se enfrenta a la tarea de asignar un líder o jefe de proyecto (agente) a cada cliente (tarea). En este momento, tres individuos no tienen otros compromisos y están disponibles para su asignación como lideres de proyecto. Sin embargo la administración de ABC se da cuenta que el tiempo requerido para terminar cada uno de los estudios dependerá de la experiencia y capacidad del líder de proyecto que se le asigne, los tres proyectos tienen aproximadamente la misma prioridad y la administración desea asignar lideres de proyecto para minimizar el numero total de días necesarios para completar los tres. Si debe asignarse un líder de proyecto a un solo cliente, ¿Qué asignaciones deberán efectuarse? Para responder a esta pregunta la administración de ABC primero deberá considerar todas las posibles asignaciones líder de proyecto-cliente y a continuación estimar los tiempos de terminación del proyecto correspondiente. Con tres lideres de proyecto y tres clientes, son posibles nueve alternativas de asignación. Las alternativas y tiempos de terminación de proyecto estimados en días se resumen en la tabla siguiente: Líder del Proyecto Terry Carlos José

1 10 9 6

Cliente 2 15 18 14

3 9 5 3

La figura siguiente muestra la representación en red del problema de asignación de ABC. Los nodos corresponden a líderes de proyecto y a cliente, y los arcos representan las asignaciones posibles de líder de proyecto a cliente. La oferta en cada uno de los nodos origen, y la demanda, en cada nodo destino, es igual a 1; el costo de asignar un líder de proyecto a un cliente es el tiempo que le tomara a dicho líder terminar la tarea del cliente. Note la similitud entre los modelos de red en un problema de asignación y en un problema de transporte El problema de asignación es un caso especial del problema de transporte, en el que todos los valores de oferta y demanda son iguales a 1, y la cantidad que se embarca en cada uno de los arcos es 0 ó 1.

Ing. Efraín Murillo Msc.

Investigación de Operaciones

7

Modelo de Red del Problema de Asignación de ABC Dado que el problema de asignación es un caso especial del problema de transporte se puede desarrollar una formulación de programación lineal. De nuevo, es necesaria una restricción para cada nodo y una variable para cada arco. Como en el caso del problema de transporte utilizaremos variables de decisión con dobles índices, x11 indicando la asignación del líder de proyecto 1(Terry) al cliente 1, con x12 la asignación del líder de proyecto 1 (Terry) al cliente 2, y así sucesivamente, por lo que definiremos las variables de decisión para el problema de asignación de ABC de la forma: Xij =

1 si el de proyecto i se le asigna al cliente j 0 de no ser ese el caso

Donde i= 1, 2, 3 y j= 1, 2, 3 Utilizando esta notación y los datos de tiempos de terminación de la tabla anterior, desarrollamos las expresiones para el tiempo de terminación. Días requeridos para la asignación de Terry = 10x11+15x12+9x13 Días requeridos para la asignación de Carlos = 9x21+18x22+5x23 Días requeridos para la asignación de José = 6x31+14x32+3x33 La suma de los tiempos de terminación de los tres líderes de proyecto nos dará los días totales necesarios para terminar las tres asignaciones, por lo que la función objetivo es: Min. 10x11+15x12+9x12+9x21+18x22+5x23+6x31+14x32+3x33 Las restricciones para el problema de asignación reflejan la condición de que cada líder de proyecto solo puede ser asignado como máximo a un cliente y que cada cliente solo puede tener como máximo un líder de proyecto asignado. Estas restricciones se escriben como siguen: x11 + x12 + x13 ≤ 1 x21 + x22 + x23 ≤ 1 x31 + x32 + x33 ≤ 1 x11 + x21 + x31 = 1 x12 + x22 + x32 = 1 x13 + x23 + x33 = 1

Asignación de Terry Asignación de Carlos Asignación de José Cliente 1 Cliente 2 Cliente 3

Ing. Efraín Murillo Msc.

Investigación de Operaciones

8

Note que existe una restricción para cada uno de los nodos de la figura de Red del problema. Combinando la función objetivo y las restricciones en un modelo se obtiene el modelo de programación lineal con nueve variables y seis restricciones siguiente: Min. 10x11+15x12+9x12+9x21+18x22+5x23+6x31+14x32+3x33 Sujeto a x11 + x12 + x13

≤1 ≤1 x31 + x32 + x33 ≤ 1 + x31 =1 + x32 =1 + x23 + x33 = 1

x21 + x22 + x23 x11

+ x21 x12

+ x22 x13

xij ≥0 para i =1, 2, 3; j = 1, 2, 3 La tabla siguiente muestra la solución por computadora de este modelo. Terry es asignado al cliente 2 (x12 = 1), Carlos es asignado al cliente 3 (x23 = 1), y José es asignado al cliente 1 (x31=1). El tiempo total de terminación requerido es de 26 días.

Esta solución se resume en la siguiente Tabla:

Variantes del Problema Debido a que el problema de asignación se puede considerar como un caso especial del problema de transporte, las variantes que pueden ocurrir en un problema de asignación son paralelas a las correspondientes en los problemas de transporte. Específicamente, podemos manejar 1. 2. 3.

Numero total de agentes (de suministros) distinto al número total de tareas (demanda). Una función objetivo de maximización Asignaciones no aceptables.

UN MODELO GENERAL DE PROGRAMACION LINEAL PARA EL PROBLEMA DE ASIGNACION El problema general de asignación involucra a m agentes y n tareas. Si hacemos que xij = 1 o 0, dependiendo si el agente i es asignado o no a la tarea j, y si cij indica el costo de asignar el agente i ala tarea j, podemos escribir el modelo general de asignación de la forma

Ing. Efraín Murillo Msc.

Investigación de Operaciones m

Min i 1

9

n

c x

ij ij

j 1

Sujeto a: n

x

 si

ij

j 1

m

x

ij

i = 1,2,…,m Suministro

 dj

j = 1,2,…, n Demanda

i 1

x ij  0

para todas las i y j

Asignaciones Múltiples Al principio de esta sección, indicábamos que una característica distintiva del problema de asignación es que un agente es asignado a una y solo una tarea. En la generalización del problema de asignación, conde un agente puede ser asignado a dos o mas tareas, es posible modificar con facilidad la formulación de programación lineal del problema. Por ejemplo, supongamos que en el problema de ABC, Terry hubiera podido ser asignado hasta a dos clientes; en este caso, la restricción que presenta la asignación de Terry sería x11 + x12 + x13 ≤ 2. En general, si ai indica cual es el limite superior del numero de tareas al que se puede asignar a agente i, podemos escribir las restricciones correspondientes a los agentes de la formula n

x

ij

j 1

 ai i = 1,2,…,m

Por lo que vemos que una ventaja de la formulación y resolución de problemas de asignación en forma de programas lineales es que se pueden manejar con facilidad casos especiales como el de la situación que involucra asignaciones múltiples.

1.3 Modelo de Transbordo EL MODELO DE RED Y LA FORMULACIÓN DE PROGRAMACION LINEAL El problema de transbordo es una extensión al problema de transporte en el cual se agregan nodos intermedios, conocidos como nodos de transbordo para tomar en consideración localizaciones como por ejemplo almacenes. En este tipo más general del problema de distribución, los embarques pueden ser efectuados entre cualquier par de tres tipos generales de nodos: de origen, de transbordo y de destino. Por ejemplo, el problema de transbordo permite embarques de bienes del origen a los nodos de trasbordo y hacia los de destino, de un origen a otro, de una localización de trasbordo a otra, de un destino a otro y directamente desde los orígenes hacia los destinos. Como resulto cierto en el caso del problema de transporte, la oferta o suministro disponible en cada origen es limitada y en cada destino la demanda esta definida o especificada. El objetivo en el problema de transbordo es determinar cuantas unidades deberán embarcarse por cada uno de los arcos de la red, de manera que todas las demandas- destino se satisfagan, al costo de transporte mínimo posible. Veamos el problema de transbordo que encara JR. JR es una empresa electrónica con instalaciones de producción en Denver y en Atlanta. Los componentes producidos en cualquiera de estas instalaciones pueden ser embarcados a cualquiera de los almacenes regionales de la empresa, que están localizados en Kansas City y en Louisville. De los almacenes regionales la empresa suministra a los detallistas al menudeo en Detroit, Miami, Dallas y Nueva Orleáns. Las características clave del problema aparecen en el modelo de red, que se muestra en la figura siguiente:

Ing. Efraín Murillo Msc.

Investigación de Operaciones

10

Representación en Red del problema de transbordo de JR. Note que el suministro en cada origen y la demanda en cada destino aparecen en los márgenes izquierdo y derecho respectivo. Los nodo 1 y 2 son de origen; los nodos 3 y 4 son de transbordo, y los nodos 5, 6, 7, 8 son de destino. En la tabla siguiente aparece el costo unitario de transporte para cada ruta de distribución, así como sobre los arcos del modelo de red en la figura anterior. Costos de transporte unitario para el problema de JR Almacén Planta

Kansas City

Lousville

2 3

3 1

Denver Atlanta

Almacén

Kansas City Louisville

Distribución al detalle Detroit

Miami

Dallas

Nueva Orleans

2 4

6 4

3 6

6 5

Igual que en los problemas de transporte y asignación, podemos formular un modelo de programación lineal del problema de transbordo a partir de la representación en red. De nuevo, necesitaremos una restricción por cada nodo y una variable por cada arco. Supongamos que x ij denota el número de unidades embarcadas del nodo i, hacia el nodo j. Por ejemplo, x13 indica el número de unidades que se embarcan desde la planta de Denver al almacén de Kansas City, x14 el número de unidades embarcadas de la planta de Denver al almacén de Louisville, y así sucesivamente. Dado que el suministro de la planta de Denver es de 600 unidades, las cantidades embarcadas desde la planta de Denver deben ser menor que o igual a 600. Matemáticamente escribimos esta restricción de suministro de la forma X13 + x14 ≤ 600 Similarmente, para la planta de Atlanta tenemos X23 + x24 ≤ 400 Consideremos ahora como expresar las restricciones que corresponden a los dos nodos de trasbordo. Para el nodo 3 (almacén de Kansas City), debemos garantizar que el número de unidades que se embarquen sea igual al número de unidades que se hayan recibido en el almacén. En vista que el: Número de unidades embarcadas hacia fuera del nodo 3 = x35 + x36 + x37 + x38 y Número de unidades embarcadas hacia el nodo 3 = x13 + x23

Ing. Efraín Murillo Msc.

Investigación de Operaciones

11

obtenemos: x35 + x36 + x37 + x38 = x13 + x23 Colocando todas las variables del lado izquierdo obtenemos una restricción, que corresponde al nodo 3, de la forma - x13 - x23 + x35 + x36 + x37 + x38 = 0 De manera similar, la restricción que corresponde al nodo 4 es: - x14 - x24 + x45 + x46 + x47 + x48 = 0 Para desarrollar las restricciones asociadas con los nodos destino, reconocemos que, para cada nodo, la cantidad embarcada al destino debe ser igual a la demanda. Por ejemplo: para satisfacer la demanda de 200 unidades en el nodo 5 (la tienda al detalle de Detroit), escribimos: X35 + x45 = 200 Similarmente, para los nodos 6, 7 y 8 tenemos: X36 + X46 = 150 X37 + X47 = 350 X38 + X48 = 300 Como es normal la función objetivo refleja el costo total de embarque en las 12 rutas de embarque. Combinando la función objetivo y las restricciones nos lleva a un modelo de programación lineal con 12 variables y 8 restricciones del problema de trasbordo de IJK mostrado a continuación:

Para obtener la solución óptima utilizamos el software Lindo 6.0. El cuadro siguiente muestra el resultado:

La tabla siguiente resume la solución óptima.

Ing. Efraín Murillo Msc.

Investigación de Operaciones

12

Tal y como fue mencionado al principio de esta sección, los arcos del problema de trasbordo pueden conectar cualquier par de nodos. En un problema de trasbordo son posibles todos estos patrones de embarque. Sólo seguiremos requiriendo una restricción por nodo, pero la restricción deberá incluir una variable por cada uno de los arcos que entren o salgan del nodo. En los nodos de origen, la suma de los embarques hacia fuera, menos la suma de los embarques hacia adentro, deberá ser menor o igual al suministro en el origen. Por lo que se refiere a los nodos destino, la suma de los embarques de entrada, menos la suma de los embarques de salida deberá ser igual a la demanda. En el caso de los nodos de trasbordo, la suma de los embarques de salida deberá ser igual a la suma de los embarques de entrada, tal u como se dijo antes. Para una ilustración de este problema de trasbordo, de tipo más general, modifiquemos el problema de JR. Suponga que fuera posible embarcar directamente desde Atlanta hasta Nueva Orleáns a 4 dólares por unidad y de Dallas hasta Nueva Orleáns a 1 dólar por unidad. El modelo de red que corresponde a este problema de JR modificado aparece en la figura siguiente:

Representación en Red del problema modificado de transbordo de JR. La formulación de programación lineal en la siguiente figura:

Ing. Efraín Murillo Msc.

Investigación de Operaciones

13

y la solución por computadora en la figura siguiente:

En la figura de la Red del problema modificado de JR agregamos dos nuevos arcos al modelo de red, por lo que son necesarias dos nuevas variables en la formulación de la programación lineal. La figura del modelo de programación lineal muestra las nuevas variables x 28 y x78, pareciendo en la función objetivo y en las restricciones que corresponden a aquellos nodos a los cuales están conectados estos nuevos arcos. La figura anterior muestra el valor de la solución óptima que ha sido reducido en 600 dólares, al agregar las dos rutas de embarque: x28 = 250 unidades, que se están embarcando directamente de Atlanta a Nueva Orleáns, y x 78 = 50 unidades, que se están embarcando directamente desde Dallas a Nueva Orleáns.

Variantes del problema Igual que en los problemas de transporte y de asignación, se pueden formular problemas de trasbordo con varias variables, incluyendo: 1. Suministro total no igual a la demanda total 2. Maximización de la función objetivo 3. Rutas con capacidad limitada 4. Rutas inaceptables Las modificaciones al modelo de programación lineal requeridas para aceptar estas variantes son idénticas a las modificaciones necesarias para el problema del transporte descrito en la sección anterior. Cuando agregamos una o más restricciones de la forma xij ≤ Lij, para mostrar que la ruta del nodo i al nodo j tiene una capacidad Lij, nos referimos al problema de trasbordo como un problema de trasbordo con capacidad limitada.

Un modelo general de programación lineal del problema de transbordo El modelo de programación lineal general del problema de trasbordo es: Min.

c

x

ij ij todos _ los _ ar cos

sujeto _ a :

Ing. Efraín Murillo Msc.

Investigación de Operaciones

14

Donde:

x  x

 s _ Nodos _ de _ origen _ i

ij ij i ar cos_ de _ salida ar cos_ deentrada

x

ij ar cos_ de _ salida



x

ij ar cos_ de entrada

 0 _ Nodos _ de _ transbordo _ i

 x   x  d _ Nodos _ de _ destino _ j

ij ij j ar cos_ de _ entradaa ar cos_ de _ salida

Donde: Xij = número de unidades embarcadas del nodo i al nodo j Cij = costo unitario de embarque del nodo i al nodo j Si = suministro u oferta en el nodo origen i Dj = demanda en el nodo destino j

1.4 Una Aplicación de Producción e Inventarios La introducción a los problemas de transporte y de trasbordo en las secciones anteriores implicaba aplicaciones para el embarque de bienes desde varias localizaciones de suministro, es decir, orígenes, hacia varios sitios de demandas, es decir destinos. Aunque el embarque de bienes es el objeto de muchos problemas de transporte y trasbordo se pueden desarrollar modelos de transportes y/o trasbordo para aplicaciones que no tienen nada que ver con el embarque de trasbordo para resolver un problema de programación de la producción y de inventarios. Ismael es un pequeño fabricante de alfombras para instalación en el hogar y en la oficina. En la tabla siguiente aparecen la capacidad de producción, la demanda y los costos de producción por yarda cuadrada y el costo de posesión del inventario por yarda cuadrada para los siguientes cuatro trimestres. Note que la capacidad reproducción, la demanda y los costos de producción varían cada trimestre, en tanto el costo de posesión del inventario de un trimestre al siguiente es constante en $0.25 por yarda. Ismael desea determinar cuantas yardas de alfombra fabricar cada trimestre, a fin de minimizar el costo total de producción y de inventarios, para el período de cuatro trimestres.

Empezamos desarrollando una representación en red del problema. Primero, creamos cuatro nodos que corresponden a la producción en cada uno de los trimestres y cuatro nodos que corresponden a la demanda de cada trimestre. Cada nodo de producción esta conectado por un arco de salida al nodo de demanda correspondiente del mismo período. El flujo del arco representa las yardas cuadradas de alfombras fabricadas durante el período. Para cada nodo de demanda, un arco de salida representa el inventario (yardas cuadradas de alfombra) que se trasladan hacia el nodo de demanda correspondiente al período siguiente.

Ing. Efraín Murillo Msc.

Investigación de Operaciones

15

Representación en red del problema de Ismael En la red, note que los nodos 1-4 representan la producción correspondiente a cada trimestre y que los nodos 5-8 representan la demanda de cada trimestre. Las capacidades trimestrales de producción aparecen en el margen izquierdo y las demandas trimestrales en el derecho. El objetivo es determinar un programa de producción y una política de inventarios que minimicen el costo total de producción y de inventarios para los cuatro trimestres. Las restricciones implican la capacidad de producción y la demanda de cada trimestre. Como es costumbre, al establecer una restricción para cada nodo y una variable para cada arco se puede desarrollar un modelo de programación lineal a partir de la red. Supongamos que X15 indique el número de yardas cuadradas de alfombra manufacturadas en el trimestre 1. En el trimestre 1, la capacidad de la instalación es de 600 yardas cuadradas, por lo que la restricción por capacidad de producción es X15 ≤ 600 Utilizando variables de decisión similares, obtenemos las capacidades de producción para los trimestres 2 al 4: X26 ≤ 300 X37 ≤ 500 X48 ≤ 400 Ahora veamos el desarrollo de las restricciones para cada uno de los nodos de demanda. Para el nodo 5 entra un arco al nodo, que representa el número de yardas cuadradas de carpeta producidas en el trimestre 4, y sale un arco, que representa el número de yardas cuadradas de alfombra que no serán vendidas en el trimestre 1 y que se trasladarán para su posible venta durante el trimestre 2. En general, para cada trimestre, el inventario inicial, más

Ing. Efraín Murillo Msc.

Investigación de Operaciones

16

la producción, menos el inventario final, deberá ser igual a la demanda. Sin embargo, en el trimestre 1 no hay inventario inicial; por lo que la restricción del nodo 5 es X15 – X56 = 400 Las restricciones asociadas con los nodos de demanda de los trimestres 2, 3 y 4 son X56 + X26 – X67 = 500 X67 + X37 – X78 = 400 X78 + X48 = 400 Note que la restricción del nodo 8 (demanda del cuarto trimestre) sólo involucra dos variables, ya que no hay ninguna provisión de mantener inventarios para un quinto trimestre. El objetivo es minimizar la producción total y el costo del inventario, por lo que escribimos la función objetivo de la forma Mín. 2x15 + 5x26 + 3x37 + 3x48 + 0.25x56 + 0.25x67 + 0.25x78 La formulación completa de la programación lineal del problema de Ismael es:

Utilizamos el Lindo 6.0 para resolver el problema de Ismael. La figura siguiente muestra los resultados: Ismael deberá fabricar 600 yardas cuadradas de alfombra en el trimestre 1, 300 yardas en el trimestre 2,400 yar das en el 3 y 400 yardas en el trimestre 4. Note también que se trasladarán 200 yardas cuadradas del trimestre 1 al trimestre 2. El costo total de producción y de inventarios es de 5,150 dólares.

Ing. Efraín Murillo Msc.

Investigación de Operaciones

17

1.7 Problemas Propuestos 1.

Considere la representación en red siguiente de un problema de transporte: Los suministros, demandas y costos de transporte por unidad aparecen en la red.

a. b. 2.

Desarrolle un modelo de programación lineal para este problema; asegúrese de definir las variables de su modelo. Resuelva el programa lineal para determinar cuál es la solución óptima.

Un producto es manufacturado en tres plantas y embarcado a tres almacenes (los costos de transporte por unidad aparecen en la tabla siguiente). Planta P1 P2 P3 Demanda de cada almacén a. b. c.

3.

W1 20 10 12 200

Almacén W2 16 10 18 400

W3 24 8 10 100

Capacidad de la planta 300 500 100

Muestre una representación en red del problema. Desarrolle un modelo de programación lineal para minimización de costos de transpone: resuelva el modelo para determinar la solución a costo mínimo. Suponga que las entradas en la tabla representan utilidad por unidad producida en la planta i y vendidas al almacén j. ¿Cómo cambia la formulación del modelo, en comparación con el inciso (b)?

Sound Electronics produce una grabadora de cinta operada por baterías en plantas localizadas en Martinsville, Carolina del Norte; Plymouth. Nueva York, y Franklin, Missouri. El costo de transporte uni tario de embarques desde las tres plantas a los centros de distribución en Chicago, Dallas y Nueva York es como sigue:

Después de tomar en consideración los costos de transporte, la administración ha decidido que bajo ninguna circunstancia se utilizará la ruta Plymouth-Dallas. Las capacidades de planta y los pedidos de los distribuidores para el siguiente mes son los siguientes:

Ing. Efraín Murillo Msc.

Investigación de Operaciones

18

Debido a que existen diferentes escalas de salario en las tres plantas, el costo unitario de producción varía de una a otra. Suponiendo que el costo es de 29.50 dólares por unidad en Martinsville, 31.20 dó lares por unidad en Plymouth y 30.35 dólares por unidad en Franklin. Determine un plan de producción y de distribución que minimice los costos de producción y de transporte. 4.

El Ace Manufacturing Company tiene pedidos de tres productos similares: Producto A B C

Pedidos (unidades) 2000 500 1200

Hay disponibles tres máquinas para las operaciones de manufactura; las tres pueden producir todos los productos a la misma velocidad de producción. Sin embargo, debido a distintos porcentajes de defectuosos en cada producto y cada máquina, el costo unitario de los productos varía, dependiendo de la máquina utilizada. La capacidad de máquinas para la semana siguiente, así como los costos unita rios son los siguientes: Capacidad Máquina (unidades) 1 1500 2 1500 3 1000 Máquina 1 2 3

Producto B $1.20 $1.40 $1.00

A $1.00 $1.30 $1.10

C $0.90 $1.20 $1.20

Utilice el modelo de transporte para desarrollar el programa de producción a costo mínimo de pro ductos y máquinas. Muestre la formulación de programación lineal. 5.

En una operación de taller por tarea, se pueden llevar a cabo cuatro tareas en cualquiera de cuatro máquinas. El número de horas requerido para cada tarea en cada una de las máquinas se resume en la ta bla siguiente. ¿Cuál es la asignación tarea-máquina que minimice el tiempo total? Tarea 1 2 3 4

6.

A 32 22 24 26

B 18 24 30 30

Máquina C 32 12 26 28

D 24 15 24 20

HTV utiliza el producto químico RB en sus operaciones de producción en cinco divisiones. Sólo seis proveedores llenan los estándares de control de calidad de HTV para RB. Los seis proveedores pueden producir RB en cantidades suficientes para dar servicio a las necesidades de cada una de las divisiones. Los volúmenes de RB necesarios para cada división de HTV y el precio por galón que carga cada proveedor son como sigue: División 1

Ing. Efraín Murillo Msc.

Demanda Miles de galones 40

Proveedor 1 2 3 4 5 6

Precio por galón($) 12.60 14.00 10.20 14.20 12.00 13.00

Investigación de Operaciones 2 3 4 5

19 45 50 35 45

El costo por galón ($) para embarcar de cada uno de los proveedores a cada una de las divisiones aparece en la siguiente tabla. División 1 2 3 4 5

1 2.75 0.80 4.70 2.40 3.40

Proveedor 3 4 3.15 2.80 5.40 1.20 5.30 2.80 4.40 2.40 5.00 1.20

2 2.50 0.20 2.60 1.80 0.40

5 2.75 3.40 4.00 5.00 2.60

6 2.75 1.00 5.60 2.80 3.60

HTV cree en distribuir sus necesidades entre proveedores, de manera que la empresa resulte menos afectada por sus problemas (por ejemplo, huelgas o disponibilidad de recursos). La política de la empresa requiere que coda una de las divisiones tenga un proveedor distinto. a. b. 7.

Para cada combinación proveedor-división, calcule el costo total de satisfacer la demanda de dicha división. Determine la asignación óptima de proveedores a divisiones.

El sistema de distribución para la empresa HC está formado por tres plantas, dos almacenes y cuatro clientes. La capacidad de las plantas y los costos de embarque (en $) desde cada una de las plantas a cada uno de los almacenes, son

Planta 1 2 3

1 4 8 5

Almacén 2 7 5 i

Capacidad 450 100 380

La demanda de clientes y los costos unitarios de embarque (en $) de cada uno de los almacenes a cada uno de los clientes son: Cliente Almacén 1 2 3 4 1 6 4 8 4 2 3 6 7 7 Demanda 300 300 300 400 a. b. c.

Desarrolle una representación en red para este problema. Formule un modelo de programación lineal del problema. Resuelva el problema lineal para determinar el plan óptimo de embarque.

8.

Refiérase al problema 7. Suponga que están permitidos embarques entre los dos almacenes a 2 dó lares por unidad y que se pueden efectuar embarques directos de la planta 3 al cliente 4 a un costo de 7 dólares por unidad. a. Desarrolle una representación en red de este problema. b. Formule un modelo de programación lineal del problema. c. Resuelva el programa lineal para determinar el plan óptimo de embarque.

9.

Una empresa tiene dos plantas (P1 y P2), un almacén regional (W) y dos tiendas de menudeo (R1 y R2). En la red siguiente aparece la capacidad de las plantas, las demandas de la tienda de menudeo y los costos unitarios de embarque.

Ing. Efraín Murillo Msc.

Investigación de Operaciones

a. b. c.

20

Formule un modelo de programación lineal para minimizar los costos de embarque de este problema. Resuelva el programa lineal para determinar la solución óptima. ¿Qué cambio tendría que efectuarse en el modelo de programación lineal, si el máximo de bienes que se puedan embarcar de W a R1 fuera de 500? ¿Cómo cambiaría lo anterior la solución óptima?

10. Hay cinco trabajadores disponibles para realizar cuatro trabajos. En la Tabla siguiente da el tiempo que tarda cada trabajador para realizar cada trabajo. La meta es asignar los trabajadores a los trabajos de tal manera que se minimice el tiempo total requerido para realizar los cuatro trabajos. Utilice el método Húngaro para resolver el problema.

Trabajador 1 Trabajador 2 Trabajador 3 Trabajador 4 Trabajador 5 11.

Trabajo 1 10 12 12 6 16

TIEMPO (horas) Trabajo Trabajo 2 3 15 10 8 20 9 12 12 15 12 8

Trabajo 1 15 16 18 18 12

Una compañía debe satisfacer las demandas siguientes de un producto: enero, 30 unidades; febrero, 30 unidades; marzo, 20 unidades. Se puede dejar pendiente una demanda a un costo de 5 dólares/unidad/mes. Naturalmente, hay que satisfacer toda la demanda para el fin del mes de marzo. Así, si se satisface 1 unidad de demanda de enero durante el mes de marzo, se incurre en un costo por demanda pendiente de 5(2) = 10 dólares. En la tabla siguiente se muestran: la capacidad de producción mensual y el costo de producción por unidad para cada mes

Enero Febrero Marzo

COSTO CAPACIDAD DE DE PRODUCCIÓN PRODUCCIÓN (dólares) 35 400 30. 420 35 410

Formule un problema de transporte balanceado que se podría utilizar para determinar cómo minimizar el costo total (incluyendo los costos por demandas pendientes, los costos de mantener el inventario y los costos de producción) para satisfacer la demanda.

Ing. Efraín Murillo Msc.

Investigación de Operaciones 12.

21

ABC Cleaning tiene cinco sirvientas para limpiar completamente mi casa, tienen que limpiar con aspiradora, limpiar la cocina, limpiar el cuarto de baño y poner en orden todo. En la tabla siguiente se muestran los tiempos que necesita cada sirvienta para realizar cada trabajo. Se asigna un trabajo a cada sirvienta. Formule un modelo matemático para determinar las asignaciones que minimizan el número total de horas-sirvienta que se requieren para limpiar mi casa.

Sirvienta 1 Sirvienta 2 Sirvienta 3 Sirvienta 4 Sirvienta 5

Ing. Efraín Murillo Msc.

Limpiar con aspiradora 6 9 8 7 5

TIEMPO (h) Limpiar la Limpiar el cocina cuarto de baño 5 2 8 7 5 9 7 8 5 6

Ordenar lodo 1 3 4 3 4