IORTutorial Archivos - Gestión de Operaciones

Programación Lineal (Método Gráfico)

El Método Gráfico (resolución gráfica) constituye una excelente alternativa de representación y resolución de modelos de Programación Lineal que tienen 2 variables de decisión. Para estos efectos existen herramientas computacionales que facilitan la aplicación del método gráfico como los softwares TORA, IORTutorial y Geogebra, los cuales se pueden consultar en detalle en Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA, Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial y Cómo Resolver Gráficamente un modelo de Programación Lineal con Geogebra, respectivamente. En este contexto a continuación presentamos un compendio de ejercicios de Programación Lineal resueltos a través del método gráfico.

Ejercicios Resueltos del Método Gráfico en Programación Lineal

Ejercicio N°1: Una empresa vitivinícola ha adquirido recientemente un terreno de 110 hectáreas. Debido a la calidad del sol y el excelente clima de la región, se puede vender toda la producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar de cada variedad en las 110 hectáreas, dado los costos, beneficios netos y requerimientos de mano de obra según los datos que se muestran a continuación:

Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días hombre durante el horizonte de planificación. Formule y resuelva gráficamente un modelo de Programación Lineal para este problema. Detalle claramente el dominio de soluciones factibles y el procedimiento utilizado para encontrar la solución óptima y valor óptimo.

Variables de Decisión:

$X_{1}$ : Hectáreas destinadas al cultivo de de Sauvignon Blanc
$X_{2}$ : Hectáreas destinadas al cultivo de Chardonay

Función Objetivo:

Maximizar $50X_{1}+120X_{2}$

Restricciones:

$X_{1}+X_{2}\leq 110$
$100X_{1}+200X_{2}\leq 10.000$
$10X_{1}+30X_{2}\leq 1.200$
$X_{1},X_{2}\geq 0$

Donde las restricciones están asociadas a la disponibilidad máxima de hectáreas para la plantación, presupuesto disponible, horas hombre en el período de planificación y no negatividad, respectivamente.

El siguiente gráfico muestra la representación del problema de la empresa vitivinícola. El área achurada corresponde al dominio de soluciones factibles, donde la solución básica factible óptima se alcanza en el vértice C, donde se encuentran activas las restricciones de presupuestos y días hombre. De esta forma resolviendo dicho sistema de ecuaciones se encuentra la coordenada de la solución óptima donde $X_{1}=60$ y $X_{2}=20$ (hectáreas). El valor óptimo es $V(P)=50(60)+120(20)=5.400$ (dólares).

Ejercicio N°2: Un taller tiene tres (3) tipos de máquinas A, B y C; puede fabricar dos (2) productos 1 y 2, todos los productos tienen que ir a cada máquina y cada uno va en el mismo orden: Primero a la máquina A, luego a la B y luego a la C. La siguiente tabla muestra:

Las horas requeridas en cada máquina, por unidad de producto
Las horas totales disponibles para cada máquina, por semana
La ganancia por unidad vendida de cada producto

Formule y resuelva a través del método gráfico un modelo de Programación Lineal para la situación anterior que permite obtener la máxima ganancia para el taller.

Variables de Decisión:

$X_{1}$ : Unidades a producir del Producto 1 semanalmente
$X_{2}$ : Unidades a producir del Producto 2 semanalmente

Función Objetivo:

Maximizar $X_{1}+1,5X_{2}$

Restricciones:

$2X_{1}+2X_{2}\leq 16$
$X_{1}+2X_{2}\leq 12$
$4X_{1}+2X_{2}\leq 28$
$X_{1},X_{2}\geq 0$

Las restricciones representan la disponibilidad de horas semanales para las máquinas A, B y C, respectivamente, además de incorporar las condiciones de no negatividad.

Para la resolución gráfica de este modelo utilizaremos el software GLP cual abordamos en el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP). El área de color verde corresponde al conjunto de soluciones factibles y la curva de nivel de la función objetivo que pasa por el vértice óptimo se muestra con una línea punteada de color rojo.

La solución óptima es $X_{1}=4$ y $X_{2}=4$ con valor óptimo $V(P)=1(4)+1,5(4)=10$ que representa la ganancia para el taller.

