13 Programación lineal Procedimiento básico Método Simplex: Suponemos conocido un vértice factible Comprobamos si es solución: Comprobar condiciones necesarias y suficientes Si no lo es, buscamos un vértice contiguo mejor Criterio de selección entre vértices contiguos
14 Programación lineal Método Simplex: Aspectos básicos: ¿Cómo podemos calcular un vértice factible? ¿Qué debemos comprobar para saber si un vértice es solución? ¿Cómo podemos escoger un vértice contiguo mejor?
15 Programación lineal Comprobar si un vértice es óptimo: Paso 1. ¿Es un vértice factible? ¿Es factible? ¿Tiene al menos n – m variables iguales a cero? Paso 2. ¿Es solución? Condiciones de óptimo Signo de los multiplicadores
16 Programación lineal Condiciones de óptimo en un vértice Problema en forma estándar Versión más eficiente de las condiciones Sistema de ecuaciones de tamaño reducido Basado en partición de variables para un vértice factible xb cb x = c = A = ( B N ) xn cn
17 Programación lineal Derivación de condiciones de óptimo Condiciones generales de extremo Condición basada en ausencia de descenso Estudiar las direcciones factibles en el vértice Estudiar solo las aristas que salen del vértice Determinar si la función objetivo decrece Vértice solución: si la f. objetivo no decrece a lo largo de ninguna arista
18 Programación lineal Condiciones necesarias y suficientes: Ax = b , x ? 0 c = AT? + ? ? ? 0 , ?Tx = 0 Para comprobar si un punto es solución: Factibilidad Existencia de multiplicadores Signo de multiplicadores ?
19 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 Comprobar si ( 3 1 2 0 0 )T es solución
20 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
21 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
22 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
23 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
24 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
25 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
26 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
27 Programación lineal Vértice más prometedor ?
28 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
29 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
30 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
31 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
32 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
33 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
34 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
35 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
36 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
37 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
38 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
39 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
40 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 }
41 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
42 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
43 Programación lineal Problema lineal auxiliar (fase I) Problema lineal relacionado con el de partida, pero distinto de él Propiedades deseadas: Debe tener un vértice factible que se pueda calcular de forma trivial La solución del problema auxiliar debe ser un vértice factible del problema de partida
44 Programación lineal Supondremos que b ? 0 Problema auxiliar min cTx min eTw s.a Ax = b ? s.a Ax + w = b x ? 0 x ,w ? 0 Vértice inicial: ( x , w ) = ( 0 , b ) Si la solución del problema modificado resultase ser ( x , 0 ) , x sería un vértice factible del problema original
45 Programación lineal Paso 1. Asegurar que b ? 0 Paso 2. Construir el problema modificado Paso 3. Resolver dicho problema partiendo de ( 0 , b ) Paso 4. Si en la solución w = 0 , resolver el problema original desde x Paso 5. Si en la solución w ? 0 , el problema original no es factible
46 Programación lineal Ejemplo: max 2×1 – 3×2 – x3 + 2×4 s.a x1 + x2 – x3 – x4 ? -2 2×1 – x2 + 2×3 + x4 ? 1 -x1 + x2 + x3 – 2×4 = -2 x ? 0 Lado derecho mayor que cero: max 2×1 – 3×2 – x3 + 2×4 s.a -x1 – x2 + x3 + x4 ? 2 2×1 – x2 + 2×3 + x4 ? 1 x1 – x2 – x3 + 2×4 = 2 x ? 0
47 Programación lineal Problema en forma estándar max 2×1 – 3×2 – x3 + 2×4 s.a -x1 – x2 + x3 + x4 + s1 = 2 2×1 – x2 + 2×3 + x4 – s2 = 1 x1 – x2 – x3 + 2×4 = 2 x , s ? 0 Problema auxiliar: min w1 + w2 s.a -x1 – x2 + x3 + x4 + s1 = 2 2×1 – x2 + 2×3 + x4 – s2 + w1 = 1 x1 – x2 – x3 + 2×4 + w2 = 2 x , s , w ? 0
48 Programación lineal Ejemplo Punto inicial del problema auxiliar: x = ( 0 0 0 0 )T , s = ( 2 0 )T , w = ( 1 2 )T Punto solución del problema auxiliar: x = ( 0 0 0 1 )T , s = ( 1 0 )T , w = ( 0 0 )T Vértice factible del problema inicial: x = ( 0 0 0 1 )T
49 Programación lineal Los cálculos del método Simplex: Paso 1. Obtener un vértice factible inicial Paso 1.1 Asegurar que b ? 0 Añadir variables auxiliares Formar problema auxiliar Paso 1.2 Fase I Resolver el problema auxiliar Determinar un vértice factible para el problema original
50 Programación lineal Paso 2. Comprobar si el vértice factible es solución BT? = cb , ?n = cn – NT? ?n ? 0 ? Paso 3. Calcular la dirección de movimiento p i = arg mink (?n )k pn = ei , Bpb = -Nei
51 Programación lineal Paso 4. Calcular la longitud de paso ? ? = min { -xi /pi | pi < 0 } Paso 5. Obtener el nuevo vértice x' = x + ?p
52 Programación lineal Ejemplo min x1 – 2×2 – x3 s.a x1 + x3 ? 1 x1 + 2×2 + 2×3 ? 2 x ? 0 Paso 0. Poner en forma estándar min x1 – 2×2 – x3 s.a x1 + x3 – s1 = 1 x1 + 2×2 + 2×3 + s2 = 2 x , s ? 0
53 Programación lineal Paso 1. Vértice factible inicial Problema auxiliar: min a s.a x1 + x3 – s1 + a = 1 x1 + 2×2 + 2×3 + s2 = 2 x , s , a ? 0 Vértice factible inicial: x = ( 0 0 0 )T , s = ( 0 2 )T , a = 1 Solución: x = ( 1 0 0 )T , s = ( 0 1 )T , a = 0
54 Programación lineal Paso 2. Solución del problema original Variables básicas: x1 , s2 ¿Es solución el vértice? ? = B -Tcb = ( 1 0 )T , ?n = cn – NT? = ( -2 -2 1 )T Dirección de movimiento: pn = ( 1 0 0 )T , pb = -B -1Npn = ( 0 -2 )T , p = ( 0 1 0 0 -2 )T Longitud de paso: ? = 1/2 Nuevo vértice: x' = ( 1 1/2 0 0 0 )T
55 Programación lineal Siguiente iteración: Variables básicas: x1 , x2 ¿Es solución el vértice? ? = B -Tcb = ( 2 -1 )T , ?n = cn – NT? = ( -1 2 1 )T Dirección de movimiento: pn = ( 1 0 0 )T , pb = -B -1Npn = ( -1 -1/2 )T , p = ( -1 -1/2 1 0 0 )T Longitud de paso: ? = min{ 1/1 , (1/2)/(1/2) } = 1 Nuevo vértice: x' = ( 0 0 1 0 0 )T
56 Programación lineal Siguiente iteración: Variables básicas: x1 , x3 ¿Es solución el vértice? ? = B -Tcb = ( 3 -2 )T , ?n = cn – NT? = ( 2 3 2 )T El vértice es solución Vértice degenerado ¿Qué habría sucedido si hubiésemos considerado como variables básicas x2 , x3 ?
57 Programación lineal Convergencia del método Simplex Un problema lineal puede ser: No factible No acotado max x1 + x2 s.a x ? 0 Factible y acotado ? óptimo
58 Programación lineal Convergencia del método Simplex Si el problema no tiene solución Basta con poder identificar la situación Si el problema no es factible: La fase I acaba con una solución w ? 0 Si el problema no está acotado: El método Simplex encuentra un paso ? = ? En alguna iteración pb ? 0
59 Programación lineal Si el problema es óptimo En cada iteración la función objetivo decrece Descenso: cTp = (?n )i < 0 Siempre que ? > 0 Se sigue descendiendo hasta que ?n ? 0 Existe un número finito de vértices El argumento solo puede fallar si ? = 0
60 Programación lineal Vértices degenerados Para que ? = 0 se debe tener que ?i , (xb )i = 0 y (pb )i < 0 Puede suceder en vértices degenerados Posibilidad de ciclos: Intercambiar variables básicas y no básicas Sin modificar el valor de x
61 Programación lineal Cómo evitar ciclos: Si no hay empate, no pueden existir ciclos En caso de empates: regla de Bland Variable que entra en la base: Primera con el menor valor del multiplicador Variable que sale de la base: Primera con el menor cociente para ? Orden de variables: cualquiera pero fijo Ineficiencia en la práctica
62 Programación lineal Organización de los cálculos Para su aplicación manual Se disponen los datos en una tabla, cT 0 A b En un vértice, la tabla se reajusta como cT – cbTB -1A -cbTB -1b B -1A B -1b
63 Programación lineal ¿Qué información proporciona la tabla? cT – cbTB -1A -cbTB -1b B -1A B -1b Multiplicadores Función objetivo Dir. de movimiento Valores de variables Cada vértice corresponde a diferentes valores de B y cB
64 Programación lineal ¿Cómo actualizar la tabla al cambiar B ? Cambio de B Variable no básica ? básica: multiplicador Variable básica ? no básica: longitud de paso Una columna de B cambia por otra B = ( b1 … bk … bm ) ? ( b1 … bj … bm ) = B' B' = B + (bj – bk )ekT = B (I + ( B -1bj – ek )ekT ) = BE
65 Programación lineal La matriz de interés en la tabla es la inversa, B' -1 = E -1B -1 , E -1 = I – (1/ekTB -1bj )( B -1bj – ek )ekT N' = B -1N , nj' = B -1nj B' -1A = B -1A – (1/ekTnj' )(nj' – ek )ekTB -1A Operaciones sobre la tabla: A cada fila i se le resta la fila k multiplicada por nij' /nkj' Se pivota sobre el elemento kj
66 La misma operación de pivotaje se aplica al lado derecho y a la fila superior Ejemplo: Introducir en la base x3 y eliminar x1 0 -5 3 0 -1 26 -3 -2 0 0 2 20 0 2 -3 1 1 2 ? 3 -1 0 1 -2 8 1 -1 1 0 -1 2 1 -1 1 0 -1 2 Propiedad de las columnas básicas: Matriz identidad más ceros en la fila superior Programación lineal
67 Programación lineal Ejemplo min x1 – 2×2 – x3 s.a x1 + x3 ? 1 x1 + 2×2 + 2×3 ? 2 x ? 0 Problema auxiliar: min a s.a x1 + x3 – s1 + a = 1 x1 + 2×2 + 2×3 + s2 = 2 x , s , a ? 0
68 Programación lineal Tablas para el problema auxiliar 1 -2 -1 0 0 0 0 1 -2 -1 0 0 0 0 0 0 0 0 0 1 0 -1 0 -1 1 0 0 -1 1 0 1 -1 0 1 1 ? 1 0 1 -1 0 1 1 1 2 2 0 1 0 2 1 2 2 0 1 0 2 Paso 2.1. ¿Son positivos los multiplicadores? Paso 2.2. Dir. de movimiento y long. de paso: Columna multipl. más negativo, fila cociente menor Se pivota sobre el valor 1
69 Programación lineal Nueva tabla: 1 -2 -1 0 0 0 0 0 -2 -2 1 0 -1 -1 -1 0 -1 1 0 0 -1 0 0 0 0 0 1 0 1 0 1 -1 0 1 1 ? 1 0 1 -1 0 1 1 1 2 2 0 1 0 2 0 2 1 1 1 -1 1 Nueva tabla es óptima para problema auxiliar 0 -2 -2 1 0 -1 1 0 1 -1 0 1 0 2 1 1 1 1
70 Programación lineal De vuelta al problema original: 0 -2 -2 1 0 -1 0 0 -1 2 1 0 1 0 1 -1 0 1 ? 1 0 1 -1 0 1 0 2 1 1 1 1 0 1 1/2 1/2 1/2 1/2 ¿Es solución? No Siguiente vértice: 0 0 -1 2 1 0 0 2 0 1 2 1 1 0 1 -1 0 1 ? 1 -2 0 -2 -1 0 0 1 1/2 1/2 1/2 1/2 0 2 1 1 1 1
71 Programación lineal Resumen: En la tabla se selecciona: Columna del multiplicador más negativo Fila con menor cociente bik' /nik' para nik' > 0 Se pivota sobre el elemento nik' El proceso se repite hasta que los multiplicadores tienen el signo correcto
| Página siguiente |