Programación Lineal (Método Gráfico)

El Método Gráfico (resolución gráfica) constituye una excelente alternativa de representación y resolución de modelos de Programación Lineal que tienen 2 variables de decisión. Para estos efectos existen herramientas computacionales que facilitan la aplicación del método gráfico como los softwares TORA, IORTutorial y Geogebra, los cuales se pueden consultar en detalle en Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORACómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorialCómo Resolver Gráficamente un modelo de Programación Lineal con Geogebra, respectivamente. En este contexto a continuación presentamos un compendio de ejercicios de Programación Lineal resueltos a través del método gráfico.

Ejercicios Resueltos del Método Gráfico en Programación Lineal

Ejercicio N°1: Una empresa vitivinícola ha adquirido recientemente un terreno de 110 hectáreas. Debido a la calidad del sol y el excelente clima de la región, se puede vender toda la producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar de cada variedad en las 110 hectáreas, dado los costos, beneficios netos y requerimientos de mano de obra según los datos que se muestran a continuación:

variedad-vinos-programacion

Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días hombre durante el horizonte de planificación. Formule y resuelva gráficamente un modelo de Programación Lineal para este problema. Detalle claramente el dominio de soluciones factibles y el procedimiento utilizado para encontrar la solución óptima y valor óptimo.

Variables de Decisión:

  • X_{1} : Hectáreas destinadas al cultivo de de Sauvignon Blanc
  • X_{2} : Hectáreas destinadas al cultivo de Chardonay

Función Objetivo:

Maximizar 50X_{1}+120X_{2}

Restricciones:

  • X_{1}+X_{2}\leq 110
  • 100X_{1}+200X_{2}\leq 10.000
  • 10X_{1}+30X_{2}\leq 1.200
  • X_{1},X_{2}\geq 0

Donde las restricciones están asociadas a la disponibilidad máxima de hectáreas para la plantación, presupuesto disponible, horas hombre en el período de planificación y no negatividad, respectivamente.

El siguiente gráfico muestra la representación del problema de la empresa vitivinícola. El área achurada corresponde al dominio de soluciones factibles, donde la solución básica factible óptima se alcanza en el vértice C, donde se encuentran activas las restricciones de presupuestos y días hombre. De esta forma resolviendo dicho sistema de ecuaciones se encuentra la coordenada de la solución óptima donde X_{1}=60X_{2}=20 (hectáreas). El valor óptimo es V(P)=50(60)+120(20)=5.400 (dólares).

metodo-grafico-vitivinicola

Ejercicio N°2: Un taller tiene tres (3) tipos de máquinas A, B y C; puede fabricar dos (2) productos 1 y 2, todos los productos tienen que ir a cada máquina y cada uno va en el mismo orden: Primero a la máquina A, luego a la B y luego a la C. La siguiente tabla muestra:

  • Las horas requeridas en cada máquina, por unidad de producto
  • Las horas totales disponibles para cada máquina, por semana
  • La ganancia por unidad vendida de cada producto

tabla-maquinas-y-requerimie

Formule y resuelva a través del método gráfico un modelo de Programación Lineal para la situación anterior que permite obtener la máxima ganancia para el taller.

Variables de Decisión:

  • X_{1} : Unidades a producir del Producto 1 semanalmente
  • X_{2} : Unidades a producir del Producto 2 semanalmente

Función Objetivo:

Maximizar X_{1}+1,5X_{2}

Restricciones:

  • 2X_{1}+2X_{2}\leq 16
  • X_{1}+2X_{2}\leq 12
  • 4X_{1}+2X_{2}\leq 28
  • X_{1},X_{2}\geq 0

Las restricciones representan la disponibilidad de horas semanales para las máquinas A, B y C, respectivamente, además de incorporar las condiciones de no negatividad.

Para la resolución gráfica de este modelo utilizaremos el software GLP cual abordamos en el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP). El área de color verde corresponde al conjunto de soluciones factibles y la curva de nivel de la función objetivo que pasa por el vértice óptimo se muestra con una línea punteada de color rojo.

glp-metodo-grafico

La solución óptima es X_{1}=4X_{2}=4 con valor óptimo V(P)=1(4)+1,5(4)=10 que representa la ganancia para el taller.

