SOLUCION DE PROBLEMAS DE

PROGRAMACION LINEAL POR

EL METODO GRAFICO.
Problema 2:

Un departamento de publicidad tiene que planear para el próximo mes

una estrategia de publicidad para el lanzamiento de una línea de T.V. a
color tiene a consideración 2 medios de difusión: La televisión y el
periódico.
Los estudios de mercado han mostrado que:

1. La publicidad por T.V. Llega al 2 % de las familias de ingresos altos y

al 3 % de las familias de ingresos medios por comercial.
 
2. La publicidad en el periódico llega al 3 % de las familias de ingresos
altos y al 6 % de las familias de ingresos medios por anuncio.
 
La publicidad en periódico tiene un costo de 500 dls. por anuncio y la
publicidad por T.V. tiene un costo de 2000 dls. por comercial. La meta es
obtener al menos una presentación como mínimo al 36 % de las familias
de ingresos altos y al 60 % de las familias de ingresos medios
minimizando los costos de publicidad.
UNILA M. en C. JD PÉREZ NAVEJAS
 

UNILA M. en C. JD PÉREZ NAVEJAS

SOLUCION ÓPTIMA:

UNILA M. en C. JD PÉREZ NAVEJAS

Problema 3:
 

UNILA M. en C. JD PÉREZ NAVEJAS

SOLUCION ÓPTIMA:

UNILA M. en C. JD PÉREZ NAVEJAS

El método gráfico de solución de problemas de programación
lineal (PL) solo aplica a problemas con dos variables de decisión;
sin embargo, ilustra adecuadamente los conceptos que nos
permitirán entender la naturaleza del problema PL y de allí
entender los métodos de solución algebraicos.
Primeramente graficaremos la región factible. Después
ilustraremos el comportamiento de funciones lineales para
entender como determinar los puntos óptimos.
 

UNILA M. en C. JD PÉREZ NAVEJAS

Nuestra primera meta es graficar en el plano la región factible; es decir,
graficar la totalidad de puntos del plano que satisfacen las restricciones.
Notemos que las restricciones se deben cumplir simultáneamente. Es decir,
que los puntos deben cumplir la restricción R1, la restricción R2, y así
sucesivamente hasta la restricción R5. Desde el punto de vista de teoría básica
de conjuntos, la región factible es la intersección de los conjuntos que
satisfacen por separado cada una de las restricciones. Para avanzar en
nuestra meta, debemos saber como determinar los puntos del plano que
satisfacen una desigualdad lineal. Distinguimos dos casos:

o Cuando en la desigualdad solo aparece una variable de decisión (es decir,

la otra variable tiene coeficiente cero).
o Cuando en la desigualdad aparecen las dos variables de decisión (es decir,
ambas tienen coeficientes diferentes de cero en tal desigualdad).
Cuando solo aparece una variable:
En este caso, cuando cambiamos el símbolo de desigualdad por el símbolo de
igualdad lo que obtenemos es el conjunto frontera del conjunto de puntos que
cumple la desigualdad. En este caso, dicha frontera es una línea horizontal o
vertical: por inspección, es fácil determinar el lado de dicha frontera que
cumple la desigualdad.

M. en C. JD PÉREZ NAVEJAS
Cuando aparecen las dos variables:
Nuevamente, cambiamos el símbolo de desigualdad por el símbolo de
igualdad y lo que obtenemos es una línea recta. Esta recta es fácil de graficar
usando la técnica de intersección con los ejes: hacemos cero una de las
variables y despejamos para la otra variable. De nuevo, la recta es la frontera
de nuestro conjunto: por inspección, es fácil determinar el lado de dicha
frontera que cumple la desigualdad.

Problema 4:
Minimizar Z = 3x + 4y 

Sujeta a

3x - 4y ≤ 12, 
x + 2y ≥ 4 
x ≥ 1,   y ≥ 0.
Graficando las ecuaciones de restricción:

UNILA M. en C. JD PÉREZ NAVEJAS

UNILA M. en C. JD PÉREZ NAVEJAS
Aunque no es acotada la región factible, estamos minimizando C = 3x + 4y, cuyos
coeficientes son no negativos. Entonces existe una solución obtenida por el método
más arriba a la izquierda.

La siguiente tabla muestra el valor de C a cada punto de esquina:

Punto C = 3x + 4y

(1, 1.5) 3(1)+4(1.5) = 9  mínimo

(4, 0) 3(4)+4(0) = 12  

Entonces, la solución es x = 1, y = 1.5, que da C = 9 como el valor mínimo.

UNILA M. en C. JD PÉREZ NAVEJAS

Problema 4: de mezcla de productos.
Un fabricante está tratando de decidir sobre las cantidades de
producción para dos artículos: mesas y sillas. Se cuenta con 96
unidades de material y con 72 horas de mano de obra. Cada mesa
requiere 12 unidades de material y 6 horas de mano de obra. Por otra
parte, las sillas usan 8 unidades de material cada una y requieren 12
horas de mano de obra por silla. El margen de contribución es el mismo
para las mesas que para las sillas: $5.00 por unidad. El fabricante
prometió construir por lo menos dos mesas. 
Paso 1: formulación del problema.
El primer paso para resolver el problema es expresarlo en términos
matemáticos en el formato general de PL. ¿Cuál es el objetivo? Es
maximizar la contribución a la ganancia. Cada unidad de mesas o sillas
producidas contribuirá con $5 en la ganancia. Así las dos alternativas
son la producción de mesas y la producción de sillas. Ahora puede
escribirse la función objetivo: 

UNILA M. en C. JD PÉREZ NAVEJAS

Maximizar   Z = 5x1 + 5x2 

En donde:        x1 = número de mesas producidas

                        x2 = número de sillas producidas 

¿Cuáles son las restricciones o limitaciones del problema? Existen tres

restricciones. Primero, el material está limitado a 96 unidades. Cada mesa
se lleva 12 unidades de material y cada silla usa 8 unidades. La primera
restricción es, entonces: 
12x1 + 8x2 £ 96 
La segunda restricción es el total de horas de mano de obra. Una mesa se lleva 6
horas, una silla 12 horas y se dispone de un total de 72 horas. Así: 
6x1 + 12x2 £ 72 
Existe una limitación más. El fabricante prometió producir por lo menos dos
mesas. Esto puede expresarse como:
x1 ³ 2 
Por último, las restricciones de no negatividad son: 
UNILA x1 ³ 0,  x2 ³ 0  M. en C. JD PÉREZ NAVEJAS
Poniendo todo junto el modelo se tiene: 

                                               Maximizar    Z = 5x1 + 5x2

                                               Restricciones: 12x1 + 8x2 £ 96

                                                                       6x1 + 12x2 £ 72

                                                                       x1 ³ 2

                                                                       x1 ³ 0,  x2 ³ 0
 Paso 2: gráfica de las restricciones.

El siguiente paso en el método gráfico es dibujar todas las restricciones

en una gráfica. Esto puede hacerse en cualquier orden. Por conveniencia
se comenzará con las restricciones de no negatividad. Éstas se muestran
en la siguiente figura: 

UNILA M. en C. JD PÉREZ NAVEJAS

 En esta gráfica, una solución se representaría por un punto con
coordenadas x1 (mesas) y x2 (sillas). Las coordenadas representarían las
cantidades de cada artículo que se deben producir. El cuadrante superior
derecho se llama Región Factible puesto que es el único cuadrante en
que pueden estar las soluciones. Los otros tres cuadrantes no son
factibles, ya que requerirían la producción de cantidades negativas de
mesas o de sillas o de ambas. 

UNILA M. en C. JD PÉREZ NAVEJAS

La siguiente restricción es  x1 ³ 2. La manera más sencilla de dibujar las
restricciones de recursos es en dos pasos: (1) convertir una desigualdad
en una ecuación y graficar la ecuación y (2) sombrear el área apropiada
arriba y abajo de la línea que resulta en el paso 1. Convertir una igualdad
en una ecuación aquí significa ignorar la parte de “mayor que” o “menor
que” de la restricción. 
Así, en el ejemplo, x1 ³ 2 se convierte en x1 = 2. Esta ecuación está trazada
en la siguiente figura: 

UNILA M. en C. JD PÉREZ NAVEJAS

 Cualquier punto en la línea x1 = 2 satisface la ecuación. Sin embargo, la
restricción es más amplia, ya que cualquier punto x1 > 2 también la
cumplirá. Esto incluye todos los puntos que están a la derecha de la línea
x1 = 2. Entonces, la región factible incluye todos los valores de x1 que
están sobre o a la derecha de la línea x1 = 2. 
La limitación sobre las horas de mano de obra es la siguiente restricción.
Como antes, primero se convierte en una ecuación: 6x1 + 12x2 = 72. Puede
graficarse esta línea si se encuentran dos puntos sobre ella. El par de
puntos más sencillos de localizar son las intersecciones con los ejes X1 y
X2. Para encontrar la intersección con el eje X2 se hace x1 = 0. La ecuación
se reduce, entonces, a: 
12x2 = 72
    x2 =   6 
La intersección con el eje X1 se encuentra haciendo x2 = 0. Así: 
6x1 = 72
  x1 = 12 
Estos dos puntos y la línea que los une se muestran en la siguiente
figura: 

UNILA M. en C. JD PÉREZ NAVEJAS

 Cualquier punto que está sobre o abajo de esta línea cumplirá con la
restricción. Cualquier punto arriba de esta línea requerirá más de 72 horas
de mano de obra y no es aceptable. En la siguiente figura se combina esta
restricción con la anterior. En la región factible, ambas restricciones se
cumplen. 

UNILA M. en C. JD PÉREZ NAVEJAS

 La última restricción es la de material. Siguiendo el procedimiento
anterior, primero se encuentran las intersecciones para la igualdad. Éstas
son x1 = 0, x2 = 12 y x1 = 8, x2 =0. Se localizan los dos puntos en la gráfica;
se traza la línea, y como la restricción es del tipo menor o igual que, se
sombrea el área que está abajo de la línea. El resultado se muestra en la
siguiente figura: 

UNILA M. en C. JD PÉREZ NAVEJAS

Cualquier solución que esté en la frontera o dentro del área sombreada
cumplirá con todas las restricciones. Ahora se utilizará la función
objetivo para seleccionar la solución óptima. 

UNILA M. en C. JD PÉREZ NAVEJAS

Pasó 3: obtención de la solución óptima: líneas de indiferencia.

Para encontrar la solución óptima, se grafica la función objetivo en la

misma gráfica de las restricciones. La función objetivo en este problema
es Z = 5x1 + 5x2. Como todavía no se conoce el máximo valor factible de Z,
no puede trazarse el óptimo de la función objetivo. No obstante, es
posible suponer algunos valores para Z y graficar las líneas resultantes.
En la siguiente figura se muestran las líneas para Z = 25 y Z = 50: 

UNILA M. en C. JD PÉREZ NAVEJAS

Las líneas de este tipo se llaman líneas de indiferencia, porque cualquier
punto sobre una línea dada da la misma ganancia total. Nótese que la
distancia perpendicular del origen a la línea aumenta al aumentar el valor
de Z. También, todas las líneas de indiferencia son paralelas entre sí.
Estas propiedades gráficas pueden usarse para resolver el problema. 
En la siguiente figura, se ilustran todas las restricciones y las dos líneas
de indiferencia supuestas. En la gráfica puede observarse que la línea de
indiferencia para Z = 50 está completamente fuera de la región factible.
Para Z = 25, parte de la línea cae dentro de la región factible. Por tanto,
existe alguna combinación de x1 y x2 que satisface todas las restricciones
y da una ganancia total de $25. Por inspección, puede observarse que
hay ganancias más altas que son factibles. 

UNILA
Imaginando que la línea de indiferencia Z = 25 se mueve hacia la línea Z =
50, de las propiedades de la gráfica que se hicieron notar antes, el punto
óptimo estará sobre la línea de indiferencia más lejana al origen pero que
todavía toque la región factible. Esto se muestra en la siguiente figura:

Con el punto óptimo localizado gráficamente, la única tarea que queda es

encontrar las coordenadas del punto. Nótese que el punto óptimo está en
la intersección de las líneas de restricción para materiales y horas de
mano de obra. Las coordenadas de este punto se pueden encontrar
resolviendo el sistema de ecuaciones que forman estas dos restricciones
utilizando cualquiera de los métodos de solución (suma y resta,
sustitución o igualación).
UNILA M. en C. JD PÉREZ NAVEJAS
Las coordenadas de este punto resultan ser (6, 3). La sustitución de este
punto en la función objetivo da la ganancia máxima: 

Z = 5(6) + 5(3) = $45

 Resumen del método gráfico.

Para resolver gráficamente problemas de programación lineal:

1.   Exprésense los datos del problema como una función objetivo y
restricciones.

2.   Grafíquese cada restricción.

3.   Localícese la solución óptima. 

UNILA M. en C. JD PÉREZ NAVEJAS

Uso del método gráfico para minimización.

Consideremos un Problema de PL en el cual el objetivo es minimizar

costos. La solución del problema de minimización sigue el mismo
procedimiento que la de problemas de maximización. La única diferencia
es que ahora se quiere el menor valor posible para la función objetivo.
Supóngase que se tiene el siguiente problema: 

Problema 5: de dieta.
Un comprador está tratando de seleccionar la combinación más barata de
dos alimentos, que debe cumplir con ciertas necesidades diarias de
vitaminas. Los requerimientos vitamínicos son por lo menos 40 unidades
de vitamina W, 50 unidades de vitamina X y 49 unidades de vitamina Y.
Cada onza del alimento A proporciona 4 unidades de vitamina W, 10
unidades de vitamina X y 7 unidades de vitamina Y; cada onza del alimento
B proporciona 10 unidades de W, 5 unidades de X y 7 unidades de Y. El
alimento A cuesta 5 pesos/kilogramo y el alimento B cuesta 8
pesos/kilogramo. 

UNILA M. en C. JD PÉREZ NAVEJAS

Paso 1: formulación del problema.
La meta en este problema es encontrar la manera menos costosa para
satisfacer las necesidades vitamínicas. Las dos alternativas disponibles
son los alimentos A y B. Matemáticamente la función objetivo es: 

Minimizar   Z = 5A + 8B 
Las restricciones son los requerimientos mínimos de las tres vitaminas.
Éstas se muestran enseguida: 

Restricciones:   4A + 10B ³ 40  vitamina W

                                   10A + 5B ³ 50  vitamina X
                                   7A + 7B ³ 49  vitamina Y
                                   A ³ 0,  B ³ 0  no negatividad 

UNILA M. en C. JD PÉREZ NAVEJAS

Paso 2: gráfica de las restricciones.
El procedimiento para graficar es el mismo que se usó antes: (1) graficar
cada ecuación de restricción; (2) graficar el área apropiada. Para la
primera restricción la ecuación es 4A + 10B = 40. Las dos intersecciones
con los ejes son (0,4) y (10,0). Esta línea se muestra en la siguiente
figura: 

La restricción pide 40 unidades o más de la vitamina W. Cualquier punto

que esté arriba de la línea de restricción será factible y todos los puntos
que quedan abajo de esa línea serán aceptables. En la siguiente figura se
muestra la región factible: 
 Después se grafica la restricción para la vitamina X. La ecuación 10A + 5B
= 50 tiene intersecciones con los ejes en (0,10) y (5,0). En la siguiente
figura se ilustran las restricciones para las vitaminas W y X. Nótese que
las soluciones que quedan en las áreas a o b no son factibles, ya que
quedarían abajo de las líneas de restricción. 
UNILA M. en C. JD PÉREZ NAVEJAS
 Al agregar la tercera restricción, este segundo paso queda terminado,
como se muestra en la siguiente figura: 

UNILA M. en C. JD PÉREZ NAVEJAS

 Paso 3: localización de la solución óptima.

En la siguiente figura se muestra la frontera extrema más dos líneas de

indiferencia, las de Z = 40 pesos y Z = 60 pesos. La frontera extrema está
formada por los puntos a, b, c y d, puesto que éstos son los puntos de
intersección factibles más cercanos al origen. 
Gráficamente, el objetivo de minimizar el valor de Z significa ajustar una
línea de indiferencia tan cerca del origen como sea posible. En la figura
anterior puede observarse que existen muchas soluciones posibles para
Z = 60, pero ninguna para Z = 40. Imaginando mover la línea Z = 60 hacia
el origen, el último punto de contacto con la frontera extrema será el
punto b. Entonces, el punto b es la solución óptima. En la figura anterior
se observa que el punto b es la intersección de dos líneas: 

UNILA M. en C. JD PÉREZ NAVEJAS

 (1)  4A + 10B = 40
(2)  7A +   7B = 49 

Resolviendo el sistema de ecuaciones:

Multiplíquese la ecuación (1) por 7:                               

                                                                    
   (3)     28A + 70B =   280
Multiplíquese la ecuación (2) por – 4:          (4)   –28A – 28B = –196
42B =  84

                                                                                                B =  2

Sustitúyase B = 2 en la ecuación (1):            4A + 10(2) =  40

                                                                          A =  5 

UNILA M. en C. JD PÉREZ NAVEJAS

La solución menos costosa es 5 kilogramos de alimento A y 2 kilogramos
de alimento B. El costo total de esta combinación es:
Z = 5A + 8B = 5(5) + 8(2) = 25 + 16 = 41 pesos
Si se usa el método de prueba y error para localizar la solución óptima, se
deben encontrar las coordenadas de los puntos a, b, c, y d. Se debe
calcular después el valor de la función objetivo para cada punto. A
continuación se muestran los resultados de este procedimiento: 

Resultados de prueba y error

Punto Coordenadas Z = 5A + 8B
a A = 10, B = 0 50
b A = 5, B = 2 41 menor
c A =3, B = 4 47
d A = 0, B = 10 80

UNILA M. en C. JD PÉREZ NAVEJAS

