Introducción a la Programación Lineal

Introducción a la Programación Lineal
J. Montealegre
I. Flores
Febrero de 2015
1.
Desigualdades en el plano cartesiano
Si en un plano P consideramos una recta L éste queda dividido en tres conjuntos: el conjunto
de puntos que están en la recta misma, y los semiplanos P1 y P2 formados por los puntos que
están a uno y otro lado de la recta L.
Consideremos la recta vertical x = a.
Y
x
a
x
a
X
Los puntos que están en la recta son aquellos que satisfacen su ecuación. Los puntos que están
a la izquierda satisfacen la inecuación x < a, y los puntos que están a la derecha satisfacen la
inecuación x > a.
Ejemplo 1.1. Graficar en el plano cartesiano la desigualdad y < x + 1.
Solución. Primero graficamos a la recta y = x + 1.
Y
y = x +1
X
Luego verificamos si las coordenadas del punto (0, 0) satisfacen la desigualdad. Como este es
el caso, entonces el semiplano que representa gráficamente a la inecuación es el que contiene
al origen.
Y
y < x +1
X
Notar que los puntos que están en la recta satisfacen y = x + 1, lo que se indica con un trazo
discontinuo.
Ejemplo 1.2. Graficar en un mismo sistema de coordenadas el conjunto determinado por las
siguientes desigualdades:

x + 2y ≤ 6



x+y ≤4
x≥0