Ejercicio N°3: Una compañía elabora dos productos diferentes. Uno de ellos requiere por unidad 1/4 de hora en labores de armado, 1/8 de hora en labores de control de calidad y US$1,2 en materias primas. El otro producto requiere por unidad 1/3 de hora en labores de armado, 1/3 de hora en labores de control de calidad y US$0,9 en materias primas. Dada las actuales disponibilidades de personal en la compañía, existe a lo más un total de 90 horas para armado y 80 horas para control de calidad, cada día. El primer producto descrito tiene un valor de mercado (precio de venta) de US$9,0 por unidad y para el segundo este valor corresponde a US$8,0 por unidad. Adicionalmente se ha estimado que el límite máximo de ventas diarias para el primer producto descrito es de 200 unidades, no existiendo un límite máximo de ventas diarias para el segundo producto.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita maximizar las utilidades de la compañía.

Variables de Decisión:

  • X_{1} : Unidades a producir diariamente del Producto 1
  • X_{2} : Unidades a producir diariamente del Producto 2

Función Objetivo:

Maximizar (9-1,2)X_{1}+(8-0,9)X_{2}=7,8X_{1}+7,1X_{2}

Restricciones:

  • \frac{X_{1}}{4}+\frac{X_{2}}{3}\leq 90
  • \frac{X_{1}}{8}+\frac{X_{2}}{3}\leq 80
  • X_{1}\leq 200
  • X_{1},X_{2}\geq 0

La primera restricción representa las limitantes de horas de armado diariamente. La segunda restricción la disponibilidad de horas para labores de control de calidad (también diariamente). La tercera restricción establece una cota superior para la producción y ventas diarias del Producto 1. Adicionalmente se incluyen las condiciones de no negatividad para las variables de decisión.

El dominio de soluciones factibles tiene 5 vértices que corresponden a los candidatos a óptimos del problema. En particular el vértice óptimo es D de modo que la solución óptima es X_{1}=200X_{2}=120 con valor óptimo V(P)=7,8(200)+7,1(120)=2.412 que corresponde a la utilidad máxima para la empresa.

metodo-grafico-produccion

Importante: A la fecha de esta publicación disponemos de más de 70 artículos relativos a la Programación Lineal los cuales recomendamos revisar, donde se aborda la resolución gráfica de este tipo de modelos como también la resolución a través de algoritmos como el Método Simplex y la implementación computacional con herramientas como Solver, What’sBest! y OpenSolver, entre otras.

En el siguiente tutorial de nuestro canal de Youtube se explica un ejemplo adicional con todos los elementos del método gráfico en Programación Lineal:

Problema de Tamaño de Lote No Capacitado (Formulación y Resolución en Solver)

El Problema de Tamaño de Lote No Capacitado o ULS (por sus siglas en inglés, Uncapacitated Lot-Sizing), consiste en decidir sobre un Plan de Producción para un horizonte de T periodos para un solo producto. El objetivo consiste en minimizar la sumatoria de los costos de producción, almacenamiento de productos en inventario y setup (costos de emisión), asumiendo que las demandas son conocidas en cada uno de los T periodos y éstas deben ser satisfechas de forma íntegra.

Una formulación típica del Problema de Tamaño de Lote No Capacitado considera los siguientes parámetros y variables de decisión.

Formulación Tradicional Problema de Tamaño de Lote No Capacitado

Variables de Decisión:

  • x_{t} = cantidad producida en el periodo t.
  • s_{t} = inventario al final del periodo t.
  • y_{t} = 1 si la producción ocurre en el periodo t, 0 si no.

Parámetros:

  • f_{t} = costo fijo de producción en el periodo t.
  • p_{t} = costo unitario de producción en el periodo t.
  • h_{t} = costo unitario de almacenamiento en el periodo t.
  • d_{t} = demanda en el periodo t.

La definición anterior da origen al siguiente problema de Programación Entera Mixta (PEM).

formulación tradicional tamaño de lote no capacitado

La función objetivo consiste en minimizar la suma de los costos de producción, costos de almacenamiento de productos en inventario y costos de emisión de pedidos, para todo el horizonte de planificación (T períodos).

Por otra parte las restricciones del problema quedan definidas por:

Balance de Inventario s_{t}=s_{t-1}+x_{t}-d_{t}: El inventario al final de un período t es igual al inventario al final del período anterior (t-1) más lo producido en el período t y menos lo demandado en el período t.

