Problema Dual

PROBLEMA DUAL
Se llama problema dual al modelo matemtico que se deriva directamente del problema original,
llamada tambin primal, y se puede establecer para todos los casos a partir de la forma estndar.
Cabe recordar que la forma estndar es aquel ppl que puede ser maximizar o minimizar, todas sus
restricciones son ecuaciones (igualdades), todas sus variables son no negativas, es decir:
Aij . Xj = Bi
donde i=1,2,3,.,m
Xj >= 0 j= 1,2,3,,n
Bi >=0
REGLAS DEL DUAL
A partir de esta forma se obtiene simtricamente el problema dual siguiendo las siguientes reglas:
1) A toda restriccin primal le corresponde una variable dual
2) A toda variable primal le corresponde una restriccin dual
Es decir en el Dual se obtendrn n restricciones y m variables
3) Los coeficientes en las restricciones de una variable primal son los coeficientes de la restriccin
dual correspondiente
4) Los coeficientes de la funcin objetivo primal se convierten en los valores constantes del
segundo miembro de las restricciones duales.
5) Si el primal es maximizacin, entonces: En el dual tenemos la funcin objetivo de minimizacin,
las restricciones son todas >= y las variables son irrestrictas en signo.
6) Si el primal es minimizacin, entonces: En el dual tenemos la funcin objetivo de maximizacin,
las restricciones son todas <= y las variables son irrestrictas en signo.
(Nota: todas las restricciones primales son restricciones con segundos miembros no negativos; y
todas las variables son no negativas)
7) Los segundos miembros de la restricciones primales son los coeficientes de los coeficientes dual
EJERCICIO
PRIMAL
Max Z= 5x1 + 12 x2 + 4x3 + x4 tres restricciones
Sa x1 + 2x2 + x3 <= 10 Y1
2x1 x2 +3x3 = 8 Y2
Xj >=0
DUAL hay q estandarizar la primal (todas les resctricciones sean de igualdad, 10 , 8 no negativos)
Sean Yj variables duales
Min G = 10 Y1 + 8 Y2
Sa Y1 + 2 Y2 >=5
2Y1 Y2 >= 12
Y1 + 3 Y2 >= 4
Y1 >= 0
Y2 irrestricta
Max w = 10 Y1 + 8 Y2
Sa Y1 + 2 Y2 <= 5
2Y1 Y2 <= 12
Y1 + 3 Y2 <= 4
Y1 <= 0
Y2 irrestricta
La solucin nos permite obtener directamente la solucin ptima primal. Esto es importante porque
puede ser ms provechoso en trminos de clculo, resolver el dual en vez del dual; pues debe
considerarse que la iteracin del simplex depende ms del nmero del nmero de restricciones que el de
variables. Entonces si el dual tienes el menor nmero de restricciones que el dual, es ms eficiente
resolver el dual y luego de ello deducir la tabla optima del primal
Del ejercicio presentado, los tableros primal dual siguientes
Dado
Max Z= 5x1 + 12 x2 + 4x3 + x4 tres restricciones
Sa x1 + 2x2 + x3 <= 10 Y1
2x1 x2 +3x3 = 8 Y2
Xj >=0
Estandarizando el primal
Max Z= 5X1 + 12 X2 + 4X3 + 0 X4 MR
M muy pequeo
Sa X1 + 2x2 + X3 + X4 = 10 (no negativos) x4 variable de holgura

2x1 X2 +3x3 + R = 8 R variable artificial
X1,X2,X3,X4,R >=0
Por lo tanto el dual ser

Min W = 10 Y1 + 8 Y2
Sa Y1 + 2 Y2 >= 5
2 Y1 Y2 >= 12
Y1 + 3 Y2 >= 4
Y1 >= 0
Y2 >= -M
Nota: Para resolver el dual, siendo Y2 irrestricta en signo entonces hacemos Y2 = Y2 Y2 tal que Y2 =
Y2 Y2
Estandarizando el Dual, tenemos
Y2 = Y2 Y2 / Y2 = Y2 Y2
Min W =
Sa
Y1 + 2 Y2 2Y2 y3 + R1 = 5
2 Y1 Y2 + y2 y4 + R2 = 12
Y1 + 3 Y2 3Y2 Y5 + R3 = 4
Y1, y2, y2, y3, y4, y5, R1, R2, R3 >= 0
Tabla simplex optima del primal (MAX)

X1
0
0
1
Z
X2
X1
X2
0
1
0
X3
3/5
-0.2
7/5
X4
29/5
2/5
1/5
R
-2/5 + m
- 1/5
2/5
Y5
R1
26/5-M
7/5
-2/5
1/5
s optima
54 4/5
12/5
26/5
Tabla simplex del dual (MIN)

