MÉTODO GRÁFICO
El método gráfico es un procedimiento de solución de problemas de programación lineal
muy limitado en
cuanto al número de variables (2 si es un gráfico 2D y 3 si es 3D)
pero muy rico en materia de interpretación de resultados e incluso
análisis de sensibilidad. Este consiste en representar cada
una de las restricciones y encontrar en la medida de lo posible el
polígono (poliedro) factible, comúnmente llamado el conjunto solución o
región factible, en el cual por razones trigonométricas
en uno de sus vértices se encuentra la mejor respuesta (solución
óptima).
EL PROBLEMA
La fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos
tejidos de calidad diferente T y T’; se dispone de 500 Kg de hilo a, 300
Kg de hilo b y 108 Kg de hilo c. Para obtener un metro de
T diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c;
para producir un metro de T’ por día se necesitan 200 gr de a, 100 gr de
b y 27 gr de c.
El T se vende a $4000 el metro y el T’ se vende a $5000 el metro. Si
se debe obtener el máximo beneficio, ¿cuántos metros de T y T’ se deben
fabricar?
LA MODELIZACIÓN MEDIANTE PROGRAMACIÓN LINEAL
VARIABLES
XT: Cantidad de metros diarios de tejido tipo T a fabricar
XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar
RESTRICCIONES
0,12XT + 0,2XT’ <= 500 Hilo “a”
0,15XT + 0,1XT’ <= 300 Hilo “b”
0,072XT + 0,027XT’ <= 108 Hilo “c”
Las restricciones de no negatividad no son necesarias en este
ejemplo dado que se trata de un ejercicio de maximización, cuando el
ejercicio sea de minimización lo más recomendado es incluirlas.
FUNCIÓN OBJETIVO
ZMAX = 4000XT + 5000XT’
LA SOLUCIÓN MEDIANTE MÉTODO GRÁFICO
PASO 1: GRAFICAR LAS RESTRICCIONES
Para iniciar con el trazado de las restricciones es indispensable
igualar las restricciones a 0, de esta manera podemos mediante despeje
de ecuaciones iniciar con la tabulación que nos otorgará
las coordenadas para esbozar cada una de las gráficas. Además dado
que se trabajará en el plano cartesiano sería prudente renombrar las
variables
XT = x
XT' = y
Igualamos las restricciones,
0,12X + 0,2y = 500
0,15X + 0,1y = 300
0,072X + 0,027y = 108
Acto seguido iniciamos con la primera restricción, hallamos las
primeras dos coordenadas. Para hallar las coordenadas regularmente
llevamos una de las variables a cero, para de esta manera
despejar más fácilmente la segunda.
Por ejemplo, para un x = 0
0,12(0) + 0,2y = 500
0,2y = 500
500/0,2 = y
2500 = y
y para un y = 0
0,12x + 0,2(0) = 500
0,12x = 500
x = 500/0,12
x = 4167
Seguimos con la segunda restricción,
0,15X + 0,1y = 300
0,15X + 0,1y = 300
Tercera restricción,
0,072X + 0,027y = 108
En el siguiente gráfico se muestra el polígono solución de color
gris, en este conjunto es donde cada coordenada cumple con todas las
restricciones, las cuales se caracterizan por ser
restricciones de menor o igual y esta característica se representa
con una flecha hacía abajo.
Una vez se llega a este punto es indispensable saber que las
soluciones óptimas se alojan en los vértices del polígono solución
(color gris) y que identificar a la solución óptima es cuestión de
elegir la mejor alternativa dependiendo de las herramientas
disponibles (tecnológicas y conocimientos matemáticos).
La primera opción es la geométrica, esta depende de trazar la
ecuación que representa a la función objetivo (este paso consiste en
realizar el mismo procedimiento de las restricciones).
Función objetivo,
ZMAX = 4000x + 5000y
luego igualamos a 0.
4000x + 5000y = 0
luego tabulamos para obtener las coordenadas necesarias para esbozar
la gráfica correspondientes a la ecuación (en esta ocasión es
recomendable más de dos coordenadas, incluyendo la coordenada
(x = 0, y = 0).
Una vez se ha esbozado la función objetivo (línea negra) sacamos
replicas paralelas a esta que se encuentren con cada vértice, y solo en
el caso en que la línea imaginaria paralela a la
función objetivo no corte el polígono solución se ha encontrado la
solución óptima. En otras palabras trasladamos la función objetivo por
todo el polígono conservando su forma paralela con
la original, la detenemos en los vértices y evaluamos si esta corta o
no el conjunto solución.
Claramente solo en el punto "B", es decir en el vértice formado por
la intersección de las ecuaciones 1 y 2, la línea imaginaria no corta el
polígono solución, entonces es este punto el
correspondiente a la coordenada óptima.
Para hallar el valor de esta coordenada es indispensable recurrir a
la resolución de ecuaciones lineales 2x2, y se pueden considerar varios
métodos de solución entre ellos:
- Método por sustitución
- Método por igualación
- Método por reducción o Eliminación
- Método por eliminación Gauss
- Método por eliminación Gauss - Jordán
- Método por determinantes
La riqueza de las matemáticas nos deja suficientes alternativas,
para mi gusto el método de reducción o eliminación es muy sencillo de
aplicar.
El método por reducción o eliminación consiste en igualar los
coeficientes de una de las variables multiplicando una o las dos
ecuaciones, teniendo en cuenta que estos coeficientes queden iguales
pero con signos contrarios.
Ecuación 1 0,12x + 0,2y = 500
Ecuación 2 0,15x + 0,1y = 300 multiplicamos por (-2)
Ecuación 3 (2*(-2)) -0,30x - 0,2y = -600
Sumamos 1 y 3 -0,18x = -100
Despejamos "x" x = -100 / (-0,18)
x = 555,55
luego reemplazamos x = 555,55 en cualquiera de las dos ecuaciones originales con el objetivo de despejar "y".
Ecuación 1 0,12x + 0,2y = 500
Reemplazamos "x" 0,12(555,55) + 0,2y = 500
Despejamos "y" 66,666 + 0,2y = 500
0,2y = 500 - 66,666
0,2y = 433,334
y = 433,334 / 0,2
y = 2166,67
De esta forma hemos obtenido los valores para "x" y "y".
Recordemos que x y y fueron los nombres que recibieron las variables originales XT y XT'
x = XT
y = XT'
XT = 555,55
XT' = 2166,67
y la contribución obtenida (reemplazando las variables en la función objetivo) es de:
Zmax = 4000XT + 5000XT'
Zmax = 4000(555,55) + 5000(2166,67)
Zmax = 13.055.550
Ahora podemos cotejar los resultados con los obtenidos mediante resolución por Solver - Excel,
sin embargo recuerden
que el método de búsqueda de la solución óptima en el método gráfico
que utilizamos es el geométrico y que existe una posibilidad mucho más
engorrosa pero igualmente efectiva, este es el método
de iteración por vértice, y que consiste en hallar todas las
coordenadas de los vértices y luego en cada coordenada se evalúa la
función objetivo, (cada coordenada nos proporciona un valor en "x"
y otro en "y", luego reemplazamos estos valores en la función
objetivo "4000x + 5000y = ?" y luego evaluamos los resultados
seleccionando la mayor cantidad).
Una herramienta muy útil al momento de resolver ejercicios mediante
el método gráfico es una calculadora graficadora, como es el caso de la
calculadora de encarta (disponible aquí).
VARIANTES EN EL MÉTODO GRÁFICO
Como en la mayoría de los casos el ejemplo con el que aquí se
explicó el método gráfico es el ideal, es decir un ejercicio de conjunto
acotado con solución óptima única, sin embargo existen una
variedad de problemas diferentes a los ideales y que vale la pena
analizar:
SOLUCIÓN ÓPTIMA MÚLTIPLE
Una de las variantes que puede presentar un ejercicio de programación lineal
consiste en la
cantidad de soluciones óptimas, gran cantidad de ellos presenta más
de una solución óptima, es decir una solución en la cual la función
objetivo es exactamente igual en una combinación
cuantitativa de variables diferente.
Estos problemas deben de afrontarse de tal manera que prime el
análisis de sensibilidad, es decir una vez encontradas múltiples
soluciones iguales se debe proceder al comportamiento del consumo
de los recursos y restricciones, evidentemente prevaleciendo el
concepto de productividad de los recursos más limitados y costosos.
Un ejemplo de este caso es el siguiente:
La ebanistería "SALAZAR LTDA" ha recibido una gran cantidad de
partes prefabricadas para la elaboración de mesas, sin embargo no ha
podido iniciar un plan de producción enfocado a estas por la
alta demanda que tiene de sus productos restantes. Las mesas que
pueden elaborarse de las partes prefabricadas son de dos modelos, modelo
A y B, y estas no requieren más que ser ensambladas y
pintadas. Esta semana se ha determinado dedicar 10 horas de ensamble
y 8 de pintura para elaborar la mayor cantidad de mesas posibles
teniendo en cuenta que cada mesa modelo A requiere de 2 horas
de ensamble y 1 de pintura respectivamente, y que cada mesa modelo B
requiere de 1 hora de ensamble y 2 de pintura respectivamente. Si el
margen de utilidad es de $20000 por cada mesa modelo A y
$10000 por cada mesa modelo B. Determine el modelo adecuado de
producción para esta semana.
X = Cantidad de mesas modelo A a fabricar esta semana
Y = Cantidad de mesas modelo B a fabricar esta semana
Restricciones
2X + Y <= 10 "Horas de ensamble"
X + 2Y <= 8 "Horas de pintura"
X, Y => 0 "De no negatividad"
Función objetivo
Zmax = 20000X + 10000Y
La gráfica resultante sería:
Y = Cantidad de mesas modelo B a fabricar esta semana
Restricciones
2X + Y <= 10 "Horas de ensamble"
X + 2Y <= 8 "Horas de pintura"
X, Y => 0 "De no negatividad"
Función objetivo
Zmax = 20000X + 10000Y
La gráfica resultante sería:
Como nos podemos dar cuenta mediante la geometría en dos vértices la
línea imaginaria perpendicular a la función objetivo no atraviesa el
conjunto solución, por ende en dos puntos se presentan
soluciones óptimas, que son los puntos B y C.
Observemos la solución óptima múltiple
Z(0) = 20000(0) + 10000(0) = 0
Z(A) = 20000(0) + 10000(4) = $40000
Z(B) = 20000(4) + 10000(2) = $100000
Z(C) = 20000(5) + 10000(0) = $100000
Existen entonces dos soluciones óptimas
Solución óptima 1
X = 4 Y = 2
Solución óptima 2
X = 5 Y = 0
La pregunta siguiente es ¿cual decisión tomar?, pues depende de
factores tales como una análisis de sensibilidad donde se tenga en
cuenta el consumo distinto de determinados recursos (horas
ensamble vs. horas pintura) y factores extras al modelo como lo
puede llegar a ser en este caso una necesidad de espacio de
almacenamiento, dado que existe una alternativa en la que se elaboran
más mesas que en la otra, de todas formas es interesante el paso
posterior a esbozar los resultados pues requerirá de la capacidad de
quien toma las decisiones.
SOLUCIÓN ÓPTIMA NO ACOTADA
Otra de las variantes que presentan los modelos de programación lineal
corresponde a los
modelos de solución óptima no acotada, es decir problemas con
infinitas soluciones óptimas. Hay que reconocer que en la vida real gran
parte de estos problemas se deben a un mal planteamiento de
las restricciones, sin embargo es común que este tipo de problemas
sean evaluados en la vida académica.
Un ejemplo:
La compañía comercializadora de bebidas energéticas "CILANTRO
SALVAJE" se encuentra promocionando dos nuevas bebidas, la tipo A y la
tipo B, dado que se encuentran en promoción se puede asegurar
el cubrimiento de cualquier cantidad de demanda, sin embargo existen
2 políticas que la empresa debe tener en cuenta. Una de ellas es que la
cantidad de bebidas tipo A que se vendan no puede ser
menor que las de tipo B, y la segunda es que se deben de vender por
lo menos 1500 bebidas de cualquier tipo.
Dado que se encuentran en promoción el precio de venta de ambas bebidas equivale a $1800 pesos.
Determine la cantidad de unidades que deben venderse!!
Variables
X = Cantidad de bebidas tipo A a vender
Y = Cantidad de bebidas tipo B a vender
Restricciones
X => Y
X + Y => 1500
Función Objetivo
Zmax = 1800X + 1800Y
La gráfica resultante sería:
Es claro que en este ejercicio las variables pueden aumentar
mejorando indefinidamente la función objetivo, en estos casos se dice
que la solución óptima no es acotada, por lo cual las posibles
soluciones son infinitas.
SOLUCIÓN INFACTIBLE
El caso de la solución infactible es más típico de lo pensado, y
corresponde a los casos en los cuales no existen soluciones que cumplen
con todas las restricciones. Es muy común ver este
fenómeno producto de inviables proporciones de oferta y demanda.
Un ejemplo:
La compañía de galletas "CAROLA" desea planificar la producción de
galletas que tendrá que entregar a su cliente en dos semanas, el
contrato indica que la compañía "CAROLA" se compromete a
entregar por lo menos 300 cajas de galletas cualquiera sea su tipo
(presentación D, presentación N o una combinación de ambas
presentaciones), cada caja de galletas presentación D tiene un tiempo
de elaboración de 2 horas, y un tiempo de horneado de 3 horas,
mientras cada caja de presentación N tiene un tiempo de elaboración de 3
horas y un tiempo de horneado de 1 hora. La compañía cuenta
estas dos semanas con 550 horas para elaboración y con 480 horas de
horneado.
Teniendo en cuenta que el margen de utilidad de cada caja de
galletas presentación D y N es de $8500 y $8100 respectivamente,
determine mediante un modelo de programación lineal el plan de
producción que maximice las utilidades.
Variables
X = Cantidad de cajas de galletas presentación D a producir en 2 semanas
Y = Cantidad de cajas de galletas presentación N a producir en 2 semanas
Restricciones
2X + 3Y <= 550
3X + Y <= 480
X + Y => 300
Función Objetivo
Zmax = 8500X + 8100Y
La gráfica resultante es la siguiente:
Evidentemente no existe forma alguna de satisfacer todas las
restricciones, por ende se concluye que no existe solución factible.
REDUNDANTES O SOBRANTES
Existen en los modelos de programación lineal un tipo de
restricciones que no juegan rol alguno en la determinación del conjunto
solución (de igual manera en la solución óptima), lo que lleva a
deducir que estas son redundantes.
Por ejemplo:
La compañía "CONGELADORES MAJO" pretende fabricar dos tipos de
congeladores denominados A y B. Cada uno de ellos debe pasar por tres
operaciones antes de su comercialización: Ensamblaje, pintura
y control de calidad. Los congeladores tipo A requieren 2 horas de
ensamblaje, 3 kg de pintura y 4 horas de control de calidad; los
congeladores tipo B requieren 3 horas de ensamblaje, 6 kg de
pintura y 5 horas de control de calidad. El margen contributivo por
cada congelador tipo A y B es de $102000 y $98000 respectivamente.
La compañía dispone como máximo semanalmente 300 horas de
ensamblaje, 840 kg de pintura y 450 horas de control de calidad. Con
base en la información suministrada determine las unidades a
producir semanalmente de cada referencia para maximizar las
utilidades.
Las variables:
X = Cantidad de congeladores tipo A a producir semanalmente
Y = Cantidad de congeladores tipo B a producir semanalmente
Las restricciones:
2X + 3Y <= 300
3X + 5Y <= 840
4X + 5Y <= 450
Función Objetivo:
Zmax = 102000X + 98000Y
La gráfica resultante es la siguiente,
La solución óptima corresponde a:
X = 150
Y = 0
y la función objetivo quedaría.
Zmax = $15300000
X = 150
Y = 0
y la función objetivo quedaría.
Zmax = $15300000
Claramente podemos observar como la restricción 1 y la restricción 2
no determinan el conjunto solución, por ende se denominan restricciones
redundantes o sobrantes.
No hay comentarios.:
Publicar un comentario