investigación de operaciones Archivos - Página 2 de 26

Qué es la Programación Entera

¿Qué es la Programación Entera?: Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programación Lineal.

En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas: Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).

Programación Entera Mixta (PEM)

A esta categoría pertenecen aquellos problemas de optimización que consideran variables de decisión enteras o binarias pero no de forma exclusiva. De esta forma un problema de PEM puede considerarse como un híbrido entre distintas categorías de modelamiento, siendo un caso típico aquel que considera la mezcla de variables enteras y variables continuas (estas últimas características de los modelos de Programación Lineal). A modo de ejemplo los siguientes artículos que hemos abordado en el Blog dan cuenta de modelos de Programación Entera Mixta:

Programación Entera Pura (PEP)

En esta categoría encontramos aquellos modelos de Programación Entera que consideran exclusivamente variables de decisión que adoptan valores enteros o binarios. Un ejemplo de ello son las siguientes aplicaciones:

Problema de Asignación
Problema de Corte de Rollos
Selección de Invitados a una Boda
Programación de la Explotación Forestal
Problema de la Mochila

Notar que en los problemas anteriores (PEP) el conjunto de las soluciones factibles (o dominio de soluciones factibles) es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros).

Adicionalmente resulta interesante hacer un contrastes entre las propiedades de un modelo de Programación Lineal (PL) y uno de Programación Entera (PE). A continuación se presentan 2 modelos de optimización que se diferencian únicamente en que al segundo de ellos (PE) se le exige que las variables de decisión adopten valores enteros.

Para los problemas propuestos realizamos una representación gráfica haciendo uso del software Geogebra. El dominio de soluciones factibles del Problema Lineal (PL) corresponde al área achurada de color verde. Por otro lado el dominio de soluciones factibles del Problema Entero (PE) es enumerable y corresponde a las coordenadas denotadas por A, E, F, B, G, H, I, J, K, C, L, M, D (que es un subconjunto del dominio de factibilidad del PL). En este caso en particular la solución óptima de ambos problemas coincide (en el vértice C), no obstante, perfectamente podrían ser distintas (bastaría con modificar los parámetros del problema).

En este contexto y dada la naturaleza de los problemas propuestos, el valor óptimo del Problema Lineal (PL) será una cota superior del valor óptimo del Problema Entero (PE). También se concluye que el dominio de soluciones factibles de un modelo de Programación Lineal (cuando existe) representa un conjunto convexo (los problemas de Programación Lineal son convexos) y en el caso del problema de Programación Entera Pura su conjunto de soluciones factibles es discreto.

Adicionalmente según tratamos en el artículo Por qué no aparece el Informe de Confidencialidad (o Informe de Sensibilidad) en Solver de Excel se debe tener en cuenta que en la utilización de software para la resolución computacional del modelos de Programación Entera no tendremos acceso a los reportes de sensibilidad como en el caso de la implementación de modelos de Programación Lineal. De esta forma ante la necesidad de analizar el impacto en los resultados ante la modificación de los parámetros del problema será necesario reoptimizar ante la información que brinde el o los nuevos escenarios.

Es importante destacar que las aplicaciones de la Programación Entera no reemplaza la versatilidad que ofrece el disponer de modelos de Programación Lineal. Más aún, se pueden considerar estas categorías de modelamiento matemático como complementarias en el ámbito de la Investigación de Operaciones.

En este sentido en términos abstractos los modelos de Programación Entera imponen un desafío mayor al momento de la resolución en comparación a las propiedades simplificadoras que están asociadas a los problemas de Programación Lineal. De esta forma se espera que el tomador de decisiones sea capaz de evaluar la relación rigurosidad del modelado con el costo (complejidad) de la resolución del mismo.

Optimización de la Mezcla de Combustibles en una Refinería

El siguiente problema representa la optimización de la mezcla de combustibles en una refinería con el propósito de maximizar los beneficios asociados a su explotación. En este contexto este caso constituye una variante o extensión del Ejemplo de un Problema de Mezcla de Productos en Programación Lineal y otros conceptualmente similares como el Problema de Producción de Mezcla de Café, entre otros. A continuación los antecedentes de nuestro caso de estudio:

Problema de Mezcla de Combustibles

Una refinería compra 4 tipos de gasolinas no refinadas con las cuales puede fabricar hasta 3 tipos de combustibles para venta al público. La información se resume en la siguiente tabla:

Por ejemplo, la Gasolina No Refinada Tipo 1 tiene 68 Octanos y se dispone de un máximo de 4.000 barriles diarios, donde cada uno de estos barriles se compra a 23 Euros. Así mismo, por ejemplo, el Combustible 1 requiere un mínimo de 95 Octanos y su precio de venta es de 45 Euros el barril. Para el Combustible 1 en particular se establece un máximo de producción de 10.000 barriles diarios.

La refinería puede vender adicionalmente la gasolina no refinada a un precio de 39 Euros el barril si ésta tiene un octanaje mayor o igual a 90 Octanos. Alternativamente el precio de venta se reduce a 37 Euros el barril si el octanaje es inferior a 90 Octanos.

Formule un modelo matemático de Programación Lineal para ayudar a la refinería a maximizar sus ganancias diarias.

Variables de Decisión: Cada tipo de gasolina sin refinar tiene 4 usos posibles: ser vendida directamente o ser utilizada como insumo para producir Combustible tipo 1, 2 y 3.

Función Objetivo: Se desea maximizar la ganancia asociada al proceso de mezcla y venta de combustibles. Con verde se destaca los ingresos asociados a la venta de los 3 tipos de combustibles, con celeste los ingresos que provienen de la venta de gasolinas sin refinar y con color amarillo se descuentan los costos asociados a la compra de las gasolinas sin refinar.

Restricciones:

Disponibilidad de barriles diarios: Cada gasolina no refinada tiene 4 usos posibles: venta directa o como mezcla para elaborar combustible 1, 2 o 3. En cualquier caso su uso no podrá superar el máximo de barriles disponibles.

Octanaje mínimo: El octanaje de la mezcla de cada uno de los 3 combustibles (obtenido como un promedio ponderado de los octanajes de las respectivas gasolinas) debe al menos igualar el requerimiento mínimo establecido en este aspecto.

Límites de venta: No se puede vender más de 10.000 barriles diarios de Combustible 1 y adicionalmente no se puede vender menos de 15.000 barriles diarios de Combustible 3.

No negatividad: Las variables de decisión deben adoptar valores no negativos.

Obtenga la solución óptima y valor óptimo para el modelo utilizando Solver de Excel. Comente brevemente las características de la solución obtenida.

La solución óptima se observa en las celdas con color amarillo de la imagen anterior. Notar que no se produce Combustible tipo 2 y que el Combustible 3 se produce a máxima capacidad. La utilidad o valor óptimo es de 285.509,26 euros.

Analice las siguientes variantes del problema, explicando los resultados:

Aumento de la disponibilidad de la Gasolina No Refinada Tipo 4 a 5.000 barriles por día.

En este caso el valor óptimo aumenta en 10.629,63 euros en relación al valor óptimo original. El Precio Sombra de la restricción de disponibilidad de barriles diarios para la gasolina 4 (disponible en el archivo para descarga al final de este artículo) es de aproximadamente 15,185 con un aumento permisible para el lado derecho de 3.662,5 barriles (diarios). Luego un incremento en la disponibilidad de gasolina 4 en 700 barriles diarios genera una utilidad adicional del 700*15,185=10.629,5 (la diferencia con los 10.629,63 euros es sólo por efecto de la aproximación de decimales).

Aumento de los costos de las gasolinas con un octanaje menor a 90 en un 10%.

En este caso no se observa un cambio en la solución óptima en comparación al escenario inicial, no obstante las utilidades se ven reducidas dado el aumento en el costo de las gasolinas 1 y 2 (aquellas que tienen un octanaje inferior a 90 puntos).

Aumento de la demanda del Combustible 3 en 2.000 barriles diarios.

Este caso representa una merma en cuanto a las utilidades al ser más restrictivo que el problema original. Notar que ahora no se asignan gasolinas para venta directa y que también disminuye la cantidad de barriles diarios a fabricar del Combustible 1, llegado a 3.450.

¿Quieres tener la resolución en Solver de Excel de este modelo de optimización?

[sociallocker]Problema Refinación de Combustibles[/sociallocker]

Problema de Manejo de Aves en Programación Lineal

