DUAL PRIMAL
Teoría
Se inicia bajo la consideración de que todo problema de programación
lineal tiene un problema asociado; llamándose problema primal al
conocido y problema dual al asociado.
Ambos problemas están muy relacionados, de tal manera que la solución
óptima de cualquiera de ellos proporciona la solución óptima del otro.
Las relaciones entre el primal y el
dual se utilizan para reducir el
esfuerzo de cómputo en ciertos
problemas y para obtener
información adicional sobre las
variaciones en la solución óptima
debidas a ciertos cambios en los
coeficientes y en la formulación
del problema. Esto se conoce
como análisis de sensibilidad o
post-optimidad.
El problema dual se puede obtener a partir del
problema primal y viceversa de la siguiente manera:
1. Cada restricción de un problema corresponde a una variable en
el otro.
2. Los elementos del lado derecho de las restricciones en un
problema son iguales a los coeficientes respectivos de la función
objetivo en el otro.
3. Un problema busca maximizar y el otro minimizar.
4. El problema de maximización tiene restricciones menor o igual que
y el problema de minimización tiene restricciones mayor o igual que.
5. Las variables en ambos casos son no negativas.
Características
a) El problema dual tiene tantas variables
como restricciones tiene el programa primal.
b) El problema dual tiene tantas
restricciones como variables tiene el
programa primal.
c) Los coeficientes de la función objetivo del
problema dual son los términos
independientes de las restricciones o RHS
del programa primal.
d) Los términos independientes de las
restricciones o RHS del dual son los
coeficientes de la función objetivo del
problema primal.
e) La matriz de coeficientes técnicos del
problema dual es la traspuesta de la matriz
técnica del problema primal.
f) El sentido de las desigualdades de las
restricciones del problema dual y el signo de las
variables del mismo problema, dependen de la
forma de que tenga el signo de las variables del
problema primal y del sentido de las restricciones
del mismo problema.
g) Si el programa primal es un
problema de maximización, el
programa dual es un problema de
minimización.
h) El problema dual de un problema
dual es el programa primal original.
PRIMAL DUAL
MAXIMIZAR MINIMIZAR
Restricion ≤ Variable ≥ 0
Restricion = Variable sin restricion de signo
Restricion ≥ Variable ≤ 0
Variable ≥ 0 Restricion ≥
Variable sin restricion de signo Restricion =
Variable ≤ 0 Restricion ≤ 0
¿ Porqué se plantea un problema de
forma dual?
Por una parte permite resolver problemas
lineales donde el numero de restricciones
es mayor que el numero de variables.
Gracias a los teoremas que plantea la
solución de unos de los problemas (
primal o dual) nos proporciona de forma
automática la solución del otro
problema.
¿ Que significado tiene su solución?
La dualidad permite realizar
importantes interpretaciones
económicas de los
problemas de programación
lineal.
¿ La solución del dual se puede
obtener desde el primal?
La dualidad permite generar
métodos como el método dual
del simplex de gran importancia
en el análisis de postoptimización
y en la programación lineal
parametrica.
TEOREMAS DE LA DUALIDAD EN
PROGRAMACIÓN LINEAL
Si el modelo primal o dual tiene solución óptima finita entonces su
respectivo dual o primal tendrán solución óptima finita.
Si el modelo primal o dual tiene solución óptima no acotada, entonces su
respectivo dual o primal no tendrán solución, será un modelo infactible.
Si el modelo primal o dual no tiene solución entonces su respectivo dual o
primal no tendrán solución.
Sea "A" un modelo primal cuyo modelo dual es "B", el modelo dual de "B"
es igual a "A", es decir "El modelo dual de un dual es un modelo primal".
Ejemplo
Dado el siguiente modelo primal, El modelo dual queda de la
siguiente forma:
ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 +
ZMAX = 40X1 + 18X2
120ʎ4
16ʎ1 + 6ʎ2 + ʎ3 ≥ 40
16X1 + 2X2 ≤ 700
2ʎ1 + 3ʎ2 + ʎ4 ≥ 18
6X1 + 3X2 ≤ 612
ʎ1;ʎ4 ≥ 0
X1 ≤ 80
X2 ≤ 120
Ejemplo
Ahora preparamos el modelo para ser resuelto mediante Método Simplex,
utilizaremos el procedimiento en el cual la función objetivo es multiplicada
por (-1) y resolveremos el modelo mediante maximización.
ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 + 120ʎ4
Lo que es igual a:
(-Z)MAX = -700ʎ1 - 612ʎ2 - 80ʎ3 - 120ʎ4
Ejemplo
Ahora dado que los signos de las inecuaciones son mayor o igual
procedemos a volverlas ecuaciones agregando variables de exceso,
recordemos que en este caso las variables de exceso se restan del lado
izquierdo de la igualdad
16ʎ1 + 6ʎ2 + ʎ3 + 0ʎ4 - 1S1 + 0S2 = 40
21ʎ1 + 3ʎ2 + 0ʎ3 + ʎ4 + 0S1 - 1S2 = 18
ʎ1;ʎ4 ≥ 0
Ejemplo
Recordemos que el Método Simplex solo es posible por la formación de la
matriz identidad, sin embargo en una matriz identidad no pueden ir
coeficientes negativos, el cual es el caso, por ende recurriremos al artificio
denominado "Método de la gran M" utilizando variables artificiales, las cuales
siempre se suman.
16ʎ1 + 6ʎ2 + ʎ3 + 0ʎ4 - 1S1 + 0S2 + 1A1 + 0A2 ≥ 40
21ʎ1 + 3ʎ2 + 0ʎ3 + ʎ4 + 0S1 - 1S2 + 0A1 + 1A2 ≥ 18
ʎ1;ʎ4 ≥ 0
Ejemplo
Ahora si observamos la matriz identidad formada por las variables artificiales,
nuestra función objetivo es la siguiente (varía dada la incorporación de las nuevas
variables).
(-Z)MAX = -700ʎ1 - 612ʎ2 - 80ʎ3 - 120ʎ4 + 0S1 + 0S2 - MA1 - MA2
Recordemos que el coeficiente de las variables de holgura y exceso es 0, además
que los coeficientes de las variables artificiales es M, donde M corresponde a un
número grande poco atractivo cuyo signo en la función objetivo depende del
criterio de la misma, dado que la función es maximizar el signo es negativo. Dado
que utilizaremos el Método Simplex y no un software para la resolución del modelo
es necesario que M adquiera valor, en este caso será "-10000" un número bastante
grande en el problema.
Ejemplo
Ejemplo
Podemos observar que todos los Cj - Zj son menores o iguales a 0, por ende
hemos llegado a la solución óptima del problema, sin embargo
recordemos que la función objetivo fue alterada en su signo al principio,
por ende se hace necesario regresarle su signo original a Zj y a la fila Cj - Zj.
(-Z)max = -3310 * (-1)
Zmax = 3310
Podemos cotejar con la función objetivo del modelo primal y encontraremos
que hallamos el mismo resultado.
Interpretación de los resultados
Ahora se hace necesario interpretar los resultados de la tabla dual respecto al
modelo primal, y esta interpretación se realiza siguiendo los siguientes
principios.
Interpretación de los resultados
Análisis de sensibilidad
El análisis de sensibilidad es un término financiero, muy utilizado en las
empresas para tomar decisiones de inversión, que consiste en calcular los
nuevos flujos de caja y el VAN (en un proyecto, en un negocio, etc.), al
cambiar una variable (la inversión inicial, la duración, los ingresos, la tasa
de crecimiento de los ingresos, los costes, etc.) De este modo teniendo los
nuevos flujos de caja y el nuevo VAN podremos calcular y mejorar nuestras
estimaciones sobre el proyecto que vamos a comenzar en el caso de que
esas variables cambiasen o existiesen errores de apreciación por nuestra
parte en los datos iniciales.
Wikipedia, 2019
En IO
Llamaremos Análisis de Sensibilidad al estudio de la variación del optimo de un LP producto
de modificaciones de ciertos parámetros como coeficientes de variables en la función
objetivo, coeficientes del lado derecho de restricciones, etc.
La idea general consiste en determinar rangos de variación de los parámetros del LP de
forma de mantener una cierta base optima, teniendo en cuenta que una solución básica es
factible sólo si todas las variables básicas tienen un valor no negativo.
Posibilidades:
1. Cambio del coeficiente en la función objetivo de una variable no básica.
2. Cambio del coeficiente en la función objetivo de una variable básica.
3. Cambio del coeficiente del lado derecho de una restricción.
4. Incorporación de una nueva variable.
5. Incorporación de una nueva restricción.
INTERVALO DE VARIACIÓN COEFICIENTES DE
LA FUNCIÓN OBJETIVO
Por ejemplo, actualmente el coeficiente que acompaña a X1 en la
función objetivo (de maximización) es 40. La solución óptima se mantendrá
en la medida que dicho coeficiente varié en el intervalo entre [0,144] y
asumiendo que el resto de los parámetros del modelo permanecen
constante. También se puede llegar a una conclusión similar para el
coeficiente que acompaña a X2 en la función objetivo (actualmente 18) y
cuyo rango de variación que conserva la actual solución óptima es [0,Inf].
PRECIO SOMBRA DE LAS
RESTRICCIONES
El precio sombra corresponde a una tasa de cambio del valor óptimo ante
una modificación marginal de un lado derecho de una restricción. Por
ejemplo, el lado derecho de la restricción 1 es 700 y su precio sombra es
2,5. El intervalo donde este precio sombra es válido es [912,1160] es decir
que cualquier variación de dicho lado derecho en ese intervalo provocará
una variación proporcional al precio sombra en cuanto al valor de la
función objetivo.
Por ejemplo, si el lado derecho aumenta de 700 a 800 el nuevo valor
óptimo será V(P)= 3310 + (800-700)*2,5 = 3560. Nuevamente se asume que
el resto de los parámetros del modelo permanecen constante.
PRECIO SOMBRA DE LAS
RESTRICCIONES
Otro aspecto relevante del precio sombra resulta ser su significado
económico. Los lados derechos en el caso de un modelo de maximización
generalmente están asociados a la disponibilidad de recursos escasos, por
ejemplo, para la utilización en un proceso productivo (materiales, horas
hombre, recursos financieros, etc). En este sentido el precio sombra puede
representar una disposición a pagar por unidad adicional de recurso. En el
ejemplo anterior se puede considerar que como máximo se pagará $2,5
por cada unidad adicional del recurso (lado derecho) de la primera
restricción. Si el precio del recurso es menor al precio sombra entonces
existirá un incentivo a "comprar" más debido a que esto tendrá un impacto
neto positivo en la función objetivo.
ExcelQM
