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 |