PROGRAMACIÓN LINEAL Solución optima: Función objetivo: 𝑧 = 𝑥1 + 2𝑥2

Es un método que consiste en Es la solución factible que Piden el mín de 𝑧 = 𝑥1 + 2𝑥2

optimizar (maximizar o optimiza la función objetivo.
minimizar) una función lineal, Evaluando en los vértices
Teorema:
llamada función objetivo, sujeta Si existe la solución optima, ✓ (8; 6) ⟹ 𝑧 = (8) + 2(6) = 20
a restricciones lineales esta se encuentra en los
(inecuaciones lineales) vértices de la región factible ✓ (4; 9) ⟹ 𝑧 = (4) + 2(9) = 22
DEFINICIONES Ejemplito ✓ (2; 3)⟹ 𝑧 = (2) + 2(3) = 8
Región 𝑀í𝑛 𝑧 = 𝑥1 + 2𝑥2 ✓ (5; 1) ⟹ 𝑧 = (5) + 2(1) = 7
factible
(4; 9) Solución optima Valor optimo

(2; 3) (8; 6) Nota

En caso pidan el máximo,
(5; 1) entonces:
Solución ❖ Solución optima: (4; 9)
factible Resolución ❖ Valor optimo: 22
CONJUNTO CONVEXO Teorema: Ejemplito
El segmento pertenece al Toda región factible es un m𝑎𝑥 𝑓(𝑥; 𝑦) = 2𝑥 + 𝑦
conjunto conjunto convexo
Ejemplito (5; 10)
m𝑎𝑥 𝑓(𝑥; 𝑦) = 𝑥 + 3𝑦
(8; 4)
(7; 1)

NO ES Absurdo! Ya que, la región Resolución

