UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

1

“ EL PROBLEMA DE TRANSPORTE” La TÉCNICA DE TRANSPORTE se puede aplicar a todo problema físico compatible con el siguiente esquema:

FUENTES

DESTINOS

TRANSPORTE DE UNIDADES Donde “transporte de unidades” puede ser, por ejemplo: • flujo de energía • transporte de mercaderías • prestaciones de servicios • transporte de materia prima • etc. OBJETIVO: Minimizar los costos de “transporte” desde las fuentes a los destinos. DEFINICIÓN DEL MODELO: Suponemos: • m fuentes i • n destinos j • a i ( i = 1,..., m) n° de unidades disponibles en la fuente i • bj (j = 1, ...,n) n° de unidades demandadas por el destino j. • c i j costo de transporte de una unidad desde la fuente i al destino j • x i j n° de unidades transportadas desde las fuente i al destino j. REPRESENTACIÓN MATEMÁTICA:

MIN Z =

Σ Σ c ij

x ij

Sujeto a:

Σ x ij = a i Σ x ij = b j x i j >= 0

i = 1,..., m ( restricciones de disponibilidad)

j = 1,..., n ( restricciones de demanda) ∀i ;

∀ j

Las etapas básicas para resolver un Problema de Transporte son:

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

2

Etapa 1: Balancear el problema Etapa 2: Encontrar una solución básica factible inicial Etapa 3: Optimización Etapa 1: Para que un problema esté balanceado el n° de unidades disponibles debe ser igual al n° de unidades requeridas. Cuando la condición de balance no se cumple naturalmente, se utilizarán fuentes o destinos ficticios para balancear el problema y poder aplicar la Técnica de Transporte.
Si la demanda excede el suministro, se utilizará una fuente ficticia que suministra la cantidad faltante.
Si la disponibilidad excede la demanda se utilizará un destino ficticio que consuma la cantidad sobrante. Los costos utilizados en las fuentes o destinos ficticios deben ser todos iguales, convenimos en que sean cero. Etapa 2: Encontrar una solución básica factible inicial (S.B.F.I.) Hay varios Métodos para encontrar una solución inicial. Aquí veremos dos de ellos:  El Método del Extremo Noroeste (Regla del Noroeste)  El Método del Mínimo Costo Utilizaremos la siguiente matriz de costos para desarrollar ambos Métodos: O1 O2 O3 O4 requerim.

D1 8 5 9 4 70

D2 5 7 3 8 130

D3 2 4 6 2 140

D4 7 5 4 5 150

D5 3 8 2 1 150

D6 9 6 7 9 190

Disponib. 100 250 300 180 830

Regla del Noroeste El algoritmo es el siguiente:  Asignar la mayor cantidad posible a la variable x 11 

La columna (fila) satisfecha es tachada, indicando que las restantes variables de esa columna (fila) no son básicas

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

3



Continuar asignando la mayor cantidad posible a la próxima variable de la columna o fila no tachada



El algoritmo finaliza cuando queda solo sin tachar una fila o una columna que es la que recibe la cantidad restante



Una vez realizada la asignación, corroborar que la cantidad de asignaciones sea igual a m + n – 1 .

En nuestro ejemplo la S.B.F.I. por Noroeste es: (tabla 1) O1 O2 O3 O4 requerim.

D1 70 70

D2 30 100 130

D3 140 140

D4 10 140 150

D5 150 150

D6 10 180 190

Disponib. 100 250 300 180 830

Z = 70 x 8 + 30 x 5 + 100 x 7 + 140 x 4 + 10 x 5 + 140 + 4 + 150 x 2 + 10 x 7 + 180 x 9 = $ 4570

Método del Mínimo Costo El algoritmo es el siguiente:  Asignar la mayor cantidad posible a la variable que posee el menor costo unitario, en caso de existir más de una elegir arbitrariamente. 

La columna o fila satisfecha se tacha.



Continuar asignando la mayor cantidad posible a la variable no tachada con menor costo unitario



El algoritmo finaliza cuando sólo queda sin tachar una fila o una columna que recibe lo que quedó sin asignar aún.



Una vez realizada la asignación, corroborar que la cantidad de asignaciones sea igual a m + n – 1 .

