características de asignación. método húngaro o de matriz...

UNIDAD 8

MODELO DE ASIGNACIÓN

características de asignación.

método húngaro o de matriz reducida.

Investigación de operaciones

309

Introducción

Un caso particular del modelo de transporte es el modelo de asignación, que tiene como propósito asignar personas u objetos a tareas de tal forma que se optimice algún objetivo, por ejemplo:

Históricamente el problema de asignación se resolvió util izando las mismas técnicas que se uti lizaban para el modelo de transporte, sin embargo, resultaba tedioso hacerlo de esta manera debido a las características particulares del mismo. A partir del trabajo realizado por dos matemáticos húngaros, se obtiene un algoritmo ef iciente para este modelo, el cual se conoce como método húngaro .

Iniciamos la unidad planteando el problema general de asignación, hacemos hincapié en su estructura, como en el caso especial del modelo de transporte y planteamos algunos problemas tipo. Continuamos resolviendo el modelo de asignación por el método húngaro. Terminamos la unidad estudiando algunos problemas de asignación desbalanceados.

8.1. Definición del modelo de asignación

Los problemas de asignación aparecen en varios contextos de la ingeniería económica, en donde se requiere asignar de manera óptima objetos o personas “ indivisibles” a ciertas tareas, por ejemplo:

especializados en cada tipo de soldadura existentes (mig, tig, bajo el agua, eléctrica, oxiacetilénica, etc.). Si no se cuenta con personal especializado representa un costo extra en gasto de material. Por lo tanto, se debe asignar a la persona óptima en cada puesto de trabajo para minimizar costos.

en cada máquina (recta, zigzag, ojales, etc.) para minimizar tiempos de producción.

grupo, pensando en optimizar los espacios disponibles.

Unidad 8

310

El problema clásico de asignación consiste en asignar n objetos o personas indivisibles a m tareas de una manera óptima.

Las propiedades que debe cumplir un conflicto para formularse como un problema de asignación son las siguientes:

Ci j de asignación de la persona i a la tarea j.

totales.

8.1.1. Construcción del modelo de asignación

Las variables que se util izan en el modelo de asignación son variables binarias, es decir, variables que sólo pueden tomar los valores 0 o 1. Matemáticamente se escribe:

xi j

ij

1

0

si el asignado realiza la tarea

en caso contrario para i=1, 2,... n j=1, 2, 3,... n

El costo total de la asignación es igual a la suma de los productos de cada variable x

i j por el costo asignado C

i j

Z C xij ijj

n

i

n

mín11

En las restricciones se asigna una persona a cada una de las tareas y cada tarea debe ser realizada por una persona. Esto lo representamos como:

x i n

x j n

ijj

n

iji

n

1 1 2

1 1 2

1

1

para

para

, ,...

, ,...

El modelo completo de asignación se obtiene al añadir la restricción de no negatividad y la de variables binarias:


311

Z C xij ijj

n

i

n

mín 11

Sujeto a:

x i n

x j n

ijj

n

iji

n

1 1 2

1 1 2

1

1

para

para

, ,...

, ,...

x i j

xij

ij

binarias para toda y

0

Vemos que el modelo de asignación es muy parecido al modelo de transporte, la diferencia radica en que las variables del modelo de asignación son binarias, mientras que en el modelo de transporte las variables son enteras. Entonces podemos tomar el modelo de asignación como un problema de transporte donde cada una de las personas es el origen y cada una de las tareas son los destinos. La oferta y demanda son igual a uno, es decir, cada origen tiene una sola persona y cada destino necesita sólo una persona. Los costos de capacitación representan el costo de transportar una unidad del origen i al destino j. Por lo tanto, el objetivo es encontrar la combinación que minimice los costos de asignación y cumpliendo las restricciones de oferta y demanda.

Al f inal de la unidad veremos problemas que aunque no cumplen la primera propiedad pueden formularse como problemas de asignación.

Ejemplo 1

Una empresa contrata a cuatro personas para cubrir los siguientes puestos: supervisor de acabado, supervisor de empaque, supervisor de producción, supervisor de materia prima.

A cada uno se aplica un examen de aptitudes para determinar sus habilidades. A partir del resultado de los exámenes se determina el costo que tiene su capacitación para cada uno de los puestos. Los costos se presentan en la siguiente tabla.

Unidad 8

312

Si se desea conocer la asignación de menor costo para la empresa, obtener la tabla inicial asociada al problema.

La tabla inicial asociada al problema es:

Ejemplo 2

Una empresa dedicada a la compra y venta de equipo de cómputo adquirió seis máquinas para ser vendidas, sin embargo, el cl iente pide una prórroga de un mes para que le entreguen las máquinas. La empresa tiene que almacenar las seis máquinas durante este tiempo, se cotizan los precios de seis bodegas que pueden almacenar las máquinas, los costos se muestran en la siguiente tabla.


313

Nuevamente podemos ver este problema como un modelo de transporte, donde los orígenes son las máquinas, los destinos son las bodegas y el costo Ci j es el costo de almacenaje. La oferta de cada uno de los orígenes es uno, mientras que la demanda de cada uno de los destinos también es uno. Nuevamente, las variables sólo pueden tomar el valor cero o uno. La tabla inicial de este problema es:

Ejercicio 1

1. El objetivo en el problema de asignación es ________________ los costos.2. Las variables en el problema de asignación son _______________.3. Una persona debe ser asignada a ________ tarea.4. El número de tareas y el número de personas por asignar deben ser _____________.5. Construir la tabla inicial del siguiente problema de asignación.

Se abrirán 3 centros de cómputo en diferentes ciudades de la República Mexicana, por lo que se lanza una convocatoria para que se presenten propuestas. Tres empresas interesadas hacen las siguientes ofertas:

Empresa 1: $ 3 000, $ 5 000 y $ 8 000 por cada uno de los centros.Empresa 2: $ 4 000, $ 6 000 y $ 9 000 por cada uno de los centros.Empresa 3: $ 3 500, $ 5 000 y $ 7 000 por cada uno de los centros.

Se desea asignar de manera óptima cada uno de los proyectos a cada una de las empresas.

Unidad 8

314

8.2. Método húngaro o de matriz reducida

Una vez que obtenemos el modelo de un problema de asignación, es conveniente desarrollar un procedimiento que nos permita hallar la solución óptima del mismo. Dos matemáticos húngaros desarrollaron un algoritmo ef iciente para el problema de asignación l lamado método de matriz reducida o método húngaro, en honor a sus creadores. A continuación describimos el algoritmo.

Algoritmo general

1. Se construye una tabla de n+1 por n+1, la primera columna se uti liza para colocar las etiquetas de los candidatos a asignar, mientras que la primera f i la se util iza para colocar las etiquetas de las tareas. En las intersecciones se escribe el costo de asignación asociado.

2. Se identif ica el costo menor de cada una de las f i las y se resta a los costos de la misma fila (o renglón).

3. Para la matriz que resulte del punto anterior, se identif ica el costo menor por columna y se resta a los costos de la misma columna.

4. Se buscan los llamados ceros de asignación que son únicos en su renglón y su columna, de manera que si existen dos o más ceros en un solo renglón o en una sola columna, éstos se marcan con dos líneas cruzadas. Los ceros de asignación generan la solución óptima del problema. La posición de los ceros de asignación indican la tarea que corresponde a cada persona. Cuando el número de ceros de asignación sea igual al número de columnas (o filas) hemos llegado a la solución óptima. Termina, si no, seguir con el algoritmo.

5. Si no es posible obtener todos los ceros de asignación con el proceso anterior, entonces se procede como sigue:

a) Trazamos el menor número de líneas rectas horizontales y verticales, de tal manera que se cubran todas las entradas con un cero.b) Seleccionamos el costo menor no cubierto por línea de alguna de las rectas trazadas en el inciso anterior y se lo restamos al resto de las entradas no cubiertas.


