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

Partes: 1, 2, 3

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