jueves, 6 de abril de 2017

TEORÍA DE REDES


  La modelación de redes permite la resolución de múltiples problemas de programación matemática mediante la implementación de algoritmos especiales creados para tal fin, conocidos como Algoritmos  de optimización de redes. 
La modelación de redes permite permite la resolución de múltiples problemas de programación matemática mediante la implementacion  de algoritmos especiales creados para tal fin, conocidos como algoritmos de optimizacion de redes.


 CONCEPTOS BÁSICOS EN TEORÍA DE REDES 

Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas líneas llamadas ramales o arcos.


Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales. Por ejemplo una gráfica cuyo flujo en sus ramales sea la electricidad es una red eléctrica. En las redes se usa una simbología específica para denotar su tamaño y elementos que la constituyen, dicha notación es la (N, A) donde N representa el número de nodos que contiene la red y A representa el número de arcos o ramales.


Cadena: Una cadena corresponde a una serie de elementos ramales que van de un nodo a otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7 y que se compone por los elementos [1-4, 4-7].

Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente caso [1, 4, 7].


Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].



Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido determinado, es decir que posee un nodo fuente y un nodo destino.


Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus ramales se encuentran orientados.
Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.

Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.

Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se encuentran orientados hacia afuera.
 
Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se encuentran orientados hacia él.


QUE ES UN ÁRBOL DE DECISIÓN Y PARA QUE SIRVE 

Un Árbol de Decisión (o Árboles de Decisiones) es un método analítico que a través de una representación esquemática de las alternativas disponible facilita la toma de mejores decisiones, especialmente cuando existen riesgos, costos, beneficios y múltiples opciones. 

Los árboles de decisión son herramientas excelentes para ayudar a realizar
elecciones adecuadas entre muchas posibilidades. Su estructura permite
seleccionar una y otra vez diferentes opciones para explorar las diferentes
alternativas posibles de decisión. 

El nombre se deriva de la apariencia del modelo parecido a un árbol y su uso es amplio en el ámbito de la toma de decisiones bajo incertidumbre (Teoría de Decisiones) junto a otras herramientas como el Análisis del Punto de Equilibrio.

Ejemplo de un árbol de decisiones;





lunes, 6 de marzo de 2017

MODELOS DE TRANSPORTE

·       Método de la esquina Noroeste

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.
Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado.
Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste.

EJEMPLO:

·       Método de aproximación de vogel

El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo producen mejores resultados iniciales que los mismos.

EJEMPLO:

·       Método de aproximación de Russell

Para cada renglón de origen i que queda bajo consideración, debe determinarse ui, su mayor costo unitario (cij) de lso que quedan en ese renglón.

Para cada columna de destino que todavía está bajo consideración, se determina vj, su mayor costo unitario de los que hay en esa columna.

Para cada variable xij que no haya sido seleccionada en estos renglones o columnas, se calcula:

         Δij = cij - ui - vj.

Se elige la variable con el mayor valor negativo (en términos absolutos) de Δij. (Los empates se pueden romper arbitrariamente)

EJEMPLO:



jueves, 2 de febrero de 2017

MODELO DE TRANSPORTE

MODELO DE TRASPORTE 

¿QUÉ ES?
·         
     El modelo de transporte es un problema de optimización de redes donde debe determinarse como hacer llegar los productos desde los puntos de existencia hasta los puntos de demanda, minimizando los costos de envió.

   
      El Modelo de transporte es una clase especial de problema de Programación Lineal. Trata la situación en la cual se envía un bien de los puntos de origen (fábricas), a los puntos de destino (almacenes, bodegas, depósitos).



·   OBJETIVO

El objetivo primordial del modelo de transporte es buscar minimizar el cotos de envió de la cantidad de elementos que se enviaran de cada fuente a cada destino, tal que se minimice el costo del transporte total de los envíos. Por otra parte el modelo de transporte establece un método que regula el transporte de mercancías de varias fuentes a varios destinos.

·        CUANDO SE UTLIZA

El problema del transporte o distribución es un problema de redes especial en programación lineal que se funda en la necesidad de llevar unidades de un punto específico llamado Fuente u Origen  hacia otro punto específico llamado Destino.

-       Ejemplo:

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.




Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

Modelo de transporte
Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.

·        TECNICAS Y PASOS

Los pasos básicos del algoritmo de transporte son exactamente iguales a los del método simplex. Sin embargo, en lugar de utilizar la tabla simplex regular, aprovechamos la estructura especial del modelo de transporte para organizar los cálculos en una forma más conveniente.

ü  Paso 1. Determine una solución factible básica inicial y vaya al paso 2.çç

ü  Paso 2. Use la condición de optimalidad del método simplex para determinar la variable de entrada de entre todas las variables no básicas. Si se satisfacen las condiciones de optimalidad, deténgase. De lo contrario, avance al paso 3.

ü  Paso 3. Use la condición de factibilidad del método simplex para determinar la variable de entrada de entre todas las variables básicas actuales, y halle la nueva solución básica. Regrese al paso 2.


·        METODOS

-       El método de la esquina Noroeste: Es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.

Paso 1. Asigne lo más posible a la celda seleccionada, y ajuste las cantidades asociadas de oferta y demanda restando la cantidad asignada.

Paso 2. Tache la columna o fila con oferta o demanda cero para indicar que no se hagan más asignaciones en esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tache sólo una, y deje una oferta (demanda) cero en la fila (columna) no tachada.

Paso 3. Si se deja sin tachar exactamente una fila o columna, deténgase. De lo contrario, muévase a la celda a la derecha si acaba de tachar una columna, o abajo si acaba de tachar una fila. Vaya al paso 1.

-       El método de aproximación de Vogel: es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.

Paso 1. Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.

Paso 2. Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

Paso 3. De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).

Paso 4: de ciclo y excepciones
- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.
- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.
- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.

-       El método del costo mínimo o de los mínimos costos: es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos.

Paso 1: De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.

Paso 2: En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.

Paso 3: Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse". La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".

BIBLIOGRAFIA 
https://jrvargas.files.wordpress.com/2009/01/investigacic3b3n-de-operaciones-9na-edicic3b3n-hamdy-a-taha-fl.pdf

domingo, 15 de enero de 2017

Investigación de Operaciones.


 INVESTIGACIÓN DE OPERACIONES.

Historia.

 La investigación de operaciones tiene su origen a raíz de que la mano del hombre fue reemplazada por las maquinas, es decir en la época de la revolución industrial,  a través de los años fue evolucionando y es así como la segunda guerra mundial tuvo mucho esplendor al elaborar planes de ataque gracias a la IO, siguió evolucionando, en Gran Bretaña con la creación del método simplex para el problema de programación lineal y así fue sucesivamente con diferentes tipos de programación. En la investigación de operaciones, las computadoras son la herramienta fundamental en la investigación de operaciones.

 La investigación de operaciones IO aspira a determinar el mejor curso de acción (optimo) de un problema de decisión con la restricción de recursos limitados 

 La Investigación de Operaciones, es la aplicación del método científico por un grupo multidisciplinario de personas a un problema, principalmente relacionado con la distribución eficaz de recursos limitados (dinero, materia prima, mano de obra, energía), que apoyados con el enfoque de sistemas (este enfoque, es aquel en el que un grupo de personas con distintas áreas de conocimiento, discuten sobre la manera de resolver un problema en grupo.). Puede considerarse tanto un arte como una ciencia. Como arte refleja los conceptos eficiente y limitado de un modelo matemático definido para una situación dada. Como ciencia comprende la deducción de métodos de cálculo para resolver los modelos.

ELEMENTOS DE UN MODELO DE DECISIONES.

  La investigación de operaciones nos ayuda a  detectar un problema y resolverlo esto no es fácil por lo cual se dice que la IO es un arte y ciencia.

 Se dice que es una ciencia ya que ofrece técnicas y algoritmos matemáticos, se dice que es un arte ya que el éxito depende de la creatividad y la habilidad de los analistas encargados de tomar las decisiones es decir interviene el capital humano 
 Componentes básicos de toma de decisión:
  1.  Opciones de decisión.- hay problema
  2.  Restricciones de los problemas.-se restringe a un problema 
  3.  Criterio de objetivo.- la mejor opción que te convenga


TIPOS DE MODELOS DE INVESTIGACIÓN DE OPERACIONES.

Un modelo es una representación ideal de un sistema y la forma en que este opera. El objetivo es analizar el comportamiento del sistema o bien predecir su comportamiento futuro. Obviamente los modelos no son tan complejos como el sistema mismo, de tal manera que se hacen las suposiciones y restricciones necesarias para representar las porciones más relevantes del mismo. Claramente no habría ventaja alguna de utilizar modelos si estos no simplificaran la situación real.

·         Modelo matemático; Tiene a considerar el sistema desde un nivel menos detallado, este modelo bien diseñado es muy adecuado desde el punto de vista computacional. El desarrollo de un modelo de simulación es muy costoso en tiempo y recursos.

·         Modelo de simulación; ofrece una mayor flexibilidad en la representación de sistemas complejos. La razón principal es que la simulación enfoca el sistema desde un nivel básico elemental

EFECTO DE LA DISPONIBILIDAD DE DATOS EN LA REPRESENTACIÓN POR MEDIO DE MODELOS.

Aunque un modelos este bien defino la calidad de la solución depende evidentemente de la eficacia con que podamos estimar los costos de transporte unitarios. En algunos casos quizás no se conozcan con certeza los datos, más bien determina a través de distribuciones de probabilidad

