METODO HUNGARO

EL MÉTODO HÚNGARO

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.

olución
Como se puede observar, se tiene un problema balanceado, ya que se cuenta con el mismo número de vendedores y distritos.
Entonces construimos la tabla de asignación, después identificamos el costo menor de cada una de las filas y se lo restamos a los costos de la misma fila:

	1	2	3	4
A	6510	7318	550	583
B	9023	670	8720	758
C	10620	860	9610	893
D	8415	690	7910	778

Posteriormente se identifica el costo menor de cada una de las columnas y se lo restamos a los costos de la misma columna:

	1	2	3	4
A	650	7318	550	580
B	9013	670	8720	755
C	10610	860	9610	890
D	845	690	7910	775

Como no se tiene una asignación posible, tachamos los ceros con el número menor de líneas verticales y horizontales:

Ahora identificamos el menor de los costos no cubiertos por una línea, se lo restamos a los costos no cubiertos por una línea y lo sumamos a los costos que se encuentran en la intersección de dos líneas. Los demás quedan iguales, obteniendo:

	1	2	3	4
A	650	7323	550	580
B	908	670	8715	750
C	10610	865	9610	890
D	840	690	795	770

Realizando una permutación de las columnas logramos obtener una asignación posible y ésta es óptima:

	3	2	4	1
A	550	7323	580	650
B	8715	670	750	908
C	9610	865	890	10610
D	795	690	770	840

Entonces la asignación que minimiza el costo total es:

Vendedor A - Distrito 2

Vendedor B - Distrito 4

Vendedor C - Distrito 1

Vendedor D - Distrito 3

Con un costo mínimo de $295.

METODO DE VOGEL

MÉTODO DE VOGEL

Para cada renglón o columna en el que quede alguna oferta o alguna demanda, se calcula su penalización, que es la diferencia no negativa entre los 2 costos más pequeños de transporte C_ij asociados con las variables no asignadas en ese renglón o en esa columna. Se considera el renglón o la columna para la mayor diferencia (en caso de empate se selecciona uno arbitrariamente). En este renglón o columna se localiza la variable no asignada (celdilla) que tenga el costo unitario más pequeño de transporte y se le asignan tantas unidades como sea posible sin ir en contra de las restricciones; se calculan las nuevas diferencias y se repite el procedimiento anterior hasta satisfacer todas las demandas.

Para cada renglón o columna en el que quede algún suministro o alguna demanda, calcúlese su diferencia, que es la diferencia no negativa entre los 2 más pequeños costos de embarque C_ijasociadas con las variables no asignadas en ese renglón o en esa columna. Considérese el renglón o la columna para la mayor diferencia en caso de empate selecciónese uno arbitrariamente. En este renglón o columna localice la variable no asignada (celdilla) que tenga el costo unitario más pequeños de embarque y asígnele tantas unidades como sea posible sin ir en contra de las restricciones calcúlese las nuevas diferencias y repítase el procedimiento anterior hasta satisfacer todas las demandas.

Ejemplo:

Encuentre la solución inicial del problema de la compañía de renta de autos por el método de aproximación de vogel.

Una empresa está considerando satisfacer las necesidades de 4 clientes empleando los artículos que tiene disponibles en 3 almacenes. La cantidad de artículos que tiene en cada almacén son y es, 40 y 20 unidades respectivamente. Los clientes necesitan 12, 15, 30 y 20 unidades respectivamente. El costo unitario de embarque desde los almacenes hasta el cliente se encuentran en la siguiente tabla:

Encuentre la solución inicial del modelo de transporte utilizando el método de aproximación de vogel.

METODO DE COSTOS MINIMOS

MODELO DEL COSTO MINIMO

Asígnese el más grande valor posible a la variable con el menor costo unitario de toda la tabla. Táchese el renglón o columna satisfecha. Después de ajustar la oferta y la demanda de todos los renglones y columnas no tachados, repítase el proceso asignando el valor más grande posible a la variable con el costo unitario no tachado más pequeño. El procedimiento esta completo cuando queda exactamente un renglón o bien una columna sin tachar.

Características

http://es.scribd.com/doc/39695565/59/Metodo-del-costo-minimo

EN ESTE ENLACE PODRÁN VISUALIZAR EJERCICIOS RESUELTOS SOBRE ESTE MÉTODO 

METODO DE LA ESQUINA NOROESTE

. METODO DE LA ESQUINA NOROESTE.

Este método comienza asignando la cantidad máxima permisible para la oferta y la demanda a la variable X₁₁ (la que está en la esquina noroeste de la tabla).

La columna o renglón satisfechos se tacha indicando que las variables restantes en la columna o renglón tachado son igual a cero. Si la columna y el renglón se satisfacen simultaneamente, únicamente uno (cualquiera de los dos) debe tacharse. Esta condición garantiza localizar las variables básicas cero si es que existen. Después de ajustar las cantidades de oferta y demanda para todos los renglones y columnas no tachados, la cantidad máxima factible se asigna al primer elemento no tachado en la nueva columna o renglón. El procedimiento termina cuando exactamente un renglón o una columna se dejan sin tachar.

Ejemplo:

Una compañía tiene 3 almacenes con 15, 25 y 5 artículos disponibles respectivamente. Con estos productos disponibles desea satisfacer la demanda de 4 clientes que requieren 5, 15, 15 y 10 unidades respectivamente. Los costos asociados con el envío de mercancía del almacén al cliente por unidad se dan en la siguiente tabla.

	Clientes
