Embed Size (px)
Citation preview
UNIDAD II
PROGRAMACIÓN ENTERA Y CUADRÁTICA
PROGRAMACIÓN CUADRÁTICA
Ahora la función objetivo f(x) debe ser cuadrática; esta incluye variables cuadráticas o el
producto de 2 variables.
CONOCIMIENTOS PREVIOS
La pendiente de una recta.- esta representa el grado de inclinación de una recta.
𝑚 =𝑌2−𝑌1
𝑋2−𝑋1 𝑚 = tan ∝= 𝑦1
La distancia entre dos puntos.-
𝑑2 = (𝑥2 − 𝑥1)2 + (𝑦2 − 𝑦1)2
La distancia de un punto a la recta
𝑑 = |𝑎𝑥 + 𝑏𝑦 + 𝑐
√𝑎2 + 𝑏2
CÓMO RECONOCER UNA ECUACIÓN DE LA CIRCUNFERENCIA,
LA HIPÉRBOLE, ELIPSE Y PARÁBOLA
ECUACIÓN DE LA CIRCUNFERENCIA
Esta se reconoce porque tiene dos variables elevadas al cuadrado con un mismo coeficiente; se
representa por: (𝑋1 − ℎ)^2 + (𝑋2 − 𝑘)^2
EJEMPLO 1:
𝑿𝟐 + 𝟑𝑿 + 𝒀𝟐 − 𝟓𝒀 = 𝟑
(𝑥2 + 3𝑥 +9
4) + (𝑦2 − 5𝑦 +
25
4) = 3 +
9
4+
25
4
(𝑥 +3
2)
2
+ (𝑦 −5
2)
2
= 23
2
Centro 𝐶 = (−3
2;
5
2)
Radio 𝑅 = (23√2
2)
EJEMPLO 2:
𝟐𝑿𝟐 + 𝟐𝒀𝟐 = 𝟕
𝑋2 + 𝑌2 = 3.5
𝐶 = (0; 0)
𝑅 = √3.5
𝑅 = 1.87
Ecuación de la elipse
A diferencia de la ecuación que representa una circunferencia, en la elipse los coeficientes de los
cuadrados son diferentes.
Las curvas que más se utilizan en I.O. son la circunferencia y la elipse.
ECUACIÓN DE LA HIPÉRBOLE
Cuando la ecuación tiene signo negativo representa una hipérbole.
ECUACIÓN DE LA PARÁBOLA
Se da cuando tengo una variable cuadrática y una lineal.
Ejemplo:
2𝑥2 + 3𝑥 + 𝑦 = 7
EJEMPLO 1:
2𝑥2 + 3𝑦2 = 8
2𝑥2
8+
3𝑦2
8=
8
8
√𝑥2
4+ √
𝑦2
83
= 1
𝑥 = ±2
𝑦 = ±1.6
EJEMPLO 2:
5𝑥2 + 7𝑦2 = 11
5𝑥2
11+
7𝑦2
11=
11
11
√𝑥2
115
+ √𝑦2
117
= 1
𝑥 = ±1.5
𝑦 = ±1,3
EJEMPLO 2
𝑦 = 7 − 2𝑥2 − 3𝑥
Ahora, para saber hacia dónde se abre la parábola, debo asignar valores a x y a y:
Programación cuadrática es el nombre que recibe un procedimiento que minimiza una función
cuadrática de n variables sujetas a m restricciones lineales de igualdad o desigualdad.
EJERCICIO 1
Minimizar 𝒛 = (𝒙𝟏 − 𝟐)𝟐 + (𝒙𝟐 − 𝟐)𝟐
s.a 𝑥1 + 2𝑥2 ≤ 3
8𝑥1 + 5𝑥2 ≥ 10
𝑥𝑖 ≥ 0
Resolución:
1.- En este caso puedo determinar las coordenadas del centro de la circunferencia:
𝑪 = (𝟐; 𝟐)
2.- Resuelvo las restricciones y gráfico:
𝒙𝟏 + 𝟐𝒙𝟐 = 𝟑
X1 X2
0 3/2
3 0
x Y
-3 -2
-2 5
-1 8
0 7
1 2
2 -7
3 -20
GRÁFICO PARÁBOLA
(3;1.5)
0≤3 Verdadero
𝟖𝒙𝟏 + 𝟓𝒙𝟐 = 𝟏𝟎
X1 X2
0 2
5/4 0
(1.25;2)
0≥10 Falso
3.- Calculo la pendiente (m) de la recta cuyo punto esté más cercano al origen, despejando en la
ecuación de la recta que está alejada.
𝑥1 + 2𝑥2 = 3
𝑥2 =−𝑥1 + 3
2
𝑥2 = −1
2𝑥1 +
3
2
𝑚1 = −1
2
𝒎𝟏 ∗ 𝒎𝟐 = −𝟏
−1
2∗ 𝑚2 = −1
𝑚2 = 2 4.- Reemplazo en la ecuación de la recta, la pendiente (de la recta cercana al origen) hallada y
los puntos centro de la ecuación (de circunferencia) dada.
𝒚 − 𝒚𝟏 = 𝒎(𝒙 − 𝒙𝟏)
𝑦 − 2 = 2(𝑥 − 2)
𝑥2 − 2 = 2(𝑥1 − 2)
𝑥2 − 2 = 2𝑥1 − 4
−2𝑥1 + 𝑥2 = −2
2𝑥1 − 𝑥2 = 2
5.- Despejo por eliminación:
2𝑥1 − 𝑥2 = 2
(-2) 𝑥1 + 2𝑥2 = 3
2𝑥1 − 𝑥2 = 2
−2𝑥1 − 4𝑥2 = −6
−5𝑥2 = −4
𝒙𝟐 = 𝟒/𝟓
2𝑥1 −4
5= 2
𝑥1 =2 +
45
2
𝒙𝟏 =𝟕
𝟓
Los puntos resaltados se dibujan en el plano y representan el punto que minimiza la función. La
circunferencia debe tocar en este punto.
Para graficar la circunferencia, calculo la distancia desde el punto centro a la recta (basado en la
nueva ecuación para la recta más cercana al origen) y obtengo el valor de mi radio.
𝑑 = |𝑎𝑥+𝑏𝑦+𝑐
√𝑎2+𝑏2 𝑑 = |
2(2)+(−1)(2)+2
√22+22 𝑑 = |
4
√8 𝑑 = |1.41
6.- Reemplazar en Z
𝑧 = (7
5− 2)
2
+ (4
5− 2)
2
𝑧 = 1.8
EJECICIO 2
Minimizar 𝒁 = −𝟔𝒙𝟏 − 𝟏𝟑𝒙𝟐 − 𝒙𝟏𝒙𝟐 − 𝟒𝒙𝟏𝟐 − 𝟒𝒙𝟐
𝟐
s.a 𝑥2 + 𝑥3 = 20
𝑥1 + 𝑥2 + 𝑥4 = 23
𝑥1 ≥ 0
Resolución:
𝒙𝟑 = 0
𝒙𝟒 = 0
𝒙𝟐 = 20
𝒙𝟏 + 𝒙𝟐 + 𝒙𝟒 = 𝟐𝟑
𝒙𝟏 + 20 + 0 = 23
𝒙𝟏 = 3
𝑍 = −6(3) − 13(20) − 3(20) − 4(3)2 − 4(202)
𝑍 = 1974
EJERCICIO 3
Minimizar 𝒁 = (𝒙𝟏 − 𝟔)𝟐 + (𝒙𝟐 − 𝟖)𝟐
S.a. 𝑥1 ≤ 7
𝑥2 ≤ 5
𝑥1 + 2𝑥2 ≤ 12
𝑥1 + 𝑥2 ≤ 9
𝑥𝑖 ≥ 0
Desarrollo
𝒙𝟏 = 7
𝒙𝟐 = 5
𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟐
X1 X2
0 6
12 0
(12; 6)
0≤12 Verdadero
𝒙𝟏 + 𝒙𝟐 = 𝟗
X1 X2
0 9
9 0
(9;9)
0≤9 Verdadero
𝑑 = |𝑎𝑥+𝑏𝑦+𝑐
√𝑎2+𝑏2 𝑑 = |
1(6)++2(8)(2)−12
√12+22 𝑑 = |
10
√5 𝑑 = |4.47
(𝑋1 − ℎ)2 + (𝑋2 − 𝑘)2 = 𝑅
(𝑋1 − 6)2 + (𝑋2 − 8)2 = (10
√5)
2
Despejo 𝑋1 de 𝑥1 + 2𝑥2 = 12
𝑥1 = −2𝑥2 + 12 .- Reemplazo en la ecuación de la circunferencia:
(−2𝑥2 + 12 − 6)2 + (𝑋2 − 8)2 = 20
(6 − 2𝑥2)2 + (𝑋2 − 8)2 = 20
36 − 4𝑥2 + 4𝑥2 + 𝑥2 − 16𝑥2 + 64 − 20 = 0
5𝑥22 − 20𝑥2 + 80 = 0
5𝑥22 − 20𝑥2 + 80 = 0
5
𝑥22 − 4𝑥2 + 16 = 0
(𝑥2 − 4)^2 = 0 𝑥2 = 4 𝑥1 = 12 − 8 𝑥1 = 4
EJERCICIO 5
MAXIMIZAR 𝑍 = (𝑋 − 3)2 + (𝑌 − 1)2
S.a. 2𝑋 + 𝑌 ≤ 2
𝑋 + 3𝑌 ≤ 3
𝑌 ≤ 4
C= (3,1)
2𝑋 + 𝑌 ≤ 2
X Y
0 2
1 0
(1,2) Verdadero
𝑋 + 3𝑌 ≤ 3
X Y
0 1
3 0
(3,1) Verdadero
Y=4 Verdadero
𝑑 = |𝑎𝑥+𝑏𝑦+𝑐
√𝑎2+𝑏2 𝑑 = |
2(3)+1(1)−2
√4+1 𝑑 = |
5
√5 𝑑 = |2.24
(𝑋 − 3)2 + (𝑌 − 1)2 = (5
√5)
2
2𝑋 + 𝑌 = 2
𝑌 = 2 − 2𝑋
(𝑋 − 3)2 + (2 − 2𝑋 − 1)2 = 5
𝑋2 − 6𝑋 + 9 + (1 − 2𝑋)2 = 5
𝑋2 − 6𝑋 + 9 + 1 − 4𝑋 + 4𝑋2 − 5 = 0
5𝑋2 − 10𝑋 + 5 = 0
5
𝑋2 − 2𝑋 + 1 = 0
(𝑋 − 1)^2 =0
𝑿 = 𝟏
𝑌 = 2 − 2(1) 𝒀 = 𝟎
EJERCICIO 6
MINIMIZAR 𝒇(𝒙) = 𝒙𝟐 + 𝟐𝒙 − 𝟑 Representa la ecuación de una parábola
Para hallar el vértice en X 𝑉𝑋 =−𝑏
2𝑎 𝑉𝑋 =
−2
2(1) 𝑉𝑋 = −1
Para hallar el vértice en Y 𝑉𝑌 = (−1)2 + (2)(−1) − 3
𝑉𝑌 = −4
Vértice de la parábola (-1,-4)
Puntos de corte para f(x) o y; x=0
𝑓(𝑥) = 𝑥2 + 2𝑥 − 3
𝑓(𝑥) = 02 + 2(0) − 3
𝑓(𝑥) = −3 Punto de corte (0,-3)
Punto de corte para x; f(x)=0
𝑜 = 𝑥2 + 2𝑥 − 3
𝑥2 + 2𝑥 − 3 = 0
(𝑥 + 3)(𝑥 − 1) = 0
𝑥1 = −3
𝑥2 = 1
ALGORITMO DE RAMIFICACIÓN Y ACOTAMIENTO
Este método se aplica para obtener soluciones enteras.
𝑥 ≤ ⟦𝑎⟧ 𝑥 ≥ ⟦𝑎⟧ + 1
⟦−3,5⟧ = −4
⟦−3,8⟧ = −4
⟦−3,2⟧ = −4
⟦2,5⟧ = 2
⟦2,8⟧ = 2
⟦2,1⟧ = 2
La parte entera es el número que no excede al número dado.
En esta técnica al maximizar encontramos el menor valor, y
Al minimizar encontramos el mayor valor.
ALGORITMO DE BRANCH AND BOUND (RAMIFICACIÓN Y
ACOTAMIENTO)
Es un algoritmo diseñado para la resolución de modelos de programación entera, sin embargo, es
muy frecuente que la naturaleza del problema nos indique que las variables son enteras o
binarias. Su operatoria consiste en resolver este como si fuese un modelo de programación lineal
y luego generar cotas en caso que al menos una variable de decisión adopte un valor
fraccionario. El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que
favorecen la obtención de valores enteros para las variables de decisión.
En este contexto resolver el modelo lineal asociado a un modelo de programación entera se
conoce frecuentemente como resolver la relajación continua del modelo entero.
EJERCICIO 1:
MAIMIZAR 𝒁 = 𝟑𝑿𝟏 + 𝟒𝑿𝟐
2𝑋1 + 𝑋2 ≤ 6
2𝑋1 + 3𝑋2 ≤ 9
- 0 +
𝑋𝑖 ≥ 0; 𝑒𝑛𝑡𝑒𝑟𝑜𝑠
DESARROLLO
2𝑋1 + 𝑋2 ≤ 6
X y
0 6
3 0
2𝑋1 + 3𝑋2 ≤ 9
x y
0 3
9/2 0
C= (3, 3/2)
Resolver las ecuaciones por eliminación:
(-1) 2𝑋1 + 𝑋2 = 6
2𝑋1 + 3𝑋2 = 9
- 2𝑋1 − 𝑋2 = −6
2𝑋1 + 3𝑋2 = 9
2𝑋2 = 3
𝑋2 =3
2 𝑋2 = 1,5 𝑍 = 3𝑋1 + 4𝑋2 𝑍 = 12,75
Solución óptima o problema relajado
SOLUCIÓN ENTERA Z=12; X1=0 X2=3
Cotas:
𝑍 = 12 𝑋1 = 0 𝑋2 = 3
𝑍 = 10 𝑋1 = 1 𝑋2 = 2
𝑍 = 12,2 𝑋1 = 1
𝑋2 = 2,3
𝐼𝑛𝑓𝑎𝑐𝑡𝑖𝑏𝑙𝑒
𝑍 = 10 𝑋1 = 2 𝑋2 = 1
𝑍 = 12,5 𝑋1 = 1,5 𝑋2 = 2
𝑍 = 12,8 𝑋1 = 2
𝑋2 = 1,7
𝑍 = 9 𝑋1 = 3 𝑋2 = 0
𝒁 = 𝟏𝟐, 𝟕𝟓 𝑿𝟏 = 𝟐, 𝟐𝟓 𝑿𝟐 = 𝟑, 𝟐
2𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 2
2𝑋1 + 3𝑋2 ≤ 9 𝑋2 ≤ 1,7
𝑋1 ≤ 2 𝑋1 = 2
𝑋2 = 1,7
2𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 0 𝑋2 = 0
2𝑋1 + 3𝑋2 ≤ 9 𝑋2 ≤ 1
𝑋1 ≥ 3
𝑋1 = 3
𝑋2 = 0
X1≤2 X1≥3
X2≤1 X2≥2
X1≤1 X1≥2
X2≤2 X2≥3
2𝑋1 + 𝑋2 ≤ 6 𝑋1 ≤ 2,5
2𝑋1 + 3𝑋2 ≤ 9 𝑋1 ≤ 3
𝑋1 ≤ 2
𝑋2 ≤ 1
𝑋2 = 1
𝑋1 = 2
2𝑋1 + 𝑋2 ≤ 6 𝑋1 ≤ 2
2𝑋1 + 3𝑋2 ≤ 9 𝑋1 ≤ 1,5
𝑋1 ≤ 2
𝑋2 ≥ 2
𝑋2 = 2
𝑋1 = 1,5
2𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 4 2𝑋1 + 3𝑋2 ≤ 9 𝑋2 ≤ 2,3
𝑋1 ≤ 2
𝑋2 ≥ 2
𝑋1 ≤ 1
𝑋1 = 1
𝑋2 = 2,3
2𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 2
2𝑋1 + 3𝑋2 ≤ 9 𝑋2 ≤ 1,7
𝑋1 ≤ 2
𝑋2 ≥ 2
𝑋1 ≥ 2
𝑋1 = 2
𝑋2 = 1
INFACTIBLE
2𝑋1 + 𝑋2 ≤ 6 𝑋1 ≤ 2
2𝑋1 + 3𝑋2 ≤ 9 𝑋1 ≤ 1,5
𝑋1 ≤ 2
𝑋2 ≥ 2
𝑋1 ≤ 1
𝑋2 ≤ 2
𝑋2 = 2
𝑋1 = 1
2𝑋1 + 𝑋2 ≤ 6 𝑋1 ≤ 1,5
2𝑋1 + 3𝑋2 ≤ 9 𝑋1 ≤ 0
𝑋1 ≤ 2
𝑋2 ≥ 2
𝑋1 ≤ 1
𝑋2 ≤ 3
𝑋2 = 3
𝑋1 = 0
EJERCICIO 2
MINIMIZAR 𝒁 = −𝟓𝑿𝟏 − 𝟖𝑿𝟐
𝑋1 + 𝑋2 ≤ 6
5𝑋1 + 9𝑋2 ≤ 45
𝑋𝑖 ≥ 0; 𝑒𝑛𝑡𝑒𝑟𝑜𝑠
𝑋1 + 𝑋2 ≤ 6
𝑋1 = 6
𝑋2 = 6
5𝑋1 + 9𝑋2 ≤ 45
X Y
0 5
9 0
−5𝑋1 − 5𝑋2 ≤ −30
5𝑋1 + 9𝑋2 ≤ 45
4𝑋2 ≤ 15
𝑋2 ≤ 3,75
𝑋1 + 3,75 ≤ 6
𝑋1 ≤ 2,25
𝑍 = −41,25
SOLUCIÓN 𝑍 = −40 𝑋1 = 0 𝑋2 = 5
𝑍 = −39 𝑋1 = 3 𝑋2 = 3
𝑍 = −41 𝑋1 = 1,8 𝑋2 = 4
𝒁 = 𝟒𝟏, 𝟐𝟓 𝑿𝟏 = 𝟐, 𝟐𝟓 𝑿𝟐 = 𝟑, 𝟕𝟓
𝑍 = −40,2 𝑋1 = 1
𝑋2 = 4,4
𝑁𝑜 𝑓𝑎𝑐𝑡𝑖𝑏𝑙𝑒
𝑍 = −37 𝑋1 = 1 𝑋2 = 4
𝑍 = −40 𝑋1 = 0 𝑋2 = 5
𝑋1 + 𝑋2 ≤ 6 𝑋1 ≤ 3
5𝑋1 + 9𝑋2 ≤ 45 𝑋1 ≤ 3,6
𝑋2 ≤ 3
𝑋1 ≤ 3
𝑋1 + 𝑋2 ≤ 6 𝑋1 ≤ 2
5𝑋1 + 9𝑋2 ≤ 45 𝑋1 ≤ 1,8
𝑋2 ≥ 4
𝑋1 ≥ 1,8
𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 5
5𝑋1 + 9𝑋2 ≤ 45 𝑋2 ≤ 4,4
𝑋2 ≥ 4
𝑋1 ≤ 1 𝑋1 = 1
𝑋2 ≤ 4,4
𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 4
5𝑋1 + 9𝑋2 ≤ 45 𝑋2 ≤ 3,89
𝑋2 ≥ 4
𝑋1 ≥ 2 𝑋1 = 1
𝑋2 = 4 No Factible
X2≤3 X2≥4
X1≤1 X1≥2
X1≤1
X2≤4 X2≥5
𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 2
5𝑋1 + 9𝑋2 ≤ 45 𝑋2 ≤ 1,8
𝑋1 ≤ 1
𝑋2 ≤ 4 𝑋2 = 4
𝑋1 ≤ 1
𝑋1 + 𝑋2 ≤ 6 𝑋2 ≤ 1 5𝑋1 + 9𝑋2 ≤ 45 𝑋2 ≤ 0
𝑋1 ≤ 1 𝑋2 ≥ 5
𝑋2 = 5 𝑋1 = 0
