Teoría de La Dualidad

Teoría de la dualidad.
La solución óptima de un problema representa los resultados del modelo de acuerdo a

su formulación original. En el mundo real, los ambientes de decisión rara vez son
estáticos, por lo cual se hace necesario el uso de otras herramientas para determinar el
grado de variación en la solución óptima de un problema al cambiar sus parámetros
iniciales. Por ello, se requiere del uso del análisis de sensibilidad, el cual será estudiado
a partir de la teoría de la dualidad, que facilita la obtención de las nuevas soluciones.
1. Definición del problema dual
El modelo estudiado ha sido el que se conoce como problema primal. El problema dual
es un modelo derivado del problema primal, cuya solución es equivalente.
Dado un problema primal en forma estándar (o aumentada), su modelo dual se

estructura como sigue:
Modelo primal Modelo Dual
Max Z = C1X1 + C2X2 + … + CnXn Min w = b1Y1 + b2Y2 + … + bmYm

s.a:
a11X1 + a12X2 + … + a1nXn = b1 a11Y1 + a21Y2 + … + am1Ym ≥ C1
a21X1 + a22X2 + … + a2nXn = b2 a12Y1 + a22Y2 + … + am2Ym ≥ C2
: : : : : :
am1X1 + am2X2 + … + amnXn = bm a1nY1 + a2nY2 + … + amnYm ≥ Cn

Xj ≥ 0 Yi irrestrictas
El modelo dual se puede construir a partir del modelo primal, siguiendo un conjunto de
lineamientos:
1) Si el MP tiene n variables, entonces el MD tendrá n restricciones.

2) Si el MP tiene m restricciones, entonces el MD tendrá m variables.
3) Los lados derechos de las restricciones del MP serán los coeficientes de la
función objetivo del MD.
4) Los coeficientes de la función objetivo del MP serán los lados derechos de las
restricciones del MD.
5) El sentido de optimización del MD es opuesto al del MP.
6) Si el MD resultante es del tipo Max, entonces las restricciones serán del tipo ≤;
por el contrario, si el MD resultante es del tipo Min, entonces las restricciones
serán del tipo ≥.
7) Si para el MP el coeficiente de la j-ésima variable en la i-ésima restricción es aij,
entonces, en el MD, el coeficiente de la i-ésima variable en la j-ésima restricción
será aij.
8) Las variables del MD son irrestrictas.
Otra relación que surge a través de una transformación en el MD resultante, es que si en

el MP original una variable es no restringida, entonces la restricción dual asociada a esa
variable será de igualdad. En forma similar, si se tiene una restricción de igualdad en el
MP original, entonces la variable dual asociada a esa restricción será no restringida.
A nivel de la tabla simplex, la relación entre el problema primal y el dual, puede
interpretarse como se muestra:
2. Relaciones y cálculos primales-duales.
1) - Si el MP es de tipo Max, entonces:

a) Propiedad de dualidad débil: Z ≤ w.
b) Propiedad de dualidad fuerte: en el óptimo Z = w.
Z0 Z1 Z2 Z3=w3 w2 w1 w0
Análogamente, se tiene que

- Si el MP es de tipo Min, entonces:
a) Propiedad de dualidad débil: Z ≥ w.
b) Propiedad de dualidad fuerte: en el óptimo Z = w.
w0 w1 w2 w3=Z3 Z2 Z1 Z0
2) La solución óptima de ambos problemas puede ocurrir de una de las siguientes

formas:
a) Si un problema tiene soluciones factibles y una función objetivo acotada, y por

lo tanto, una solución óptima, entonces ocurre lo mismo con el otro problema,
de forma que se aplican tanto la propiedad de dualidad débil como la fuerte. En
este caso, Z*=w*, siendo este un valor finito.
b) Si uno de los problemas tiene soluciones factibles y una función objetivo no
acotada, entonces el otro problema no tiene soluciones factibles.
c) Si un problema no tiene soluciones factibles, entonces el otro problema no tiene
soluciones factibles o la función objetivo es no acotada.
3) El dual de un problema dual es el problema primal: Dual (Dual) = Primal.

