Semana 15
Álgebra
semana
Academia CÉSAR VALLEJO Material Didáctico
15
Programación lineal
¡Tenga en cuenta que...! DEFINICIÓN
Es un método de optimización cuya finalidad es maximizar y/o
También podemos resolver un problema
de programación lineal con interpreta- minimizar una función lineal con dos variables, llamada función
ción gráfica. objetivo, sujeta a restricciones que están dadas por inecuaciones
Ejemplo lineales.
máx f(x; y) = 3x + 2y
Función objetivo
sujeto a la siguiente región
Es una función lineal con dos variables que se quiere optimizar.
Y Forma general
D máx (mín) f(x; y) = ax + by + c
E
donde:
x; y : variables de decisión
A S a; b; c : constantes fijas
Conjunto de restricciones
B C X
Es el conjunto de inecuaciones lineales.
Forma general
La dirección del crecimiento de las rectas
a1x b1y c1
de nivel que se obtiene de
a2 x b2 y c2
z = f(x; y) = 3x + 2y es el vector (3; 2).
a x b y c
n n n
máx f
Condiciones de no negatividad x ≥ 0; y ≥ 0
mín f Y
D Ejemplo
Dado el problema de programación lineal
f(x; y) = 2x + 5y
máx
A S
2 sujeto a las restricciones
y − x ≤ 3 (I)
3 C X
y + x ≤ 7 (II)
x ≥ 0; y ≥ 0
vector de
crecimiento
grafique el conjunto de restricciones.
Resolución
Entonces
De (I)
f(A) = mín f
y ≤ x+3
f(D) = máx f
De (II)
y ≤ – x + 7
Semestral Intensivo Virtual UNI Álgebra
Dando valores obtenemos
Y
¡Sabía que...!
7
En una región convexa, se distinguen los
5 siguientes puntos:
3
punto
1 extremo
–3 2 7 X
Punto factible
Al par ordenado P = (x0; y0) que satisface todas las restricciones se
punto punto
llama punto factible. interior frontera
Región factible
Es el conjunto de puntos P = (x0; y0) que satisface todas las restric-
ciones y puede ser acotada y no acotada.
¡Recuerde que...!
Solución óptima
Dado f(x; y) = ax + by
Al par ordenado P=(x0; y0) que pertenece a la región factible y maxi-
miza o minimiza la función objetivo, se le llama solución óptima.
punto
óptimo
Valor óptimo
Es el valor mínimo o máximo que adquiere la función objetivo.
Teorema fundamental de la optimización
Sea S la región factible convexa acotada formada por las restriccio-
ax+by=0
nes de un problema de programación lineal, entonces el máximo o
mínimo de la función objetivo f (x; y) se alcanza en puntos extremos.
Puntos óptimos consecutivos (infinitas
soluciones)
Si hay una solución óptima, esta se encuentra en un
punto extremo de la región factible. puntos óptimos
consecutivos
(infinitas soluciones)
Corolario
Si hay infinitas soluciones, estas se encuentran en dos puntos extre-
mos consecutivos y en el segmento que une estos puntos.
ax+by=0
Academia CÉSAR VALLEJO Material Didáctico
Problemas resueltos Las condiciones x ≥ 0 ∧ y ≥ 0 indican que la
1. Esboce la región factible del siguiente proble- región factible está en el primer cuadrante, en-
ma de programación lineal. tonces obtendremos la siguiente figura
z = 3x + 8y
máx
4x+3y ≤ 12
4 x + 3 y ≤ 12
2 x + 5 y ≤ 10 4
x≥0
y≥0 2
Resolución
Para graficar 4x + 3y ≤ 12, primero graficamos 3
2x+5y ≤ 10
la igualdad.
4x + 3y = 12
4 2. Resuelva el siguiente problema de programa-
→ y = − x + 4 ción lineal mediante el método gráfico.
3
máx z = 2y – x
Y
Sujeto a las restricciones
X Y Y (8; 5)
(0; 4)
0 4
3 0 (1; 3)
S
(3; 0) X
(3; 0) X
Y como Resolución
4x + 3y ≤ 12 Como z = – 1x + 2y, el vector que indica la direc-
4 ción de crecimiento es v = ( – 1; 2).
→ y ≤ − x + 4
3
Trazamos las rectas de nivel por la región factible.
Sombreamos la región que está por debajo de
la recta. Y
Y (1; 3)
dirección de
2
4 crecimiento S recta de nivel
–1 X
3 X
Por lo tanto, el máximo de z ocurre en (1; 3) y
es 5.
Semestral Intensivo Virtual UNI Álgebra
A) VFF B) VFV C) VVV
Práctica dirigida D) VVF E) FVF
1. Halle el conjunto de restricciones que determi- 3. Una compañía posee dos minas. La mina A
na la siguiente región factible R. produce cada día 1 tonelada de hierro de alta
calidad, 3 toneladas de calidad media y 5 to-
Y neladas de baja calidad. La mina B produce
9 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 tone-
3 ladas de calidad media y 200 toneladas de baja
R calidad. Si se sabe que el costo diario de ope-
3 9 X ración es de S/100 000 en cada mina, ¿cuántos
días debe trabajar cada mina para que el costo
sea mínimo?
y + 3x ≤ 9 3 x − 9 ≤ − y
A) 20 días en A y 40 días en B
A) 3 y + x ≤ 3 B) 3 y + x ≤ 9
x ≥ 0; y ≥ 0 x ≥ 0; y ≥ 0 B) 40 días en A y 40 días en B
C) 30 días en A y 40 días en B
3 y + x ≤ 9 D) 40 días en A y 30 días en B
C) y − 3 x ≤ 9 E) 40 días en A y 20 días en B
x ≥ 0; y ≥ 0
4. En un almacén de frutas hay 800 kg de naran-
y + 3x ≥ 9 3 y + x ≤ 9 jas, 800 kg de manzanas y 500 kg de plátanos.
D) 3 y + x ≥ 9 E) y + 3 x ≥ 6 Para su venta se hacen dos lotes, A y B: el lote
x ≥ 0; y ≥ 0 x ≥ 0; y ≥ 9 A contiene 1 kg de naranja, 2 kg de manzanas y
1 kg de plátanos; el lote B se compone de 2 kg
2. La región admisible S del problema de progra- de naranjas, 1 kg de manzanas y 1 kg de pláta-
mación lineal mín f(x; y) = 7x + 6y se muestra en nos. El beneficio por kilogramo que se obtiene
el gráfico. con el lote A es de S/1,2 y con el lote B es de
S/1,4. Calcule el beneficio máximo.
Y
A) S/900 B) S/560 C) S/660
20
D) S/800 E) S/400
S
10 5. Calcule el valor de b(b < 0 ) para que la fun-
ción f(x; y) = 3x + by alcance su máximo valor en
3 infinitos puntos de la región generada por el
siguiente sistema de inecuaciones.
x + y ≥ 3
2 8 15 X
x + 5 y ≤ 15
Indique el valor de verdad (V) o falsedad (F) según x − 3 ≤ y
corresponda.
I. El valor óptimo es 74. 1
- 2 C)
A) -1 B) -
II. El problema tiene infinitas soluciones. 2
3
16 D) - - 3
E)
III. El punto 6; es una solución. 2
3
Academia CÉSAR VALLEJO Material Didáctico
6. Un almacén guarda bidones de aceite de oliva y II. Si a y b son negativos, entonces el máximo
de girasol. Para atender a los clientes, se ha de de f(x; y) se encuentra en A.
tener almacenados un mínimo de 20 bidones III. ∃ a ∧ b ∈ R/ el máximo valor de f(x; y) se en-
de aceite de girasol y 40 de aceite de oliva; ade- cuentra en D.
más, el número de bidones de aceite de oliva
no debe ser inferior a la mitad del número de A) FFF B) VFV C) VFF
bidones de aceite de girasol. La capacidad total D) FVV E) VVV
del almacén es de 150 bidones. El gasto de al-
macenaje es de $1, el mismo para los dos tipos 9. La región admisible S y el crecimiento de la
de aceite. ¿Cuántos bidones de cada tipo habrá
función objetivo del problema
que almacenar para que el gasto sea mínimo?
(f(x; y)=ax+by; a ∧ b ∈ Z ∧ a y b PESI ∧ a > b)
maximizar f(x; y) sujeto a (x; y) ∈ S como se
A) 40 y 20 B) 40 y 30 C) 80 y 40
muestra en la siguiente figura.
D) 130 y 80 E) 130 y 20
7. Si f(x; y)=ax+by; {a ∧ b} ⊂ R+ está sujeto a la región Y
Y (3; 4)
crecimiento 3
2+ 3 D
2 S
C
2
1 B
–1 2 3 4 5 6 7 8 X
A 1 2 3 4 5 X
–2
determine la variación de a/b para que el
máximo de f(x; y) ocurra solo en C.
20 15 26
-1 A) B) C)
A) 3 ; 1 B) 3; 2 C)
1; 3 3 2 3
-1 12
D) 〈1; 2〉 E) 0; 3 D) E) 7
5
8. Se tiene el problema máx f(x; y) = ax + by sujeto 10. Indique cuáles son las proposiciones correctas.
al siguiente recinto. I. En un problema de programación lineal, el
Y valor óptimo de la función objetivo es alcan-
C zado en un vértice de la región admisible.
5
D II. Si a la región admisible de un problema de
4
programación lineal se le adiciona una nue-
va restricción de la forma ax + by ≤ c, el valor
óptimo de la función objetivo no varía.
III. Si (x*; y*) es la solución de un problema
A
1 B de maximización y z* es el valor óptimo,
se tiene que z* ≥ ax + by, para todo (x; y)
1 2 6 8 X
en la región admisible (ax + by es la función
Indique la secuencia correcta de verdad (V) o objetivo).
falsedad (F).
I. Para que C sea la solución óptima, se tiene A) solo I B) I y II C) I y III
que cumplir 2b > a > 0. D) solo III E) I, II y III
Semestral Intensivo Virtual UNI Álgebra
3. En una granja de pollos, se aplicará una dieta
Práctica domiciliaria para engordar con una composición mínima
de 15 kilos de una sustancia A, y otros 15 de
1. Esboce el conjunto una sustancia B. En el mercado solo se en-
{
S = (x; y)∈R 0+ ×R 0+ nx + y ≤ n ∧ x + 2 ny ≥ 2 n; n∈Z + } cuentran dos clases de compuestos: el tipo I
con una composición de un kilo de A y cinco
A) Y B) Y de B; y el tipo II con una composición de cinco
n n kilos de A y una de B. El precio de tipo I es de
S/10 y el de tipo II es S/30. ¿Qué cantidades se
1 1
X X han de comprar de cada tipo para cubrir las
1 2n 1 2n necesidades con un costo mínimo?
C) Y A) 2 y 3
n B) 1 y 4
C) 3 y 2
1 D) 1,5 y 3,5
X
E) 2,5 y 2,5
1 2n
D) Y E) Y 4. De la siguiente gráfica.
2n 2n
1 1 Y (9; 8) (10; 8)
X X (12; 7)
(6; 7)
1 n 1 n
(4; 6)
(11; 5)
2. Resuelva el siguiente problema de programa- S
ción lineal: (10; 4)
x 2y
máx: f( x; y ) = +
5 5 (6; 2)
x + y ≤ 105 (1; 1) (4; 1)
x − y ≥ 5 X
x + 2 y ≥ 50
x ≥ 0 ∧ y ≥ 0
Luego indique las proposiciones correctas. Si f(x; y) = x + 3y está sujeta a la región S, halle el
139 máximo valor de f(x; y).
I. 25; es un punto factible.
7
II. El valor óptimo es 31. A) 32
III. La solución óptima es (55; 50) B) 28
C) 36
A) solo I B) I, II y III C) II y III D) 42
D) solo III E) I y II E) 34
Academia CÉSAR VALLEJO Material Didáctico
5. Sea f(x; y) = ax + by la función objetiva del pro- D) 40 semanas en la planta P y 30 semanas en
blema P con a; b ≠ 0. la planta Q.
P: minimizar f(x; y); sujeto a S ⊂ R2.
E) 40 semanas en la planta P y 20 semanas en
Y la planta Q.
C(4; 7)
D 7. Si f(x; y) = 4x + 3y se maximiza para infinitos pun-
tos de la arista CD.
S
A B(8; 2) Y B(1; 7)
C(x0; y0)
X
Si las soluciones óptimas se encuentran en el D(x1; y1)
segmento BC, ¿a qué es igual ab – 1?
5 5 3 E(5; 1)
- C)
A) - B)
2 4 4
5 5 A X
D) E)
4 2
6. Una empresa de automóviles tiene dos plantas (4 x1 + y0 + 3 y1)2
calcule el valor de .
de montaje de vehículos, P y Q, en las que pro- x 02 + 2 x 0 y0 + y02
duce tres modelos, A, B y C, con las siguientes
condiciones:
A) 16 B) 4 C) 25
D) 4/5 E) 9/4
Modelo Modelo Modelo
A B C
8. Calcule fmín + fmáx si f(x; y) = 2x – y está sujeto a la
N.º de vehículos
10 30 15 siguiente región:
P por semana
N.º de vehículos
20 20 70
Q por semana
Y
N.º de vehículos 8
que se necesita 800 1600 1800 2x–3y = –18
como mínimo
4x–y = 8
Si el gasto de mantenimiento semanal en cada
planta es de 6 millones de soles, ¿cuántas se-
manas ha de funcionar cada planta para que el –1 X
costo de producción sea mínimo?
–2
A) 50 semanas en la planta P y 20 semanas en
la planta Q.
B) 30 semanas en la planta P y 30 semanas en
la planta Q.
C) 45 semanas en la planta P y 30 semanas en A) 2 B) – 8 C) – 4
la planta Q. D) 5 E) 3
Semestral Intensivo Virtual UNI Álgebra
9. Halle el máximo valor de f(x; y) = 3x + 2y sujeto a II. Si R es acotado, entonces siempre es posi-
la región M, tal que ble encontrar fmáx y fmín para cualquier fun-
ción objetivo (f).
III. Si existe fmáx y fmín, entonces
b+3 fmáx ≥ 0 ∧ fmín ≥ 0
A) VVF B) VVV C) VFF
b M D) FVV E) FVF
y=x+4
12. Una textilería produce 2 tipos de tela: la prime-
ra necesita 1 hora máquina y 1 hora hombre y
1
la segunda 1 hora máquina y 2 horas hombre
2 a a2 –1 para producir una ganancia de S/300 y S/400
por tela, respectivamente; además, se dispone
y=– 2x+7
de 6 horas máquina y 10 horas hombre. Halle
la producción óptima para obtener la mayor
A) 36 B) 42 C) 49 ganancia si se exige que el número de telas del
D) 45 E) 40 tipo A no supere al número de telas del tipo B.
10. Un grupo de aficionados a un equipo de fút-
bol encarga a una empresa de transporte el A) 3 del tipo A y 3 del tipo B
viaje para llevar a los 1200 socios a ver la final B) 2 del tipo A y 4 del tipo B
de su equipo. La empresa dispone su flota de C) 3 del tipo A y 4 del tipo B
autobuses de 50 asientos y microbuses de 30 D) 1 del tipo A y 5 del tipo B
asientos. El precio del viaje en cada autobús es E) 2 del tipo A y 3 del tipo B
de 252 dólares y en cada microbús es de 180
dólares. Si se sabe que la empresa dispone de 13. Determine la relación entre a y b para que el
28 conductores, ¿cuál es el costo mínimo del siguiente problema presente infinitas solucio-
viaje? nes óptimas.
máx f(x; y) = ax + by, tal que (x; y) ∈ S
A) 6048 B) 6056 C) 6336 x + y ≥ 3
D) 7036 E) 7080
S = x + 5 y ≤ 15
x − y ≤ 3
11. Con respecto al problema
f(x; y) = ax + by, sujeto a
mx + ny ≤ p A) a = b2 ∨ 5a = b
rx + 5 y ≤ t b
B) a = b ∨ a =
φ≠ R=
5
qx + uy ≤ s
x ≥ 0 ∧ y ≥ 0 b
C) a2 = b2 ∨ a =
indique la secuencia correcta de verdad (V) o 5
falsedad (F). a
D) a2 = b2 ∨ =b
I. Si R es no acotado, entonces existe un f, tal 5
que fmáx y fmín ∈R. E) a2 = b ∨ 5a = b
Academia CÉSAR VALLEJO Material Didáctico
14. Dado el siguiente problema de programación lineal: 15. Si un problema de programación lineal se
mín: f(x; y) = mx + ny ∧ mn ≠ 0 ha resuelto por el método gráfico como se
a1x + b1y ≤ c1 muestra
a x + b2 y ≤ c2
φ≠ R= 2
a3 x + b3 y ≤ c3 Y
x ≥ 0 ∧ y ≥ 0 (3; 6)
vector direccional
Indique la secuencia correcta de verdad (V) o (6; 5) 1 –2
4 v= ;
falsedad (F). 5 5
I. R es un recinto convexo. rectas a nivel generadas
II. Si (x0; y0) es la solución óptima, entonces al 1 por z=ax+by
aumentar una restricción más (ax + by ≤ c), 1 2 5 X
(x0; y0) sigue siendo la solución óptima.
III. Si cambiamos f por g(x; y) = m3x + m2ny, en- determine las proposiciones que son correctas.
tonces se mantiene igual al solución óptima. I. zmín ocurre en (3; 6) y zmáx ocurre en (5; 1).
II. ab < 0
A) VFV III. Si {a; b} ⊂ Z ∧ |a| y |b| son PESI, entonces
B) VVV z = x – 2y
C) FFF
D) VFF A) I y III B) II y III C) solo III
E) VVF D) I y II E) I, II y III
01 - C 03 - E 05 - B 07 - A 09 - A 11 - A 13 - C 15 - E
02 - B 04 - E 06 - E 08 - C 10 - A 12 - B 14 - A
