unidad 1

download unidad 1

of 10

description

unidad 1

Transcript of unidad 1

UNIDAD IAPLICACIONES DE LA PROGRAMACIN LINEALEL MTODO DE TRANSPORTEEste 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.

Existe una diferencia en la suma de O y D; por lo que debemos agregar una oferta con costos 0.

Ahora si est lista para poder resolver

Se lo puede resolver mediante: 1. MCM, Mtodo del Costo Mnimo.2. MEN, Mtodo de la Esquina Noroeste3. MAV o VAM, Mtodo de Aproximacin de VogelEstos 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 modificada2. Mtodo de Pasos Secuenciales3. Mtodo del TrampolnEstos ltimos nos proporcionan solucin ptima; como tambin es el caso del mtodo simplex.

MTODO DE COSTO MNIMOALGORITMO DE RESOLUCIN1. 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

SOLUCIN BSICA FACTIBLECOMPROBACIN Nmero de celdas ocupadas

EJERCICIO 2

SOLUCIN BSICA FACTIBLECOMPROBACIN

MTODO DE LA ESQUINA NOROESTE Proporciona una solucin bsica factible. Empieza en la celda 11EJERCICIO 1La 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.

EJERCICIO 2

EJERCICIO 3

MTODO DE APROXIMACIN DE VOGEL (VAM)(MAV) Proporciona Solucin Factible BsicaALGORITMO DE RESOLUCIN1. 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

MTODO DE ASIGNACIN O HNGARO Para su aplicacin debemos tener igual nmero de filas que de columnas No se integra con oferta ni demandaEJEMPLO PARA MINIMIZAR

EJEMPLO PARA MAXIMIZAR

MTODO DE PASOS SECUENCIALESEste 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 rutasCallejones sin salida.- cuando no se encuentran trayectorias apropiadas.ALGORITMO DE RESOLUCIN1. 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 MEN=12200

MTODO DE DISTRIBUCIN MODIFICADA En este mtodo se elabora el circuito en direccin de las manecillas del reloj.EJERCICIO MEN Z=12200

Z= 12000

MTODO DEL CRUCE DEL ARROYO Aqu los ceros constan como celdas llenas.EJERCICIO MEN Z=410

Z= 315 Solucin ptimaComo se puede apreciar, este mtodo es el que nos ofrece una solucin ptima. 1