Metodo STL

Problema de Asignación

De los problemas de localización de múltiples instalaciones el más sencillo es el que recibe el nombre de problema de Asignación o de Afectación. Se trata de determinar la localización de m instalaciones indivisibles que se relacionaran con p instalaciones existentes pero no se relacionaran entre si y que pueden ubicarse en algún emplazamiento de los n disponibles; se conoce o puede calcularse la distancia, d (k,j), entre cada instalación existente k y cada emplazamiento j y, por otra parte, se conoce el coste por unidad de distancia, w(i,k), entre la nueva instalación i y la ya existente k; cada emplazamiento puede albergar solo una instalación, por lo cual si el número de nuevas instalaciones es igual al de emplazamientos disponibles (m=n) la solución consiste en asignar a cada emplazamiento una instalación y solo una misma (si m>n el problema no admite solución y si m<n se añade a la lista de nuevas instalaciones n-m instalaciones ficticias –con w(i,k) = 0 ∀ k – con lo que se asimila al caso m=n).

Este problema de localización múltiple es, pues un caso particular del problema que consiste en, dados dos conjuntos de objetos con el mismo número de elementos, formar parejas que consten de un elemento del primer conjunto y otro del segundo de modo que la asignación tenga valor máximo o mínimo (dado un valor para cada pareja posible). Toda la información necesaria para resolverlo se puede resumir en una matriz m x n tal y como la que se presenta en la figura 23.

El problema se puede plantear como un programa lineal en variables binarias (como se puede ver en la figura 24). El valor 1 de una variable x(i,j) está asociado al hecho de situar la instalación l(i) en el emplazamiento E(j); la variable tiene valor 0 en caso contrario. Se trata de hacer mínima la suma de costes respetando las condiciones de que cada emplazamiento acoge una instalación y sólo una (primer grupo de restricciones) y de que cada instalación se sitúa en un emplazamiento y sólo uno (segundo grupo de restricciones). Aunque las variables son binarias, el problema se puede resolver con algoritmos habitualmente utilizados para resolver programas lineales con variables continuas, ya que su peculiar estructura garantiza el carácter entero de la solución óptima obtenida. El problema de asignación es también un caso particular del problema del transporte y se puede resolver mediante cualquier algoritmo adecuado para dicho problema, pero además admite algoritmos específicos, como el denominado algoritmo húngaro. La figura 25 muestra la solución óptima del ejemplo de la figura 23.

Problema de asignación generalizado

Hasta aquí se ha prescindido de las dimensiones de los emplazamientos y de las instalaciones; cada emplazamiento ha sido tratado como un punto que podría ser ocupado únicamente por una instalación.

Considérese ahora que los recursos a localizar (lo que hasta aquí se ha venido denominado habitualmente instalaciones) son m artículos y que se trata de determinar cuáles de las n parcelas en que se considera dividido el almacén conviene asignar a cada artículo, sabiendo que el articulo i necesita A(i) parcelas y que hay p muelles de carga y descarga (que juegan aquí el papel desempeñado hasta ahora por lo que se ha denominado instalaciones existentes) y conociendo asimismo las distancias, d(k,j), desde casa muelle k a cada parcela j y los costes por unidad de distancia del transporte, a través de k, del articulo i. En el supuesto de que los movimientos de un artículo se reparten por igual entre las A (i) parcelas que tiene asignas, el coste, c (i, j) de asignar la parcela j al artículo i es:

c (i,j) = 1/(A(i)) ■(p@Σ@k=1) w (i,k) d(k,j)

y el problema se pude formular como un programa lineal, tal como se puede ver en la figura 26.

Para dicha formulación se ha hecho el supuesto (que se mantiene en lo sucesivo) de que el número de parcelas requeridas para los artículos es igual al de parcelas disponibles (si es menor, basta definir un articulo ficticio que requiera tantas parcelas como sean necesarias para establecer la igualdad). Las variables del programa lineal están asociadas al hecho de asignar o no el emplazamiento j al recurso i y el modelo expresa que se desea minimizar el coste respetando las condiciones de que a cada recurso se le debe asignar exactamente A (i) emplazamientos (primer grupo de restricciones) y de que a cada emplazamiento se le debe asignar un recurso y sólo uno. Se trata de un caso particular del denominado problema del transporte; su estructura peculiar garantiza, si las A (i) son enteras, que la solución obtenida mediante un algoritmo de la familia del simplex es entera; puede resolverse también mediante cualquiera de los algoritmos específicos que existen para dicho problema del transporte.

En cualquier caso, y salvo para problemas de muy reducidas dimensiones, la resolución de problemas de este tipo requiere el uso de ordenadores, salvo en algunos casos particulares en que cabe aplicar algoritmos mucho más sencillos.

Localización de un solo articulo

Este caso es prácticamente trivial. Cada parcela puede ser o no asignada al artículo. El coste de asignar la parcela j es (basta con suprimir el subíndice i en la expresión que define c (i,j), más arriba):

c (j) = 1/A = ■(p@Σ@k=1) w(k) d(k,j)

y evidentemente la solución óptima consiste en localizar el artículo en las A primeras parcelas según el orden creciente de las c (j). Puede verse un ejemplo en la figura 27.

En ella se indica la posición de las puertas de entrada y salida (E y S, respectivamente), así como los valores de la distancia rectangular del centro de cada parcela a dichas puertas (el valor de la parte superior izquierda corresponde a la distancia S y el de la parte superior derecha a la distancia a E); se ha calculado también los promedios de estos dos valores (en régimen permanente, el promedio de las entradas es igual al promedio de salidas), que figuran en la parte inferior del cuadrado correspondiente a cada parcela. Las parcelas asignan según el orden creciente de estos últimos valores.

A = 29 parcelas

...