Programación lineal (Powerpoint) (página 3)

Partes: 1, 2, 3

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