View
215
Download
0
Category
Preview:
Citation preview
Programación Lineal
Julio Yarasca
CEPREUNI
13 de diciembre de 2015
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 1 / 21
Introducción
Figura: George Dantzing
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 2 / 21
Conjunto Convexo
Conjunto Convexo
Un conjunto C ⊂ R2 es convexo si para cada par de puntos del conjunto, elsegmento que los une esta incluido en el conjunto.
x1
x2
x1
x2
Conjunto convexo Conjunto no convexo
CS
1
1C es convexo si dados dos puntos cualesquiera x1 y x2 en C , entonces λx1 + (1− λ)x2 ∈ Cpara todo λ ∈ [0, 1].
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 3 / 21
Conjunto Convexo
Conjunto Convexo
Un conjunto C ⊂ R2 es convexo si para cada par de puntos del conjunto, elsegmento que los une esta incluido en el conjunto.
x1
x2
x1
x2
Conjunto convexo Conjunto no convexo
CS
1
1C es convexo si dados dos puntos cualesquiera x1 y x2 en C , entonces λx1 + (1− λ)x2 ∈ Cpara todo λ ∈ [0, 1].
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 3 / 21
Propiedades de los conjuntos convexos
1 Si S ,T son conjuntos convexos, entonces S ∩ T es un conjunto convexo.
2 Si S1,S2, · · · ,Sn son conjuntos convexos, entonces
n⋂i=1
Si := S1 ∩ S2 ∩ · · · ∩ Sn
es un conjunto convexo.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 4 / 21
Propiedades de los conjuntos convexos
1 Si S ,T son conjuntos convexos, entonces S ∩ T es un conjunto convexo.
2 Si S1,S2, · · · ,Sn son conjuntos convexos, entonces
n⋂i=1
Si := S1 ∩ S2 ∩ · · · ∩ Sn
es un conjunto convexo.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 4 / 21
Unión?
Veamos que la unión de dos conjuntos convexos no necesariamente es un conjuntoconvexo, sean los conjuntos A y B
A B
claramente convexos pero tenemos que la unión A∪B, no es un conjunto convexo.
A ∪ B
x1 x2
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 5 / 21
Ejemplos
Ejemplo: Semiplano
El siguiente conjunto es un conjunto convexo
S ={(x , y) ∈ R2 / ax + by ≤ c
}
ax + by ≤ c
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 6 / 21
Ejemplos
Ejemplo: Semiplano
El siguiente conjunto es un conjunto convexo
S ={(x , y) ∈ R2 / ax + by ≤ c
}
ax + by ≤ c
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 6 / 21
Ejemplo: Poliedro
Sea U el conjunto solución del sistema de inecuacionesx + y ≤ 100x + 4y ≤ 160x + 2y ≤ 110
x ≥ 0y ≥ 0
es un conjunto convexo.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 7 / 21
Problema de Programación lineal
Un problema de programación lineal PPL (en dos variables) consiste en maximizaro minimizar (es decir, optimizar) una función f (llamada función objetivo) de laforma
z = f (x , y) = ax + by
sujeta a las restricciones (�s.a�)
(1)
a1x + b1y ≤ c1a2x + b2y ≤ c2
...anx + bny ≤ cn
y
(2)
{x ≥ 0y ≥ 0
llamadas restricciones de vínculo y de no negatividad, respectivamente, alconjunto solución de (1) y (2) se le conoce como región admisible.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 8 / 21
Ejemplo
Sea el PPLmáx f (x , y) = 4x + ys.a
x + y ≤ 6−x + 2y ≤ 8
x ≥ 0y ≥ 0
Gra�que la región admisible.
(6, 0)
(43 ,
143
)(0, 6)
(0, 0)
región admisible
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 9 / 21
Ejemplo
Sea el PPLmáx f (x , y) = 4x + ys.a
x + y ≤ 6−x + 2y ≤ 8
x ≥ 0y ≥ 0
Gra�que la región admisible.
(6, 0)
(43 ,
143
)(0, 6)
(0, 0)
región admisible
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 9 / 21
Puntos del conjunto admisible
Una solución factible o admisible de un PPL, es todo par ordenado (x , y)que pertence a la región admisible.
Una solución óptima de un PPL, es una solución factible que optimiza lafunción objetivo.
Si (x0, y0) es una solución óptima de un PPL, f (x0, y0) es llamado valor
óptimo.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 10 / 21
Teorema
Teorema Fundamental de la Programación Lineal
Si un PPL tiene valor óptimo, tal valor es alcanzado por lo menos en un vértice dela región admisible; y si este valor óptimo se alcanza en dos vértices A,B tal valorse logra en todo el segmento de extremos A y B.
Este teorema nos brinda una herramienta para poder resolver los problemas deprogramación lineal.
Método Analítico
Consiste basicamente de dos pasos
1 Gra�car la región admisible y encontrar los vertices.
2 Evaluar la función objetivo en cada vertice y encontrar cual maximiza ominimiza la función.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 11 / 21
Teorema
Teorema Fundamental de la Programación Lineal
Si un PPL tiene valor óptimo, tal valor es alcanzado por lo menos en un vértice dela región admisible; y si este valor óptimo se alcanza en dos vértices A,B tal valorse logra en todo el segmento de extremos A y B.
Este teorema nos brinda una herramienta para poder resolver los problemas deprogramación lineal.
Método Analítico
Consiste basicamente de dos pasos
1 Gra�car la región admisible y encontrar los vertices.
2 Evaluar la función objetivo en cada vertice y encontrar cual maximiza ominimiza la función.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 11 / 21
Ejemplo
Sea el PPLmáx f (x, y) = 4x + ys.a
x + y ≤ 100x + 4y ≤ 160x + 2y ≤ 110x ≥ 0, y ≥ 0
La región admisible es
(100, 0)
(90, 10)
(60, 25)
(0, 40)
(0, 0)
Region Admisible
vértices (x, y) f(x,y)=4x+y(0; 0) 0(0; 40) 40(60; 25) 265(90; 10) 360(100; 0) 400
Por lo tanto el máximo se obtiene en el punto (100, 0)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 12 / 21
Ejemplo
Sea el PPLmáx f (x, y) = 4x + ys.a
x + y ≤ 100x + 4y ≤ 160x + 2y ≤ 110x ≥ 0, y ≥ 0
La región admisible es
(100, 0)
(90, 10)
(60, 25)
(0, 40)
(0, 0)
Region Admisible
vértices (x, y) f(x,y)=4x+y(0; 0) 0(0; 40) 40(60; 25) 265(90; 10) 360(100; 0) 400
Por lo tanto el máximo se obtiene en el punto (100, 0)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 12 / 21
Ejemplo
Sea el PPLmáx f (x, y) = 4x + ys.a
x + y ≤ 100x + 4y ≤ 160x + 2y ≤ 110x ≥ 0, y ≥ 0
La región admisible es
(100, 0)
(90, 10)
(60, 25)
(0, 40)
(0, 0)
Region Admisible
vértices (x, y) f(x,y)=4x+y(0; 0) 0(0; 40) 40(60; 25) 265(90; 10) 360(100; 0) 400
Por lo tanto el máximo se obtiene en el punto (100, 0)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 12 / 21
Región acotada
Región admisible acotada
Una región admisible es acotada si alrededor del origen existe una cirfunferenciaque lo contenga.
Sea el PPL
máx f (x , y) = 4x + ys.a
x + y ≤ 6−x + 2y ≤ 8
x ≥ 0y ≥ 0
(6, 0)
(4
3,14
3
)(0, 6)
(0, 0)
Región admisible acotada
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 13 / 21
Sea el PPL
máx f (x , y) = 4x + ys.a
4y − x ≤ 32−x + 2y ≤ 12
x ≥ 0y ≥ 0
Región admisible no acotada(0,6)
(8,10)
(0,0)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 14 / 21
Teorema
Teorema de representación
En un PPL si la región admisible es no vacía entonces el conjunto de sus vérticeses un conjunto no vacío y �nito.
Como cololario tenemos
1 En un PPL si la región admisible es acotada y no vacía, entonces el problematiene solución.
Propiedad
Sobre cualquier región admisible tenemos
máximo ax + by = −mínimo − (ax + by)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 15 / 21
Método geométrico
Sea el problema máx F (x , y) = ax + by sobre cualquier región admisible.
1 Gra�camos la región admisible.
2 Gra�camos la rectas ax + by = k y las movemos en la direción (a, b) tantocomo sea posible .
En caso de un problema de minimización las rectas las movemos tanto como seaposible en la direción (−a,−b), es decir en la direción opuesta.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 16 / 21
Ejemplo
Sea el problema
máx f (x , y) = x + 2ys.a
x − 2y ≥ −10x + 4y ≤ 10
x ≥ 0y ≥ 0
Entonces la región admisible es:
(100, 0)
(90, 10)
(65, 25)
(0, 40)
(0, 0)
(5, 0)
(2, 6)
(0, 5)
región admisible
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 17 / 21
Ejemplo
Sea el problema
máx f (x , y) = x + 2ys.a
x − 2y ≥ −10x + 4y ≤ 10
x ≥ 0y ≥ 0
Entonces la región admisible es:
(100, 0)
(90, 10)
(65, 25)
(0, 40)
(0, 0)
(5, 0)
(2, 6)
(0, 5)
región admisible
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 17 / 21
Gra�camos las rectas x + 2y = z y la movemos hasta en la direción2 (1, 2) tantocomo sea posible.
(100, 0)
(90, 10)
(65, 25)
(0, 40)
(5, 0)
(2, 6)
(0, 5)
(0, 0)
(1, 2)
Por lo tanto la solución es el punto (2, 6)
2En el caso de un problema de minimización es en la dirección opuesta.Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 18 / 21
Otra forma
1 Gra�camos la región admisible.
2 Gra�camos la rectas con dirección (−b, a) que pasan por los puntosextremos3.
3 Se observa en qué vértice la función objetivo se hace máxima (o mínima) soloteniendo en cuenta cuál de las rectas corta en un punto mayor (o menor) aleje y.
3Es decir, sea (x0, y0) una punto extremo, gra�camos la recta ax + by = ax0 + byoJulio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 19 / 21
Ejemplo
En el problema anterior
máx f (x , y) = x + 2ys.a
x − 2y ≥ −10x + 4y ≤ 10
x ≥ 0y ≥ 0
(100, 0)
(90, 10)
(65, 25)
(0, 40)
(0, 0)
(−2, 1)
(5, 0)
(2, 6)
(0, 5)
(0, 7)
(0, 2,5)
Por lo tanto
la solución es (2, 6)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 20 / 21
Ejemplo
En el problema anterior
máx f (x , y) = x + 2ys.a
x − 2y ≥ −10x + 4y ≤ 10
x ≥ 0y ≥ 0
(100, 0)
(90, 10)
(65, 25)
(0, 40)
(0, 0)
(−2, 1)
(5, 0)
(2, 6)
(0, 5)
(0, 7)
(0, 2,5)
Por lo tanto
la solución es (2, 6)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 20 / 21
Bibliografía
1 Programación y �ujos de redes, Mokhtar Bazaraa.
2 Que es la programación lineal, Barsov.
3 Técnicas de Cálculo para Sistemas de Ecuaciones, Programación Lineal yProgramación Entera, Jose Luis de la Fuente O'Connor.
Gracias por su tiempo.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 21 / 21
Bibliografía
1 Programación y �ujos de redes, Mokhtar Bazaraa.
2 Que es la programación lineal, Barsov.
3 Técnicas de Cálculo para Sistemas de Ecuaciones, Programación Lineal yProgramación Entera, Jose Luis de la Fuente O'Connor.
Gracias por su tiempo.
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 21 / 21
Recommended