Copia de CLASE 17 1 - Patricia Torres

Vista previa del material en texto

TEMA
Programación lineal (parte I)
2021-2
17.1
PREUNIVERSITARIO
Contenido
La función objetivo:
Teorema de
invarianza
Teorema de existencia 
(de soluciones óptimas)
Teorema de 
monotonía
Método analíticoMétodo geométrico
Motivación:
Problema de Programación Lineal (PPL):
Región factible:
Teorema de separación (o descomposición)
I.
El plano cartesiano:
II.
III.
IV.
V.
Métodos para resolver un PPL:VI.
Teorema de convexidad
formulación matemática de una situación concreta
formulación
esbozo, estudio
estudio
Motivación:I. formulación matemática de una situación concreta
4
Una persona necesita en su dieta
alimenticia (de una semana), como
mínimo
Proteínas Hidratos Grasas
Un Kg de A 
contiene
2 unid. 6 unid. 1 unid.
Un Kg de B
contiene
1 unid. 1 unid. 3 unid.
Un Kg de A cuesta S/ 600 
Un Kg de B cuesta S/ 400
¿Cuantos kilogramos de cada producto deben comprarse
semanalmente para que el costo de preparar la dieta sea mínimo?
8 unidades de proteínas
12 unidades de hidratos de carbono
9 unidades de grasa. 
Esta dieta se obtiene mezclando los 
productos A y B. 
El contenido proteico y el costo por
kilogramo de cada uno de estos
productos es el que se muestra en
las tablas que se adjuntan.
5
𝐱 ≥ 0 ∧ 𝐲 ≥ 0
z(x, y) = 600x + 400y
Representan cantidades,
son no negativas, es decir:
𝐲
kilogramos del producto 
A que se deben comprar
kilogramos del producto B
que se deben comprar
𝐱 :
:
las(1) Identificamos variables.
función objetivo.(2) Identificamos la
En este caso se trata de una 
función costoz: ℝ
2 → ℝ
definida como
lo que se nos pide hacer con la función objetivo.(3) Identificamos
Se nos pide minimizarla
6
Proteínas Hidratos Grasas
Un Kg de A contiene 2 unid. 6 unid. 1 unid.
Un Kg de B contiene 1 unid. 1 unid. 3 unid.
Proteínas Hidratos Grasas
En x Kg de A hay 2x unid. 6x unid. x unid.
En y Kg de B hay y unid. y unid. 3y unid.
deducimos esta otra:
De la siguiente tabla (da en el enunciado del problema)
que existen entre las variables(4) Encontramos la relación
7
Proteínas Hidratos Grasas
En un preparado de x kilos de A y 
𝑦 kilo de B, respectivamente, hay:
2x + y unid. 6x + y unid x + 3y unid
las variables se relacionan
mediante las inecuaciones
2x + y ≥ 8 6x + y ≥ 12 x + 3y ≥ 9
Y, por ende, también esta otra
Pero por datos del problema:
“Las necesidades semanales 
mínimas de una persona” son:
8 
unidades 
proteínas
12 
unidades de 
hid.de carbono 
9 
unidades 
de grasa
Por tanto, 
8
𝐂
∀ x, y ∈ 𝐂 z x0, y0 ≤ z(x, y)
(x, y) = 600x + 400y
matemáticamente el problema que se nos pide resolver.(5) Formulamos
Deseamos encontrar
2x + y ≥ 8
6x + y ≥ 12
x + 3y ≥ 9
x ≥ 0
y ≥ 0
x0, y0
:
el (o los) punto(s) (𝑥, 𝑦) que
satisfaga(n) simultáneamente las
inecuaciones
De modo que
La función objetivo 
alcance un mínimo en
Es decir
𝐙 𝐙 ℝ
2 → ℝ:
𝐙
9
¿Cómo se grafica?
¿Cómo se comporta?
¿Siempre es posible encontrar un
punto en el conjunto C donde esta
alcance un mínimo (o un máximo)?
¿Es único este punto?
¿Existen métodos que permitan
determinar estos puntos?
¿Qué características tiene?
Con respecto al conjunto
Con respecto a la función
Nos planteamos algunas interrogantes
𝐂
𝐙
Motivación:
Problema de Programación Lineal (PPL):
I.
II.
formulación matemática de una situación concreta
formulación
11
una función z: ℝ2 → ℝ
un conjunto 𝐂, de puntos x, y ,
que verifican simultáneamente un
numero finito de las inecuaciones
lineales.
Definición: 
z(x, y) = a x b y+
función objetivo
Un problema de programación
lineal (PPL) en dos variables es
todo problema constituido por:
≤
>
⋮
≤
𝐚𝟏𝐱 + 𝐛𝟏𝐲
𝐚𝟐𝐱 + 𝐛𝟐𝐲
𝐚𝐧𝐱 + 𝐛𝐧𝐲
𝐜𝟏
𝐜𝟐
𝐜𝐧
sistema de
restricciones
Determinan en el plano
una región
variables 
de 
decisión
Cada par (𝐱, 𝐲) de la
región admisible
región factible o
admisible
solución factible o
admisible
llamada
se llama
se llaman
hallar el punto (o los puntos)
donde la función objetivo alcanza
su menor y/o mayor valor.
En todo PPL se desea 
12
Se dice que: 
solución optima 
mínimo
máximo
Valor
mínimo
máximo
de la función
∃ x0, y0 ∈ C tal que ∀ 𝐱, 𝐲 : 𝐳 x0, y0 ≤ 𝐳(𝐱, 𝐲)
≥
∈ C
∃ x0, y0 ∈ C tal que ∀ 𝐱, 𝐲 : 𝐳 x0, y0 𝐳(𝐱, 𝐲)∈ CMaximizar 
Minimizar
x0, y0 valor óptimo𝐳 x0, y0y
Punto donde la
función objetivo
alcanza un
es una es el
Hallar las soluciones óptimas que la
función objetivo
13
Ejemplo: 
Alcanza cuando se le restringe a la
región factible delimitada por las
inecuaciones
z x, y = x + 2y
3x + 4y ≤ 12
2x + y ≥ 2
x ≥ 0
y ≥ 0
Motivación:
Problema de Programación Lineal (PPL):
Teorema de separación (o descomposición)
I.
El plano cartesiano:
II.
III.
formulación matemática de una situación concreta
formulación
15
L = x, y ∈ ℝ2 |𝐚x + 𝐛y = c
𝐧 = 𝐚, 𝐛Se llama 
Definición:
a ≠ 0 o b≠ 0
es cualquier lugar geométrico constituido
por puntos (x, y) que satisfacen
ax + by = c
Esto es,
Una recta L en el plano cartesiano
vector normal
Su
característica
principal
forman 90 grados
sexagesimales con la recta
una ecuación de primer grado: 
16
ℝ2
Es una recta Es un semiplano
𝐱, 𝐲 |𝐚𝐱 + 𝐛𝐲 > 𝐜= 𝐱, 𝐲 | 𝐚𝐱 + 𝐛𝐲 < 𝐜 ∪ 𝐱, 𝐲 |𝐚𝐱 + 𝐛𝐲 = 𝐜 ∪
Es un semiplano
Está del lado a donde apunta
el vector −n = −a,−b
Está del lado a donde
apunta el vector n = a, b
Una recta L: ax + by = c tres partes disjuntas:divide al plano cartesiano en
(de separación o descomposición)Teorema
17
vector normal
Interpretación
geométrica
del
Teorema
de
separación
> 𝟎
𝐧 = (𝐚, 𝐛)
Cuadro (1)
18
Cuadro (2)
Cuadro (3)
vector normal
Interpretación geométrica
del Teorema de separación
> 𝟎
𝐧 = (𝐚, 𝐛)
19
Cuadro (4) Cuadro (5)
vector normal
Interpretación geométrica
del Teorema de separación
> 𝟎
𝐧 = (𝐚, 𝐛)
20
Cuadro (6) Cuadro (7)
Cuadro (8)
vector normal
Interpretación geométrica
del Teorema de separación
< 𝟎
𝐧 = (𝐚, 𝐛)
21
Demostremos lo que
atañe al cuadro
Esto hace que la recta
L: ax + by = c pueda
reescribirse como
Demostración
b ≠ 0
y = −
a
b
x +
c
b
Cuadro (1)
𝐧 = 𝐚, 𝐛 es tal que 𝐚 > 𝟎, 𝐛 > 𝟎
(b > 0)
22
𝐱, 𝐲 está en la dirección del vector 𝐧 = (𝐚, 𝐛)
𝐱, 𝐲 está en la dirección del vector −𝐧 = (−𝐚,−𝐛)
𝐛𝐲 < −𝐚𝐱 + 𝐜
𝐚𝐱 + 𝐛𝐲 < 𝐜
𝐛𝐲 > −𝐚𝐱 + 𝐜
𝐚𝐱 + 𝐛𝐲 > 𝐜
𝐲 > −
𝐚
𝐛
𝐱 +
𝐜
𝐛
𝐲 < −
𝐚
𝐛
𝐱 +
𝐜
𝐛
Motivación:
Problema de Programación Lineal (PPL):
Región factible:
Teorema de separación (o descomposición)
I.
El plano cartesiano:
II.
III.
IV. Teorema de convexidad
formulación matemática de una situación concreta
formulación
esbozo, estudio
La región factible
delimitada por las
inecuaciones lineales
24
Ejemplo: 
es la que se muestra en
video adjunto
3x + 4y ≤ 12
2x + y ≥ 2
x ≥ 0
y ≥ 0
Esbozar la región delimitada
por las inecuaciones lineales
25
Ejemplo 
Resolución: Graficamos por separado cada uno de los semiplanos
x + y ≥ 2
2x − y ≤ 4
Intersecando los semiplanos
obtenemos la región
conformada por todos
aquellos puntos que
satisfacen ambas
desigualdades
26
27
En el espacio euclídeo,
A + t B − A
Simbólicamente
Definición:
Ejemplo: 
Son conjuntos convexos
contenido en 𝐂 (i.e. no se escapa de 𝐂).
un conjunto 𝐂 se llama 
convexo cuando el segmento que une dos puntos cualesquiera de C está 
∀ A, B ∈ C : ∀ 0 ≤ t ≤ 1 ∈ C:
el conjunto vacío
ℝ𝟐 ℝ𝟑 ℝ𝟒
también
Teorema
Si 𝐂𝟏, 𝐂𝟐, … , 𝐂𝐧,
son convexos, entonces
𝐂𝟏 ∩ 𝐂𝟐 ∩⋯∩ 𝐂𝐧
también es convexo
Observación
La unión de conjuntos
convexos no siempre
es convexo
ℝ2 o ℝ3 o ℝ4 o … o ℝn
28
El Teorema no descarta que
dicha región sea el conjunto
vacío: recuerde que el vacío es
un conjunto convexo.
Teorema
Ejemplo: 
(convexidad de la región factible)
Este conjunto convexo puede
ser acotado o no acotado.
x + 3y ≥ 3
−x + y ≤ 1
En el plano cartesiano, toda región
delimitada por una cantidad finita
de Inecuacionesconjunto convexoes un 
La región 𝐂, delimitada por las 
inecuaciones:
 no acotado
 convexoes un conjunto:
