antologia metodo de asignacion unidad 2

CATEDRTICO

ING. VIOLETA GPE. CLEMENTE ARCE

UNIDAD II

MTODO DE TRANSPORTE

TEMA

MTODO DE ASIGNACIN

INTEGRANTES

YANCELI DEL CARMEN LZARO RAMREZ

VANESSA DAYALI ROS GARCA

BRENDA YARISBETH ZAVALA CRUZ

ALEX OVANDO NATAREN

JAIRO JASETH LAGUNA FONSECA

JESS ALBORES RUIZ

RAL ARTEMIO OVANDO VENTURA

MARCOS TEODOLINDO SOLS REYES

JOS IGNACIO CRDOVA HERNNDEZ

Ing. Informtica 4E

CINTALAPA DE FIGUEROA CHIS, A 11/ABRIL/2014

INSTITUTO TECNOLOGICO SUPERIOR DE

CINTALAPA

MTODO DE ASIGNACIN

Problema de asignacin

Este problema consiste en asignar n individuos a n tareas de modo que todos los

individuos realicen una tarea y todas las tareas se realicen. Se exige adems que

el costo total sea mnimo.

Ejemplo: Una empresa tiene 4 mquinas y debe completar cuatro tareas. Cada mquina puede y debe realizar una y slo una de las tareas. La tabla siguiente nos

da el tiempo que tarda cada mquina en completar cada trabajo.

Asignar una tarea a cada mquina de modo que la suma de los tiempos

trabajados por las cuatro mquinas sea mnimo, este problema se puede resolver

por el algoritmo de transporte, ya que las mquinas pueden ser interpretadas

como orgenes con oferta 1 y las tareas como destinos con una demanda de 1,

puesto que cada mquina slo hace una tarea y todas las tareas han de ser

realizadas.

Las soluciones de este problema slo pueden tomar los valores 0 1. Un 1

en la celda (i, j) significa que al individuo i se asigna la tarea j.

Aunque el problema puede resolverse por el algoritmo de transporte, se

suele presentar un alto grado de degeneracin.

Para el problema de asignacin es ms eficiente usar el mtodo Hngaro,

que exponemos a continuacin.

MTODO DE HNGARO

MTODO HNGARO

El Mtodo Hngaro es un problema de transporte balanceado, en el cual todas las

ofertas y todas las demandas son iguales a uno. Se puede resolver eficientemente

un problema de asignacin m x m mediante el mtodo Hngaro: Apartndonos un

poco de la idea expresada en mdulos anteriores respecto a la facilidad de

resolver problemas atinentes a la investigacin operativa en especial aquellos de

transporte mediante el uso de herramientas tecnolgicas como lo son WinQSB,

LINGO, TORA, STORM, Excel etc. Vale la pena ya sea para fines acadmicos o de

cultura ingenieril realizar la resolucin del problema de asignacin mediante el

algoritmo que se cre para tal fin, como lo es el Mtodo Hngaro.

El mtodo Hngaro es un mtodo de optimizacin de problemas de asignacin,

conocido como tal gracias a que los primeros aportes al mtodo clsico definitivo

fueron de Dnes Knig y Jen Egervry dos matemticos hngaros. El algoritmo

tal como se detallar a continuacin est diseado para la resolucin de

problemas de minimizacin nicamente, ser entonces cuestin de agregar un

paso adicional para abordar ejercicios de maximizacin.

ALGORITMO HNGARO, PASO 1

Antes que nada cabe recordar que el mtodo hngaro trabaja en una matriz de

costos n*m (en este caso conocida como matriz m*m, dado que el nmero de filas

es igual al nmero de columnas n = m), una vez construida esta se debe encontrar

el elemento ms pequeo en cada fila de la matriz.


Una vez se cumple el procedimiento anterior se debe construir una nueva matriz

n*m, en la cual se consignarn los valores resultantes de la diferencia entre cada

costo y el valor mnimo de la fila a la cual cada costo corresponde (valor mnimo

hallado en el primer paso).


Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores

referidos ahora a las columnas, es decir, se halla el valor mnimo de cada

columna, con la diferencia que este se halla de la matriz resultante en el segundo

paso, luego se construir una nueva matriz en la cual se consignarn los valores

resultantes de la diferencia entre cada costo y el valor mnimo de la columna a la

cual cada costo corresponde, matriz llamada "Matriz de Costos Reducidos".


