(TALLER) Unidad 6 Programación lineal entera Objetivo general Objetivos específicos El alumno: Resolverá modelos de programación lineal entera por el método de ramificación y acotamiento y por el método de Gomory. Diferenciará los modelos de P.L. de los modelos de P.L. entera. Utilizará el método de ramificación y acotamiento para resolver modelos de programación lineal entera. Utilizará el método de Gomory para resolver modelos de programación lineal entera. Recomendaciones Refuerce los conocimientos de los alumnos por medio de prácticas y tareas, haciendo énfasis en la construcción de modelos matemáticos. Los ejercicios de este taller se presentan completamente resueltos, paso por paso y con dificultad graduada, de manera que también puede utilizarlos para repasar en clase alguna parte del proceso de solución que considere importante. Si además decide utilizar otros ejercicios que no se encuentren en este material, verifique que cumplan con los objetivos establecidos.
Transcript
(TALLER)
Unidad 6
Programación lineal entera
Objetivo general Objetivos específicos
El alumno:
Resolverá modelos de programación lineal entera por el método de ramificación y acotamiento y por el método de Gomory.
Diferenciará los modelos de P.L. de los modelos de P.L. entera.
Utilizará el método de ramificación y acotamiento para resolver modelos de programación lineal entera.
Utilizará el método de Gomory para resolver modelos de programación lineal entera.
Recomendaciones
Refuerce los conocimientos de los alumnos por medio de prácticas y tareas, haciendo énfasis en la construcción de modelos matemáticos.
Los ejercicios de este taller se presentan completamente resueltos, paso por paso y con dificultad graduada, de manera que también puede utilizarlos para repasar en clase alguna parte del proceso de solución que considere importante.
Si además decide utilizar otros ejercicios que no se encuentren en este material, verifique que cumplan con los objetivos establecidos.
Clasificación de ejercicios de acuerdo al nivel de dificultad:
. Simple . Medio . Avanzado . Aplicación
Ejercicios con nivel de dificultad:
Simple
1. Considere el problema de presupuestar el capital donde participan tres proyectos para ejecutarse en los siguientes tres años. Los rendimientos esperados para cada proyecto y los gastos anuales (en miles de unidades monetarias) se muestran en seguida. Suponga que cada proyecto aprobado será ejecutado sobre el periodo de tres años y que el objetivo es elegir aquellos que maximicen los rendimientos totales.
Proyecto Año 1 Año 2 Año 3 Rendimientos
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
Fondos disponibles máximos 25 25 25
Determine si se trata de un problema de P.L. o P.L.E.
Solución
Se trata de un problema de P.L.E. ya que cada variable sólo puede tomar el valor de 0 o 1.
Recomendaciones
Ejemplifique al alumno una posible asignación, para que observe que cada variable sólo puede tomar el valor de 0 o 1.
2. Considere el problema de planear la producción de 2,000 unidades de un cierto producto que se fabrican en tres máquinas. Los costos de preparación, de producción por unidad y la
capacidad de producción máxima para cada máquina están tabulados a continuación. El objetivo es minimizar el costo total de producción del lote requerido.
Máquina Costo de preparación Costo de producción/unidad Capacidad
1 100 10 600
2 300 2 800
3 200 5 1200
Determine si se trata de un problema de P.L. o P.L.E.
Solución
Se trata de un problema de P.L.E. ya que cada variable sólo puede tomar valores enteros.
Recomendaciones
Ejemplifique al alumno cuáles son los posibles valores que puede tomar cada variable.
3. Utilizando el método de ramificación y acotamiento resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas Solución
0 -120 -80 0 0 0
0 2 1 1 0 6
0 7 8 0 1 28
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 400/9 40/9 391.11
0 1 0 8/9 -1/9 20/9
0 0 1 -7/9 2/9 14/9
La solución óptima es: y con un valor de .
Ahora elegimos la variable y formulamos los problemas 1 y 2:
y
Resolvemos el problema 1:
La tabla simplex inicial es:
Variables básicas Solución
1 -120 -80 0 0 0 0
0 2 1 1 0 0 6
0 7 8 0 1 0 28
0 1 0 0 0 1 2
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 0 10 -70 380
0 0 0 1 -1/8 -9/8 1/4
0 0 1 0 1/8 -7/8 7/4
0 1 0 0 0 1 2
La solución óptima es: y con un valor de .
Resolvemos el problema 2 por el método dual simplex cambiando la función objetivo:
La tabla simplex inicial es:
Variables básicas Solución
1 120 80 0 0 0 0
0 2 1 1 0 0 6
0 7 8 0 1 0 28
0 -1 0 0 0 1 -3
La tabla simplex óptima es:
Variables básicas Solución
1 0 80 0 0 120 -360
0 0 1 1 0 2 0
0 0 8 0 1 7 7
0 1 0 0 0 -1 3
La solución óptima es: y con un valor de .
Por lo tanto el valor óptimo de nuestro problema original es: y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
4. Utilizando el método de ramificación y acotamiento resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas Solución
0 -1 -1 0 0 0
0 1 5 1 0 5
0 2 1 0 1 4
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 1/9 8/18 7/3
0 0 1 2/9 -1/9 2/3
0 1 0 -1/9 8/18 5/3
La solución óptima es: y con un valor de .
Ahora elegimos la variable y formulamos los problemas 1 y 2:
y
Resolvemos el problema 1:
La tabla simplex inicial es:
Variables básicas Solución
1 -1 -1 0 0 0 0
0 1 5 1 0 0 5
0 2 1 0 1 0 4
0 1 0 0 0 1 1
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 1/5 0 4/5 9/5
0 0 1 1/5 0 -1/5 4/5
0 0 0 -1/5 1 -9/5 6/5
0 1 0 0 0 1 1
La solución óptima es: y con un valor de .
Resolvemos el problema 2 por el método dual simplex cambiando la función objetivo:
La tabla simplex inicial es:
Variables básicas Solución
1 1 1 0 0 0 0
0 1 5 1 0 0 5
0 2 1 0 1 0 4
0 -1 0 0 0 1 -2
La tabla simplex óptima es:
Variables básicas Solución
1 0 1 0 0 1 -2
0 0 5 1 0 0 3
0 0 1 0 1 -2 8
1 0 0 0 0 -1 2
La solución óptima es: y con un valor de .
Por lo tanto el valor óptimo de nuestro problema original es: y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
5. Utilizando el método de ramificación y acotamiento resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas Solución
0 -11 -9 0 0 0
0 1 2 1 0 1
0 3 1 0 1 2
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 6/15 17/15 126/15
0 0 1 3/5 -1/5 1/5
0 1 0 -1/5 6/15 9/15
La solución óptima es: y con un valor de .
Ahora elegimos la variable y formulamos los problemas 1 y 2:
y
Resolvemos el problema 1:
La tabla simplex inicial es:
Variables básicas Solución
1 -11 -9 0 0 0 0
0 1 2 1 0 0 1
0 3 1 0 1 0 2
0 1 0 0 0 1 0
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 9/2 0 13/2 9/2
0 0 1 1/2 0 -1/2 1/2
0 0 0 -1/2 1 -5/2 3/2
0 1 0 0 0 1 0
La solución óptima es: y con un valor de .
Para el problema 2 no existe región factible, por lo cual no existe solución.
Entonces sólo trabajamos el problema 1 de donde se obtienen los problemas 3 y 4:
y
Para el problema 3 la única solución óptima es: y con un valor de , ya que la región factible sólo es el origen.
Para el problema 4 no existe región factible, por lo cual no existe solución.
Por lo tanto el valor óptimo de nuestro problema original es: y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
6. Utilizando el método de Gomory resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas Solución
1 -4 -2 0 0
0 4 10 1 34
La tabla simplex óptima es:
Variables básicas Solución
1 0 8 1 34
0 1 5/2 1/4 17/2
La solución óptima es: y con un valor de .
Como la variable no es entera elegimos este renglón para trabajar; entonces la ecuación asociada es:
Escribimos los coeficientes como una combinación de un número entero y una parte fraccionaria entre cero y uno:
Pasamos todos los coeficientes fraccionarios al lado izquierdo:
Después hacemos la parte izquierda mayor o igual que cero, la incorporamos a la tabla óptima del problema y aplicamos el método dual simplex para obtener la solución.
La tabla simplex inicial es:
Variables básicas Solución
1 0 8 1 0 34
0 1 5/2 1/4 0 17/2
0 0 -1/2 -1/4 1 -1/2
La tabla simplex óptima es:
Variables básicas
Solución
1 0 6 0 4 32
0 1 2 0 1 8
0 0 2 1 -4 2
Por lo tanto el valor óptimo de nuestro problema original es: y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
Ejercicios con nivel de dificultad:
Medio
1. Utilizando el método de ramificación y acotamiento resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas Solución
1 -3 -2 0 0 0 0 0
0 1 2 1 0 0 0 6
0 2 1 0 1 0 0 8
0 -1 1 0 0 1 0 1
0 0 1 0 0 0 1 2
La tabla simplex óptima es:
Variables básicas
Solución
1 0 0 1/3 8/6 0 0 38/3
0 0 1 2/3 -1/3 0 0 4/3
0 1 0 -1/3 2/3 0 0 10/3
0 0 0 -1 1 1 0 3
0 0 0 -2/3 1/3 0 1 2/3
La solución óptima es: y con un valor de .
Ahora elegimos la variable y formulamos dos problemas:
y
Resolvemos el problema 1:
Variables básicas Solución
1 -3 -2 0 0 0 0 0 0
0 1 2 1 0 0 0 0 6
0 2 1 0 1 0 0 0 8
0 -1 1 0 0 1 0 0 1
0 0 1 0 0 0 1 0 2
0 1 0 0 0 0 0 1 3
La tabla simplex óptima es:
Variables básicas Solución
1 0 2 1 0 0 0 0 12
0 0 1 1/2 0 0 0 -1/2 3/2
0 0 0 -1/2 1 0 0 -3/2 1
0 0 0 -1/2 0 1 0 3/2 -1
0 0 0 -1/2 0 0 1 1/2 1
0 1 0 0 0 0 0 1 3
La solución óptima es: y con un valor de .
Resolvemos el problema 2 por el método dual simplex cambiando la función objetivo:
Variables básicas Solución
1 3 2 0 0 0 0 0 0
0 1 2 1 0 0 0 0 6
0 2 1 0 1 0 0 0 8
0 -1 1 0 0 1 0 0 1
0 0 1 0 0 0 1 0 2
0 -1 0 0 0 0 0 1 -4
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 0 0 0 0 3 12
0 0 2 1 0 0 0 1 2
0 0 1 0 1 0 0 2 0
0 0 1 0 0 1 0 1 5
0 0 1 0 0 0 1 0 2
0 1 0 0 0 0 0 1 4
La solución óptima es: y con un valor de .
Como podemos observar, en ambos problemas se tiene el mismo valor óptimo por lo cual la
solución a nuestro problema original es: y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
2. Utilizando el método de Gomory resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas Solución
1 -5 -1 -1 0 0 0
0 1 1 2 1 0 10
0 6 2 2 0 1 10
La tabla simplex óptima es:
Variables básicas Solución
1 0 2/3 2/3 0 5/6 25/3
0 0 2/3 5/3 1 -1/6 25/3
0 1 1/3 1/3 0 1/6 5/3
La solución óptima es: , y con un valor de .
Como la variable no es entera elegimos este renglón para trabajar; entonces la ecuación asociada es:
Escribimos los coeficientes como una combinación de un número entero y una parte fraccionaria entre cero y uno:
Pasamos todos los coeficientes fraccionarios al lado izquierdo:
Después hacemos la parte izquierda mayor o igual que cero, la incorporamos a la tabla óptima del problema y aplicamos el método dual simplex para obtener la solución.
La tabla simplex inicial es:
Variables básicas Solución
1 0 2/3 2/3 0 5/6 0 25/3
0 0 2/3 5/3 1 -1/6 0 25/3
0 1 1/3 1/3 0 1/6 0 5/3
0 0 -1/3 -1/3 0 -1/6 1 -2/3
La tabla simplex óptima es:
Variables básicas Solución
1 0 -1 -1/6 0 0 1 5
0 0 1 2 1 0 -1 9
0 1 0 0 0 0 1 1
0 0 2 2 0 1 -6 4
Por lo tanto el valor óptimo de nuestro problema original es: , y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
Ejercicios con nivel de dificultad:
.
Avanzado
1. Utilizando el método de Gomory resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas
Solución
1 -1 -9 -1 0 0 0
0 1 2 3 1 0 9
0 3 2 2 0 1 15
La tabla simplex óptima es:
Variables básicas Solución
1 7/2 0 25/2 9/2 0 81/2
0 1/2 1 3/2 1/2 0 9/2
0 2 0 -1 -1 1 6
La solución óptima es: y con un valor de .
Como la variable no es entera elegimos este renglón para trabajar; entonces la ecuación asociada es:
Escribimos los coeficientes como una combinación de un número entero y una parte fraccionaria entre cero y uno:
Pasamos todos los coeficientes fraccionarios al lado izquierdo:
Después hacemos la parte izquierda mayor o igual que cero, la incorporamos a la tabla óptima del problema y aplicamos el método dual simplex para obtener la solución.
La tabla simplex inicial es:
Variables básicas Solución
1 7/2 0 25/2 9/2 0 0 81/2
0 1/2 1 3/2 1/2 0 0 9/2
0 2 0 -1 -1 1 0 6
0 -1/2 0 -1/2 -1/2 0 1 -1/2
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 9 1 0 7 37
0 0 1 1 0 0 1 4
0 0 0 -3 -3 1 4 4
0 1 0 1 1 0 -2 1
Por lo tanto el valor óptimo de nuestro problema original es: , y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
2. Utilizando el método de Gomory resuelve el siguiente modelo de P.L.E.:
Solución
Resolvemos el problema sin considerar que las variables sean enteras:
La tabla simplex inicial es:
Variables básicas Solución
0 -1 -1 0 0 0
0 1 5 1 0 6
0 2 1 0 1 4
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 1/9 8/18 7/3
0 0 1 2/9 -1/9 2/3
0 1 0 -1/9 8/18 5/3
La solución óptima es: y con un valor de .
Como la variable no es entera elegimos este renglón para trabajar; entonces la ecuación asociada es:
Escribimos los coeficientes como una combinación de un número entero y una parte fraccionaria entre cero y uno:
Pasamos todos los coeficientes fraccionarios al lado izquierdo:
Después hacemos la parte izquierda mayor o igual que cero, la incorporamos a la tabla óptima del problema y aplicamos el método dual simplex para obtener la solución.
La tabla simplex inicial es:
Variables básicas Solución
1 0 0 1/9 8/18 0 7/3
0 0 1 2/9 -1/9 0 2/3
0 1 0 -1/9 8/18 0 5/3
0 0 0 -2/9 1/9 1 -2/3
La tabla simplex óptima es:
Variables básicas Solución
1 0 0 0 1/2 1/2 2
0 0 1 0 0 1 0
0 1 0 0 7/18 -1/2 2
0 0 0 1 -1/2 -9/2 3
Por lo tanto el valor óptimo de nuestro problema original es: y .
Recomendaciones
Indique al alumno que debe desarrollar las tablas intermedias.
TRONCO COMÚN INGENIERÍA
Investigación de Operaciones 4º Cuatrimestre
(TALLER)
Integración: Unidades 7 y 8
Modelo de Transporte y Modelo de Asignación
Recomendaciones
Refuerce los conocimientos de los alumnos por medio de prácticas y tareas, haciendo énfasis en la construcción de modelos matemáticos.
Los ejercicios de este taller se presentan completamente resueltos, paso por paso y con dificultad graduada, de manera que también puede utilizarlos para repasar en clase alguna parte del proceso de solución que considere importante.
Si además decide utilizar otros ejercicios que no se encuentren en este material, verifique que cumplan con los objetivos establecidos.
Clasificación de ejercicios de acuerdo al nivel de dificultad:
. Simple . Medio . Avanzado . Aplicación
Unidad 7. Modelo de Transporte.
Objetivo general Objetivos específicos
El alumno:
Resolverá problemas de transporte balanceados y no balanceados por los métodos computacionales conocidos como: Método de la esquina noreste, Método de aproximación de Vogel y Método de Modi.
El alumno:
Resolverá problemas de transporte utilizando los métodos computacionales conocidos como: Método de la esquina noreste, Método de aproximación de Vogel y Método de Modi.
Resolverá problemas de transporte no balanceados.
Ejercicios con nivel de dificultad:
Simple
1. Se envían automóviles por tren desde tres centros de distribución a cinco distribuidores. El costo de envío está basado en la distancia recorrida. La siguiente tabla hace un resumen de las distancias (en millas) de recorrido entre los centros de distribución y los distribuidores. También se muestran las cifras mensuales de oferta y demanda calculadas en números de automóviles. Dado que el costo de transporte por milla recorrida por el tren es $10, encuentre una solución óptima por el Método de la esquina noreste y el Método de Modi.
Centros
de
Distribuidores Oferta
10 15 20 2.1 20 400
Distribución5 7 6 6.5 8 200
5 10 15 15 13 150
Demanda 100 200 150 160 140
Solución
Primero calculamos: oferta total = 400+200+150=750 y demanda total = 100+200+150+160+140=750. Como son iguales tenemos un problema balanceado.
Después construimos la tabla de transporte asociada e iniciamos asignando 100 a la celda (1,1) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 5 Oferta
1 100
100
150 200 210 200 400
300
2 50 70 60 65 80 200
3 50 100 150 150 130 150
Dem. 100
0
200 150 160 140
Ahora asignamos 200 a la celda (1,2) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 5 Oferta
1 100
100
150
200
200 210 200 400
100
2 50 70 60 65 80 200
3 50 100 150 150 130 150
Dem. 100 200 150 160 140
0 0
Después asignamos 100 a la celda (1,3) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 5 Oferta
1 100
100
150
200
200
100
210 200 400
0
2 50 70 60 65 80 200
3 50 100 150 150 130 150
Dem. 100
0
200
0
150
50
160 140
Ahora asignamos 50 a la celda (2,3) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 5 Oferta
1 100
100
150
200
200
100
210 200 400
0
2 50 70 60
50
65 80 200
150
3 50 100 150 150 130 150
Dem. 100 200 150 160 140
0 0 0
Entonces asignamos 150 a la celda (2,4) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 5 Oferta
1 100
100
150
200
200
100
210 200 400
0
2 50 70 60
50
65
150 80
200
0
3 50 100 150 150 130 150
Dem. 100
0
200
0
150
0
160
10
140
En seguida, ajustamos el renglón restante como se muestra en la tabla:
1 2 3 4 5 Oferta
1 100
100
150
200
200
100
210 200 400
0
2 50 70 60
50
65
150 80
200
0
3 50 100 150 150
10
130
140
150
0
Dem. 100
0
200
0
150
0
160
0
140
0
Entonces tenemos una solución inicial:
x1,1=100, x1,2=200, x1,3=100, x2,3=50, x2,4=150, x3,4=10 y x3,5,=140 con un costo mínimo de $92,450.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=100 u1=0, v1=100
Celda (1,2) u1+v2=150 v2=150
Celda (1,3) u1+v3=200 v3=200
Celda (2,3) u2+v3=60 u2=-140
Celda (2,4) u2+v4=65 v4=205
Celda (3,4) u3+v4=150 u3=-55
Celda (3,5) u3+v5=130 v5=185
Después calculamos los costos marginales asociados:
Celda (1,4) 210-u1-v4=5
Celda (1,5) 200-u1-v5=15
Celda (2,1) 50-u2-v1=90
Celda (2,2) 70-u2-v2=60
Celda (2,5) 80-u2-v5=45
Celda (3,1) 50-u3-v1=5
Celda (3,2) 100-u3-v2=5
Celda (3,3) 150-u3-v3=5
Como todos los costos marginales son positivos, la solución inicial es óptima.
Entonces la asignación que minimiza el costo total de transporte es:
C. de distribución 1 transporta 100 automóviles al distribuidor 1.
C. de distribución 1 transporta 200 automóviles al distribuidor 2.
C. de distribución 1 transporta 100 automóviles al distribuidor 3.
C. de distribución 2 transporta 50 automóviles al distribuidor 3.
C. de distribución 2 transporta 150 automóviles al distribuidor 4.
C. de distribución 3 transporta 10 automóviles al distribuidor 4.
C. de distribución 3 transporta 140 automóviles al distribuidor 5.
Con un costo mínimo de $92,450.
Recomendaciones
Indique al alumno que debe tener cuidado al aplicar el Método de Modi.
2. Tres refinerías con capacidades diarias máximas de 6, 5 y 8 millones de galones de gasolina reparten a tres áreas de distribución con demandas diarias de 4, 8 y 7 millones de galones del combustible. La gasolina se transporta a las tres áreas de distribución a través de una red de tubería. El costo de transporte se calcula con base en la longitud de la tubería aproximadamente a 1 peso por 100 galones por milla recorrida. La tabla de distancias es la siguiente:
Refinería Área de distribución
1 2 3
1 120 180 160
2 300 100 80
3 200 250 120
Encuentre la combinación que minimice los costos de transportación. Utilice el método de Vogel y el Método de Modi.
Solución
Primero calculamos: oferta total = 6+5+8=19 y demanda total = 4+8+7=19; como son iguales tenemos un problema balanceado.
Después construimos la tabla de transporte asociada; posteriormente calculamos las penalidades asociadas a cada renglón y columna restando los dos costos menores por renglón y columna. En seguida identificamos el renglón o columna con la penalidad más grande (en este caso se tienen varias penalidades con el valor de 80). Como la elección es arbitraria elegimos la columna dos, asignamos 5 a la variable x2,2 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 Oferta Pen. 1
1 120 180 160 6 40
2 300 100
5 80
5
0
20
3 200 250 120 8 80
Dem. 4 8
3
7
Pen. 1 80 80 40
Ahora calculamos las penalidades asociadas a cada renglón y columna, menos al renglón 2. Después identificamos el renglón o columna con la penalidad más grande (en este caso se tienen dos penalidades con el valor de 80). Como la elección es arbitraria elegimos la columna uno, asignamos 4 a la variable x1,1 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 Oferta Pen. 2
1 120
4
180 160 6
2
40
2 300 100
5 80
5
0
X
3 200 250 120 8 80
Dem. 4 8 7
0 3
Pen. 2 80 70 40
Entonces calculamos las penalidades asociadas a cada renglón y columna, menos al renglón 2 y columna 1. Después identificamos el renglón o columna con la penalidad más grande, que en este caso es el renglón tres, asignamos 7 a la variable x3,3 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 Oferta Pen. 3
1 120
4
180 160 6
2
20
2 300 100
5 80
5
0
X
3 200 250 120
7
8
1
80
Dem. 4
0
8
3
7
0
Pen. 3 X 70 40
Después ajustamos el renglón restante, como se muestra en la tabla:
1 2 3 Oferta
1 120
4
180
2
160 6
0
2 300 100 80 5
0
5
3 200 250
1
120
7
8
0
Dem. 4
0
8
0
7
0
Entonces tenemos una solución inicial:
x1,1=4, x1,2=2, x2,2=5, x3,2=1 y x3,3=7, con un costo mínimo de $2,430.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=120 u1=0, v1=120
Celda (1,2) u1+v2=180 v2=180
Celda (2,2) u2+v2=100 u2=-80
Celda (3,2) u3+v2=250 u3=70
Celda (3,3) u3+v3=120 v3=50
Después calculamos los costos marginales asociados:
Celda (1,3) 160-u1-v3=110
Celda (2,1) 300-u2-v1=260
Celda (2,3) 80-u2-v3=110
Celda (3,1) 200-u3-v1=10
Como todos los costos marginales son positivos la solución inicial es óptima.
Entonces el costo mínimo de transporte es de $2,430 y la asignación que lo minimiza es:
Que la refinería 1 transporta 4 millones de galones de gasolina al área de distribución 1.
Que la refinería 1 transporta 2 millones de galones de gasolina al área de distribución 2.
Que la refinería 2 transporta 5 millones de galones de gasolina al área de distribución 2.
Que la refinería 3 transporta 1 millón de galones de gasolina al área de distribución 2.
Que la refinería 3 transporta 7 millones de galones de gasolina al área de distribución 3.
Recomendaciones
Indique al alumno que debe tener cuidado al calcular las penalidades.
Mencione al grupo que deben tener cuidado al aplicar el Método de Modi.
Ejercicios con nivel de dificultad:
Medio
1. Tres plantas de energía eléctrica con capacidades de 25, 40 y 50 millones de kilovatios/hora, proporcionan electricidad a tres ciudades. La demanda máxima es de 30, 35 y 25 millones de kilovatios/hora. El costo de transporte por millón de kilovatio/hora está dado en la siguiente tabla:
Ciudad 1 Ciudad 2 Ciudad 3
Planta 1 $600 $700 $700
Planta 2 $320 $300 $350
Planta 3 $500 $480 $450
Encuentre una solución óptima por el Método de la esquina noreste y el Método de Modi.
Solución
Primero calculamos: oferta total = 25+40+50=115 y demanda total = 30+35+25=90. Como no son iguales tenemos un problema no balanceado, esto implica añadir una 4ta. ciudad ficticia con una demanda de 25, para tener un problema balanceado.
Después construimos la tabla de transporte asociada e iniciamos asignando 25 a la celda (1,1) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 Oferta
1 600 700 700 0 25
25
0
2 320 300 350 0 40
3 500 480 450 0 50
Dem. 30
5
35 25 25
Ahora asignamos 5 a la celda (2,1) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 Oferta
1 600
25
700 700 0 25
0
2 320
5
300 350 0 40
35
3 500 480 450 0 50
Dem. 30
0
35 25 25
En seguida asignamos 35 a la celda (2,2) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 Oferta
1 600
25 700
700 0 25
0
2 320
5
300
35
350 0 40
0
3 500 480 450 0 50
Dem. 30
0
35
0
25 25
Posteriormente asignamos 0 a la celda (3,2) y ajustamos la oferta y la demanda como se muestra en la tabla:
1 2 3 4 Oferta
1 600
25
700 700 0 25
0
2 320
5
300
35
350 0 40
0
3 500 480
0
450 0 50
Dem. 30
0
35
0
25 25
Después ajustamos el renglón restante, como se muestra en la tabla:
1 2 3 4 Oferta
1 600
25 700
700 0 25
0
2 320
5
300
35
350 0 40
0
3 500 480
0
450
25
0
25
50
0
Dem. 30
0
35
0
25
0
25
0
Entonces tenemos una solución inicial:
x1,1=25, x2,1=5, x2,2=35, x3,2=0, x3,3=25 y x3,4=25, con un costo mínimo de $38,350.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=600 u1=0, v1=600
Celda (2,1) u2+v1=320 u2=-280
Celda (2,2) u2+v2=300 v2=580
Celda (3,2) u3+v2=480 u3=-100
Celda (3,3) u3+v3=450 v3=550
Celda (3,4) u3+v4=0 v4=100
Después calculamos los costos marginales asociados:
Celda (1,2) 700-u1-v2=120
Celda (1,3) 700-u1-v3=150
Celda (1,4) 0-u1-v4=-100
Celda (2,3) 350-u2-v3=80
Celda (2,4) 0-u2-v4=180
Celda (3,1) 500-u3-v1=0
Como tenemos un valor negativo la solución inicial no es óptima. Elegimos la celda (1,4) para construir una trayectoria cerrada:
1 2 3 4 Oferta
1 600
25-
700 700 0
25
0
2 320 300 350 0 40
5+
35- 0
3 500 480
0+
450
25
0
25-
50
0
Dem. 30
0
35
0
25
0
25
0
Como todas las asignaciones deben ser mayores o iguales a cero, obtenemos las siguientes desigualdades:
El máximo valor de que satisface todas las desigualdades es 25; realizamos los ajustes a cada una de las celdas:
1 2 3 4 Oferta
1 600
0
700 700 0
25
0
2 320
30
300
10
350 0 40
0
3 500 480
25
450
25
0 50
0
Dem. 30
0
35
0
25
0
25
0
Entonces tenemos una solución inicial:
x1,1=0, x1,4=25, x2,1=30, x2,2=10, x3,2=25 y x3,3=25, con un costo mínimo de $35,850.00.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=600 u1=0, v1=600
Celda (1,4) u1+v4=0 v4=0
Celda (2,1) u2+v1=320 u2=-280
Celda (2,2) u2+v2=300 v2=580
Celda (3,2) u3+v2=480 u3=-100
Celda (3,3) u3+v3=450 v3=550
Después calculamos los costos marginales asociados:
Celda (1,2) 700-u1-v1=100
Celda (1,3) 700-u1-v3=150
Celda (2,3) 350-u2-v3=80
Celda (2,4) 0-u2-v4=280
Celda (3,1) 500-u3-v1=0
Celda (3,4) 0-u3-v4=100
Como todos los costos marginales son positivos la solución inicial es óptima.
Nota: La 4ta. ciudad es ficticia, por lo que no existe suministro de la planta 1 a esta ciudad.
Entonces la asignación que minimiza el costo total de transporte es:
Que la planta 1 transporta 0 millones de kilovatios/hora a la ciudad 1.
Que la planta 2 transporta 30 millones de kilovatios/hora a la ciudad 2.
Que la planta 2 transporta 10 millones de kilovatios/hora a la ciudad 2.
Que la planta 3 transporta 25 millones de kilovatios/hora a la ciudad 2.
Que la planta 3 transporta 25 millones de kilovatios/hora a la ciudad 3.
Con un costo mínimo de $35,850.
Recomendaciones
Indique al alumno que se trata de un problema no balanceado por lo que se agrega una ciudad ficticia.
Mencione a los estudiantes que deben tener cuidado al aplicar el Método de Modi.
2. Una tienda de cosméticos tiene dos plantas productoras, una en Panamá y otra en Estados Unidos. Los productos se deben comercializar a través de unas tiendas que se encuentran en España, México y Brasil. La oferta de cada una de las plantas es de 4000 y 5000 artículos, respectivamente, mientras que la demanda de éstos es de 4000, 2800 y 2000. Los costos unitarios de transporte son:
España México Brasil
Panamá $200 $150 $190
USA $180 $100 $240
El gerente de almacén desea buscar la combinación que minimice los costos de transporte. Utilice el Método de Vogel y el Método de Modi.
Solución
Primero calculamos: oferta total = 4000+5000=9000 y demanda total = 4000+2800=6800. Como no son iguales tenemos un problema no balanceado, lo que implica añadir una tienda ficticia con una demanda de 2000, para tener un problema balanceado.
Entonces construimos la tabla de transporte asociada, después calculamos las penalidades asociadas a cada renglón y columna restando los dos costos menores por renglón y columna. Posteriormente identificamos el renglón o columna con la penalidad más grande, en este caso es el renglón uno, asignamos 200 a la variable x1,4 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 1
1 200 150 190 0
200
4000
3800
150
2 180 100 240 0 5000 100
Dem. 4000 2800 2000 200
0
Pen. 1 20 50 30 0
Ahora calculamos las penalidades asociadas a cada renglón y columna, menos a la columna 4. Después identificamos el renglón o columna con la penalidad más grande, en este caso es el renglón dos, asignamos 2800 a la variable x2,2 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 2
1 200 150 190 0
200
4000
3800
40
2 180 100
2800
240 0 5000
2200
80
Dem. 4000 2800
0
2000 200
0
Pen. 2 20 50 30 X
Calculamos las penalidades asociadas a cada renglón y columna, menos a los renglones 2 y 4. Después identificamos el renglón o columna con la penalidad más grande, en este caso el renglón dos, asignamos 2200 a la variable x2,1 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 3
1 200 150 190 0
200
4000
3800
10
2 180
2200
100
2800 240
0 5000
0
40
Dem. 4000
1800
2800
0
2000 200
0
Pen. 3 20 X 30 X
Después ajustamos el renglón restante, como se muestra en la tabla:
1 2 3 4 Oferta
1 200
1800
150 190
2000
0
200
4000
0
2 180
2200
100
2800 240
0 5000
0
Dem. 4000
0
2800
0
2000 200
0
Entonces tenemos una solución inicial:
x1,1=1800, x1,3=2000, x1,4=200, x2,1=2200 y x2,2=2800, con un costo mínimo de $1,058,000.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=200 u1=0, v1=100
Celda (1,3) u1+v3=150 v3=150
Celda (1,4) u1+v4=0 v4=0
Celda (2,1) u2+v1=180 u2=80
Celda (2,2) u2+v2=100 v2=20
Después calculamos los costos marginales asociados:
Celda (1,2) 150-u1-v2=130
Celda (2,3) 240-u2-v3=10
Celda (2,4) 0-u1-v4=0
Como todos los costos marginales son positivos la solución inicial es óptima.
Nota: La 4ta. tienda es ficticia, por lo que no existe suministro de Panamá a ésta.
Entonces la asignación que minimiza el costo total de transporte es:
Que Panamá transporta 1800 cosméticos a España.
Que Panamá transporta 2000 cosméticos a Brasil.
Que Estados Unidos transporta 2200 cosméticos a España.
Que Estados Unidos transporta 2800 cosméticos a México.
Con un costo mínimo de $1,058,000.
Recomendaciones
Indique al alumno que se trata de un problema no balanceado, por lo que se agrega una ciudad ficticia.
Mencione a los estudiantes que deben tener cuidado al calcular las penalidades.
Indique al grupo que debe tener cuidado al aplicar el Método de Modi.
3. Una compañía tiene plantas en el D.F. y Monterrey. Sus centros de distribución principales están ubicados en Puebla, Coahuila y Zacatecas. Las capacidades de las dos plantas durante el semestre próximo son 2000 y 1400 motocicletas.
Las demandas semestrales en los centros de distribución son 1000, 1500 y 1200 motocicletas. El costo de transporte de una motocicleta por tren es aproximadamente de 8 centavos por milla. La siguiente tabla muestra la distancia recorrida entre las plantas y los centros de distribución:
D.F. Monterrey
Puebla 850 1350
Coahuila 2688 1000
Zacatecas 1250 1275
Determine la cantidad que se enviará de cada planta que minimice el costo de transporte total. Utilice el Método de Vogel y el Método de Modi.
Solución
Primero calculamos: oferta total = 2000+1400=3400 y demanda total = 1000+1500+1200=3700, como no son iguales tenemos un problema no balanceado, esto implica añadir una planta ficticia con una demanda de 300, para tener un problema balanceado.
Después construimos la tabla de transporte asociada, calculamos las penalidades asociadas a cada renglón y columna, restando los dos costos menores por renglón y columna. Posteriormente identificamos el renglón o columna con la penalidad más grande, elegimos el renglón tres, asignamos 300 a la variable x3,3 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 Oferta Pen. 1
1 68 108 0 2000 68
2 215 80 0 1400 80
3
100 102 0
300
300
0
100
Dem. 1000 1500 1200
900
Pen. 1 32 22 0
Ahora calculamos las penalidades asociadas a cada renglón y columna, menos al renglón 3. Después identificamos el renglón o columna con la penalidad más grande, elegimos la columna uno, asignamos 1000 a la variable x1,1 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 Oferta Pen. 2
1 68
1000
108 0 2000
1000
68
2 215 80 0 1400 80
3 100 102 0
300
300
0
X
Dem. 1000
0
1500 1200
900
Pen. 2 147 22 0
Entonces calculamos las penalidades asociadas a cada renglón y columna, menos al renglón 3 y columna 1. Después identificamos el renglón o columna con la penalidad más grande,
que en este caso es el renglón uno, asignamos 900 a la variable x1,3 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 Oferta Pen. 3
1 68
1000
108 0
900
2000
100
108
2 215 80 0 1400 80
3 100 102 0
300
300
0
X
Dem. 1000
0
1500 1200
0
Pen. 3 X 22 0
Después ajustamos el renglón restante, como se muestra en la tabla:
1 2 3 Oferta Pen. 3
1 68
1000
108
100
0
900
2000
0
108
2 215 80
1400
0 1400
0
80
3
100 102 0
300
300
0
X
Dem. 1000
0
1500
0
1200
0
Pen. 3 X 22 0
Entonces tenemos una solución inicial:
x1,1=1000, x1,2=100, x1,3=900, x2,2=1400 y x3,3=300, con un costo mínimo de $190,800.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=68 u1=0, v1=68
Celda (1,2) u1+v2=108 v2=108
Celda (1,3) u1+v3=0 v3=0
Celda (2,2) u2+v2=80 u2=-28
Celda (3,3) u3+v3=0 u3=0
Después calculamos los costos marginales asociados:
Celda (2,1) 215-u2-v1=175
Celda (2,3) 0-u2-v3=28
Celda (3,1) 100-u3-v1=32
Celda (3,2) 102-u3-v2=-6
Como tenemos un valor negativo la solución inicial no es óptima. Elegimos la celda (3,2) para construir una trayectoria cerrada:
1 2 3 Oferta
1 68
1000
108
100-
0
900+
2000
0
2 215 80
1400
0 1400
0
3 100 102
0
300-
300
0
Dem. 1000 1500 1200
0 0 0
Como todas las asignaciones deben ser mayores o iguales a cero, obtenemos las siguientes desigualdades:
El máximo valor de que satisface todas las desigualdades es 100. Realizamos los ajustes a cada una de las celdas:
1 2 3 Oferta
1 68
1000
108 0
800
2000
0
2 215 80
1400
0 1400
0
3 100 102
100
0
200
300
0
Dem. 1000
0
1500
0
1200
0
Entonces tenemos una solución inicial:
x1,1=1000, x1,3 =800, x2,2=1400, x3,2=100 y x3,3=200, con un costo mínimo de $190,200.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=68 u1=0, v1=68
Celda (1,3) u1+v3=0 v3=0
Celda (2,2) u2+v2=80 u2=-28
Celda (3,2) u3+v2=102 v2=102
Celda (3,3) u3+v3=0 u3=0
Después calculamos los costos marginales asociados:
Celda (1,2) 108-u1-v2=6
Celda (2,1) 215-u2-v1=175
Celda (2,3) 0-u2-v3=28
Celda (3,1) 100-u3-v1=32
Como todos los costos marginales son positivos la solución inicial es óptima.
Nota: La planta 3 es ficticia, por lo que no existe suministro del distribuidor 3 a esta planta.
Entonces la asignación que minimiza el costo total de transporte es:
De la planta de Puebla se transportan1000 motocicletas al distribuidor del D.F.
De la planta de Coahuila se transportan 1400 motocicletas al distribuidor de Monterrey.
De la planta de Zacatecas se transportan 100 motocicletas al distribuidor de Monterrey.
Con un costo mínimo de $190,200.
Recomendaciones
Indique al alumno que se trata de un problema no balanceado por lo que se agrega una ciudad ficticia.
Mencione al grupo que deben tener cuidado al calcular las penalidades.
Indique a los estudiantes que deben tener cuidado al aplicar el Método de Modi.
Ejercicios con nivel de dificultad:
.
Avanzado
1. Una compañía produce motores eléctricos pequeños para cuatro fabricantes de electrodomésticos, en cada una de sus plantas. Los costos de producción por unidad varían según las ubicaciones debido a diferencias en el equipo de producción y en el rendimiento de
los obreros. Los costos de producción por unidad y la capacidad mensual se presentan en la siguiente tabla:
PlantaCosto de producción por unidad
Capacidad de producción mensual
A $17 700
B $20 500
C $24 600
Los pedidos de clientes que deben producirse el siguiente mes son:
Cliente Demanda
1 300
2 500
3 400
4 600
El costo de abastecimiento de estos clientes varía de una planta a otra. El costo de transporte por unidad aparece en la siguiente tabla:
A
Desde 1 2 3 4
A 3 2 5 7
B 6 4 8 3
C 9 1 5 4
La compañía debe decidir cuántas unidades se producirán en cada planta y qué porción de la demanda de cada cliente se surtirá desde cada una de ellas. Se desea minimizar la producción total y los costos de transporte. Utilice el Método de Vogel y el Método de Modi.
Solución
Primero calculamos: oferta total = 700+500+600=1800 y demanda total = 300+500+400+600=1800; como son iguales tenemos un problema balanceado.
Después construimos la tabla de transporte asociada, calculamos las penalidades asociadas a cada renglón y columna restando los dos costos menores por renglón y columna. Posteriormente identificamos el renglón o columna con la penalidad más grande (en este caso se tienen varias penalidades con el valor de 6). Como la elección es arbitraria elegimos la columna uno, asignamos 300 a la variable x1,1 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 1
1 20
300
19 22 24 700
400
1
2 26 24 28 23 500 1
3 33 25 29 28 600 3
Dem. 300
0
500 400 600
Pen. 1 6 5 6 1
Ahora calculamos las penalidades asociadas a cada renglón y columna, menos a la columna 1. Después identificamos el renglón o columna con la penalidad más grande, elegimos la columna tres, asignamos 400 a la variable x1,3 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 2
1 20
300
19 22
400
24 700
0
3
2 26 24 28 23 500 1
3 33 25 29 28 600 3
Dem. 300
0
500 400
0
600
Pen. 2 X 5 6 1
En seguida calculamos las penalidades asociadas a cada renglón y columna, menos a las columnas 1 y 3. Después identificamos el renglón o columna con la penalidad más grande (en este caso se tienen varias penalidades con el valor de 5). Como la elección es arbitraria en
este caso elegimos el renglón uno, asignamos 0 a la variable x1,2 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 3
1 20
300
19
0
22
400
24 700
0
5
2 26 24 28 23 500 1
3 33 25 29 28 600 3
Dem. 300
0
500 400
0
600
Pen. 3 X 5 X 1
Calculamos las penalidades asociadas a cada renglón y columna, menos al renglón 1 y a las columnas 1 y 3. Después identificamos el renglón o columna con la penalidad más grande, que en este caso es la columna cuatro, asignamos 500 a la variable x2,4 y ajustamos la oferta y la demanda, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 4
1 20
300
19
0
22
400
24 700
0
X
2 26 24 28 23
500
500
0
1
3 33 25 29 28 600 3
Dem. 300
0
500 400
0
600
100
Pen. 4 X 1 X 5
Posteriormente ajustamos el renglón restante, como se muestra en la tabla:
1 2 3 4 Oferta Pen. 4
1 20
300
19
0
22
400
24 700
0
X
2 26 24 28 23
500
500
0
1
3 33 25
500
29 28
100
600
0
3
Dem. 300
0
500
0
400
0
600
0
Pen. 4 X 1 X 5
Entonces tenemos una solución inicial:
x1,1=300, x1,2=0, x1,3=400, x2,4=500, x3,2=500 y x3,4=100, con un costo mínimo de $41,600.
Ahora aplicamos el Método de Modi para ver si la solución inicial obtenida es óptima. Calculamos los valores de los multiplicadores:
Celda (1,1) u1+v1=20 u1=0, v1=20
Celda (1,2) u1+v2=19 v2=19
Celda (1,3) u1+v3=22 v3=22
Celda (2,4) u2+v4=23 u2=1
Celda (3,2) u3+v2=25 u3=6
Celda (3,4) u3+v4=28 v4=22
Después calculamos los costos marginales asociados:
Celda (1,4) 24-u1-v4=2
Celda (2,1) 26-u2-v1=5
Celda (2,2) 24-u2-v2=4
Celda (2,3) 28-u2-v3=5
Celda (3,1) 33-u3-v1=7
Celda (3,3) 29-u3-v3=1
Como todos los costos marginales son positivos la solución inicial es óptima.
Entonces la asignación que minimiza el costo total de transporte es:
De la planta A se envían 300 motores eléctricos al fabricante 1.
De la planta A se envían 0 motores eléctricos al fabricante 2.
De la planta A se envían 400 motores eléctricos al fabricante 3.
De la planta B se envían 500 motores eléctricos al fabricante 4.
De la planta C se envían 500 motores eléctricos al fabricante 2.
De la planta C se envían 100 motores eléctricos al fabricante 4.
Con un costo mínimo de $41,600.
Recomendaciones
Indique al alumno que debe tener cuidado al calcular las penalidades.
Mencione al grupo que deben tener cuidado al aplicar el Método de Modi.
Unidad 8. Modelo de Asignación.
Objetivo general Objetivos específicos
El alumno:
Resolverá problemas de asignación balanceados y no balanceados por el Método Húngaro.
El alumno:
Resolverá problemas de asignación utilizando el método conocido como Húngaro o de matriz reducida.
Resolverá problemas de asignación no balanceados.
Ejercicios con nivel de dificultad:
Simple
1. Una empresa dedicada a la compra-venta de equipo de cómputo adquirió cuatro máquinas para ser vendidas; sin embargo, el cliente pide una prórroga de 1 mes para que le entreguen las máquinas. La empresa tiene que almacenar las cuatro durante este tiempo. Se cotizan los precios de cuatro bodegas que pueden almacenar las máquinas, los cuales se muestran en la siguiente tabla:
Bodega 1 Bodega 2 Bodega 3 Bodega 4
Máquina 1 5 15 20 10
Máquina 2 2 12 17 7
Máquina 3 15 25 30 20
Máquina 4 10 20 25 15
Determine la forma de asignar una máquina a cada bodega, de tal manera que se minimice el costo total.
Solución
Como se puede observar, se tiene un problema balanceado, ya que se cuenta con el mismo número de máquinas y tareas.
Ahora 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
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 asignación posible, la cual es óptima.
Entonces la forma de asignar una máquina a cada bodega, de tal manera que se minimice el costo total es:
Máquina 1- Bodega 1
Máquina 2- Bodega 2
Máquina 3- Bodega 3
Máquina 4- Bodega 4
Con un costo mínimo de $62.
Recomendaciones
Indique al alumno que no es la única asignación posible y cualquier otra tiene el mismo costo mínimo.
2. Un socio de una agencia de publicidad trata de decidir cuál de cuatro ejecutivos de contabilidad debe asignar a cada uno de cuatro clientes. En la siguiente tabla se presentan los costos estimados de la asignación de cada ejecutivo. Use el Método Húngaro para encontrar la solución óptima del problema. Establezca el valor óptimo de la función objetivo.
Clientes
Ejecutivos 1 2 3 4
A 15 19 20 18
B 14 15 17 14
C 11 15 15 14
D 21 24 26 24
Solución
Como se puede observar, se tiene un problema balanceado, ya que se cuenta con el mismo número de clientes y ejecutivos.
Primero 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 15
0
19
4
20
5
18
3
B 14
0
15
1
17
3
14
0
C 11
0
15
4
15
4
14
0
D 21
0
24
3
26
5
24
3
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 15
0
19
3
20
2
18
3
B 14
0
15
0
17
0
14
0
C 11
0
15
3
15
1
14
0
D 21
0
24
2
26
2
24
3
Como no se tiene una asignación posible, tachamos los ceros con el número menor de líneas verticales y horizontales:
1 2 3 4
A 15
0
19
3
20
2
18
3
B
14
0
15
0
17
0
14
0
C 11
0
15
3
15
1
14
0
D 21
0
24
2
26
2
24
3
Ahora identificamos el menor de los costos no cubiertos por una línea, luego se lo restamos a los costos no cubiertos y lo sumamos a lo costos que se encuentran en la intersección de dos líneas. Los demás quedan iguales, obteniendo:
1 2 3 4
A 15
0
19
2
20
1
18
3
B 14
1
15
0
17
0
14
1
C 11
0
15
2
15
0
14
0
D 21
0
24
1
26
1
24
3
Como no se tiene una asignación posible, tachamos los ceros con el número menor de líneas verticales y horizontales:
1 2 3 4
A 15
0
19
2
20
1
18
3
B
14
1
15
0
17
0
14
1
C
11
0
15
2
15
0
14
0
D 21
0
24
1
26
1
24
3
Ahora identificamos el menor de los costos no cubiertos por una línea, después 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 15
0
19
1
20
0
18
2
B 14
2
15
0
17
0
14
1
C 11
1
15
2
15
0
14
0
D 21
0
24
0
26
0
24
2
Realizando una permutación de las columnas logramos obtener una asignación posible y ésta es óptima:
1 2 4 3
A 15
0
19
1
18
2
20
0
B 14
2
15
0
14
1
17
0
C 11
1
15
2
14
0
15
0
D 21
0
24
0
24
2
26
0
Entonces la asignación que minimiza el costo total es:
Ejecutivo A - Cliente 1
Ejecutivo B - Cliente 2
Ejecutivo C - Cliente 4
Ejecutivo D - Cliente 3
Con un costo mínimo de $70.
Recomendaciones
Indique al alumno cómo realizar las permutaciones de columnas.
Mencione al grupo que no es la única asignación posible y cualquier otra tiene el mismo costo mínimo.
Indique a los estudiantes que el número de líneas verticales y horizontales para tachar los ceros debe ser mínima.
3. Una compañía va a decidir cuál 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 compañía le gustaría minimizar el costo de transporte total. En la siguiente tabla se muestran los estimados. Use el Método Húngaro para resolver este problema. Establezca el valor óptimo de la función 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
Solució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 65
10
73
18
55
0
58
3
B 90
23
67
0
87
20
75
8
C 106 86 96 89
20 0 10 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 asignación posible, tachamos los ceros con el número menor de líneas verticales y horizontales:
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 69 79 77
5 0 10 5
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 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 permutación de las columnas logramos obtener una asignación 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 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.
Recomendaciones
Indique al alumno que el número de líneas verticales y horizontales para tachar los ceros debe ser mínima.
Ejercicios con nivel de dificultad:
Medio
1. Una empresa de transporte 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 son:
Camión 1 Camión 2 Camión 3 Camión 4
Conductor 1 180 150 200 200
Conductor 2 250 305 450 500
Conductor 3 200 208 320 100
Encuentren la asignación que minimiza los costos de combustible adicional.
Solución
Como se puede observar, se tiene un problema no balanceado, ya que hay más camiones que conductores; esto implica añadir un conductor ficticio, para tener un problema balanceado.
Primero 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
1 180
30
150
0
200
50
200
50
2 250
0
305
55
450
200
500
250
3 200
100
208
108
320
220
100
0
4 0
0
0
0
0
0
0
0
Después 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 180
30
150
0
200
50
200
50
2 250
0
305
55
450
200
500
250
3 200
100
208
108
320
220
100
0
4 0
0
0
0
0
0
0
0
Realizando una permutación de las columnas logramos obtener una asignación posible y ésta es óptima:
2 1 4 3
1 150 180 200 200
0 30
50
50
2 305
55
250
0
500
250
450
200
3 208
108
200
100
100
0
320
220
4 0
0
0
0
0
0
0
0
Nota: El conductor 4 es ficticio, por lo que no existe asignación de éste al camión 3.
Entonces la asignación que minimiza los costos de combustible adicional es:
Conductor 1 - Camión 2
Conductor 2 - Camión 1
Conductor 3 - Camión 4
Con un costo mínimo de $500.
Recomendaciones
Mencione al grupo que se trata de un problema no balanceado por lo cual se agrega un conductor ficticio.
Indique al alumno cómo realizar las permutaciones de columnas.
2. Samuel tiene cuatro fosas de reparaciones en su taller de mantenimiento y tres trabajos para asignárselos. Debido a diferencias en el equipo disponible, en la gente asignada a cada fosa y las características del trabajo, cada uno de éstos requiere diferente cantidad de tiempo en cada fosa, como se muestra en la siguiente tabla: Samuel quiere minimizar el tiempo total requerido. Use el Método Húngaro para obtener la solución óptima a este problema. Establezca el valor óptimo de la función objetivo.
Trabajo
Fosa 1 2 3
A 24 45 25
B 33 48 23
C 24 52 20
D 30 56 21
Solución
Como se puede observar, se tiene un problema no balanceado, ya que se cuenta con más fosas que trabajos; esto implica añadir un trabajo ficticio, para tener un problema balanceado.
Primeramente, 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; y por ultimo se identifica el costo menor de cada una de las columnas y se lo restamos a los costos de la misma:
1 2 3 4
A 24
24
45
45
25
25
0
0
B 33
33
48
48
23
23
0
0
C 24
24
52
52
20
20
0
0
D 30
30
56
56
21
21
0
0
En seguida se identifica el costo menor de cada una de las columnas y se le resta a los costos de la misma columna:
1 2 3 4
A 24
0
45
0
25
5
0
0
B 33
9
48
3
23
3
0
0
C 24 52 20 0
0 7
0
0
D 30
6
56
11
21
1
0
0
Como no se tiene una asignación posible, tachamos los ceros con el número menor de líneas verticales y horizontales:
1 2 3 4
A
24
0
45
0
25
5
0
0
B 33
9
48
3
23
3
0
0
C
24
0
52
7
20
0
0
0
D 30
6
56
11
21
1
0
0
Ahora identificamos el menor de los costos no cubiertos por una línea, después 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 24
0
45
0
25
5
0
1
B 33
8
48
2
23
2
0
0
C 24
0
52
7
20
0
0
1
D 30
5
56
10
21
0
0
0
Realizando una permutación de las columnas logramos obtener una asignación posible y ésta es óptima:
2 4 1 3
A 45
0
0
1
24
0
25
5
B 48
2
0
0
33
8
23
2
C 52
7
0
1
24
0
20
0
D 56
10
0
0
30
5
21
0
Nota: El trabajo 4 es ficticio, por lo que no existe asignación de la fosa C a éste.
Entonces la asignación que minimiza el costo total es:
Fosa A - Trabajo 2
Fosa B - Trabajo 4
Fosa D - Trabajo 3
Con un costo mínimo de $90.
Recomendaciones
Mencione al grupo que se trata de un problema no balanceado por lo cual se agrega un trabajo ficticio.
Muestre al alumno cómo realizar las permutaciones de columnas.
Indique a los estudiantes que el número de líneas verticales y horizontales para tachar los ceros debe ser mínima.
3. Un corredor de bienes raíces planea la compra de cuatro lotes de terreno y ha recibido ofertas individuales de cuatro vendedores, cada uno le ofrece 5 lotes. Debido a la cantidad
de capital que se requiere, estas ofertas se han hecho en el entendimiento de que ninguno de los cuatro le venderá más de un lote. Las ofertas se muestran en la siguiente tabla. Resuelve este problema mediante el Método Húngaro. Establece el valor de la función objetivo.
Lote
Vendedor 1 2 3 4 5
A 16 15 25 19 20
B 19 17 24 15 25
C 15 15 18 17 16
D 19 18 15 17 18
Solución
Como se puede observar se tiene un problema no balanceado, ya que se cuenta con más lotes que vendedores; esto implica añadir un vendedor ficticio, para tener un problema balanceado.
Entonces construimos la tabla de asignación, después identificamos el costo menor de cada una de las filas, se lo restamos a los costos de la misma fila y por último 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 5
A 16
1
15
0
25
10
19
4
20
5
B 19
4
17
2
24
9
15
0
25
10
C 15
0
15
0
18
3
17
2
16
1
D 19
4
18
3
15
0
17
2
18
3
E 0
0
0
0
0
0
0
0
0
0
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 5
A 16
1
15
0
25
10
19
4
20
5
B 19
4
17
2
24
9
15
0
25
10
C 15
0
15
0
18
3
17
2
16
1
D 19
4
18
3
15
0
17
2
18
3
E 0
0
0
0
0
0
0
0
0
0
Realizando una permutación de las columnas logramos obtener una asignación posible y ésta es óptima.
2 4 1 3 5
A 15
0
19
4
16
1
25
10
20
5
B 17
2
15
0
19
4
24
9
25
10
C 15
0
17
2
15
0
18
3
16
1
D 18 17 19 15 18
3 2 4 0 3
E 0
0
0
0
0
0
0
0
0
0
Nota: El vendedor E es ficticio, por lo que no existe asignación de éste al lote 5.
Entonces tenemos que la asignación que minimiza los costos es:
Vendedor A - Lote 2
Vendedor B - Lote 4
Vendedor C - Lote 1
Vendedor D - Lote 3
Con un costo mínimo de $60.
Recomendaciones
Mencione al grupo que se trata de un problema no balanceado por lo cual se agrega un vendedor ficticio.
Muestre al alumno cómo realizar las permutaciones de columnas.
Indique a los estudiantes que no es la única asignación posible y cualquier otra tiene el mismo costo mínimo.
