GEO Tutoriales, Autor en Gestión de Operaciones

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$ ).

Efecto de cambios en el Número de Aceptación en la Curva Característica de Operación

En la construcción de una Curva Característica de Operación asociada a un plan de muestreo, resulta de interés sensibilizar los resultados frente a variaciones de los parámetros que determinan la probabilidad de aceptación del lote para distintos valores de calidad a la entrada. En este artículo abordaremos el caso donde se modifica el número de aceptación c el cual establece el límite máximo de unidades defectuosas que se esta dispuesto a aceptar en la inspección de un lote productivo.

Consideremos el ejemplo que representa un plan de muestreo simple que se aplica a un lote de N=1.200 unidades, sobre las cuales se toma una muestra aleatoria de n=100 unidades. Nos interesa evaluar el impacto en la probabilidad de aceptación del lote para distintos niveles de porcentajes de defectuosos a la entrada, asumiendo tres escenarios para los números de aceptación c: 4 (curva roja), 6 (curva azul) y 8 (curva verde) unidades.

Se observa que en la medida que aumenta el valor de c (número de aceptación) manteniendo el resto de los parámetros constantes, aumenta también la probabilidad de aceptación del lote. Esto se refleja en las Curvas Características Operativas en un desplazamiento hacia la derecha en relación a planes de muestreos con valores de c más pequeños (restrictivos). Dicho resultado queda de manifiesto en las siguientes tablas resumen generadas en Excel.

Por ejemplo si consideramos en cada uno de los 3 escenarios una porcentaje de unidades defectuosas a la entrada de un 2% entonces la probabilidad de aceptación del lote para valores de c igual a 4, 6 y 8 unidades será un 94,73%, 99,55% y 99,98%, respectivamente.

Problema de Planificación Financiera en Programación Lineal resuelto con Solver

El siguiente artículo trata de un problema de planificación financiera el cual se aborda a través de la Programación Lineal y se resuelve computacionalmente haciendo uso del complemento Solver de Excel. En este contexto se presenta un problema de inversión en distintos instrumentos financieros en los cuales se planifica invertir al inicio de cada uno de los próximos 10 años (horizonte de planificación), considerando los siguientes montos disponibles al comienzo de cada año (independiente de los retornos obtenidos producto de las mismas inversiones en años anteriores).

Los instrumentos disponibles son:

Depósito a plazo (anuales) con un retorno de 4,5% anual.
Bono a 6 años plazo con retorno de 4,9% anual.
Bono a 9 años plazo con retorno de 5,2% anual.

Se busca formular un modelo de optimización que posea los mayores retornos al término del décimo año (o inicio del año 11). Para ello se propone el siguiente problema de Programación Lineal:

Problema de Planificación Financiera

Variables de Decisión: Se establecen las posibilidades de inversión en los distintos instrumentos financieros. Notar que dado el período de maduración de los mismos se define la factibilidad de invertir en ellos en cada uno de los años. Por ejemplo, como el depósito anual tiene una maduración de un año se puede invertir en él en cada uno de los años del período de planificación. No así, por ejemplo, con el Bono a 9 años plazo el cual se puede invertir sólo al inicio del año 1 y 2.

Función Objetivo: Se desea maximizar el dinero obtenido al finalizar el período de planificación correspondiente al término del año 10 (o inicio del año 11).

Restricciones: Para cada año se limita las posibilidades de inversión según los instrumentos disponibles, el presupuesto del período y el retorno de los instrumentos que ya maduraron. Por ejemplo, en el año 1 se puede invertir en cada una de las 3 alternativas respetando el presupuesto de MM$20. En el año 2 nuevamente se puede invertir en las 3 alternativas y el presupuesto disponible corresponderá a los MM$20 de dicho período (según se detalla en la tabla al inicio) y eventualmente se podrá hacer uso del retorno de la inversión del depósito anual realizado en el año 1. Si, por ejemplo, se invierte los MM$20 en el depósito anual a inicio del año 1, entonces el presupuesto disponible para el año 2 será: 20+1,045(20)=MM$40,9.

A continuación se presenta un extracto de los resultados que provee la implementación computacional del modelo anterior haciendo uso de Solver. Las celdas color amarillo corresponde a la solución óptima, alcanzando un valor óptimo de MM$402,64.

Es interesante analizar la estructura de la solución óptima alcanzada. En el año 1 y 2 se invierte la totalidad del presupuesto en el Bono a 9 años plazo; en los años 3, 4 y 5 se invierte de forma exclusiva en los bonos a 6 años plazo; finalmente del año 5 al año 10 se invierte en el depósito anual.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre “Descarga el Archivo” se mostrará abajo una vez que nos hayas recomendado).

[l2g name=»Descarga el Archivo» id=»4694″]

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})$ .

Revista Ingeniería Industrial de la Universidad del Bio-Bio Chile

Uno de nuestros principales objetivos como sitio referente en el ámbito de la Ingeniería Industrial es compartir con nuestros valiosos usuarios publicaciones y referencias en el área de operaciones que dan cuenta del estado del arte de esta disciplina a nivel mundial. En esta oportunidad quisiéramos invitarlos a visitar la Revista Ingeniería Industrial la cual corresponde a una divulgación científica responsabilidad del Departamento de Ingeniería Industrial, perteneciente a la Facultad de Ingeniería de la Universidad del Bío-Bío, Concepción, Chile.

La revista es una fuente de referencia en artículos de investigación originales e inéditos de todo iberoamérica en las distintas áreas de la Ingeniería Industrial y sus aplicaciones. Los usuarios pueden acceder a interesantes publicaciones las cuales pueden ser descargadas bajo la modalidad de acceso abierto en forma digital como también la posibilidad de suscribirse anualmente por un valor de $30.000 (pesos chilenos) o US$100 (dólares norteamericanos) . Adicionalmente existe la posibilidad de registrarse de modo de poder contribuir con artículos e investigaciones relevantes en el área, las cuales serán consideradas a evaluación por un prestigioso equipo editorial con amplia experiencia en la Ingeniería Industrial.

De modo de tener una referencia de las temáticas tratadas en la revista a continuación un extracto de los contenidos de la versión correspondiente al Segundo Semestre 2014:

Reiteramos nuestros saludos y felicitaciones el equipo de la Revista Ingeniería Industrial y esperamos mantener un estrecho contacto con ellos en el futuro.