315

c) Se suma a los elementos que se encuentren en el cruce de dos líneas el elemento menor seleccionado del inciso anterior.d) Los elementos cruzados por una sola línea se copian en la nueva tabla.e) Regresa al paso 4.

Ejemplo 3

Hallar la solución óptima del siguiente problema de asignación:

Una empresa compra 3 impresoras, una de inyección de tinta, una de punto matriz y una láser. Las impresoras se deben asignar a los siguientes departamentos: recursos humanos, facturación y di rección. Debido a la frecuencia de uso en cada departamento y al tipo de impresora se tiene un costo de asignación, el cual se muestra en la siguiente tabla:

Paso 1. La tabla inicial del método húngaro es:

Paso 2. El costo menor de cada una de las f ilas es 5, 4 y 4 respectivamente. Al restar 5 a los elementos de la primer f ila, restar 4 a los de la segunda y 4 a los de la tercera, obtenemos:

Unidad 8

316

Paso 3. El costo menor de cada una de las columnas es 0, 0 y 2 respectivamente. Al restar en su columna respectiva obtenemos:

Paso 4. Buscamos los ceros de asignación. En este caso, la entrada (1, 1) tiene asignado un cero, por lo tanto la impresora de inyección de tinta va al departamento de recursos humanos. La celda (2, 2) tiene un cero de asignación, por lo tanto, la impresora de punto matriz va al departamento de facturación. La celda (3, 3) tiene un cero de asignación, por lo tanto, la impresora láser va a la dirección. El costo total mínimo de esta asignación es: 5 + 4 + 6 = $ 15.

Una manera de identificar si se puede realizar una asignación óptima es: “ si al permutar las filas podemos hacer que la diagonal principal de la tabla tenga entradas cero” .


317

Ejemplo 4

Retomando el ejemplo 1, cuya tabla de costos es:

Obtener la asignación de menor costo para la empresa.

Paso 1. La tabla inicial del método húngaro es:

Paso 2. El costo menor de cada una de las f i las es 100, 300, 250 y 150 respectivamente. Al restar el costo mínimo de cada una de las f i las correspondientes obtenemos:

Paso 3. El costo menor por columna de esta nueva tabla es 50, 0, 0 y 0. Al restar este costo mínimo a cada una de las columnas correspondientes obtenemos:

Unidad 8

318

Paso 4. Para verif icar si es posible realizar una asignación factible óptima, intercambiamos las filas para ver si es posible obtener entradas ceros en la diagonal principal.

Intercambiamos la f i la cuatro por la f ila uno y obtenemos la siguiente tabla:

El método asegura que la asignación óptima es: La persona 4 supervisa el departamento de acabado, la persona 2 al departamento de empaque, la persona tres al departamento de producción y la persona uno al departamento de materia prima, con un costo mínimo de $ 850.

Ejemplo 5

Se necesitan hacer trabajos de jardinería, pintura y plomería en una casa. Se pide a Juan, Pedro y Luis que realicen un presupuesto sobre cada uno de los trabajos de manera independiente. A continuación se muestra el costo que presentaron para las diferentes tareas.


319

Debemos asignar una tarea a cada uno de ellos, de tal manera que se minimice el costo total.

Paso 1. La tabla inicial es:

Paso 2. Los costos mínimos de cada una de las f i las son 15, 25 y 18 respectivamente. Al restar cada uno de ellos a cada una de las f ilas respectivas obtenemos:

Paso 3. Los costos mínimos de esta nueva tabla por columna son 0, 0 y 3. Al restar cada uno de estos valores a la columna respectiva obtenemos la siguiente tabla:

Paso 4. La celda (1, 2) y la (2, 2) tienen cero, pero no es cero de asignación por no ser único en su columna. La celda (3, 1) tiene un cero, pero no es de asignación. La celda (3, 3) tiene un cero pero tampoco es de asignación ya que no es único en su renglón.

Aunque permutemos las f ilas no es posible colocar ceros en la diagonal principal, como fue el caso del ejemplo 1, por lo tanto continuamos con el algoritmo:

Unidad 8

320

Trazamos el menor número de líneas rectas que cubran todas las celdas con entradas cero

a) El costo menor no cubierto es $ 2, que se resta de las entradas no cubiertas por línea alguna:

b) Le sumamos el costo menor $ 2 a las celdas donde se intersectan dos rectas:

c) La tabla que obtenemos es:

Regresamos al paso 4.

Paso 4. Si intercambiamos la f i la tres con la f ila uno, obtenemos los ceros de asignación en la diagonal principal:


321

Como el número de ceros de asignación es igual al número de columnas (f i las), por lo tanto la asignación óptima es:

A Luis el trabajo de jardinería con un costo de $ 18, a Pedro el trabajo de pintura con un costo de $ 25 y a Juan el trabajo de plomería con un costo de $ 20. El costo total mínimo es de $ 63.

Ejemplo 6

Hallar la solución óptima del problema del ejemplo 3, pero con la condición de que Juan no realiza trabajos de plomería.

Paso 1. La tabla inicial del modelo es:

Paso 2. Los costos mínimos por f i la son 15, 25 y 18, se restan a los valores en la f ila correspondiente:

Unidad 8

322

Paso 3. Los costos mínimos por columna son 0, 0 y 12, se restan a los valores de su columna correspondiente:

Paso 4. Se buscan los ceros de asignación. En la celda (2, 1) se tiene un cero de asignación ya que es único en su f i la y columna. Si en la celda (1, 2) elegimos el cero como de asignación entonces el cero de su misma columna se anula y por tanto el cero en la celda (3, 3) también será de asignación. Concluimos que:

Pedro realiza el trabajo de jardinería, Juan el de pintura y Luis el de plomería con un costo mínimo de $ 25 + $ 15 + $ 30 = $ 70.

Ejercicio 2

1. El método de matriz reducida fue desarrollado por dos matemáticos:

a) Ingleses.b) Rusos.c) Estadounidenses.d) Húngaros.

2. El tamaño de la tabla inicial del método de matriz reducida es de:

a) m nb) n mc) n nd) n–1 n–1


323

3. Para comenzar el algoritmo se selecciona el costo _______________ por f ila y se resta del resto de las entradas de la f ila.

4. Para poder l levar acabo una asignación óptima, debemos escribir la matriz reducida con ____________ en la diagonal principal.

5. Si no es posible realizar una asignación óptima, debemos trazar el _____________ número de líneas posibles que cubran todas las celdas con entrada cero.

6. Una empresa compra 3 computadoras, una Pentium I, una Pentium II y una Pentium III. Las computadoras se deben asignar a los siguientes departamentos: recursos humanos, facturación y di rección. Debido a la frecuencia de uso en cada departamento y al tipo de computadora se tiene un costo de asignación, el cual se muestra en la siguiente tabla:

Hallar la asignación óptima y el costo mínimo.

8.3. Algoritmo de solución

Una vez que aprendimos a util izar el método húngaro para la solución de problemas de asignación, es importarte que ahora estudiemos el porqué funciona.

En la primera sección de la unidad encontramos que el modelo de P. L. de asignación es el siguiente:

Z C xij ijj

n

i

n

mín 11

Unidad 8

324

Sujeto a:

x i n

x j n

ijj

n

iji

n

1 1 2

1 1 2

1

1

para

para

, ,...

, ,...

x i j

xij

ij

binarias para toda y

0

Vamos a demostrar que la solución óptima de este modelo permanece sin cambios si se suma o resta una constante a cualquier fila o columna de la matriz de costos.

Supongamos que la matriz de costos es la siguiente:

Sea pi el costo menor de cada f ila, al restar esta cantidad de cada f ila nos queda un nuevo costo, dado por: C’ i j = Ci j – pi

La tabla actualizada es:

Sea qj el costo menor por columna de la tabla anterior, al restar esta cantidad de cada columna nos queda un nuevo costo, dado por: C’’ i j = Ci j – pi –qj. La tabla actualizada es:


325

Ahora calculemos la función objetivo, en término de estos nuevos costos:

Z=(C11–p1–q1)x11+(C12–p1–q2)x12+(C21–p2–q1)x21+(C22–p2–q2)x22

Realizando algunos cambios algebraicos, podemos llegar a la siguiente expresión equivalente:

Z=C11x11+ C12x12+ C21x21+ C22x22–(p1+q1) x11–(p1+q2)x12–(p2+q1)x21

–(p2+q2)x22

Esta expresión la podemos rescribir como:

Z C x p q xij ijj

n

i

n

i j ijj

n

i

n

11 11

( )

Por restricciones del problema de asignación, sólo una de las variables de cada f i la puede ser igual a uno y el resto debe ser igual a cero, por lo tanto, la suma del segundo término es:

( )p q x p qi j ijj

n

i

n

ii

n

jj

n

11 1 1

Finalmente la función objetivo la podemos escribir como:

Z C x p q C xij ijj

n

i

n

ii

n

jj

n

ij ijj

n

i11 1 1 1

constanteii

n

Debido a que esta función objetivo dif iere de la original por sólo una constante, ambas deben tener los mismos valores de xi j, por lo tanto tienen la misma solución. Con esto demostramos que los pasos realizados en el algoritmo húngaro son válidos.

Unidad 8

326

Ejemplo 7

Una empresa compra 3 compresoras de diferentes capacidades, una grande, una mediana y una chica. Las compresoras se deben asignar a los siguientes departamentos: pintura de interiores, pintura de exteriores y pintura de detalle. Debido a la frecuencia de uso en cada departamento y al tipo de compresora se tiene un costo de asignación, el cual se muestra en la siguiente tabla:

Obtener la asignación de compresoras a los diferentes departamentos de tal manera que se minimicen los costos.

Paso 1. Al resolver el modelo, obtenemos la tabla inicial:

Paso 2. Las cantidades mínimas de cada f i la son 10, 2 y 5 respectivamente, se restan a cada valor en la f i la correspondiente:


327

Paso 3. Las cantidades mínimas por columna son 0, 0 y 2 respectivamente, se restan a cada valor en la columna correspondiente:

Paso 4. Los ceros de asignación están en la diagonal principal de la tabla, por tanto, la solución óptima del problema es: la compresora grande a pintura de exteriores, la compresora mediana a pintura de interiores y la compresora chica a pintura de detalle (solución óptima: x11=1, x22=1, x33=1) con un costo mínimo de asignación de Z=$ 19.

Ahora, si los costos se incrementan en 10% la tabla con los nuevos costos es:

Al resolver obtenemos:

Paso 2. Los costos menores por f ila son 11, 2.20 y 5.50, respectivamente, se restan de los costos en su f ila correspondiente:

Unidad 8

328

Paso 3. Los costos menores por columna son 0, 0 y 2.20, respectivamente, se restan de los costos en su columna correspondiente:

La solución óptima del problema es: x11=1, x22=1, x33=1 con un costo mínimo de asignación de Z=$ 20.90. Observamos que la solución es la misma, es decir, tenemos las mismas variables con valor uno, lo único que cambia es el valor de Z, el cual se incrementa en $ 1.90.

8.4. Problemas no balanceados

La primera condición que debe cumplir un problema de asignación es que el número de personas a asignar sea igual al número de tareas, sin embargo, en ocasiones algunos problemas no lo cumplen. En esta sección vamos a aprender cómo podemos modif icar este tipo de problemas para aplicar el algoritmo de asignación.

Ejemplo 8

Una empresa de transportes tiene cuatro diferentes modelos de camiones. Dependiendo de la pericia del conductor para manejar los cambios de la caja de velocidades, el camión consume más o menos combustible. En la actualidad la planta cuenta con tres conductores. Los costos por uso adicional de combustible se muestran en la siguiente tabla:


329