Capacidad de Producción x_{t}\leq M\cdot y_{t}: Si bien hemos definido el problema como no capacitado, esta restricción permite vincular la decisión de producción en un período con la cantidad (volumen) de dicha producción. De esta forma se evita situaciones anómalas como que en un período cualquiera se produzca y al mismo tiempo el y_{t} respectivo sea cero.

Además, asumiremos que la constante M es lo suficientemente grande (por ejemplo, la suma de las demandas para el horizonte de planificación). En términos prácticos esto hace que el problema no tenga limitantes de capacidad (es decir, es no capacitado) y que, en un extremo, podría producir en el primer período todo lo requerido durante el horizonte de planificación para luego ir satisfaciendo dichos requerimientos con los remanentes de inventario.

Inventario Inicial s_{0}=0: Se asume que no se dispone de inventario al inicio del horizonte de planificación.

Finalmente se establecen condiciones de no negatividad y binarios a las variables según corresponda.

Alternativamente se propone otra formulación como alternativa al Problema de Tamaño de Lote No Capacitado.

Formulación Dinámica Problema de Tamaño de Lote No Capacitado

Variables de Decisión:

  • w_{ts} = cantidad producida en el periodo t para satisfacer la demanda en el periodo s.
  • s_{ts} = inventario al final del periodo t destinado para el periodo s.
  • y_{t} = 1 si la producción ocurre en el periodo t, 0 si no.

Al conservar la definición de parámetros definida para la formulación anterior, se propone el siguiente modelo de Programación Entera:

formulación dinámica tamaño de lote no capacitado

De modo de corroborar la equivalencia de las formulaciones anteriores se propone una instancia sencilla que corresponde a 5 períodos de planificación (T=5) y donde los valores de los parámetros se resumen en la siguiente tabla. Por ejemplo, p_{1}=3 representa el costo de producción unitario en el período 1.

parámetros uls

La solución óptima alcanzada con la Formulación Tradicional del Problema de Tamaño de Lote No Capacitado ULS se observa en las celdas de color amarillo en la imagen a continuación. Se producen 32, 125 y 20 unidades en los períodos 1, 2 y 5, respectivamente, almacenando sólo productos en inventario al final del período 2 y 3 (84 y 36 unidades, respectivamente). El valor óptimo (costo total) asciende a $781.

solución óptima formulación tradicional uls

De forma análoga la solución óptima obtenida con la Formulación Dinámica del Problema de Tamaño de Lote No Capacitado ULS se observa en las celdas de color amarillo en la tabla a continuación.

Notar que w_{11}=32, es decir, en el primer período se produce sólo lo necesario para satisfacer los requerimientos de dicho período. Adicionalmente w_{22}=41, w_{23}=48 y w_{24}=36, es decir, en el período 2 se producen en total 125 unidades (41+48+36), para satisfacer la demanda de los períodos 2, 3 y 4. Por último en el período 5 se produce simplemente 20 unidades (w_{55}=20) para cumplir lo requerido.

Naturalmente dado lo descrito, la solución alcanzada en la Formulación Dinámica del ULS es equivalente a la obtenida en la Formulación Tradicional del ULS.

solución óptima formulación dinámica uls

Se puede consultar otras variantes de Problemas de Planificación de la Producción en nuestro sitio donde se detalla diversas formulaciones e instancias de problemas de esta naturaleza, donde destaca la contribución de la Investigación de Operaciones como herramienta de apoyo para la toma de decisiones.

[sociallocker]Descarga Aquí el Problema de Tamaño de Lote No Capacitado (ULS)[/sociallocker]




Ejemplo de Relajación Lagrangeana en Programación Entera

El método de Relajación Lagrangeana (o Relajación Lagrangiana) consiste básicamente en un Método de Descomposición cuya idea se basa en descomponer un problema original restringido, en principio complejo de resolver, de modo de reemplazarlo por otro problema que permita simplificar la resolución. Esto se logra incorporando aquellas restricciones que se consideran difíciles (las que hacen compleja la resolución directa del problema) a la función objetivo, donde cada una de éstas tendrá asociada un Multiplicador de Lagrange \lambda que permitirá (iterativamente) penalizar el incumplimiento de las mismas al ser establecidos distintos valores para los multiplicadores. De esta forma se espera que las restantes restricciones (las que no se incorporan mediante penalizaciones en la función objetivo) permitan verificar un problema cuya resolución sea fácil (o al menos más sencilla que el problema en su estructura original).

