1
Problemas lineales (forma estándar)
min cTx
s.a Ax = b
x ? 0
Estudiaremos sus propiedades especiales
Métodos específicos de solución:
Método Simplex
Métodos de puntos interiores
Programación lineal
2
Programación lineal
Propiedades especiales del problema
La región factible es convexa
Toda solución local es global
Las condiciones necesarias de primer orden son suficientes
Propiedad de convexidad: x e y factibles,
A (?x +(1-?)y ) = ?Ax + (1-?)Ay = ?b + (1-?)b = b
?x +(1-?)y ? 0
3
Programación lineal
Propiedades especiales del problema
La región factible es un politopo :
Figura limitada por hiperplanos
Elementos de un politopo:
Caras, aristas, vértices
Algunos de estos elementos son importantes para el cálculo de la solución
Cómo identificarlos: caracterización algebraica
4
Politopos
Programación lineal
5
Soluciones
Programación lineal
6
Programación lineal
Teorema básico:
"Si existe una solución del problema lineal, existe un vértice solución"
Importancia de los vértices:
Basta con buscar soluciones en vértices (número finito)
Método Simplex:
Probar vértices eficientemente hasta encontrar la solución
7
Programación lineal
Justificación:
Resultado básico (teor. de representación)
Todo punto de un conjunto convexo puede expresarse como combinación convexa de n+1 puntos extremos del conjunto
x = ?i ?i xi , ?i ?i = 1, ?i ? 0
cT x = ?i ?i cTxi ? mini cTxi
8
Programación lineal
Caracterización algebraica de vértices
Representación gráfica solo válida si n ? 3
Caracterización general basada en la de otras partes de un politopo
Caras, aristas, etc.
9
Programación lineal
Partes de un politopo, Ax ? b
Caras: subconjuntos de hiperplanos
Vértices:
Puntos intersección de al menos n caras
Aristas:
Segmentos intersección de n – 1 caras
Comienzan y acaban en un vértice
Vértices contiguos:
unidos por una misma arista
10
Programación lineal
Caracterización algebraica:
Caras: {x | ?j ajTx = bj , Ax ? b }
Vértices: existe una partición de A y b,
Ab bb
A = b =
An bn
Ab ? ?n?n, bb ? ?n, det(Ab ) ? 0,
Ab x = bb , An x ? bn
11
Programación lineal
Vértices de
Ax = b, x ? 0, A ? ?m?n
Siempre existen m restricciones activas,
Ax = b
Necesitamos n – m restricciones activas en
x ? 0
En un vértice al menos n – m variables deben ser iguales a cero: variables no básicas
Variables distintas de cero: variables básicas
12
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 son vértices:
( 1 1 2 1 1 )T , ( -3 4 0 0 -2 )T ,
( 9/2 1/4 5/2 0 1/2 )T , ( 3 1 2 0 0 )T
Página siguiente  |