Y1
W
Y5
Y2''
Y1
Y2'
0
0
0
1
Y2''
0
0
-1
0
Y3
Y4
0
-26/5
-12/5
0 -7/5
1/5
1 2/5
-1/5
0 -1/5
-2/5
0
1
0
0
R2
R3
12/5-M -M
-1/5
1/5
2/5
Solucin
54 4/5
-1 3/5
0 2/5
0 29/5
Y1 = 29/5 variables bsicas

Y2= 2/5
Y5 = 3/5
W = 54 4/5
Adems y2 = 0 R1= 0 variables no bsicas
Y3 = 0 R2 = 0
Y4= 0 R3 = 0
MARTES 28 DE OCTUBRE 2014.

INTERPRETACION ECONOMICA DE LA DUALIDAD.
1.-Valor de la funcin objetivo en la primal es igual al valor de la funcin objetivo en la dual.
2.-El coeficiente de la ecuacin de la variable xj es igual a: Valor de primer miembro de la
restriccin dual correspondiente menos el valor del segundo miembro de la restriccin dual
correspondiente.
De esto se deriva lo siguiente:
a.-Las variables duales yj representan el precio sombra del recurso correspondiente esto es el
valor unitario del recurso y. Se debe recordad que este ndice nos indica la prioridad del recurso
a ser incrementado para aumentar el valor de la funcin objetivo.
Precio sombra: Valor del recurso en relacin a la funcin objetivo.
R3 es 7$/pie3 de madera Si se aumenta la madera en 1pie3 , las utilidades aumentan en 7$.
R3 es 1.5$/galones por pintura-> Si se aumenta la pintura en 1galon , las utilidades aumentan en
1.5$.
La maximizacin parte de un valor menor y busca un valor superior. Mientras que la
minimizacin parte de un valor superior en bsqueda de un valor menor.
Por tanto en la iteracin antes del ptimos se tiene que z <w, es decir buscamos que las
utilidades aumenten con el nmero de productos o disminuyan en el uso de recursos y solo se
alcanza la optimizad cuando la ganancia es igual al valor de los recursos.
Z: utilidad
W: valor de los recursos.
b.- Las restricciones duales nos indican la condicin de optimidad de modo que si la diferencia
entre el costo aplicable y la ganancia por unidad es menor que cero la actividad del recurso
debe incrementarse.
c.-La dualidad en general . Todo modelo de programacin lineal un sistema de entrada y salida
donde la entrada son los recursos limitados y la salida es la contribucin de una actividad a la
funcin objetivo, de manera que el modelo expresa la conversin de recursos limitados a
actividades.
Este modelo en la maximizacin se puede mejorar mediante 3 acciones:
1.-incrementando la contribucin de la actividad a la funcin objetivo(aumentando cj)
2.-incrementando la disponibilidad de los recursos limitados (aumentando Bj)
3.- disminuyendo el consumo de los recursos limitados de parte de las
actividades.(disminuyendo Aij)
LINDO
Su manejo es simple es un software libre esta simplicidad pone de relieve la importancia del
diseo del modelo para que le programa lineal sea correcto. Una vez aplicado interesa sobre
todo la interpretacin de los resultados tanto de la optimizacin como del anlisis de
sensibilidad.
Problema
Se deben mesclar minerales procedentes de 4 minas diferentes para fabricar un determinado
dispositivo que tiene determinadas especificaciones tcnicas. La mezcla debe contener 3
elementos bsicos A B C
Cada tonelada debe contener por lo menos 5 libras de A, 100 libras de B y al menos 30 libras de
C.
Los minerales procedentes de las 4 minas contienen estos elementos bsicos pero en diferentes
proporciones.
El objetivo de ingeniero responsable de la produccin es encontrar una mezcla de costo mnimo.
Ver diagrama
Min 800x1 + 400x2 + 600x3 + 500x4
subject to
10x1 + 3x2 + 8x3 + 2x4 >= 5
90x1 + 150x2 + 75x3 + 175x4 >= 100
45x1 + 25x2 + 20x3 + 37x4 >= 30
end
INTERPRETACION DE RESULTADOS
OBJECTIVE FUNCTION VALUE .- es el valor optimo del proceso
VALUE.- REPRESENTA EL VALOR DE LA VARIABLE DE DECISION EN LA SOLUCION OPTIMA.
REDUCED COST.- ES LA CANTIDAD EN QUE DEBE CAMBIAR EL COEFICIENTE DE LAVARIABLE EN LA
FUNCION OBJETIVO PARA TENER UN VALOR PTIMO POSITIVO.
POR TANTO TODA VARIABLE BASICA TIENE UN COSTO REDUCIDO IGUAL A CERO Y SOLO LAS
VARIABLES NO BASICAS TIENEN UN VALOR POSITIVO. ESTOS VALORES CORRESPONDEN A LA FILA Z
DEL TABLERO OPTIMO.
SLACK OR SURPLUS (OLGURA O EXCESO).- PARA CADA RESTICCION DADO EL VALOR DE LA VARIBLE
OLGURA O EXCESO.
DUAL PRICE.- ES EL INDICE DE MEJORA EN EL VALOR OPTIMO DE LA FUNCION OBJETIVO CUANDO LA

DISPONIBILIDAD AUMENTA EN UNA UNIDAD(SI ES MINIMIZACION SI DISMINUYE).
RANGE IN WHICH THE BASIS IS UNCHANGED
Max 100x1 + 120x2

subject to
4x1 + 8x2 <= 480
5x1 + 6x2 <= 600
12x1 + 8x2 <= 540
End
LP OPTIMUM FOUND AT STEP
OBJECTIVE FUNCTION VALUE
1)
7500.000
VARIABLE
VALUE
REDUCED COST
X1
7.500000
0.000000
X2
56.250000
0.000000
ROW SLACK OR SURPLUS

2)
0.000000
3)
225.000000
4)
0.000000
DUAL PRICES
10.000000
0.000000
5.000000
NO. ITERATIONS=
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES

VARIABLE
CURRENT
COEF
ALLOWABLE
INCREASE
ALLOWABLE
DECREASE
X1
100.000000
80.000000
40.000000
X2
120.000000
80.000000
53.333332
RIGHTHAND SIDE RANGES

ROW
CURRENT
RHS
ALLOWABLE
INCREASE
ALLOWABLE
DECREASE
480.000000
60.000000
600.000000
INFINITY
540.000000
900.000000
300.000000
225.000000
60.000000
SENSIBILIDAD DE LOS COEFICIENTES OBJETIVOS (Cj)

En la solucin grfica se puede observar que los coeficientes objetivos Cj determinan la pendiente de
la FO, pendiente que a su vez define la ubicacin del punto ptimo.

Por tanto, una variacin en estos coeficientes estn limitados dentro de rangos que permitan o
no el cambio de la solucin ptima.
As, el anlisis de sensibilidad de estos coeficientes objetivos (econmicos) responde a la
pregunta de qu tanto pueden variarse sus valores antes que tenga lugar el desplazamiento
hacia una nueva solucin ptima. Es decir, nos interesa encontrar los rangos de variacin de los
costos unitarios, beneficios unitarios, tiempos unitarios, etc., para seguir ptimos.
Este rango se expresa en el costo reducido que aparece en el tablero de sensibilidad del
software LINDO.
Por otra parte, si nos referimos al tablero ptimo de la solucin manual del simplex observamos
que:
a) Sensibilidad de coeficientes econmicos(objetivos) de variables no bsicas
El valor (Zj - Cj) indica el aumento que necesitaramos en el coeficiente de la variable Xj no bsica para
que esta variable ingrese a la solucin ptima y, por tanto, el (Zj - Cj) se convierta en 0.
Observacin: Todo lo anterior es en relacin a la maximizacin; y siempre en este caso una disminucin
de ese coeficiente solo alejara a la variable de la solucin ptima.
b) Sensibilidad de coeficientes econmicos(objetivos) de variables bsicas

Con los mismos criterios anteriores aplicados correspondientemente a los valores de la solucin ptima,
el rango de variacin posible de estos coeficientes tienen valores cerrados distintos al infinito, es decir,
con rango superior y rango inferior definidos; y siempre tiene que con la capacidad de variacin de la
pendiente de la funcin objetivo.
http://pirhua.udep.edu.pe/bitstream/handle/123456789/1328/ECO_033.pdf?sequence=1
https://joseordinolaboyer.files.wordpress.com/2012/04/eva-valladares_rev.pdf
http://old.cies.org.pe/files/economia-sociedad/maldonado-rios-desigualdad-oportunidades.pdf

Problema Dual

Cargado por

Copyright:

Formatos disponibles

Problema Dual

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Problema Dual

Cargado por

Copyright:

Formatos disponibles

PROBLEMA DUAL

Sa X1 + 2x2 + X3 + X4 = 10 (no negativos) x4 variable de holgura

Por lo tanto el dual ser

Tabla simplex optima del primal (MAX)

Tabla simplex del dual (MIN)

Y1 = 29/5 variables bsicas

MARTES 28 DE OCTUBRE 2014.

DUAL PRICE.- ES EL INDICE DE MEJORA EN EL VALOR OPTIMO DE LA FUNCION OBJETIVO CUANDO LA

Max 100x1 + 120x2

LP OPTIMUM FOUND AT STEP

OBJECTIVE FUNCTION VALUE

ROW SLACK OR SURPLUS

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

RIGHTHAND SIDE RANGES

SENSIBILIDAD DE LOS COEFICIENTES OBJETIVOS (Cj)

la FO, pendiente que a su vez define la ubicacin del punto ptimo.

b) Sensibilidad de coeficientes econmicos(objetivos) de variables bsicas

También podría gustarte