Programación lineal. Redes de transporte

La programación lineal se utiliza en problemas de asignación de recursos limitados que deben repartirse de forma óptima entre las distintas actividades o productos realizados por un sistema para optimizar el objetivo de dichos problemas. La formulación del modelo matemático correcto determina en una gran medida que la solución soporte la toma de decisiones en una base cuantitativa, por lo que el modelo debe abarcar de forma correcta todos los aspectos del problema que sean relevantes.

En esta Unidad revisarás tres tipos de modelos de redes: transporte, asignación y transbordo, los cuales parten de una red que representa un problema.

Dentro del contexto de la IO, una red es un conjunto de elementos de dos tipos: los nodos y arcos. Los primeros pueden denotar almacenes, puntos de demanda, personas, tareas, entre otros. Estos nodos se unen a través de arcos que representan las variables de decisión del problema y que indican con flechas el flujo en la red. Mover cada artículo o recurso por los arcos tiene un costo asociado.

El objetivo de los problemas de redes es determinar la manera óptima de mover o asignar los recursos a través de los distintos nodos que conforman la red, siempre y cuando se respeten las condiciones que la red misma define. Tales restricciones son: el sentido del flujo, la capacidad de los nodos y la capacidad de los arcos.

Redes de transporte

Una red de transporte identifica dos tipos de nodos: nodos de oferta (fuentes u orígenes) y nodos de demanda (destinos), en donde es posible únicamente transportar artículos (productos, personas, energía, etc.) de los nodos de oferta a los nodos de demanda. Es decir, no se pueden mover artículos entre los nodos de oferta o entre los nodos de demanda.

El costo unitario de transportación permanece constante y es proporcional al número de artículos transportados, es decir, mover 10 unidades costará 10 veces que mover sólo 1.

La figura 2 representa la estructura general de un modelo de transporte:

[pic 1]

Aquí, como en todo modelo de PL, se tienen tres elementos que lo conforman.

Función objetivo

Es una función que involucra los costos unitarios de transportación asociados entre cada nodo de oferta y cada nodo de demanda. Se denotan como Cij (desde el nodo i al nodo j). Comúnmente se desea minimizar el costo total de transportación al mover los artículos por la red. Su forma general es:

Min Z = C11X11 + C12X12 +… + CmnXmn para m orígenes y n destinos.

Conjunto de restricciones

Son expresiones que denotan que no se puede exceder la capacidad de oferta para los orígenes o sólo se debe enviar la cantidad que los destinos demandan. Para tal fin se usan los símbolos = (igual), ≤ (menor que) y ≥(mayor que), según corresponda a cada problema. Aquí es importante definir tantas restricciones como nodos se cuenten en la red de transporte. Del lado derecho de las restricciones debe aparecer el número de artículos disponibles por la fuente i y el número de artículos requeridos por el destino j.

Variables de decisión

Son las incógnitas a las que el modelo debe dar respuesta. De manera común se representan con la letra Xij, donde la i indica el nodo origen (desde 1 hasta m) y la j, el nodo destino (desde 1 hasta n). No es obligatorio que se tenga el mismo número de orígenes que de destinos. Con el valor de estas variables se sabrán cuántos artículos deben moverse de la fuente i al destino j.

Redes de transbordo

Una red de transbordo identifica tres tipos de nodos: nodos de oferta, nodos de transbordo y nodos de demanda. En ella es posible asignar flujos de artículos libremente entre los distintos tipos de nodos siempre y cuando se esté habilitado y no se exceda la capacidad de flujo permitida por cada arco de la red. El costo unitario de transbordo permanece constante y es proporcional al número de artículos transportados, es decir, mover 10 unidades costará 10 veces más que mover sólo 1.

...