Problemas de Flujo con Costo Mínimo

Páginas: 15 (3633 palabras) Publicado: 21 de enero de 2014
UNIVERSIDAD NACIONAL DEL CALLAO
FACULTAD DE CIENCIAS NATURALES Y MATEMÁTICA
ESCUELA PROFESIONAL DE MATEMÁTICA












“MÉTODO SIMPLEX EN PROBLEMAS DE PROGRAMACIÓN LINEAL DEL TIPO DE FLUJO DE COSTO MÍNIMO”


HÉCTOR AQUILES LLANOS VALENCIA
JULIO 2013

CALLAO –PERÚ

ÍNDICE



Resumen……………………………………………………………………………………….…...2

Introducción……………………………………………………………………………………..…..3

1. Capítulo I…………………………………………………………………………………………4
Marco Teórico

1.1. Red Dirigida………………………………………………………………………………..…..4
1.1.1. Tipos de Red Dirigida……………………………………………………………………….4
Trayectoria……………………………………………………………………………………….…..4Cadena………………………………………………………………………………………………..5
Circuito………………………………………………………………………………………………..5
Ciclo……………………………………………………………………………………………..….…6
Árbol………………………………………………………………………………………………..…6
1.2. Espacio Vectorial Euclidiano n-dimensional……………………………………………..….6
1.3. Combinación Lineal………………………………………………………………………...…..7
1.4 Independencia Lineal………………………………………………………………………..….7
1.5 Matriz No Singular…………………………………………………………………………..…..7
1.6 rango de una Matriz…………………………………………………………………………..…7

2. CapítuloII………………………………………………………………………………………….8
Flujo con Costo Mínimo

2.1. Introducción……………………………………………………………………………………..8
2.2. Definiciones……………………………………………………………………………………..8
2.2.1. Flujo……………………………………………………………………………………………8
2.2.2. Matriz de Incidencia Nodo- Arco……………………………………………………………8
2.2.3. Modelo General de un Problema de Flujo con Costo Mínimo…………………………..9
2.2.4. ÁrbolGenerador……………………………………………………………………………..11
2.2.5. Rango de una Matriz de Incidencia Nodo-Arco…………………………………………..12
2.2.6. Variable Artificial……………………………………………………………………………..13
2.2.7. Método de los Ciclos………………………………………………………..………………14
2.3. Solución Inicial Básica Factible………………………………………………………………16
2.4. Cálculo de los ………………………………………………………………………..21
2.5. Determinación de la Columna de Salida…………………………………………………....23

Conclusiones………………………………………………………………………………………..28Bibliografía…………………………………………………………………………………………..29


RESUMEN


A partir de la necesidad de transportarse cierto recursos disponibles a través de un red, para satisfacer la demanda a un costo mínimo, nace el Problema de Flujo con Costo Mínimo (PFCM), en el presente trabajo se dará a entender que este tipo de problema es un tipo más de los Problemas de Programación Lineal y por tanto podrán ser resueltosmediante un algoritmo Simplex para Redes el cual podremos entenderlo como una especialización del Método Simplex Primal. Pues se requerirán de nuevas definiciones como Red Dirigida, Matriz de Incidencia, Árbol Generador Enraizado, etc.
Pudiendo concluir así, que el Método Simplex para Redes es bastante poderoso en la resolución de Problemas de Flujo con Costo mínimo.






ABSTRACTFrom the need for certain resources transported through a network to meet the demand at minimum cost, the problem arises with Minimum Cost Flow (PFCM), in the present work given to understand that this type of problem is one more type of linear programming problems and therefore can be solved by simplex algorithm for network swhich we can understand as a specialization of the Primal Simplex method.As new definitions are required as Red Directed, Incidence matrix, Generator Rooted Tree, etc..
We can conclude thus that the Simplex Method for Networks is quite powerful in solving flow problems with minimum cost.








INTRODUCCIÓN



Los problemas de programación lineal son modelos lineales que tiene por característica surgir con frecuencia de diferentes aspectos de la vidareal y tener una representación natural mediante un modelo de red.


Los problemas en redes dirigidas que estudiaremos aquí, están relacionados con la existencia de un flujo a lo largo de los arcos de la red que generalmente se refiere al envío o circulación de...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Problema De Flujo De Costo Mínimo
  • flujo de costo minimo y maximo
  • Flujo de costo mínimo
  • Flujo de costo minimo
  • Flujo maximo y flujo minimo
  • Costo Minimo
  • Costo minimo
  • costo minimo

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS