Método de la Esquina Noroeste (Algoritmo de Transporte en Programación Lineal)

El Método de la Esquina Noroeste (o esquina superior izquierda) es una heurística que se aplica a una estructura especial de problemas de Programación Lineal llamada Modelo de Transporte, la cual permite asegurar que exista una solución básica factible inicial (no artificial). Otros métodos para la obtención de una solución básica de inicio son el Método de Costo Mínimo y Método de Aproximación de Vogel. En general, el Método de Vogel produce la mejor solución básica de inicio y el de la Esquina Noroeste la peor, sin embargo, el Método de la Esquina Noroeste implica el mínimo de cálculos.

El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la esquina noroeste, o superior izquierda, de la tabla (variable x_{11}). A continuación una descripción de los pasos:

Paso 1: Asignar todo lo posible a la celda seleccionada y ajustar las cantidades asociadas de oferta y demanda restando la cantidad asignada.

Paso 2: Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tachar sólo uno (la fila o columna) y dejar una oferta (demanda) cero en la fila (columna) que no se tachó.

Paso 3: Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a la de abajo si se tachó un reglón. Seguir con el Paso 1.

Método de la Esquina Noroeste

Para ilustrar la aplicación del Método de la Esquina Noroeste consideremos el siguiente problema balanceado de transporte que considera 3 silos productos (oferta) que satisfacen las necesidades de 4 molinos (demanda). El algoritmo de transporte se basa en la hipótesis que el modelo está balanceado, es decir, que la demanda total es igual a la oferta total (si el modelo no está balanceado siempre se podrá aumentar con una fuente ficticia o un destino ficticio para restaurar el equilibrio o balance).

ejemplo-esquina-noroeste

Los costos unitarios de transporte desde el silo i al molino j c_{ij} se representan en la esquina superior derecha de cada cuadro. Por ejemplo el costo unitario de enviar una unidad de producto desde el silo 1 al molino 1 es de $10. Adicionalmente los silos 1, 2 y 3 tienen capacidad u oferta de 15, 25 y 10 unidades, respectivamente. Por otra parte los molinos 1, 2, 3 y 4 tienen requerimientos o demanda de 5, 15, 15 y 15 unidades, respectivamente. El modelo esta balanceado (suma oferta = suma demanda = 50 unidades).

Al aplicar el Método de la Esquina Noroeste al ejemplo anterior se obtienen los siguientes resultados. Las flechas indican el orden en el que se generan las cantidades asignadas:

solucion-esquina-noroeste

  • La cantidad asignada a la celda x_{11} son 5 unidades, dado que si bien el silo 1 tiene capacidad de 15 unidades, el molino 1 sólo necesita (demanda) 5 unidades (no se realizan más asignaciones a la columna 1 correspondiente al molino 1).

  • A continuación nos movemos a la derecha y asignamos lo máximo posible (10 unidades remanentes) a la celda x_{12} (con lo cual se completa la capacidad del silo 1 y en consecuencia no es posible seguir realizando asignaciones en la fila 1).

  • Luego asignamos 5 unidades a la celda x_{22} lo cual es por cierto menor que la capacidad del silo 2 pero lo suficiente para satisfacer los requerimientos del molino 2 (ahora no es posible generar asignaciones adicionales a la columna 2).

  • Nos movemos a la derecha y se asignan 15 unidades del silo 2 al molino 3 (x_{23}=15) lo que cubre inmediatamente los requerimientos del molino 3 (no es necesario asignar más en la columna 3).

  • Nuevamente nos movemos a la derecha y asignamos lo máximo posible (5 unidades que es la capacidad remanente del silo 2, es decir, x_{24}=5) con lo cual el silo 2 opera a máxima capacidad (ahora ya no es posible nuevas asignaciones en la fila 2).

  • Finalmente se asignan 10 unidades del silo 3 al molino 4 (x_{34}=10) cubriendo la demanda de dicho molino (y la capacidad del correspondiente silo).

En consecuencia la solución básica factible inicial es: x_{11}=5, x_{12}=10, x_{22}=5, x_{23}=15, x_{24}=5, x_{34}=10 que reporta un costo del programa (valor en la función objetivo) de: Z=5(10)+10(2)+5(7)+15*(9)+5(20)+10*(18)=$520. Notar que si se implementa computacionalmente el problema anterior haciendo uso de Solver de Excel y utilizando como motor de resolución Simplex_LP se alcanza la siguiente solución óptima (celdas amarillas) con costo mínimo (valor óptimo) de $435.

solucion-solver-transporte-

Problema de Producción y Transporte resuelto con Solver

El siguiente problema de producción y transporte fue enviado por uno de nuestros usuarios de Colombia de la ciudad de Santa Cruz de Lorica: «Una compañía que fabrica Cereal de Maíz tiene dos campos de siembra, el Campo I y el Campo II, y dos molinos, A y B. Las capacidades de suministro mensual de maíz de los Campos I y II son 125 y 245 toneladas, respectivamente. El molino A requiere por lo menos 190 toneladas de Maíz al mes y el B por lo menos 158 toneladas mensuales. Los costos de transporte en unidades monetarias por tonelada de cada Campo a cada molino son los siguientes: 2 del Campo I al molino A, 3 desde el Campo I al molino B, 4 desde el Campo II al molino A, y 5 desde el Campo II al molino B».

¿Qué cantidad de Maíz debe transportarse desde cada Campo I y II a cada molino A y B de forma que se logre minimizar el costo total de transporte? ¿Cuál es ese costo mínimo? ¿Hay algún envío que no debe realizarse para conseguir dicho costo mínimo?.

Para una mejor comprensión del problema anterior representaremos gráficamente la información anterior donde se puede apreciar los distintos oferentes (Campos) y demandantes (Molinos), además de la capacidad de producción y demanda (en toneladas mensuales) junto a los costos de transporte para cada combinación origen destino.

diagrama-problema-transport

Problema de Producción y Transporte

1. Variables de Decisión: (con i=I,II y j=A,B)

variable-decision-produccio

2. Función Objetivo: Minimizar los costos que se asumen mensualmente por el transporte de cereal desde los campos a los molinos.

funcion-objetivo-produccion

3. Restricciones: 

Capacidad de Producción de los Campos: La cantidad de toneladas que se transporte desde cada campo a cada uno de los molinos no puede superar su capacidad de producción.

restriccion-capacidad-trans

Demanda de los Molinos: Cada molino debe recibir un mínimo de toneladas mensuales de cereal desde los campos.

restriccion-demanda-transpo

No Negatividad: Las variables de decisión deben adoptar valores reales no negativos.

A continuación se detalla la implementación computacional del modelo de optimización haciendo uso de Solver de Excel:

solver-produccion-y-transpo

Notar que la celda F9 es una fórmula asociada a la función objetivo que pondera los costos unitarios de transporte por las toneladas transportas en cada combinación de origen (campos) destino (molinos). La celda E3 es la suma de C3 y D3 (análogamente E4=C4+D4) representando las restricciones de capacidad. De similar forma la celda C5 es una fórmula que considera la suma de las celdas C3 y C4 (por supuesto D5=D3+D4). Una vez generada la estructura del modelo de Programación Lineal se carga éste en la interfaz de Solver:

interfaz-solver-produccion-

La solución óptima (celdas color amarillo) consiste en transportar 125 toneladas del Campo I al Molino B y el Campo II envía 190 y 33 toneladas a los Molinos A y B, respectivamente. El valor óptimo es de 1.300 unidades monetarias.

solucion-optima-produccion-

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook o Google+ utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo.

[sociallocker]Problema de Producción y Transporte[/sociallocker]

Problema de Asignación de Capacidad de un Avión (Programación Lineal)

La industria de transporte de pasajeros enfrenta diariamente el problema de determinar cómo asignar de forma eficiente su capacidad de transporte al momento de ofrecer distintos tipos de tarifas a sus clientes para una ruta específica. Para ello se debe considerar de forma simultanea los ingresos por venta asociados a cada tipo de tarifa, una estimación de demanda de los clientes por dichas tarifas y la capacidad del medio de transporte en términos de la cantidad de asientos.

El siguiente problema considera la formulación y resolución computacional de un Problema de Asignación de capacidad de un avión para una empresa de transporte aéreo. La complejidad del problema y el nivel de detalle de la información se ha simplificado para fines académicos.

Problema de Asignación de Capacidad de un Avión

Consideremos una línea aérea que realiza la ruta Santiago (Chile) a Bogotá (Colombia) con escala en Lima (Perú). Para dicha ruta utiliza un avión con capacidad de 200 pasajeros. El departamento de ventas ha estimado los precios de mercado (en dólares) para las combinaciones de origen destino de 3 tipos de tarifas que actualmente ofrece la empresa: «Tarifa Y» (primera clase), «Tarifa B» (estándar) y «Tarifa C» (turista).

tabla-tarifas-origen-destin

Adicionalmente y según información histórica de esta ruta, la línea aérea ha estimado el número máximo de pasajes que los clientes demandarán por cada combinación de tarifa en un tramo del vuelo. Por ejemplo la demanda máxima esperada para el tramo Santiago (SCL) a Bogota (BOG) en la Tarifa B es de 35 tickets.

maximo-tickets-por-tarifa-o

Con esta información la línea aérea desea determinar cómo asignar la capacidad del avión de modo de ofrecer un determinado número de pasajes para cada tipo de tarifa en un tramo del vuelo. Para ello definiremos el siguiente modelo de Programación Lineal:

Variables de Decisión:

variables-problema-avion

Donde i=1,2,3 representa los distintos tipos de tarifa (Y, B y C, respectivamente) y j=1,2,3 las combinaciones de origen destino (SCL-LIM, LIM-BOG y SCL-BOG, respectivamente).

Parámetros:

parametros-problema-avion

Al utilizar una notación con parámetros podemos representar el modelo de optimización de forma compacta.

Función Objetivo:

funcion-objetivo-problema-a

Restricciones:

Se ofrece para cada tarifa en las combinaciones origen destino un número de tickets que no supere la demanda máxima del mercado.

restriccion-de-demanda-prob

Para cada tramo del vuelo se debe respetar la capacidad total del avión de 200 pasajeros.

restriccion-capacidad-avion

Cuando el avión despega desde Santiago con destino Lima lleva pasajeros con destino tanto a Lima como Bogotá. Por tanto independiente de la tarifa que cada uno de estos pasajeros haya pagado (por ello la sumatoria en las tarifas) no pueden superar la capacidad total del avión. Lo anterior esta garantizado por la primera restricción de capacidad.

La segunda restricción de capacidad es para el tramo desde Lima a Bogotá, donde se consideran adicionalmente los pasajeros que vienen desde Santiago.

Finalmente se definen las condiciones de no negatividad.

no-negatividad-problema-avi

Al resolver con Solver el problema anterior se alcanza la siguiente solución óptima que determina cuántos pasajes debería ofertar la línea aérea para cada combinación de tarifa y origen destino.

solucion-optima-problema-av

El valor óptimo del problema que representa los ingresos totales (en dólares) asociados a la solución óptima propuesta es de US$158.340.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.

[sociallocker]Descarga Aquí el Archivo[/sociallocker]

Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte

¿Qué complemento de Excel es mejor para resolver un modelo de optimización: SolverPremium Solver Pro o What’sBest!?. Esta consulta fue enviada por uno de nuestros seguidores de México y en este artículo trataremos de presentar algunos argumentos que permitan al lector formar una opinión al respecto. Para ello utilizaremos como caso aplicado la resolución del Problema de Localización y Transporte (Programación Entera Mixta). A continuación te presentamos los resultados que alcanzamos con Solver, Premium Solver Pro y What’sBest!.

Resolución con Solver: Se alcanza una solución factible con un costo total asociado de US$12.617.919.

solver-pem

Resolución con Premium Solver Pro: Se alcanza una solución factible con un costo total de US$12.414.340.

solver-premium-pro-pem

Resolución con What’sBest!: Se alcanza una solución factible con un costo total de US$12.414.340. Notar sin embargo que la solución óptima difiere de la alcanzada al implementar el modelo con Premium Solver Pro aun cuando tiene asociado idéntico valor de la función objetivo.

whatsbest-pem

Comentarios: Se puede apreciar que la versión básica de Solver genera una solución factible con un costo mayor a la obtenida tanto con Premium Solver Pro y What’sBest!. Lo anterior sugiere la conveniencia de implementar este tipo de problemas con una herramienta de resolución mejorada. Adicionalmente, en la medida que un modelo de optimización crece en tamaño y complejidad es recomendable poder contrastar los resultados obtenidos con distintas herramientas de resolución de modo de tener una mayor claridad si las soluciones obtenidas son sólo factibles o eventualmente óptimas. A continuación encontrarás un tutorial que hemos subido a Youtube con la resolución del problema de localización y transporte.

Formulación de un Problema de Localización y Transporte (Programación Entera Mixta)

Un modelo de Programación Entera Mixta (PEM) es un híbrido entre la Programación Lineal (PL) y la Programación Entera (PE), es decir, corresponde a una categoría particular de modelamiento matemático con características similares a la Programación Lineal pero donde un subconjunto de las variables de decisión deben adoptar valores enteros o binarios. Este característica de la Programación Entera Mixta permite representar situaciones de naturaleza real como los problemas que consideran la inclusión de costos fijos. En este contexto el siguiente artículo aborda la formulación de un Problema de Localización y Transporte el cual se describe a continuación.

Una ciudad tiene 10 zonas o áreas urbanas cada una de los cuales genera una determinada cantidad de basura (en toneladas) durante el periodo de planificación según se describe a continuación:

total-basura-generada-por-z

La basura generada debe ser transportada a centros de depósitos o vertederos entre un total de 5 candidatos posibles, cada uno de los cuales tiene un costo fijo de construcción en dólares.

costo-fijo-depositos

Adicionalmente se ha estimado el costo de transportar una tonelada de basura desde una zona a cada uno de los potenciales centros de depósito, el cual depende básicamente de la distancia a recorrer y el tipo de transporte seleccionado.

costos-transporte-zonas-a-d

Formule un modelo de Programación Entera Mixta que permita seleccionar los centros de depósito a construir y la política de transporte de basura que minimiza los costos totales.

1. Variables de Decisión: Sea i=1,…,10 las Zonas y j=1,…,5 los Depósitos:

variables-decision-localiza

2. Función Objetivo: Con el propósito de trabajar con una notación compacta podemos definir el siguiente conjunto de parámetros para el modelo de optimización:

  • Tij: Costo de transportar una tonelada de basura desde la Zona i al Depósito j
  • Fj: Costo fijo de construcción del Depósito j

La función objetivo en consecuencia se puede representar a través de la siguiente expresión:

funcion-objetivo-localizaci
3. Restricciones:

Se debe despachar (transportar) la totalidad de la basura que genera cada Zona (definimos para ello el parámetro Ai como la cantidad de basura en toneladas que genera la Zona i).

despacho-de-basura

Se debe respetar la capacidad de almacenamiento de basura para cada Depósito, utilizándolo sólo en caso que se decida su construcción. Para ello definimos el parámetro Cj como la capacidad de almacenamiento de basura en toneladas del Depósito j. Lo anteriormente expuesto explica la ponderación de la capacidad por la variable binaria para cada j.

capacidad-de-los-depositos-

Finalmente establecemos condiciones de no negatividad para Xij>=0 Para todo i,j y Yj{0,1} para todo j.

¿Quieres saber cuál es la solución de este problema?. Te recomendamos leer el siguiente artículo: Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte.