Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Programación lineal II (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

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

Monografias.com

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?

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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 ?

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

27
Programación lineal
Vértice más prometedor
?

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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 }

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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 ?

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter