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
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
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
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
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
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
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
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
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
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
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
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
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
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 ?
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 |