En nuestro ejemplo la S.B.F.I. por Mínimo Costo es: (tabla 2) O1 O2 O3 O4 requerim.

D1 70 70

D2 130 130

D3 100 10 30 140

D4 150 150

D5 150 150

D6 170 20 190

Disponib. 100 250 300 180 830

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

4

Z = $ 2950 Etapa 3: Optimización Para optimizar utilizaremos el Método iterativo MODI. Método MODI Trabajaremos con una matriz de costos indirectos. Los costos indirectos cumplen la condición: que se pueden descomponer en un valor u i correspondiente a fila y otra v j correspondiente a columnas. (C i j = u i + vj ). ¿ Cómo lo aplicamos en el Método MODI? Luego de obtener una S.B.F.I. construimos una nueva matriz en la cuál ubicamos los valores de la matriz inicial de costos en aquellos lugares donde aparecen las soluciones (asignaciones de valores) correspondientes a la 1era. Solución (utilizaré la solución encontrada por Mínimo Costo); luego fijamos un valor marginal ( ui o vj) y automáticamente quedarán fijados todos los restantes. En nuestro ejemplo: (tabla 3) D1 O1 3 O2 5 O3 6 O4 3 vj 2

D2 0 2 3 0 -1

D3 2 4 5 2 1

D4 1 3 4 1 0

D5 1 3 4 1 0

D6 4 6 7 4 3

ui 1 3 4 1

Luego de construir esta tabla hacemos la diferencia entre ella y la tabla de costos iniciales,; esta diferencia puede ser mayor, menor o igual a cero. Si la diferencia es negativa colocamos el signo _ en la tabla de costos indirectos, si es positiva colocamos el signo + y el resultado de la operación y si es cero colocamos 0. Las diferencias con signo + son las que nos interesan, ya que nos indican que podemos mejorar la solución anterior introduciendo en ese lugar una nueva solución, en nuestro ejemplo la introducimos en el casillero (3, 5), indicamos esto colocando en la tabla 2 un ; luego construimos un circuito cerrado que tome a lo largo de filas y columnas otros elementos (asignaciones distintas de cero). Los circuitos pueden ser únicos o no, se elige cualquier sentido para realizarlo, pues la solución no varía. Si hay más de una diferencia positiva elegimos el casillero que da la mayor diferencia, si hay 2 o más diferencias positivas iguales y menores elegimos el que corresponde al menor costo en la tabla de costos iniciales. Luego colocamos signos + y – en forma alternada empezando por + en los vértices del polígono determinado por el circuito (este vértice siempre debe tener un valor).

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

5

¿Cómo elegimos el valor a introducir en el casillero (3,5)?. Al valor a introducir lo llamamos θ y deberá cumplir la condición de ser el mínimo de los valores que poseen el signo + en el circuito, en nuestro ejemplo: θ = mín ( 20, 10, 150) θ = 10. Construimos una nueva tabla (Tabla 4), colocando en el casillero (3,5) el valor 10, los valores que no eran vértices o no pertenecían al circuito se mantienen y los vértices del polígono que tenían signo + cambian colocando en su lugar el valor anterior menos θ y los que tenían signo negativo cambian por la suma del anterior y θ. (tabla 4) O1 O2 O3 O4 requerim.

D1 70 70

D2 130 130

D3 100 40 140

D4 150 150

D5 10 140 150

D6 180 10 190

Disponib. 100 250 300 180 830

Z = $ 2930 Volvemos a repetir el proceso (hacer tabla de costos indirectos). Continuar como ejercicio y comprobar que se alcanza el óptimo en Z = $2920. Podemos observar que al hacer la diferencia entre la tabla de costos indirectos y la de costos iniciales aparecen ceros en aquellos lugares que corresponden a las asignaciones (en nuestro caso hay 9 asignaciones), con lo que podemos afirmar que si el número de soluciones es n deben aparecer como mínimo n ceros; si aparecen más significa que el problema tiene soluciones alternativas.

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

6