Ejercicio N°3: Una compañía elabora dos productos diferentes. Uno de ellos requiere por unidad 1/4 de hora en labores de armado, 1/8 de hora en labores de control de calidad y US$1,2 en materias primas. El otro producto requiere por unidad 1/3 de hora en labores de armado, 1/3 de hora en labores de control de calidad y US$0,9 en materias primas. Dada las actuales disponibilidades de personal en la compañía, existe a lo más un total de 90 horas para armado y 80 horas para control de calidad, cada día. El primer producto descrito tiene un valor de mercado (precio de venta) de US$9,0 por unidad y para el segundo este valor corresponde a US$8,0 por unidad. Adicionalmente se ha estimado que el límite máximo de ventas diarias para el primer producto descrito es de 200 unidades, no existiendo un límite máximo de ventas diarias para el segundo producto.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita maximizar las utilidades de la compañía.

Variables de Decisión:

$X_{1}$ : Unidades a producir diariamente del Producto 1
$X_{2}$ : Unidades a producir diariamente del Producto 2

Función Objetivo:

Maximizar $(9-1,2)X_{1}+(8-0,9)X_{2}=7,8X_{1}+7,1X_{2}$

Restricciones:

$\frac{X_{1}}{4}+\frac{X_{2}}{3}\leq 90$
$\frac{X_{1}}{8}+\frac{X_{2}}{3}\leq 80$
$X_{1}\leq 200$
$X_{1},X_{2}\geq 0$

La primera restricción representa las limitantes de horas de armado diariamente. La segunda restricción la disponibilidad de horas para labores de control de calidad (también diariamente). La tercera restricción establece una cota superior para la producción y ventas diarias del Producto 1. Adicionalmente se incluyen las condiciones de no negatividad para las variables de decisión.

El dominio de soluciones factibles tiene 5 vértices que corresponden a los candidatos a óptimos del problema. En particular el vértice óptimo es D de modo que la solución óptima es $X_{1}=200$ y $X_{2}=120$ con valor óptimo $V(P)=7,8(200)+7,1(120)=2.412$ que corresponde a la utilidad máxima para la empresa.

Importante: A la fecha de esta publicación disponemos de más de 70 artículos relativos a la Programación Lineal los cuales recomendamos revisar, donde se aborda la resolución gráfica de este tipo de modelos como también la resolución a través de algoritmos como el Método Simplex y la implementación computacional con herramientas como Solver, What’sBest! y OpenSolver, entre otras.

En el siguiente tutorial de nuestro canal de Youtube se explica un ejemplo adicional con todos los elementos del método gráfico en Programación Lineal:

Cadenas de Markov (Ejercicios Resueltos)

Un proceso estocástico en tiempo discreto se denomina una Cadena de Markov en tiempo discreto si y solo sí se satisface la Propiedad Markoviana (esto es básicamente que el futuro t=n+1 es independiente del pasado dado el presente t=n) y Propiedad Estacionaria (la probabilidad de pasar de un estado i a un estado j al cabo de una etapa no depende de la etapa n). A continuación presentamos un conjunto de problemas resueltos de Cadenas de Markov que sirvan de complemento para los estudios de nuestros usuarios.

Ejercicios Resueltos de Cadenas de Markov

Ejercicio N°1: Una empresa esta considerando utilizar Cadenas de Markov para analizar los cambios en las preferencias de los usuarios por tres marcas distintas de un determinado producto. El estudio ha arrojado la siguiente estimación de la matriz de probabilidades de cambiarse de una marca a otra cada mes:

Si en la actualidad la participación de mercado es de 45%, 25% y 30%, respectivamente. ¿Cuales serán las participaciones de mercado de cada marca en dos meses más?.

En primer lugar definimos la variable aleatoria $X_{n}$ que representa la marca que adquiere un cliente cualquiera en el mes n. Dicha variable aleatoria puede adoptar los valores 1,2,3 en el mes n=0,1,2,3,..

Adicionalmente conocemos cuál es la distribución inicial y la matriz de probabilidades de transición en una etapa tal como se observa a continuación:

