TEOREMA FUNDAMENTAL DE DUALIDAD

TEOREMA FUNDAMENTAL DE DUALIDAD

En un par de problemas primal-dual, si el primal o el dual tienen solución óptima entonces el otro también, y el valor de la función objetivo optimal es el mismo para ambos.

Demostración:

Sea el primal Min z(x)=Cx y su dual Max w()=b

s.a.: Ax=b s.a.: A≤C

x≥0  SRS

donde A es mxn, supongamos que tiene solución óptima, por lo cual el problema tiene base óptima, supongamos que la solución básica óptima es XB=(x1,x2,............,xm) y sea B la base asociada a dicha solución y sea N la matriz de orden mx(n-m) asociada a las variables no básicas XN=(xm+1,.......,xn) entonces el problema puede ser representado de la siguiente forma en su tabla original:

XB -z XN b

B 0 N b

CB 1 CN 0

Y su tabla óptima de la siguiente forma:

V.B. XB -z XN b

XB I 0 B-¹N B-¹b

-z 0 1 CN-CB B-¹N -CB B-¹b

para la obtención de esta tabla óptimas se multiplicó toda la tabla inicial por la matriz:

B-¹ 0 pues esta es la inversa de B 0

-CB B-¹ 1 CB 1

ya que esta es una tabla óptima se debe cumplir que:

Cj≥0 para todo j entonces CN-CB B-¹N≥0 entonces, Cj- CB B-¹Aj≥0 para todo j entonces,

CB B-¹Aj≤Cj para todo j con lo cual CB B-¹A≤C, si definimos  como CB B-¹ tendríamos entonces que A≤C, por lo que se tendría factibilidad dual, además si el primal tiene solución óptima CB B-¹b por el teorema fuerte de dualidad b= CB B-¹b con lo cual = CB B-¹ es la solución óptima dual.

COROLARIOS:

Si ambos problemas tienen soluciones factibles, entonces ambos tienen soluciones óptimas y el valor de la función objetivo es el mismo. De aquí se desprenden las condiciones primales duales que son:

Cj = Cj-Aj

...