Gestión de Operaciones

Qué es una Solución Básica Factible en Programación Lineal

En Programación Lineal una Solución Básica Factible (SBF) es aquella que además de pertenecer a la región o área factible del problema se puede representar a través de una solución factible en la aplicación del Método Simplex satisfaciendo las condiciones de no negatividad.

En este contexto una solución básica factible corresponderá a uno de los vértices del dominio de factibilidad cuya coordenada o solución se puede representar a través de un conjunto de restricciones activas para el modelo.

Para desarrollar el concepto anterior consideremos el siguiente problema de optimización matemática (lineal):

La resolución gráfica del problema anterior haciendo uso de Geogebra se presenta en el siguiente gráfico:

El área achurada corresponde al dominio de factibilidad del problema, identificándose en particular 5 vértices que hemos llamado arbitrariamente A, B, C, D y E.

La solución óptima del modelo lineal se alcanza en el vértice C donde X=100 e Y=350 con valor óptimo V(P)=3.100. Notar que dicha solución se puede obtener a través de la resolución de un sistema de ecuaciones con las restricciones 1 y 3 (R1 y R3) en igualdad.

En consecuencia, el vértice C además de ser una solución básica factible es una solución básica factible óptima.

En cuanto a los vértices A, B, D y E son soluciones básicas factibles (no óptimas) debido a que en la aplicación del Método Simplex al menos una variable no básica tendrá costo reducido negativo (lo que permitirá mejorar el actual valor de la función objetivo).

La tabla a continuación es la que se obtiene al llevar al problema a su forma estándar, agregando S1, S2 y S3 como variables de holgura de las restricciones 1, 2 y 3, respectivamente (R1, R2 y R3).

Ambas variables no básicas (iniciales) X e Y tienen costo reducido negativo (-3 y -8) por tanto X=0 e Y=0 que si bien es una solución básica factible (vértice A) no es solución óptima.

Para continuar la demostración realizaremos una iteración del Método Simplex incorporando la variable Y a la base (criterio costo reducido “más negativo“) y donde el mínimo cuociente Min {1.600/4; 1.700/2; 350/1}=350 ==> S3 deja la base:

La solución básica factible ahora es X=0 e Y=350 (vértice B), sin embargo, el costo reducido de la variable X sigue siendo negativo y por tanto aún no nos encontramos en el óptimo. En consecuencia X entra a la base y obtenemos el mínimo cuociente: Min {200/2; 1.000/6}=100 ==> S1 deja la base:

Finalmente se alcanza la solución óptima (solución básica factible óptima) con X=100 e Y=350 (vértice C) donde todas las variables no básicas (S1 y S3) tienen costos reducido mayor o igual a cero, cumpliendo con el criterio de optimalidad.

¿Qué sucede con los vértices D y E? También son soluciones básicas factibles (no óptimas) que se podrían encontrar por ejemplo incorporando en primera instancia (tabla inicial) a la variable X a la base. De esta forma se debería alcanzar el vértice E luego de una iteración y el vértice D en una segunda iteración.

Notar que también existen otras soluciones factibles (no básicas) como, por ejemplo, X=100 e Y=100 que pertenecen al dominio de soluciones factibles pero no se puede representar a través de la resolución de un sistema de ecuaciones.

Como resolver un modelo de Programación Lineal con OpenSolver

OpenSolver es una excelente complemento de Excel que permite resolver modelos de optimización. En el siguiente artículo se describe cómo resolver un modelo de Programación Lineal con esta herramienta (previa descarga e instalación de OpenSolver en Excel 2010). Para fines académicos consideraremos un modelo lineal con 2 variables de decisión, no obstante se puede extender su aplicación a problemas de mayor tamaño sin inconvenientes.

A continuación necesitamos preparar una planilla Excel que considere los parámetros y variables del modelo (este paso es similar a la carga de un modelo en Solver de Frontline). Se puede apreciar que las celdas B2 y C2 (color amarillo) han sido asignadas a las variables de decisión y la función objetivo (celda azul) corresponde a la celda E2 que es una fórmula que vincula las variables de decisión y los respectivos parámetros que ponderan a éstas. Finalmente las celdas D5 y D6 son fórmulas que representan el “lado izquierdo” de las restricciones del problema (por ejemplo la celda D5 corresponde a B2*B5+C2*C5 o equivalentemente SUMAPRODUCTO(B2:C2;B5:C5)).

Una vez completado el paso anterior se debe ejecutar OpenSolver cuyo menú esta disponible en la pestaña de “Datos” de Excel. Luego se selecciona “Model…” según se muestra a continuación:

La interfaz para implementar el modelo es bastante similar a la versión tradicional de Solver (Frontline). Se define la celda objetivo (E2) en maximización; a continuación se selecciona el rango de variables de decisión (según se muestra en la siguiente imagen) y las restricciones. Si intentas replicar la estructura del ejemplo que desarrollamos en este artículo se debería ver así:

Luego seleccionamos “Save Model” (cambiará la estructura de la planilla la cual adoptará colores lo cual es una de las características de OpenSolver que hacen de este complemento una herramienta intuitiva para el usuario).

