DUALIDAD.


Cuando tenemos un PL asociado con otro PL esto se llama obtener el dual de un problema. Nuestro primer PL se conoce como primal. Si el primal es un problema de maximizar el dual será uno de minimizacion y viceversa. Para nuestra conveniencia las variable para maximizar son z, x1, x2, ... , xn, y para minimizar las variables son w, y1, y2, ..., ym.
Para obtener el dual de un problema de max, se requiere que todas las variables sean no negativas y que todas las restricciones sean de <= (problema de max normal).

Max z = c1x1 + c2x2 + ...+ cmxm
s.a. a11x1 + a21x2 + ... + am1xm =< b1
a12x1 + a22x2 + ... + am2xm =< b2
. . .
. . .
. . .
a1nx1 + a2nx2 + ... + amnxn =< bn
xi =< 0 ( i = 1,2,...,m)

El dual de un problema de max normal como el anterior se define como:

Min w = b1y1 + b2y2 + ...+ bmym
s.a. a11y1 + a21y2 + ... + am1ym => c1
a12y1 + a22y2 + ... + am2ym => c2
. . .
. . .
. . .
a1ny1 + a2ny2 + ... + amnyn => cn
yi => 0 ( i = 1,2,...,m)

Esto es cambiar de max a min y cambiar todas las X por Y y la Z por W.

OBTENER EL DUAL DE UN PROBLEMA MAX O MIN NORMAL.

Si el primal es un problema de max normal se podrá encontrar utilizando la tabla horizontalmente; el dual se obtendrá utilizando la tabla verticalmente.
Si el primal es un problema de min normal, se podrá obtener utilizando la tabla verticalmente; el dual se obtendrá utilizando la misma tabla horizontalmente.


Min w = 50y1 + 20y2 + 30y3 + 80y4
s.a. 400y1 + 200y2 + 150y3 + 500y4 => 500
3y1 + 2y2 => 6
2y1 + 2y2 + 4y3 + 4y4 => 10
2y1 + 4y2 + y3 + 5y4 => 8
yi => 0

omo el primal es un problema de min normal, podemos encontrarlo verticalmente en la tabla de abajo, y su dual horizontalmente en la misma tabla.
Max z = 500x1 + 6x2 + 10x3 + 8x4
s.a. 400x1 + 3x2 + 2x3 + 2x4 =< 50
200x1 + 2x2 + 2x3 + 4x4 =< 20
150x1 + 4x3 + x4 =< 30
500x1 + 4x3 + 5x4 =< 80
xi => 0

min w (x1 => 0) (x2 => 0) (x3 => 0) (x4 => 0)
x1 x2 x3 x4
(y1 => 0) y1 400 3 2 2 <=50
(y2 => 0) y2 200 2 2 4 <=20
(y3 => 0) y3 150 0 4 1 <=30
(y4 => 0) y4 500 0 4 5 <=80
>=500 >=6 >=10 >=8


OBTENER EL DUAL DE UN PROBLEMA NO NORMAL.


Un problema no normal es aquel que tiene dos tipos de restricciones ( => y =<), y/o una igualdad, y/o una variable sin restricción de signo por ejemplo:


Max = 2x1 + x2
s.a. x1 + x2 = 2
2x1 - x2 => 3
x1 - x2 =< 1
x1 => 0, x2 srs


PASOS PARA CONVERTIR UN PROBLEMA DE MAX NO NORMAL EN UN NORMAL:

1. Multiplique cada restricción => por 1. Esto convertirá cada restricción => en una restricción =<. Por ejemplo: 2x1 + x2=< -3
2. Reemplace cada restricción en forma de igualdad por dos restricciones en forma de desigualdad. Después convierta la restricción => en una restricción =<.
X1 + x2 => 2 x1 + x2 =< 2
-X1 - x2 =< -2 -x1 - x2 =< -2

3. Cambie cada variable xi srs, por xi = x´i &#8211; x´´ i, en donde x´i => 0 y x´´ i, => 0.
x &#8217;2 &#8211; x´´2

Entonces nuestro PL se convierte en :

Max = 2x1 + x´2 &#8211; x´´2
s.a. x1 + x´2 &#8211; x´´2 =< 2
-x1 &#8211; x´2 &#8211; x´´2 =< -2
-2x1 + x´2 &#8211; x´´2 =< -3
x1 &#8211; x´2 &#8211; x´´2 =< 1
x1, x´2,x´´2 => 0

PASOS PARA CONVERTIR UN PROBLEMA DE MIN NO NORMAL EN UN NORMAL:

1. Convertir cada restricción =< en una restricción => multiplicando cada restricción =< por &#8211;1.
2. Reemplace cada restricción en forma de igualdad por una restricción =< y una restricción =>. Luego transforme la restricción =< en una restricción =>.
3. Cambie cada variable yi srs, por yi = y´i &#8211; y´´i, donde y´i, y´´i => 0.


OBTENER EL DUAL DE UN PROBLEMA MAX NO NORMAL:

Una vez que llenamos la tabla de tal manera que el primal se pueda encontrar horizontalmente, tenemos que realizar algunos cambios para poder obtener el dual verticalmente:
a) Si la i-ésima restricción del primal es una restricción =>, la variable correspondiente del dual yi tendrá que satisfacer yi=< 0.
b) Si la i-ésima restricción del primal es una restricción en forma de igualdad, la variable dual yi ahora será sin restricción de signo.
c) Si la i-ésima variable del primal es srs, la i-ésima restricción del dual será una restricción en forma de igualdad.

min w (x1 => 0) x2 srs*
x1 x2
y1 1 1 2*
y2 2 -1 >=3*
(y3 => 0) y3 1 -1 <=1
>=2 1

En la tabla anterior se indica con un asterisco los lugares donde hay que aplicar las reglas para determinar parte del dual.


min w (x1 => 0) x2 srs
x1 x2
y1 srs y1 1 1 2
(y2 =< 0) y2 2 -1 >=3
(y3 => 0) y3 1 -1 <=1
>=2 1

El dual queda asi:
Min z = 2y1 + 3y2
s.a. y1 + 2y2 + y3 => 2
y1 &#8211; y2 - y3 = 1
y1 srs, y2 =< 0, y3 => 0

OBTENER EL DUAL DE UN PROBLEMA MIN NO NORMAL:

Una vez que escribimos la tabla de tal forma que el primal se pueda encontrar verticalmente, ahora se obtendrá el dual horizontalmente y se tendrán que hacer algunos cambios:
a) si la i-ésima restricción del primal es una restricción =<, la variable dual correspondiente xi tendrá que satisfacer xi =< o.
b) Si la i-ésima restricción del primal es una restricción en forma de igualdad, la variable dual correspondiente xi será srs
c) Si la i-ésima variable del primal yi, es srs, la i-ésima restricción del dual será una restricción en forma de igualdad.