“ MODELOS O PROBLEMAS DE ASIGNACIÓN PERSONAL” EL PROBLEMA DE ASIGNACIÓN se aplica a todo problema que requiere “asignar m elementos (tareas, máquinas, equipos, operarios, etc.) a otros n elementos (máquinas, tareas, equipos, operarios, etc.), disponiéndose de más de una alternativa de asignación posible. Para simplificar el tema y sin pérdida de generalidad, consideremos el caso particular de asignar “m tareas” a “n máquinas”. OBJETIVO Asignar las tareas a las máquinas (una tarea por máquina) de tal forma de optimizar un índice de performance (objetivo) establecido. En nuestro caso particular será minimizar el costo total de asignación. Este problema es un caso particular del PROBLEMA DE TRANSPORTE en el cuál las FUENTES son cada una de las tareas y los DESTINOS cada una de las máquinas, la disponibilidad de cada fuente es 1 y la demanda de cada destino es 1. REPRESENTACIÓN TABULAR T A R E A S

1 .... i .... m Bj

1 C11 ... Ci1 ... Cm1 1

2 C12 ... Ci2 .... Cm2 1

Ai: disponibilidad

MÁQUINAS ..... ... ... ...

j C1j ... CiJ ... Cmj 1

...... ... ... ....

Bj: requerimientos

REPRESENTACIÓN MATEMÁTICA: MIN Z =

Σ Σ c ij

x ij

Sujeto a:

Σ x ij = 1

i = 1,..., m ( restricciones de disponibilidad)

Σ x ij = 1 x ij = 0

ó

j = 1,..., n ( restricciones de demanda) x ij = 1

∀i ;

∀ j

n C1n ... Cin ... Cmn 1

Ai 1 ... 1 ... 1

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

7

donde: x i j = 0 si la i-ésima tarea no es asignada a la j-ésima máquina x i j = 1 si la i-ésima tarea es asignada a la j-ésima máquina Por lo tanto un problema de Asignación Personal puede resolverse por el Método Simplex. Condición de balance: Para que un problema esté balanceado el n° de tareas a asignar debe ser igual al número de máquinas. Cuando no se cumple la condición de balance será necesario adicionar tantas tareas o máquinas como sea necesario para balancearlo Los costos utilizados en las tareas o máquinas ficticias deben ser todos iguales. RESOLUCIÓN DE UN PROBLEMA DE MINIMIZACIÓN “EL MÉTODO HÚNGARO” Para explicar los pasos del Método Húngaro utilizaremos el siguiente ejemplo: Se desea asignar en forma óptima 7 trabajos a 7 equipos. La tabla siguiente muestra los costos que ocasionarían cada una de las posibles asignaciones. Tabla 1 T1 T2 T3 T4 T5 T6 T7 Mínimo

E1 8 9 6 11 1 16 14 1

E2 9 4 8 7 9 14 4 4

E3 3 3 4 7 10 13 12 3

E4 6 5 11 12 7 14 5 5

E5 1 9 8 3 9 12 1 1

E6 6 7 5 9 7 11 1 1

E7 4 10 9 4 7 6 9 4

Método Húngaro El algoritmo es el siguiente:  1) Se eligen los valores mínimos de cada una de las columnas de la matriz de costos (tabla 1) y se anotan en el margen inferior (lo hacemos en la tabla 1). 

2) Formamos una nueva matriz restando a los elementos de la tabla 1 (por columna) los elementos que figuran en el margen inferior de la misma.

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

8

Tabla 2 T1 T2 T3 T4 T5 T6 T7

E1 7 8 5 10 0 15 13

E2 5 0 4 3 5 10 0

E3 0 0 1 4 7 10 9

E4 1 0 6 7 2 9 0

E5 0 8 7 2 8 11 0

E6 5 6 4 8 6 10 0

E7 0 6 5 0 3 2 5

Mínimo

0 0 1 0 0 2 0

Podemos observar que en la tabla 2 aparecen varios ceros, éstos son de gran importancia en la resolución del problema. Definición Llamaremos ceros esenciales o independientes a aquellos ceros que son únicos en su fila o en su columna. En la tabla 2 es esencial el cero de la posición x 47, por ejemplo. El Método Húngaro busca que efectuando transformaciones en la matriz inicial de costos aparezcan sobre la nueva matriz ceros esenciales. 

3) Se trazan el menor número de líneas posibles sobre filas, sobre columnas o en forma combinada sobre filas y columnas que cumplan la condición de cubrir todos los ceros de la matriz.