Luego para conocer la distribución de las participaciones de mercado al cabo de 2 meses (2 etapas) podemos utilizar la fórmula $f^{n}=P^{T}*f^{n-1}$ :

Se concluye que las cuotas de mercado (participaciones de mercado) en dos meses a cambiado de un 45% a un 40.59%; de un 25% a un 33.91% y de un 30% a un 25.50%, para las marcas 1,2 y 3 respectivamente.

Ejercicio N°2: ¿Cuál es la cuota de mercado en el largo plazo para cada una de las marcas descritas en el Ejercicio N°1?.

La Cadena de Markov del Ejercicio N°1 es irreducible (es decir todos los estados se comunican entre sí) con estados recurrentes positivos y aperiódicos. Lo anterior se concluye luego de la Clasificación de Estados de una Cadena de Markov en Tiempo Discreto. Verificado lo anterior podemos obtener la Distribución Límite de una Cadena de Markov en Tiempo Discreto a través del siguiente sistema de ecuaciones:

La solución del sistema corresponde a: $\pi _{1}=0,2373$ , $\pi _{2}=0,6184$ y $\pi _{3}=0,1443$ , que representan las cuotas de mercado en el largo plazo para las marcas 1,2 y 3, respectivamente. Notar que las actuales participaciones de mercado difieren significativamente de las cuotas obtenidas en el largo plazo lo cual sugiere que de alguna manera deban ser corregidas las probabilidades de transición.

Ejercicio N°3: En una Unidad de Cuidados Intensivos en un determinado hospital, cada paciente es clasificado de acuerdo a un estado crítico, serio o estable. Estas clasificaciones son actualizadas cada mañana por un médico internista, de acuerdo a la evaluación experimentada por el paciente. Las probabilidades con las cuales cada paciente se mueve de un estado a otro se resumen en la tabla que sigue:

¿Cuál es la probabilidad que un paciente en estado crítico un día Jueves esté estable el día Sábado?.

Sea $X_{n}$ la variable aleatoria que indica el estado que se encuentra un paciente cualquiera en el hospital en el día n. Los valores posibles para dicha variable son C, S y E, representando los estados crítico, serio y estable, respectivamente. Un grafo que representa dicho proceso estocástico dada la tabla anterior es:

La probabilidad de que un paciente esté en estado crítico el día Jueves y que el día Sábado esté estable, esta dado por: $\mathbb{P}_{CE}^{2}$ , es decir, la probabilidad de pasar del estado crítico al estado estable al cabo de 2 etapas (días).

$\mathbb{P}_{CE}^{2}=0,3*0,2+0,1*0,5+0,6*0,1=0,17$

Notar que de forma equivalente se pueden utilizar las ecuaciones matriciales $f^{n}=P^{T}*f^{n-1}$ :

Se comprueba que la probabilidad de pasar del estado crítico al estado estable al cabo de 2 etapas es de un 17%.

¿Cuál es la probabilidad que un paciente que está en estado estable el Lunes experimente alguna complicación y no esté estable nuevamente el Miércoles?.

En este caso cambia la distribución inicial respecto al escenario anterior (ahora el paciente está en estado estable), no obstante, también resulta de nuestro interés analizar qué sucede al cabo de 2 etapas.

Con color verde se marca la probabilidad de que comenzando en un estado estable al cabo de 2 días un paciente se encuentre en estado crítico o serio. La suma de dichas probabilidades es un 66% que da respuesta a la interrogante anterior.

¿Qué porcentaje de la Unidad de Cuidados Intensivos usted diseñaría y equiparía para pacientes en estado crítico?.

Naturalmente se desea estimar la probabilidades de estado en el largo plazo independiente de la distribución inicial. La cadena es irreducible con estados recurrentes positivos aperiódicos. Utilizando las ecuaciones de estado estable presentadas en el Ejercicio N°2 se obtiene que $\pi _{C}\cong0,2373$ , $\pi _{S}\cong0,6184$ y $\pi _{E}\cong0,1443$ , que representan la probabilidad de que un individuo se encuentre en estado crítico, serio y estable, respectivamente.

El software Interactive Operations Research Tutorial (IORTutorial) permite estimar las probabilidades de largo plazo luego de ingresar la matriz de probabilidades de transición según se muestra a continuación:

Comentarios: En el Blog hemos desarrollado otros ejercicios resueltos que recomendamos revisar, entre ellos uno que aborda una Política de Gestión de Inventarios a través de Cadenas de Markov en Tiempo Discreto y Ejemplo de una Cadena de Markov en Tiempo Discreto. Adicionalmente en la categoría de contenidos de Cadenas de Markov periódicamente estamos publicando nuevo material didáctico sobre dicha materia. Esperamos que este material sea de utilidad para tus estudios y te agradecemos puedas ayudarnos a difundir éste a través de las redes sociales.

Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA

El software TORA es una excelente herramienta para resolver de forma intuitiva distintos modelos y aplicaciones de la Investigación Operativa. TORA está incluido en un CD (Compact Disc) adjunto al libro Investigación de Operaciones de Hamdy Taha y es compatible aún con las últimas versiones disponibles de Windows. Al respecto en el siguiente artículo se muestra su uso en un computador con sistema operativo Windows 7 Home Premium de 64 bits. para abordar la pregunta Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA. Adicionalmente el libro de Investigación de Operaciones de Hamdy Taha puede ser adquirido en sus versiones en español e inglés a precios convenientes desde distintos portales de comercio electrónico como Amazon.

Luego de su instalación y previo a su utilización es necesario realizar un ajuste a la resolución de pantalla seleccionando alguno de las 2 opciones recomendadas: 800×600 o 1024×786 pixeles (en realidad en este último caso 1024×768 como se podrá observar abajo). Para ello se debe ir al Panel de Control.

A continuación seleccionamos la resolución 1024×768 pixeles y Aplicar.

Luego se despliega una ventana que nos solicita confirmar nuestra selección anterior. En este caso debemos Conservar Cambios.

Una vez que el cambio en la resolución de pantalla ha sido ejecutado abrimos el programa TORA y se procede seleccionando el botón Click Here.

Una vez en el menú principal podemos seleccionar un importante número de funcionalidades relativas a la Investigación Operativa que se tratan en el libro de Hamdy Taha y donde TORA resulta ser un excelente complemento para el aprendizaje de los estudiantes. En esta oportunidad mostraremos cómo resolver un modelo de Programación Lineal por ello seleccionamos la opción Linear Programming.

En el menú que se despliega ingresamos el nombre o título del problema, la cantidad de variables y restricciones (aquellas adicionales a las de no negatividad).

En este tutorial utilizaremos el mismo ejemplo que implementamos en el artículo Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial, un problema que tiene 2 variables de decisión y 5 restricciones (donde 2 de ellas son las de no negatividad).

Luego se completan los parámetros de la grilla con la información relativa al ejemplo que nos interesa resolver tal como se observa en la siguiente imagen:

Una vez ingresados los datos del problema se selecciona Solve Menu, Solve Problem y Graphical.

En la ventana a continuación se nos pide confirmar la cantidad de decimales. En este caso mantendremos los valores que ofrece el programa por defecto y seleccionamos Go To Output Screen.

Finalmente llegamos a la interfaz que permite realizar una representación gráfica del modelo lineal. Para graficar las restricciones se debe seleccionar cada una de ellas de forma individual y finalmente marcar la función objetivo que mostrará el desplazamiento de la curva de nivel que permite alcanzar la solución óptima y valor óptimo (visible en la esquina inferior izquierda de la siguiente imagen). En próximos artículos seguiremos mostrando funcionalidades adicionales de TORA, hasta entonces.

Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial

Los modelos de Programación Lineal han sido motivo de amplio estudio en nuestro Blog y en esta oportunidad queremos presentar a nuestros usuarios una herramienta computacional sencilla e intuitiva llamada IORTutorial (Interactive Operations Research Tutorial) la cual nos permite resolver gráficamente modelos de Programación Lineal con 2 variables de decisión, además de proporcionar informes de sensibilidad para complementar la interpretación de los resultados alcanzados.

