Método Stepping Stone


El método stepping-stone llega a la solución óptima partiendo de una solución inicial e investigando si puede obtenerse alguna solución mejor. Como el método parte de una solución inicial, debemos encontrar una solución factible cualquiera para poder utilizar el método.

Existen diversos métodos que pueden utilizarse para obtener una solución inicial factible; todos ellos, sin embargo, se basan en la máxima cantidad que podrá asignarse a una celda cualquiera de la matriz de transportes.

Hecha la asignación, se elimina la fila (o columna) de la matriz en la que se alcanzó la oferta (demanda) y se procede a elegir otra celda para asignar, hasta que no haya más sobrantes de oferta y demanda.

Sin embargo, los métodos se diferencian en la elección de la celda. Hay tres métodos que normalmente se presentan en la literatura:

El programa DDM implementa el Método de la esquina noroeste.

Optimización
El algoritmo de optimización será:

  1. Equilibrar ofertas y demandas
    Si la sumatoria de las ofertas es mayor que la de las demandas, cree una demanda ficticia con la diferencia en valor absoluto; y si la sumatoria de las demandas es mayor que la de las ofertas, cree una oferta ficticia con la diferencia en valor absoluto.
  2. Crear una solución inicial
    Puede usarse el Método de la esquina noroeste:
    1. Comenzar por la variable X11
    2. Si aún hay oferta disponible, pasar a la variable Xi+1, j
    3. Si solo hay demanda disponible, pasar a la variable Xi, j+1
    4. Continuar hasta obtener todas las variables básicas (las que tienen un círculo); todas las otras variables (no básicas) serán cero.
  3. Prueba de optimalidad
    1. Asumiendo una solución básica:
    2. Una Solución Básica Factible es óptima si y solo si:
      Cij – Ui – Vj ≥ 0

      para todo (i, j) en que Xij es variable no básica

      Si la solución es óptima, detenga la ejecución; si no, continúe con el siguiente paso
    3. Elegir la VB de entrada (VBE)
      • Como Cij – Ui – Vj representa la tasa a la que la función objetivo evolucionará a medida que la variable no básica Xij aumenta, la VBE deberá tener un coeficiente Cij – Ui – Vj negativo para disminuir el costo total.
      • La VBE será la que tenga el coeficiente Cij – Ui – Vj más negativo, es decir, X13
    4. Elegir la VB de salida
      • Aumentar la VBE provocará una reacción en cadena, en la cadena que definimos.
      • Así, pasaremos a tener celdas receptoras y celdas proveedoras, representadas en el Cuadro de Transportes por los signos + y –
      • En este caso utilizaremos la cadena marcada en rojo
      • El valor que se transferirá de las celdas proveedoras a las receptoras está dado por el mínimo (x11 = 70, x23 = 75), es decir, 70
      • VBE = x11
    5. Identificar la nueva solución básica factible
    6. Volver al paso 1
  4. Después de la ejecución del algoritmo, todas las variables estarán calculadas y la lista de variables básicas VB contendrá los valores de las cantidades que se transportarán