Fuente: @ydavgonzalez

Saludos a toda la comunidad de #STEEMSTEM, #STEM-ESPANOL y de Steemit en general, el día de hoy les comparto un post relacionado con la optimización matemática específicamente un tema perteneciente a la Investigación de Operaciones conocido como el modelo de transporte.

En la programación lineal existe un tipo de problema relacionado con el transporte de artículos desde varias fuentes (por lo general fábricas) hasta diversos destinos (por lo general almacenes) satisfaciendo ciertas restricciones relacionadas con la oferta y la demanda, el transporte debe ser realizado con el objetivo de minimizar los costos, de esta forma, se trata también de un modelo de programación lineal que cuenta con una estructura especial conocido como el modelo de transporte, debido a que dicho problema se basa en un modelo de programación lineal puede ser resuelto mediante la aplicación del método simplex, sin embargo, su estructura especial permite aplicar un algoritmo específico que simplifica el proceso de solución.

DEFINICIÓN DEL MODELO

Básicamente se trata de un problema en el que existen m fuentes y n destinos, por cada ruta, es decir, transporte de la fuente i al destino j, hay un costo asociado C_ij según se muestra en la siguiente tabla:

Tabla N°1 Fuentes-Destinos modelo de transporte. Fuente: @ydavgonzalez.

Asumiendo que de la fuente i al destino j se transportan X_ij unidades del producto y que cada fuente tiene una oferta determinada que se representa por O_i y cada destino una demanda determinada del producto que se representa por D_j la tabla del modelo de transporte se representaría de la siguiente forma:

Tabla N° 2 Fuentes-Destinos modelo de transporte. Fuente: @ydavgonzalez.

La tabla se ordena de esta manera debido a que la suma de todas las unidades enviadas desde la fuente i debe ser igual a la oferta disponible para dicha fuente, y la suma de todas las unidades enviadas al destino j debe ser igual a la demanda de dicho destino.

En general el modelo de transporte se basa en la premisa de que el problema está balanceado, es decir, que la oferta total es equivalente a la demanda total, si el modelo no esta balanceado se puede restaurar el equilibrio al agregar una fuente o un destino ficticio según sea el caso.

Ahora analizaremos un ejemplo en el cual se aplica el modelo de transporte, así como el procedimiento utilizado para resolverlo.

Ejemplo N° 1

La chocolatería el antojito caliente tiene 3 sedes en la ciudad de Arequipa ubicadas en diferentes distritos (Paucarpata, Characato y Cerro Colorado), y debe transportar el chocolate a 4 destinos (San camilo, Plaza de Armas, Av Dolores y Yanahuara) los costos de transporte por unidad (en soles) así como la oferta y demanda se muestran en la siguiente tabla:

Tabla N°3 Modelo inicial del ejemplo 1. Fuente: @ydavgonzalez.

Básicamente se trata de determinar la cantidad de chocolate que debe transportarse de cada destino a cada fuente (Variables X_ij) de modo que se satisfagan las restricciones de oferta y demanda y se minimice el costo del transporte.

Para resolver el problema se debe determinar una solución básica de inicio a partir de la cual mediante la determinación de las variables de entrada y salida de la tabla se va iterando hasta llegar a la solución óptima.

DETERMINACIÓN DE LA SOLUCIÓN BÁSICA DE INICIO – MÉTODO DE LA ESQUINA NOROESTE

El método de la esquina noroeste o de la esquina superior izquierda, comienza en la esquina superior izquierda a la cual asigna el mayor valor posible sin exceder las restricciones de oferta y demanda.

Tabla N°4 Método de la esquina noroeste. Fuente: @ydavgonzalez.

No se puede asignar un valor mayor a 10 debido a que la demanda para el destino 1 es de 10 unidades, como ya la demanda para el destino 1 (columna 1) está satisfecha salimos de esa columna hacia la siguiente columna.

Tabla N° 5 Cálculos del Método de la esquina noroeste. Fuente: @ydavgonzalez.

Asignamos 20 a la variable X₁₂ debido a que con ese valor la oferta alcanza el máximo valor posible y luego pasamos a la fila inferior debido a que la oferta de la fila 1 ya esta completa, en caso de que la oferta y demanda alcancen el máximo al mismo tiempo se elige si se debe dar por completada la oferta o demanda y se pasa a la siguiente fila o columna (según sea el caso) colocando cero como valor para no exceder las restricciones.

Aplicando el mismo procedimiento se encuentra la solución básica inicial

Tabla N°6 Solución básica inicial Método de la esquina noroeste. Fuente: @ydavgonzalez.

Se observa que el costo del transporte en esta solución básica de inicio viene dado por la suma del producto del número de unidades transportadas de la fuente i al destino j multiplicados por los costos C_ij, las variables que no tengan valores en la tabla se asumen como cero al calcular el costo del transporte.

CÁLCULOS ITERATIVOS – MÉTODO DE LOS MULTIPLICADORES

Una vez encontrada la solución básica de inicio, se procede a aplicar el método de los multiplicadores, asociando los multiplicadores u_i y v_j a las filas i y las columnas j de la tabla del modelo de transporte

Tabla N°7 Solución básica inicial Método de la esquina noroeste. Fuente: @ydavgonzalez.

Ahora para cada variable básica, es decir, que este en la solución básica inicial obtenida por el método de la esquina noroeste, se procede a asociar los multiplicadores según la siguiente ecuación

Según la solución básica del ejemplo se obtiene

Para resolver se iguala alguno de los u_i a cero y se resuelve para los demás valores

A continuación se usan los u_i y v_j obtenidos para evaluar las variables que no estén en la base con la siguiente expresión

