En la aplicación del Método Simplex, un problema no acotado se detecta cuando en una iteración cualquiera existe unavariable no básica con costo reducido negativo y todos los elementos en la columna de dicha variable son negativos o cero. Es decir, no se puede seleccionar un pivote para determinar la variable que debe dejar la base.
Si resolvemos gráficamente dicho modelo nos podemos percatar que éste es no acotado. Notar que el dominio de soluciones factibles (área sombreada o achurada) es no acotado dado que crece indefinidamente en la dirección de la variable X2.
Las curvas de nivel de la función objetivo crecen a su mayor tasa en la dirección del vector gradiente lo que indica que se podría desplazar indefinidamente en esa dirección y siempre interceptar el dominio de soluciones factibles.
¿Cómo podemos detectar esta situación (Problema No Acotado? utilizando el Método Simplex?
Para ello llevamos el modelo a su forma estándar, agregando X3 y X4 como variables de holgura de la restricción 1 y 2, respectivamente. Lo anterior define la siguiente tabla inicial del método:
Notar que X2 es la variable no básica con el costo reducido más negativo y siguiendo ese criterio debería ser aquella que ingresamos a la base. Sin embargo, no es factible hacer el criterio de factibilidad o mínimo cuociente debido a que los elementos en la columna de X2 son negativos o cero. En esta instancia ya se puede afirmar que el problema es no acotado.
Observación: Se puede verificar que si seleccionamos X1 como la variable que entra a la base y se aplica una iteración del Método Simplex se llegara a una conclusión similar a la presentada anteriormente.
En la aplicación del Plan de Requerimientos de Materiales (MRP) es necesario determinar una política de lotificación que establezca cuánto y cuándo pedir las partes y piezas necesarias para poder cumplir con una meta de producción del producto final o categoría superior. El objetivo es cumplir con dichos requerimientos y a la vez procurar los menores costos asociados a la gestión del inventario.
Una de las políticas de lotificación es la de Cantidad Económica de Pedido (EOQ) utilizada en la Gestión de Inventarios, que busca minimizar los Costos Totales del Inventario. Para ello se deben verificar los supuestos de este modelo, principalmente que la demanda (en nuestro caso necesidades netas) sea constante. No obstante, como es difícil encontrar una situación práctica donde los requerimientos sean fijos durante el tiempo, se flexibiliza este supuesto y se usa un promedio para poder estimar el valor de la demanda anual.
Ejemplo Lotificación EOQ en el Plan de Requerimientos de Materiales
Consideremos las necesidades netas para el Producto X en un período de 10 semanas. Adicionalmente asumiremos que el Costo de Emisión(S), es decir, el costo asociado a realizar cada pedido (independiente de su tamaño) es de $50 y que el Costo de Almacenar una unidad del Producto X en inventario durante un año es igual a $4(H).
Un primer paso para aplicar la política de lotificación de la Cantidad Económica de Pedido (EOQ) es estimar un valor de la demanda anual para el producto. En este sentido la suma de las necesidades netas para las 10 semanas es igual a 500 unidades, lo que otorga un promedio de 50 unidades por semana. Si consideramos que un año tiene 52 semanas, entonces la demanda promedio anual es de 2.600 unidades.
Con esta información el tamaño de pedido que minimiza los costos de la gestión del inventario del Producto X es:
Luego desarrollamos la planificación de los pedidos en el tiempo para el período de 10 semanas, asumiendo que el tiempo de espera (lead time) es cero, es decir, tan pronto se emite un pedido se asume que este se recibe.
El primer pedido se realiza en la semana 1 por 255 unidades. Como la necesidad neta es de 40 unidades, nos quedan 215 unidades en inventario. El costo emisión es de $50 para la semana 1 (se realizó un pedido) y el costo de almacenamiento es de $16,54 (costo de almacenamiento semanal: $4/52*215 unidades).
Se puede observar que el inventario disponible luego del primer pedido es suficiente para satisfacer en forma íntegra la demanda hasta la semana 5.
En la semana 6 realizamos un segundo pedido por 255 unidades. Notar que en la semana 10 queda un inventario de 10 unidades a diferencia de lo que sucedería si aplicamos la política Lote a Lote.
Es importante destacar que al utilizar la política de lotificación de la Cantidad Económica de Pedido (EOQ)no se garantiza necesariamente los menores costos de la gestión del inventario. En nuestro ejemplo el costo total es de $190,68 (si utilizáramos Lote a Lote el costo sería $500).
El Plan de Requerimientos de Materiales o simplemente MRP por sus siglas en inglés (Material Requirements Planning) es una metodología que permite administrar el inventario y planificar pedidos de partes y piezas con demanda dependiente.
En la actualidad el MRP resulta ser un módulo indispensable para la gestión de los recursos de las empresas de manufactura y son parte fundamental de las prestaciones de los más prestigiosos softwares ERP (Enterprise Resource Planning) disponibles en el mercado (destacándose entre ellos SAP).
En el siguiente artículo encontrarás a través de un ejemplo sencillo, explicado con detalle, cómo realizar un Plan de Requerimientos de Materiales (MRP) y cuáles son los elementos necesarios para su construcción. Para una correcta comprensión introduciremos algunos conceptos que te recomendamos leer detenidamente.
En primer lugar se afirma que un producto tiene demanda dependiente en la medida que su demanda se puede derivar de un producto de categoría superior.
Ejemplo N°1: las plantillas, cuero, cordones, etc, son partes de demanda dependiente, basadas en la demanda de zapatos (demanda independiente).
Ejemplo N°2: si una empresa vende 1.000 triciclos, entonces se van a necesitar 1.000 ruedas delanteras y 2.000 ruedas traseras (más pequeñas). Este tipo de demanda interna no necesita un pronóstico, sino sólo una tabulación (demanda dependiente). Por otra parte la cantidad de triciclos que la empresa podría vender es la demanda independiente.
En este contexto, una empresa que vende un producto final (con demanda independiente) está interesada en qué, cuánto y cuándo ordenar de las distintas partes y piezas que permiten la producción de dicho producto final. Esta Planeación de Requerimientos de Materiales es crítica dado que permitirá alcanzar las metas de producción en tiempo y cantidad de lo planificado previamente en un plan maestro de producción.
Para llevar a cabo un Plan de Requerimientos de Materiales (MRP) se necesitan 3 elementos:
Estructura del Producto, Lista de Materiales o Bill of Materials (BOM)
Registro del Inventario (IRF)
El Plan Maestro de la Producción (PMP) establece las necesidades en cantidad y tiempo del producto final o con demanda independiente.
Por otra parte la estructura del producto o Bill of Materials (BOM) detalla cuántas partes y piezas se necesitan para obtener una unidad de producto final y cómo dicho producto se compone. Generalmente se utiliza una representación gráfica para el BOM como la de la siguiente imagen:
Por ejemplo, para cada unidad de X (producto final con demanda independiente) se necesitan 2 unidades de la pieza A (producto con demanda dependiente). Análogamente, por cada unidad de la pieza A se necesitan 3 unidades de la pieza C.
Así también, un típico juego de Lego viene con un instructivo que detalla la cantidad de piezas componentes del producto (juego) final y el orden en el cual se deben ensamblar. De este modo si hemos armado un juego de Lego ya tenemos una idea intuitiva de lo que consiste un MRP.
Finalmente necesitamos el Registro del Inventario (Inventory Record File o IRF) (tanto para productos con demanda dependiente e independiente) que contiene la información del inventario disponible y el tiempo de espera (o lead time) asociado a cada producto. Un ejemplo del IRF es el siguiente:
Arbitrariamente vamos a considerar que necesitamos 100 unidades el producto X en la semana 10. Toda esta información nos permitirá desarrollar el Plan de Requerimientos de Materiales, el cual se resume a continuación:
Ejemplo del Plan de Requerimientos de Materiales
La forma usual de poder completar la información del Plan de Requerimientos de Materiales (MRP) es desde el producto de categoría superior, en este caso, el Producto X. Para la semana 10 existe una necesidad bruta de este producto por 100 unidades, sin embargo, el inventario disponible (40 unidades) finalmente determina que sólo se necesiten 60 unidades adicionales. Como el tiempo de espera (lead time) para el Producto X es de 2 semanas, el pedido se debe realizar en la semana 8.
Posteriormente, por cada unidad del Producto X necesitamos 2 unidades del Producto A. Esto determina la necesidad bruta del Producto A en 120 unidades en la semana 8. Luego, como se dispone de un inventario de 60 unidades del producto A, la necesidad neta es sólo de 60 unidades, las cuales se piden con 3 semanas de antelación dado el tiempo de espera. Siguiendo el mismo procedimiento se determinan las necesidades netas del Producto B.
Es importante destacar el caso del Producto C, el cual depende tanto de A como B. Por cada unidad de A se necesitan 3 unidades de C (en este caso 180 unidades) y por cada unidad de B se necesitan 2 unidades de C (en este caso 80 unidades).
El procedimiento utilizado para desarrollar el Plan de Requerimientos de Materiales (MRP) es la política de lotificación Lote a Lote, es decir, cada vez que se necesitan unidades se piden éstas en forma exacta. Esta alternativa, sin embargo, NO garantiza los menores costos en la planificación, especialmente cuando los costos de emisión (generar un pedido) son relativamente superiores a los costos de almacenamiento (inventario).
Te recomendamos consultar al final de esta publicación los “Artículos Relacionados” donde podrás encontrar otros ejemplos aplicados de MRP utilizando distintas alternativas de políticas de lotificación (Costo Total Mínimo, Costo Unitario Mínimo, EOQ).
Las características de Solver han evolucionado en las distintas versiones de Office y en esta oportunidad mostraremos cómo activar este complemento en la versión del año 2003 y 2007. Para ello se deben seguir los siguientes pasos:
Paso 1: Abrir el programa Excel y en el menú de Herramientas seleccionar Complementos.
Paso 2: Seleccionar la opción Solver y luego Aceptar.
Paso 3: Puede ser necesario aprobar la ejecución del complemento como muestra la imagen a continuación. En este caso se debe seleccionar Sí
Paso 4: Una vez completada la activación de Solver el complemento estará disponible en el menú de Herramientas de Excel.
Una alternativa a Solver es el complemento de Excel OpenSolver el cual se puede descargar gratuitamente desde www.opensolver.org. En el artículo Cómo resolver un modelo de Programación Lineal con OpenSolver mostramos su utilización en un problema sencillo. Adicionalmente What’sBest! resulta ser otra excelente alternativa para Solver y desarrollado para Excel. En el siguiente tutorial detallamos cómo descargar e instalar What’sBest!.
Uno de los teoremas principales en la Teoría de Dualidad en Programación Lineal es el Teorema de Holguras Complementarias.
El Teorema de Holguras Complementarias nos permite encontrar la solución óptima del Problema Dual cuando conocemos la solución óptima del Problema Primal (y viceversa) a través de la resolución de un sistema de ecuaciones conformado por las variables de decisión (primales y duales) y las restricciones (del modelo primal y dual).
La importancia de este teorema radica en que facilita la resolución de los modelos de optimización lineal, permitiendo a quién los resuelve buscar el modelo más sencillo para abordar (desde el punto de vista algorítmico) dado que de cualquier forma podrá obtener los resultados del modelo equivalente asociado (sea éste el modelo primal o dual).
Ejemplo Teorema de Holguras Complementarias
Consideremos el siguiente modelo de Programación Lineal (en adelante Primal) en 2 variables cuya solución óptima obtenida por el Método Gráfico es X=14/5 e Y=8/5 con valor óptimo V(P)=20,8.
Luego, el Teorema de Holguras Complementarias plantea las siguientes relaciones:
Como sabemos X=14/5 e Y=8/5 (Solución Básica Factible Óptima del modelo primal). Si reemplazamos estos valores de X e Y en la tercera y cuarta ecuación generamos un sistema de ecuaciones de 2×2 en términos de A y B cuya solución corresponde a A=6/5 y B=2/5 (solución óptima del modelo dual). Si posteriormente evaluamos en la función objetivo del problema dual dicha solución obtenemos: V(D)=12(6/5)+16(2/5)=20,8 que es similar al valor óptimo del problema primal (Teorema de Dualidad Fuerte).
Siendo A=6/5 y B=2/5 una solución factible para el problema dual, ésta es la solución optima de dicho problema.
Observaciones: Notar que la restricción 1 y 2 del problema primal son activas en el óptimo, es decir, se cumplen en igualdad. Esto permite descartar que A y B (variables duales asociadas a dichas restricciones) son iguales a cero. Si por ejemplo, la restricción 1 del modelo primal no fuese activa en el óptimo se podría afirmar que A es igual a cero en el dual.
Ejercicio Teorema de Holguras Complementarias en Programación Lineal
Una empresa que fabrica muebles desea estudiar la producción de varios tipos de mesas de madera. Las mesas a fabricar son mesas de comedor, de centro y de arrimo, las que deben ser procesadas por 3 tipos de máquinas, una cortadora, una ensambladora y una pulidora. Se dispone de a lo mas de 80 horas de trabajo en cada una de las máquinas y 2.000 unidades de madera. La siguiente tabla muestra los tiempos y la madera necesaria para la fabricación de cada mesa, así como la utilidad que reporta cada una de ellas.
Dadas las siguientes soluciones del Problema PrimalS1=(900,100,0), S2=(176,496,656), S3=(200,400,550) y S4=(800,0,400). Determine mediante el Teorema de Holguras Complementarias si alguna de estas soluciones es óptima para el Problema Primal planteado.
MIN W = 4.800 Y1 + 4.800 Y2 + 4.800 Y3 + 2.000 Y4
S.A.
5 Y1 + 2 Y2 + 3 Y3 + 2 Y4 >= 3
3 Y1 + 5 Y2 + 2 Y3 + 2 Y4 >= 3
2 Y1 + 3 Y2 + 5 Y3 + 1 Y4 >= 2
Y1>= 0, Y2>=0, Y3>=0, Y4>=0
A continuación verificamos la factibilidad de las soluciones propuestas para el Problema Primal:
S1=(900,100,0), V(S1)=3.000 Satisface todas las restricciones S2=(176,496,656) V(S2)=3.328 Satisface todas las restricciones S3=(200,400,550) V(S3)=2.900 Satisface todas las restricciones S4=(800,0,400) V(S4)=3.200 Satisface todas las restricciones
Todas las soluciones satisfacen todas las restricciones por lo que son todas soluciones factibles. De ellas se escoge S2 ya que entrega la mayor utilidad para verificar si es solución óptima: X1=176, X2=496, X3=656.
En restricción (1) holgura X4 = 1.120
En restricción (2) holgura X5 = 0
En restricción (3) holgura X6 = 0
En restricción (4) holgura X7 = 0
De esta forma el Teorema de Holguras Complementarias permite obtener lo siguiente:
Que al ser reducido permite obtener un sistema de ecuaciones de 3×3:
2 Y2 + 3 Y3 + 2 Y4 = 3
5 Y2 + 2 Y3 + 2 Y4 = 3
3 Y2 + 5 Y3 + 1 Y4 = 2
Solución Problema Dual : Y1=0, Y2=1/25, Y3=3/25, Y4=32/25. Al evaluar la solución alcanzada en la función objetivo del dual se obtiene: W=4.800*0+4.800*1/25+4.800*3/25+2.000*32/25=3.328. Por el Teorema de Dualidad FuerteW=Z por lo tanto S2 es solución óptima del Problema Dual.
lo que indica que se podría desplazar indefinidamente en esa dirección y siempre interceptar el dominio de soluciones factibles.