Para ello consideremos el ejemplo descrito en el artículo Cálculo del Intervalo de Variación del Lado Derecho que conserva la Base Óptima que permitirá al lector contrastar los resultados alcanzados en dicho ejemplo con el procedimiento alternativo que presentamos a continuación a través del uso de IORTutorial. El ejemplo en cuestión que considera 2 variables de decisión y 5 restricciones (considerando las 2 de no negatividad) es el siguiente:

La implementación computacional se muestra en el siguiente tutorial disponible en nuestro canal de Youtube que detalla Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial:

Cabe destacar que los resultados que se observan en el Informe de Sensibilidad (o Análisis de Sensibilidad) son equivalentes a los obtenidos en la resolución con Solver de Excel como se muestra en la imagen a continuación:

Cómo calcular Gráficamente el Precio Sombra de una Restricción

El Precio Sombra de una restricción en Programación Lineal indica cuánto cambia el valor de la función objetivo (óptimo) ante una variación marginal del lado derecho de una restricción. Se asume que el resto de los parámetros del modelo permanecen constantes. De antemano es conveniente señalar que el Precio Sombra puede ser positivo, cero o negativo y en el Blog iremos discutiendo estos distintos escenarios.

Para obtener los Informes de Sensibilidad de un modelo de Programación Lineal se puede hacer uso de herramientas computacionales como Solver de Excel, sin embargo, en esta oportunidad nos enfocaremos en el cálculo del precio sombra de una restricción en forma gráfica, lo que nos ayudará más adelante a entender los conceptos que fundamentan los resultados de Solver.

Cálculo del Precio Sombra de una Restricción con el Método Gráfico

A continuación calcularemos el precio sombra de una restricción del siguiente modelo de Programación Lineal:

La solución óptima de este modelo es X=100 e Y=350 con valor óptimo V(P)=3.100 según su resolución gráfica con Geogebra o su resolución con Solver de Excel. El siguiente diagrama muestra la solución óptima obtenida gráficamente en el vértice C, que corresponde a la intersección de la restricción 1 (R1: color rojo) y la restricción 3 (R3: color gris), siendo ésta una solución básica factible óptima.

Supongamos que deseamos saber cuánto cambiará el valor óptimo (respecto a su valor actual) si aumenta en una unidad el lado derecho de la restricción 1 pero sin resolver nuevamente el problema. El precio sombra nos permite dar respuesta a dicha interrogante y permite anticipar el nuevo valor óptimo ante una variación marginal del lado derecho de una restricción.

Un variación marginal de un lado derecho implica que la nueva solución óptima se seguirá encontrando con las actuales restricciones activas, es decir, aquellas que se cumplen en igualdad en el óptimo (esto es se conserva la base óptima).

En el caso de la restricción 1 si aumentamos su lado derecho, ésta se desplazará en forma paralela hacia arriba. Si buscamos garantizar que la nueva solución óptima aún se encontrará con R1 y R3 activas llegaremos al vértice donde actualmente se interceptan la R2 y R3 que corresponde a la coordenada X=166,67 e Y=350 (ésta será la máxima variación).

En forma análoga si disminuimos el lado derecho de la restricción 1 y buscamos mantener R1 y R3 activas en el nuevo óptimo, el último punto donde se garantiza esto es el vértice B cuyas coordenadas son X=0 e Y=350 (ésta será la menor variación). Con esta información calculamos el precio sombra de la restricción 1:

Este precio sombra es válido si el lado derecho de la restricción 1 (actualmente b1=1.600) varía entre [1.400,1.733,33]. Por ejemplo, si el lado derecho de R1 aumenta de 1.600 a 1.700 el nuevo valor óptimo será V(P)=3.100+100*1,5=3.250. Análogamente si el lado derecho de R1 disminuye de 1.600 a 1.550 el nuevo valor óptimo será V(P)=3.100-50*1,5=3.025. (Se recomienda corroborar estos resultados gráficamente con TORA o IORTutorial). Notar que si la variación del lado derecho de la restricción 1 está por fuera del intervalo [1.400,1.733,33], no se puede utilizar el precio sombra para predecir cuál será el nuevo valor óptimo.

En un próximo análisis complementaremos el cálculo del precio sombra de las restricciones 2 y 3 en conjunto con otros Análisis de Sensibilidad en la resolución de modelos de programación lineal. Hasta entonces!