Embed Size (px)
Citation preview
UNIDAD UNO
PROGRAMACIÓN
LÍNEAL
Parte 4
Ing. César Urquizú
Ing. César Urquizú
Teoría de la dualidad
El desarrollo de esta teoría de la dualidad es debido al interés que
existe en la interpretación económica del problema que se estudia.
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.
El problema dual de cualquier problema primal se puede obtener
con manejo algebraico, convirtiendo primero a las formas canónicas
ya conocidas y después a la correspondiente al dual.
Ing. César Urquizú
Problema dual obtenido en la forma
canónica.
En donde
C: es un vector renglón de coeficientes de la función objetivo primal.
b: es un vector columna de términos independientes de restricciones del primal.
A: es una matriz de coeficientes tecnológicos de restricciones del primal.
X: es un vector columna de variables del primal.
T: es la transpuesta del vector o matriz.
Y: es un vector columna de variables duales.
Dual asociado a un PL primal en forma
canónica de máximo
Para el dual, los coeficientes del ejemplo se arreglan en sus vectores como sigue:
Dual asociado a un PL primal en forma canónica de
mínimo
Se producen dos clases de fertilizante distinguidos
por contenido químico, disponibilidad del mismo
y costo de ingredientes como se muestra aquí:
Significado de las variables duales.
La interpretación económica del problema en estudio, es posible a partir
de la conversión del problema primal a su correspondiente dual asociado,
con el análisis de las unidades dimensionales del primero. Esta interpretación
no es única y es según el interés de quien lo estudia. Considere el ejemplo de
producción de fertilizantes.
Primera parte .- Definición de variables:
Segunda parte.- Función objetivo o económica:
Tercera parte.- Sujeta a las restricciones:
Cuarta parte.- Condiciones de signo para variables:
• Problema dual.
• Primera parte.- Definición de variables duales.
• Segunda parte.- Función económica
• Tercera parte.- Sujeta a las restricciones:
• Cuarta parte.- Condiciones de signo:
La función objetivo dual significa la cantidad mínima de
dinero que se debe recuperar de la materia prima, en caso
de tener que parar la producción de fertilizantes; cada término de
dicha función representa la contribución de los componentes N,
P, K, en la venta total. Cada término de las restricciones duales
significa la contribución ( $ ) de los componentes químicos i, a la
utilidad de una tonelada de fertilizante j.
• Los componentes químicos tienen valor para la empresa debido a que
representan la oportunidad de tener utilidad. Para conseguirlo debe
buscar la combinación más redituable de manera que el valor
marginal de unidades adicionales de recurso sea mínimo.
• Por esto, también se puede interpretar la función objetivo dual, como
representación del valor mínimo de los recursos N, P, K, utilizados
en la producción de fertilizante.
Precio Sombra.- Se define como la proporción con que mejora el
valor de la función objetivo a partir de la i - ésima restricción,
dependiendo si se trata de maximización tiende a aumentar y a
disminuir cuando es de minimización.
La interpretación económica de la dualidad se basa directamente en
la interpretación más frecuente del problema primal
Problema del carpintero1:
X1: Número de Mesas a producir
X2: Número de sillas a producir
Maximizar las ganancias Z= 5X1 + 3X2
sa:
2X1 + X2 ≤ 40 Restricción de mano de obra
X1 + 2X2 ≤ 50 Restricción de materiales
X1, X2 ≥ 0
Solución óptima {Z = 110, X1=10, X2 =20}
Supóngase que el carpintero desea contratar un seguro para sus ingresos netos, entonces que
tendría el seguro que determinar?
- Y1 = El monto en dólares a pagar al carpintero por cada hora de trabajo perdida.
- Y2 = El monto en dólares a pagar al carpintero por cada unidad de materia prima perdida
Por supuesto que el corredor de seguros intenta minimizar el monto total de dólares a pagar por la
compañía de seguros, que sería: “40 horas de mano de obra *el costo de cada hora (Y1) mas 50
unidades de materiales * el costo de unidad de materiales (Y2).”
La función a minimizar por el Seguro es: W = 40Y1+50Y2, como vemos corresponde con la
función objetivo del Dual. Como es de esperar el carpintero fijara las restricciones es decir las
condiciones para que la compañía de seguros cubra la pérdida que equivale a sus ingresos netos,
debido a que no puede fabricar los productos, en consecuencia las restricciones serían:
2Y1 + Y2 ≥ 5 (Ingresos neto por una mesa)
Y1 + 2Y2 ≥ 3 (Ingresos netos por una silla)
Y1, Y2 ≥ 0
Por todo ello el problema de la compañía de seguro es:
Min, W= 40Y1 + 50Y2
sa:
2Y1 + Y2 ≥ 5
Y1 + 2Y2 ≥ 3
Y1 ≥ 0
Y2 ≥ 0
Correspondiente al Dual del Pl original.
Si determinamos la solución a este PL Dual, obtenemos:
Y1=7/3 (Corresponde al precio sombra de la primera restricción en el Primal, es decir
el precio sombra del recurso “hora de mano de obra”)
Y2 =1/3 (Corresponde al precio sombra de la segunda restricción en el Primal, es
decir el precio sombra del recurso “unidad de materia prima”)
W = 110 ( este es el monto que el carpintero espera recibir, este valor coincide con su
ganancia si el produjera sillas y mesas).
El valor óptimo W del Dual = valor óptimo del Primal Z
El carpintero solo tendría un costo adicional por la comisión que cobra la compañía
de seguros.
El problema dual:
y0 = b1y1 + b2y2 + ................ + bmym
Y0 = Ganancia total en la iteración actual.
yi = Contribución a la ganancia por cada unidad
del recurso i.
biyi = Aporte a la ganancia por disponer de bi
unidades del recurso i (en el primal).
FORMA DE PRESENTAR EL PROBLEMA DUAL
MIN = 2X1 - 3X2
Sujeto a:
1X1 + 2X2 12
4X1 - 2X2 3
6X1 - 1X2 = 10
X1,2 0
1. Llevar el problema a su equivalente de maximización, multiplicando la función
objetivo por –1: MAX -2X1 + 3X2
2. Convertir las restricciones en una restricción equivalente multiplicando por –
1 ambos lados: -4x1 + 2x2 -3
3. Para las restricciones de igualdad, obtener 2 restricciones de desigualdad, una
de forma y la otra de forma ; después regresar al punto anterior y cambiar la
restricción a la forma :
6X1 – 1X2 10
6X1 – 1X2 10
6X1 – 1X2 10
-6X1 + 1X2 -10
Así el problema primal se ha replanteado en la forma equivalente:
MAX Z= -2X1 + 3X2
Sujeto a:
1X1 + 2X2 12
-4X1 + 2X2 - 3
6X1 – 1X2 10
-6X1 + 1X2 -10
X1,2 0
Así el problema primal se ha replanteado en la forma
equivalente:
MAX Z= -2X1 + 3X2
Sujeto a:
1X1 + 2X2 12
-4X1 + 2X2 - 3
6X1 – 1X2 10
-6X1 + 1X2 -10
X1,2 0
Teniendo el problema primal convertido a la forma canónica de un
problema de maximización, es fácil llevarlo al problema dual:
MIN 12Y1 – 3Y2 + 10 Y’3 - 10 Y’’3
Sujeto a: Y1–4Y2 + 6Y3’–6Y3’’ -2
2Y1 + 2Y2 – 1Y3’ + 1Y3’’ 3
Y1, 2, 3’, 3’’ 0
Y’3 y Y’’3 ambas se refieren a la tercera restricción del problema primal.
Método de Dos fases