Problema 6. Una compañía posee dos minas: la mina A produce cada día
1 tonelada de hierro de alta calidad, 3 toneladas de calidad media y 5 de baja
calidad. La mina B produce cada día 2 toneladas de cada una de las tres
calidades. La compañía necesita al menos 80 toneladas de mineral de alta calidad,
160 toneladas de calidad media y 200 de baja calidad. Sabiendo que el coste
diario de la operación es de 2000 euros en cada mina ¿cuántos días debe trabajar
cada mina  para que el coste sea mínimo?

Solución
Organizamos los datos en una tabla:

  días Alta calidad Calidad media Baja calidad Coste diario

Mina A x 1x 3x 5x 2000x
Mina B y 2y 2y 2y 2000y
    80 160 200  

UNILA M. en C. JD PÉREZ NAVEJAS

 

UNILA M. en C. JD PÉREZ NAVEJAS

Los vértices son los puntos A (0, 100), B (20, 50), C (40, 20), D (80, 0), que se
encuentran al resolver el sistema que determinan dos a dos las rectas auxiliares
(y que estén dentro de la región factible).

UNILA M. en C. JD PÉREZ NAVEJAS

 

UNILA M. en C. JD PÉREZ NAVEJAS

Problema 7. En una pastelería se hacen dos tipos de tartas: Vienesa y
Real. Cada tarta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y
produce un beneficio de 250 Pts, mientras que una tarta Real necesita medio Kg.
de relleno por cada Kg. de bizcocho y produce 400 Ptas. de beneficio. En la
pastelería se pueden hacer diariamente hasta 150 Kg. de bizcocho y 50 Kg. de
relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tartas
de cada tipo. ¿Cuántas tartas Vienesas y cuantas Reales deben vender al día para
que sea máximo el beneficio?

Solución
En primer lugar hacemos una tabla para organizar los datos:

Tipo Nº Bizcocho Relleno Beneficio

T. Vienesa x 1.x 0,250x 250x
T. Real y 1.y 0,500y 400y
    150 50  

UNILA M. en C. JD PÉREZ NAVEJAS

 

x Y x Y
0 100 0 150
200 0 150 0

UNILA M. en C. JD PÉREZ NAVEJAS

Las otras dos son paralelas a los ejes

Al eje OY :   x=125 Al eje OX:      y =125

Y las otras restricciones (x e y mayor o igual a cero) nos indican que las
soluciones deben estar en el primer cuadrante .

La región factible la hemos coloreado de amarillo:

UNILA M. en C. JD PÉREZ NAVEJAS

 

UNILA M. en C. JD PÉREZ NAVEJAS

 

x Y
0 0
200 -125
Se ve gráficamente que la solución es el punto (100, 50), ya que es el vértice más
alejado (el último que nos encontramos al desplazar la rectas 250x+400y=0)

Lo comprobamos con el método analítico, es decir usando el teorema que dice

que si existe solución única debe hallarse en uno de los vértices.
La función objetivo era: f(x, y)=250x+400y, sustituyendo en los vértices
obtenemos:

f(125,0)=250(125)+400(0)=31250.
f(125,25)=250(125)+400(25)=31250+10000=41250.
f(100,50)=250(100)+400(50)=25000+20000=45000.
f(0,100)=250(0)+400(100)=40000.

El máximo beneficio es 45000 y se obtiene en el punto (100, 50)

Conclusión: se tienen que vender 100 tartas vienesas y 50

tartas reales.

UNILA M. en C. JD PÉREZ NAVEJAS

Problema 8. Disponemos de 210.000 euros para invertir en la Bolsa de
Valores. Nos recomiendan dos tipos de acciones. Las del tipo A, que rinden el
10% y las del tipo B, que rinden el 8%. Decidimos invertir un máximo de 130.000
euros en las del tipo A y como mínimo 60.000 en las del tipo B. Además queremos
que la inversión en las del tipo A sea menor que el doble de la inversión en B.
¿Cuál tiene que ser la distribución de la inversión para obtener el máximo interés
anual?

Solución
Es un problema de programación lineal.

Llamamos x a la cantidad que invertimos en acciones de tipo A

Llamamos y a la cantidad que invertimos en acciones de tipo B

  inversión rendimiento

Tipo A x 0,1x

Tipo B y 0,08y

UNILA M. en C. JD PÉREZ NAVEJAS

 

UNILA M. en C. JD PÉREZ NAVEJAS

 r1                                           r2 (paralela a OY)          r3 (paralela a OX)                r4
x y x y X y x y

0 210000 130000 0 0 60000 0 0

210000 0        
130000 65000

La región factible es la pintada de amarillo, de vértices A, B, C, D y E

 

UNILA M. en C. JD PÉREZ NAVEJAS