ANALISIS DE DUALIDAD
Conceptos Básicos
Modelo Dual
Pasos para convertir a
modelo Dual
Ejemplos de Aplicación
Conceptos básicos
El concepto de dualidad plantea que, asociado a todo problema de
programación lineal, existe otro problema lineal llamado dual .
El problema de programación lineal dual que se define a partir
de un problema original (primal), comparte con el :
a) Los mismos coeficientes tanto de la función objetivo y
b) Los coeficientes de las restricciones, pero en diferente posición
Uno de los papeles clave que juega la teoría de la dualidad es la
interpretación y realización del análisis de sensibilidad ( siguiente tema )
• Todo problema en Programación
lineal primal, encuentra un problema
Análisis de dual con soluciones iguales, es decir,
cada problema resolviéndolo en la
Dualidad forma inversa, nos dará igual
solución que la primal
Ventajas de la Dualidad
Si la cantidad de variables en el primal fuera bastante
menor que la cantidad de restricciones. Ya que la
cantidad de cálculos simplex depende mucho de la
cantidad de restricciones.
Otra de las ventajas que presenta es que dado a que el
número de restricciones y variables entre problema dual
y primal es inverso, se pueden resolver gráficamente
problemas que presenten dos restricciones sin importar
el número de variables
Modelo Dual : Método Simplex Dual
En particular este método se puede utilizar cuando al
llevarlo a la forma estándar un modelo de Programación
Lineal no se dispone de una solución básica factible inicial
y la aplicación del método simplex es compleja
La aplicación básica del método simplex dual es cuando :
1. Función objetivo del PL es de Minimización ( Zmin )
2. Restricciones del tipo >= ( Mayor que )
Modelo Dual : Método Simplex Dual
Como el dual del problema es en si mismo el
problema primal (original ), los métodos
presentados se pueden aplicar en forma simétrica
para determinar la solución optima del primal a
partir del dual.
Solución problema Dual Solución problema Primal ( original )
El dual es formulado partiendo del
problema primo en la siguiente forma:
• Si el primo es un problema de Maximización, el dual es un problema de
1 Minimización y viceversa.
• Los coeficientes de la función objetivo del primo se convierten en las
2 restricciones constantes de las ecuaciones del dual.
• Las restricciones de las ecuaciones del primo se convierten en los coeficientes
3 de la función objetivo del dual.
• Los coeficientes de las variables del DUAL en las ecuaciones restrictivas son obtenidas sacando la
transpuesta de la matriz de coeficientes del primo (los arreglos de los coeficientes en las
4 columnas del primo se convierten en los coeficientes de las filas en el dual y viceversa).
• Los signos de la desigualdad son invertidos.
5
• Las X variables del primo son remplazadas por Y variables en el dual
6
Ejemplo 1: Conversión al modelo Dual
1. Paso : F.O Maximización a Minizacion o
viceversa Min Z
2. Paso : Coeficiente F.O del dual Es el
coeficiente de Rest. del primal
3. Paso : Constante Rest. del dual Es el
coeficiente de las F.O del primal
4. Paso : Coeficientes de las rest. Columnas
del primal son las Filas en el Dual
5. Paso : Signos de desigualdad son
invertidos <= a >=
6. Paso : Las X del Primo son las Y del
Dual (o variables diferentes )
Ejemplos : Conversión al modelo Dual
Primal Primal
Max 200x+150y+120z Max 3x+3y+3z
Sujeto a:15x+7.5y+5z < o = 315 Sujeto a:2x+10y+4z <o = 500
2x+3y+2z < o = 110 2y+4z < o = 100
x + y+ z < o = 50 10x + 20y+ 10z <= 1000
x, y, z,> o = 0 x, y, z,> o = 0
Dual Dual
Min 315A+110B+ 50C Min 500A+100B+ 1000C
Sujeto a:15A+2B+1C > o = 200 Sujeto a:2A+10C > o = 3
7.5A+3B+1C > o = 150 10A+2B+20C > o = 3
5A +2B+ 1C > o = 120 4A +4B+ 10C > o = 3
A, B, C,> o = 0 A, B, C,> o = 0
Ejemplos : Conversión al modelo Dual
Primal Primal
Min Z = 2X1 + 3X2 Max 2X1+X2+3X3+6X4
Sujeto a; Sujeto a:2x1+2X2+X3+X4 < o = 8
2X1 + X2 < o = 16 2X1 +X3+2X4 < o = 12
X1 + 3X2 < o = 20 X1,X2,X3,X4 > o = 0
X1 + X2 < o 10
X1,X2 > o =0
Dual
Dual
Min 8Y1+12Y2
Max Z=16W1 + 20W2+10W3
Sujeto a:2Y1+2Y2 > o = 2
Sujeto a;
2Y1 > o = 1
2W1 + W2 +W3 > o = 2
Y1+Y2 > o = 3
W1 + 3W2 +W3 > o = 3
Y1+2Y2> o = 6
De tres (3) restricciones pasamos a De dos (2) restricciones pasamos a
dos restricciones (2 ) ; pero se alargo la cuatro(4 ) ; pero se acorta la F.O y nos
F.O quedamos con 2 variables únicamente
Ejemplos : Conversión al modelo Dual
ANALISIS DE SENBILIDAD
Análisis de Sensibilidad
Análisis de Sensibilidad : Es el estudio de cómo los cambios en
los coeficientes de un problema de programación lineal afectan a
la solución optima .
Este análisis es importante para los tomadores de decisiones
debido a que los problemas reales ocurren en un entorno en
constante cambio
Se conoce también como análisis de Postoptimalidad ya que
comienza hasta que se obtiene la solución optima del problema
de PL
Análisis de Sensibilidad
El análisis de sensibilidad proporciona información necesaria para
responder a estos cambios sin requerir una solución radical de un
programa lineal modificado
También se utiliza para determinar cuales coeficientes en el
modelo de programación lineal son cruciales .
Como afectara el cambio de un coeficiente de la función
objetivo a la solución optima ?
El análisis de sensibilidad puede ayudar a determinar cuanto vale
cada unidad de material adicional y cuantas unidades se pueden
añadir antes de que disminuyan los rendimientos establecidos .
Como afectara el cambio de un valor de lado derecho de una
restricción a la solución optima
Conceptos Básicos
1. Costo Reducido: Indica cuanto tendría que mejorar cada uno de
los coeficientes de la función objetivo antes de que la
correspondiente variable de decisión pueda tomar valor
positivo en la solución optima.
2. Rango de Optimalidad: Intervalo de valores permisible para que
NO cambie la solución optima
3. Precio Dual: Mejora en el valor de la función objetivo por cada
incremento unitario en el lado derecho de la restricción. En un
problema de maximizar el precio dual es el mismo precio
sombra. En un problema de minimizar el precio dual es el
negativo del precio sombra.
Ejemplo # 1 en Solver
Microsoft Office
Excel Worksheet
Ejemplo # 1 : Informe de Respuesta
VALOR OPTIMO
DE LA FUNCION
OBJETIVO
SOLUCION OPTIMA
DE LAS VARIABLES
X=2 unidades
Y=2 unidades
CARENCIA O
EXCEDENTE
Ejemplo # 1 : Informe de
Confidencialidad o Sensibilidad
CUANTO PODRIA LA SOLUCION NO
MEJORAR LOS CAMBIA SI :
COHEFICIENTES X varia de 1 a 3
( GANANCIA ) DE LA F.O Y varia de 1.5 a 3
RANGO DE
OPTIMALIDAD
PRECIOS
DUALES
RANGOS DEL
LADO DERECHO
DE LAS
RESTRICCIONES
Ejemplo # 2 en Solver
Microsoft Office
Excel Worksheet
Ejemplo # 2 : Informe de Respuesta
VALOR OPTIMO
DE LA FUNCION
OBJETIVO ( Z )
SOLUCION
OPTIMA
X=0
Y=115
CARENCIA O
EXCEDENTE
REST # 3
REST # 2
REST # 1
Ejemplo # 2 : Informe de
Confidencialidad o Sensibilidad
CUANTO PODRIA LA SOLUCION NO
MEJORAR LOS CAMBIA SI :
COHEFICIENTES X varia de 1 a 3
( GANANCIA ) DE LA F.O Y varia de 1.5 a 3
RANGO DE
OPTIMALIDAD
PRECIOS
DUALES
RANGOS DEL
LADO DERECHO
DE LAS
RESTRICCIONES
Ejemplo # 3
Televisor Hi-Fi Altavoces Disponibles
Chasis 1 1 0 450
Tubo de imágenes 1 0 0 250
Conos de altavoces 2 2 1 800
Fuente de alimentación 1 1 0 450
Componentes electrónicos 2 1 1 600
Beneficios por Producto 75 50 35
Estos componentes están disponibles en cantidades limitadas, por lo que se trata de plantear el
problema de maximización restringida de beneficios sabiendo que la contribución neta de los tres
productos es, respectivamente, de 75 €, 50 €, y 35 €.
El primer paso sería plantear el problema en la hoja de cálculo:
Televisores HiFi Altavoces Funcion Objetivo
200 200 0 25000 VLD Holgura
Max 75 50 35
Restricciones
Chasis 1 1 0= 400 450 -50
Tubo de Imágenes 1 0 0= 200 250 -50
Conos de Altavoces 2 2 1= 800 800 0
Fuente de Alimentacion 1 1 0= 400 450 -50
Componente Electrico 2 1 1= 600 600 0
Ejemplo # 3: Informe de Respuesta
Ejemplo # 3 : Informe de
Confidencialidad o Sensibilidad
Análisis del Ejemplo ( Resumen )
Cambios Simultáneos
( Si dos o mas coeficientes de F.O cambian simultáneamente )
Regla del 100% para los coeficientes de la F.O : Para todos los
coeficiente de la función objetivo que cambian , sume los porcentajes de
los aumentos y las disminuciones permisibles ; si la suma es menor o
igual al 100% , la solución optima no cambiara
Asumamos que estos valores
cambian a 2 y 4 respectivamente
Calculo de la regla del 100% para X ( Decrease)
X =(3-2)=11/1= 1 =100 %
Calculo de la regla del 100% para Y ( Increase )
Y =(4-2)=22/1= 2 =200 %
No cumple ( 100% +200% =300%>100% La solución optima NO se
mantiene , si cambiara )
Cambios Simultáneos
( Si dos o mas coeficientes de F.O cambian simultáneamente )
Asumamos que estos
valores cambian a 4 y
4 respectivamente
Calculo de la regla del 100% para X ( Increase )
X=(4-3)=11/2= 0.5=50 %
Calculo de la regla del 100% para Y ( Decrease )
Y=(5-4)=11/2= 0.5 =50 %
Si cumple ( 50% + 50% = 100% ) La solución optima NO cambia
Tarea # 4
Ejercicios Prácticos
Modelo Dual &
Análisis de Sensibilidad
Gracias !!!!