El problema asociado a encontrar los valores de \lambda que permitan minimizar la función LR(\lambda) (que en sí es un problema de maximización) se conoce como el Problema Dual Lagrangeano. En general puede resultar un problema tedioso de resolver, no obstante, a continuación se enumeran una serie de pasos que permiten una aproximación a la implementación del método de Relajación Lagrangeana.

Supongamos que el problema original es de Maximización y que la o las restricciones relajadas son inecuaciones del tipo \leqslant:

  1. Comenzar con cada \lambda igual a cero. Definir inicialmente (y de forma arbitraria) un Paso de magnitud k.
  2. Resolver LR(\lambda) de modo de alcanzar la solución óptima en términos de x.
  3. Para cada restricción violada por x, incrementar el correspondiente \lambda por k.
  4. Si han transcurrido m iteraciones desde que se alcanzo la última relajación para el problema dual lagrangeano, disminuir k a la mitad.
  5. Ir al Paso 2.

Para ilustrar el procedimiento anterior consideremos un Problema de la Mochila como el que se describe a continuación:

ejemplo relajación lagrangeana

Luego de resolver el problema de Programación Entera propuesto haciendo uso de Solver de Excel se alcanza la Solución Óptima: x_{1}=0, x_{2}=0, x_{3}=1, x_{4}=1 con Valor Óptimo: V(PE)=13.

Relajaremos las Restricciones 1 y 2 incorporando éstas a la función objetivo y dejando exclusivamente las condiciones de binarios para las variables de decisión. Esto da origen a nuestro problema de Relajación Lagrangeana LR(\lambda):

relajación lagrangeana programación entera

Consideraremos inicialmente \lambda_{1}=0 y \lambda_{2}=0. La resolución de dicha instancia es trivial obteniéndose como Solución Óptima: x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1 y Valor Óptimo: LR(\lambda)=22. Notar que la solución alcanzada no satisface la Restricción 1 (sin embargo, se satisface la Restricción 2).

Penalizaremos la Restricción 1 al considerar \lambda_{1}=0,5 (penalización arbitrariamente definida como punto de partida) y manteniendo \lambda_{2}=0 (dado que la Restricción 2 se satisface). La Solución Óptima es x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1 con Valor Óptimo de LR(\lambda)=20. En consecuencia, la penalización establecida resulto ser insuficiente para que se evitara la violación (incumplimiento) de la Restricción 1.

Sea \lambda_{1}=1 (aumentamos nuevamente en 0,5 la penalización de la Restricción 1) y \lambda_{2}=0. La Solución Óptima se mantiene: x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1 con Valor ÓptimoLR(\lambda)=18.

Sea \lambda_{1}=1,5 y \lambda_{2}=0. La Solución Óptima se mantiene: x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1 con Valor Óptimo: LR(\lambda)=16. Se sigue violando la Restricción 1.

Sea \lambda_{1}=2 y \lambda_{2}=0. La Solución Óptima ahora es: x_{1}=0, x_{2}=1, x_{3}=0, x_{4}=0 con Valor ÓptimoLR(\lambda )=15. Ahora se satisfacen las Restricciones 1 y 2, teniendo éstas holguras de 5 y 1, respectivamente. Luego si se decide disminuir la penalización de la Restricción 1 a \lambda_{1}=1,5 se vuelve al mismo punto de la iteración anterior. En consecuencia se disminuye la magnitud del paso (penalización) a 0,25 de modo que \lambda_{1}=1,75 y \lambda_{2}=0. La Solución Óptima es: x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=0 con Valor Óptimo: LR(\lambda)=15.

No obstante, la Restricción 2 no se satisface para esta nueva solución y de esta forma se establecen nuevas penalizaciones: \lambda_{1}=1,75 y \lambda_{2}=0,25 y  que dan origen a la Solución Óptima: x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1 con Valor Óptimo: LR(\lambda)=15.

El procedimiento continua de esta forma disminuyendo la magnitud del paso (penalización) cuando resulta necesario. Notar que de esta forma las respectivas penalizaciones pueden aumentar o disminuir al cabo de una iteración. El detalle de las iteraciones realizadas se muestra a continuación:

iteraciones relajación lagrangeana

Para cada iteración k se muestra la penalización aplicada para la Restricción 1 y 2 respectivamente, el criterio para la actualización del Paso, el valor de la función objetivo de la Relajación Lagrangeana LR(\lambda ), la Solución Óptima alcanzada para el problema (destacado con color amarillo), el valor que representa dicha solución óptima al ser evaluada en la función objetivo original V(PE), la holgura de la Restricción 1 (2) (con color rojo se destaca cuando se viola la restricción en una determinada magnitud) y si la solución óptima alcanzada en la iteración k-ésima es factible en el problema original PE).

convergencia dual lagrangeano

Según se señala en un tutorial  por Michael A. Trick (donde se ha tomado este ejemplo y se ha extendido a un número mayor de iteraciones con ciertas variaciones en la aplicación de las mismas) las penalizaciones “óptimas” (luego de seguir iterando) corresponderán aproximadamente a \lambda_{1}=1,83 y \lambda_{2}=0,33, alcanzando LR(\lambda )=14,67 que constituye una cota superior del valor óptimo del problema original. La Solución Óptima asociada a este escenario es x_{1}=0, x_{2}=1, x_{3}=1, x_{4}=0 que es factible en el problema original y reporta un valor en la función objetivo de 11. Notar que la Solución Óptima del PE) es x_{1}=0, x_{2}=0, x_{3}=1, x_{4}=1 con Valor Óptimo de 13.




Informes de Sensibilidad en Premium Solver Pro (Interpretación)

Las ventajas que ofrece la utilización de una herramienta de optimización profesional como Premium Solver Pro son múltiples y son rápidamente identificadas por quienes comienzan a formarse en el apasionante mundo de la Investigación de Operaciones. Respecto a este tema en particular he tenido el honor de publicar un artículo (en inglés) en el Blog del prestigioso sitio de FrontlineSolvers (desarrolladores del complemento Solver para Excel) llamado How to Correctly Interpret Sensitivity Reports in Premium Solver. En este contexto a continuación presentamos la traducción del mismo a español teniendo en cuenta que parte mayoritaria de nuestros lectores son de países de habla hispana.

En mi experiencia como profesor de Investigación de Operaciones he constatado de forma directa los beneficios de implementar computacionalmente modelos de optimización de distinta complejidad en un ambiente de aprendizaje intuitivo y al mismo tiempo confiable. En este sentido los alumnos adquieren rápidamente las destrezas suficientes para resolver problemas de optimización de distinto tamaño en una plataforma conocida como resulta ser Excel.

Cabe destacar adicionalmente que Premium Solver Pro no solo nos permite resolver modelos de optimización, también ofrece la oportunidad de generar Informes de Sensibilidad una vez alcanzada la solución óptima y valor óptimo de un modelo base. En este contexto el análisis de sensibilidad o postoptimal buscar analizar el impacto que tiene en los resultados de un modelo la modificación de uno o varios parámetros del mismo.

Un Informe de Sensibilidad de Premium Solver Pro se divide en 3 partes:

  1. Función objetivo
  2. Celdas variables
  3. Restricciones

A continuación presentamos un sencillo modelo de Programación Lineal el cual será implementado computacionalmente, obteniendo el Informe de Sensibilidad que analizaremos en detalle con el objetivo de interpretarlo de forma correcta.

modelo pl premium solver

Luego de utilizar Premium Solver Pro para resolver el modelo anterior se alcanza la solución óptima x_{1}=3 y x_{2}=6, con valor óptimo V(PL)=342.

solución premium solver

A continuación podemos obtener el Informe de Sensibilidad accediendo al módulo Reports > Optimization > Sensitivity, tal cual se muestra a continuación:

sensitivity report premium solver

Una vez que solicitemos el Informe de Sensibilidad se generará una nueva hoja en el archivo Excel que estemos trabajando con el reporte de los resultados. Para el ejemplo propuesto en este artículo los resultados son los siguientes:

análisis de sensibilidad premium solver

