1. 1. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 1 1 2 3 OFERTA A 300 B 100 C 200 600 1500 600500400DEMANDA 1 2 3 OFERTA A 300 B 100 C 200 f 0 0 0 900 1500 1500 600500400DEMANDA EL MTODO DE TRANSPORTE Este mtodo se utiliza para minimizar tiempo y los cotos al crear guas de rutas. Para cualquiera de los mtodos de resolucin, es fundamental que la matriz del problema mantenga su oferta y demanda equilibrada; caso contrario ser necesario equilibrarla aumentando ficticias (filas o columnas) en la oferta o en la demanda segn se requiera para cada ejercicio. Se lo puede resolver mediante: 1. MCM, Mtodo del Costo Mnimo. 2. MEN, Mtodo de la Esquina Noroeste 3. MAV o VAM, Mtodo de Aproximacin de Vogel Estos mtodos proporcionan una solucin bsica factible, y para resolver cada uno se debe conocer el algoritmo. Tambin se resuelve por los siguientes mtodos: 1. MODI, Mtodo de distribucin modificada 2. Mtodo de Pasos Secuenciales 3. Mtodo del Trampoln Estos ltimos nos proporcionan solucin ptima; como tambin es el caso del mtodo simplex. Existe una dif erencia en la suma de O y D; por lo que debemos agregar una of erta con costos 0. Ahora si est lista para poder resolv er
2. 2. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 2 A 6 300 8 12 200 5 500 B 7 100 9 700 10 6 800 C 300 4 5 13 9 300 1600 1600 OFERTAORIGEN DEMANDA 700 200400300 32 4 DESTINOS 1 MTODO DE COSTO MNIMO ALGORITMO DE RESOLUCIN 1. De la matriz se elige la ruta menos costosa (en caso de empate, rompa arbitrariamente) y se le asigna la mayor cantidad de unidades posibles, cantidad que se ver restringida por las restricciones de oferta o demanda. Aqu mismo ajuste la oferta y la demanda restando la cantidad asignada. 2. Elimine la fila cuya oferta o demanda sea cero, si dado el caso, ambas son cero, arbitrariamente elija cual eliminar y la restante se deja con demanda u oferta cero, segn sea el caso. 3. Una vez en este paso, existen dos posibilidades. La primera es que quede un solo rengln o columna; si este es el caso, se llega al final del mtodo. La segunda es que quede ms de un rengln o columna, si este es el caso, inicie nuevamente el paso uno. EJERCICIO 1 = 1 + 2 + 4 + 2 + 3 = 2400 + 1000 + 900 + 7000 + 1200 = 12500 SOLUCIN BSICA FACTIBLE COMPROBACIN + Nmero de celdas ocupadas + + EJERCICIO 2 = 1 + 1 + 2 + 2 + 2 + 3 + 4 = 1000 + 1500 + 1400 + 1200 + 200 + 5600 + 400 1 A 6 8 12 5 500 B 7 9 10 6 800 C 4 5 13 9 300 1600 1600 OFERTAORIGEN DEMANDA 700 200400300 32 4 DESTINOS 1 4 6 8 12 500 2 6 14 4 1 600 3 5 16 16 20 350 4 2 16 8 9 200 1650 1650 OFERTAORIGEN DEMANDA 300 200700450 CB D DESTINOS A 1 250 4 250 6 8 12 500 2 6 100 14 300 4 200 1 600 3 5 350 16 16 20 350 4 200 2 16 8 9 200 1650 1650 OFERTAORIGEN DEMANDA 300 200700450 CB D DESTINOS A
3. 3. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 3 = 11300 SOLUCIN BSICA FACTIBLE COMPROBACIN + 4 + 4 1 7 MTODO DE LA ESQUINA NOROESTE Proporciona una solucin bsica factible. Empieza en la celda 11 EJERCICIO 1 La Panadera Granis con sucursales en la Dolorosa, Circunvalacin y Plaza Giralda oferta 30, 40 y 10 unidades de panes a la Condamine, TIA, AK y Sp-Maxi, que demandad de 20, 10, 30 y 20 unidades de pan respectivamente. = 240 + 80 + 270 + 120 + 100 = 810 EJERCICIO 2 = 200 + 600 + 100 + 300 + 600 + 400 + 300 + 200 = 2700 EJERCICIO 3 1 100 2 100 6 2 10 5 200 2 3 100 1 100 3 2 10 200 3 5 4 100 6 8 5 100 4 9 5 100 4 100 3 100 2 300 800 800 OFERTAORIGEN DEMANDA 300 100200100 CB E DESTINOS A D 100 DOLOROSA 20 12 10 8 4 8 30 CIRCUNVALACIN 5 7 30 9 10 12 40 PLAZAGIRALDA 10 2 7 10 10 10 80 80 OFERTAORIGEN DEMANDA 30 201020 AKTA SP-MAXI DESTINOS CONDAMINE DOLOROSA 12 8 4 8 30 CIRCUNVALACIN 5 7 9 12 40 PLAZA GIRALDA 10 2 7 10 10 80 80 OFERTAORIGEN DEMANDA 30 201020 AKTA SP-MAXI DESTINOS CONDAMINE 1 2 6 2 10 5 200 2 3 1 3 2 10 200 3 5 4 6 8 5 100 4 9 5 4 3 2 300 800 800 OFERTAORIGEN DEMANDA 300 100200100 CB E DESTINOS A D 100
4. 4. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 4 1 3 7 9 630 2 6 12 10 515 1145 1375 OFERTAORIGEN DEMANDA 205420750 CB DESTINOS A = 1890 + 720 + 4740 = MTODO DE APROXIMACIN DE VOGEL (VAM)(MAV) Proporciona Solucin Factible Bsica ALGORITMO DE RESOLUCIN 1. Determinar para cada fila y columna una medida de penalizacin restando los 2 costos menores en filas y columnas. 2. Seleccione la fila o columna con la mayor penalizacin. 3. De la fila o columna de mayor penalizacin escojo la celda con el menor costo y asigne la cantidad posible de unidades. 4. Si queda sin tachar una fila o columna, detngase. Si queda sin tachar una fila o columna con oferta o demanda positiva aplique el mtodo de costo mnimo y termine. Si todas las filas y columnas que no se tacharon tienen oferta cero o demanda cero determine las variables bsicas cero utilizando el MCM y termine. Si no se presenta ninguno de los casos anteriores, vuelva al paso 1 hasta que las ofertas se hayan agotado. EJERCICIO 1 630 3 7 9 630 2 120 6 395 12 10 515 3 0 25 0 205 0 230 1375 1375 OFERTAORIGEN DEMANDA 205420750 CB DESTINOS A ANGEL 12 13 300 4 5 300 MATEO 6 5 10 11 100 1 CARLOS 10 9 11 4 200 5 600 600 4 4 7 OFERTAORIGEN DEMANDA 30010050 INFANTILMALDONADO DESTINOS SUCRE BELLAVISTA 150 ANGEL 12 13 300 4 5 300 MATEO 50 6 50 5 10 11 100 CARLOS 10 50 9 11 150 4 200 600 600 OFERTAORIGEN DEMANDA 30010050 INFANTILMALDONADO DESTINOS SUCRE BELLAVISTA 150 ANGEL 12 13 4 5 300 1 MATEO 6 5 10 11 100 1 CARLOS 10 9 11 4 200 5 600 600 4 4 6 1 OFERTAORIGEN DEMANDA 30010050 INFANTILMALDONADO DESTINOS SUCRE BELLAVISTA 150 ANGEL 12 13 300 4 5 300 MATEO 6 5 10 11 100 1 CARLOS 10 9 11 150 4 200 5 600 600 4 4 OFERTAORIGEN DEMANDA 30010050 INFANTILMALDONADO DESTINOS SUCRE BELLAVISTA 150
5. 5. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 5 = 1200 + 300 + 250 + 450 + 600 = 2700 MTODO DE ASIGNACIN O HNGARO Para su aplicacin debemos tener igual nmero de filas que de columnas No se integra con oferta ni demanda EJEMPLO PARA MINIMIZAR = 4 + 1 + 3 + 9 = 17 EJEMPLO PARA MAXIMIZAR S. ALFONSO DOLOROSA BELLAVISTA LAMERCED 9137 9 8 4 12 3 5 46 8 3 2 8 ORIGEN DESTINOS GUANO PENIPE COLTA PALLATANGA 5 4 0 8 REDUCCIN DE FILAS 6 1 0 6 6 2 0 8 0 2 3 1 6 1 0 7 5 3 0 7 0 1 3 0 6 0 0 5 ASIGNACIN E1 E2 E3 E4 10151613 14 11 9 7 15 9 1413 12 14 17 9 ORIGEN DESTINOS A B C D E1 E2 E3 E4 10151613 14 11 9 7 15 9 1413 12 14 17 9 ORIGEN DESTINOS A B C D 3 6 8 10 MATRIZ REDUCIDAPARAMINIMIZAR 5 3 0 8 4 1 2 7 2 8 4 3 0 3 5 7 5 3 0 8 3 0 1 6 REDUCCIN DE FILAS 0 6 2 1 S. ALFONSO DOLOROSA BELLAVISTA LAMERCED 9137 9 8 4 12 3 5 46 8 3 2 8 ORIGEN DESTINOS GUANO PENIPE COLTA PALLATANGA 5 3 0 7 6 0 0 5 6 1 0 7 REDUCCIN DE COLUMNAS 0 1 3 0 0 3 0 2 1 0 0 0 1 1 0 2 ASIGNACIN 0 6 8 0
6. 6. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 6 = + + + = MTODO DE PASOS SECUENCIALES Este mtodo comienza con una solucin inicial factible (como el que produce el MEN, MCM, MAV). En cada paso se intenta enviar artculos por una ruta que no se haya usado en la solucin factible actual, en tanto se elimina na ruta usada actualmente. En cada cambio de ruta debe cumplirse que: La solucin siga siendo factible. Que mejore el valor de la funcin objetivo. El procedimiento termina cuando no hay cambio de rutas que mejore el valor de la funcin. Problema degenerado.- es cuando una solucin factible usa menos de m+n-1 rutas Callejones sin salida.- cuando no se encuentran trayectorias apropiadas. ALGORITMO DE RESOLUCIN 1. Usar la solucin actual (MEN, MCM, MAV) para crear una trayectoria nica del paso secuencial. Usar estas trayectorias para calcular el costo marginal de introducir a la solucin cada ruta no usada. 2. Si todos los costos marginales son iguales o mayores que cero, terminar. Se tendr la solucin ptima; sino, elegir la celda que tenga el costo marginal ms negativos (empates se resuelven arbitrariamente) 3. Usando la trayectoria del paso secuencial determine el mximo nmero de artculos que se pueden asignar a la ruta elegida en el punto 2 y ajustar la distribucin adecuadamente. 4. Regrese al paso 1. EJERCICIO REDUCCIN DE COLUMNAS 0 6 2 0 5 3 0 7 3 0 1 5 0 3 5 6 3 0 1 5 0 3 5 6 0 6 2 0 5 3 0 7 ASIGNACIN
7. 7. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 7 MEN=12200 = 2400 + 800 + 2400 + 1000 + 1800 + 1600 = 10000 MTODO DE DISTRIBUCIN MODIFICADA En este mtodo se elabora el circuito en direccin de las manecillas del reloj. EJERCICIO MEN Z=12200 1 12 13 4 6 400 2 6 4 10 11 600 3 10 9 12 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400 1 300 12 100 13 4 6 400 2 6 600 4 10 11 600 3 10 100 9 200 12 400 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400 1 300 12 100 13 4 6 400 2 6 600 4 10 11 600 3 10 100 9 200 12 400 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400 1C= 4-12+9-13 -12 1D= 6-4+9-13 -2 2A= 6-12+13-4 3 2C= 10-12+9-4 3 2D= 11-4+9-4 12 3A= 10-12+13-9 2 1 300 12 13 100 4 6 400 2 6 600 4 10 11 600 3 10 200 9 100 12 400 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400 1B= 13-9+12-4 12 1D= 6-4+12-4 10 2C= 10-12+9-4 3 2D= 11-4+9-4 12 3A= 10-12+4-12 -10 A 12 13 4 6 500 B 6 4 10 11 700 C 10 9 12 4 800 2000 2000 OFERTAORIGEN DEMANDA 200900400 32 DESTINOS 1 4 500 A 400 12 100 13 4 6 500 B 6 700 4 10 11 700 C 10 100 9 200 12 500 4 800 2000 2000 OFERTAORIGEN DEMANDA 200900400 32 DESTINOS 1 4 500 1 300 12 13 100 4 6 400 2 6 600 4 10 11 600 3 10 200 9 100 12 400 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400 1 200 12 13 200 4 6 400 2 6 600 4 10 11 600 3 100 10 200 9 12 400 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400 1 200 12 13 200 4 6 400 2 6 600 4 10 11 600 3 100 10 200 9 12 400 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400 1B= 13-9+10-12 2 1D= 6-4+10-12 0 2A= 6-10+9-4 1 2D= 11-4+9-4 12 3C= 12-10+12-4 10 1 200 12 13 200 4 6 400 2 6 600 4 10 11 600 3 100 10 200 9 12 400 4 700 1700 1700 OFERTAORIGEN DEMANDA 200800300 CB DESTINOS A D 400
8. 8. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 8 1 5 10 10 0 20 11 15 2 12 5 7 15 9 5 20 25 3 0 14 16 5 18 5 45 45 OFERTAORIGEN DEMANDA 15155 CB DESTINOS A D 10 Z= 12000 MTODO DEL CRUCE DEL ARROYO Aqu los ceros constan como celdas llenas. EJERCICIO MEN Z=410 U1+V1 = 12 U1=0 V1=12 CA3= 4-(U1+V3)= 4-(0+16) = -12 U1+V2 = 13 U2=-9 V2=13 CA4= 6-(U1+V4)= 6-(0+8) = -2 U2+V2 = 4 U3=-4 V3=16 CB1= 6-(U2+V1)= 6-(-9+12) = 3 U3+V2 = 9 V4=8 CB3= 10-(U2+V3)= 10-(-9+16) = 3 U3+V3 = 12 CB4= 11-(U2+V4)= 11-(-9+8) = 12 U3+V4 = 4 CC1= 10-(U3+V1)= 10-(-4+12) = 2 CELDAS LLENAS DONDE: COSTOS EN CELDAS VACAS A 400 12 - 13 100 4 6 500 B 6 700 4 10 11 700 C 10 200 9 100 12 500 4 800 2000 2000 OFERTAORIGEN DEMANDA 200900400 32 DESTINOS 1 4 500 U1+V1 = 12 U1=0 V1=12 CA2= 13-(0+1) = 12 U1+V3 = 4 U2=3 V2=1 CA4= 6-(0-4) = 10 U2+V2 = 4 U3=8 V3=4 CB1= 6-(3+12) = -9 U3+V2 = 9 V4=-4 CB3= 10-(3+4) = 3 U3+V3 = 12 CB4= 11-(3-4) = 12 U3+V4 = 4 CC1= 10-(8+12) = -10 CELDAS LLENAS DONDE: COSTOS EN CELDAS VACAS A 300 12 13 200 4 6 500 B 6 700 4 10 11 700 C 100 10 200 9 12 500 4 800 2000 2000 OFERTAORIGEN DEMANDA 200900400 32 DESTINOS 1 4 500 U1+V1 = 12 U1=0 V1=12 CA2= 13-(0+11) = 2 U1+V3 = 4 U2=-7 V2=11 CA4= 6-(0+6) = 0 U2+V2 = 4 U3=-2 V3=4 CB1= 6-(-7+12) = 1 U3+V1 = 10 V4=-6 CB3= 10-(-7+4) = 13 U3+V2 = 9 CB4= 11-(-7+6) = 12 U3+V4 = 4 CC1= 12-(-2+4) = 10 CELDAS LLENAS DONDE: COSTOS EN CELDAS VACAS 1C = 18 1D = -2 2A = -5 3A = -15 3B = 9 3C = 9 1 0 10 15 0 20 11 15 2 12 0 7 15 9 10 20 25 3 5 0 14 16 0 18 5 45 45 OFERTAORIGEN DEMANDA 15155 CB DESTINOS A D 10
9. 9. UNIDAD I APLICACIONES DE LA PROGRAMACIN LINEAL ROSA G. | Investigacinde OperacionesII 9 1 0 10 5 0 20 10 11 15 2 12 10 7 15 9 0 20 25 3 5 0 14 16 0 18 5 45 45 OFERTAORIGEN DEMANDA 15155 CB DESTINOS A D 10 Z= 315 Solucin ptima Como se puede apreciar, este mtodo es el que nos ofrece una solucin ptima. 1C = 18 1D = -2 2A = 10 3B = 24 3C = 9 1C = 18 2A = 14 3B = 7 3C = 9