solución básica factible 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:

Cambio en el Lado Izquierdo de las Restricciones en Programación Lineal

El el contexto del Análisis de Sensibilidad en Programación Lineal es usual analizar el impacto que tiene la modificación en la disponibilidad de los recursos en la solución óptima alcanzada originalmente. Esto corresponde al Cambio en el Lado Derecho de las Restricciones (Análisis de Sensibilidad en Programación Lineal). En el siguiente artículo abordaremos el caso cuando cambia un coeficiente o parámetro en el lado izquierdo de las restricciones, generalmente asociado a un coeficiente tecnológico o factor de productividad (por ejemplo, la cantidad de horas hombre que puede requerir la fabricación de un producto, la cantidad de dinero requerido por unidad a producir dada una restricción presupuestaria, entre otras). En relación a lo anterior consideremos el caso de una empresa la cual tiene un plan de producción representado por:

Donde $x_{j}$ es la cantidad a producir del bien j, z la utilidad de la empresa (en unidades monetarias u.m) y los coeficientes $a_{ij}$ de las restricciones, la cantidad de recurso i por unidad del producto j. Al aplicar el Método Simplex al modelo anterior incorporando $x_{4}$ y $x_{5}$ como variables de holgura de las restricciones del recurso 1 y 2 respectivamente, resulta la siguiente tabla final:

Si el requerimiento del primer recurso por parte del producto j=2 cambia de 5 a 2 debido a la incorporación de una nueva tecnología ¿Cambia la actual solución óptima? ( $x_{1}=\frac{20}{3}$ , $x_{2}=\frac{4}{3}$ y $x_{3}=0$ ). Sabemos que:

Luego al cambiar un coeficiente en el lado izquierdo asociado a la variable básica $x_{2}$ , es necesario actualizar la matriz de base inversa o $B^{-1}$ . Lo anterior se deduce del cálculo de la matriz inversa asociada a la matriz $B$ donde los elementos en la columna correspondiente a los coeficientes en el lado izquierdo (forma estándar del Método Simplex) asociadas a las variables básicas $x_{1}$ y $x_{2}$ , respectivamente. Finalmente obtenemos la nueva solución básica y verificamos si es factible, esto es si el valor que adopta cada una de las variables básicas satisface las condiciones de no negatividad (en caso que una de las variables básicas alcance un valor negativo se puede continuar las iteraciones con el Método Simplex Dual luego de actualizar el valor de la función objetivo).

En nuestro ejemplo $x_{1}=\frac{28}{3}$ , $x_{2}=\frac{2}{3}$ y $x_{3}=0$ lo cual implica que se modifica la solución óptima original pero se conserva la actual base óptima (las mismas variables básicas originales). El nuevo valor óptimo será:

Cálculo del Intervalo de Variación del Lado Derecho que conserva la Base Óptima

Una vez concluidas las iteraciones del Método Simplex y en el caso de alcanzar una solución básica factible óptima, puede resultar de interés determinar un intervalo de variación para un parámetro del vector de los lados derechos de las restricciones que permita conservar la geometría del problema. Esto implica que se conservan las restricciones activas originales en el nuevo escenario (es decir, se mantiene la base óptima) que se genera a partir de la modificación (individual) de un parámetro o coeficiente del lado derecho. Para ilustrar el resultado anterior consideremos el siguiente modelo de Programación Lineal.

Luego de llevar a la forma estándar el modelo anterior agregando $x_{3}$ , $x_{4}$ y $x_{5}$ como las variables de holgura de las restricciones 1, 2 y 3, respectivamente, y aplicar las iteraciones necesarias del Método Simplex, se alcanza la siguiente tabla final (óptima):

La solución óptima es $x_{1}=15$ y $x_{2}=40$ con valor óptimo $V(P)=615$ . El valor de las variables de holgura en el óptimo $x_{3}$ , $x_{4}$ y $x_{5}$ es 0, 0 y 20, respectivamente. Luego se puede concluir que la solución óptima del problema se alcanza con las restricciones 1 y 2 activas (notar que sus respectivas holguras con variables no básicas en el óptimo) y la base actual esta conformada por las variables $x_{1}$ , $x_{2}$ y $x_{5}$ .

Sabemos adicionalmente que, por ejemplo, el costo reducido de la variable de holgura $x_{3}$ representa el precio sombra asociado a la primera restricción ( $\pi_{1}=1/2$ ). No obstante desconocemos en qué intervalo puede variar el parámetro del lado derecho de la restricción 1 (actualmente $b_{1}=180$ ) de modo que se conserve la base óptima y por tanto nos permita hacer un correcto uso de la información del precio sombra.

