OPTIMIZACIÓN MATEMÁTICA, EL MODELO DE TRANSPORTE COMO CASO ESPECIAL DEL MODELO DE PROGRAMACIÓN LINEAL

in steemstem •  last month

caratula.png



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 Cij según se muestra en la siguiente tabla:

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

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

t2.png
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:

t3.png
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 Xij) 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.

t4.png
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.

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

Asignamos 20 a la variable X12 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

t6.png
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 Cij, las variables que no tengan valores en la tabla se asumen como cero al calcular el costo del transporte.

f1.png

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 ui y vj a las filas i y las columnas j de la tabla del modelo de transporte

t7.png
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

f2.png

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

f3.png

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

f4.png

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

f5.png

Obteniendo

t8.png
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

t9.png
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

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

Es decir X31 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 X31 tendrá un valor asignado ∆.

A incrementar el valor de X31 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

t11.png
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 X11 como variable de salida. Por ser X11 la variable de salida ya no colocamos su valor en la nueva tabla en cambio a pesar de que X22 nos dio cero como no es nuestra variable de salida mantenemos el valor de cero.

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

Iteración N° 2

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

f6.png

Asignando a

f7.png

Obtenemos

f8.png

Para las variables no básicas se evalúa

f5.png

Obteniendo

t13.png
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:

t14.png
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 X14 por tener el mayor valor, por lo tanto construimos el ciclo al igual que en la iteración anterior.

t15.png
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

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

Iteración N° 3

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

f9.png

Asignando a

f7.png

Obtenemos

f10.png

Para las variables no básicas se evalúa

f5.png

Obteniendo

t17.png
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

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

Como todos los

f5.png

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.

f11.png

Con un costo asociado de

f12.png

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.

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

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  





This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @utopian-io and @curie.


If you appreciate the work we are doing then consider voting all three projects for witness by selecting stem.witness, utopian-io and curie!


For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

Congratulations @ydavgonzalez! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You received more than 10000 upvotes. Your next target is to reach 15000 upvotes.

You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

Do not miss the last post from @steemitboard:

Carnival Challenge - Here are the winners

You can upvote this notification to help all Steem users. Learn how here!

Hi @ydavgonzalez!

Your post was upvoted by Utopian.io in cooperation with @steemstem - supporting knowledge, innovation and technological advancement on the Steem Blockchain.

Contribute to Open Source with utopian.io

Learn how to contribute on our website and join the new open source economy.

Want to chat? Join the Utopian Community on Discord https://discord.gg/h52nFrV