Llamaremos con n 1, al número de líneas que cubren los ceros y con n al número de filas o columnas de la matriz de los datos. Para hacer la prueba de optimidad comparamos n 1 con n y si: • n 1 < n el problema aún no está resuelto y debo continuar con el método. • n 1 = n el problema finalizó y se llegó a la solución óptima. En el ejemplo n 1 < n entonces:  4) Colocamos ahora en la tabla 2 los mínimos por fila en el margen derecho y procedemos a hacer una nueva tabla (tabla 3), restando a las filas de la tabla 2 el mínimo correspondiente. h Tabla 3 E1 E2 E3 E4 E5 E6 E7 T1 7 5 0 1 0 5 0 T2 8 0 0 0 8 6 6 T3 4 3 0 5 6 3 4 T4 10 3 4 7 2 8 0 T5 0 5 7 2 8 6 3 T6 13 8 8 7 9 8 0 T7 13 0 9 0 0 0 5 0 0 -1 0 -1 0 -1

1 0 1 1 0 1 0

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

9

Tachamos los ceros y nuevamente n 1 < n por lo tanto, el problema no llegó al óptimo, continuamos con un proceso cíclico que consiste en lo siguiente: 

5) Se elige de las filas o columnas “descubiertas” el valor mínimo que llamaremos “h”, este mínimo se ubica en el margen de la derecha en aquellos lugares que corresponde a una fila descubierta y el valor cero en las filas cubiertas. En el margen inferior colocamos el valor - h (h cambiado de signo) en aquellos lugares que corresponde a columnas cubiertas (tabla 3). En nuestro ejemplo h = 1 Se forma entonces una nueva matriz o tabla restando a cada uno de los elementos de la última matriz sus dos valores marginales correspondientes.

En el ejemplo obtenemos: Tabla 4 E1 6 8 3 9 0 12 13 0

T2 T3 T4 T5 T6 T7

E2 4 0 2 2 5 7 0 0

E3 0 1 0 4 8 8 10 0

E4 0 0 4 6 2 6 0 0

E5 0 9 6 2 9 9 1 0

E6 4 6 2 7 6 7 0 0

E7 0 7 4 0 4 0 6 -2

h Como n 1 < n el problema aún no está resuelto y debo continuar con el método. Comenzamos entonces el proceso cíclico, repito el paso 5) eligiendo h = 2. La nueva matriz será: Tabla 4 T1 T2 T3 T4 T5 T6 T7

E1 6 8 3 7 [0] 10 13

E2 4 0 2 0 5 5 φ

E3 φ 1 [0] 2 8 6 10

E4 0 0 4 4 2 4 φ

E5 0 9 6 0 9 7 1

E6 4 6 2 5 6 5 [0]

E7 2 9 6 φ 6 [0] 8

Como n 1 = n el problema está resuelto. ¿Cómo realizamos las asignaciones? Se hacen primero las asignaciones fijas en aquellos lugares donde están los ceros esenciales.

0 0 0 2 0 2 0

UNIVERSIDAD TECNOLÓGICA NACIONAL – FAC. REG. RAFAELA Docentes: Lic. Elda G. de Huck – Lic. Cristian Bergesse Cátedra: Investigación Operativa

10

En nuestro ejemplo tenemos 4 ceros esenciales por lo que tendremos 4 asignaciones fijas. ¿ Y las restantes cómo las elijo, ya que hay que hacer 7 asignaciones? Éstas se hacen en aquellos lugares donde aparecen los otros ceros en la matriz final (tabla 5), podemos observar que hay 6 ceros no esenciales de los cuáles hay que elegir 3 para que se cumpla la condición de que ningún equipo se quede sin utilizar y ningún trabajo sin realizar y cuidando de que no se otorgue dos o más trabajos a un mismo equipo (asignación 1 a 1). Teniendo en cuenta lo anterior la elección de los ceros se hace en forma arbitraria ya que con cualquier elección posible el costo total será el mismo. Podemos hacer lo siguiente: Asignaciones fijas: T5

E1

T3

E3

T7

E6

T6

E7

Restantes Asignaciones T2

E2

T1

E4

T4

E5

El costo total mínimo será de $ 25. Realizar como ejercicio otras asignaciones, modificando la elección de los ceros no esenciales.