Descargar

Programación lineal (Powerpoint)

Enviado por Pablo Turmero


Partes: 1, 2, 3

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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.

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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?

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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 ?

    edu.red

    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

    Partes: 1, 2, 3
    Página siguiente