programacion lineal.duallidad

DUALIDAD

ESQUEMA
1.
2.
3.
4.

INTRODUCCION
CONDICIONES DE KUHN – TUCKER
FORMULACION GENERAL DEL DUAL
LAS SOLUCIONES
1. USO DEL PRIMAL PARA RESOLVER EL DUAL
2. USO DEL DUAL PARA RESOLVER EL PRIMAL
3. ALGORITMO DUAL–SIMPLEX

5. INTERPRETACION DEL DUAL
PRECIOS SOMBRA
DUALIDAD

2

1. INTRODUCCION
Tal y como se ha expuesto, la Programación Lineal permite asignar
recursoslimitados entre actividades competitivas de manera que se
optimice un objetivo.
– Por ejemplo, esta técnica es muy útil para decidir el número de productos a
fabricar teniendo en cuenta las limitaciones de los recursos productivos de
manera que se maximice el beneficio global.
– Sin embargo la solución óptima no explica cómo podrían ser asignados los
recursos (ejemplo: materia prima, capacidadde las máquinas, el dinero, etc.)
para obtener un objetivo establecido.

En este capítulo veremos que a cada problema de programación lineal se le
asocia otro problema de programación lineal que proporciona la siguiente
información respecto del problema de programación original:
1. La solución óptima del problema dual aporta la solución óptima del problema
original y viceversa.
2. Lasolución óptima del problema dual proporciona los precios en el mercado o
los beneficios de los recursos escasos asignados en el problema original.
DUALIDAD

3

2. CONDICIONES DE KUHN – TUCKER
Para obtener los extremos de una función multivariable, cuando las variables están sujetas a
ecuaciones de ligadura entre sí, se aplica el método de los multiplicadores de Lagrange.
La funciónlagrangiana para un problema de P.L., al que llamaremos programa PRIMAL,
planteado en forma matricial
Max Z = Ct X
s.a. A X ≤ B
X≥0

adopta la expresión:
Max L(X,Y) = Ct X + Y ( B – AX )
Siendo Y (y1 , y2 , ..., ym) el vector de los multiplicadores de Lagrange.
Las condiciones de optimalidad de esta función, denominadas de Kuhn-Tucker, son:

∂L
= B− A⋅X ≥ 0
∂Y

∂L
= Ct − Y ⋅ A ≤ 0
∂X
∂L⋅ X = (C t − Y ⋅ A ) ⋅ X = 0
∂X

Y⋅
DUALIDAD

∂L
= Y ⋅ (B − A ⋅ X) = 0
∂Y
4

Consideremos otro problema de P.L., al que llamaremos programa DUAL, asociado al
anterior y planteado en los siguientes términos:
Min W = Y B
s.a.

Y A ≥ Ct
Y≥0

La función lagrangiana de este nuevo problema adopta la expresión:
Min L(Y,X) = Y B + (Ct – Y A) X
Siendo X (x1 , x2 , ..., xn) el vector delos multiplicadores de Lagrange.
Las condiciones de optimalidad (Kuhn-Tucker) de esta función son

∂L
= B− A⋅X ≥ 0
∂Y

∂L
= Ct − Y ⋅ A ≤ 0
∂X

∂L
∂L
⋅ X = (C t − Y ⋅ A ) ⋅ X = 0
= Y ⋅ (B − A ⋅ X) = 0
∂X
∂Y
Las condiciones de optimalidad de esta función coinciden con las del PRIMAL

Y⋅

La función lagrangiana de ambos, PRIMAL Y DUAL, coincide:
Max L(X,Y) = Ct X + Y ( B – AX )= Y B + (Ct – Y A) X = Min L(Y,X)
DUALIDAD

5

EJEMPLO
x1

h1

h2

1

Sea el programa PRIMAL

x2
2

0

0

x1 + 2x2

s.a.

1

1

1

0

4

0

1

0

–1

1

2

Wj

2

2

2

0

CRj

–1

0

–2

0

y2

s1

s2

–4

x 1 + x2 ≤ 4

2

h2

SOLUCION

x2

y1

Max Z =

–6

0

0

2x1 + x2 ≤ 6
x1 , x2 ≥ 0

Elprograma DUAL (*)
Min W =

4y1 + 6y2

s.a.

y1 + 2y2 ≥ 1

Z=8

y1

–4

1

1

0

–1

2

s1

0

0

–1

1

–1

1

y1 + y2 ≥ 2

Wj

–4

–4

0

4

y1 , y2 ≥ 0

CRj

0

–2

0

–4

SOLUCION

–W = – 8

(*) Se ha resuelto Max (–W). s1 , s2 son las variables de exceso .
En la tabla final se han omitido las variables artificiales.
Como puedeobservarse, se ha obtenido que el Max (–W) = – 8 ⇒ MinW = 8

DUALIDAD

6

3. FORMULACION GENERAL DEL DUAL
Consideremos un problema de P.L.
Máx Z = Ct X
s.a. AX ≥≤ B
al que denominaremos programa PRIMAL.

A este programa primal se le asocia otro problema de P.L.:
Min W = Bt Y
s.a. At Y ≥≤ C siendo Yt = (y1 , y2 , …, ym)
al que denominaremos programa DUAL.

RELACIONES
Cuando el...