Mdulo: II Unidad: I Semana: 2
PROGRAMACIN LINEAL
Alejandro Chambergo
Ejemplos de la Programacin Lineal
Un problema de minimizacin
Dorian Auto fabrica y vende coches y
furgonetas.La empresa quiere emprender una
campaa publicitaria en TV y tiene que decidir
comprar los tiempos de anuncios en dos tipos
de programas: telenovelas y ftbol.
Cada anuncio del programa telenovelas es visto por 6 millones de mujeres y 2
millones de hombres.
Cada partido de ftbol es visto por 3 millones de mujeres y 8 millones de hombres.
Un anuncio en el programa telenovelas cuesta 50.000 y un anuncio del ftbol
cuesta 100.000 .
Dorian Auto quisiera que los anuncios sean vistos por lo menos 30 millones de
mujeres y 24 millones de hombres.
Dorian Auto quiere saber cuntos anuncios debe contratar en cada tipo de
programa para que el coste de la campaa publicitaria sea mnimo.
Formulacin del problema:
Cada anuncio del programa
telenovela es visto por 6 millones de
mujeres y 2 millones de hombres. Corazn Ftbol
Cada partido de ftbol es visto por 3
millones de mujeres y 8 millones de (x) (y)
hombres.
Un anuncio en el programa de mujeres 6 3 6x + 3y 30
telenovela cuesta 50.000 y un
anuncio del ftbol cuesta 100.000 .
Dorian Auto quisiera que los
anuncios sean vistos por lo menos 30 hombres 2 8 2x + 8y 24
millones de mujeres y 24 millones de
hombres. Costo
Dorian Auto quiere saber cuntos 50 100 50x +100y
anuncios debe contratar en cada tipo 1.000
de programa para que el costo de la
campaa publicitaria sea mnimo.
Formulacin del problema:
Variables de decisin: x = n de anuncios en telenovelas
y = n de anuncios en ftbol
Min z = 50x + 100y (funcin objetivo en 1.000 )
s.a: 6x + 3y 30 (mujeres)
2x + 8y 24 (hombres)
x, y 0 (no negatividad)
Dibujamos la regin factible.
Y
14
Min z = 50 x + 100y 12
6x + 3y = 30
s.a. 6x + 3y 30
10
2x + 8y 24
x, y 0 8
4
2x + 8y = 24
2
X
2 4 6 8 10 12 14
Calculamos los vrtices de la regin factible:
La regin factible
Y
El vrtice A es solucin del no est acotada
sistema 14
6x + 3y = 30
x=0 12
Por tanto, A(0, 10)
10 A
Regin
El vrtice B es solucin de 8 Factible
6x + 3y = 30
2x + 8y = 24 6
Por tanto, B(4, 2)
4
El vrtice C es solucin de B
2
2x + 8y = 24
y=0 C
Por tanto, C(12, 0) 2 4 6 8 10 12 14
X
Resolvemos por el mtodo analtico
Evaluamos la funcin objetivo z en los vrtices.
Y
Vrtice z = 50x + 100y
14
z = 500 + 10010 =
A(0, 10)
= 0+10000 = 10 000 12
z = 504 + 1002 = 10
A(0, 10)
B(4, 2) Regin
= 200+200 = 400 Factible
8
z = 5012 + 1000 =
C(12, 0)
= 6000+0 = 6 000 6
El costo mnimo se obtiene en B. 4
B(4, 2)
Solucin: 2
x = 4 anuncios en telenovelas
C(12, 0)
y = 2 anuncios en futbol
Costo z = 400 (mil ) 2 4 6 8 10 12 14
X
Resolvemos por el mtodo grfico
Min z = 50 x + 100y Y
s.a. 6x + 3y 30 14
2x + 8y 24
12
x, y 0
10 A(0, 10)
El costo mnimo Regin
se obtiene en el Z = 600
8 Factible
punto B.
6
Z = 400
4
B(4, 2)
2
Solucin:
x = 4 anuncios en telenovelas C(12, 0)
y = 2 anuncios en futbol X
2 4 6 8 10 12 14
Costo z = 400 (mil )
Nmero de Soluciones de un PPL
Los dos ejemplos anteriores, Gepetto y Dorian Auto,
tienen, cada uno, una nica solucin ptima.
No en todos los PPL ocurre esto. Se pueden dar
tambin las siguientes posibilidades:
Algunos PPL tienen un nmero infinito de
soluciones ptimas (alternativas o mltiples
soluciones ptimas).
Algunos PPL no tienen soluciones factibles (no
tienen regin factible).
Algunos PPL son no acotados: Existen puntos en
la regin factible con valores de z arbitrariamente
grandes (en un problema de maximizacin).
Veamos un ejemplo de cada caso.
Nmero infinito de soluciones ptimas
Y
Consideremos el siguiente 60
problema:
50
C
max z = 3x + 2y
40
s.a: 3x + 2y 120
x + y 50
x,y0 B
30 Regin
Factible
z = 120
Cualquier punto (solucin) situado 20
en el segmento AB puede ser una
solucin ptima de z =120. z = 60
10
z = 100
A
10 20 30 40 50 X
Sin soluciones factibles
Y
Consideremos el siguiente
60
problema:
No existe
Regin Factible
max z = 3x1 + 2x2 50
x 30
s.a: 3x + 2y 120 40
x + y 50 x + y 50 y 30
x 30
y 30 30
x,y0
20
10 3x + 2y 120
No existe regin factible
10 20 30 40 50 X
PPL no acotado
max z = 2x y Y
s.a: xy1 6
Regin Factible
2x + y 6
x, y 0 5
La regin factible es no
4
acotada. Se muestran en el
grfico las rectas de nivel z=4
para z = 4 y z = 6. Pero 3
podemos desplazar las
rectas de nivel hacia la
2
derecha indefinidamente sin
z=6
abandonar la regin factible.
Por tanto, el valor de z 1
puede crecer
indefinidamente.
1 2 3 4 5 X
FIN
