Programacin Lineal para la Ingeniera Tcnica
Volver al bloque 3
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:
77
Programacin Lineal para la Ingeniera Tcnica
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.
Segn estas afirmaciones, el problema dual queda unvocamente determinado por
su primal. Si x1 , , xn son las variables primales, y1 , , ym las correspondientes
variables duales, el planteamiento del problema dual es:
1. Duales simtricos:
Primal: max f X c1 x1 cn xn
s.a.: a11x1 a1n xn b1
am1 x1 amn xn bm
xi 0, i 1, , n
Dual: min gY b1 y1 bm ym
s.a.: a11 y1 am1 ym c1
a1n y1 amn ym cn
yi 0, i 1, , m
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:
78
Programacin Lineal para la Ingeniera Tcnica
PROGRAMAS PRIMAL (MAX.)
a11 a12 a1n x1 0 b1
DUAL (MIN.)
am1 am 2 amn xn 0 bm
y1 0 y2 0 ym 0 variables
relacin
c1 c2 cn constantes
2. Duales asimtricos:
a) Primal: max f X c1 x1 cn xn
s.a.: a11 x1 a1n xn b1
am1 x1 amn xn bm
xi 0, i 1, , n
Dual: min gY b1 y1 bm ym
s.a.: a11 y1 am1 ym c1
a1n y1 amn ym cn
yi , i 1, , m , no restringidas en signo
b) Primal: min f X c1 x1 cn xn
s.a.: a11 x1 a1n xn b1
am1 x1 amn xn bm
xi 0, i 1, , n
Dual: max gY b1 y1 bm ym
s.a.: a11 y1 am1 ym c1
a1n y1 amn ym cn
yi , i 1, , m , no restringidas en signo
79
Programacin Lineal para la Ingeniera Tcnica
La tabla anterior queda ahora de la siguiente forma:
PROGRAMAS PRIMAL MAX. (MIN.)
a11 a12 a1n x1 0 b1
DUAL MIN.
(MAX.)
am1 am 2 amn xn 0 bm
y1 y2 ym variables
relacin
c1 c2 cn 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 Problema de
minimizacin maximizacin
0
VARIABLES 0 RESTRICCIONES
no restringidas
0
RESTRICCIONES 0 VARIABLES
no restringidas
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.
80
Programacin Lineal para la Ingeniera Tcnica
Ejemplos:
Volver a
1. Primal: max 2x1 x2
problema
primal s.a.: x1 5x2 10
x1 3x2 6
2x1 2x2 8
x1 , x2 0
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:
Volver a Dual min 10y1 6 y2 8 y3
problema
dual s.a.: y1 y2 2 y3 2
5y1 3y2 2y3 1
y1 , y2 , y3 0
2. Primal min 5x1 2x2 x3
s.a.: 2x1 3x2 x3 20
6x1 8x2 5x3 30
7x1 x2 3x3 40
x1 2x2 4x3 50
x1 , x2 , x3 0
En este caso, leemos la tabla de izquierda a derecha, resultando el dual:
Dual max 20 y1 30 y2 40 y3 50y4
s.a.: 2 y1 6 y2 7 y3 y4 5
3y1 8y2 y3 2 y4 2
y1 5y2 3y3 4 y4 1
y1 , y2 , y3 , y4 0
81
Programacin Lineal para la Ingeniera Tcnica
3. Primal min x1 3x2 2x3
s.a.: 4x1 8x2 6x3 25
7x1 5x2 9x3 30
x1 , x2 , x3 0
Ahora, aunque como en el ejemplo anterior hay que leer la tabla de
izquierda a derecha, la formacin del dual ser ligeramente diferente a la de
dicho ejemplo.
Dual max 25 y1 30 y2
s.a.: 4 y1 7 y2 1
8y1 5y2 3
6 y1 9 y2 2
y1 , y2 no restringidas en signo
4. Primal max 3x1 x2
s.a.: x1 x2 7
2x1 3x2 8
x1 , x2 0
Al igual que el ejemplo 1, leemos la tabla de derecha a izquierda, resultando:
Dual min 7 y1 8 y2
s.a.: y1 2 y2 3
y1 3y2 1
y1 , y2 no restringidas en signo
Nota:
La forma del dual asimtrico (ejemplos 3 y 4) est determinada exclusivamente por
la forma del dual simtrico. Si pasamos a forma estndar el problema con
restricciones de desigualdad y calculamos el dual, que sera dual asimtrico, el
problema que se obtiene es el mismo que le correspondera al primal como dual
simtrico. Por ejemplo:
82
Programacin Lineal para la Ingeniera Tcnica
max f X c1 x1 cn xn
s.a.: a11x1 a1n xn b1
am1 x1 amn xn bm
xi 0, i 1, , n
Si pasamos a forma estndar:
max f X c1x1 cn xn 0xnH1 0xnH m
s.a.: a11x1 a1n xn xnH 1 b1
am1 x1 amn xn xnH m bm
xi 0, i 1, , n , xnH j 0, j 1, , m
El correspondiente dual asimtrico de este ltimo problema primal es:
min gY b1 y1 bm ym
s.a.: a11 y1 am1 ym c1
a1n y1 amn ym cn
y1 0
ym 0
Es el mismo que el dual simtrico que le correspondera al problema sin
transformar en su formulacin estndar.
Una vez visto que los duales simtricos pueden convertirse en asimtricos
utilizando variables de holgura, vamos a enunciar un teorema de dualidad vlido
para ambos.
83
Programacin Lineal para la Ingeniera Tcnica
Teorema:
Sea P un problema de Programacin Lineal cuya regin de factibilidad es F, y sea
D su problema dual de regin de factibilidad G. Entonces:
i) Si X F , Y G , se cumple que f X g Y .
ii) Si para algn X F y algn Y G se verifica que f X g Y ,
entonces X es solucin ptima de P, Y es solucin ptima de D.
iii) Si uno de los problemas P D tienen una solucin ptima X * Y * , el
otro tambin la tiene, verificndose adems que f X * gY * .
iv) Si f est acotada superiormente en F , g est acotada
inferiormente en G , entonces ambos problemas P y D tienen
solucin ptima.
Consecuencias del teorema:
1. Si el primal tiene solucin finita, entonces el dual tambin la tiene y ambas
coinciden.
2. Si el primal tiene solucin no acotada, el dual no tiene solucin.
3. Si el primal no tiene solucin, entonces el dual no tiene solucin tiene
solucin no acotada.
El dual del dual:
Volver al
Dual del Dual Consideremos ahora como primal al dual, cul es su dual?.
min gY b1 y1 bm ym
s.a.: a11 y1 am1 ym c1
a1n y1 amn ym cn
yi 0, i 1, , m
84
Programacin Lineal para la Ingeniera Tcnica
Introducimos variables de holgura:
min gY b1 y1 bm ym 0 ym 1 H 0 ymH n
s.a.: a11 y1 am1 ym ym 1H c1
H
a1n y1 amn ym ym n cn
yi 0, i 1, , m , ymH j 0, j 1, , n
Su dual sera:
max f X c1 x1 cn xn
s.a.: a11x1 a1n xn b1
am1 x1 amn xn bm
x1 0
xn 0
Las ltimas n restricciones son las de no negatividad, y el problema que se obtiene
es el primal. Luego el dual del dual es el primal.
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
X 0
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:
85
Programacin Lineal para la Ingeniera Tcnica
max Z CB X B CN X N
s.a.: BX B NX N b
XB , XN 0
La solucin de este problema consiste en hacer que el vector no bsico X N sea cero,
y resolver el vector bsico en trminos de la base B, es decir:
BX B NXN b BX B b XB B1b
y la funcin objetivo ser:
Z CB X B CN X N CB X B CB B1b
Ahora bien, la funcin objetivo dual es gY bTY Y T b , y en el ptimo el valor de
la funcin objetivo primal coincide con el valor ptimo de la funcin objetivo dual,
esto es, Z X * gY * . Por lo tanto:
ZX * g Y * CB* B* b Y * b CB* B* Y *
1 T 1 T
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:
Variables originales Variables de holgura
Valor de las
Volver a Variables bsicas variables
Primal-Dual
bsicas B1 A B1
XB
XB B1b
C CB B1 A CB B1
Solucin ptima primal
Solucin ptima dual
opuesta en signo
86
Programacin Lineal para la Ingeniera Tcnica
Ejemplo:
max 4x1 3x2 max 4x1 3x2
Paso a
forma s.a.: 2x1 3x2 18 s.a.: 2x1 3x2 x3H 18
estndar 4x1 2x2 10 4x1 2x2 x4H 10
x1 , x2 0 x1 , x2 , x3H , x4H 0
Introduciendo las variables de holgura. La ltima tabla es:
x1 x2 x3H x4H
x3H 3 -4 0 1 -3/2
x2 5 2 1 0 1/2
-2 0 0 -3/2
3
Solucin ptima dual: Y* 0,
2
Soluciones
ptimas Solucin ptima primal: X * 0,5
Funcin objetivo primal y dual ptimas: f X * g Y * 15
El dual sera:
min 18y1 10 y2 max 18 y1 10 y2 My5A My6A
s.a.: 2 y1 4y2 4 s.a.: 2 y1 4y2 y3H y5A 4
3y1 2 y2 3 3y1 2y2 y4H y6A 3
y1 , y2 0 y1 , y2 , y3H , y4H , y5A , y6A 0
Se puede comprobar con el Simplex que da la misma solucin, pero el proceso es
ms largo por la introduccin de variables de holgura y artificiales, de ah el inters
Sobre el de la relacin entre dual y primal (entre otras razones).
Dual
Interesar pasar al dual cuando su resolucin sea ms fcil que la del primal. As,
podemos resolver el dual por el Simplex y deducir, sin ningn clculo
87
Programacin Lineal para la Ingeniera Tcnica
suplementario, la solucin ptima del primal. Este caso se presentar cuando el
primal incluya restricciones de mayor o igual para las cuales es preciso introducir
variables de holgura y artificiales.
Ejemplo:
min 5x1 6x2 max 5x1 6x2 Mx5A Mx6A
Paso a s.a.: 5x1 2x2 20 s.a.: 5x1 2x2 x3H x5A 20
forma
estndar 3x1 8x2 24 3x1 8x2 x4H x6A 24
x1 , x2 0 x1 , x2 , x3H , x4H , x5A , x6A 0
Si calculamos su dual:
max 20 y1 24 y2 max 20 y1 24 y2
Clculo s.a.: 5y1 3 y2 5 s.a.: 5y1 3 y2 y3H 5
del Dual
2 y1 8 y2 6 2 y1 8y2 y4H 6
y1 , y2 0 y1 , y2 , y , y
3
H
4
H
0
Se ve que es ms fcil aplicar el Simplex al estndar del dual que al del primal.
La ltima tabla es:
y1 y2 y3H y4H
y1 11/17 1 0 ----- -----
y2 10/17 0 1 ----- -----
0 0 -56/17 -30/17
Lo que realmente nos interesa es el valor de los costes en la tabla final, por eso
dejamos sin rellenar huecos en esa tabla que no aportan nada a la solucin que
buscamos. As:
Soluciones
11 ,10 56 , 30 460
ptimas Y* , X* , f X * g Y *
17 17 1717 17
88
Programacin Lineal para la Ingeniera Tcnica
12.3. MTODO DUAL DEL SIMPLEX
Supongamos el problema de la dieta (mezcla de alimentos ms barata,
satisfaciendo unos valores nutritivos necesarios):
min c1 x1 cn xn
s.a.: a11x1 a1n xn b1
am1 x1 amn xn bm
xi 0, i 1, , n
Aqu, x j representa la cantidad del alimento j a precio c j y con una composicin
aij de un cierto elemento nutritivo Ni del cual hay un requerimiento de al menos
bi unidades.
Una posible interpretacin del dual sera: supongamos que una empresa se plantea
la posibilidad de fabricar un concentrado de cada uno de los elementos nutritivos
que se requieren para la correcta alimentacin, de modo que propondra que se
ingirieran los concentrados directamente en lugar de los alimentos que contienen
los elementos nutritivos, de modo que se satisfacieran las necesidades
nutricionales igualmente.
El problema que se planteara la compaa consistira en encontrar los precios
unitarios y1 , , ym para cada nutriente de forma que maximizara su beneficio, pero
teniendo en cuenta que al mismo tiempo este procedimiento debera ser
competitivo con el usual en el que se aportan directamente los alimentos. As, se
debe maximizar b1 y1 bm ym .
Esta competitividad significa que la suma de los precios totales de los elementos
nutritivos en las cantidades que intervienen en cada alimento deber ser menor o a
lo sumo igual que el precio o coste de este alimento. As, para el alimento j-simo
de coste c j , deber verificarse a1 j y1 amj ym c j .
89
Programacin Lineal para la Ingeniera Tcnica
Por ltimo, el precio de cada unidad de nutriente yi debe ser positivo. Con todo
esto, planteamos el dual:
max b1 y1 bm ym
s.a.: a11 y1 am1 ym c1
a1n y1 amn ym cn
yi 0, i 1, , m
Podemos deducir fcilmente del estudio desarrollado en los apartados anteriores
una de las aplicaciones inmediatas de la teora de la dualidad: la resolucin de
problemas lineales con ms restricciones que variables. Puesto que parte de la
dificultad y el nmero de iteraciones del Simplex dependen del nmero de
restricciones, resolveremos el primal si m < n, y el dual si m > n.
Otra aplicacin de la dualidad es la resolucin de problemas lineales utilizando
el Algoritmo Dual del Simplex, que consiste bsicamente en aplicar el Simplex al
problema dual, pero efectuando los clculos sobre el primal. Lo explicamos a
continuacin.
Para comenzar con el Simplex, si no es posible obtener una solucin factible, se
aaden tantas variables artificiales como sea necesario. El Mtodo Dual del
Simplex hace innecesario el empleo de dichas variables artificiales, pero necesita
para comenzar a iterar una condicin llamada de factibilidad dual, es decir, que
todos los costes marginales c j sean negativos o nulos (en caso de mximo). Por
tanto, no siempre se podr aplicar.
Volver a
Mtodo Dual Algoritmo.
del Simplex
Paso 1: Partimos de una tabla en la que c j cj z j 0.
Paso 2: Si X B (solucin bsica) es tal que X B 0 , estamos en la solucin ptima.
PARAR.
90
Programacin Lineal para la Ingeniera Tcnica
En otro caso, elegimos para que salga de la base la variable xi , cuya
coordenada X B i es la ms negativa.
Paso 3: Si todos los elementos aij de la fila correspondiente a la variable que sale
de la base son positivos o nulos, entonces el problema no tiene solucin o
tiene solucin ptima no acotada.
Si al menos algn aij 0 , calculamos:
min cj
ck
aij 0
j 1, , n
aij aik
Si corresponde a la columna k-esima, entra en la base xk .
Paso 4: Pivotamos sobre aik , efectuando las operaciones precisas para que la
columna k tenga un 1 en el lugar i-simo y ceros en el resto.
Volver al paso 2.
Ntese que los problemas ideales para resolver mediante este algoritmo son
aquellos de minimizacin que incluyen restricciones del tipo mayor o igual, y
cuyas desigualdades contienen coeficientes positivos. As, el problema de la dieta
es un candidato para aplicarle este procedimiento.
Ejemplo:
min 3x1 4x2 5x3 max 3x1 4x2 5x3
s.a.: x1 2x2 3x3 5 s.a.: x1 2x2 3x3 5
2x1 2x2 x3 6 2x1 2x2 x3 6
x1 , x2 , x3 0 x1 , x2 , x3 0
Introducimos las correspondientes variables de holgura para obtener la
formulacin estndar:
91
Programacin Lineal para la Ingeniera Tcnica
max 3x1 4x2 5x3
s.a.: x1 2x2 3x3 x H 4 5
2x1 2x2 x3 xH 5 6
x1 , x2 , x3 , x H4 , x H5 0
La tabla inicial con la que comenzar a iterar, siguiendo los pasos del Algoritmo
Dual del Simplex, es la siguiente:
x1 x2 x3 x4H x5H
paso 2 x4H -5 -1 -2 -3 1 0
x5H -6 -2 -2 -1 0 1
-3 -4 -5 0 0
paso 3
Puesto que c j 0, j , sale de la base la variable cuya coordenada X B i es la ms
negativa, en este caso x5 6 , y aplicamos el criterio de entrada, calculando:
3 4 5 3
min , ,
2 2 1 2
As pues, entra en la base la variable x1 , siendo el elemento pivote a21 2 .
Con todo esto, la siguiente tabla quedar como sigue:
x1 x2 x3 x4H x5H
x4H -2 0 -1 -5/2 1 -1/2
paso 2 x1 3 1 1 1/2 0 -1/2
0 -1 -7/2 0 -3/2
paso 3
92
Programacin Lineal para la Ingeniera Tcnica
Seguimos teniendo que c j 0, j , y ahora la variable bsica con valor ms
negativo es x4H 2 (la nica), por tanto es la que abandona la base.
Aplicamos el criterio de entrada calculando:
1 7 2 3 2
min , , 1
1 5 2 1 2
que corresponde a la variable x2 , que entra en la base, siendo el elemento pivote el
elemento a12 1.
Con todo esto, la siguiente tabla quedar como sigue:
x1 x2 x3 x4H x5H
x2 2 0 1 5/2 -1 1/2
x1 1 1 0 -2 1 -1
0 0 -1 -1 -1
paso 2
Todas las variables bsicas son positivas, por lo que el algoritmo termina con la
solucin ptima:
x1* 1, x2* 2, x3* 0, Z * 11
Ejemplo:
min Z 2x1 x2 max Z 2x1 x2
H
s.a.: 3x1 x2 3 s.a.: 3x1 x2 x3 3
4x1 3x2 6 4x1 3x2 x4H 6
x1 2x2 3
x1 2x 2 x 5 3
H
x1 , x2 0 3 4 5
x1 , x2 , xH , x H , x H 0
93
Programacin Lineal para la Ingeniera Tcnica
Una vez que hemos cambiando de signo, e introducido las correspondientes
variables de holgura, la primera tabla ser:
x1 x2 x3H x4H x5H
paso 2 x3H -3 -3 -1 1 0 0
H
x 4 -6 -4 -3 0 1 0
H
x 5 -3 -1 -2 0 0 1
-2 -1 0 0 0
paso 3
paso 4
x1 x2 xH 3 xH 4 xH 5
paso 2
x3
H
-1 -5/3 0 1 -1/3 0
x2 2 4/3 1 0 -1/3 0
x5
H
1 5/3 0 0 -2/3 1
-2/3 0 0 -1/3 0
paso 3
paso 4
x1 x2 x3H x4H x5H
x1 3/5 1 0 -3/5 1/5 0
x2 6/5 0 1 4/5 -3/5 0
x5H 0 0 0 1 -1 1
0 0 -2/5 -1/5 0
paso 2
Todas las variables bsicas son positivas, por tanto el algoritmo concluye con la
solucin ptima:
x1* 3 5 , x2* 6 5, Z* 12 5
Ir al bloque 5
94