Hallar la asignación que minimiza los costos de combustible adicional.

El problema tiene tres personas para asignar, pero el número de tareas (camiones) es de cuatro, por lo tanto tenemos un problema no balanceado. Para poder utilizar el método húngaro, lo primero que debemos hacer es balancear el problema. Para hacerlo debemos agregar un conductor ficticio, el costo para este conductor en todos los casos es cero, para que de esta manera no afecte el resultado de la función objetivo. Al agregar un nuevo conductor, la tabla inicial del problema queda de la siguiente forma:

Ahora aplicamos el método húngaro.

Paso 1. La tabla inicial del modelo es:

Paso 2. Los costos mínimos por f ila son 150, 250, 100, 0, respectivamente, al restar este valor de cada una de las f ilas obtenemos la siguiente tabla:

Unidad 8

330

Paso 3. El paso tres no es necesario, debido a que todas las columnas contienen al menos un cero que proviene de la f ila de la persona f icticia.

Paso 4. Intercambiamos las f i las 1 con la 2 y la 3 con la 4 para obtener los ceros de asignación en la diagonal principal:

La asignación óptima es:

El conductor 2 al camión 1, el conductor 1 al camión 2 y el conductor 3 al camión 4. La asignación del conductor 4 al camión 3 no es posible, debido a que el conductor 4 es ficticio, por lo tanto, el camión 3 es el que no se ocupa. El costo mínimo es de $ 500.

Ejemplo 9

En un centro de cómputo se tienen tres lugares l ibres, el de programador, el de analista y el de supervisor. La empresa tiene a cuatro candidatos para ocupar los puestos; el salario de cada uno de ellos depende del puesto en donde se les coloque. En la siguiente tabla se resume esta información.

Programador Analista Supervisor Candidato 1 $ 11 800 $ 15 000 $ 20 000

Candidato 2 $ 12 500 $ 13 000 $ 14 400

Candidato 3 $ 20 000 $ 18 000 $ 23 000 Candidato 4 $ 18 000 $ 17 000 $ 16 000 En este caso, tenemos cuatro personas para tres tareas, por lo tanto el problema es desbalanceado. Tenemos que agregar un puesto f icticio para balancear el problema, con un costo de cero para todos los candidatos:


331

Util izamos el método húngaro.

Paso 1. La tabla inicial es:

Paso 2. Este paso no tiene ningún sentido aplicarlo, porque el costo menor por f i la es cero, por lo tanto la tabla queda igual al paso uno.

Paso 3. Las cantidades mínimas por columna son 11 800, 13 000, 14 400, 0, respectivamente, se restan a cada valor en la columna correspondiente:

Unidad 8

332

Paso 4. No es posible obtener la matriz con ceros en la diagonal, sólo tenemos 3 ceros de asignación y existen 4 columnas, por lo tanto debemos continuar con el algoritmo.

Paso 5. a)

b) El costo menor no tachado es 1 600, lo restamos al resto de las entradas l ibres.

c) Sumamos el costo menor (1 600) a las celdas donde se intersectan dos rectas.

Regresamos al paso 4.

Paso 4. Buscamos los ceros de asignación:


333

Intercambiamos la f i la 3 por la 4.

Por lo tanto la asignación óptima es candidato 1 a programador, candidato 2 a analista y candidato 4 a supervisor. El candidato 3 no se emplea. El costo de esta asignación es $ 40 800.

Ejercicio 3

1. Decimos que un problema de asignación es no balanceado si el número de personas a asignar y el número de tareas a ocupar son:

a) Diferentes.b) Positivas.c) Negativas.d) Iguales.

2. Si tenemos una tarea más que personas para asignar debemos crear:

a) Una tarea f icticia.b) Una persona f icticia.c) Dos tareas f icticias.d) Asignar dos personas a una tarea.

Unidad 8

334

3. El costo de asignación para una columna f icticia debe ser igual a:

a) 10b) 5c) 0d) Negativa.