A continuación detallaremos cómo interpretar cada una de las 3 partes que nos ofrece el Informe de Sensibilidad de Solver.

  1. Objective Cell (Max): Se observa que el valor óptimo, es decir, el valor de la función objetivo del problema de maximización al ser evaluada en la solución óptima alcanzada es de 342. Dicho valor se obtiene de: V(PL)=(34)*3+(40)*6=342.

  1. Decision Variable Cells: En esta sección se puede identificar la solución óptima (valores bajo la columna etiquetada como Final Value), los coeficientes o parámetros en la función objetivo (valores en la columna Objective Coefficient), el aumento permisible y la disminución permisible para cada uno de los coeficientes de forma individual en la función objetivo que permite garantizar que se conserva la actual solución óptima.

Por ejemplo, consideremos el coeficiente c_{1}=34 asociado a la variable de decisión x_{1} en la función objetivo de maximización. La disminución permisible para dicho parámetro es de 7,333 aprox (equivalente a 22/3) unidades y el aumento permisible de 6, de modo que si c_{1}\epsilon [34-\frac{22}{3},34+6] ==>c_{1}\epsilon [26,\bar{6},40] se conserva la solución óptima original (notar que se asume para este análisis que el resto de los parámetros del modelo mantienen sus valores iniciales). De forma análoga recomendamos al lector verificar que el intervalo de variación para c_{2} que conserva la actual solución óptima es c_{2}\epsilon [34,51].

  1. Constraints: Un primer aspecto a observar es si una restricción se encuentra activa al ser evaluada en la solución óptima. Una restricción activa es aquella que se satisface en igualdad. Por ejemplo, se puede ver que para las Restricciones 1 y 2 el valor bajo la columna Final Value es idéntico al lado derecho de la restricción o Constraint R.H. Side. Dicho de otra forma, dado que las Restricciones 1 y 2 son activas en el óptimo, la solución óptima del problema propuesto se puede obtener mediante la resolución de un sistema de ecuaciones con 1 y 2 activas. Notar que adicionalmente la Restricción 3 si bien se satisface no se cumple en igualdad.

También resulta de interés interpretar lo que se conoce como Precio Sombra de una restricción.

El Precio Sombra corresponde a la tasa de cambio del valor óptimo de un modelo de Programación Lineal ante la modificación marginal del lado derecho de una restricción. Se entiende por una modificación marginal aquella que permite conservar la base óptima del problema (idénticas variables básicas originales en el caso del Método Simplex) o la geometría del problema (mantener las restricciones activas originales).

