MoDelos De Optimizacion De Recursos
Modelos de Optimización de Recursos
Unidad III: Algoritmos especiales de
programación línea
Unidad IV: Modelos de flujos en redes
Martin Dominguez Luis Enrique
Profesor:
Dr. Ing. Espinet Vázquez Salvador Felipe
Carrera:
Ingeniería Civil
Semestre:
3
Grupo:
“C”
Aula:
10
[Año]
[Seleccionar fecha]
Tabla de contenido
Algoritmosespeciales de programación lineal……………………………………..2
El problema del Transporte2
Caso en que la producción es mayor a la demanda 3
Caso en que la demanda es mayor a la producción 4
Problema de Asignación6
Métodos para encontrar soluciones factibles 7
Método de la esquina noroeste………………………………………………………..8
Etapas del método algoritmo húngaro…………………………………………..…13Ejercicio…………………………………………………………………………………..14
Modelos de flujos en redes………………………………………………………...…16
Modelos de redes…………………………………………………………………….…16
Modelo de Flujo Máximo………………………………………………………………17
Modelo de la ruta más corta…………………………………………………………..18
Notación y terminología…………………………………………………………….…19
Redes dirigidas y no dirigidas………………………………………………………..21
Aplicaciones prácticas de la optimización de redes…………………………..…21
Ejemplos de términos………………………………………………………………….22
Problema delflujo de costo mínimo………………………………………………...23
Ejercicio…………………………………………………………………………………..24
Bibliografía………………………………………………………………………………26
Algoritmos especiales de programación línea
El problema del Transporte
Son problemas balanceados de transporte en los cuales todas las ofertas y todas las demandas son iguales a 1. Además tiene como objetivo determinar que hay que enviar desde unos puntos deorigen a unos puntos de destino sin superar los límites que establece la oferta y de forma que minimice el costo por asignación de los recursos para el desempeño de actividades.
Este modelo consiste en determinar la asignación optima de agentes u objetos indivisibles a n tareas por lo que ningún agente será designado a una y sólo una tarea.
Por lo que podemos resumir que este modelo consiste eldeterminar la asignación optima de los agentes de los puntos de origen a los puntos de destino pero recordar que son problemas de programación entera por lo que las variables o agentes tendrán que tomar valores enteros.
Los cuatro elementos principales de este problema son:
1. Datos
m: el número de orígenes
n: el número de destinos
ui: la cantidad que debe enviarse desde el origen i
vj :la cantidad que debe ser recibida en el destino j
cij : el coste de envío de una unidad de producto desde el origen i al destino j
2. Variables
xij : la cantidad que se envía desde el origen i al destino j.
Se supone que las variables deben ser no negativas:
xij ≥ 0; i = 1, . . . , m; j = 1, . . . , n (1.1)
Esto implica que la dirección de envío del producto está=
Caso en que la producción es mayor a la demanda ( )
Dentro de estos problemas de transporte podemos encontrar casos en los que la producción es mayor que la demanda. Son casos especiales y se solucionan balanceando el problema agregándole un destino imaginario o artificial en el cual tendrá como demanda la sobreproducción que se encuentra en nuestro problema.Y los costos en este destino se establecerán como cero
donde
dn+1 =
y
ci,n+1 = 0, para i = 1, 2, ..., m
Caso en que la demanda es mayor a la producción ( )
Si el caso es que se tiene mayor demanda de lo que se produce, entonces para balancear el problema se agrega un origen imaginario o artificial el cual tendrá como recursos dicha sobredemanda. En cuanto a los costos asociadosa este nuevo origen los estableceremos a cero
donde
sm+1 =
y
cm+1j = 0 para j = 1, 2, ..., n
Como todas las restricciones funcionales en el problema de transporte son igualdades, el método símplex obtendría una solución inicial básica factible introduciendo variables artificiales y usándolas como variables básicas...
Regístrate para leer el documento completo.