31

12.1. EL MODELO DUAL A todo programa lineal, llamado problema primal, le corresponde otro que se denomina problema dual. Las relaciones existentes entre ambos problemas son las siguientes:

El dual tiene tantas variables como restricciones existen en el primal.

El dual tiene tantas restricciones como variables tiene el primal.

Los coeficientes de la funcin objetivo del primal son los trminos independientes de las restricciones del dual.

Los trminos independientes de las restricciones del primal son los

coeficientes en la funcin objetivo del dual.

La matriz de coeficientes de las restricciones del dual es igual a la traspuesta de la del primal.

Se pueden distinguir dos tipos de problemas duales:

1. Duales simtricos: para primales que incluyan restricciones de desigualdad.

2. Duales asimtricos: para primales en forma estndar, es decir, con

restricciones de igualdad. Otro tipo de relaciones entre los problemas primal y dual son las siguientes:

32

Para duales simtricos el sentido de desigualdad de las restricciones del dual es inverso al de las del primal; mientras que para asimtricos, las restricciones del dual son de sentido menor o igual en caso de que el problema primal sea de minimizacin, y de mayor o igual en caso de maximizacin. Adems, las variables del dual, variables duales, no estn sujetas a la condicin de no negatividad.

El problema dual de uno de minimizacin es de maximizacin y

viceversa.

El dual del programa dual es el primal.

Primal: max ( ) nn xcxcXf ++= 11 s.a.: 11111 bxaxa nn ++ mnmnm bxaxa ++11 nixi ,,1,0 =

Dual: min ( ) mm ybybYg ++= 11 s.a.: 11111 cyaya mm ++

nmmnn cyaya ++11 miyi ,,1,0 =

Se pueden resumir primal y dual en un cuadro como el que sigue, donde el primal se lee verticalmente y el dual de forma horizontal:

33

PROGRAMAS PRIMAL (MAX.)

DUAL (MIN.)

mnmm

n

aaa

aaa

21

11211

0

01

nx

x

mb

b

1

000 21 myyy variables relacin nccc 21 constantes

1. Duales asimtricos: a) Primal: max ( ) nn xcxcXf ++= 11 s.a.: 11111 bxaxa nn =++ mnmnm bxaxa =++ 11 nixi ,,1,0 =

Dual: min ( ) mm ybybYg ++= 11 s.a.: 11111 cyaya mm ++

nmmnn cyaya ++11 miyi ,,1, = , no restringidas en signo

b) Primal: min ( ) nn xcxcXf ++= 11 s.a.: 11111 bxaxa nn =++ mnmnm bxaxa =++ 11 nixi ,,1,0 =

Dual: max ( ) mm ybybYg ++= 11 s.a.: 11111 cyaya mm ++

nmmnn cyaya ++ 11 miyi ,,1, = , no restringidas en signo

34

La tabla anterior queda ahora de la siguiente forma:

PROGRAMAS PRIMAL MAX. (MIN.)

DUAL MIN. (MAX.)

mnmm

n

aaa

aaa

21

11211

0

01

nx

x

=

=

mb

b

1

myyy 21 variables ( ) ( ) ( ) relacin nccc 21 constantes

Nota: Sin distinguir en el caso de duales simtricos o asimtricos, podemos formular una tabla general, que rene las relaciones entre el problema primal y dual, sea cual sea su formulacin:

Problema de minimizacin

Problema de maximizacin

VARIABLES asrestringid no

00

=

RESTRICCIONES

RESTRICCIONES =

asrestringid no

00

VARIABLES

La ventaja de esta tabla es que se puede leer de derecha a izquierda o viceversa, segn el problema primal sea de maximizacin o minimizacin, respectivamente. Adems, en el problema primal pueden darse diferentes combinaciones en cuanto al sentido de sus desigualdades o al signo de sus variables.

35

Ejemplos: 1. Primal: max 212 xx + s.a.: 105 21 + xx 63 21 + xx 822 21 + xx 0, 21 xx

Como el primal es de maximizacin, el dual ser de minimizacin, por lo que leemos la ltima tabla de derecha a izquierda. Esto nos dice que por ser todas las restricciones de menor o igual, las variables duales sern de signo no negativo; adems por ser las variables primales no negativas, todas las restricciones duales sern de mayor o igual. El problema dual quedar por lo tanto como: Dual min 321 8610 yyy ++ s.a.: 22 321 ++ yyy 1235 321 ++ yyy 0,, 321 yyy

2. Primal min 321 25 xxx ++ s.a.: 2032 321 ++ xxx 30586 321 ++ xxx 4037 321 ++ xxx 5042 321 ++ xxx 0,, 321 xxx

En este caso, leemos la tabla de izquierda a derecha, resultando el dual: Dual max 4321 50403020 yyyy +++ s.a.: 5762 4321 +++ yyyy 2283 4321 +++ yyyy 1435 4321 +++ yyyy 0,,, 4321 yyyy

36

12.2. RELACIONES PRIMAL-DUAL Con la solucin del primal, se obtiene con el Simplex implcitamente la del dual. Vemoslo: Sea el primal en forma estndar: max Z = CX s.a.: AX = b

0X Escribimos A = (B/N), con B la submatriz formada por las columnas correspondientes a las variables bsicas, y N lo mismo para las no bsicas o libres. Entonces: max NNBB XCXCZ += s.a.: bNXBX NB =+ 0, NB XX La solucin de este problema consiste en hacer que el vector no bsico NX sea cero,

y resolver el vector bsico en trminos de la base B, es decir:

bBXbBXbNXBX BBNB1

===+

y la funcin objetivo ser:

bBCXCXCXCZ BBBNNBB1

==+=

Ahora bien, la funcin objetivo dual es ( ) bYYbYg TT == , y en el ptimo el valor de la funcin objetivo primal coincide con el valor ptimo de la funcin objetivo dual, esto es, ( ) ( )** YgXZ = . Por lo tanto:

( ) ( ) ( ) ( ) ( ) ( )TBTB YBCbYbBCYgXZ *1***1**** === En los casos particulares que estudiaremos, este valor no hace falta calcularlo explcitamente si hemos resuelto el primal aplicando el algoritmo del Simplex, puesto que en la ltima tabla:

Solucin ptima primal

Variables originales Variables de holgura

Variables bsicas

BX

Valor de las variables bsicas

bBX B

1=

AB 1 1B

ABCC B1

1 BCB

Ejemplo: max 21 34 xx + max 21 34 xx + s.a.: 1832 21 + xx s.a.: 1832 321 =++

Hxxx

1024 21 + xx 1024 421 =++Hxxx

0, 21 xx 0,,, 4321 HH xxxx

Introduciendo las variables de holgura. La ltima tabla es:

1x 2x Hx3

Hx4 Hx3 3 -4 0 1 -3/2

2x 5 2 1 0 1/2

-2 0 0 -3/2

Solucin ptima dual:

=

23

,0*Y

Soluci ( )5,0* =X Funcin

Solucin ptima dual opuesta en signo n ptima primal:

objetivo primal y dual ptimas: ( )* =Xf

37

( ) 15* =Yg