Para ello se propone la siguiente fórmula que permite encontrar el intervalo de variación para un lado derecho que conserva la base óptima:

Max {-bj/yij con yij>0} <= D <= Min {-bj/yij con yij<0}

Por ejemplo determinemos el intervalo para el parámetro $b_{1}$ :

En consecuencia $b_{1}$ puede disminuir en 30 unidades y aumentar en 15 unidades y se conserva la base óptima. Es decir, si $b_{1}\epsilon [150,195]$ se mantiene la base óptima.

El resultado anterior se puede corroborar gráficamente. La solución óptima se encuentra en el vértice C donde las restricciones 1 y 2 son activas (notar la curva de nivel que pasa por el vértice óptimo es la línea punteada de color azul). Si para el lado derecho de la restricción 1 consideramos $b_{1}=150$ se obtiene la línea de color verde y para $b_{1}=195$ la línea de color rojo. En estos casos si bien se modifica el dominio de soluciones factibles, la solución óptima conserva las actuales restricciones activas (y por ende cuando $b_{1}$ adopta un valor fuera de este intervalo cambia la geometría del problema o base óptima).

Esto es consistente con el Informe de Confidencialidad de Solver. En particular el reporte de restricciones donde se aprecia el aumento y reducción permisible que conserva la actual base óptima:

Por ejemplo, ¿cuál es el nuevo valor óptimo si el lado derecho de la restricción 1 ahora es $b_{1}=190$ ?. Como $b_{1}=190\epsilon[150,195]$ , entonces $V(P)=615+\Delta b_{1}\pi _{1}=615+(190-180)*(1/2)=620$ . ¿Cuál es la nueva solución óptima?. Como sabemos que se conservan las restricciones activas en el óptimo para la variación propuesta, la solución óptima del nuevo escenario se obtiene simplemente resolviendo el siguiente sistema de ecuaciones (notar que la restricción 1 y 2 se conservan activas):

De donde $x_{1}=20$ y $x_{2}=110/3$ , que al evaluar en la función objetivo se obtiene: $V(P)=9*(20)+12*(110/3)=620$ corroborando el resultado anterior. Dejamos al lector el desafío de aplicar los conceptos presentados en este articulo para encontrar un intervalo para $b_{2}$ y $b_{3}$ que conserve la base óptima.

Método del Costo Mínimo (Algoritmo de Transporte en Programación Lineal)

El Método del Costo Mínimo determina una mejor solución básica factible inicial que el Método de la Esquina Noroeste debido a que se concentra en las rutas menos costosas.

De esta forma el Método del Costo Mínimo se inicia asignando lo máximo posible a la celda que tenga el mínimo costo unitario (en caso de empates, éstos se rompen de forma arbitraria). A continuación, la fila o columna ya satisfechos de tacha, y las cantidades de oferta y demanda se ajustan en consecuencia. Si se satisfacen de forma simultanea una fila y una columna, sólo se tacha uno de los dos (de forma idéntica que el Método de la Esquina Noroeste). Luego se busca la celda no tachada con el costo unitario mínimo y se repite el proceso hasta que queda sin tachar exactamente una fila o una columna.

Consideremos nuevamente el Problema de Transporte donde se desea satisfacer la demanda de 4 molinos a través de los envíos de 3 silos, donde los valores en la esquina superior derecha de cada cuadro $c_{ij}$ representan los costos unitarios de transporte desde el silo i al molino j.

Fe de Erratas: En la imagen dice Molino 1, 2, 3 y 5 (columnas). Debería decir: Molino 1, 2, 3 y 4.

La aplicación del Método de Costo Mínimo al problema de transporte anterior da origen a la siguiente solución factible de inicio:

Los pasos aplicados para llegar a dichos resultados se resumen a continuación:

La celda $x_{12}$ tiene el menor costo unitario, por tanto se asigna lo máximo posible (15 unidades correspondiente a la oferta del silo 1). Con $x_{12}=15$ se satisface tanto la demanda del molino 2 como la oferta del silo 1. Se tacha de forma arbitraria la columna 2.
Ahora la celda $x_{31}$ tiene el mínimo costo unitario sin tachar. Se asigna $x_{31}=5$ y se tacha la columna 1 porque quedó satisfecha (lo cual deja una capacidad remanente del silo 3 de 5 unidades).
Al continuar de este modo, se asignan en forma sucesiva 15 unidades a la celda $x_{23}$ , 0 unidades a la celda $x_{14}$ (la capacidad del silo 1 ya fue asignada), 5 unidades a la celda $x_{34}$ y 10 unidades a la celda $x_{24}$ .

