Teoría de Sistemas
Ingeniería en Sistemas
Ing. Dulce Díaz
Teoría de la dualidad y análisis de la
sensibilidad
INTRODUCCIÓN
Se estudian la teoría de la dualidad y el análisis de
sensibilidad, temas fundamentales de la
programación lineal, vinculados a la búsqueda de
información económica acerca del valor de
recursos que son escasos, cómo se utilizan,
cuándo se analizan y cómo se plantea el
problema dual, o cuándo se aplica al problema
primal el análisis de sensibilidad.
TEORÍA DE LA DUALIDAD
La teoría de la dualidad establece que un
problema dual de programación lineal se origina
directamente del modelo original denominado
problema primal.
Ambos se encuentran muy relacionados, de
modo que la solución óptima de uno de ellos
proporciona la solución óptima del otro.
TEORÍA DE LA DUALIDAD
La importancia de la teoría de la dualidad radica en tres
razones:
1. El planteamiento dual de un problema de programación
lineal puede dar como resultado una reducción considerable
en los cálculos.
2. La posibilidad de obtener información económica acerca
del valor de recursos que son escasos y de cómo se utilizan
cuando se analiza el problema dual.
3. La relación dual tiene un nexo importante con el análisis de
sensibilidad.
TEORÍA DE LA DUALIDAD
Para todo problema de maximización de programación
lineal existe un problema de minimización, y viceversa.
Esta regla nos indica que existe una correspondencia
directa entre los elementos del problema primal y su
dual.
En la siguiente diapositiva se muestra cómo, para la
forma estándar de un problema de programación
lineal, tenemos a la izquierda el problema primal y,
después de hacer la conversión, tenemos a la derecha
su dual:
TEORÍA DE LA DUALIDAD
Problema primal Problema dual
Maximizar Z = ∑ cjxj Maximizar W = ∑bjyj
Sujeto a: ∑ajxj ≤ bi para i = 1,2,...m Sujeto a: ∑aiyi ≥ cj para j = 1,2,..n
xj≥ 0 para j = 1, 2,.....n yj ≥ 0 para i = 1,2,......n
TEORÍA DE LA DUALIDAD
Las variables Xj j = 1, 2…..., n, incluyen las variables de holgura, las excedentes y las
artificiales, si existen
En el problema dual se usan exactamente los mismos parámetros (ak, bi y cj) que en el
problema primal, pero de diferente manera:
a) Se define una variable dual por cada ecuación primal (restricción) y una restricción
dual por cada variable primal.
b) Los coeficientes de restricción (columna) de una variable primal definen los
coeficientes en el lado izquierdo de la restricción dual, y su coeficiente objetivo define
el valor a la derecha.
c) Los coeficientes objetivo del primal definen los valores a la derecha de las ecuaciones
de restricción dual.
d) El sentido de las desigualdades en el dual con respecto al primal siempre son
opuestos.
TEORÍA DE LA DUALIDAD
(Notación matricial)
Problema primal Problema dual
Maximizar: Z = cx Minimizar: W = yb
Sujeto a: Sujeto a:
Ax ≤ b yA ≥ c
x≥ 0 y ≥0
TEORÍA DE LA DUALIDAD
(Con las operaciones matriciales indicadas)
Problema primal Problema dual
Maximizar: Z (Xo) = CX Minimizar: W (Yo) = 𝑏 𝑇 Y
Sujeto a: Sujeto a:
AX ≤ b 𝐴𝑇 Y ≥ 𝑐 𝑇
X≥0 Y≥0
Minimizar: Z (Xo) = CX Maximizar: W (Yo) = 𝑏 𝑇 Y
Sujeto a: Sujeto a:
AX ≥ b 𝐴𝑇 Y ≤ 𝐶 𝑇
X≥0 Y≥0
TEORÍA DE LA DUALIDAD
(Con las operaciones matriciales indicadas)
C, representa el vector renglón de coeficientes de la función objetivo primal.
b, representa el vector columna de términos independientes de restricciones del
primal.
A, representa la matriz de coeficientes tecnológicos de restricciones del primal.
X, representa el vector columna de las variables primales.
T, representa la transpuesta de una matriz o de un vector.
Y, representa el vector columna de las variables duales.
Con excepción de X y Y, los vectores y matrices en ambos problemas son los
mismos, pero debe cuidarse el orden del arreglo vectorial atendiendo a la
transposición T indicada.
TEORÍA DE LA DUALIDAD
Recordemos el problema de la elaboración de dos tipos de sofás
(formulado en el capítulo 3, pág. 55 y solucionado gráficamente en el
capítulo 4, pág. 65):
Maximizar: Z = 10X + 25Y
Sujeto a:
X + 2Y ≤ 80 Departamento de corte
(3/4)X + (1/2)Y ≤ 20 Departamento de armado
X ≤ 50 Departamento de tapicería
Y ≤ 10 Departamento de cubiertas
donde: X, Y ≥ 0
TEORÍA DE LA DUALIDAD
Recordemos que las restricciones correspondientes a los departamentos de
corte y armado son redundantes, por tanto el problema se plantea como sigue:
Maximizar: Z = 10X + 25Y
Sujeto a:
(3/4)X + (1/2)Y ≤ 20
Y ≤ 10
donde: X ≥ 0, Y ≥ 0
TEORÍA DE LA DUALIDAD
Problema primal en forma algebraica Problema dual en forma algebraica
Maximizar: Z (Xo) = 10X1 + 25X2 Minimizar: W (Yo) = 20Y1 +10Y2
Sujeto a: Sujeto a:
(3/4)X1 + (1/2) X2 ≤ 20 3/4Y1 ≥ 10
X2 ≤ 10 1/2Y1 + Y2 ≥ 25
donde: donde:
X1 ≥ 0, X2 ≥ 0 Y1≥ 0, Y2 ≥ 0
ANÁLISIS DE SENSIBILIDAD
En un problema de programación lineal, se utiliza para estudiar cómo
afectan los cambios de los coeficientes a la solución óptima y los
cambios en el valor independiente a una restricción.
Los valores numéricos en la solución óptima pueden estar sujetos a
cambios
Por ejemplo, los coeficientes de la función objetivo pueden mudar en
relación con los costos de los productos o con la mano de obra;
igualmente, los valores (del lado derecho de las restricciones) que
representan a los recursos pueden cambiar por diversos factores tales
como una huelga o cambios en la materia prima disponible.
El análisis de sensibilidad analiza los límites de operación de los
parámetros de los valores independientes de las restricciones y de los
coeficientes de la función objetivo.
ANÁLISIS DE SENSIBILIDAD
El precio dual es el mejoramiento en el valor de la solución
óptima por unidad de aumento en el valor independiente del
lado derecho de una restricción.
El precio dual y el precio sombra son iguales para todos los
problemas de maximización; sin embargo, en un problema
de minimización, el precio sombra es el negativo del precio
dual correspondiente.
Ambos proporcionan información económica que ayuda a
tomar decisiones para la administración de recursos
adicionales.