Dada la definición anterior es natural comprender que el Precio Sombra de la Restricción 3 sea cero. Si el lado derecho representa la disponibilidad de un recursos (por ejemplo, horas hombre, unidades de materia prima, etc), en la solución óptima original se utiliza 12 de las 16 unidades disponibles (que es consistente con una disminución permisible de 4 unidades y un aumento permisible de 1E+30 o infinito) para el recurso. Adicionalmente como la Restricción 3 no es activa, cualquier variación del lado derecho de dicha restricción en el intervalo b_{3}\epsilon [12,+\infty[  no solo conserva el valor óptimo, sino también la solución óptima original.

El caso de las Restricciones 1 y 2 es diferente. Por ejemplo, si aumenta en una unidad el lado derecho de la Restricción 1, pasando de 48 a 49 unidades (notar que el aumento permisible para dicho parámetro  es de 6 unidades) el valor óptimo aumentará de forma proporcional al Precio Sombra de dicha restricción: V(\bar{P})=V(P)+\Delta b_{1}*\pi _{1}=342+(49-48)*3=345. De forma análoga si, por ejemplo, en vez de aumentar el lado derecho de la Restricción 1, disminuye de 48 a 45 (disminución de 3 unidades que está dentro del rango permitido), el nuevo valor óptimo será: V(\bar{P})=V(P)+\Delta b_{1}*\pi _{1}=342+(45-48)*3=333. Recomendamos al lector verificar directamente estos resultados luego de reoptimizar ante los cambios propuestos.

En síntesis queda en evidencia que la utilidad de Premium Solver Pro va más allá de implementar y resolver computacionalmente un modelo de optimización. En este sentido interpretar de forma correcta el análisis de sensibilidad que nos ofrece genera un ahorro de tiempo frente al escenario de reoptimizar que muchas veces es evitable, además de que nos permitir comprender de mejor forma la estructura de una solución óptima, que no sólo se limita a identificar cuál es el valor que alcanzan las variables de decisión en la resolución computacional.




Modelo de Localización y Transporte con Preferencias

Los modelos de optimización que integran decisiones de localización y transporte han sido materia de análisis detallado en nuestro sitio como se aborda en los artículos Optimización de una Red Logística de Transporte y Localización de Centros de Distribución y el Problema de Transbordo en una Red Logística de Transporte Multiperíodo, entre otros. En esta ocasión incorporaremos un concepto adicional a la problemática anterior a través de la incorporación de las preferencias de los clientes por ser abastecidos por determinados centros de oferta. A este problema lo llamaremos Modelo de Localización y Transporte con Preferencias de Clientes y a continuación describiremos un caso particular que permita visualizar una alternativa de formulación sencilla con su correspondiente implementación computacional.

Asumamos que cada cliente (demandante) ha manifestado su preferencia por ser abastecido por determinados oferentes (potenciales). En este contexto cada cliente elegirá siempre su mejor (menor) prioridad de las alternativas ofertas disponibles, es decir, de aquellas que se decidan instalar (localizar).

Consideremos los siguientes parámetros para el modelo:

Sea C_{ij} el costo de abastecer al cliente j (para el total de su demanda) desde el centro de oferta i. Como se puede apreciar asumiremos que cada cliente debe ser abastecido por solo un oferente. Adicionalmente y para efectos de ilustración consideraremos 4 oferentes (potenciales) y 6 clientes.

costo transporte oferentes a demandantes

Sea K_{i} el costo de instalar el centro de oferta i. Por ejemplo, habilitar (localizar) el oferente 1 tiene un costo fijo de 3.500 unidades monetarias.

costo instalación oferente

Sea p_{ij} la preferencia que manifiesta el cliente j por ser abastecido por el oferente i. Asumiremos que un menor valor representa una mayor preferencia. Por ejemplo, el cliente 1 prefiere ser abastecido por los oferentes 4,1,3,2, respectivamente. En este sentido si se llegará, por ejemplo, solo a instalar el oferente 1 y 3, el cliente 1 debe ser abastecido del oferente 1 dado que de las 2 alternativas este oferente representa una mayor preferencia.

matriz de preferencias

Dada las definiciones anteriores, el Modelo de Localización y Transporte con Preferencias de Clientes es el siguiente:

localización y transporte con preferencias

Donde x_{i} es una variable binaria que adopta un valor 1 si se instala el centro (oferente) i (cero en caso contrario. Por otra parte y_{ij} es una variable binaria que indica si el cliente j se abastece (exclusivamente) desde el oferente i (cero en caso contrario). Luego, la función objetivo representa la minimización de los costos de instalación de los oferentes y el transporte que se origina entre éstos y los clientes.

En cuanto a las restricciones tenemos:

  • (1) Determina que cada cliente sea abastecido desde un único centro de oferta.
  • (2) Los clientes pueden optar a ser abastecidos desde aquellos oferentes que hayan sido seleccionados.
  • (3) La preferencia de cada cliente corresponderá al promedio ponderado de columna correspondiente en la matriz de preferencias (asociada a dicho cliente) por la decisión de abastecimiento desde un oferente dado.
  • (4) Se impone a través de la preferencia calculada en (3) que cada cliente sea atendido por aquel oferente que le reporta la mayor satisfacción (menor puntuación en el ejemplo según lo descrito previamente).
  • (5) Las variables de decisión son binarias.

Luego de implementar en Solver el modelo de Programación Entera anterior se alcanzan los siguientes resultados:

solución óptima localización con preferencias

Se observa que se instalan los centros de oferta 1, 2 y 4, que representa un costo de localización (total) de $9.000. En cuanto a las decisiones de distribución, el oferente 1 abastece al cliente 4; el oferente 2 abastece a los clientes 2 y 5 y finalmente el oferente 4 abastece a los clientes 1, 3 y 6. El costo total de transporte es de $12.062, de modo que el costo total es $21.062 (valor óptimo). Notar que cada cliente recibe los pedidos de su mejor alternativa posible (marcado con color verde). A continuación se encuentra disponible el archivo Excel con la implementación computacional del Modelo de Localización y Transporte con Preferencias para ser descargado.

[sociallocker]Localización y Transporte con Preferencias[/sociallocker]