Habiéndose definido previamente el problema, se formula el modelo matemático, su procedimiento
se ha demostrado en la Unidad 1 anterior. El modelo obtenido estará listo para aplicar los diversos
métodos de solución, los cuales permitirán determinar el valor de las variables de decisión y la
función objetivo. Los métodos de solución que trataremos en la Unidad 2 son los siguientes:
?
?
?
?
Método gráfico
Método algebraico
Método Simplex, y
Solución del modelo asistido por computadora
1.1.
El método gráfico. Procedimiento y aplicación
Se aplica cuando tenemos un modelo matemático de Programación Lineal con dos variables
solamente y cualquier número de restricciones (la función objetivo y restricciones son funciones
lineales). Los pasos a seguir para hallar la solución gráfica son los siguientes:
a) Representar gráficamente las restricciones del modelo, ubicando los puntos de intersección
con los ejes x e y ó x1 y x2.
b) Unir los puntos de intersección en los ejes o coordenadas con una recta para cada restricción
del modelo.
c) Ubicar todos los puntos de intersección que se generan en el cruce de las rectas de cada
restricción graficadas en el plano.
d) Determinar el espacio de soluciones, que define las soluciones factibles que satisfacen las
restricciones.
e) Determinar la solución óptima probando todos los puntos de intersección en el espacio de
soluciones factibles.
Una solución óptima de Maximización (utilidades) o Minimización (costos), se encuentra siempre
en uno de los vértices o puntos de esquina del conjunto de soluciones factibles, formado por la
intersección de las líneas de restricción.
Solución factible, es la solución que satisface las restricciones del modelo y cumple con las
restricciones de no negatividad. Un modelo matemático de programación lineal tiene varias
soluciones factibles.
Solución óptima, es una solución factible que optimiza la
función objetivo, maximizándolo o minimizándolo según el
modelo matemático.
El método gráfico, es la base para el desarrollo y
entendimiento del método algebraico y del método simplex.
Las iteraciones en el desarrollo del algoritmo van mostrando
las soluciones factibles, hasta llegar a la solución óptima.
Aplicación del método gráfico
Presentamos problemas para mostrar la aplicación,
análisis e interpretación del método gráfico:
1). Problema: La Compañía WG produce artículos de vidrio de alta calidad, incluyendo ventanas y
puertas de vidrio. La compañía tiene tres plantas. Los marcos y molduras de aluminio se hacen en
la planta 1, los marcos de madera se realizan en la planta 2 y en la planta 3 se produce el vidrio y se
ensamblan los productos. La gerencia ha decidido reorganizar la línea de producción. Se va
emprender la fabricación de dos productos nuevos que han tenido demanda. El producto A es una
puerta de vidrio con marco de aluminio. El producto B es una ventana grande para vidrio doble con
marco de madera. El departamento de mercadotecnia indica que la compañía tiene mercado para
vender la producción de cualquiera de los productos. Ambos productos compiten por la misma
capacidad de producción en la planta 3. Se determinó la capacidad de producción en cada planta
que estará disponible para los productos A y B, el porcentaje de esta capacidad que requiere cada
unidad producida y la ganancia unitaria semanal por cada producto. La información se resume en
la siguiente tabla:
Determinar la producción de puertas y ventanas de vidrio que permita optimizar las ganancias por
la venta semanal de los productos. Hallar la solución del problema aplicando el método gráfico.
Esquematización y Formulación del modelo matemático de PL
Para hallar la solución del problema primero esquematizamos el problema
Características del producto:
Producto A = puerta de vidrio con marco de aluminio.
Producto B = ventana grande para vidrio doble con marco de madera.
?
?
Definición de las variables de decisión:
x1 = número de lotes del producto A fabricados por semana
x2 = número de lotes del producto B fabricados por semana
Definición de la Función objetivo:
Z = ganancia total semanal (en miles de $) por elaborar los dos productos.
Optimizar las ganancias significa maximizar la función objetivo
Maximizar: Z = 3 x1 + 5 x2
Capacidad 4
Capacidad 12
PLANTA 2
MP “A”
MP “B”
Producto “A”
Producto “B”
PLANTA 1
PLANTA 3
Capacidad 18
?
Definición de las restricciones:
restricciones
de
capacidad
Solo tenemos
disponible por planta
Planta
2:
Planta 1:
2 x1 = 12
Planta 3:
x1 = 4 ;
y
3 x1 + 2 x2 = 18
Luego el modelo matemático de programación
lineal del problema será:
Maximizar: Z = 3 x1 + 5 x2
Sujeto a:
x1 = 4
2 x1 = 12
3 x1 + 2 x2 = 18
x1, x2 > 0
Solución del modelo con el método gráfico:
Como el problema tiene sólo dos variables de decisión, o sea dos dimensiones, se puede usar el
método gráfico para hallar la solución. Este procedimiento incluye la construcción de una gráfica de
dos dimensiones con x1 y x2 en los ejes.
El primer paso es dibujar en el plano cartesiano x1 x2 cada una de las rectas que limitan los valores
permitidos por cada restricción.
Las restricciones de no negatividad x1 = 0 y x2 = 0 exigen que el punto (x1, x2) se encuentre en el
lado positivo de los ejes, es decir, en el primer cuadrante.
Observamos que la restricción x1 = 4 significa que (x1, x2) no puede estar a la derecha de la recta x1 =
4. Estos resultados se muestran en la figura 2.1, el área sombreada contiene los únicos valores de
(x1, x2) permitidos.
Figura 2.1
De igual manera, la restricción 2 x2 = 12 (equivalente a x2 = 6) implica que la recta 2 x2 = 12 cruza
la recta x1 = 4 en el punto (4, 6) formando una nueva área sombreada cuando se grafica las
restricciones, como se muestra en la figura 2.2.
Figura 2.2
La restricción: 3 x1 + 2 x2 = 18, se encuentra al graficar los puntos (x1, x2) de la recta 3 x1 + 2 x2 = 18
; haciendo en la recta x1 = 0 hallamos el punto (0, 9); y haciendo x2 = 0 hallamos el punto (6, 0).
El gráfico de la recta 3 x1 + 2 x2 = 18 cruza a los dos rectas anteriores en los puntos (4, 3) y (2, 6)
tal como se muestra en la figura 2.2.
Para el punto (4, 0),
reemplazamos en:
Z = 3 x1 + 5 x2
,
obtenemos:
Para el punto (4, 3),
Z = 3 x1 + 5 x2 , obtenemos:
Z = 3 (4) + 5 (0) = 12
reemplazamos en:
Z = 3 (4) + 5 (3) = 27
Para el punto (2, 6), reemplazamos en:
Z = 3 (2) + 5 (6) = 36
Para el punto (0, 6),
reemplazamos en:
Z = 3 (0) + 5 (6) = 30
Para el punto (0, 0), obtenemos:
Z =0
Tomamos un punto cualquiera dentro del polígono (región factible), por ejemplo el punto (3, 4),
reemplazamos en Z y obtenemos Z = 29
Solución del problema: La solución óptima será aquel valor que maximiza la función objetivo
del modelo. Por tanto, el valor máximo de la función objetivo “Z” se encuentra en el punto (2, 6);
x1 = 2, y x2 = 6; con el cual se obtiene un Z = 36
entonces la solución del problema es:
(máximo).
Interpretando la respuesta de acuerdo al problema, se debe tomar la decisión de producir
semanalmente 2 puertas de vidrio con marco de aluminio y 6 ventanas grande para vidrio doble,
los cuales generan una ganancia semanal de 36,000 $ por la venta de los dos productos.
Se demuestra también que la solución óptima del modelo matemático se encuentra solamente en
uno de los vértices del polígono. Además, podemos advertir que una mala formulación de la
función objetivo del modelo nos puede llevar a tomar una decisión equivocada, lo cual aplicado a la
gestión empresarial puede generar graves consecuencias.
2). Problema: La empresa BGC fabrica camisas para caballeros y blusas para damas y para el
almacén de la empresa. El proceso de producción incluye: corte, costura y empacado. La empresa
emplea 25 trabajadores en el departamento de corte, 35 en el departamento de costura y 5 en el
departamento de empacado. La fábrica trabaja un turno de 8 horas diarias, y sólo 5 días a la
semana. La siguiente tabla proporciona los requerimientos de tiempo y la utilidad por unidad para
las dos prendas.
Determine el programa de producción semanal óptimo para la empresa.
?
Definición de variables de decisión
x1 = Cantidad de camisas para caballeros a fabricarse semanalmente.
x2 = Cantidad de blusas para damas a fabricarse semanalmente.
El proceso de formulación del modelo matemático de programación lineal fue desarrollado en la
Unidad 1.
?
Formulación del modelo de PL
Tiempo disponible por Proceso de Corte:
Maximizar: Z = 2.50 x1 + 3.20 x2
Sujeto a:
20 x1 + 60 x2 < 60,000
70 x1 + 60 x2 < 84,000
12 x1 + 4 x2 < 12,000
x1, x2 > 0
?
Solución del modelo con el método gráfico
Primero se procede a graficar las restricciones del modelo, determinamos los puntos de
intersección en las coordenadas (x1, x2), y obtenemos los siguientes valores que se muestran en el
gráfico de la figura 2.3:
Primera restricción:
20 x1 + 60 x2 < 60,000
Si x1 = 0, entonces x2 = 1000; se obtiene el punto A (0, 1000)
Si x2 = 0, entonces x1 = 3000; se obtiene el punto B (3000, 0)
Segunda restricción:
70 x1 + 60 x2 < 84,000
Se obtiene los puntos
E (0, 1400)
;
F (1200, 0)
Tercera restricción:
12 x1 + 4 x2 < 12,000
Se obtiene los puntos
H (0, 3000)
;
I (1000, 0)
(0, 3000)
Figura 2.3
(0, 1400)
(0, 1000)
(1200, 0)
(3000, 0)
(3000, 0)
Al graficar las restricciones y la condición de no negatividad del modelo, se limita un área
sombreada formándose un polígono irregular, en donde se encuentran las soluciones factibles.
Seguidamente desarrollamos el procedimiento reemplazando todos los puntos O, A, C, G, I; que
forman los vértices del polígono (región factible) en la función objetivo: Z = 2.50 x1 + 3.20 x2; y
obtenemos los siguientes resultados:
Solución del problema
La solución óptima será aquel valor que maximiza la función objetivo del modelo. Luego la solución
del problema es el valor máximo de Z, el cual se encuentra en el punto C (480, 840).
Entonces la solución del problema es: x1 = 480, y x2 = 840. Con el cual se obtiene un valor de Z =
3,888 $ (utilidad total).
También podemos indicar en la figura 2.3 que los puntos O, A, G, e I son soluciones factibles y el
punto C es la solución óptima del modelo.
Interpretando de acuerdo al enunciado del problema, se concluye que para maximizar la
utilidad de la empresa BGC, debe producir semanalmente 480 camisas para caballeros y 840
blusas para damas; lo cual le va generar una utilidad semanal de $ 3,888.00.
1.2.
Aplicación del método algebraico
El método algebraico complementa al método gráfico en la solución del modelo, se determina
resolviendo como ecuaciones simultáneas las restricciones del modelo, de dos en dos, para hallar el
punto de intersección de las rectas.
Aplicamos el método algebraico en la solución del problema 2). Tomamos las restricciones del
modelo y lo expresamos como ecuaciones, luego procedemos a desarrollar:
20 x1 + 60 x2 = 60,000
70 x1 + 60 x2 = 84,000
………. (1)
………. (2)
12 x1 + 4 x2 = 12,000………. (3)
Hallamos la solución simultánea de las ecuaciones (1) y (2); se multiplica por (-1) la ecuación (1)
para eliminar la variable x2 y hallar la variable x1.
– 20 x1 – 60 x2 = – 60,000
70 x1 + 60 x2 = 84,000
50 x1 + 0
= 24,000
x1 = 480;
Luego remplazando x1 en la ecuación (1) ó (2) se obtiene x2 = 840
Significa que las ecuaciones (1) y (2) se interceptan en el punto (480, 840).
De igual manera se procede para desarrollar las ecuaciones simultáneas (1) y (3); y las ecuaciones
(2) y (3) y obtenemos los puntos de intersección de las rectas, que en conjunto forman el espacio de
soluciones factibles. Luego se reemplazan los valores obtenidos de las variables (x1, x2) en cada
punto de intersección en la función objetivo, y obtenemos valores similares como se muestra en la
tabla 2.1.
El grafico de las restricciones permite visualizar el espacio de soluciones para hallar las
soluciones factibles del modelo y determinar la solución óptima.
3). Problema: La fábrica de muebles “La Moderna” produce dos modelos de muebles: Virginia y
Mónaco; utilizando dos procesos, de construcción y pintado. La utilidad unitaria del modelo
Virginia es de $ 200 y del modelo Mónaco es de $ 240. La tabla siguiente, proporciona los datos
básicos del problema.
PROCESOS
Tiempo de fabricación por modelo
Capacidad horaria
disponible
Construcción
Pintado
Modelo Virginia
6
8
Modelo Virginia
12
4
Modelo Mónaco
120
64
Con la información indicada se pide determinar la producción de muebles que optimice las
utilidades de la fábrica.
?
?
Variables de decisión
x1 = Cantidad a producir de muebles modelo Virginia.
x2 = Cantidad a producir de muebles modelo Mónaco.
Modelo matemático de PL
Maximizar: Z = 200 x1 + 240 x2
Sujeto a:
6 x1 + 12 x2 < 120
8 x1 + 4 x2 < 64
x1, x2 > 0
Solución con el método algebraico
Tomamos las restricciones del modelo y lo expresamos como ecuaciones, luego procedemos a
desarrollar:
6 x1 + 12 x2 = 120
8 x1 + 4 x2 = 64
………. (1)
………. (2)
Hallamos la solución simultánea de las ecuaciones (1) y (2); se divide entre (-3) la ecuación (1) para
eliminar la variable x2 y hallar la variable x1 .
-2 x1 – 4 x2 = -40
8 x1 + 4 x2 = 64_ .
6 x1 + 0
= 24
x1 = 4 ;
Luego remplazando x1 en la ecuación (1) ó (2) se obtiene x2 = 8
Significa que las ecuaciones (1) y (2) se interceptan en el punto (4, 8). Además, haciendo igual a
cero cada uno de las variables en las restricciones obtenemos el punto de intersección con las
coordenadas x1 y x2.
Solución del modelo con el método gráfico
Se determinan los puntos de intersección en las coordenadas (x1, x2), y obtenemos los siguientes
valores que se muestran en el gráfico de la figura 2.4
Primera restricción:
6 x1 + 12 x2 = 120
Si x1 = 0, entonces x2 = 10;
Si x2 = 0, entonces x1 = 20;
se obtiene el punto A (0, 10)
se obtiene el punto B (20, 0)
;
Segunda restricción:
8 x1 + 4 x2 = 64
Se obtiene los puntos: E (0, 16)
x2
F (8, 0)
Figura 2.4
(0, 10)
(4, 8) Solución óptima
(0, 0)
(8, 0)
x1
Seguidamente reemplazamos en la función objetivo: Z = 200 x1 + 240 x2; todos los puntos O, A,
C, E; que forman los vértices del polígono y obtenemos:
Las soluciones factibles se encuentran al graficar las restricciones y la condición de no negatividad
del modelo, formándose un polígono irregular.
Solución e interpretación del problema
La solución óptima será aquel valor que maximiza la función objetivo del modelo. Luego la solución
del problema es el valor máximo de Z, el cual se encuentra en el punto C (4, 8). Entonces la
solución del problema es: x1 = 4, y x2 = 8. Con el cual se obtiene un valor de Z = 2,720 $ (utilidad
total).
También podemos indicar en la figura 2.4 que los puntos O, A, E son soluciones factibles y el punto
C es la solución óptima del modelo.
Interpretando, se concluye que para optimizar la utilidad de la Fábrica de Muebles “La
Moderna” se debe producir 4 muebles modelo Virginia y 8 muebles modelo Mónaco, lo cual va
generar una utilidad de $ 2,720.
4) Problema: La empresa MIKY produce dos calidades de pinturas: para interiores y para
exteriores; a partir de dos tipos de materias primas: M1 y M2. El consumo de materia prima por
producto y su disponibilidad diaria en toneladas de MP, se muestra en el cuadro siguiente:
Tipo materia prima
Pintura exterior
Pintura interior
Disponibilidad MP
Materia prima M1
Materia prima M2
6
1
4
2
24
6
La utilidad diaria (en miles de $) de la pintura para exteriores es de 5 $, y de la pintura para
interiores es de 4 $ por tonelada de pintura respectivamente. El estudio de mercado indica que la
demanda máxima de pinturas para interiores es de 2 ton. Además, la demanda de pinturas para
interiores no puede exceder a las pinturas para exteriores en 1 ton. La empresa MIKY desea hallar
un modelo matemático que optimice la mezcla de productos, con el objeto de maximizar la utilidad
diaria total.
Definición de las variables de decisión
x1 = Toneladas diarias de producción de pinturas para exteriores
x2 = Toneladas diarias de producción de pinturas para interiores
La función objetivos del modelo es maximizar la utilidad diaria total de la producción de pinturas
para exteriores e interiores (en miles de $).
Luego el Modelo matemático de Programación Lineal será:
Maximizar:
Sujeto a:
Z = 5 x1 + 4 x2
6 x1 + 4 x2 < 24
x1 + 2 x2 < 6
– x1 +
x2 < 1
x2 < 2
x1, x2 = 0
Tenemos un modelo matemático PL de dos variables con cuatro restricciones.
La solución óptima del modelo matemático de PL es:
x1 = 3.0 toneladas diarias de producción de pinturas para exteriores
x2 = 1.5 toneladas diarias de producción de pinturas para interiores
Z = 21,000 $ (utilidad total máxima diaria, determinado en la función objetivo)