GEO Tutoriales, Autor en 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:

Cómo descargar e instalar OpenSolver en Excel 2010

OpenSolver es una alternativa gratuita a Premium Solver Pro y What’sBest! que permite resolver modelos de optimización haciendo uso de Excel. Este complemento fue desarrollado y actualmente mantenido por Andrew Mason y estudiantes del departamento de ciencias de la ingeniería de la Universidad de Auckland (Nueva Zelanda). En el siguiente artículo mostraremos cómo descargar e instalar OpenSolver en un computador que utiliza Windows 7 Home Premium como sistema operativo y Microsoft Office Professional Plus 2010.

Paso 1: Descargar OpenSolver21 (~~A la fecha de este artículo la versión 2.1 del 6 de Septiembre de 2012 es la más reciente~~).

Actualización: La última versión disponible a Octubre de 2015 es la edición 2.7.1 con fecha de lanzamiento 28 de Junio de 2015. Para descargar dicha versión se puede acceder directamente a la Página de Descarga e Instalación de OpenSolver.

Paso 2: Descomprimir el archivo ZIP de preferencia en una carpeta o en un lugar a elección.

Paso 3: Abrir el archivo «OpenSolver.xlam» (es aquel con el icono de Excel y un pequeño cuadrado color rojo en la esquina superior derecha).

Paso 4: Es probable que Excel solicite tu autorización para ejecutar el programa. En este caso debes seleccionar «Habilitar macros».

Una vez concluidos los pasos anteriores OpenSolver debería estar disponible en la pestaña de Datos en Excel (esquina superior derecha) tal como se muestra a continuación. En efecto se podrá encontrar a la derecha del acceso a Solver.

El complemento estará disponible hasta cerrar Excel. Si se desea que OpenSolver este siempre disponible al ejecutar Excel se deben copiar todos los archivos que están incluidos en el archivo comprimido (ZIP) de la instalación (aquellos que se pueden observar en la imagen del Paso 3) en el directorio de «add-in» de Excel. La ruta típica suele ser: C:/Documents and Settings/»user name»/Application Data/Microsoft/Addins (se debe tener en cuenta que el acceso puede cambiar dependiendo de la versión de Windows que se este utilizando).

Por qué no aparece el Informe de Confidencialidad (o Informe de Sensibilidad) en Solver de Excel

Cuando resolvemos un modelo de Programación Lineal en Solver de Excel tenemos la posibilidad de generar una serie de informes de respuesta entre los cuales destaca el denominado «Confidencialidad» (o «Sensibilidad» en versiones de Excel anteriores) que resume los principales resultados relativos al análisis de sensibilidad. Lo anterior es fácilmente accesible en el módulo de Resultados de Solver en una interfaz similar como la que se presenta a continuación:

Sin embargo la opción de obtener el Informe de Confidencialidad no siempre está disponible. Para ello consideremos que nos interesa resolver el siguiente modelo de Programación Entera:

A continuación desarrollamos la implementación computacional según se muestra en la imagen a continuación:

Se puede apreciar que la celda E3 es la fórmula de la función objetivo que representa la ponderación de los parámetros de la misma (10 y 16) por los valores que adquirirán las celdas que definiremos como variables de decisión (B3 y C3). Adicionalmente las celdas D6 y D7 también son fórmulas que considera la ponderación de los parámetros del lado izquierdo de las restricciones por las variables de decisión. Luego, se carga el modelo en Solver de Excel en la interfaz «Parámetros de Solver»:

Para obtener los resultados sólo es necesario presionar «Resolver» donde se actualizará en la planilla los resultados con la solución óptima X=2 e Y=2 y valor óptimo V(PE)=52. Notar sin embargo que el informe de Confidencialidad ya no se encuentra disponible.

¿Por qué sucede ésto?. Básicamente por qué los informes de sensibilidad en Solver se pueden obtener si el problema que se implementa es de naturaleza continua (como lo que sucedería en este mismo problema si se omiten las condiciones de integralidad para las variables de decisión lo que daría lugar a un modelo de Programación Lineal). Por el contrario un modelo de Programación Entera como el que hemos utilizado en este artículo tiene un dominio de factibilidad discreto. Lo anterior queda en evidencia en la siguiente representación gráfica del problema realizada con Geogebra:

El dominio de factibilidad continuo del modelo de Programación Lineal (omitiendo las condiciones de enteros para las variables de decisión) corresponde al área achurada denotada por el polígono que tiene por los vértices A, B, C y D. En cuanto al modelo de Programación Entera el dominio de factibilidad es discreto y se puede enumerar, lo cual corresponde a las coordenadas que representan los puntos A, E, F, B, I, H, G, J, K, C, M, L y D. En este contexto se debe recordar que uno de los supuestos básicos de la Programación Lineal es la proporcionalidad el cual ya no es admisible cuando nos enfrentamos a un problema de Programación Entera.

En consecuencia, si en la utilización de Solver de Excel queremos analizar el impacto que tiene la modificación de los parámetros del modelo en la resolución de un modelo de Programación Entera (principalmente en lo que se refiere a la solución óptima y valor óptimo) se propone reoptimizar modificando la(s) celda(s) que sean necesarias y ejecutar el programa nuevamente.