CÁLCULOS DE INVESTIGACIÓN DE OPERACIONES.

Los tipos de cálculo existentes son los tipos de modelos, el modelo de simulación, los cálculos son comúnmente voluminoso y consumen mucho tiempo.
 Por otra parte los cálculos de los modelos matemáticos de la IO son por lo común de naturaleza iterativa
 No todos los modelos matemáticos de la IO poseen algoritmos o métodos de solución, las dificultades evidentes de los cálculos de los modelos matemáticos han obligado a los analistas a buscar otros medios de cálculo, pero no garantizan la optimidad de la solución final, tales métodos pueden denominarse heurístico porque su lógica está basada en reglas o métodos prácticos que conllevan a obtener una buena solución  
 Los métodos heurísticos suelen emplearse para 2 fines:

1.    Se pueden utilizar dentro del contexto de un algoritmo de optimización exacto, con fin de aumentar la velocidad del proceso para alcanzar el nivel optimo

2.    Se utilizan simplemente para obtener una buena solución al problema

FASES DE UN ESTUDIO DE INVESTIGACIÓN DE OPERACIONES.

Un estudio de IO no puede ser realizado y controlado solo por el analista de IO. En otras palabras un analista de IO comete un grave error al suponer que puede resolver problemas sin la cooperación de aquellos que implantaran sus recomendaciones.
 Las principales fases a través de las cuales pasaría el tiempo a fin de efectuar un estudio de IO son:

1.    Definición del problema.
2.    Construcción del modelo.
3.    Solución del modelo.
4.    Validación del modelo.
5.    Implementación de la solución.

La definición del problema; implica definir el alcance del problema investigado. Esta función debe ser realizada por todo el equipo de IO. El objetivo es identificar tres elementos principales del problema de decisión: (a) una descripción de la meta o el objetivo del estudio; (b) una identificación de las alternativas y decisión del sistema, y (c) un reconocimiento de las limitaciones, restricciones y requisitos del sistema.

La construcción del modelo; implica un intento de transformar la definición del problema en relaciones matemáticas. Si el modelo resultante se ajusta a uno de los modelos matemáticos estándar, como la programación lineal, se suele obtener una solución utilizando los algoritmos disponibles. Por otra parte, si las relaciones matemáticas son demasiado complejas como para permitir la determinación de una solución analítica, el equipo de IO puede optar por simplificar el modelo y utilizar un método heurístico, o bien considerar la simulación, si es lo apropiado. En algunos casos, una simulación matemática puede combinarse con modelos heurísticos para resolver el problema de decisión.

La solución del modelo; es por mucho la más sencilla de todas las fases de IO porque implica el uso de algoritmos de optimización bien definidos. Un aspecto importante de la fase de solución del modelo es también conocido como el análisis de sensibilidad. Tiene que ver con la obtención de información adicional sobre el comportamiento de la solución óptima cuando el modelo experimenta algunos cambios de parámetros. El análisis de sensibilidad es particularmente necesario cuando no se pueden estimar con precisión los parámetros del modelo. En estos casos es importante estudiar el comportamiento de la solución óptima en el entorno de los parámetros estimados.

La validez del modelo; Un modelos es válido si, independientemente de sus inexactitudes al representar el sistema, puede dar una predicción confiable del funcionamiento del sistema, un método común para probar la validez de un modelo es comparar su funcionamiento con algunos datos pasados disponibles en el sistema actual. También ya que el modelo está basado en el examen cuidadoso de datos anteriores, esta comparación siempre deberá revelar resultados favorables.

La implementación de los resultados finales; Esta última fase habla sobre la implementación de los resultados probados del modelo. La implementación  de la solución de un modelo validado implica la transformación de los resultados en instrucciones de operación comprensibles que se emitirán a las personas que administrarán el sistema recomendado. La responsabilidad de esta tarea recae principalmente en el equipo de IO

OPTIMIZACIÓN.-

La optimización le ayuda a encontrar la solución que le brinda los mejores resultados, le da la utilidad más alta (producción o valor deseado), o el resultado con el mínimo costo (desperdicio o valor no deseado). Estos problemas involucran el uso más eficiente de los recursos, incluyendo tiempo, dinero,  maquinaria, personal, inventario y otras más.

APLICACIONES DE IO.


Las IO se puede aplicar casi en todo desde un problema muy personal y común hasta un problema a de una gran empresa muy conocida, la planificación de la producción, transporte, las finanzas, problemas de portafolios de inversión, presupuesto de capital, problemas de mezclas o aleaciones, programación de horarios, modelos de inventarios, asignación de recursos, problemas de producción mixta, problemas de redes de distribución, problemas de localización de plantas,  balanceo de línea de ensamble (minimizar ciclo de tiempo), modelos de planeación estratégica, y mucho más, todo esto con una sola finalidad hacer más fácil la vida del ser humano.