Finalmente seleccionamos “Solve”:

El programa se ejecutará y proporcionará (de existir) la solución óptima (X=0 e Y=60) y valor óptimo (V(P)=1.200) del problema de optimización:

Los resultados alcanzados son coincidentes con los alcanzados en la resolución gráfica del problema que hemos abordado en el artículo “Qué significa un Precio Sombra igual a Cero en Programación Lineal“ según muestra la imagen a continuación:

A continuación puedes descargar el archivo con la resolución en OpenSolver de este problema de modo de que puedas familiarizarte con este complemento de Excel: Modelo de Programación Lineal resuelto con OpenSolver

Análisis de Sensibilidad en Programación Lineal utilizando la Tabla Final del Método Simplex

Un supuesto básico asociado a la Programación Lineal es que los parámetros o constantes son valores conocidos con exactitud al momento de resolver el modelo de optimización. Este supuesto de asumir que no existe incertidumbre claramente implica una simplificación en el modelamiento de problemas de naturaleza real y es conocido como el supuesto de modelo determinista.

La optimización también permite incorporar explícitamente la incertidumbre en los parámetros en el modelamiento, asumiendo que la totalidad o un conjunto de éstos se distribuyen aleatoriamente, lo cual se puede representar a través de una función de probabilidad conocida o una distribución empírica que modela distintos escenarios para los parámetros, asociando una probabilidad de ocurrencia en cada caso. Esta categoría de modelos de optimización (por cierto más complejos en comparación al caso determinista) se llaman modelos estocásticos, los cuales en rara oportunidad se analizan en cursos introductorios de Investigación de Operaciones, de modo que forman parte del programa de estudios en cursos de Magíster y Doctorado asociado al área de optimización matemática.

En relación a lo anterior, si bien un modelo determinista considera valores fijos para los parámetros, aún podemos analizar los cambios en los resultados del modelo (solución óptima y valor óptimo principalmente) en comparación a lo obtenido en una instancia de resolución original o escenario base. Esto se conoce como análisis de sensibilidad o análisis postoptimal.

Recordemos que la estructura de la tabla final del Método Simplex se puede representar de la siguiente forma:

Donde:

I: Matriz Identidad (Diagonal de “1”)
0: Vector de costos reducidos asociados a las variables básicas
B: Matriz de variables básicas
D: Matriz de variables no básicas
b: Vector de “lado derecho”
Cb: Coeficientes en la función objetivo asociados a las variables básicas
Cd: Coeficientes en la función objetivo asociados a las variables no básicas

A continuación presentamos los Análisis de Sensibilidad más recurrentes asociados a los modelos de Programación Lineal y utilizando como fuente de información la tabla final del Método Simplex. El siguiente es un listado de los artículos que hemos desarrollado para cada uno de estos temas los cuales te recomendamos visitar:

Intervalo de Confianza para un Pronóstico de Demanda

En el siguiente artículo abordaremos cómo calcular un Intervalo de Confianza para un Pronóstico de Demanda, lo cual permite incorporar de forma explícita el impacto que tiene la incertidumbre en la planificación de las actividades comerciales y operacionales de una empresa.

Para ello utilizaremos el Método de Alisado Exponencial o Suavizamiento Exponencial el cual hemos descrito previamente en nuestro sitio. (Ver también: Suavizamiento Exponencial Doble Ejercicios Resueltos).

Consideremos una serie histórica con la demanda de un producto para un periodo de 12 semanas. Se requiere desarrollar un intervalo de confianza del 95% para el Pronóstico de Demanda de la semana 13 utilizando el Método de Suavizamiento Exponencial Simple con α=0,3.

Para ello adoptaremos el supuesto que los errores del pronóstico se distribuyen normalmente lo cual es algo que por supuesto se puede verificar con una dedicación mayor de trabajo y para lo cual se puede utilizar un software de análisis estadístico como Easyfit.

En este contexto la tabla a continuación se muestra el pronóstico comenzando a contar de la semana 4 (esta es una decisión arbitraria dado que podría haber comenzado antes).

Notar que el primer pronóstico corresponde simplemente a la Media Móvil Simple de las primeras 3 semanas.

Luego el pronóstico de la semana 5 se obtiene de la aplicación de la siguiente fórmula: F5=F4+α(A4-F4) que al reemplazar se obtiene F5=1.775+0,3*(1.860-1.775)=1.800,5~1.801 (hemos aproximado éste y los otros pronósticos al entero más cercano según se puede apreciar en la fórmula de Excel utilizada):

Ahora necesitamos calcular la desviación estándar del error del pronóstico la cual se obtiene simplemente evaluando en los datos de la tabla anterior según se muestra a continuación:

Finalmente el intervalo de confianza de un 95% para el pronóstico de la semana 13 se obtiene: (notar que F13=1.766+0,3*(1.780-1.766)=1.770,2~1.770)

El resultado anterior es consistente con el proporcionado por la herramienta de Cálculos de Probabilidad de Geogebra donde para una distribución de probabilidad normal (recordar el supuesto de normalidad del error adoptado anteriormente) con media μ=1.770 (F13) y desviación estándar SF=71, el área achurada en color azul representa los valores contenidos en el intervalo de confianza de un 95% (% del área bajo la curva achurada).

Cómo utilizar una Regresión Lineal para realizar un Pronóstico de Demanda

El Método de Mínimos Cuadrados o Regresión Lineal se utiliza tanto para pronósticos de series de tiempo como para pronósticos de relaciones causales. En particular cuando la variable dependiente cambia como resultado del tiempo se trata de un análisis de serie temporal.

En el siguiente artículo desarrollaremos un Pronóstico de Demanda haciendo uso de la información histórica de venta de un producto determinado durante los últimos 12 trimestres (3 años) cuyos datos se observan en la siguiente tabla resumen:

La ecuación de mínimos cuadrados para la regresión lineal es la que se muestra a continuación donde β0 y β1 son los parámetros de intercepto y pendiente, respectivamente:

Estimar los valores de dichos parámetros es sencillo haciendo uso de una planilla Excel tal como muestra la tabla a continuación:

Luego evaluamos en las ecuaciones presentadas anteriormente para obtener los valores de β0 y β1:

Una vez obtenido los parámetros de la regresión lineal se puede desarrollar un pronóstico de demanda (columna color naranja) evaluando en la ecuación de la regresión para los distintos valores de la variable independiente (x).

Por ejemplo, para el primer trimestre el pronóstico es: Y(1)=441,71+359,61*1=801,3.

Observación: los valores de los pronósticos han sido redondeados arbitrariamente a un decimal para mayor comodidad.

Notar que con la información que hemos obtenido podemos calcular el MAD y la Señal de Rastreo y utilizar estos indicadores para validar la conveniencia de utilizar este procedimiento como dispositivo de pronóstico.

Adicionalmente puede resultar de interés consultar el artículo Ejemplo de una Regresión Lineal Múltiple para un Pronóstico con Excel y Minitab que muestra cómo abordar el caso de realizar una regresión lineal con más de una variable independiente (explicativa).

Siguiendo con nuestro análisis a continuación podemos desarrollar un pronóstico de demanda para los próximos 4 trimestres (un año) que corresponden a los trimestres 13, 14, 15 y 16:

Y(13)=441,71+359,61*13=5.116,64
Y(14)=441,71+359,61*14=5.476,25
Y(15)=441,71+359,61*15=5.835,86
Y(16)=441,71+359,61*16=6.195,47

Si bien el procedimiento anterior es válido puede ser resumido haciendo uso de las herramientas de análisis de datos de Excel o simplemente realizando un ajuste de una regresión lineal en un gráfico de dispersión de la misma forma que abordamos en el articulo sobre el Método de Descomposición. Para ello luego de realizar el gráfico nos posicionamos en una de las observaciones y luego botón derecho del mouse para seleccionar “Agregar línea de tendencia…”.

Luego en la interfaz de Excel activamos las opciones “Presentar ecuación en el gráfico” y “Presentar el valor R cuadrado en el gráfico” (este último indicador según se aborda en los cursos de estadística consiste en una medida de la bondad de ajuste de la regresión).

Notar que los valores obtenidos para los parámetros de la regresión son similares salvo menores diferencias por efecto de aproximación.

Otra opción disponible para ajustar una Regresión Lineal haciendo uso de Excel es a través del Complemento llamado Herramientas para análisis.

Su activación es simple: en el menú Archivo (esquina superior izquierda en Excel) ir a Opciones, luego Complementos, a continuación a la derecha de donde dice Complementos de Excel presionar Ir… y luego activar la Herramientas para análisis.

Una vez activada las Herramientas para análisis, se puede encontrar ésta abajo del complemento Solver en el menú de Datos.

Luego de las opciones disponibles que nos ofrece este complemento seleccionamos Regresión.

A continuación seleccionamos el Rango Y de entrada las celdas correspondientes a la variable dependiente (Ventas) y en Rango X de entrada las celdas correspondientes a la variable independiente (Trimestre).

Debemos activar adicionalmente la casilla Residuos si deseamos obtener un pronóstico para las ventas del Trimestre 1 al Trimestre 12 (junto al cálculo del error o residuo de la estimación).

Finalmente presionamos Aceptar lo que generará una nueva hoja en nuestra planilla de cálculo.

Un extracto de los resultados es el que se presenta a continuación, donde en color celeste se destaca los coeficientes asociados a los parámetros de la regresión lineal β0 y β1, respectivamente, y en color naranjo el pronóstico obtenido para cada uno de los doce trimestres al utilizar la ecuación de la regresión.

Por ejemplo: Y(1)=441,67+359,61*1=801,28. El residuo o error correspondiente para dicho período (Trimestre 1) es: $e_{1}=A_{t}-F_{t}=600-801,28=-201,28$ .

¿Quieres tener el archivo Excel con el ajuste de la Regresión Lineal de este problema?.

[sociallocker]MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO[/sociallocker]