4) Propiedad de soluciones complementarias: en cada iteración, el método simplex
identifica de manera simultánea una solución básica factible en un vértice, X,
para el problema primal; y una solución complementaria, Y, para el problema
dual, donde CX = Yb.
Si X no es óptima para el problema primal, entonces Y no es factible para el
problema dual.
Nota: de aquí en adelante, las letras en negrita indican que las variables son
matrices o vectores.
5) Propiedad de soluciones complementarias óptimas: al finalizar las iteraciones, el

método simplex identifica de manera simultánea una solución óptima, X*, para
el problema primal; y una solución óptima complementaria, Y*, para el
problema dual, donde CX* = Y*b.
Para establecer los cálculos primales duales se debe conocer cada una de las
transformaciones que surgen de la aplicación del algoritmo simplex. Para ello,
consideremos el problema general de programación lineal, suponiendo un problema de
Max, las restricciones del tipo ≤ y las variables ≥ 0, con lo que se tiene:
Max Z = c1 x1 + c2 x2 + ... + cn xn
sujeto a las restricciones :
a11 x1 + a12 x2 + ... + a1n xn ≤ b1
a21 x1 + a22 x2 + ... + a2 n xn ≤ b2
# # # #
am1 x1 + am 2 x2 + ... + amn xn ≤ bm
xj ≥ 0
De manera matricial, esto puede expresarse como:
Max Z = cx
s.a:
Ax ≤ b
x ≥ 0,
donde:
⎡ x1 ⎤ ⎡ b1 ⎤ ⎡0⎤ ⎡ a11 a12 " a1n ⎤

⎢x ⎥ ⎢b ⎥ ⎢0⎥ ⎢a a22 " a2 n ⎥⎥
c = [ c1 c2 " cn ] , x = ⎢ 2 ⎥ , b = ⎢ 2 ⎥ , 0 = ⎢ ⎥ , A = ⎢ 21
⎢#⎥ ⎢#⎥ ⎢# ⎥ ⎢ # # " # ⎥
⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥
⎣⎢ xn ⎦⎥ ⎣⎢bn ⎦⎥ ⎣0⎦ ⎣⎢ am1 am 2 " amn ⎦⎥
Para obtener la forma aumentada debe agregarse una variable de holgura por cada
restricción del tipo ≤, con lo que se obtiene:
⎡ s1 ⎤
⎢s ⎥
S = ⎢ 2 ⎥ , donde S es el vector columna que representa las variables de holgura.
⎢#⎥
⎢ ⎥
⎢⎣ sm ⎥⎦
De forma tal que las restricciones se convierten en:
⎡ x⎤ ⎡ x⎤
[ A, I ] ⎢ ⎥=b y ⎢ ⎥ ≥ 0,
⎣S ⎦ ⎣S ⎦
donde I es la matriz identidad de orden m x m y el vector nulo tiene n + m elementos.
El conjunto de ecuaciones inicial puede escribirse como:
Z − c1 x1 − c2 x2 " − cn xn + 0 s1 + 0s2 " 0sm = 0

0 + a11 x1 + a12 x2 " + a1n xn + s1 = b1
0 + a21 x1 + a22 x2 " + a2 n xn + s2 = b2
# # # #
0 + am1 x1 + am 2 x1 " + amn xn + sm = bm
Lo que a su vez, puede reescribirse en forma matricial:
⎡Z ⎤
⎡ 1 -c 0 ⎤ ⎢ ⎥ ⎡ 0 ⎤
⎢0 A I ⎥ ⎢ x ⎥ = ⎢b ⎥
⎣ ⎦⎢ ⎥ ⎣ ⎦
⎣S ⎦
Recordemos de lo visto previamente que el problema con n variables tendrá m variables

básicas y n – m variables no básicas. Entonces, el problema con n + m variables tendrá
m variables básicas y n variables no básicas. Cuando se eliminan estas n variables no
básicas, el nuevo sistema puede denotarse como:
⎡ xB1 ⎤
⎢x ⎥
Bx B = b , donde el vector de variables básicas x B = ⎢ B 2 ⎥ se obtiene al eliminar las
⎢ # ⎥
⎢ ⎥
⎢⎣ xBm ⎥⎦
⎡ B11 B12 " B1m ⎤
⎢B B22 " B2 m ⎥⎥
⎡ x⎤ ⎢ 21
variables no básicas de ⎢ ⎥ y la matriz base B = se obtiene al
⎣S ⎦ ⎢ # # " # ⎥
⎢ ⎥
⎣⎢ Bm1 Bm 2 " Bmm ⎦⎥
eliminar las columnas correspondientes a los coeficientes de las variables no básicas de
[ A, I ] .
El método simplex introduce sólo variables básicas tales que B sea no singular, de
manera que B-1 siempre existe. De esta forma, para resolver Bx B = b , se premultiplican
ambos lados por B-1:
B -1 BxB = B -1b . Como B-1b = I, la solución queda como x B = B -1b .
Sea cB el vector cuyos elementos son los coeficientes de la función objetivo que
corresponden a las variables xB. El valor de la función objetivo será:
Z = cB xB = cB B -1b .
Las soluciones Z y xB serán válidas para cualquier iteración.
Volviendo a la forma matricial inicial, se tiene que las operaciones algebraicas del
método simplex se expresan en forma matricial al premultiplicar ambos lados del
conjunto original de ecuaciones por la matriz apropiada. A partir de una serie de
operaciones algebraicas en varias iteraciones, esta matriz puede deducirse, quedando:
⎡1 c B B −1 ⎤
⎢ −1 ⎥
. Luego, conociendo Z y xB, el lado derecho de la forma matricial (columna
⎣ 0 B ⎦
solución) se obtiene como:
⎡ Z ⎤ ⎡1 cB B −1 ⎤ ⎡ 0 ⎤ ⎡cB B −1b ⎤
⎢x ⎥ = ⎢ −1 ⎥ ⎢ ⎥
= ⎢ −1 ⎥ , con lo que se comprueba que la matriz es la
⎣ B ⎦ ⎣0 B ⎦ ⎣b ⎦ ⎣ B b ⎦
correcta. Luego, para el lado izquierdo de la forma matricial, se tiene:
⎡1 cB B −1 ⎤ ⎡1 -c 0 ⎤ ⎡1 cB B −1 A - c cB B −1 ⎤
⎢ −1 ⎥ ⎢ ⎥=⎢ ⎥
⎣0 B ⎦ ⎣0 A I ⎦ ⎣0 B −1 A B −1 ⎦
La forma matricial completa, para cualquier iteración, puede escribirse como:

⎡Z ⎤
⎡1 cB B −1 A - c cB B −1 ⎤ ⎢ ⎥ ⎡cB B −1b ⎤
⎢ ⎥ x =⎢ ⎥
⎣0 B −1 A B −1 ⎦ ⎢ ⎥ ⎣ B −1b ⎦
⎢⎣ S ⎥⎦
En la tabla simplex, esto se refleja como:

Entonces, para cualquier iteración, se tiene que:
Solución básica factible Xj Inicial XB Solución

Z Zj-Cj = CBB Aj- Cj Y = CBB Z = CBB-1b
-1 -1
XB Aj =B-1Aj B-1 XB = B-1b
Donde Z es el valor óptimo de la iteración actual, XB es el vector columna de variables

básicas actuales, Zj-Cj es el coeficiente de Xj en el renglón Z para la iteración actual, CB
es el vector fila de los coeficientes de la F.O. originales para las variables básicas
actuales (en el mismo orden como aparecen en la tabla), B-1 es la matriz inversa de la
iteración actual (que depende de las variables básicas actuales), Aj es el vector columna
de coeficientes de la variable j para cada restricción original (aij), Cj es el coeficiente de
Xj en la F.O. original, Y es el vector fila de las variables duales para la iteración actual,
y b es el vector columna correspondiente al lado derecho de cada restricción.
En la iteración óptima se tiene que:
Solución básica factible Xj Inicial XB Solución

Z (Zj-Cj)* = CBB Aj- Cj Y* = CBB Z* = CBB-1b
-1 -1
XB Aj* =B-1Aj B-1 XB* = B-1b
A partir de esta última tabla pueden plantearse los siguientes cálculos primales duales.
6) En cualquier iteración simplex, se cumple que:
Coeficiente Lado izquierdo

del objetivo menos el lado
de la variable
j en un
= derecho de la
restricción j en el
problema otro problema
La ecuación para esta relación, queda establecida como:

m
Zj – Cj = ∑a Y −C
i =1
ij i j
7) Para cualquier iteración y cualquier columna, excepto las de la matriz inversa, se

