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
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
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
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
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
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.
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
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
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
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
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
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?
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
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
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
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 ?
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
Página siguiente  |