4. En un laboratorio farmacéutico se tienen tres puestos libres, el de control de calidad, el de producción y el de supervisor. La empresa tiene a cuatro candidatos para ocupar los puestos. El salario de cada uno de ellos depende del puesto en donde se les coloque. En la siguiente tabla se resume esta información.

Hallar la asignación que optimiza los recursos.

Ejercicios propuestos

Resolver el siguiente problema de asignación:

1. Los tres hijos del sr. Rodrigo Uribe: Miguel, Pedro y Luis quieren obtener recursos para asistir a una f iesta. Su padre les ofrece pagarles si realizan algunas mejoras a su automóvil. Las mejoras posibles son: lavar el exterior, lavar el interior y cambiar el aceite. Las reglas son que cada uno sólo puede realizar una tarea y cada uno debe hacer una oferta secreta de cuánto cobraría por cada una de las tareas. En la siguiente tabla se muestran estos costos.


335

Hallar la asignación óptima.

2. Resolver el problema de asignación, cuya matriz de costos se muestra a continuación.

3. En un centro de cómputo se tienen tres lugares libres, el de programador, el de analista y el de supervisor. La empresa tiene a cuatro candidatos para ocupar los puestos; el salario de cada uno de ellos depende del puesto en donde se les coloque. En la siguiente tabla se resume esta información:

Además el candidato 1 no puede ocupar el puesto de analista y el candidato 3 no puede ocupar el puesto de programador. Hallar la asignación óptima y el costo total mínimo.

Unidad 8

336

Autoevaluación

1. El problema de asignación balanceado tiene n fuentes y:

a) n+1 destinos.b) n destinos.c) n–1 destinos.d) n–2 destinos.

2. El método óptimo para resolver problemas de asignación es:

a) Símplex.b) Símplex dual.c) Modi.d) Húngaro.

3. Las variables en el modelo de asignación son:

a) Fraccionarias.b) Negativas.c) No restringidas.d) Binarias.

4. El objetivo del modelo de asignación es:

a) Minimizar costos.b) Maximizar costos.c) Minimizar ganancias.d) Minimizar util idades.

5. El paso 2 del método húngaro consiste en restar el costo menor de cada f ila al resto de los elementos de:

a) La columna.b) De toda la matriz.c) De la diagonal.d) La misma f i la.


337

6. Si no es posible obtener una asignación factible, debemos trazar el menor número de rectas que cubran todas las entradas con valor:

a) Cero.b) Negativo.c) Positivo.d) Mayor a 5.

7. La solución óptima del siguiente problema de asignación es:

a) x12=1, x21=1, x33=1b) x13=1, x21=1, x33=1c) x11=1, x22=1, x33=1d) x12=1, x33=1, x31=1

8. El costo de la asignación óptima del siguiente problema es:

a) $ 630b) $ 520c) $ 360d) $ 620

Unidad 8

338

9. El costo de la asignación óptima del siguiente problema es:

a) $ 630b) $ 520c) $ 640d) $ 620

10. El número de variables distintas de cero en un problema balanceado de asignación es:

a) n+1b) nc) n+m–1d) 2n–1


339

Respuestas a los ejercicios

Ejercicio 1

1. Minimizar.2. Binarias.3. Una.4. Iguales.5.

Ejercicio 2

1. d)2. a)3. Menor.4. Ceros.5. Menor.6. x

11=1, x

22=1, x

33=1 con Z

mín=15

Ejercicio 31. a)2. b)3. c)4. x

11=1, x

22=1, x

43=1 Z

mín=$ 41 400

Unidad 8

340

Respuestas a los ejercicios propuestos

1. x12

=1, x21

=1, x33

=1 Zmín

=$ 27

2. x11=1, x

23=1, x

32=1, x

44=1 Z

mín=$ 21

3. x11=1, x

22=1, x

43=1 Z

mín= $ 41 800

Respuestas a la autoevaluación

1. b)2. d)3. d)4. a)5. d)6. a)7. c)8. a)9. c)10. b)

características de asignación. método húngaro o de matriz...

Documents