cumple que:
Matriz Columna l en
Columna l en inversa en la la iteración 0
la iteración k = x (Columna l
iteración k
original)
8) Los valores duales en la iteración i, se pueden obtener de la siguiente forma:
[Y1, Y2, … , YB] = [C1, C2, …, CB] * B-1
donde C1, C2, …, CB, son los coeficientes originales de las variables básicas de la
iteración i, en el mismo orden en el que aparecen en la tabla simplex.
Método dual simplex.
1) Expresar el modelo original en forma estándar, con la excepción de que se

permiten lados derechos negativos.
2) Determinar una solución inicial no necesariamente factible.
3) Construir la tabla simplex.
4) Comenzar a iterar de acuerdo a los siguientes criterios:
a) Determinar la variable a sacar, por medio de la condición de factibilidad, que en
este caso establece lo siguiente: sacar aquella variable que tenga el valor más
negativo.
b) Seleccionar la variable de entrada según la condición de optimidad, que ahora
establece lo siguiente: seleccionar de entre las no básicas aquella que tenga el
menor valor absoluto del cociente entre el coeficiente de la FO y el coeficiente
en la fila de la variables que sale, descartando los denominadores no negativos.
c) En ambos casos los empates se rompen arbitrariamente.
d) Si la solución encontrada no es factible, se vuelve al paso 4a)

Teoría de La Dualidad

Cargado por

Copyright:

Formatos disponibles

Teoría de La Dualidad

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Teoría de La Dualidad

Cargado por

Copyright:

Formatos disponibles

Teoría de la dualidad.

La solución óptima de un problema representa los resultados del modelo de acuerdo a

1. Definición del problema dual

Dado un problema primal en forma estándar (o aumentada), su modelo dual se

Modelo primal Modelo Dual

Max Z = C1X1 + C2X2 + … + CnXn Min w = b1Y1 + b2Y2 + … + bmYm

am1X1 + am2X2 + … + amnXn = bm a1nY1 + a2nY2 + … + amnYm ≥ Cn

1) Si el MP tiene n variables, entonces el MD tendrá n restricciones.

Otra relación que surge a través de una transformación en el MD resultante, es que si en

2. Relaciones y cálculos primales-duales.

1) - Si el MP es de tipo Max, entonces:

Análogamente, se tiene que

2) La solución óptima de ambos problemas puede ocurrir de una de las siguientes

a) Si un problema tiene soluciones factibles y una función objetivo acotada, y por

3) El dual de un problema dual es el problema primal: Dual (Dual) = Primal.

5) Propiedad de soluciones complementarias óptimas: al finalizar las iteraciones, el

De manera matricial, esto puede expresarse como:

⎡ x1 ⎤ ⎡ b1 ⎤ ⎡0⎤ ⎡ a11 a12 " a1n ⎤

De forma tal que las restricciones se convierten en:

donde I es la matriz identidad de orden m x m y el vector nulo tiene n + m elementos.

El conjunto de ecuaciones inicial puede escribirse como:

Z − c1 x1 − c2 x2 " − cn xn + 0 s1 + 0s2 " 0sm = 0

Lo que a su vez, puede reescribirse en forma matricial:

Recordemos de lo visto previamente que el problema con n variables tendrá m variables

B -1 BxB = B -1b . Como B-1b = I, la solución queda como x B = B -1b .

Las soluciones Z y xB serán válidas para cualquier iteración.

La forma matricial completa, para cualquier iteración, puede escribirse como:

En la tabla simplex, esto se refleja como:

Solución básica factible Xj Inicial XB Solución

XB Aj =B-1Aj B-1 XB = B-1b

Donde Z es el valor óptimo de la iteración actual, XB es el vector columna de variables

En la iteración óptima se tiene que:

Solución básica factible Xj Inicial XB Solución

XB Aj* =B-1Aj B-1 XB* = B-1b

6) En cualquier iteración simplex, se cumple que:

Coeficiente Lado izquierdo

La ecuación para esta relación, queda establecida como:

7) Para cualquier iteración y cualquier columna, excepto las de la matriz inversa, se

8) Los valores duales en la iteración i, se pueden obtener de la siguiente forma:

[Y1, Y2, … , YB] = [C1, C2, …, CB] * B-1

1) Expresar el modelo original en forma estándar, con la excepción de que se

También podría gustarte