Programación Lineal

Conceptos y Principios Básicos

Un problema de programación lineal en formulación estándar, es un problema de la forma
Min Ctx
Sujeto a
Ax = b
x ≥ 0
Donde A∈ Mmxn, con rango(A)=m, b∈Rm, C∈Rn
A partir de ahora llamaremos a este problema P. Al vector C le llamamos vector de costes, A será la matriz de restricciones y B será el vector de restricciones.

Las dimensiones del problema m y n son respectivamente, el número de filas y el nnúmero de columnas de la matriz A.

La idea es que el conjunto factible

    S = {x∈Rn : Ax = b, x≥ 0}

es un conjunto poliédrico denominado polítopo, formado por la intersección de semiespacios generados por cada una de las restricciones y en particular es un conjunto convexo, los teoremas de programación lineal junto con la teoría de convexidad demuestran que si P tiene solución finita, ella está dentro del conjunto de sus puntos extremos.

Teoría en extensión

El conjunto factible

    S = {x∈Rn : Ax = b, x≥ 0}

Se puede caracterizar S en términos de sus puntos extremos y sus direcciones extremas.
Teorema 1 (existencia de puntos extremos)
El conjunto S tiene al menos un punto extremo.
Si B es una submatriz de A mxm (con rango m), entonces podemos escribir
     A = [B, N]
y el sistema de programación lineal se puede poner en la forma
    BXB + NXN = b
y podemos escribir la solución en la forma
    x = [XB, XN]
Todo esto es notación, lo que hemos hecho es solo dividir el sistema de ecuaciones que forma la región factible en dos sistemas de ecuaciones, uno para una submatriz cuadrada de A (de rango m) y otro con las ecuaciones restantes.
Existe una caracterización de los puntos extremos del conjunto factible S, la idea intuitiva es que todo punto extremo es en realidad solución del un sistema lineal de ecuaciones construído a partir de una submatriz de A de rango m (en nuestro caso B).
Teorema 2 (Caracterización de puntos extremos)
Sea S = {x∈Rn : Ax = b, x≥ 0} ⊂ Rn.
Donde
    A∈ Mmxn, con rango(A)=m, b∈Rm, C∈Rn
entonces x es un punto extremo si y solo si ∃ B submatriz de A con rango(B) = m tal que
    x = [B-1b, 0]t

El siguiente corolario nos pone una cota superior para el número de puntos extremos.
Corolario
El número máximo de puntos extremos de S es (n m) = n!/m!(n-m)!
(Pedimos disculpas por la notación, no tenemos otra forma de escribir números combinatorios )

Como veremos, no todo problema de programación lineal tiene solución óptima finita, pero en caso de tenerla existe una caracterización en el siguiente terorema:

Teorema 3 (Caracterización de soluciones óptimas finitas del problema P)
Sean
    x1, x2, ... xk los puntos extremos de S y sean
    d1, d2, ... dr las direcciones extremas de S.
P tiene solución óptima finita si y solo si Ctdj ≥ 0, j =1,2, ..., r
Además uno de los puntos extremos es solución del problema





Ha sido util? Alguna idea para complementar el texto?



Deja tu post

Comentarios de otros usuarios





Deja tu post