La función objetivo:
Teorema de
invarianza
Teorema de existencia 
(de soluciones óptimas)
Teorema de 
monotonía
Motivación:
Problema de Programación Lineal (PPL):
Región factible:
Teorema de separación (o descomposición)
I.
El plano cartesiano:
II.
III.
IV.
V.
Teorema de convexidad
formulación matemática de una situación concreta
formulación
esbozo, estudio
estudio
30
=L
conjunto
recta
línea
nivel 
curva
de 
Se le llama
en aquellas rectas cuyo vector normal es n = a, b
Sea z x, y = ax + by una función objetivo. Entonces, esta se mantiene 
invariante (i.e. constante) 
Una recta de vector normal
(invarianza de la función objetivo) Teorema
x, y ∈ ℝ2 ax + by = 𝐜}
Observación:
n = a, b es de la forma
El valor constante a lo largo de toda esta recta es
Es decir:
𝐜
=𝐱, 𝐲 𝐳 x, 𝑦∈ L∀ 𝐜:
31
Ejemplo:
Teorema
32
Es decir :
y si fijamos una recta 
L1: ax + by = c1
y después de está,
siguiendo el sentido del
otra recta L2: ax + by = c2,
entonces
c1 < c2
z x, y = ax + by
si
(Monotonía de la función objetivo)
Una función objetivo crece en la dirección del vector normal que esta genera.
fijamos
vector normal n = (a, b), 
33
z x, y = 𝟏 x + y z x, y = 𝟎 𝒙 + y
z x, y = 𝟏 x + 0y
z x, y = 𝟏 x − y
z x, y = −𝟏 x + y
z x, y = −𝟏 x + 0y
z x, y = −𝟏 x − y z x, y = 𝟎 𝒙 − y
Ejemplo:
Estudiemos el comportamiento de cada una de las siguientes funciones 
objetivo.
34
en cada recta de vector normal
n = (1,1), es decir en cada recta
L: x + y = c.
a medida que las rectas de
desplazan en la dirección del
vector n = (1,1).
Se mantiene constante:
crece
𝐳 𝐱, 𝐲 = 𝟏 𝐱 + 𝐲
35
en cada recta de vector normal
n = (1,−1) , es decir en cada
recta L: x − y = c.
a medida que las rectas de
desplazan en la dirección del
vector n = (1,−1).
Se mantiene constante:
crece
𝐳 𝐱, 𝐲 = 𝟏 𝐱 − 𝐲
36
en cada recta de vector normal n = (1,0), es decir en cada recta L: x = c.
a medida que las rectas de desplazan en la dirección del vector n = (1,0).
Se mantiene constante:
crece
𝐳 𝐱, 𝐲 = 𝟏 𝐱 + 𝟎
37
en cada recta de vector normal n = (−1,1), es decir en cada recta de la
forma L:−x + 𝑦 = 𝑐.
a medida que las rectas de desplazan en la dirección del vector n = (−1,1).
Se mantiene constante:
crece
z x, y = −𝟏 x + y
38
en cada recta de vector
normal n = (−1,−1), es
decir en cada recta de la
forma L:−x − 𝑦 = 𝑐.
a medida que las rectas
de desplazan en la
dirección de
n = (−1,−1).
Se mantiene constante:
crece
z x, y = −𝟏 x − y
39
a medida que las rectas de
desplazan en la dirección del
vector normal n = (−1,0).
Se mantiene constante:
crece
z x, y = −𝟏 x + 0y
En cada recta de vector normal
n = (−1,0), es decir en cada recta
horizontal L: x = c
40
en cada recta de vector normal
n = (0,1), es decir en cada recta
horizontal L: 𝑦 = 𝑐.
a medida que las rectas de
desplazan en la dirección del
vector normal n = (0,1).
Se mantiene constante:
crece
z x, y = 𝟎 𝑥 + 𝑦
41
Se mantiene constante:
crece
𝐳 𝐱, 𝐲 = 𝟎 𝐱 − 𝐲
En cada recta de vector
normal n = (0,−1), es decir en
cada recta horizontal L: y = c
A medida que las rectas de
desplazan en la dirección del
vector normal n = (0,−1)
42
Teorema (existencia de soluciones óptimas)
un conjunto convexo y
z toma valores mínimos
y máximos en las
esquinas o arista de C.
C acotado
Sea z x, y = ax + by una 
función objetivo. Y sea C
delimitado por rectas.
un mínimo
es posible
un máximo y/o
No se descarta el hecho que el
mínimo y/o máximo
Se alcance en toda una
Si nos quedamos solo con esto
C acotadola condición
Es decir, si quitamos
no alcance
que la función objetivo
Pero
En el caso que
lo alcance
Esto se da en una
arista
esquina
O en toda una 
La función objetivo:
Teorema de
invarianza
Teorema de existencia 
(de soluciones óptimas)
Teorema de 
monotonía
Método analíticoMétodo geométrico
Motivación:
Problema de Programación Lineal (PPL):
Región factible:
Teorema de separación (o descomposición)
I.
El plano cartesiano:
II.
III.
IV.
V.
Métodos para resolver un PPL:VI.
Teorema de convexidad
formulación matemática de una situación concreta
formulación
esbozo, estudio
estudio
44
Planteamiento del Problema
 convexa
 acotada