Almacén	1	2	3	4
1	10	0	20	11
2	12	7	9	20
3	0	14	16	18

Construya la solución básica inicial por el método de la esquina noroeste.

Ejemplo 2.

Una compañía de renta de autos tiene problemas de distribución debido a que los acuerdos de renta permiten que los autos se entreguen en lugares diferentes a aquellos en que originalmente fueron rentados. Por el momento, hay 2 lugares (fuentes) con 15 y 13 autos en exceso, respectivamente, y cuatro lugares (destinos) en los que se requieren 9, 6, 7, y 9 autos respectivamente. Los costos unitarios de transporte en dólares entre los lugares son los siguientes:

Elabore la tabla inicial de transporte por el método de la esquina noroeste.

Crear un origen ficticio con autos disponibles.

MÉTODO DE LAS DOS FASES

MÉTODO DE LAS DOS FASES.

---

La desventaja de la técnica M es el posible error de cómputo que podría resultar de asignar un valor muy grande a la constante M. Esta situación podría presentar errores de redondeo en las operaciones de la computadora digital. Para evitar esta dificultad el problema se puede resolver en 2 fases.

FASE 1. Formule un nuevo problema reemplazando la función objetivo por la suma de las variables artificiales.

La nueva función objetivo se minimiza sujeta a las restricciones del problema original. Si el problema tiene un espacio factible el valor mínimo de la función objetivo óptima será cero, lo cual indica que todas las variables artificiales son cero. En este momento pasamos a la fase 2.

* Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles

FASE 2. Utilice la solución óptima de la fase 1 como solución de inicio para el problema original. En este caso, la función objetivo original se expresa en términos de las variables no básicas utilizando las eliminaciones usuales Gauss-Jordan.

PROBLEMA # 1
Minimizar

Sujeto a:


Minimizar

Sujeto a:



FASE I

Minimizar

Sujeto a:




Minimizar

Sujeto a:

V.B.	Z	X1	X2	S1	S2	R1	R2	Solución
Z	1	0	0	0	0	-1	-1	0
R1	0	2	3	-1	0	1	0	36
R2	0	3	6	0	-1	0	1	60

V.B.	Z	X1	X2	S1	S2	R1	R2	Solución
Z	1	5	9	-1	-1	0	0	96
R1	0	2	3	-1	0	1	0	36
R2	0	3	6	0	-1	0	1	60

V.B.	Z	X1	X2	S1	S2	R1	R2	Solución
Z	1	1/2	0	-1	1 /2	0	3/2	6
R1	0	1/2	0	-1	1 /2	1	-1/2	6
X2	0	1/2	1	0	-1/6	0	1/6	10

V.B.	Z	X1	X2	S1	S2	R1	R2	Solución
Z	1	0	0	0	0	-1	-1	0
X1	0	1	0	-2	1	2	-1	12
X2	0	0	1	1	-2/3	-1	2/3	4

FASE II.

Minimizar

V. Básica	Z	X1	X2	S1	S2	Solución
Z	1	-2000	-500	0	0	0
X1	0	1	0	-2	1	12
X2	0	0	1	1	-2/3	4

V. Básica	Z	X1	X2	S1	S2	Solución
Z	1	0	0	-3500	5000/3	26000
X1	0	1	0	-2	1	12
X2	0	0	1	1	-2/3	4

V. Básica	Z	X1	X2	S1	S2	Solución
Z	1	-5000/3	0	-500/3	0	6000
S2	0	1	0	-2	1	12
X2	0	2/3	1	-1/3	0	12

PROBLEMA 2.


Maximizar

Sujeto a:












FASE I.

En la FASE I siempre es un problema de minimización.

Minimizar

Sujeto a:

V. Básica	Z	X1	X2	X3	S1	R1	Solución
Z	1	0	0	0	0	-1	0
S1	0	3	6	1	1	0	20
R1	0	3	1	2	0	1	15

V. Básica	Z	X1	X2	X3	S1	R1	Solución
Z	1	3	1	2	0	-1	15
S1	0	3	6	1	1	0	20
R1	0	3	1	2	0	1	15

V. Básica	Z	X1	X2	X3	S1	R1	Solución
Z	1	0	0	0	0	-1	0
S1	0	0	5	-1	1	-1	5
X1	0	1	1/3	2/3	0	1/3	5

Aquí termina la fase I.

FASE II.

Maximizar

V. Básica	Z	X1	X2	X3	S1	Solución
Z	1	-6	-4	-4	0	0
S1	0	0	5	-1	1	5
X1	0	1	1/3	2/3	0	5

V. Básica	Z	X1	X2	X3	S1	Solución
Z	1	0	-2	0	0	30
S1	0	0	5	-1	1	5
X1	0	1	1/3	2/3	0	5

V. Básica	Z	X1	X2	X3	S1	Solución
Z	1	0	0	-2/5	2/5	32
X2	0	0	1	-1/5	1/5	1
X1	0	1	0	11/15	-1/15	14/3

V. Básica	Z	X1	X2	X3	S1	Solución
Z	1	6/11	0	0	4/11	380/11
X2	0	3/11	1	0	2/11	25/11
X1	0	15/11	0	1	-5/11	70/11