Programación lineal Condiciones simplificadas: cb BT 0 = ? + , ?n ? 0 cn NT ?n Equivalentes a cb = BT? , cn = NT? + ?n , ?n ? 0 o bien cn – NTB -T cb ? 0 Se resuelve un sistema de dimensión m ? m
Programación lineal Comprobación de las condiciones: Paso 1. Se resuelve el sistema de ecuaciones BT? = cb Paso 2. Se calcula el multiplicador como ?n = cn – NT? Paso 3. Se comprueba la condición ?n ? 0
Programación lineal Condiciones de óptimo en un vértice Esfuerzo a realizar: Factibilidad Multiplicar matriz por vector Existencia de multiplicadores Resolver un sistema de ecuaciones Dimensión n ? n Signo de los multiplicadores Comparación simple
Programación lineal Cálculo de los multiplicadores para ( 3 1 2 0 0 )T 1 2 -1 1 1 2 3 B = 2 4 1 N = 2 -1 cB = 1 cN = 1 4 1 -1 2 -1 0 B T? = cb ? ? = ( 5/6 4/3 -3/2 )T ?n = cn – NT? = ( -2 7/2 )T Como (?n )1 < 0 , el punto no es solución
Programación lineal Método Simplex Nos dan un vértice factible Si es solución, se termina Si no lo es, buscar un nuevo vértice Cálculo de un nuevo vértice Para alcanzar la solución más rápidamente, se calcula un vértice mejor Para facilitar el cálculo del nuevo vértice, se elige un vértice contiguo
Programación lineal Cálculo del nuevo vértice Buscar entre vértices contiguos Problema en forma estándar: Un vértice contiguo comparte n – 1 restricciones activas Un vértice contiguo comparte n – m – 1 variables no básicas Una variable no básica diferente Existen n – m vértices contiguos
Programación lineal ¿Qué vértice contiguo escoger? El mejor: Vértice contiguo con el menor valor de la función objetivo Demasiado caro de calcular El que resulte más prometedor: Vértice contiguo en la arista con el mayor descenso en la función objetivo
Programación lineal Vértice más prometedor ?
Programación lineal Selección de vértice contiguo Clave: valor de los multiplicadores Multiplicador: cambio en la función objetivo al alejarse de la restricción Supongamos que ?i < 0 Si aumenta xi , la función objetivo disminuye a un ritmo dado por ?i Multiplicador más negativo: decrecimiento más rápido
Programación lineal Cálculo del vértice contiguo Si el vértice no es solución, existe algún multiplicador negativo Seleccionar el multiplicador más negativo Desplazarse a lo largo de la arista asociada Expresión de la arista: x + ?p , ? ? 0 p vector que representa la dirección de la arista ? escalar que indica distancia sobre la arista Cuanto mayor es ? , más nos alejamos del vértice
Programación lineal Cálculo de dirección de movimiento, p Dirección p tal que a lo largo de x + ?p : Aumente xi Las restricciones de igualdad se cumplan Las demás variables no básicas sean cero Cálculo de componentes básicas y no básicas: pb p = pn
Programación lineal Información de partida: vértice factible x xb x = , A x = b , x ? 0 , xn = 0 xn Condiciones que debe cumplir p : Debe aumentar (xn)i ? (pn)i > 0 Demás variables no básicas iguales a cero ? (pn)j = 0 ?j ? i
Programación lineal Condiciones que debe cumplir p : Se deben cumplir las restricciones de igualdad A x = b , A (x + ?p ) = b ? Ap = 0 ? Bpb + Npn = 0 ? Bpb = -Npn ¿Qué queda por determinar? Componente no básica a aumentar, i Valor de la componente (pn)i Se toma el valor 1
Programación lineal Resumen Forma de p : pn = ei , Bpb = -Nei ¿Qué i se selecciona? Variable no básica con (?n)i más negativo Justificación: cT (x + ?p ) = cTx + ? cTp cTp = cnTpn + cbTpb = ( cn + N TB -Tcb )T ei = (?n )i
Programación lineal Cálculo de p Dado un vértice factible no solución Paso 1. Encontrar el multiplicador más negativo, (?n )i Paso 2. Definir pn como pn = ei Paso 3. Resolver el sistema de ecuaciones Bpb = -Nei
Programación lineal Ejemplo: min 2×1 + x2 – x3 + 3×4 s.a x1 + 2×2 – x3 + x4 + x5 = 3 2×1 + 4×2 + x3 + 2×4 – x5 = 12 x1 + 4×2 + x3 – x4 + 2×5 = 9 x ? 0 Estudiar el punto ( 3 1 2 0 0 )T -2 ?n = cn – NTB -Tcb = 7/2
Programación lineal Definición de p Componentes no básicas: pn = e1 Componentes básicas: 1 2 1 1 1 -1 -3 Bpb = -Ne1 ? 2 4 1 pB = – 2 -1 e1 = -2 ? pB = 1 1 4 1 1 2 1 0 Dirección de movimiento: p = ( -3 1 0 1 0 )T
Programación lineal Justificación de la condición de óptimo ¿Se tiene ascenso en el vértice a lo largo de todas las aristas? Cálculo de todas las aristas en un vértice: pn = ei ?i , Bpb = -Npn Puntos a lo largo de la arista: x + ? p ¿Descenso o ascenso? cT ( x + ? p ) – cT x = ? cT p cT p < 0 descenso, cT p > 0 ascenso
Programación lineal Justificación de la condición de óptimo Expresión formal cT p = cnT pn + cbT pb = cnT ei + cbT (-B -1Nei ) = eiT ( cn – NTB -T cb ) = eiT ?n donde ?n = cn – NTB -T cb Se tiene una solución (para minimización) si ?n ? 0
Programación lineal Cálculo de la longitud de paso ? xk+1 = xk + ?pk ¿Cómo interesaría moverse? A lo largo de pk la función objetivo decrece linealmente Moverse tan lejos como sea posible Unica limitación: Restricciones de cota de las variables básicas
Programación lineal Cálculo de la longitud de paso ? Condición: xi + ?pi ? 0 ?i ? B Para cada componente i básica calculamos el mayor paso factible, -xi /pi El paso se define como el menor de los cocientes para los pasos positivos ? = min { -xi /pi | pi < 0 }
Programación lineal Ejemplo: min 2×1 + x2 – x3 + 3×4 s.a x1 + 2×2 – x3 + x4 + x5 = 3 2×1 + 4×2 + x3 + 2×4 – x5 = 12 x1 + 4×2 + x3 – x4 + 2×5 = 9 x ? 0 En ( 3 1 2 0 0 )T hemos obtenido p = ( -3 1 0 1 0 )T Solo existe una componente negativa en p ? = -3/(-3) = 1 , x’ = x + p = ( 0 2 2 1 0 )T
Programación lineal Cálculo del vértice factible inicial Para aplicar el método Simplex falta un vértice inicial Pero el método Simplex es capaz de generar vértices factibles Las soluciones de un problema lineal lo son Basta con encontrar un problema lineal con las propiedades adecuadas
| Página siguiente |