La solución básica factible de inicio resultante con 6 variables básicas es: $x_{12}=15, x_{14}=0, x_{23}=15, x_{24}=10, x_{31}=5, x_{34}=5$ la cual reporta un valor en la función objetivo (costo) de Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=$475 que efectivamente es una mejor solución inicial que la obtenida por el Método de la Esquina Noroeste (que provee un valor de $520 al ser evaluado en la función objetivo) pero por cierto no es la solución óptima según se aprecia en la siguiente imagen que resume la implementación computacional del problema en Solver.

Método de Aproximación de Vogel (Algoritmo de Transporte en Programación Lineal)

El Método de Aproximación de Vogel es una versión mejorada del Método del Costo Mínimo y el Método de la Esquina Noroeste que en general produce mejores soluciones básicas factibles de inicio, entendiendo por ello a soluciones básicas factibles que reportan un menor valor en la función objetivo (de minimización) de un Problema de Transporte balanceado (suma de la oferta = suma de la demanda).

Los pasos que requiere la aplicación del Método de Aproximación de Vogel son los siguientes:

Paso 1: Determinar para cada fila (columna) una medida de penalización restando el elemento de costo unitario mínimo en la fila (columna) del elemento con costo unitario siguiente al mínimo de la misma fila (columna).

Paso 2: Identificar la fila o columna con la mayor penalización. Romper los empates (de existir) de forma arbitraria. Asignar todo lo posible a la variable que tenga el mínimo costo unitario de la fila o columna seleccionada. Ajusta la oferta y la demanda y tachar la fila o la columna ya satisfecha. Si se satisfacen una fila y una columna en forma simultánea, sólo se tacha uno de los dos y al que queda se le asigna oferta o demanda cero.

Paso 3:

Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
Si queda sin tachar una fila (columna) con oferta (demanda) positiva, determinar las variables básicas en la fila (columna) con el Método del Costo Mínimo. Detenerse.
Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda (restante), determinar las variables básicas cero por el Método del Costo Mínimo. Detenerse.
En cualquier otro caso, seguir en el Paso 1.

Ejemplo Método de Aproximación de Vogel

Consideremos nuevamente un problema de transporte balanceado que tiene 3 fuentes de oferta (silos) y 4 fuentes de demanda (molinos). Los valores numéricos en la esquina superior derecha de cada cuadro, en adelante $c_{ij}$ representan el costo unitario de transporte desde el silo i al molino j. Por ejemplo $c_{11}=10$ es el costo unitario de transporte desde el silo 1 al molino 1.

Según lo descrito anteriormente el primer paso consiste en calcular el factor de penalización para cada fila y columna de la tabla que representa el problema de transporte anterior. Por ejemplo, en la fila 1 el mínimo costo es $2 y y el costo unitario siguiente al mínimo es $10. En consecuencia la penalización de dicha fila es $8 ($10-$2). Se replica el mismo cálculo para cada fila y columna de la tabla lo cual es trivial y reporta los siguientes resultados (se han marcado las penalizaciones de las respectivas filas y columnas con color naranjo para mayor claridad):

Como la fila 3 tiene la máxima penalización ($10) y la celda correspondiente a $x_{31}$ tiene el costo unitario mínimo de esa fila, se asigna 5 unidades a $x_{31}$ (más no es necesario aún cuando la capacidad del silo 3 lo permite dado que la demanda del molino 1 es de sólo 5 unidades). Con esto la columna 1 se debe tachar (lo hemos marcado con color amarillo) y se procede a calcular las nuevas penalizaciones como se aprecia a continuación:

Ahora la penalización máxima es $9 ($11-$2) lo cual se alcanza en la fila 1. En consecuencia se asigna la máxima cantidad posible a la variable $x_{12}$ , con lo que se obtiene $x_{12}=15$ , y al mismo tiempo se satisfacen tanto la fila 1 como la columna 2. En forma arbitraria se tacha la columna 2 y se ajusta a cero la oferta en la fila 1.

Al continuar de la misma forma, ahora la fila 2 es la que produce la máxima penalización correspondiente a $11 ($20-$9), por tanto se asigna $x_{23}=15$ , con lo que se tacha la columna 3 y quedan 10 unidades en la fila 2. Sólo queda la columna 4 y tiene 15 unidades de oferta positiva. Al aplicar el Método del Costo Mínimo a esa columna, se asigna de forma sucesiva $x_{14}=0, x_{34}=5, x_{24}=10$ (se recomienda verificar dichos resultados). Notar adicionalmente que hay otras soluciones posibles que dependen de cómo se rompen los empates.

El valor de la función objetivo asociado a esta solución factible inicial es Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=$475 que es similar a lo alcanzado por el Método del Costo Mínimo, no obstante, en general el Método de Aproximación de Vogel reporta mejor solución de inicio.