determinar y/o identificar localizary/o los puntos donde
la función objetivo alcance un mínimo máximoy/o un
En la figura adjunta se aprecia una
región factible:  delimitada por rectas
Y sea z x, y = ax + by una función
objetivo definida en dicha región
AnalíticoExisten dos métodos: Geométrico
Deseamos
45
z(esquina1) z(esquina2)
z(esquina3)
z(esquina4)z(esquina5)
z(esquina6)
Método analítico
Teorema de existencia
Consiste en hacer del:
Evaluamos
la función objetivo en cada una 
de las esquina
comparamos
los valores obtenidos y vemos
cuál es el menor valor y cuál el
mayor.
46
Este consiste en hacer de los teoremas:
está en la dirección del vector n
y
de vector normal n = a, b
de modo que la región convexa 
quede contenida en el semiplano que 
la recta en la dirección del vector normal
Método geométrico
invarianza monotonía
una recta 
Trazamos
Desplazamos
El(los) primer(os) punto(s) de contacto,
entre la recta y la región, es (son)
donde la función alcanza un mínimo
El(los) último(s) punto de contacto,
entre la recta y la región, es(son)
donde la función alcanza su máximo
47
Ejemplo:
En la figura adjunta se muestra
una región convexa acotada
Y sobre esta región se considera
definida la función objetivo
z x, y = x + y
Determine los puntos de la región
donde la función alcanza un
mínimo o un máximo
48
 un mínimo en el punto 1,1
 un máximo en el punto 8,5
Resolución
z 0,4 = 4
z 1,1 = 2 z 7,2 = 9
z 8,5 = 13
z 2,6 = 8
z 0,4 = 4
 El valor mínimo es 2
 este valor máximo es 13
En cada una de las esquina
La función objetivo alcanza:
Método analítico
Evaluamos
comparamos
49
está en la dirección del vector n
una recta de vector normal n = 1,1
de modo que la región convexa 
quede contenida en el semiplano que 
la recta en la dirección del vector
Método geométrico
Trazamos
Desplazamos
Primer punto de corte 𝐏𝐦𝐢𝐧 = 𝟏, 𝟏 Último punto de corte 𝐏𝐦𝐚𝐱 = (𝟖, 𝟓)
En este punto la función objetivo
toma su menor valor z 1,1 = 2
En este punto la función objetivo
toma su mayor valor z 8,5 = 13
normal
Indicar el valor de verdad de las siguientes afirmaciones:
50
Ejercicio:
 En un P.P.L. la solución optima
de existir , es única.
 El conjunto unitario es convexo.