geogebra Archivos - Página 3 de 7 - Gestión de Operaciones

Cómo detectar que un Problema de Programación Lineal es infactible con el Método Simplex de 2 Fases

Un problema infactible en Programación Lineal es una situación que se detecta cuando en la aplicación del Método Simplex de 2 Fases el valor óptimo del problema de la Fase 1 es distinto a cero (para continuar a la Fase 2 se requiere que el valor óptimo de la Fase 1 sea cero). Cabe recordar que un problema infactible es aquel cuyo dominio de soluciones factibles es vacío.

Consideremos el siguiente modelo de Programación Lineal en 2 variables que nos permitirá representar dicha situación:

Agregamos las siguientes variables al modelo para aplicar el Método Simplex de 2 Fases: $x_{3} (holgura), x_{4} (exceso), x_{5} (auxiliar)$ .

Definiendo el problema inicial de la Fase 1:

A continuación llevamos el costo reducido de la variable $x_{5}$ a cero, multiplicando por -1 la fila 2 y sumando ésta a la fila 3:

Para favorecer la rapidez de convergencia del método $x_{2}$ entra a la base. Luego calculamos el criterio del mínimo cuociente: $Min \begin{Bmatrix}{\frac{2}{1}, \frac{12}{4}}\end{Bmatrix}=2$ por tanto $x_{3}$ deja la base. Actualizamos la tabla:

Notar que todas las variables no básicas $x_{1}, x_{3}, x_{4}$ tienen costos reducidos mayores o iguales a cero. Adicionalmente las variables básicas $x_{2}, x_{5}$ cumplen con las condiciones de no negatividad. En consecuencia hemos finalizado la Fase 1 del Método Simplex de 2 Fases, sin embargo, el valor de la función objetivo es distinto de cero (en el ejemplo es -4) lo que determina que el problema es infactible.

La siguiente representación gráfica del problema anterior se puede realizar con Geogebra. El área achurada color rojo corresponde a la intersección de los conjuntos de factibilidad definido por la restricción 1 y las de no negatividad. Por otra parte el área achurada color azul es la intersección de los conjuntos de factibilidad definido por la restricción 2 y las de no negatividad. Luego resulta evidente que la intersección de dichos conjuntos (rojo y azul) es vacío, por tanto no existen valores que puedan adoptar las variables de decisión y satisfacer de forma simultanea todas las restricciones del problema.

Qué es una Solución Óptima Degenerada en Programación Lineal

En la aplicación del Método Simplex al hacer el cálculo del mínimo cuociente o condición de factibilidad, se puede romper un empate en la razón o cuociente mínimo en forma arbitraria. En este caso, al menos una variable básica será cero en la siguiente iteración, afirmándose en este caso que la nueva solución es degenerada. La implicancia práctica de dicha condición indica que el modelo tiene al menos una restricción redundante.

Solución Óptima Degenerada

Consideremos el siguiente modelo de Programación Lineal el cual resolveremos a través del Método Simplex y que de forma complementaria representaremos gráficamente con Geogebra:

Llevamos el problema anterior a su forma estándar de minimización, agregando $x_{3}$ y $x_{4}$ , como variables de holgura de las restricciones 1 y 2, respectivamente.

Que da origen a la siguiente tabla inicial del Método Simplex:

Para favorecer la rapidez de convergencia del algoritmo seleccionamos $x_{2}$ como la variable que ingresa a la base. A continuación calculamos el criterio de factibilidad (mínimo cuociente): $Min \begin{Bmatrix}{\frac{8}{4}, \frac{4}{2}}\end{Bmatrix}=2$ (al existir empate seleccionaremos arbitrariamente la variable $x_{3}$ como aquella que deja la base. Luego se actualiza la tabla:

Ahora $x_{1}$ ingresa a la base. El criterio de factibilidad determina que: $Min \begin{Bmatrix}{\frac{2}{1/4}, \frac{0}{1/2}}\end{Bmatrix}=0$ $x_{4}$ deja la base. Se realiza entonces una nueva iteración:

Se alcanza la solución óptima degenerada del problema lineal. Notar que $x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18$ . Como éste es un problema bidimensional, la solución está sobredeterminada y una de las restricciones es redundante tal como se corrobora en la representación gráfica:

En la práctica conocer que algunos recursos (como los asociados a una restricción) son superfluos puede ser valioso durante la implementación de la solución. Desde el punto de vista teórico, la degeneración tiene dos implicaciones: se genera el fenómeno de ciclos o círculos (es posible que el Método Simplex repita una serie de iteraciones sin mejorar el valor de la función objetivo, tal como se observo en el ejemplo anterior e incluso eventualmente nunca terminar los cálculos); el segundo aspecto teórico surge al examinar las iteraciones 1 y 2. Las dos, aunque difieren en la clasificación de las variables básicas y no básicas, producen valores idénticos para todas las variables y el valor objetivo ( $x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18$ ).

Ejemplo del Método de Frank Wolfe en Programación No Lineal

El método o algoritmo de Frank Wolfe fue propuesto en 1956 por Marguerite Frank y Philip Wolfe y se aplica a problemas de optimización matemática con una función objetivo no lineal convexa y cuyo dominio de soluciones factibles esta compuesto exclusivamente por restricciones lineales, es decir, es un conjunto convexo (en consecuencia el problema es convexo).

Consideremos el siguiente problema que asumiremos cumple con el formato anteriormente descrito:

Dada una aproximación $x^{k}$ a la solución óptima del problema, podemos resolver un problema más sencillo que aproxime al problema P), suponiendo $x^{k}$ factible.

O equivalentemente resolviendo el siguiente problema:

Que puede ser resuelto mediante el Método Simplex. Denotamos por $x_{PL}^{k}$ la solución óptima de $PL_{k}$ . El método contempla en seguida una minimización de un problema unidimensional que equivale a escoger un escalar $\alpha _{k}$ de modo que:

En seguida se define la siguiente aproximación al óptimo como:

Que equivale a definir $x^{k+1}$ como la solución óptima de f restringida al conjunto de puntos que determina al segmento que une $x^{k}$ con $x_{PL}^{k}$ .

Ejemplo: Aplicar el método de Frank Wolfe al siguiente problema no lineal restringido (convexo). Notar que la matriz hessiana o de segundas derivadas de la función objetivo es positiva definida.

Realizamos la primera iteración del método que da origen al siguiente problema de Programación Lineal:

La resolución es trivial y puede ser alcanzada de forma gráfica con Geogebra. La solución óptima es $x_{PL}^{0}=(0,3)$ según se aprecia a continuación:

Luego buscamos la solución para el problema unidimensional en términos del parámetro $\alpha$ :

Finalmente se obtiene $x^{1}=x^{0}+\frac{2}{3}(x_{PL}^{0}-x^{0})=(0,2)$ concluyendo una iteración del método de Frank Wolfe. Se propone al lector seguir las iteraciones a contar de este punto. Por ejemplo se puede verificar que $x_{PL}^{1}=(2,0)$ . (Hint: La solución óptima se alcanza en $(x_{1},x_{2})=(1,\frac{3}{2})$ .

Análisis Marginal en la Gestión de Inventarios de Productos Perecibles

En general la Gestión de Inventarios de productos perecibles enfrenta desafíos mayores en comparación a la determinación de tamaños de lotes de aquellos productos de ciclo de vida largo donde los productos se desvalorizan de forma más lenta y adicionalmente existe más de una oportunidad de venta. En este contexto el análisis marginal es una alternativa metodológica para enfrentar los problemas de determinación de tamaño de lote de producción o compra, bajo un contexto de incertidumbre (demanda incierta) donde existe una oportunidad única de orden o producción.

Si un producto es perecible (notar que bajo esta clasificación no sólo debemos considerar productos alimenticios) y la demanda excede la cantidad ordenada, entonces se pierde venta (lo que genera costos de quiebres de stock, los cuales son complejos de estimar según lo analizado en la clasificación de los costos de inventario). Por el contrario, si la demanda es menor que la cantidad ordenada entonces sobra inventario el cual puede o no tener un uso alternativo, no obstante por lo general el valor monetario que se logra rescatar de su uso alternativo no logra cubrir la totalidad del costo de compra o fabricación.

El análisis marginal enfrentar el problema de determinación de tamaño de lote de compra o producción de aquellos productos perecibles. Se enfoca en analizar lo que ocurre con el artículo a vender que tiene peor margen, y asegurar que este margen sea positivo. Si se venden “k” items, nos preocupa analizar el margen esperado (en probabilidad) del k-ésimo artículo en venderse. Si D representa la demanda (variable aleatoria) de un producto perecible, ¿cuál es la probabilidad de vender la k-ésima unidad del inventario?:

La probabilidad de que la demanda total sea por lo menos k unidades!. Luego, la probabilidad de NO vender la k-ésima unidad es:

El margen esperado de la k-ésima unidad queda descrito por:

Notar que la ganancia esperada es decreciente en la medida que aumenta el tamaño de pedido.

En consecuencia, queremos encontrar el mayor valor de k tal que esta cantidad sea no negativa. Esto equivale a encontrar el mayor k tal que:

Ejemplo Análisis Marginal en la Gestión de Inventarios

Un retailer especialista en artículos de moda debe decidir cuántas cajas de vestidos de la línea “Sass” pedir para la próxima temporada. Esta línea de vestidos es sumamente exclusiva y elaborada manualmente en Italia. Ya que se trata de un producto nuevo y altamente costoso, el Product Manager encargado de la compra pide ayuda a cinco expertos de la empresa. Juntos ellos pronostican que la demanda seguirá una distribución normal con media 10 cajas y desviación estándar igual a 2 cajas.

La ganancia por cada vestido vendido es de 24% del costo. Si no se vende un vestido, este debe ser liquidado, en cuál caso sólo se recupera el 64% del costo. Utilice el pronóstico de los expertos para modelar la demanda con una distribución normal, y determine la cantidad de cajas que debiera pedir el retailer a fin de maximizar sus ganancias. Indique el nivel de servicio instock que se ofrecerá a los clientes producto de esta estrategia. En su análisis suponga que es posible comprar (y vender) fracciones de cajas.

El nivel de servicio instock es de un 40%. El tamaño óptimo de pedido (aproximado luego de ajustar el valor de Z(40%)) según el análisis marginal es:

Notar que el tamaño óptimo de pedido calculado anteriormente se puede corroborar haciendo uso del software Geogebra, donde luego de seleccionar la función de probabilidad teórica que representa el comportamiento de la demanda, se ingresan sus parámetros y el nivel de servicio (instock) objetivo.

Otra alternativa es obtener Z(40%) haciendo uso de Excel. Para ello utilizamos la fórmula =DISTR.NORM.ESTAND.INV(0,4) según se muestra en la siguiente imagen:

Cómo construir una Curva Característica de Operación (CO) con Excel

La Curva Característica de Operación (o Curva Característica Operativa) consiste en una representación gráfica que muestra para un plan de muestreo específico (n,c) la probabilidad de aceptación del lote, para varios valores de calidad del lote a la entrada p (% de unidades defectuosas). Una Curva Característica de Operación tendrá entre sus puntos uno definido por el NCA y 1-α y otro punto definido por PTDL y β.

Para determinar la probabilidad de aceptación de un lote, se pueden utilizar las distribuciones Binomial o Poisson. Cuando el tamaño de la muestra es al menos 15 unidades (n>15), el tamaño del lote es al menos 10 veces el tamaño de la muestra (N>10*n) y el porcentaje de unidades defectuosas históricamente es menor a un 10% (p<10%), es preferible la Distribución de Poisson debido a la facilidad de los cálculos.

Consideremos el siguiente ejemplo: Un fabricante de pistones para motocicletas comenzará a vender diariamente 1.200 unidades para un nuevo cliente. Este último determina condiciones contractuales para la inspección del lote diario, especificando que tomará muestras de 100 unidades (n=100) y que sólo aceptará los pedidos con 4 o menos defectos (c=4). El fabricante menciona en el contrato, que históricamente ha obtenido un porcentaje defectivo del 2% (p=2%). Determinar la probabilidad de aceptación del lote por parte del cliente.

Para determinar la probabilidad de aceptación del lote podemos utilizar la siguiente fórmula haciendo uso de una planilla de cálculo Excel: =POISSON(4;100*2%;VERDADERO). En consecuencia la probabilidad de aceptación del lote por parte del cliente es de un 94,73% (aproximado).

Una alternativa a Excel para estos efectos es hacer uso de la herramienta de cálculo de probabilidades del software Geogebra donde se debe ingresar los parámetros de la distribución µ (equivalente a n*p=100*2%=2) y el valor correspondiente al número de aceptación c (en la imagen c=4).

De esta forma se puede extender el procedimiento calculando la probabilidad de aceptación del lote Pa para distintos valores de calidades a la entrada p. Un extracto de ello se presenta en la siguiente tabla:

A continuación se construye un gráfico con la Curva Característica de Operación. Se ha destacado con una etiqueta color amarillo el dato que hemos calculado previamente.

En un próximo artículo discutiremos el impacto que tiene en el plan de muestreo y en particular en la Curva Característica de Operación un cambio en el tamaño de la muestra o un cambio en el número de aceptación.