Metodo Hungaro

El Método Húngaro

EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.

El algoritmo desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de otros dos matemáticos Húngaros: Dénes König y Jenő Egerváry. La gran ventaja del método de Kuhn es que es fuertemente polinómico (ver Complejidad computacional para más detalles).

El algoritmo construye una solución del problema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible.

Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación. Las fases para la aplicación del método Húngaro son:

Paso 1: Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cada costo el costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna.

Paso 2: (En algunos pocos textos este paso se atribuye a Flood). Consiste en trazar el número mínimo de líneas (horizontales o verticales o ambas únicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se pueden realizar.

Paso 3: Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no está cubierto por las líneas dibujadas en el paso 2; a continuación se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos líneas (intersecciones). Por último se debe regresar al paso 2.

Notas:

1. Para resolver un problema de asignación en el cual la meta es maximizar la función objetivo, se debe multiplicar la matriz de ganancias por menos uno (−1) y resolver el problema como uno de minimización.

2. Si el número de filas y de columnas en la matriz de costos son diferentes, el problema de asignación está desbalanceado. El método Húngaro puede proporcionar una solución incorrecta si el problema no está balanceado; debido a lo anterior, se debe balancear primero cualquier problema de asignación (añadiendo filas o columnas ficticias) antes de resolverlo mediante el método Húngaro.

3. En un problema grande, puede resultar difícil obtener el mínimo número de filas necesarias para cubrir todos los ceros en la matriz de costos actual. Se puede demostrar que si se necesitan j líneas para cubrir todos los ceros, entonces se pueden asignar solamente j trabajos a un costo cero en la matriz actual; esto explica porqué termina cuando se necesitan m líneas. 

Aplicacion del Metodo:

Transporte

Definición y aplicación del modelo de transporte.

El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:

1.      Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.

2.      El costo de transporte unitario de la mercancía a cada destino. 

Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total. La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al número de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.

Un método mas resumido para representar el modelo de transporte consiste en utilizar lo que se llama tabla de transporte. Esta es una forma de matriz donde sus renglones representan las fuentes y sus columnas los destinos. Los elementos de costo C _{i j} se resumen en la esquina noroeste de la celda de la matriz (i, j). Por lo tanto, el modelo de MG se puede resumir en la tabla siguiente:

Para que un problema pueda ser resuelto por el método del transporte debe cumplir:

1) La función objetivo y las restricciones deben ser lineales.
2) El total de unidades que salen en origen debe ser igual al total de unidades que entran en destino. 

Modelo de transporte
Donde:
ai = Capacidad de la fuente i.
bj = Demanda del almacén j.
m = Número de fuentes distribuidoras.
n = Número de destinos receptores.

La matriz a emplear tiene las siguientes características:

          Desde
Hasta 1 2 3 Demanda
1 C11 C12 C13 X1
2 C21 C22 C23 X2
3 C31 C32 C33 X2
Oferta X1 X2 X3

Las columnas 1, 2 y 3 son los lugares de origen.
Las filas 1,2 y 3 son los lugares de destino.
Las ofertas x1, x2 y x3 son las cantidades ofrecidas a los clientes.
Los Cij son los costos unitarios de traslado desde un origen hasta un destino.
Los Xij son la cantidad de bienes o recursos trasladados desde un origen hasta un destino.

Para poder resolver un problema de transporte la matriz original debe estar balanceada, es decir, las cantidades ofertadas deben ser iguales a las cantidades demandadas. De NO ocurrir esto se debe crear una fila o columna ficticia cuyos costos de traslados sean iguales a cero y la cantidad ofertada o demandada suficiente para lograr el balanceo.
Aunque existen varias técnicas para solucionar modelos de transporte la más importante de ellas es la de ”Aproximación de Vogel” ya que la solución obtenida a través de ella es la optima o está más próxima a la optima.

Método de solución inicial.

Mediante el uso del método simplex se pueden resolver los modelos de transporte y de cualquier otro tipo de problemas de programación lineal. Sin embargo debido a la estructura especial de modelo de transporte, podemos utilizar otro método que se ha diseñado para aprovechar las características de los problemas de transporte.
Los método de esquina noroeste, costo mínimo y aproximación de Vogel son alternativas para encontrar una solución inicial factible.
Esquina noroeste. Este método es considera el más fácil. Es también considerado por ser el menos probable para dar una buena solución inicial y de “bajo costo” porque ignora la magnitud relativa de los costos Cij.
Antes de describir el procedimiento, es necesario establecer que el número de variables básicas en cualquier solución básica de un problema de transporte es una menos de la que se espera. Normalmente, en los problemas de programación lineal, se tiene una variable básica para cada restricción. En los problemas de transporte con m recursos y n destinos el número de restricciones funcionales es m + n. Sin embargo,
               el número de variables básicas = m + n - 1

Este procedimiento esta dado por los siguientes tres pasos:

1.- Seleccionar la celda de la esquina noroeste (esquina superior izquierda) para envío.
2.- Efectuar el más grande envío como pueda en la celda de la esquina noroeste.
Esta operación agotará completamente la disponibilidad de suministros en un origen o los requerimientos de demanda en un destino.
3.- Corrija los números de suministro y los requerimientos para reflejar lo que va quedando de suministro y requerimiento y regresar al paso 1.

El esquema siguiente representa el modelo de transporte como una red con m fuentes y n destinos. Una fuente o un destino está representado por un nodo, el arco que une  fuente y un destino representa la ruta por la cual se transporta la mercancía. La cantidad de la oferta en la fuente i es a_i, y la demanda en el destino j es b_j. El costo de transporte unitario entre la fuente  i  y el destino j es C_ij.

Si X_{i j} representa la cantidad transportada desde la fuente i al destino j, entonces, el modelo general de PL que representa el modelo de transporte es:

                   Minimiza  Z= S _i=1 ^m    S _j=1 ⁿ  C _{i j} X _{i j}          

Sujeta a:

 S _j=1 ⁿ  X _{i j} <= ai ,         i=1,2,…, m

S _i=1 ^m X _{I j} >= bj ,         j=1,2,…, n

 X _{i j} >=0         para todas las i y j  

El primer conjunto de restricciones estipula que la suma de los envíos desde una fuente no puede ser mayor que su oferta; en forma análoga, el segundo conjunto requiere que la suma de los envíos a un destino satisfaga su demanda.

 El modelo que se acaba de escribir implica que la oferta total S_i=1 ^m ai debe ser cuando menos igual a la demanda total S_j=1 ⁿ bj.  Cuando la oferta total es igual a la demanda total, la formulación resultante recibe el nombre de modelo de transporte equilibrado. Este difiere del modelo solo en el hecho de que todas las restricciones son ecuaciones, es decir: 

                   SX _{i j} = ai,        i=1,2,..., m

                   SX _{i j} = bj,        j=1,2,..., n 

El objetivo es el de formular el plan de inventario de producción a costo mínimo. Este problema se puede formular como un modelo de “transporte”. La equivalencia entre los elementos de los sistemas de producción y transporte se establece de la manera siguiente:

Sistema de Transporte	Sistema de Producción
1. Fuente i	1. Periodo de producción i
2. Destino j	2. Periodo de demanda j
3. Oferta en la fuente i	3. Capacidad de producción del periodo i
4. Demanda en el destino j	4. Demanda del periodo j
5. Costo de transporte de la fuente i al destino j	5. Costo de producto e inventario del periodo i al j

En tabla de abajo se presenta un resumen del problema como un modelo de transporte:

		Periodo
		1	2	3	4	Capacidad
Demanda	1	4	4.5	5	5.5	50
	2	6	4	4.5	5	180
	3	8	6	4	4.5	280
	4	10	8	6	4	270
	Demanda:	100	200	180	300

El costo de “transporte” unitario del periodo i al  j es:

                        Costo de producción en i,                                                            i=j

Problema Dual

 Problema Dual.

Definicion del Problema Dual.

Para poder elaborar el problema dual a partir del primal, este se debe presentar en su forma canónica de la siguiente forma:

El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera:

1. Cada restricción de un problema corresponde a una variable en el otro.

2. Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la función objetivo en el otro.

3. Un problema busca maximizar y el otro minimizar.

4. El problema de maximización tiene restricciones que y el problema de minimización tiene restricciones que.

5. Las variables en ambos casos son no negativas. 

¿Cómo convertir un problema primal a dual?

Un problema dual se formula de un problema primal de la siguiente forma: 

1. Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.

2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.

3. Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.

4. Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.

5. Los signos de desigualdad del  problema dual son contrarios a los del primal.

6. Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables Xn del primal se convierte en nuevas variables Ym en el dual.
7. 
   

   PROBLEMA PRIMAL EN FORMA CANONICA: MAX  Z= CX Sujeto a: AX £ b X ³ 0

   PROBLEMA DUAL EN FORMA CANONICA: MIN  Z= BY Sujeto a: AY ³ C Y ³ 0

   
   
   Ejemplo.
   Si el problema primal es: MAX  Z= 45X1 + 17X2 + 55X3
                                 Sujeto a:
                                           X1   +    X2  +     X3   £ 200
                                          9X1  +  8X2  +  10X3  £ 5000
                                          10X1+  7X2  + 21 X3  £ 4000
                                          Xj ³ 0
    El problema dual será:
             MIN  Z= 200Y1 + 5000Y2 + 4000Y3
             Sujeto a:
                         Y1 +   9Y2 + 10Y3  ³ 45
                         Y1 +   8Y2 +   7Y3  ³ 17
                         Y1 + 10Y2 + 21Y3 ³ 55
               Yj ³ 0 
   
   
   Forma de representar el problema dual.
   MIN  =  2X1 -  3X2                                                            
   Sujeto a:                                                                                    
             1X1 +  2X2  £  12                                                                       
             4X1 -   2X2  ³   3
             6X1 -   1X2  = 10                                                                          
   X1,2  ³ 0
     1.  Llevar el problema a su equivalente de maximización, multiplicando la función objetivo por –1: 
   MAX  -2X1 + 3X2
   2. Convertir las restricciones ³ en una restricción equivalente £ multiplicando por –1 ambos lados:
   -4x1 + 2x2  £ -3  
   3. Para las restricciones de igualdad, obtener 2 restricciones de desigualdad, una de forma £ y la otra de forma ³; después regresar al punto anterior y cambiar la restricción ³ a la forma £:
   6X1 – 1X2 £ 10 
   6X1 – 1X2 ³ 10
   6X1 –  1X2  £   10
   -6X1 + 1X2  £  -10
   
   
   
   
   Así el problema primal se ha replanteado en la forma equivalente: 
   MAX  Z= -2X1 + 3X2
   Sujeto a:
   1X1 + 2X2  £  12
   -4X1 + 2X2  £  - 3
   6X1 – 1X2   £  10
   -6X1 + 1X2  £ -10
          X1,2 ³ 0   
   4. Teniendo el problema primal convertido a la forma canónica de un problema de maximización, es fácil llevarlo al problema dual:
   MIN    12Y1 – 3Y2 + 10Y3
   Sujeto a:
   Y1–4Y2 + 6Y3’–6Y3’’ ³-2          Y’3  y  Y’’3 ambas se refieren a la tercera restricción
   2Y1 + 2Y2 – 1Y3’ + 1Y3’’  ³   3                  del problema  primal.
   Y1, 2, 3’, 3’’ ³ 0