![Page 1: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/1.jpg)
UNIDAD DOS
MODELO DE
ASIGNACIÓN
Ing. César Urquizú
Ing. César Urquizú
![Page 2: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/2.jpg)
Modelos de Transporte
Método de la Esquina Noroeste
Método del Costo Mínimo o Menor
Método de Aproximación de Vogel (MAV)
Método del Banquillo
Método de Multiplicadores
Modelo de ASIGNACION
Modelo de Transbordo
![Page 3: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/3.jpg)
Asignación
Considere un caso especial del problema de transporte en que se cumple:
m = n; es decir, el número de orígenes es igual a los destinos;
además ai= bj =1.
El modelo así definido es asignación pura, se refiere a la acción de asignar
uno a uno; esto es, en forma biunívoca. Se entiende asignar n candidatos a n
acciones requeridas, conociendo la medida de desempeño, que puede ser
costo, beneficio o rendimiento.
El problema consiste en asignar de forma idónea para conseguir el mejor
resultado general. Por ejemplo, la asignación de personas a operar máquinas,
para las cuales se tiene la información de la capacidad individual al trabajar
con ellas, se acepta como asignación pura de operarios a máquinas.
Otro ejemplo, se refiere a la asignación de competidores para desempeñarse
en la competencia de algún evento deportivo, desde luego, con diferente
eficiencia individual; aquí también se asigna un competidor para ocupar cada
relevo de la carrera o cada posición en un juego colectivo.
![Page 4: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/4.jpg)
C i j = costo o valor del desempeño individual de i en la acción j. Sujeta a las restricciones:
ΣX i j = 1; desde i = 1 hasta i = n; de j = 1 hasta j= n.
![Page 5: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/5.jpg)
• La diferencia de costos del mas pequeño con todos
los de cada columna y fila, se llama costo de
oportunidad.
• Se busca tener una matriz de costos de
oportunidad.
• El costo de oportunidad cero significa que el uso de
esa celda para una asignación da la asignación de
menor costo posible.
• Una asignación optima utiliza sólo celdas con costo
cero.
• Al hacer la asignación óptima debe haber na celda
con CERO para cada par único de renglón o
columna.
![Page 6: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/6.jpg)
Ejemplo:
• La siguiente matriz contiene los costos para operar n=4
máquinas, por n=4 personas así calificadas en su
empresa. Optimice la asignación idónea.
i / j 1 2 3 4
1 1 4 6 3
2 9 7 10 9
3 4 5 11 7
4 8 7 8 5
![Page 7: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/7.jpg)
• Paso 1 .Seleccione en cada renglón i de la
• matriz, el menor costo C i j, (menor C i j = U i ),
luego réstelo en cada elemento del renglón.
i / j 1 2 3 4
1 1 4 6 3
2 9 7 10 9
3 4 5 11 7
4 8 7 8 5
Ui
U1= 1
U2=7
U3=4
U4= 5
i / j 1 2 3 4
1 0 3 5 2
2 2 0 3 2
3 0 1 7 3
4 3 2 3 0
![Page 8: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/8.jpg)
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 réstelo
en cada elemento de la misma columna.
i / j 1 2 3 4
1 0 3 5 2
2 2 0 3 2
3 0 1 7 3
4 3 2 3 0
Vj V1= 0 V2= 0 V3=3 V4=0
i / j 1 2 3 4
1 0 3 2 2
2 2 0 0 2
3 0 1 4 3
4 3 2 0 0
![Page 9: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/9.jpg)
• Paso 3.Sombree los renglones y/o columnas de la
matriz, de tal modo que sean los mínimos
necesarias para cubrir todos los ceros.
i / j 1 2 3 4
1 0 3 2 2
2 2 0 0 2
3 0 1 4 3
4 3 2 0 0
![Page 10: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/10.jpg)
Paso 4. Seleccione entre los costos no sombreados, el
número menor C i j, (= U i j) o bien, el menor C i
j,(= V i j), y réstelo a todos los costos no sombreados; después,
sume el mismo a los costos ubicados en la intersección de los
renglones y columnas sombreados. Este paso se repite hasta
lograr la solución óptima.
i / j 1 2 3 4
1 0 3 2 2
2 2 0 0 2
3 0 1 4 3
4 3 2 0 0
U32= 1
![Page 11: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/11.jpg)
i / j 1 2 3 4
1 0 3 2 2
2 2 0 0 2
3 0 1 4 3
4 3 2 0 0
i / j 1 2 3 4
1 0 2 1 1
2 3 0 0 2
3 0 0 3 2
4 4 2 0 0
![Page 12: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/12.jpg)
Se tiene la solución óptima cuando el mínimo necesario de
renglones y columnas sombreadas para cubrir los ceros es n.
En este problema el mínimo es n =4.
Entonces la asignación óptima es la que muestra la tabla siguiente:
Solución ó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
i / j 1 2 3 4
1 0 2 1 1
2 3 0 0 2
3 0 0 3 2
4 4 2 0 0
i / j 1 2 3 4
1 2 1 1
2 3 0 2
3 0 3 2
4 4 2 0
![Page 13: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/13.jpg)
En la solución óptima, la suma de las costos Ui restados
de renglones i en paso 1, más las costos V j restados de
columnas j en paso 2, más 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
![Page 14: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/14.jpg)
Ejemplo 2
La siguiente matriz muestra costos C i j de n = 5 candidatos i ( i = 1,2,...,5 ) así
calificados, en el desempeño de n = 5 actividades j ( j = 1,2,..,5 ). Con el método
húngaro calcule la asignación óptima.
![Page 15: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/15.jpg)
![Page 16: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/16.jpg)
Asignación ó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
![Page 17: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/17.jpg)
Problema de transbordoComo una extensión necesaria del problema de transporte en
el que sólo se consideran transportes directos entre dos clases de
nodos, origen y destino, se presenta ahora el problema de transbordo,
en el cual se considera que las unidades pueden fluir entre cualquier
par de nodos en las combinaciones posibles siguientes: de nodo de
suministro a otro que también surte, de nodo demandante a otro que
también demanda, desde un nodo de transbordo a otro con la misma
función, de un nodo de transbordo a un destino, e incluso de un origen
a un destino. Se generaliza así la red de distribución.
Definición: Dada una red de n nodos ( i ), de los cuales, algunos son
orígenes con oferta de un cierto producto, algunos otros son
transbordos y destinos, que demandan el mismo producto. El objetivo
es satisfacer tal demanda con la capacidad F i j de ramas (i, j) de
conexión, a expensas de la oferta de los orígenes, cumpliendo el
objetivo de costo mínimo.
Red a transbordo, oferta = demanda
![Page 18: UNIDAD DOS MODELO DE ASIGNACIÓN · Método de Aproximación de Vogel (MAV) Método del Banquillo Método de Multiplicadores Modelo de ASIGNACION Modelo de Transbordo. Asignación](https://reader031.vdocumento.com/reader031/viewer/2022011804/5bb145ca09d3f2830e8ddea1/html5/thumbnails/18.jpg)
Equilibrio: oferta = 250 + 150 = 400 = 70 + 60 + 180 + 90 = demanda
Primera parte del modelo, definición de variables:
Sea: X i j = Unidades enviadas del nodo ( i ) al nodo ( j ), a través de la rama ( i, j ).
C i j = Costo de enviar una sola unidad utilizando la rama ( i, j )
Segunda parte del modelo, función objetivo:
Mínimo Z =70 X13 + 110 X15 + 90 X23 + 100 X 24 + 30 X 35 + 50 X36 + 40 X46