Programación lineal

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

Introducción a la 
programación lineal
ÁLGEBRA
Docente: José Luis Vásquez Carhuamaca 
Semana 40
- ÁLGEBRA
Objetivos:
 Conocer la estructura de un problema de
programación lineal.
 Resolver problemas de programación
lineal.
 Resolver problemas aplicativos con el
marco teórico desarrollado.
- ÁLGEBRA
ÍNDICE
1. Reduciendo los costos en la segunda guerra mundial
3. Estructura de un problema de programación lineal
4. Definiciones y teorema
2. Nociones básicas
5. Problemas diversos
- ÁLGEBRA
Reduciendo los costos en la segunda guerra mundial
La programación lineal estudia el problema de optimizar una función lineal
en presencia de inecuaciones lineales.
Luego de la segunda guerra mundial se evidenció la importancia de la
planificación y organización de proyectos, así como el uso eficaz de los
recursos disponibles.
Un episodio llamativo de esta época, se dio durante la Guerra Fría a
mediados del año 1948, cuando la Unión Soviética inicia el bloqueo de las
comunicaciones terrestres en Berlín, teniendo que ser abastecida por vía
aérea. Se planteaba un problema de abastecimiento muy difícil y donde
había que elegir con buen criterio los productos que debían llegar y en que
orden. Este problema logístico fue el primer gran problema de Programación
Lineal de la historia.
- ÁLGEBRA
NOCIONES PREVIAS
Grafique 
𝑥 + 𝑦 ≤ 3
2𝑥 + 3𝑦 ≥ 6
𝑥 ≥ 0; 𝑦 ≥ 0
3
3
𝑥 𝑦
0
0
𝑥 + 𝑦 = 3
Resolución:
3 𝑋
𝑌
3
Gráfica de relaciones definidas por un sistema de
inecuaciones lineales.
2
3
𝑥 𝑦
0
0
2𝑥 + 3𝑦 = 6
3 𝑋
𝑌
3
3 𝑋
𝑌
2
𝟐𝒙 + 𝟑𝒚 ≥ 𝟔
2
Intersecamos las gráficas considerando la
condición de 𝑥 ≥ 0, 𝑦 ≥ 0
3 𝑋
𝑌
3
2
primer cuadrante
Luego
- ÁLGEBRA
Un problema de programación lineal tiene como
finalidad el minimizar o maximizar una función
lineal
máx. mín. 𝑓 𝑥; 𝑦 = 𝑎𝑥 + 𝑏𝑦
sujeto a (s.a.): 
𝑎1𝑥 + 𝑏1𝑦 ≤ 𝑐1
𝑎2𝑥 + 𝑏2𝑦 ≥ 𝑐2
𝑎𝑛𝑥 + 𝑏𝑛𝑦 ≤ 𝑐𝑛
𝑥 ≥ 0; 𝑦 ≥ 0
⋮
𝐅𝐮𝐧𝐜𝐢ó𝐧
𝐨𝐛𝐣𝐞𝐭𝐢𝐯𝐨
𝐂𝐨𝐧𝐣𝐮𝐧𝐭𝐨 𝐝𝐞
𝐫𝐞𝐬𝐭𝐫𝐢𝐜𝐜𝐢𝐨𝐧𝐞𝐬
∗ condición de
no negatividad
 
𝑥 + 𝑦 ≤ 5
2𝑥 + 3𝑦 ≤ 12
𝑥 ≥ 0; 𝑦 ≥ 0
Ejemplos:
máx. 𝑓 𝑥; 𝑦 = 2𝑥 + 4𝑦
Sujeto a: 
5 𝑋
𝑌
5
4
6
 
𝑥 + 𝑦 ≥ 4
2𝑥 + 5𝑦 ≥ 10
𝑥 ≥ 0; 𝑦 ≥ 0
mín. 𝑓 𝑥; 𝑦 = 5𝑥 + 3𝑦
Sujeto a: 
4 𝑋
𝑌
2
4
5
La gráfica del conjunto de restricciones es
llamada región factible.
… ∗
𝕊
𝕊
Región factible
Región factible
Observación:
Estructura de un problema de PL:
PROGRAMACIÓN LINEAL
.
.
.
.
.
.
- ÁLGEBRA
• Punto factible: Es todo punto que pertenece a
la región factible.
• Solución óptima: Es aquel punto
perteneciente a la región factible que
maximiza o minimiza a la función objetivo.
• Valor óptimo: Es el máximo o mínimo valor
que adquiere la función objetivo .
𝑋
𝑌
Punto extremo
(vértice) 
Punto
interior
𝐎𝐛𝐬𝐞𝐫𝐯𝐚𝐜𝐢ó𝐧:
Definiciones:
Teorema fundamental de la programación lineal
máx. o mín. de𝑓 𝑥; 𝑦 ocurre en 𝐴, 𝐵, 𝐶 o 𝐷
𝑋
𝑌
𝐴
𝐵
𝐶
𝐷
Si un problema de Programación Lineal tiene
región factible no vacía, entonces, si existe el
óptimo (máximo o mínimo) de la función
objetivo, esta se encuentra en un punto extremo
(vértice) de la región factible.
- ÁLGEBRA
Resuelva máx. 𝑓 𝑥; 𝑦 = 3𝑥 + 4𝑦
s.a. 
𝑥 + 𝑦 ≤ 15
2𝑥 + 3𝑦 ≤ 36
𝑥 ≥ 0; 𝑦 ≥ 0
Resolución:
1) Grafique la región factible y halle las
coordenadas de los puntos extremos.
15
15
𝑥 𝑦
0
0
𝑥 + 𝑦 = 15
12
18
𝑥 𝑦
0
0
2𝑥 + 3𝑦 = 36
15 𝑋
𝑌
15
18
𝑋
𝑌
12
Intersecamos las regiones anteriores,
considerando la condición de 𝑥 ≥ 0, 𝑦 ≥ 0 I C
15
𝑋
𝑌
15
12
18 𝐷 15; 0
𝑋
𝑌
𝐵 0; 12
𝐴 0; 0
𝑥 + 𝑦 = 15
2𝑥 + 3𝑦 = 36
𝐶 9; 6
𝑥 = 9; 𝑦 = 6
2) Evaluamos cada uno de los vértices en la
función objetivo. 𝑓 𝑥; 𝑦 = 3𝑥 + 4𝑦
𝑓 0; 0 = 3 0 + 4 0 = 0
𝑓 𝐵 = 𝑓 0; 12 = 3 0 + 4 12
𝑓 9; 6 = 3 9 + 4 6
𝑓 15; 0 = 3 15 + 4 0
𝑓 𝐴 =
𝑓 𝐶 =
𝑓 𝐷 =
= 48
= 51
= 45
← máx.
∴ máx. 𝑓 𝑥; 𝑦 = 𝑓 𝟗; 𝟔 = 𝟓𝟏
𝕊
← valor óptimo
solución óptima
 
www.adun i . e d u . p e