PROGRAMACION CUADRTICA El problema de programacin cuadrtica difiere del problema de programacin lineal nada ms en que la funcin objetivo incluye
tambin trminos x 2j y xixj (i j). El modelo de programacin cuadrtica se define como sigue: Donde C es un vector rengln, X y b son vectores columna, Q y A son matrices y el superndice T denota la transpuesta. La funcin XTQX define una forma cuadrtica. Se supone que la matriz Q es simtrica.
FORMULA GENERAL DE LA PROGRAMACION CUADRTICA Los elementos de Q (qij) son constantes dadas, tales que qij = qji. Al realizar la multiplicacin entre los vectores y matrices indicadas la funcin objetivo queda expresada como sigue:
n 1 T 1 n n f ( x) CX X QX c j x j qij xi x j 2 2 i 1 j 1 j 1
Si i=j en esta doble suma, entonces xi xj=
, as -1/2 qjj es el coeficiente de
Si ij -qij es el coeficiente total del producto de xi y xj.
IDENTIFICACIN DE VARIABLES VECTORES Y MATRICES C: Es un vector rengln. Formado por los coeficientes de las variables lineales. X: Es un vector columna. Formado por las variables del modelo. A: Es una matriz formado por los coeficientes de las restricciones. B: Es un vector columna formado por los elementos de lado derecho de las restricciones. Q: Es una matriz formada por constantes dadas, tales que: para cada termino i=j en esta doble suma, xi xj = xj 2, as -1/2qjj es el coeficiente de xj 2. Cuando ij, entonces -
1/2(qij xi xj + qji xi xj ), de manera que - qij es el coeficiente total del producto de xi y xj Se tiene el siguiente modelo: Funcin Objetivo: F(x1, x2) = 15x1 + 30x2 + 4x1x2 2x12 4x22 Restriccin: X1 + X2 30 No negatividad: X1, X2 0 Entonces de la ecuacin: F(x1, x2) = 15x1 + 30x2 + 4x1x2 2x12 - 4 x22 Los vectores y matrices sern:
C [15 30] X= x1 x2 Q= qij (1 1) qij (2 1) qij (1 2) qij (2 2) - qij= - 2x1x1 = qij = 4x1x1 - qij = 4x1x2 = qij= - 4x1x2 - qij= 4x2x1 = qij = - 4x1x2 - qij= -4 x2x2 = 8 x2x2
Xt = [X1 X2] Entonces de las restricciones: X1 + 2X2 30 Los vectores y matrices sern: B [30] A [1 2]
PASO PARA RESOLVER Identificar las Caractersticas del Modelo Establecer condiciones Karush Kuhn Tucker(KKT) Re expresar el Modelo (ESTANDARIZAR) Aplicar Simplex Modificado
IDENTIFICAR LAS CARACTERISTICAS DEL MODELO - Funcin de Objetivo La funcin objetivo debe incluir trminos Xj (al cuadrado) Los trminos Xi y Xj de la forma XiXj (multiplicndose) - Restricciones Lineales Xi+Xj <= b -Maximizando y Minimizando *Si se est maximizando la funcin debe ser cncava *Si se est minimizando la funcin debe ser convexa DETERMINAR SI ES CONCAVA Entonces de la ecuacin para determinar si es cncava:
x t Q x = [ x1 x2 ] 4 -4 -4 x1 8 x2
= [(4x1 4x2) (-4x1 + 8x2)] X1 X2 = x1 [(4x1 4x2) + x2[(-4x1 + 8x2)] = 4x12 - 4x1 x2 - 4x2 x1 + 8x22
CALCULO DE CONDICIONES KKT
F(x1, x2) = 15x1 + 30x2 + 4x1x2 2x12 4x22 Sujeto a: X1 + 2X2 30 x1, x2 0 a) 1(j=1) 15 4x2 + 4x1 U1 0
b) 2(j=1)
x1(15 + 4x2 - 4x1 U1) = 0 y1
c) 1(j=2)
30 4x1 - 8x2 2U1 0
d) 2(j=2)
x2(30 4x1 - 8x2 2U1) = 0 y2
e) 3. f) 4. g) 5. h) 6.
X1 + 2x2 30 0 U1(X1 + 2X2 30) = 0 X1 0; X2 0 U1 0
APLICAR LAS CONDICIONES a) 1(j=1) b) 1(j=2) e) 3. -4x1 + 4x2 U1 + y1 -4x1 8x2 2U1 X1 + 2x2 + + y2 = -15 = -30 v1 = 30
b) 2(j=1) d) 2(j=2)
x1(15 4x1 8x2 2U1 = 0 x2(30 4x1 8x2 2U1) = 0
2(j=1) 2(j=2)
x 1y1 = 0 x 2y2 = 0
f) 4 i)
U1(x1 + 2x2 30) = 0 x1y1 + x2y2 + U1V1 = 0
U 1v1 = 0
Nueva Restriccin (Complementariedad)
APLICACIN DEL METODO SIMPLEX MODIFICADO Estandarizacin: Minimizar Z = z 1 + z2 4x1 4x2 + u1 - y1 -4x1 + 8x2 +2u1 X1 + 2x2 X1 0, X2 0, - y2 +v1 u1 0, y1 0, + z1 = 15 + z2 = 30 = 30 y2 0, v1 0
Restriccin Complementaria Adicional X1 * Y1 * X1 * Y2 * u1 * v1 = 0
APLICANDO METODO SIMPLEX MODIFICADO DOS FASES (SOLO LA PRIMERA FASE)
SOLUCION DE LA APLICACIN DEL MTODO MODIFICADO SIMPLEX La solucin ptima que resulta para esta Fase 1 del problema es:
Mientras que las dems variables son cero (0) Se puede verificar que esta solucin es ptima si estos valores satisfacen las condiciones KKT del problema original