A continuacin se deben de trazar lneas horizontales o verticales o ambas

(nicamente de esos tipos) con el objetivo de cubrir todos los ceros de la matriz de

costos reducidos con el menor nmero de lneas posibles, si el nmero de lneas

es igual al nmero de filas o columnas se ha logrado obtener la solucin ptima (la

mejor asignacin segn el contexto de optimizacin), si el nmero de lneas es

inferior al nmero de filas o columnas se debe de proceder con el paso.


Este paso consiste en encontrar el menor elemento de aquellos valores que no se

encuentran cubiertos por las lneas del paso 4, ahora se restar del restante de

elementos que no se encuentran cubiertos por las lneas; a continuacin este

mismo valor se sumar a los valores que se encuentren en las intersecciones de

las lneas horizontales y verticales, una vez finalizado este paso se debe volver al

paso 4.

EXPLICACIN DEL MTODO HNGARO CON EL SIMPLEX

Vamos a aplicar este algoritmo al problema del ejemplo. Se usarn los siguientes

smbolos:

Esta ltima es la matriz de costos reducidos.

Paso 2 (se indica el orden en que se han seleccionado los ceros):

Como hay 4 ceros recuadrados, sus posiciones marcan la solucin ptima. En

este caso consiste en que la mquina 1 hace la tarea 2, la mquina 2 la tarea 4, la

3 la tarea 3 y la 4 la tarea 1.

El tiempo total requerido ser 1 + 5 + 1 + 3 = 10. Con el objeto de ilustrar el resto

del algoritmo lo aplicamos a la matriz del siguiente ejemplo.

Ejemplo: Hallar la solucin ptima en el problema de asignacin cuya matriz de

costos reducidos es:

Como ya se ha realizado el paso 1 comenzamos el siguiente.

Paso 2

Como hay menos ceros recuadrados que filas (o columnas) continuamos con el

siguiente paso.

Paso 4 a, b, c.

Est indicado en la tabla el orden en que se han marcado las filas y columnas.

Ya no pueden marcarse ms filas ni ms columnas.

Paso 4e ( los elementos marcados con xx son los que estn tachados dos veces)

Paso 5

Vuelta al paso 2. Se indica el orden en que se han recuadrado los ceros.

Ahora hay 4 ceros recuadrados que marcan una solucin ptima.

EJERCICIOS RESUELTOS

RESOLUCIN DE UN PROBLEMA DE ASIGNACIN MEDIANTE EL MTODO HNGARO

PROBLEMA 1

La compaa de manufactura "Jimnez y Asociados" desea realizar una jornada de mantenimiento

preventivo a sus tres mquinas principales A, B y C. El tiempo que demanda realizar el

mantenimiento de cada mquina es de 1 da, sin embargo la jornada de mantenimiento no puede

durar ms de un da, teniendo en cuenta que la compaa cuenta con tres proveedores de servicios

de mantenimiento debe de asignarse un equipo de mantenimiento a cada mquina para poder

cumplir con la realizacin del mantenimiento preventivo. Teniendo en cuenta que segn el grado de

especializacin de cada equipo prestador de servicios de mantenimiento el costo de la tarea vara

para cada mquina en particular, debe de asignarse el equipo correcto a la mquina indicada con el

objetivo de minimizar el costo total de la jornada. Los costos asociados se pueden observar en la

siguiente tabla:

PASO 1

Encontramos el menor elemento de cada fila

PASO 2

Construimos una nueva matriz con las diferencias entre los valores de la matriz original y el

elemento menor de la fila a la cual corresponde.

PASO 3

En la matriz construida en el paso anterior se procede a efectuar el paso 1 esta vez en relacin a las

columnas, por ende escogemos el elemento menor de cada columna. Igualmente construimos una

nueva matriz con la diferencia entre los valores de la matriz 2 y el elemento menor de la columna a

la cual corresponde cada valor.

PASO 4

En este paso trazaremos la menor cantidad de combinaciones de lneas horizontales y verticales con

el objetivo de cubrir todos los ceros de la matriz de costos reducidos.

Como se puede observar el menor nmero de lneas horizontales y/o verticales necesarias para

cubrir los ceros de la matriz de costos reducidos es igual a 2, por ende al ser menor que el nmero

de filas o columnas es necesario recurrir al paso 5.

PASO 5

En este paso seleccionamos el menor elemento de los elementos no subrayados.

