Problema de transporte

1. tipos de modelos
  1. red
    1. nodos
      1. fuente
      2. destino
    2. arcos
      1. costos de transporte
  2. modelo de programación lineal
    1. variables
      1. número de unidades a transportar de la fuente i al destino j
    2. restricciones
      1. oferta
        son las restricciones que se encargan de restringir la oferta
      2. demanda
        son la restricciones que se encargan de que la demanda se cumpla.
    3. minimizado
      1. minimiza el costo total del transporte
  3. tabla
    1. filas = fuentes
    2. columnas = destinos
      1. para este caso se agrego una columna para que el problema este equilibrado y se pueda resolver
  4. pasar de un modelo a otro
2. métodos de solución
  1. MPL
    1. método simplex
  2. tabla
    1. método simplex
      1. solución inicial
        método de la esquina noroeste
        La desventaja de este procedimiento es que no toma en cuenta los costos y se deben realizar muchas iteraciones para llegar a la solución óptima.
        Pasos
        Paso 1: En la posición (1,1) asignar X11=min {b1, a1}, restar de la oferta a1 y de la demanda b1, uno de estos dos valores se volverá cero.
        Paso 2: Si a1 se vuelve cero pasar a la posición (2,1) y X21= min {b1-X11, a2}. Si b1 se vuelve cero pasar a la posición (1,2) y hacer X12= min {a1-X11, b2}.
        Paso 3: Continuar con la misma lógica hasta llegar a la posición (m,n), la solución que se tenga será básica y factible
        método de costo mínimos
        Considera costos en la solución que se obtiene, sin embargo no da una solución óptima y se requieren hacer algunas iteraciones para llegar a la solución óptima.
        pasos
        paso !: Asignar el valor más grande posible a la variable (posición) con el costo menor unitario de toda la tabla (empates se rompen arbitrariamente)
        Tachar o marcar el renglón o columna satisfecha. Si tanto el renglón como columna se satisfacen de manera simultánea solo tachar uno.
        paso 2: Ajustar la oferta y la demanda de los renglones y las columnas no tachadas
        Paso 3: Regresar al paso 1
        El procedimiento llega a su fin cuando queda un renglón o bien una columna sin tachar.
        método de voguel
        Este método es el mejor de los tres ya que con este se obtiene soluciones iniciales muy próximas a la solución óptima.
        pasos
        paso !: Evaluar para cada renglón (y columna) una penalización igual a la diferencia entre los dos costos más pequeños en el renglón (columna).
        paso 2: Elegir el renglón o columna con la penalización más grande.
        Tomar a la variable básica la que tenga en ese renglón o columna el costo de envío más pequeño.
        paso 3: Asigne a esta variable el valor más grande posible de acuerdo a las ofertas y demandas
        cancele el renglón o columna (sólo una) satisfecha y cambie la oferta y demanda asociada con la variable básica.
        Ir al paso 1 (solo utilice celdas que no se encuentren en un renglón o columna tachadas)
      2. variable de entrada
        método de los multiplicadores
        Se utilizan los multiplicadores ui y vj, asociados al renglón i y a la columna j de la tabla de transporte
        Para cada variable básica Xij de la solución actual, los multiplicadores ui y vj deben satisfacer la siguiente ecuación
        Ui+Vj=Cij para cada v. básica Xij
        Para cada variable no básica será necesario calcular su Zpq-Cpq, siendo Xpq la variable no básica, como sabemos que Zpq=Up+Vq, entonces será necesario calcular:
        Up+Vq - Cpq
        Para este caso la variable de entrada será aquella que tenga el Up+Vq-Cpq más positivo (recordando que estamos minimizando)
      3. variable de salida
        construcción de un ciclo
        El ciclo inicia y termina en la variable de entrada.
        Este ciclo consta de los segmentos sucesivos horizontales y verticales conectados cuyos puntos extremos deben ser variables básicas, salvo la variable de entrada
        Solo se puede construir un ciclo único para cada variable no básica a partir de una solución.
        Ѳ= min{Ѳ-}
3. matriz A
  1. tiene m+n renglones y m*n columnas
  2. sus elementos son 0 y 1
  3. matriz de coeficientes tecnológicos
  4. propiedades
    1. rango de A m+n-1: número de variables básica
    2. unimodularidad determinante de la matriz {0,1,-1}
    3. triangularidad superior de la matriz básica

Next up

Problema de transporte

Description

Resource summary

Media attachments

Similar

	Created by Quetzally Ortega almost 8 years ago

	Copied by Quetzally Ortega almost 8 years ago