Obteniendo

Tabla N°8 Valores de las variables no básicas por el método de los multiplicadores. Fuente: @ydavgonzalez.

Estos valores se representan en la tabla de transporte asignándolos a las variables que no estén en la solución básica inicial, quedando la nueva tabla de la siguiente forma

Tabla N°9 Iteración N° 1 Modelo de Transporte. Fuente: @ydavgonzalez.

Luego para obtener la variable de entrada, se toma la variable no básica cuyo valor sea mayor

Tabla N°10 Variable de entrada Iteración N° 1. Fuente: @ydavgonzalez.

Es decir X₃₁ es la variable de entrada, lo cual implica que se debe transportar desde la fuente 3 al destino 1 para minimizar los costos, es decir, en la siguiente iteración la variable X₃₁ tendrá un valor asignado ∆.

A incrementar el valor de X₃₁ por ∆ se debe mantener el equilibrio en la oferta y demanda, lo cual se logra mediante construir un ciclo cerrado entre la variable entrante y las variables básicas, omitiendo los valores que aparecen en recuadros pequeños, la nueva tabla sería

Tabla N° 11 Construcción del ciclo Iteración N° 1. Fuente: @ydavgonzalez.

Podemos apreciar que al sumar los nuevos valores tanto de las filas como de las columnas se conserva el equilibrio, se observa también que para cada fila o columna el ciclo empieza en un extremo y termina en el otro extremo que sea parte de la solución básica inicial.

Ahora asignamos a ∆ el mayor valor posible de manera que ninguna de las variables básicas de la tabla anterior sea negativa, teniendo en cuenta las relaciones mostradas el mayor valor posible es ∆=10, y resolvemos para dicho valor, la variable básica que nos de cero será la variable de salida en caso de que dos variables básicas nos den cero elegimos cualquiera como variable de salida, este caso sucede en el problema que estamos resolviendo en el cual elegiremos a X₁₁ como variable de salida. Por ser X₁₁ la variable de salida ya no colocamos su valor en la nueva tabla en cambio a pesar de que X₂₂ nos dio cero como no es nuestra variable de salida mantenemos el valor de cero.

Tabla N°12 Solución Básica Iteración N° 1. Fuente: @ydavgonzalez.

Iteración N° 2

Se repite el calculo de los multiplicadores u_i y v_j teniendo en cuenta la nueva solución básica

Asignando a

Obtenemos

Para las variables no básicas se evalúa

Obteniendo

Tabla N°13 Valores de las variables no básicas por el método de los multiplicadores Iteración N° 2. Fuente: @ydavgonzalez.

Resultando en la siguiente tabla de transporte:

Tabla N°14 Iteración N° 2 Modelo de Transporte. Fuente: @ydavgonzalez.

La variable de entrada del modelo de transporte será la variable no básica que tenga el mayor valor, en este caso la variable de entrada es X₁₄ por tener el mayor valor, por lo tanto construimos el ciclo al igual que en la iteración anterior.

Tabla N°15 Iteración N° 2 Construcción del ciclo. Fuente: @ydavgonzalez.

El mayor valor que puede asumir ∆ es 20, para dicho valor se obtiene

Tabla N°16 Iteración N° 2 Solución básica. Fuente: @ydavgonzalez.

Iteración N° 3

Se repite el calculo de los u_i y v_j teniendo en cuenta la nueva solución básica

Asignando a

Obtenemos

Para las variables no básicas se evalúa

Obteniendo

Tabla N°17 Iteración N° 3 Valores de las variables no básicas por el método de los multiplicadores. Fuente: @ydavgonzalez.

Obteniendo la siguiente tabla de transporte

Tabla N°18 Iteración N° 3 Modelo de Transporte. Fuente: @ydavgonzalez.

Como todos los

Son negativos en esta tabla la solución es óptima, por lo tanto la chocolatería debe transportar de la fuente 1: 10 unidades al destino 2 y 20 unidades al destino 4, de la fuente 2: 20 unidades al destino 2 y 30 unidades al destino 3 y de la fuente 3: 10 unidades al destino 1 y 10 unidades al destino 4, de esta forma satisface la oferta y demanda al costo mínimo.

Con un costo asociado de

CONCLUSIONES

1. La optimización matemática posee una gran cantidad de aplicaciones en problemas de la vida cotidiana y en economía.
2. El modelo de transporte debido a poseer una estructura de programación lineal puede ser resuelto mediante el método simplex, sin embargo, el algoritmo de transporte es un método más eficiente utilizado para resolver este modelo.
3. La relación entre el método simplex y el algoritmo de transporte tiene fundamentos matemáticos basados en la teoría de la dualidad.

REFERENCIAS BIBLIOGRÁFICAS Y LECTURAS RECOMENDADAS

1. González (2018) Aplicación del Método Simplex a un problema de maximización de ganancias fundamentado en los tópicos del Álgebra Lineal.

2. González (2018) Optimización Matemática en Modelos de Programación Lineal aplicados a la vida cotidiana, Método Simplex de las dos fases.

3. González (2018) Resolución de Modelos de Programación Lineal utilizando la Herramienta para Optimización Lingo y Análisis de su relación con el Método Simplex.

4. Taha (2004), Investigación de Operaciones. 7ma edición Editorial Pearson.

Si deseas leer contenido científico de calidad en habla hispana te invito a revisar la etiqueta #STEM-ESPANOL donde podrás encontrar diversidad de temas, Matemática, Ingeniería, Física, Química, Biología, Medicina, Ciencia, Tecnología y mucho más.

Logotipo del Área de Matemáticas de #STEM-ESPANOL