El siguiente artículo aborda la formulación y resolución computacional haciendo uso de AMPL y el solver CPLEX de un modelo de Programación Lineal que trata sobre el manejo óptimo de aves en un criadero con el objetivo de maximizar el valor comercial de su explotación transcurrido un horizonte de planificación de 4 semanas. Se busca dar un especial énfasis al modelamiento matemático y la interpretación intuitiva de la solución óptima y valor óptimo alcanzado de modo de visualizar de forma más sencilla la naturaleza del problema.

Suponga que a un ave de criadero le toma dos semanas poner 12 huevos para la venta o, alternativamente, tener 4 pollos (al empollar 4 huevos). Formule y resuelva un modelo de optimización que provea el mejor programa de manejo de las aves si al cabo de la cuarta semana todas las aves y pollos acumulados son vendidos a USD 0.60 cada unidad y los huevos a USD 0.10 cada unidad. Suponga un inventario inicial de 100 aves y 100 huevos.

Variables de Decisión:

xe0: cantidad de aves empolladoras de huevos inicial
xe2: cantidad de aves empolladoras de huevos al término de la semana 2
xe4: cantidad de aves empolladoras de huevos al término de la semana 4

xp0: cantidad de aves ponedoras de huevos inicial
xp2: cantidad de aves ponedoras de huevos al término de la semana 2
xp4: cantidad de aves ponedoras de huevos al término de la semana 4

ye0: cantidad de huevos inicial para ser empollados
ye2: cantidad de huevos empollados al término de la semana 2
yi0: cantidad de huevos inicial para inventario
yi2: cantidad de huevos en inventario al término de la semana 2

Función Objetivo:

Se desea maximizar el valor comercial del manejo de las aves, donde se obtendrá USD 0.60 por cada una de las 100 aves iniciales y los pollos que se obtienen al empollar (un pollo por cada huevo empollado). Adicionalmente se percibe un ingreso de USD 0.10 por los huevos obtenidos por las aves ponedoras y aquellos que quedan en inventario.

Max 0.6 (100 + ye0 + ye2) + 0.1 (12 xp2 + yi2)

Restricciones:

La cantidad de aves destinadas a empollar (o poner huevos, denominadas también ponedoras) deben ser menor o igual a 100 tanto al inicio del horizonte de planificación como al final de la segunda y cuarta semana. Por supuesto adicionalmente se debe satisfacer las condiciones de no negatividad.

0 ≤ xp0 ≤ 100
0 ≤ xp2 ≤ 100
0 ≤ xp4 ≤ 100
0 ≤ xe0 ≤ 100
0 ≤ xe2 ≤ 100
0 ≤ xe4 ≤ 100

La cantidad de aves destinadas para poner huevos o empollar durante al inicio del horizonte de planificación, al final de la semana 2 y al final de la semana 4, debe ser igual a 100 aves (que son las aves iniciales). Por supuesto los pollitos que puedan haber nacido durante el período de evaluación no están en condiciones de empollar o poner huevos.

xp0 + xe0 = 100
xp2 + xe2 = 100
xp4 + xe4 = 100

Los 100 huevos iniciales pueden ser destinados sólo para 2 propósitos: almacenar en inventario o ser utilizados para ser empollados.

ye0 + yi0 = 100

Por cada ave destinada a empollar (al inicio del horizonte de planificación o al término de la semana 4) se necesitarán exactamente 4 huevos.

ye0 = 4 xe0
ye2 = 4 xe2

La cantidad de huevos inicial para inventario, más los que se obtengan de las aves destinadas inicialmente como ponedoras (12 huevos por cada una de ellas), menos aquellos huevos empollados al término de la semana 2, deberá ser igual a la cantidad de huevos en inventario al término de la semana 2.

yi0 + 12xp0 – ye2 = yi2

Una vez definido el modelo de optimización lineal para el problema de manejo de las aves de criadero, se propone una formulación matemática del mismo en el lenguaje de programación matemática AMPL que da origen al siguiente código (se ha utilizado para estos efectos el software Notepad como editor de texto y el archivo se debe guardar con la extensión .mod).

A continuación podemos seleccionar algunos de los solvers compatibles con AMPL disponibles en la plataforma NEOS Solvers, en particular uno ad hoc a un modelo de Programación Lineal como resulta ser este caso. En este contexto hemos seleccionado CPLEX, cargando el archivo del modelo (que hemos llamado modeloaves.mod) de forma similar a la que usualmente se utiliza para adjuntar un archivo a un correo electrónico. Finalmente ingresamos un email donde deseamos recibir los resultados.