Luego se procede a restarse de los elementos no subrayados y a adicionarse a los elementos

ubicados en las intersecciones de las lneas, en este caso existe una nica interseccin (3).

Ahora ya efectuado este paso pasamos al paso 4.

Ahora observamos cmo se hace necesario trazar tres lneas (la misma cantidad de filas o columnas

de la matriz) por ende se ha llegado al tabulado final, en el que por simple observacin se determina

las asignaciones ptimas.

Por ende la asignacin que representa el menor costo para la jornada de mantenimiento preventivo

determina que el Equipo 1 realice el mantenimiento de la Mquina 1, el Equipo 2 realice el

mantenimiento de la Mquina 3 y el Equipo 3 realice el mantenimiento de la Mquina 2, jornada que

tendr un costo total de 17 unidades monetarias.

RESOLUCIN DE UN PROBLEMA DE MAXIMIZACIN MEDIANTE EL MTODO HNGARO

PROBLEMA 2

Una organizacin de recoleccin de caf cuenta con tres equipos de siembra y cosecha del mismo

(equipos 1, 2, 3). Estos equipos de trabajo se encuentran entrenados para trabajar en condiciones

particulares del proceso, condiciones como lo son el tipo de suelo, las condiciones del clima y el tipo

de grano. La organizacin cuenta con cuatro terrenos disponibles para efectuar el proceso de

siembra y cosecha (terrenos A, B, C, D), estos terrenos tienen condiciones particulares de suelo,

clima y tipo de grano. Cada equipo cuenta con la capacidad de efectuar el proceso en solo uno de

los terrenos disponibles, salvo el equipo 2, que cuenta con una serie de herramientas tecnolgicas

que le permiten realizar la siembra y cosecha del grano en dos de los terrenos disponibles. Se ha

contratado a un Ingeniero Industrial con el objetivo de realizar las asignaciones precisas que

maximicen la cantidad de sacos de caf cosechados en total. El siguiente tabulado muestra la

capacidad (en cientos de sacos) de cosecha de caf de cada uno de los equipos dependiendo de

cada uno de los terrenos.

RESOLUCIN

En este problema debemos recordar un concepto fundamental para la aplicacin del mtodo

hngaro, este concepto nos dice que el nmero de filas debe ser exactamente igual al nmero de

columnas. Por ende, la accin a realizar debera ser crear un equipo ficticio, el cual nos deje el

tabulado balanceado y a este asignarle un nmero de sacos cosechados equivalente a cero en cada

uno de los terrenos. Sin embargo el problema nos indica que uno de los equipos se encuentra en

capacidad de que se le asignen dos terrenos, en este caso crearemos un equipo 2 alternativo

(Equipo 2B) el cual nos balancear el tabulado y nos har prescindir del equipo ficticio pensado

inicialmente. A este equipo 2B que crearemos le corresponder la misma capacidad de cosecha del

equipo 2 (en adelante equipo 2A) segn el terreno, lgicamente.

Una vez balanceado el tabulado debemos de cuestionarnos acerca del criterio de optimizacin, pues

recordemos que el mtodo hngaro se encuentra diseado para ejercicios de minimizacin. En este

caso nuestro objetivo es maximizar, por lo que tendremos que aplicar un paso adicional.

Lo primero que debemos hacer es ubicar el mayor valor del tabulado inicial.

En este caso este valor es 15, por lo cual procederemos a realizar la siguiente operacin con cada

uno de los valores:

Restaremos a 15, el valor de cada una de las celdas y este valor quedar en cada una de las celdas

correspondientes.

Ahora nuestro tabulado inicial quedar de la siguiente manera:

A partir de este tabulado ya podemos aplicar el algoritmo del mtodo hngaro como se aplicara en

un caso e minimizacin (normalmente).

Ahora encontramos el menor elemento de cada fila.

y se lo restamos a todas las celdas de la fila.

Ahora efectuamos este mismo paso, pero esta vez con las columnas. Elegimos el menor de los

valores de cada columna y se lo restamos a cada una de las celdas de la columna correspondiente.

Ahora procedemos a cubrir la mayor cantidad de ceros, con la menor cantidad de lneas, si el

nmero de lneas que empleemos es igual al grado de la matriz (en este caso matriz grado 4, 4x4)

habremos llegado al final del ejercicio.

Dado que el nmero de lneas es igual al grado de la matriz, hemos concluido el algoritmo. Lo nico