y ≥ 0.
Indicar los vértices del polı́gono formado.
Solución. Como las desigualdades deben satisfacerse simultáneamente, se debe graficar la
intersección de las regiones correspondientes a cada una de ellas.
x y
La inecuación x + 2y ≤ 6 es equivalente a la inecuación + ≤ 1, por lo que en este caso
6 3
x y
la región a considerar se encuentra abajo de la recta (incluyendo a la recta) + = 1. Por
6
3
x y
otro lado, la inecuación x + y ≤ 4 es equivalente a la inecuación + ≤ 1 y la región que le
4
4
x y
corresponde también se ubica debajo de la recta + = 1.
4 4
Es claro que la región que corresponde a x ≥ 0 es el semiplano ubicado a la derecha del eje
Y , y la que corresponde a y ≥ 0 es el semiplano ubicado arriba del eje X.
De lo anterior se concluye que la región buscada es la que se muestra en el gráfico
Y
x+ y= 4
x + 2y = 6
X
2
2.
Programación lineal
La teorı́a de la programación lineal fue desarrollada en la década 1940 - 1950 por matemáticos
tales como John von Neumann, George Dantzig, T. Koopmans, etc. La programación lineal
sirve para encontrar el valor máximo o el valor mı́nimo de una expresión lineal sujeta a un conjunto de desigualdades lineales. La aplicación más común abarca el problema general de asignar
recursos limitados entre actividades competitivas de la mejor manera posible, esto es, en forma
óptima. Tiene aplicaciones en la investigación de operaciones, ciencias administrativas, fı́sica
y biologı́a.
Veamos el ejemplo de una fábrica que produce una gama de artı́culos y que dispone de
una variedad de recursos (personal, materias primas, máquinas, créditos, etc.) cada uno de los
cuales supone un costo a considerar. ¿Cuál debe ser la polı́tica a seguir si se quieren conseguir
los máximos beneficios?
Ejemplo 2.1. Supongamos que una compañia fabrica dos tipos de artefactos, manuales y
eléctricos. Cada uno de ellos requiere en su fabricación el uso de tres máquinas: A, B y C.
Un artefacto manual requiere del empleo de la máquina A durante dos horas, de una hora
en la máquina B y de una hora en la máquina C. Un artefacto eléctrico requiere de una
hora en A, dos horas en B y una hora en C. Supóngase, además, que el número máximo de
horas disponibles por mes para el uso de las tres máquinas es 180, 160 y 100, respectivamente.
La utilidad que se obtiene con artefactos manuales es de $4 y de $6 para los eléctricos. Si
la compañia vende todos los artefactos que fabrica ¿cuántos de ellos de cada tipo se deben
elaborar con el objeto de maximizar la utilidad mensual?
Solución. Un resumen de los datos se presenta en la siguiente tabla
Manual
Eléctrico
Horas disponibles
A
B
C
2h
1h
180
1h
2h
160
1h
1h
100
Utilidad
Unidad
$4
$6
Consideremos
x : número de artefactos manuales que se fabrican en el mes.
y : número de artefactos eléctricos que se fabrican en el mes.
p :
utilidad mensual.
La utilidad es
P = 4x + 6y
y la función objetivo es maximizar P sujeta a la condición de que x e y deben ser una solución
para el sistema de inecuaciones
2x + y ≤ 180,
(1)
x + 2y ≤ 160,
(2)
x + y ≤ 100,
(3)
x ≥ 0,
(4)
y ≥ 0.
(5)
A las restricciones (4) y (5) se les denomina condiciones de no negatividad. La región que
satisface simultáneamente las condiciones (1) a (5) se denomina región factible.
3
Formulación del problema de programación lineal
Del ejemplo anterior podemos establecer que la formulación general de un problema de
programación lineal es la siguiente:
Obtener los valores x1 , x2 , x3 , . . . , xn que maximicen o minimicen la llamada función
objetivo
z = c1 x1 + c2 x2 + c3 x3 + · · · + cn xn
Sujeta a las condiciones
a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn ≤ (≥) b1
a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn ≤ (≥) b2
..
.
am1 x1 + am2 x2 + am3 x3 + · · · + amn xn ≤ (≥) bm
Con
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, · · · , xn ≥ 0
llamadas las condiciones de no negatividad.
Ejemplo 2.2. Una fábrica produce tres productos de caucho: A, B y C y los tres productos
requieren de cuatro materias primas diferentes. La cantidad de cada materia prima usada por
libra del producto final se muestra en la tabla
Producto
A
B
C
Mat. Prima 1
4
3
6
Cantidad (onz/lb)
Mat. Prima 2
2
2
3
Mat. Prima 3
4
2
5
Mat. Prima 4
6
9
2
La fábrica debe producir al menos 1000 libras de A, 500 libras de B y 400 libras de C para
el fin de mes, pero se sabe que se pueden vender más de cada uno de los tres productos. Los
inventarios de los que dispone la fábrica son: 500 libras de la materia prima 1, 425 libras de la
materia prima 2, 650 libras de la materia prima 3 y 1100 libras de la materia prima 4. Cada
libra de A produce a la fábrica una ganancia de $7, cada libra de B una ganancia de $7 y cada
libra de C una ganancia de $6. Se deberá establecer un plan de producción de modo que las
ganancias sean máximas.
Solución.
1. Determinación de las variables. Sean
x : número de libras de A
y : número de libras de B
z : número de libras de C
u : la ganancia al mes
2. Determinación de la función objetivo. Del enunciado se tendrá que la ganancia total
deberá ser igual a la suma de las ganancias obtenidas por los tres productos. Ası́, la
función objetivo es
máx u = 7x + 7y + 6z.
4
3. Determinación de las restricciones. Identificamos restricciones de
a) Cantidad de materia prima. Primero tenemos que cada libra tiene 16 onzas y ası́ tenemos de la tabla que
4x + 3y + 6z ≤ 8000
2x + 2y + 3z ≤ 6800
4x + 2y + 5z ≤ 10400
6x + 9y + 2z ≤ 17600
b) Demanda de los productos. De los datos tenemos que
x ≥ 1000
y ≥ 500
z ≥ 400
c) De no negatividad.
x ≥ 0, y ≥ 0, z ≥ 0.
Ası́, nuestro problema de Programación lineal es
máx 7x + 7y + 6z
sujeta a
4x + 3y + 6z ≤ 8000
2x + 2y + 3z ≤ 6800
4x + 2y + 5z ≤ 10400
6x + 9y + 2z ≤ 17600
x ≥ 1000
y ≥ 500
z ≥ 400
con
x ≥ 0, y ≥ 0, z ≥ 0.
Ejemplo 2.3. Un fabricante produce dos tipos de parrillas para asar, Tipo I y Tipo II.
Durante la producción las parrillas requieren del uso de dos máquinas A y B. El número de
horas necesarias en ambas está indicado en la tabla siguiente.
Tipo I
Tipo II
Máquina A
2 horas
4 horas
Máquina B
4 horas
2 horas
Si cada máquina puede utilizarse 24 horas por dı́a y las utilidades en los modelos son de $4
y $6, respectivamente, ¿cuántas parrillas de cada tipo deben producirse por dı́a para obtener
una utilidad máxima?¿Cuál es la utilidad máxima?
5
Solución. Construimos la siguiente tabla
Máquina A
2 horas
4 horas
24
Tipo I
Tipo II
Total horas a usar
Máquina B
4 horas
2 horas
24
Utilidades
4
6
Sea x el número de parrillas del Tipo I, y el número de parrillas del Tipo II y u la utilidad
por producir parrillas Tipo I y Tipo II, con u = 4x + 6y.
Entonces el problema es equivalente a
Maximizar 4x + 6y
sujeta a 2x + 4y ≤ 24
4x + 2y ≤ 24
x ≥ 0, y ≥ 0.
Ejemplo 2.4. Una dieta debe contener al menos 16 unidades de carbohidratos y 20 de
proteı́nas. El alimento A tiene 2 unidades de carbohidratos y 4 de proteı́nas; el alimento B
contiene 2 unidades de carbohidratos y 1 de proteı́nas. si el alimento A cuesta $1.20 por unidad
y el B $0.80 por unidad, ¿cuántas unidades de cada alimento deben comprarse para minimizar
el costo?¿Cuál es el costo mı́nimo?
Solución. De los datos se tiene la siguiente tabla
Alimento A
Alimento B
Total
Carbohidratos
2
2
16
Proteı́nas
4
1
20
Costo
1.20
0.80
Sean x : unidades en el alimento A, y : unidades en el alimento B, C : costo por la compra de
x unidades de A y y unidades de B. Tenemos entonces
Problema original
Problema equivalente
Minimizar C = 1,20x + 0,80y Maximizar C1 = −1,20x − 0,80y
sujeto a
sujeto a
2x + 2y ≥ 16
2x + 2y ≥ 16
4x + y ≥ 20
2x + 2y ≥ 16
x ≥ 0, y ≥ 0
x ≥ 0, y ≥ 0
donde C1 = −C.
Ejemplo 2.5. Un fabricante produce un artı́culo en dos presentaciones: A y B, usando las
materias primas m1 y m2 . Diariamente se necesita por lo menos 18 kg. de m1 y 12 kg. de m2 ;
y como máximo 34 horas de mano de obra. Se requiere 2 kg. de m1 para cada artı́culo A y 1
kg. de m1 para cada artı́culo B. Para cada artı́culo de A y B se requiere 1 kg. de m2 . Además
en la fabricación de un artı́culo de A se emplean 3 horas y 2 horas en un artı́culo de B. Si la
utilidad por artı́culo en el modelo A es de $5 y $3 por el artı́culo B, ¿cuántos artı́culos de cada
modelo deben producirse para maximizar la utilidad y cuál es ésta utilidad máxima?
Solución. Se tiene la tabla
A
B
m1
2
1
m2
1
1
Horas
3
2
Utilidad
5
3
El problema es Maximizar z = 5x + 3y, sujeta a:
2x + y ≥ 18
x + y ≥ 12
3x + 2y ≤ 34
6
3.
Método gráfico de resolución de un PPL
Ejemplo 3.1. Supongamos que una compañia fabrica dos tipos de artefactos, manuales y
eléctricos. Cada uno de ellos requiere en su fabricación el uso de tres máquinas: A, B y C.
Un artefacto manual requiere del empleo de la máquina A durante dos horas, de una hora
en la máquina B y de una hora en la máquina C. Un artefacto eléctrico requiere de una
hora en A, dos horas en B y una hora en C. Supóngase, además, que el número máximo de
horas disponibles por mes para el uso de las tres máquinas es 180, 160 y 100, respectivamente.
La utilidad que se obtiene con artefactos manuales es de $4 y de $6 para los eléctricos. Si
la compañia vende todos los artefactos que fabrica ¿cuántos de ellos de cada tipo se deben
elaborar con el objeto de maximizar la utilidad mensual?
Solución. Según sabemos del ejemplo 2.1, si consideramos
x : número de artefactos manuales que se fabrican en el mes.
y : número de artefactos eléctricos que se fabrican en el mes.
p :
utilidad mensual.
el Problema de Programación Lineal es
máx P = 4x + 6y
sujeta a 2x + y ≤ 180,
x + 2y ≤ 160,
x + y ≤ 100,
x ≥ 0, y ≥ 0.
Aunque existen una cantidad infinita de soluciones, se debe hallar la que maximice a la
función de utilidad. Usaremos el geogebra como una herramienta para resolver el problema,
siguiendo los siguientes pasos:
1. Trazar las rectas
L1 : 2x + y = 180,
L2 : x + 2y = 160,
L3 : x + y = 100,
L4 : x = 0
y
L5 : y = 0.
Para graficar una recta en geogebra se puede hacer de varias maneras:
i. Una manera es digitar en la barra de entrada la ecuación de la recta, por ejemplo
para la recta L1 se digitará tal cual la ecuación 2x + y = 180 y luego presionar enter.
ii. También podemos etiquetar la recta, darle color, modificar su grosor, cambiar el
estilo del trazo, etc. Esto es importante porque en el método gráfico al trabajar con
muchas rectas es necesario diferenciarlas.
iii. La forma de poder editar una recta es seleccionarla, ya sea en la vista gráfica o
en la vista algebraica. Una vez seleccionada, presionar el botón derecho del mouse
7
y elegir propiedades de la lista desplegada. Se abrirá una ventana donde se puede
seleccionar qué caracterı́sticas de la recta se desean modificar.
2. Graficar las regiones que representan las inecuaciones
2x + y ≤ 180,
x + 2y ≤ 160,
x + y ≤ 100,
x≥0
y
y ≥ 0.
La intersección de éstas regiones será la región factible, pues los puntos (x, y) que están
en ella satisfacen las restricciones del problema.
Luego hallamos los vértices de la región factible intersectando las rectas que forman los
lados de dicha región. Por ejemplo, para hallar el vértice C se intersectan las rectas L2
y L3 . En geogebra se intersecta de la siguiente manera: de la barra de herramientas
elegimos el botón intersección, una vez activado éste botón hacemos clic en las rectas L2
y L3 y como resultado se obtiene el punto C.
En nuestro caso, tenemos
A (40, 60) B (80, 20) C (90, 0) D (0, 0)
8
E (0, 80) .
3. Se sabe, por el teorema de Weierstrass que una función lineal afı́n definida sobre una
región factible acotada y no vacı́a tiene un valor máximo (o mı́nimo) y se puede encontrar
este valor en un vértice de la región factible. Esta afirmación permite hallar soluciones
óptimas, para lo cual usaremos la herramienta deslizador del geogebra, de la siguiente
manera:
Seleccionamos el botón deslizador de la barra de herramientas y hacemos clic en un
espacio vacı́o de la vista gráfica, aparece una ventana donde daremos el nombre k (arbitrario) al deslizador, además ingresamos los valores mı́nimo y máximo del intervalo del
deslizador, de tal manera que al deslizar la función objetivo U , ésta comprenda todos los
puntos de la región factible. En nuestro caso el valor mı́nimo es 0 y el valor máximo 520.
El tercer paso del método descrito, es equivalente a evaluar la función objetivo en cada uno
de los vértices de la región factible y después elegir aquel en que la función objetivo resulte
óptima. En nuestro caso, si evaluamos la función objetivo en cada punto, se tiene:
P (40, 60) = 4 (40) + 6 (60) = 520
P (80, 20) = 4 (80) + 6 (20) = 440
P (90, 0) = 4 (90) + 6 (0) = 360
P (0, 0) = 4 (0) + 6 (0) = 0
P (0, 80) = 4 (0) + 6 (80) = 480.
Por consiguiente, P tiene un valor máximo de $520 en A, en donde x = 40 e y = 60.
Observación 3.1. Cuando la región factible no está acotada, la función objetivo P puede no
tener un valor máximo o mı́nimo.
Ejemplo 3.2. Un fabricante produce dos tipos de parrillas para asar, Tipo I y Tipo II.
Durante la producción las parrillas requieren del uso de dos máquinas A y B. El número de
horas necesarias en ambas está indicado en la tabla siguiente.
Tipo I
Tipo II
Máquina A
2 horas
4 horas
Máquina B
4 horas
2 horas
Si cada máquina puede utilizarse 24 horas por dı́a y las utilidades en los modelos son de $4
y $6, respectivamente, ¿cuántas parrillas de cada tipo deben producirse por dı́a para obtener
una utilidad máxima?¿Cuál es la utilidad máxima?
Solución. Como en el ejemplo 2.3, si x es el número de parrillas del Tipo I, y el número
de parrillas del Tipo II y u la utilidad por producir parrillas Tipo I y Tipo II, entonces el
9
problema es equivalente a
máx 4x + 6y
sujeta a 2x + 4y ≤ 24
4x + 2y ≤ 24
x ≥ 0, y ≥ 0.
El máximo valor de u se da en el punto A (4, 4), u = 40.
Ejemplo 3.3 (Ejemplo 2.3). Una dieta debe contener al menos 16 unidades de carbohidratos
y 20 de proteı́nas. El alimento A tiene 2 unidades de carbohidratos y 4 de proteı́nas; el alimento
B contiene 2 unidades de carbohidratos y 1 de proteı́nas. si el alimento A cuesta $1.20 por
unidad y el B $0.80 por unidad, ¿cuántas unidades de cada alimento deben comprarse para
minimizar el costo? ¿Cuál es el costo mı́nimo?
Solución. Sean
x : unidades en el alimento A,
y : unidades en el alimento B,
C : costo por comprar x unidades de A, y
y unidades de B.
Tenemos, ejemplo 2.4, que el problema es equivalente a
máx C1 = −1,20x − 0,80y
sujeto a 2x + 2y ≥ 16
2x + 2y ≥ 16
x ≥ 0, y ≥ 0.
C1 será máximo cuando x e y asumen (ambos) valores más pequeños. Este valor máximo
de C1 se dará en el punto E. Las coordenadas de E se determinan resolviendo el sistema
2x + 2y = 16
4x + y = 20
de donde se obtiene E (4, 4). Ası́, C1 = −1,20 (4) − 0,80 (4) = −8, pero como C1 = −C = −8,
entonces C = 8. Por tanto, el mı́nimo de C = 8, se da en E (4, 4).
10
Ejemplo 3.4. Un fabricante produce un artı́culo en dos presentaciones: A y B, usando las
materias primas m1 y m2 . Diariamente se necesita por lo menos 18 kg. de m1 y 12 kg. de m2 ;
y como máximo 34 horas de mano de obra. Se requiere 2 kg. de m1 para cada artı́culo A y 1
kg. de m1 para cada artı́culo B. Para cada artı́culo de A y B se requiere 1 kg. de m2 . Además
en la fabricación de un artı́culo de A se emplean 3 horas y 2 horas en un artı́culo de B. Si la
utilidad por artı́culo en el modelo A es de $5 y $3 por el artı́culo B, ¿cuántos artı́culos de cada
modelo deben producirse para maximizar la utilidad y cuál es ésta utilidad máxima?
Solución. Como en el ejemplo 2.5, el problema es
máx 5x + 3y, sujeta a:
2x + y ≥ 18
x + y ≥ 12
3x + 2y ≤ 34
Resolviendo el sistema correspondiente a las restricciones
anteriores, se tiene
2x + y = 18
x + y = 12
3x + 2y = 34
A (6, 6), B (2, 14) y C (10, 2). La gráfica correspondiente
es
En el punto A (6, 6) se tiene que z = 48, en el punto B (2, 14) se tiene que z = 52 y en el
punto C (10, 2) z = 56. Por tanto, del modelo A se deben producir 10, del modelo B se deben
producir 2 y la utilidad máxima es de $56.
4.
Ejercicios propuestos
1. Un fabricante produce dos productos, A y B, cada uno de los cuales requiere tiempo en
tres máquinas, I, II y III. Los requerimientos (en horas) y la utilidad (en dólares) de
cada unidad de A y B, ası́ como, la disponibilidad mensual (en horas) de cada máquina,
están dados en el siguiente cuadro.
A
B
Disponibilidad mensual
I
2
5
200
II
4
1
240
III
3
2
190
Utilidad por producto
$250
$300
Determine cuántas unidades de cada producto deben producirse a fin de maximizar la
utilidad total.
2. Un agricultor comprará fertilizantes que contienen tres nutrientes:A, B y C. Los requerimientos mı́nimos semanales son 80 unidades de A, 120 de B y 240 de C. Existen dos
mezclas populares de fertilizantes en el mercado. La mezcla I cuesta $4 por bolsa, con
dos unidades de A, 6 de B y 4 de C. La mezcla II cuesta $5 por bolsa, con 2 unidades
de A, 2 de B y 12 de C.¿Cuántas bolsas de cada mezcla debe comprar el agricultor para
minimizar el costo de satisfacer sus requerimientos de nutrientes?
3. Una compañı́a extrae minerales de un yacimiento. Del número de libras de minerales A
y B que puede ser extraı́do por cada tonelada de los filones I y II está dado en la tabla
11
siguiente junto con los costos por tonelada. Si la compañı́a debe extraer al menos 3000
libras de A y 2500 de B, ¿cuántas toneladas de cada filón deben ser procesados con el fin
de minimizar el costo? ¿Cuál es el costo mı́nimo?
Mineral A
Mineral B
Costo por tonelada
Filón I
110 lb
200 lb
$50
Filón II
200 lb
50 lb
$60
4. Una compañı́a petrolera, que tiene dos refinerı́as, necesita al menos 800, 1400 y 500
barriles de petróleo de grados bajo, medio y alto, respectivamente. Cada dı́a, la refinerı́a
I produce 200 barriles de grado bajo, 300 de medio y 100 de alto grado, mientras que
la refinerı́a II produce 100 barriles de grado alto, 100 de bajo y 200 de grado medio.
Si los costos diarios son de $2500 para operar la refinerı́a I y de $2000 para la refinerı́a
II, ¿cuantos dı́as debe ser operada cada refinerı́a para satisfacer los requerimientos de
producción a un costo mı́nimo?¿Cuál es el costo mı́nimo? (Suponga que existe un costo
mı́nimo).
5. Una persona posee un capital de 10 millones de soles y le aconsejan que los invierta en
dos tipos de acciones A y B. Las de tipo A tienen más riesgo pero producen un beneficio
del 10 %. Las de tipo B son más seguras pero producen solo el 7 % anual.
Después de varias deliberaciones decide invertir como máximo 6 millones de soles en la
compra de acciones A y por lo menos, 2 millones en la compra de acciones B. Además,
decide que lo invertido en A sea, por lo menos, igual a lo invertido en B. ¿ Cómo deberá invertir su capital para que el beneficio anual sea máximo?
6. Una empresa fabrica tres tipos de alimentos para animales: A, B y C. Para tal efecto,
necesita dos fases, la primera (I) de fabricación en máquina, y una segunda fase (II) de
mano de obra. Dispone de 120 horas mensuales en la fase I y de 260 en la II, y para su
fabricación necesita para cada alimento las siguientes horas en cada una de las fases
A
B
C
Horas I
0.1
0.25
–
Horas II
0.2
0.3
0.4
Si el beneficio que se obtiene por cada tipo de alimento es de $3, $5 y $4, respectivamente,
establecer un programa de fabricación en el mes para que la utilidad sea máxima.
7. Una empresa fabrica los productos A, B y C y puede vender toda su producción a los
siguientes precios: el producto A a $700 por unidad, el producto B a $3500 y el producto
C a $7000. Producir cada unidad de A requiere de 1 hora de trabajo, 2 de acabado y 3
unidades de materia prima. Producir una unidad de B requiere de 2 horas de trabajo,
3 de acabado y 2.5 unidades de materia prima. Producir una unidad de C requiere 3
horas de trabajo, 1 hora de acabado y 4 unidades de materia prima. Para este periodo de
planificación se dispone de 100 horas de trabajo, 200 horas de acabado y 600 unidades
de materia prima. Formule y construya el modelo lineal que maximice los ingresos de la
empresa.
8. Una máquina de fabricar papel produce rollos de 82 cm de ancho. Se han recibido los
12
siguientes pedidos:
60
85
85
50
rollos
rollos
rollos
rollos
de
de
de
de
58
26
24
23
cm
cm
cm
cm
Plantear el problema de cómo cortar los rollos de 82 cm, a fin de satisfacer los pedidos y
minimizar el desperdicio.
9. Una compañı́a promueve periódicamente servicios públicos, seminarios y programas. Actualmente los planes de promoción para este año están en marcha. Los medios alternativos
para realizar la publicidad ası́ como los costos y la audiencia estimados por unidad de
publicidad, además de la cantidad máxima de unidades de publicidad en que puede ser
usado cada medio se dan en la tabla siguiente
Restricciones
Audiencia por unidad de publicidad
Costo por unidad de publicidad
Uso máximo del medio
TV
100000
$2000
10
Radio
18000
$300
20
Prensa
40000
$600
10
Para lograr un uso balanceado de los medios, la publicidad en radio no debe exceder el
50 % del total de unidades de publicidad autorizados. Además la cantidad de unidades
solicitadas en televisión debe ser al menos 10 % del total autorizado. El presupuesto total
para promociones se ha limitado a $18500. Formular un programa lineal que optimice la
audiencia total o la cantidad de personas que vean la publicidad.
10. Un Banco abre de Lunes a Viernes de 8 a.m. a 4p.m. De experiencias anteriores se sabe
que va a necesitar la cantidad de cajeros señaladas en la tabla siguiente
Periodo de tiempo
Cajeros requeridos
8−9
4
9 − 10
3
10 − 11
4
11 − 12
6
12 − 1
5
1−2
6
2−3
8
3−4
8
Hay dos tipos de cajeros: los que trabajan tiempo completo de 8 a.m. a 4 p.m., los 5 dı́as,
excepto la hora de almuerzo. El Banco determina cuando debe almorzar cada cajero,
pero debe ser entre las 12 m y 1 pm o entre la 1 pm y las 2 pm. A los empleados a tiempo
completo se les paga S/.180 la hora (incluida la de almuerzo). También hay trabajadores
a tiempo parcial que deben trabajar exactamente 3 horas consecutivas cada dı́a y se les
paga S/. 110 la hora, sin ningún otro pago. A fin de mantener la calidad del servicio
el Banco desea tener un máximo de 5 cajeros contratados a tiempo parcial. Se desea
minimizar los costos de empleados contratados.
13