Al cabo de unos segundos recibiremos un correo electrónico con la solución óptima y valor óptimo del problema. Un extracto del mismo se muestra a continuación:

El valor óptimo corresponde a USD 410 que representa el valor comercial de las aves y huevos al final del período de planificación. En cuanto a la solución óptima esta corresponde a:

xe0: cantidad de aves empolladoras de huevos inicial = 25
xe2: cantidad de aves empolladoras de huevos al término de la semana 2 = 100
xe4: cantidad de aves empolladoras de huevos al término de la semana 4 = 0
xp0: cantidad de aves ponedoras de huevos inicial = 75
xp2: cantidad de aves ponedoras de huevos al término de la semana 2 = 0
xp4: cantidad de aves ponedoras de huevos al término de la semana 4 = 100
ye0: cantidad de huevos inicial para ser empollados = 100
ye2: cantidad de huevos empollados al término de la semana 2 = 400
yi0: cantidad de huevos inicial para inventario = 0
yi2: cantidad de huevos en inventario al término de la semana 2 = 500

Esquemáticamente y con el objetivo de facilitar la interpretación de la solución alcanzada, a continuación se presente una representación de la situación abordada.

Inicio: Se dispone de 100 aves y 100 huevos. De las 100 Aves, 25 de ellas son destinadas a empollar (utilizando cada una ella 4 huevos, por tanto se utiliza la totalidad del inventario inicial de huevos) y 75 aves serán ponedoras.

Semana 2: Transcurridas las 2 primeras semanas se habrán obtenido 900 huevos (12*75) por parte de las Aves ponedoras y adicionalmente tendremos 100 pollitos (que nacieron luego de que 25 Aves empollaran 4 huevos cada una por un lapso de 2 semanas). Luego se destinan las 100 Aves (por supuesto omitiendo los pollitos) a empollar (requiriendo un total de 400 huevos) y quedando de esta forma 500 huevos en inventario.

Semana 4: Se dispondrá de 500 pollitos (400 de ellos recién nacidos y los 100 restantes aquellos que nacieron en la Semana 2) y 100 Aves (que son aquellas iniciales y que en suma a los pollitos da un total de 600 aves, cada una con un valor comercial de USD 0.60, es decir, un total de USD 360). Como no se destinaron aves como ponedoras al término de la semana 2, sólo se podrán vender de forma directa aquellos huevos que quedaron en inventario al final de la semana 2 (500 huevos) a un valor unitario de USD 0.10, es decir, USD 50 en total. Se concluye que la valorización total de las aves (incluyendo los pollitos) más los huevos alcanza por tanto USD 410 (360+50).

¿Quieres tener el archivo .mod con la formulación del modelo de optimización en AMPL resuelto en este artículo? (El archivo .mod estará al interior de un archivo comprimido .zip).

[sociallocker]MUCHAS GRACIAS. DESCARGA AQUÍ EL ARCHIVO CON EL MODELO EN AMPL[/sociallocker]

Qué es la Programación Estocástica

La Programación Estocástica reúne aquellos modelos de optimización en donde uno o más parámetros del problema son modelados a través de variables aleatorias. Una manera de enfrentar esta aleatoriedad consiste en reemplazar los parámetros aleatorios por su valor esperado, lo cual lleva a resolver un problema determinístico de programación matemática, los cuales son de especial interés en cursos introductorios de Investigación de Operaciones y donde la variabilidad inherente a los parámetros se aborda a través del Análisis de Sensibilidad o Postoptimal.

No obstante, la solución obtenida de esta manera puede no ser representativa de la realidad, al no considerar la dispersión de los valores que toman los parámetros en torno al valor esperado, lo cual entre otras cosas puede invalidar su implementación al resultar finalmente escenarios muy diferentes del promedio.

De este modo y en general, una forma de incorporar esta situación de incertidumbre es considerar un número finito de posibles realizaciones o escenarios para los parámetros aleatorios.

El impacto de la incorporación explicita de la incertidumbre en modelos de programación matemática afecta la factibilidad y optimalidad del sistema en estudio. En efecto, la solución que entrega la resolución de un modelo determinista que considera reemplazar los parámetros aleatorios por su valor esperado, puede ser infactible para un escenario en particular.