que quedar ser asignar a cada equipo el terreno en el que el intercepto es igual a 0 (cero).

Las asignaciones, como es lgico debern iniciarse por el equipo al cual solo corresponda un

terreno, en este caso al Equipo 3 le corresponde el Terreno A. De esta manera al Equipo 1 le

corresponde el Terreno D. Mientras tanto el Equipo 2 se encargar de la cosecha en los terrenos B y

C. Segn el tabulado del problema (recordemos que es de maximizacin), la cantidad de sacos

(expresada en cientos de sacos) ser as:

RESOLUCIN DE UN PROBLEMA DE ASIGNACIN MEDIANTE PROGRAMACIN LINEAL

PROBLEMA 3

La compaa de manufactura "Jimnez y Asociados" desea realizar una jornada de mantenimiento

preventivo a sus tres mquinas principales A, B y C. El tiempo que demanda realizar el

mantenimiento de cada mquina es de 1 da, sin embargo la jornada de mantenimiento no puede

durar ms de un da, teniendo en cuenta que la compaa cuenta con tres proveedores de servicios

de mantenimiento debe de asignarse un equipo de mantenimiento a cada mquina para poder

cumplir con la realizacin del mantenimiento preventivo. Teniendo en cuenta que segn el grado de

especializacin de cada equipo prestador de servicios de mantenimiento el costo de la tarea vara

para cada mquina en particular, debe de asignarse el equipo correcto a la mquina indicada con el

objetivo de minimizar el costo total de la jornada. Los costos asociados se pueden observar en la

siguiente tabla:

VARIABLES DE DECISIN

Las variables de decisin de este tipo de problemas es igual a las variables de cualquier modelo de

transporte tradicional, es decir variables Xi,j donde i {Equipo de mantenimiento 1,2,3} y j {Mquina

1,2,3}, y corresponden a variables binarias en las cuales el valor 1 significa la asignacin de un

equipo de mantenimiento a una mquina en particular.

RESTRICCIONES

Dado que un equipo de mantenimiento no puede ser asignado a ms de una maquinaria, esta

caracterstica debe de restringirse mediante las siguientes inecuaciones.

X1,1 + X1,2 + X1,3 = 1

X2,1 + X2,2 + X2,3 = 1

X3,1 + X3,2 + X3,3 = 1

Adems debe restringirse el hecho de que cada mquina solo requiere de un equipo de

mantenimiento, por ende

X1,1 + X2,1 + X3,1 = 1

X1,2 + X2,2 + X3,2 = 1

X1,3 + X2,3 + X3,3 = 1

Adems se hace necesario que para efectos de resolucin en cualquier paquete de herramientas se

especifique que estas variables corresponden al conjunto de los enteros (por obvias razones) y que

deben ser mayores que cero (dado que es un problema de minimizacin esta restriccin se hace

muy necesario).

Xi,j 0

Xi,j {Z}

FUNCIN OBJETIVO

ZMIN = 10X1,1 + 9X1,2 + 5X1,3 + 9X2,1 + 8X2,2 + 3X2,3 + 6X3,1 + 4X3,2 + 7X3,3

PROBLEMA 4

Se usan cuatro barcos cargueros para transportar bienes de un puerto a otros cuatro puertos

(numerados 1, 2,3 y 4). Se puede usar cualquier barco para hacer cualquiera de los cuatro viajes.

Sin embargo, dadas algunas diferencias entre los barcos y las cargas, el costo total de cargar,

transporte y descargue de bienes para las distintas combinaciones de barcos y puerto vara mucho.

Estos costos se muestran en la siguiente tabla:

El objetivo es asignar los barcos a los puertos en una correspondencia uno a uno, de manera que se

minimice el costo total de los cuatro barcos.

Formulacin

1. Definicin de las variables:

Xij = 0, No asigne el barco i-simo (i = 1,2,3 y 4) al puerto j-simo (j = 1,2,3 y 4)

Xij = 1, Si asigne el barco i-simo (i = 1,2,3 y 4) al puerto j-simo (j = 1,2,3 y 4)

2. Funcin objetivo:

Minimice Z = 5X11 + 4X12 + 6X13 + 7X14 + 6X21 + 6X22 + 7X23 + 5X24 + 7X31 + 5X32 + 7X33 + 6X34 +

5X41 + 4X42 + 6X43 + 6X44 Sujeto a las siguientes restricciones:

3. Restricciones:

4. Condicin de no negatividad:

