CONTENIDO
§ PROBLEMA DUAL DE LA PROGRAMACION LINEAL
§ CASOS BASICO DE LOS PROBLEMAS DUALES.
§ NORMAS PARA PLANTEAR UN PROBLEMA DUAL.
§ ENLACE EJERCICIO APLICADO DEL PROBLEMA DUAL
http://spreadsheets.google.com/pub?key=pAAIO2lY9BwKPp9hyq9MJew&gid=1
§ INTERPRETACION DE LA SOLUCION SIMPLEX PARA EL PROBLEMA DUAL Y EL PRIMAL
PROBLEMA DUAL DE LA PROGRAMACION LINEAL
Todo problema de programación lineal primal, tiene asociado otro problema dual. Útil también para optimizar problemas específicos de producción, inventarios, transporte, almacenamiento, dietas, finanzas etc.
Si el problema primal se plantea como maximizar, el problema dual se plantea como minimizar y viceversa.
§ Dual Asimétrico. Se da cuando hay una igualdad.
§ Dual Simétrico. Se da cuando hay una desigualdad así: desigualdad tipo uno (1) si es <>
Después de plantear el problema dual, a partir del problema primal, el problema dual se resuelve aplicando el método SIMPLEX, el cual se explico en este mismo blog.
CASOS BASICO DE LOS PROBLEMAS DUALES.
CASO 1
1. Si el problema primal es Maximizar:
Z= C.X = función objetivo
Sujeta a las restricciones:
AX < B
Con condición de no negatividad:
Xi > 0
2. Entonces el problema dual será Minimizar
G=B.W = Función Objetivo
(B son los coeficientes independientes de las restricciones del primal y W corresponde a las nuevas variables del problema dual)
Sujeta a las restricciones:
A”W > C
(A” son los coeficientes de las variables de las restricciones del primal y C son los coeficientes de la función objetivo del primal
Con condición de no negatividad.
Wi > 0
CASO 2
1. Si el problema primal es Maximizar:
Z= C.X = función objetivo
Sujeta a las restricciones:
AX =B
Con condición de no negatividad:
Xi > 0
2. Entonces el problema dual será Minimizar
G=B.W = Función Objetivo
(B son los coeficientes independientes de las restricciones del primal y W corresponde a las nuevas variables del problema dual)
Sujeta a las restricciones:
A”W > C
(A” son los coeficientes de las variables de las restricciones del primal y C son los coeficientes de la función objetivo del primal
Wi, no tiene restricción de signo
CASO 3
1. Si el problema primal es Minimizar
Z= C.X = función objetivo
Sujeta a las restricciones:
AX > B
Con condición de no negatividad:
Xi > 0
2. Entonces el problema dual será Maximizar
G=B.W = Función Objetivo
(B son los coeficientes independientes de las restricciones del primal y W corresponde a las nuevas variables del problema dual)
Sujeta a las restricciones:
A”W < C
(A” son los coeficientes de las variables de las restricciones del primal y C son los coeficientes de la función objetivo del primal
Con condición de no negatividad.
Wi > 0
Nota: Si las restricciones a que está sujeta la función objetivo tienen combinaciones de desigualdades de tipo 1(<), tipo 2 (>) e igualdades (=). Se deben tener en cuenta algunas normas específicas para plantear el problema dual. A continuación se presentan las normas para plantear un problema dual e ilustramos con ejemplos si es necesario.
NORMAS PARA PLANTEAR UN PROBLEMA DUAL.
NORMA1. Si el primal es de tipo maximizar cualquier desigualdad de tipo 2, debe convertirse en desigualdad de tipo 1 antes de plantear el dual. Ejemplo:
§ Problema Primal: Maximizar.
Z= 2X1+2X3+2X3 (Z=CX)
Sujeto a las siguientes restricciones:
1X1+1X2+1X3<4
1X1+0X2+1X3>6
0X1+1X2+1X3<3
1X1+1X2+0X3>2
Para todo X1, X2 y X3 mayor igual a cero
Entonces la conversión para las desigualdades de tipo 2 es:
1X1+1X2+1X3<4
-1X1-0X2-1X3<-6
0X1+1X2+1X3<3
-1X1-1X2-0X3<-2
Las desigualdades de tipo 1 quedan iguales.
§ Problema Dual: Minimizar.
G=4W1-6W2+3W3-2W4
Sujeto a las siguientes restricciones:
1W1-1W2+0W3-1W4>2
1W1-0W2+1W3-1W4>2
1W1-1W2+1W3-0W4>2
Para todo W1, W2 y W3 mayor igual a cero
Para resolver este problema dual se aplica el método Simplex.
NORMA2. Si el primal es de tipo minimizar cualquier desigualdad de tipo 1 debe convertirse a desigualdad de tipo 2 antes de entrar a plantear el problema dual
NORMA3. Si el primal es de tipo minimizar, su problema dual será de tipo maximizar y viceversa.
NORMA4. Si la r-esima variable del primal no tiene restricción de signo entonces la r-esima condición del dual debe de ser una igualdad. Ejemplo
PRIMAL: MAXIMIZAR: Z=6X1+3X2+1X3
SUJETO A LAS SIGUIENTES RESTRICCIONES:
6X1+3X2+1X3<4
3X1+3X2-1X3<3
1X1+0X2+1X3<1
X1 y X3 >0
En este caso la r-esima variable del primal es X2 por que no tiene restricción de signo
DUAL: MINIMIZAR G=4W1+3W2+1W3
SUJETO A LAS SIGUIENTES RESTRICCIONES:
6W1+3W2+1W3>6
3W1+3W2+0W3 = 3 (r-esima condición del dual)
1W1-1W2+1W3>1
W1, W2, W3 >0
NORMA5. Si la r-esima variable del primal tiene la condición de no negatividad, entonces la r-esima condición del dual será una desigualdad de tipo 1si el primal es de tipo mínimo y será una desigualdad de tipo 2 si el primal es de tipo máximo.
En el ejemplo de la norma 4 el primal es de tipo máximo y la r-esima variable es X1 y también X3, que tienen restricción de no negatividad. Entonces la r-esima condición del dual es la restricción 1 y también la restricción 3 y son desigualdades de tipo 2.
NORMA6. Si la s-esima condición del primal es una igualdad, entonces la s-esima variable del dual no tiene restricción de signo. Ejemplo
PRIMAL: MINIMIZAR: Z= 2X1+3X2
SUJETA A LAS SIGUIENTES RESTRICCIONES:
1X1+1X2>1
1X1+3X2=3 (s-esima condición del primal)
2X1+1X2>2
X1 y X2 >0 (condición de no negatividad)
DUAL: MAXIMIZAR G=1W1+3W2+2W3
SUJETA A LAS SIGUIENTES RESTRICCIONES:
1W1+1W2+2W3<2
1W1+3W2+1W3<3
W1 y W3 >0
W2 es la s-esima variable del dual y no tiene restricción de signo
NORMA7. Si la s-esima condición del primal es una desigualdad, entonces la s-esima variable del dual debe tener restricción de no negatividad.
Esta condición se observa en el ejemplo de la norma 6 donde
s-esima condición del primal son las restricciones 1 y 3 a que esta sujeta la función objetivo
y las s-esimas variables de dual son W1 y W3 que tienen condición de no negatividad.
EJERCICIO APLICADO DEL PROBLEMA DUAL
El ejercicio que se presenta en el enlace:
http://spreadsheets.google.com/pub?key=pAAIO2lY9BwKPp9hyq9MJew&gid=1
Es un ejercicio aplicado a la producción y más exactamente a la optimización de los costos de producción de artículos en función de la cantidad de los mismos a elaborar, de las relaciones de consumo de las materias primas y de las disponibilidades y condiciones del suministro de las materias primas.
En el enlace este ejercicio se desarrolla en la hoja de cálculo 1. En la hoja de cálculo 2 se desarrolla el mismo ejercicio por el método Simplex de dos formas diferentes: como un problema de minimización y posteriormente se desarrolla convirtiéndolo previamente a un problema de maximización.
INTERPRETACION DE LA SOLUCION SIMPLEX PARA EL PROBLEMA DUAL Y EL PRIMAL
http://spreadsheets.google.com/pub?key=pAAIO2lY9BwKPp9hyq9MJew&gid=1
La interpretación de los resultados es la siguiente:
1) Desarrollándolo como un problema dual por el método simplex. (ver enlace hoja 1). La tabla de la tercera solución, corresponde a la optima, es decir al costo mínimo de producción de los artículos A y B (Zj=254), la respuesta se da para los valores óptimos de Y1 y Y2, pero en realidad los valores óptimos de X1 y X2 (cantidad de los artículos A y B) aparecen con signo cambiado como las entradas (Cj-Zj) para H1 y H2, por lo tanto X1 y X2 pueden obtenerse también de la solución dual.
Para que el costo de producción de los artículos A y B sea mínimo (254), se deben fabricar 14 toneladas de alimento A (X1) y 33 toneladas de Alimento B (X2)
2) Desarrollándolo como un problema primal por el método simplex. (ver enlace hoja 2). La tabla de la tercera solución corresponde a la óptima. En esta solución intervienen las variables X1 (cantidad de toneladas del Articulo A) y X2 (cantidad de toneladas del articulo B). La solución en la tabla la da la columna encabezada con Po. y es
X1=14 toneladas de alimento A a fabricar
X2=33 toneladas de alimento B a fabricar
Zj=254 costo mínimo de producción de los alimentos A y B, en función de las relaciones de consumo de las materias primas y de las restricciones de suministro de las mismas.
SUJETO A LAS SIGUIENTES RESTRICCIONES:
6X1+3X2+1X3<4
3X1+3X2-1X3<3
1X1+0X2+1X3<1
X1 y X3 >0
En este caso la r-esima variable del primal es X2 por que no tiene restricción de signo
DUAL: MINIMIZAR G=4W1+3W2+1W3
SUJETO A LAS SIGUIENTES RESTRICCIONES:
6W1+3W2+1W3>6
3W1+3W2+0W3 = 3 (r-esima condición del dual)
1W1-1W2+1W3>1
W1, W2, W3 >0
NORMA5. Si la r-esima variable del primal tiene la condición de no negatividad, entonces la r-esima condición del dual será una desigualdad de tipo 1si el primal es de tipo mínimo y será una desigualdad de tipo 2 si el primal es de tipo máximo.
En el ejemplo de la norma 4 el primal es de tipo máximo y la r-esima variable es X1 y también X3, que tienen restricción de no negatividad. Entonces la r-esima condición del dual es la restricción 1 y también la restricción 3 y son desigualdades de tipo 2.
NORMA6. Si la s-esima condición del primal es una igualdad, entonces la s-esima variable del dual no tiene restricción de signo. Ejemplo
PRIMAL: MINIMIZAR: Z= 2X1+3X2
SUJETA A LAS SIGUIENTES RESTRICCIONES:
1X1+1X2>1
1X1+3X2=3 (s-esima condición del primal)
2X1+1X2>2
X1 y X2 >0 (condición de no negatividad)
DUAL: MAXIMIZAR G=1W1+3W2+2W3
SUJETA A LAS SIGUIENTES RESTRICCIONES:
1W1+1W2+2W3<2
1W1+3W2+1W3<3
W1 y W3 >0
W2 es la s-esima variable del dual y no tiene restricción de signo
NORMA7. Si la s-esima condición del primal es una desigualdad, entonces la s-esima variable del dual debe tener restricción de no negatividad.
Esta condición se observa en el ejemplo de la norma 6 donde
s-esima condición del primal son las restricciones 1 y 3 a que esta sujeta la función objetivo
y las s-esimas variables de dual son W1 y W3 que tienen condición de no negatividad.
EJERCICIO APLICADO DEL PROBLEMA DUAL
El ejercicio que se presenta en el enlace:
http://spreadsheets.google.com/pub?key=pAAIO2lY9BwKPp9hyq9MJew&gid=1
Es un ejercicio aplicado a la producción y más exactamente a la optimización de los costos de producción de artículos en función de la cantidad de los mismos a elaborar, de las relaciones de consumo de las materias primas y de las disponibilidades y condiciones del suministro de las materias primas.
En el enlace este ejercicio se desarrolla en la hoja de cálculo 1. En la hoja de cálculo 2 se desarrolla el mismo ejercicio por el método Simplex de dos formas diferentes: como un problema de minimización y posteriormente se desarrolla convirtiéndolo previamente a un problema de maximización.
INTERPRETACION DE LA SOLUCION SIMPLEX PARA EL PROBLEMA DUAL Y EL PRIMAL
http://spreadsheets.google.com/pub?key=pAAIO2lY9BwKPp9hyq9MJew&gid=1
La interpretación de los resultados es la siguiente:
1) Desarrollándolo como un problema dual por el método simplex. (ver enlace hoja 1). La tabla de la tercera solución, corresponde a la optima, es decir al costo mínimo de producción de los artículos A y B (Zj=254), la respuesta se da para los valores óptimos de Y1 y Y2, pero en realidad los valores óptimos de X1 y X2 (cantidad de los artículos A y B) aparecen con signo cambiado como las entradas (Cj-Zj) para H1 y H2, por lo tanto X1 y X2 pueden obtenerse también de la solución dual.
Para que el costo de producción de los artículos A y B sea mínimo (254), se deben fabricar 14 toneladas de alimento A (X1) y 33 toneladas de Alimento B (X2)
2) Desarrollándolo como un problema primal por el método simplex. (ver enlace hoja 2). La tabla de la tercera solución corresponde a la óptima. En esta solución intervienen las variables X1 (cantidad de toneladas del Articulo A) y X2 (cantidad de toneladas del articulo B). La solución en la tabla la da la columna encabezada con Po. y es
X1=14 toneladas de alimento A a fabricar
X2=33 toneladas de alimento B a fabricar
Zj=254 costo mínimo de producción de los alimentos A y B, en función de las relaciones de consumo de las materias primas y de las restricciones de suministro de las mismas.