En este contexto la connotación que tiene el término factibilidad en programación estocástica es más extensa que en el caso determinista, debido a que no se puede garantizar que la solución del modelo estocástico sea factible para todas las posibles realizaciones de la variable aleatoria. Frecuentemente se incluye términos de penalización en la función objetivos que castigan estas posibles infactibilidades ponderada por un cierto costo según se constata por ejemplo en las investigaciones de Sen, S. and Higle, J.L. (1999). Introductory Tutorial on Stochastic Linear Programming Models. Interfaces 29, No.2, 33-61.

En cuanto al impacto que tiene la incertidumbre sobre la optimalidad del modelo formulado se puede observar que a mayor variabilidad de los parámetros aleatorios, el valor que alcanza la función objetivo varía en torno a una media en mayor magnitud. En este sentido la literatura reúne una serie de indicadores que cuantifica este impacto (Birge, J and Louveaux, F (1997). Introduction to Stochastic Programming, Springer – Verlag, New York, USA) de la incorporación explícita de la incertidumbre en la formulación del modelo y permite al tomador de decisiones dilucidar el real impacto de ésta.

Clasificación de los modelos de Programación Estocástica

Los modelos de optimización estocástica se dividen en dos grandes categorías, estos son: Modelos con Restricciones Probabilísticas y Modelos con Recurso. Una referencia general al respecto lo constituye un tutorial desarrollado por Sen y Higle (1999) sobre programación estocástica para el caso lineal y libros como el de Birge y Louveaux (1997).

Modelos con Recursos en 2 Etapas

En un modelo con recurso en dos etapas se pueden distinguir aquellas variables de decisión que son implementadas antes de la realización particular del parámetro aleatorio denominadas de primera etapa o here and now, que se debe tomar antes de conocer la realización de la variable aleatoria, es decir que se escoge tomando en cuenta la aleatoriedad de los parámetros, pero cuyo valor es independiente de la realización particular que finalmente vaya a tomar dicha variable aleatoria. Las variables de primera etapa pueden ser vistas como decisiones proactivas y están asociadas frecuentemente a decisiones estratégicas como la planificación y expansión de sistemas de producción.

En tanto las variables que son determinadas una vez conocida la realización particular de la variable aleatoria son llamadas de segunda etapa o de recurso, es decir, su valor es tomado en respuesta al medio. En este sentido las variables de segunda etapa son de naturaleza reactiva y generalmente están asociadas a decisiones operativas.

Análisis de Sensibilidad (Método Gráfico)

El Análisis de Sensibilidad en Programación Lineal permite analizar el impacto en los resultados del modelo (solución óptima y valor óptimo) en aquellos casos donde uno o varios parámetros sufren modificaciones en relación a sus valores originales, sin la necesidad de resolver nuevamente el problema (sin reoptimizar). En dicho contexto en el siguiente artículo presentamos un ejemplo de dicho análisis para un problema de optimización lineal que considera 2 variables de decisión.

Ejemplo Análisis de Sensibilidad (Método Gráfico)

Un productor tabaquero posee 85 hectáreas (ha) de terreno para plantar dos variedades de tabacos Virginia y Procesado. La variedad Virginia tiene un ingreso de 9.600 USD/ha y necesita 3 horas/ha de uso de maquinaria y 80 horas/ha de mano de obra. Además, el Estado limita su explotación a 30 ha como máximo. La variedad Procesado tiene un ingreso de 7.500 USD/ha y utiliza 2 horas/ha de uso de maquinaria y 60 horas/ha de mano de obra. La cooperativa local le ha asignado un máximo de 190 horas de uso de maquinaria y solo se dispone de 5.420 horas de mano de obra a 12 USD/hora.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita determinar cuánto se debe plantar de cada variedad de tabaco de manera de maximizar la utilidad total.

En primer lugar definimos el modelo de optimización para este problema. Esto consiste en identificar las variables de decisión, función objetivo y restricciones. Detalle de este procedimiento aplicado a problemas de 2 variables puede ser consultado en el artículo Programación Lineal (Método Gráfico).

Variables de Decisión:

X₁ = Número de Ha a plantar de la variedad Virginia
X₂ = Número de Ha a plantar de la variedad Procesado

Función Objetivo:

Maximizar (9.600 – 960)X₁ + (7.500 – 720)X₂ = 8.640X₁ + 6.780X₂

Restricciones:

X₁ ≤ 30
X₁ + X₂ ≤ 85
3X₁ + 2X₂ ≤ 190
80X₁ + 60X₂ ≤ 5.420
X1, X2 ≥ 0