COVEXO factible no es convexa. No
✓ 𝑓(7; 1) = 2(7) + 1 = 15
existe solución optima ✓ 𝑓(5; 10) = 2(5) + 10 = 20
Observación:
Teorema:
Si el valor optimo se repite ✓ 𝑓(8; 4) = 2(8) + 4 = 20
para los vértices 𝐴 y 𝐵, Se repite el valor optimo
entonces existen infinitas Existen infinitas soluciones
Convexo Convexo no soluciones optimas en el optimas en el segmento de puntos
acotado acotado segmento 𝐴𝐵 (5; 10) y (8; 4)
Teorema: ✓ 𝑓(5; 2) = 5 + 2 = 7 ❖ 𝑎𝑦 = 𝑏𝑥 + c , donde 𝑎 > 0
Si la región factible es no ✓ 𝑓(8; 1) = 8 + 1 = 9 𝑎𝑦 = 𝑏𝑥 + 𝑐
acotada, entonces es
✓ 𝑓(10; 2) = 10 + 2 = 12 𝒂𝒚 ≥ 𝒃𝒙 + 𝒄
posible que no exista ⋮ ⋮ ⋮
solución optima
Ejemplito Siempre se encuentra un
valor optimo mayor que el 𝒂𝒚 ≤ 𝒃𝒙 + 𝒄
m𝑎𝑥 𝑓(𝑥; 𝑦) = 𝑥 + 𝑦
anterior. ❖ 𝑥 = 𝑥0 ❖ 𝑦 = y0
no existe solución optima
𝑥 ≤ 𝑥0 𝑥 ≥ 𝑥0 𝑦 ≥ y0 𝑦 = y
(5; 2) 0
Teorema:
(8; 1) Si la región factible es 𝑦 ≤ y0
𝑥 = 𝑥0
acotada, entonces existen
Resolución el valor mínimo y máximo ❖ a ≤ 𝑥 ≤ 𝑏 ❖ a≤𝑦≤𝑏
Notar que la región es no de la función objetivo. 𝑦=𝑎
acotada, entonces podemos GRÁFICA DE LA
escoger infinitos puntos: REGIÓN FACTIBLE 𝑦=𝑏
𝑥=𝑎 𝑥=𝑏
Ejemplito Ejercicio: UNI 2018-I Variables costos
Hallar la 𝑦≥1 Se desea producir anillos de 𝑥: cant. Tipo A 𝑆/1500
región ቐ𝑥 + 𝑦 ≤ 10 dos tipos A y B. Para cada
𝑦: cant. Tipo B 𝑆/950
factible 𝑥≥2 unidad de anillo de tipo A se
Resolución empleará 3 g de oro y 1 g de Max 𝑧 = 1500𝑥 + 950𝑦
plata, y para el de tipo B se
Graficar: 𝑥 + 𝑦 ≤ 10 oro: 3 3𝑥
empleará 1 g de oro y 2 g de A
Graficar: 𝑥 ≥ 2
plata. Se venderán a S/ 1500 y plata: 1 𝑥
Graficar: 𝑦 ≥ 1
S/ 950 respectivamente cada 𝑦
oro: 1
unidad. Si se cuenta en almacén B
Región con 1800 g de oro y 2000 g de plata: 2 2𝑦
10 factible plata, ¿cuál será la función Restricciones
objetivo y las restricciones del Alancen con 1800 g de oro
1 problema de programación
lineal que permita maximizar la 3𝑥 + 𝑦 ≤ 1800
10
2 ganancia? Alancen con 2000 g de plata
Resolución 𝑥 + 2𝑦 ≤ 2000
Ejercicio Resolución 𝑥 = 4500
Variables costos 𝑥 + 𝑦 = 5000
Para recorrer toda la ciudad de 𝑥 + 𝑦 = 5000
3𝑦 = 𝑥
Machu Picchu, una compañía de 𝑥: # plazas T $30
transporte desea ofertar, como 𝑦: # Plazas P $40
máximo, 5000 plazas de dos tipos
“T” (turista) y “P” (primera). La Max 𝑍 = 30𝑥 + 40𝑦
(3750; 1250)
ganancia correspondiente a cada Restricciones
plaza de tipo “T” es de 30 Oferta como (4500; 500)
dólares, mientras que la ganancia máximo 5000 plazas (0; 0)
del tipo “P” es de 40 dólares. El 𝑥 + 𝑦 ≤ 5000 (4500; 0)
número de plazas del tipo “T” no
# plazas T no ✓ 𝑓 0; 0 = 0
excede de 4500 y el del tipo “P”
excede a 4500 ✓ 𝑓 3750; 1250 = 162500
debe ser como máximo, la tercera
parte de las del tipo “T” que 𝑥 ≤ 4500 ✓ 𝑓 4500; 500 = 155000
oferten. ¿Cuántas tienen que P debe ser como ✓ 𝑓 4500; 0 =135000 Solución
ofertarse de cada tipo para que la max la 1/3 de T 𝑥 = 3750 del tipo T optima
ganancia sea máxima? 𝑦 ≤ 𝑥/3 𝑦 = 1250 del tipo P 3750; 1250
Ejercicio Variables costos 2𝑥 + 𝑦 = 10
𝑥: # productos M 𝑆/.0,80
Un hospital planea elaborar un 𝟏𝟎 A
menú que contenga los productos 𝑦: # productos P 𝑆/.1,20
M y N. Cada onza de M Min 𝑍 = 0.8𝑥 + 1.2𝑦
proporciona una cantidad de 𝑥 B
A: 1 3; 4
vitamina A y dos unidades de B. M C
Cada onza de N suministra una B: 2 2𝑥 𝟓
unidad de vitamina A y una unidad 𝑦 Resolver :
A: 1
N 2𝑥 + 𝑦 = 10
de vitamina B. Los dos platillos B: 1 𝑦 𝑥+𝑦 =7
deben proporcionar por lo menos 7 Restricciones
unidades de vitamina A y por lo M y N: por lo menos 7 𝑓 3; 4 = 0.8 3 + 1.2(4) = 7.2
menos 10 unidades de vitamina B. unidades de vitamina A 𝑓 7; 0 = 0.8 7 + 1.2(0) = 5.6
Si cada onza de M cuesta S/.0,80 y
𝑥+𝑦 ≥7 𝑓 0; 10 = 0.8 0 + 1.2(10)
cada onza de N cuesta S/.1,20.
Determine el mínimo costo que M y N: por lo menos 10 = 12
puede tener el menú. unidades de vitamina B
Por lo tanto, el costo mínimo es
Resolución 2𝑥 + 𝑦 ≥ 10 S/.5,6