Xij 0 ; i = 1,2,3 y 4 ; j = 1,2,3 y 4

PROBLEMA 5

Una factora tiene cuatro operarios, los cuales deben ser asignados al manejo de cuatro mquinas;

las horas requeridas para cada trabajador en cada mquina se dan en la tabla adjunta; el tiempo a

laborar por cada operario en cada una de las mquinas se pretende que sea mnimo, para lo cual se

busca la asignacin ptima posible.

Planteamiento del Modelo Primal:

MIN W = 10 X11+ 14 X12+ 16 X13+ 13 X14+ 12 X21+ 13 X22+ 15 X23+ 12 X24+ + 9 X31+ 12 X32+ 12 X33+ 11 X34+ 14 X41+ 16 X42+ 18 X43+ 16 X44

Sujeto a las siguientes restricciones:

Aplicando el mtodo Hngaro tenemos:

1 2 3 4

A 10 14 16 13

B 12 13 15 12

C 9 12 12 11

D 14 16 18 16

Restamos 10, 12, 9 y 14 (costos mnimos de cada fila) de cada elemento en cada una de las filas correspondientes:

1 2 3 4

A 0 3 6 3

B 0 1 3 0

C 0 3 3 2

D 0 2 4 2

En la matriz anterior trazamos el menor nmero de lneas (3), de manera tal que cubran todos los ceros (Mtodo de Flood):

1 2 3 4

A 0 3 3 3

B 0 0 0 0

C 0 2 0 2

D 0 1 1 2

En la matriz anterior trazamos el menor nmero de lneas (3), de manera tal que cubran todos los ceros (Mtodo de Flood):

1 2 3 4

A 0 2 3 2

B 1 0 1 0

C 0 1 0 1

D 0 0 1 1

Solucin Optima Unica:A-1, B-4, C-3 y D-2.Lo anterior quiere decir que Antonio va a laborar en la mquina 1 (10 horas), Bernardo en la mquina 4 (12 horas), Carlos va a trabajar en la mquina 3 (12 horas) y Diego en la mquina 2 (16 horas).

La combinacin ptima de los recursos para este problema de minimizacin de asignacin es de 50 horas, resultantes de adicionar las asignadas a cada uno de los operarios en cada una de las mquinas. Dicho valor corresponde al valor ptimo de la funcin objetivo.

PROBLEMA 6

Una empresa dedicada a la compra-venta de equipo de cmputo adquiri cuatro mquinas para ser vendidas; sin embargo, el cliente pide una prrroga de 1 mes para que le entreguen las mquinas. La empresa tiene que almacenar las cuatro durante este tiempo. Se cotizan los precios de cuatro bodegas que pueden almacenar las mquinas, los cuales se muestran en la siguiente tabla:

Bodega 1 Bodega 2 Bodega 3 Bodega 4

Mquina 1 5 15 20 10

Mquina 2 2 12 17 7

Mquina 3 15 25 30 20

Mquina 4 10 20 25 15

Determine la forma de asignar una mquina a cada bodega, de tal manera que se minimice el costo total.

Solucin

Como se puede observar, se tiene un problema balanceado, ya que se cuenta con el mismo nmero de mquinas y tareas.

Ahora construimos la tabla de asignacin, despus 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

1 5 0

15 10

20 15

10 5

2 2 0

12 10

17 15

7 5

3 15 0

25 10

30 15

20 5

4 10 0

20 10

25 15

15 5

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

1 5 0

15 0

20 0

10 0

2 2 0

12 0

17 0

7 0

3 15 0

25 0

30 0

20 0

4 10 0

20 0

25 0

15 0

De donde se obtiene una asignacin posible, la cual es ptima.

Entonces la forma de asignar una maquina a cada bodega, de tal manera que se minimice el costo total es:

Mquina 1-bodega 1

Mquina 2- Bodega 2

Mquina 3- Bodega 3

Mquina 4- Bodega 4

Con un costo mnimo de $62.

PROBLEMA 7

Una compaa va a decidir cul de cuatro vendedores debe asignar a cada uno de sus cuatro distritos de ventas. Cada vendedor est en condiciones de lograr ventas diferentes en cada distrito. A la compaa le gustara minimizar el costo de transporte total. En la siguiente tabla se muestran los estimados. Use el Mtodo Hngaro para resolver este problema. Establezca el valor ptimo de la funcin objetivo.