Una representación gráfica del problema para el productor de tabaco se puede realizar a través del software Geogebra:

Sabemos según el Teorema Fundamental de la Programación Lineal que en caso de existir solución óptima ésta se encontrará en un vértice o en un tramo en la frontera del dominio de soluciones factibles (en el ejemplo área achurada en color verde). Adicionalmente podemos apreciar que no es tan evidente que el vértice C reporte una mayor utilidad en la función objetivo que el vértice D, por lo cual, inspeccionaremos ambos puntos.

En el caso del vértice C éste se encuentra en la intersección de las restricciones 2 y 4. La coordenada respectiva se obtiene al resolver el siguiente sistema de ecuaciones:

X₁ + X₂ = 85
80X₁ + 60X₂ = 5.420

De donde X₁=16 y X₂=69, lo cual reporta un valor en la función objetivo de V(P)=8.640*(16)+6.780(69)=606.060.

Análogamente en el caso del vértice D las restricciones activas son 3 y 4:

3X₁ + 2X₂ = 190
80X₁ + 60X₂ = 5.420

Luego de resolver el sistema lineal anterior se obtiene X₁=28 y X₂=53, lo cual reporta un valor en la función objetivo de V(P)=8.640*(28)+6.780(53)=601.260.

En consecuencia la solución óptima del problema es X₁=16 y X₂=69, con valor óptimo V(P)=8.640*(16)+6.780(69)=606.060.

Una vez resuelto el escenario original a continuación se presentan algunos análisis adicionales que representan por separado modificaciones en los coeficientes de la función objetivo y restricciones del problema.

Intervalo Variación Coeficiente Función Objetivo

Determine cuánto podría variar la utilidad por hectárea del tabaco Virginia, manteniendo constante la utilidad por hectárea del tabaco procesado, de forma que la actual solución óptima no cambie. Para este caso determine el intervalo de variación de la utilidad total.

Sea en términos generales la función objetivo Z=C₁X₁+C₂X₂, donde inicialmente en el ejemplo C₁=8.640 y C₂=6.780. La pendiente de las curvas de nivel de la función objetivo es -C₁/C₂. De este modo se conserva la actual solución óptima (vértice C) en la medida que:

$-\frac{4}{3}\leq-\frac{C_{1}}{C_{2}}\leq -1$
$\frac{4}{3}\geq \frac{C_{1}}{C_{2}}\geq 1$
$\frac{4}{3}\geq \frac{C_{1}}{6.780}\geq 1$
$9.040\geq C_{1}\geq 6.780$

En este caso la utilidad por hectárea del tabaco Virginia puede variar entre 6.780 USD y 9.040 USD, de tal forma que el actual nivel de producción (solución óptima) sería el mismo. Lo anterior permite concluir que el intervalo de variación para la utilidad total será $576.300\leq Z\leq 612.460$ .

Precio Sombra (Método Gráfico)

Si se pudiese contratar más mano de obra disponible en el mercado, ¿Cuántas horas de mano de obra en total estaría dispuesto a utilizar? ¿Cuál sería el aporte adicional de esas horas extras que utilizaría en términos monetarios? Responda lo anterior utilizando el concepto de Precio Sombra.

Para calcular gráficamente el precio sombra necesitamos identificar la máxima y mínima variación para el lado derecho de la restricción de mano de obra que permita garantizar que se conserva la actual base óptima (restricciones activas originales). En este sentido en el caso de aumentar el lado derecho de dicha restricción la solución óptima podrá ser encontrada manteniendo las restricciones activas (e incorporando una adicional) hasta la coordenada (20,65) que es donde se interceptan la segunda y tercera restricción. En el caso de disminuir la disponibilidad de horas en mano de obra se mantiene la base óptima hasta el vértice B cuya coordenada es (0,85). De esta forma se obtiene el precio sombra de la siguiente forma:

En consecuencia el lado derecho de la restricción 4 (disponibilidad de mano de obra) puede variar entre [5.100, 5.500] y se conservan las actuales restricciones activas. Adicionalmente dado que en el óptimo actual se utilizan 5.420 horas de mano de obra se deben contratar 80 horas adicionales (de modo de alcanzar las 5.500 horas). Luego, la variación de 80 horas adicionales implicaría un aumento en la utilidad total de 80*USD93=7.440USD.