Investigación de Operaciones en Redes

Árbol de Expansión. Algoritmo de la Ruta. Método del Transporte. Vogel. Ruta Crítica

  • Enviado por: El remitente no desea revelar su nombre
  • Idioma: castellano
  • País: Colombia Colombia
  • 56 páginas
publicidad
cursos destacados
Ópera y Música Escénica en el Siglo XX. Vanguardia y Mirada Retrospectiva.
Instituto Superior De Arte - I/art
En el siglo XX hablamos de “Teatro musical” antes que de “ópera” con el fin de integrar todas las modalidades...
Solicita InformaciÓn

Modelado en 3D
Dsigno
El curso de Modelado en 3D está especialmente diseñado para formarte en el modelado, caracterización material,...
Solicita InformaciÓn

publicidad

CONTENIDO

INTRODUCCIÓN

1. MÉTODO DEL TRANSPORTE

  • FORMULACIÓND DEL PROBLEMA GENERAL DE TRANSPORTE

  • MÉTODOS UTILIZADOS EN LA PRIMERA FASE

  • Método de la Esquina Noroeste

  • Método de Vogel

  • Método del Coste Mínimo

  • Ejercicio de Aplicación Métodos Primera Fase

  • MÉTODOS UTILIZADOS EN LA SEGUNDA FASE

  • 1.3.1 Ejercicio de Aplicación del Método de Stepping-Stone

    1.3.2 Ejercicio de Aplicación del Método de Distribución Modificado

  • PROBLEMA DE ASIGNACIÓN (MÉTODO HÚNGARO)

  • 1.4.1 Ejercicio de Aplicación

    2. MÉTODO DE REDES

    2.1 ARBOL DE EXPANSIÓN MINIMA

    2.1.1 Ejercicio de Aplicación

    2.2 ALGORITMO DE LA RUTA MÁS CORTA

    2.2.1 Ejercicio de Aplicación

    2.3 ALGORITMO DEL FLUJO MÁXIMO

    2.3.1 Ejercicio de Aplicación

    2.4 ALGORITMO DE REDES CAPACITADAS DE COSTO MÍNIMO

    2.4.1 Ejercicio de Aplicación

    2.5 ALGORITMO DE LA RUTA CRÍTICA (CPM)

    2.5.1 Ejercicio de Aplicación

    CONCLUSIONES

    BIBLIOGRAFÍA


    INTRODUCCIÓN

    En este trabajo se tratan dos aplicaciones especiales de la programación lineal: los problemas de transporte y de asignación y problemas de redes.

    En el primer capítulo, se abarcará el problema de transporte que estudia la distribución de un producto homogéneo desde un conjunto de fábricas a un conjunto de almacenes o puntos de venta de modo que se satisfagan las demandas de los almacenes y no se superen las disponibilidades de las fábricas, con coste mínimo. Se identifican dos fases en la solución de los problemas; en la primera encontramos los métodos de la esquina noroeste (MEN), de Vogel y de coste mínimo. En la segunda fase se utilizan los métodos de Stepping-Stone y MODI (distribución modificada, también denominada u-v).

    Por su parte, en el segundo capítulo, analizaremos el problema de redes. Dentro de los métodos que veremos aquí encontramos: árbol de expansión mínima, algoritmo de la ruta más corta, algoritmo del flujo máximo, algoritmo de redes capacitadas de costo mínimo y el algoritmo de la ruta crítica.

  • MÉTODO DEL TRANSPORTE

  • El modelo de transporte tiene notable interés por sus importantes aplicaciones que, como se vera en varios ejercicios, no se restringe únicamente a la distribución de mercancías.

    Su procedimiento especifico de solución, llamado algoritmo de transporte consta de dos fases y es rápido y eficiente. La primera fase consiste en obtener una solución factible inicial. Se pasa después a la segunda fase, en la que se comprueba si la solución obtenida en la primera fase es óptima, y si no lo es, como mejorarla.

    1.1 FORMULACIÓN DEL PROBLEMA GENERAL DE TRANSPORTE.

    El problema de Transporte presenta una estructura especial de programación lineal, que requiere de la programación entera y de la no-negatividad.

    Puede decirse que, existen m orígenes que surten a n centros de consumo (destinos) para cierto producto.

    La capacidad de oferta del origen (i) es Investigación de Operaciones en Redes
    filas.

    La demanda del centro de consumo ( j ) es Investigación de Operaciones en Redes
    con j = 1,2,3,...,n columnas.

    Teniendo en consideración el costo unitario de enviar el producto Investigación de Operaciones en Redes
    del origen (i) al centro de consumo ( j ).

    Y de esto resulta la siguiente cuestión: ¿Cuántas unidades del producto se deben enviar del origen ( i ) al centro de consumo ( j ), de manera que comúnmente se minimicen los costos totales de Transporte, se esté satisfecha la demanda del centro de consumo sin exceder la capacidad de la oferta del origen ( i)?

    El problema de transporte se representa a continuación como una matriz, que puede estar en función a los costos Investigación de Operaciones en Redes
    o a los flujos Investigación de Operaciones en Redes

    DESTINO

    ORIGEN

     

    1 2 3 ... Investigación de Operaciones en Redes

     

    OFERTA Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    DEMANDA Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

     

    Expresado en forma general queda:

    Investigación de Operaciones en Redes

    de donde

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes
    para j = 1, 2, 3, ..., n

    donde Investigación de Operaciones en Redes
    es la cantidad de recursos (x) asignados al destino ( j ) con su costo unitario (i).

    Desarrollando la función objetivo, se tiene

    Investigación de Operaciones en Redes

    Aunque la matrices de Transporte pueden presentarse de la siguiente manera:

    Caso 1.

    Que la oferta total sea mayor que la demanda total

    Es decir, Investigación de Operaciones en Redes
    .

    Se tendrá que añadir un centro de consumo artificial(n+1) cuya demanda Investigación de Operaciones en Redes
    en los cuales los costos unitarios Investigación de Operaciones en Redes
    , son todos ceros con

    k= 1,2,...,m que de forma matricial se expresa de la siguiente manera:

     DESTINO

    ORIGEN

    Columna

    agregada

    Investigación de Operaciones en Redes

    OFERTA

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    DEMANDA Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

     

     

    Caso2.

    Que la demanda total sea mayor que la oferta total, o sea:

    Investigación de Operaciones en Redes

    para lo cual se añadirá una fila a la matriz, que será (m+1), con capacidad de oferta Investigación de Operaciones en Redes
    , los costos unitarios Investigación de Operaciones en Redes
    son ceros, quedando la matriz de costos como sigue.

    DESTINO

    ORIGEN

     

    1 2 ... n

    OFERTA

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

    DEMANDA Investigación de Operaciones en Redes

    Investigación de Operaciones en Redes

     

    El objetivo de aumentar una columna o agregar una fila es el de balancear el problema de Transporte. Una vez hecho esto, se requerirá que la solución inicial sea básica y factible.

    Para esto, los métodos de resolución al problema de Transporte para obtener la solución inicial son:

    1. PRIMERA FASE:

    • Método de la Esquina Noroeste

    • Método Vogel.

    • Método del Coste Mínimo

    2. SEGUNDA FASE

    • Método de Stepping - Stone

    • Método Distribución Modificada (MODI)

    3. PROBLEMA DE ASIGNACIÓN (MÉTODO HÚNGARO)

  • MÉTODOS UTILIZADOS EN LA PRIMERA FASE

  • Método de la Esquina Noroeste.

  • También llamado noroccidental o de extremos, presenta la construcción de una matriz de flujos de la siguiente manera.

    Paso1

    En la posición (1, 1) que es el extremo Noroeste , se decide a Investigación de Operaciones en Redes
    , por lo tanto alguno de los valores se hacen cero.

    Paso 2.

    Si Investigación de Operaciones en Redes
    es CERO, se pasa a la posición que le sigue ( "abajo" en la columna) que es la (2, 1), para hacer Investigación de Operaciones en Redes
    Se cancela el resto de la fila con ceros; además no se considerarán estas posiciones en un futuro, exceptuando la posición Investigación de Operaciones en Redes
    .

    Por otro lado, si Investigación de Operaciones en Redes
    , en el paso anterior, se pasa a la posición contigua (que en este caso sería (1, 2), tal que Investigación de Operaciones en Redes
    Se cancela lo restante de la columna con ceros, y se descarta de consideración futura alguna, con excepción de la posición Investigación de Operaciones en Redes

    Paso3.

    Continuar con la misma lógica hasta llegar a la posición (m, n) de la matriz de flujos.

    En esta forma se obtendrá una solución inicial factible, básica; pero bastante distante del óptimo para el problema del transporte.

    Donde :

    Investigación de Operaciones en Redes

  • Método de Vogel

  • El algoritmo del Método Vogel para obtener una solución básica factible de un problema de Transporte es el que se muestra a continuación:

    Paso 1.

    Construcción de una matriz de costos y flujos en relación a un problema balanceado.

    Ir al paso 3.

    Paso2.

    Usar el remanente de costos y flujos de la matriz, hasta que los flujos estén asignados.

    Paso3.

    Calcular las diferencias de las filas y de las columnas de la matriz de costos. Esta diferencia resulta entre los números más pequeños (tanto de filas como de columnas).

    Paso4.

    Seleccionar a la fila o a la columna que tenga la mayor diferencia. En caso de empate, se decide arbitrariamente.

    Paso 5.

    Localizar el costo más pequeño en la matriz de costos en la fila o la columna seleccionada en el paso anterior. Esta será la posición Investigación de Operaciones en Redes

    Paso 6.

    En la matriz de flujos , decidir Investigación de Operaciones en Redes
    , con ( i, j ) identificado en el paso anterior.

    Se considerará determinar la oferta con Investigación de Operaciones en Redes
    , y la demanda será Investigación de Operaciones en Redes
    .

    Paso7.

    • Si Investigación de Operaciones en Redes
      , llénese la fila i con ceros, exceptuando la posición Investigación de Operaciones en Redes
      , eliminando la fila de cualquier consideración futura.

    • De resultar Investigación de Operaciones en Redes
      , se llenará la columna j con ceros, con excepción de la posición Investigación de Operaciones en Redes
      , las posiciones restantes se descartadas de tomarse en cuenta.

    Continuar con el paso 2 del algoritmo.

  • Método de Coste Mínimo

  • El método del coste mínimo asigna el mayor número posible de unidades a la posición de menor coste eliminando la fila y/o columna que quede satisfecha, y repite el proceso hasta eliminar todas las filas y columnas.

  • Ejercicio de Aplicación Métodos Primera Fase

  • Dada la tabla de transporte:


     

     

    1

    2

    3