Distrito Vendedor 1 2 3 4

A 65 73 55 58 B 90 67 87 75 C 106 86 96 89 D 84 69 79 77

Solucin

Como se puede observar, se tiene un problema balanceado, ya que se cuenta con el mismo nmero de vendedores y distritos.

Entonces construimos la tabla de asignacin, despus 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 65 10

73 18

55 0

58 3

B 90 23

67 0

87 20

75 8

C 106 20

86 0

96 10

89 3

D 84 15

69 0

79 10

77 8

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 65 0

73 18

55 0

58 0

B 90 13

67 0

87 20

75 5

C 106 10

86 0

96 10

89 0

D 84 5

69 0

79 10

77 5

Como no se tiene una asignacin posible, tachamos los ceros con el nmero menor de lneas verticales y horizontales:

Ahora identificamos el menor de los costos no cubiertos por una lnea, se lo restamos a los costos no cubiertos por una lnea y lo sumamos a los costos que se encuentran en la interseccin de dos lneas. Los dems quedan iguales, obteniendo:

1 2 3 4

A 65 0

73 23

55 0

58 0

B 90 8

67 0

87 15

75 0

C 106 10

86 5

96 10

89 0

D 84 0

69 0

79 5

77 0

Realizando una permutacin de las columnas logramos obtener una asignacin posible y sta es ptima:

3 2 4 1

A 55 0

73 23

58 0

65 0

B 87 15

67 0

75 0

90 8

C 96 10

86 5

89 0

106 10

D 79 5

69 0

77 0

84 0

Entonces la asignacin 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 mnimo de $295.

PROBLEMA 8

Una compaa que vende carros tiene disponible un FORD y un RAMBLER, dos oficinas de la

compaa lo solicitan. Se ha decidido a enviar solo un automvil a cada oficina de manera que el

costo total sea mnimo.

La matriz de costos se muestra a continuacin:

1 2

FORD 10 5

RAMBLER 4 3

SOLUCIN CON MTODO HNGARO

Paso 1: Con base en la tabla original de costos, desarrolle otra tabla para reducir cada

fila restndole el menor valor de sta.

1 2

FORD 10 5

OPEL 4 3

Paso 2: De la tabla que encontr en el paso anterior, reduzca ahora cada columna, restndole el

menor elemento.

1 2

FORD 5 0

OPEL 1 0

Paso 3: De la tabla que desarroll en el paso 2, elimine todos los ceros cruzndolos con el menor

nmero de lneas horizontales o verticales.

1 2

FORD 4 0

OPEL 0 0

Como el nmero de lneas es igual a 2 (orden de la matriz cuadrada), el problema queda resuelto y

se procede a la asignacin.

1 2

FORD 4 0

OPEL 0 0

De donde tenemos:

El costo de enviar un automvil FORD a la oficina 2 es: 5 um

El costo de enviar un automvil RAMBLER a la oficina 1 es: 4 um

Por tanto:

El costo mnimo es: 5+4=9 um

PROBLEMA 9

SOLUCIN CON MTODO SIMPLEX

El problema es equivalente a:

Min z = 10x1 + 5x2 + 4x3 + 3x4

S.A. 10x1 + 5x2 = 1

4x3 + 3x4 = 1

10x1 + 4x3 = 1

5x2 + 3x4 = 1

xi0, i=1, 2, 3, 4

Donde los xi solo pueden ser 0 o 1.

Agregamos variables artificiales:

z 10x1 5x2 4x3 3x4 + Ms1 + Ms2 + Ms3 + Ms4 = 0 10x1 5x2 +s1 =1 4x3 +3x4 +s2 =1 10x1 +4x3 +s3 =1 5x2 +3x4 +s4 =1

Donde M>0 es un valor muy grande, de tal manera que obligue a cada si a ser muy pequeo (lo

obligue a ser cero).

Modificamos el primer rengln para que quede expresado en trminos de x1, x2, x3 y

x4solamente. De esta forma el sistema se encontrar en la forma apropiada para la Eliminacin

Gaussiana.

z 10x1 5x2 4x3 3x4 + Ms1 + Ms2 + Ms3 + Ms4 = 0

-M(10x1+5x2+s1)=-M

-M(4x3+3x4+s2)=-M

-M(10x1+4x3+s3)=-M

-M(5x2+3x4+s4)=-M

--------------------------

z (20M+10)x1 (10M+5)x2 (8M+4)x3 (6M+3)x4 = -4M

Tabla 1:

z x1 x2 x3 x4 s1 s2 s3 s4 LD

s1 0 10 5 0 0 1 0 0 0 1

s2 0 0 0 4 3 0 1 0 0 1

s3 0 10 0 4 0 0 0 1 0 1

s4 0 0 5 0 3 0 0 0 1 1

z 1 -20M-10 -10M-5 -8M-4 -6M-3 0 0 0 0 0

Tabla 2:

z x1 x2 x3 x4 s1 s2 s3 s4 LD

x1 0 1 1/2 0 0 1/10 0 0 0 1/10

s2 0 0 0 4 3 0 1 0 0 1

s3 0 0 -5 4 0 -1 0 1 0 0

s4 0 0 5 0 3 0 0 0 1 1

z 1 0 0 -8M-4 -6M-3 M+1 0 0 0 2M+1

Tabla 3:

z x1 x2 x3 x4 s1 s2 s3 s4 LD

x1 0 1 1/2 0 0 1/10 0 0 0 1/10

x3 0 0 0 1 3/4 0 1/4 0 0 1/4

s3 0 0 -5 0 -3 -1 -1 1 0 -1

s4 0 0 5 0 3 0 0 0 1 1

z 1 0 0 0 0 M+1 2M+1 0 0 4M+1

De donde tenemos que x1=1/10 y x3=1/4, es decir, son valores distintos de cero y como solo pueden

ser 0 o 1 concluimos que:

x1=1, x2=1, x3=0 y x4=0

ANALISIS DE SENSIBILIDAD

El problema nos brinda los Siguientes datos

Min z = 10x1 + 5x2 + 4x3 + 3x4

S.A. 10x1 + 5x2 = 1

4x3 + 3x4 = 1

10x1 + 4x3 = 1

5x2 + 3x4 = 1

PROBLEMA 10

Mtodo Hngaro en la asignacin (ASIGNA1).

La siguiente matriz contiene los costos para operar n=4 mquinas, por n=4 personas as calificadas en su empresa. Optimice la asignacin idnea.

Figura 4-60. Matriz de costos en ejemplo ASIGNA1.

Paso 1 .Seleccione en cada rengln i de la matriz, el menor costo C i j, (menor C i j = U i ), luego rstelo en cada elemento del rengln.

Figura 4-61. Paso 1 Mtodo Hngaro, ejemplo ASIGNA1.

Paso 2. Seleccione en cada columna j de la matriz resultante en el paso 1, el costo menor C i j, (menor Cij=Vj) y rstelo en cada elemento de la misma columna.

Figura 4-62. Paso 2 Mtodo Hngaro, ejemplo ASIGNA1.

Paso 3.Sombree los renglones y/o columnas de la matriz, de tal modo que sean los mnimos necesarias para cubrir todos los ceros.

Figura 4-63. Paso 3 Mnimo sombreado de renglones y/o columnas cubriendo todos los ceros en ejemplo ASIGNA1.

Paso 4. Seleccione entre los costos no sombreados, el nmero menor C i j, (= U i j) o bien, el menor C i j,(= V i j), y rstelo a todos los costos no sombreados; despus, sume el mismo a los costos ubicados en la interseccin de los renglones y columnas sombreados. Este paso se repite hasta lograr la solucin ptima.

Figura 4-64. Paso 4 Mtodo Hngaro, (mnimo Cij no sombreado) en ejemplo ASIGNA1.

Se tiene la solucin ptima cuando el mnimo necesario de renglones y columnas sombreadas para cubrir los ceros es n. En este problema el mnimo es n =4.

Figura 4-65. Paso 4 Mtodo Hngaro, renglones y/o columnas sombreados necesarios para cubrir los ceros n = 4, ejemplo ASIGNA1.

Entonces la asignacin ptima es la que muestra la tabla siguiente:

Figura 4-66. Asignacin ptima en ejemplo ASIGNA1.

Solucin ptima: X11 = 1, X23 = 1, X32 = 1, X44 = 1

Z = C11 X11 + C23 X23 + C32 X32 + C44 X44 = 1(1) + 10(1) + 5(1) + 5(1) = 21

En la solucin ptima, la suma de las costos Ui restados de renglones i en paso 1, ms las costos V j restados de columnas j en paso 2, ms el costo U i j V i j, restado y / o sumado, en paso 4, proporciona el correspondiente valor ptimo. As el costo es:

Z ptimo = U i + V j + U i j + V i j, para toda i, para toda j.

U i = U1 + U2 + U3 + U4 + U32 = 1 + 7 + 4 + 5 + 1 = 18

V j = V1 + V2 + V3 + V4 = 0 + 0 + 3 + 0 = 3

U i + V j = 18 + 3 = 21

Ejemplo 4-9. Mtodo Hngaro en la asignacin (ASIGNA2).

La siguiente matriz muestra costos C i j de n = 5 candidatos i ( i = 1,2,...,5 ) as calificados, en el desempeo de n = 5 actividades j ( j = 1,2,..,5 ). Con el mtodo hngaro calcule la asignacin ptima.

Figura 4-67. Matriz de costos en ejemplo ASIGNA2.

Paso 1. Reste el menor ( U i ) de los costos C i j en cada rengln:

Figura 4-68. Paso 1 Mtodo Hngaro en ejemplo ASIGNA2.

Paso 2.- Reste el menor ( V j ) de los costos C i j en cada columna:


Paso 3.-Sombree los renglones y columnas de la matriz, de tal modo que sean los mnimos necesarios para cubrir todos los ceros. La asignacin es ptima con n = 5 renglones y/o columnas. De lo contrario se contina el mtodo con el paso 4.

Paso 4.- Selecciones entre los costos no sombreados, el nmero menor C ij, (= Uij) o bien, el menor Cij, (= Vij), y rstelo a todos los costos sin sombrear; despus, sume el mismo a los costos ubicados en la interseccion de los renglones y columnas sombreados. Repita este paso hasta conseguir n = 5 (renglones y/o columnas sombreados), la solucin ptima.


En la asignacin de la tabla anterior solo se sombrean 3 renglones y una columna con ceros, pero se necesitan 5, entonces se repite el paso 4 hasta conseguirlo.

Figura 4-71. Paso 4 Mtodo Hngaro. Renglones y columnas sombreados n = 4, ejemplo ASIGNA2.

Figura 4-72. Paso 4 Mtodo Hngaro. Se logra sombrear n = 5 renglones y columnas, ejemplo ASIGNA2.

La ltima asignacin resulta con los 5 renglones y columnas sombreadas cubriendo los ceros de la tabla.

Aqu se detiene el proceso y se interpreta la asignacin ptima localizando, al menos un cero en cada rengln y en cada columna. Estos ceros indican el costo idneo asignado a la persona i en el desempeo de la actividad j, como se muestra en la siguiente matriz.


Asignacin ptima: X15 = 1, X23 = 1, X32 = 1, X44 = 1, X51 = 1

Z ptima = C15X15 + C23X23 + C32X32 + C44X44 + C51X51

Z ptima = 3(1) + 2(1) + 4(1) + 3(1) + 9(1) = 21

Z ptimo = U i + V j + U i j + V i j = 3+2+2+2+6+0+2+0+1+0+2+1 = 21

Ejemplo 4-10. Mtodo Hngaro en la asignacin (ASIGNA3).

La siguiente matriz muestra costos C i j de n = 4 candidatos i (i = 1, 2, ..., 4) as calificados, en el desempeo de n=4 actividades j (j = 1, 2, .., 4). Con el mtodo hngaro calcule la asignacin ptima.

Figura 4-74. Tablas del ejemplo ASIGNA3.

Asignacin ptima: X14 = 1, X22 = 1, X33 = 1, X41 = 1

Z ptima = C14 X14 + C22 X22 + C33 X33 + C41 X41

Z ptima = 6(1)+1(1)+2(1)+1(1) = 10; otra asignacin ptima del problema es:


Asignacin ptima: X13 = 1, X22 = 1, X34 = 1, X41 = 1

Z ptima = C14 X14 + C22 X22 + C33 X33 + C41 X41 = 7(1) +1(1) +1(1) +1(1) = 10

En ambas cumple: Z ptimo= Ui + Vj + Uij + Vij = 5+1+1+1+0+0+1+0+1 = 10

BIBLIOGRAFIA:

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-

industrial/investigaci%C3%B3n-de-operaciones/problemas-de-asignaci%C3%B3n/

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-

industrial/investigaci%C3%B3n-de-operaciones/problemas-de-asignaci%C3%B3n/

http://normelisrojas3449.blogspot.mx/p/metodo-hungaro.html

antologia metodo de asignacion unidad 2

Documents