PLC5 - Gonzálo de la Vega S

Vista previa del material en texto

95 
5. DUALIDAD 
5.1 EL PROBLEMA DUAL 
El fenómeno de dualidad ocurre frecuentemente en economía e ingeniería. En esencia consiste 
en que, dado un modelo matemático, puede asociarse al mismo más de un problema real. 
Aplicada a programación lineal, la dualidad s ignifica que relacionado con cualquier 
problema de programación lineal, denominado problema original o problema primal, existe 
siempre otro problema lineal, llamado dual, y tal relación proporciona importantes 
interpretaciones económicas y amplía el campo del análisis de sensibilidad. Veamos entonces 
cómo se construye el programa dual. 
DEFINICIÓN DEL PROBLEMA DUAL 
Dado un programa primal en su forma canónica, 
0x
bAx 
s.a
cxz Max



 
el correspondiente programa dual asociado (en su forma canónica) está dado por 
0u
cuA 
s.a
ub wMin
TT
T



 
Por ejemplo, para el problema del taller de alfarería tendremos 
0 x,x
15x
75x5,1x3 
40x2x
a .s
45x20x z Max
21
2
21
21
21





0u ,u ,u
45uu5,1u2 
20u3u
a .s
u1575u40u wMin
321
321
21
321




1u
2u
3u
1x
2x
 
El dual se construye desde el primal (y viceversa) de la forma siguiente: 
 Un problema es de maximización y el otro de minimización. 
 El problema de maximización tiene restricciones de  y el de minimización de . 
 Cada restricción de un problema tiene asociada una variable en el otro problema. 
 Los términos independientes de las restricciones del primal son los coeficientes de la 
función económica del dual. 
 La matriz de los coeficientes tecnológicos en un problema es la traspuesta de dicha 
matriz en el otro problema. 
Capítulo 5 
 
 
96 Norma Torrent 
 En ambos problemas las variables son no negativas. 
Cada uno de estos problemas es el dual del otro, por lo tanto cualquiera de ellos puede ser 
tomado como primal y el otro será su dual (se trata de una correspondencia biunívoca). Se 
demuestra con suma facilidad que el dual del problema dual es el primal. 
5.2 TEOREMA FUNDAMENTAL DE LA DUALIDAD 
Dado un programa lineal en su forma canónica y su correspondiente programa dual asociado, 
0x
bAx 
s.a
cxz Max



0u
cuA 
s.a
ub wMin
TT
T



 
El teorema enuncia que 
Si el programa primal tiene solución óptima finita, los valores de u que minimizan el dual 
son los costos marginales del programa original. Además, el valor óptimo de la función objetivo 
del dual coincide con el valor óptimo de la función objetivo del original ).( ** zw  
Demostración. Dado el problema original, si éste tiene solución finita, obtenemos z* como 
función lineal b. 


















m
1
**
**
b
b
 fz* 
)b(xx
cxz
.
.
 
Por ser x* solución del sistema se verifica que 24 
j
*
nn
*
jj
*
22
*
11
*
nn
*
jj
*
22
*
11
AbxA...)x(A...xAxA
 bxA...xA...xAxA


 )1-5( 
con  > 0. 
Hemos pasado a un nuevo sistema en el que el vector de los términos independientes se ha 
incrementado en Aj. De (5-1) se deduce que una solución para este sistema 
es T*n*j*2*1 )x ..., ε),(x ..., ,x ,(xx  y el valor de la función económica en este punto está dado por 
jj
*
j
*
nn
*
jj
*
22
*
11 c)b(fccxcxc... xc... xcxccx  (5-2) 
Sabemos que el valor óptimo de la función económica del nuevo programa será función de b 
+ Aj y que este valor no puede ser superado por el valor que tome la función objetivo en 
cualquier otro punto. Luego 
)Ab(fcx j (5-3) 
De (5-2) y (5-3) se deduce que 
)Ab(fc)b(f jj  (5-4) 
 
24 En este caso estamos designando con n a la cantidad de actividades o variables concretas (recordemos que en su 
forma estándar designamos con n a la cantidad de variables de decisión más las correspondientes holguras). 
 
Dualidad 
 
 
97 
)εAf(b j es función de m variables (las m componentes del vector jεAb  ). Desarrollando por 
Taylor el segundo miembro de (5-4) obtenemos 
m
mj
1
j1j b
fa ... 
b
fa)b(f)Ab(f





 
ij
m
1i i
j ab
f)b(f)Ab(f 



 (5-5) 
De (5-4) y (5-5) resulta 
ij
m
1i i
j ab
f)b(fc)b(f 



 
ij
m
1i i
jij
m
1i i
j ab
fca
b
fc 






 
Ahora bien, por condición de no negatividad εx *j  , que es una componente de la 
solución, debe ser no negativa. Como 0x *j  
 Si 0,x *j  ε debe ser mayor que cero (como habíamos supuesto) para que resulte 
0εx *j  . 
 Si 0,x *j  ε puede ser mayor o menor que cero siempre que 0εx *j  . 
Resumiendo 
jij
m
1i i
*
j
jij
m
1i i
jij
m
1i i*
j
jij
m
1i i
*
j
ca
b
f0x 
ca
b
f0
ca
b
f0
0x
ca
b
f00x







































 (5-6) 
Por lo tanto siempre se cumple jij
m
1i i
ca
b
f





. Es decir siempre se verifica el siguiente 
sistema 
nmn
m
n2
2
n1
1
22m
m
22
2
12
1
11m
m
21
2
11
1
ca
b
f...a
b
fa
b
f
...............
ca
b
f...a
b
fa
b
f
ca
b
f...a
b
fa
b
f



























 
además 0,
b
f 
i


 por ser f(b) una función no decreciente. 
Capítulo 5 
 
 
98 Norma Torrent 
Observemos que lo que se ha planteado es el conjunto de restricciones de dual, 
0u
cAu 
0u
cuA TTT



 emente,equivalent o 
Este sistema admite al menos una solución: la dada por el vector 
  u ..., ,u ,u
b
f ,... ,
b
f ,
b
fu T*m*2*1
T
m21
* 













 . Estas derivadas son los valores implícitos del 
problema original. 
Hemos demostrado entonces que los precios sombra del original constituyen una solución 
del dual. Debemos demostrar ahora que esta solución es la óptima y que el máximo de la función 
objetivo del original coincide con el mínimo de la función objetivo del dual. 
Por otra parte, dado el problema original, existe un conjunto de soluciones, K, que satisface 
el sistema de restricciones Ax  b, con x ≥ 0. Asociado a este problema existe otro: ATu ≥ cT, con 
u ≥ 0, o bien, uTA ≥ c, con u ≥ 0, que posee un conjunto de soluciones, K’, no vacío, pues como 
se vio admite por lo menos una solución. 
Si a la expresión uTA ≥ c la pos-multiplicamos por x tenemos A)x(ucx T , pero 
bu)Ax(uA)x(ucx TTT  (5-7) 
relación que se satisface x  K y u  K’, en particular para x* y u*. Por lo tanto 
bu)Ax(uA)x(ucx
T
**
T
**
T
**  (5-8) 
pero 
*
nin
m
1i i
*
jij
m
1i i
*
11i
m
1i i
*
T
* x a
b
f...x a
b
f...x a
b
fA)x(u
































 

 
donde *jx puede ser igual a cero, en cuyo caso el sumando se anula, o bien *jx puede ser mayor 
que cero, en cuyo caso jij
m
1i i
ca
b
f





por (5-6). 
En consecuencia 
**
nn
*
jj
*
11
*
T
* cxxc...xc...xcA)x(u  (5-9) 
Además 


























 

*
j
n
1j
mj
*
m
*
j
n
1j
j2
*
2
*
j
n
1j
j1
*
1
*
T
* xau...xauxau)Ax(u 
*
ju (valor implícito del original) puede ser igual a cero , en cuyo caso el sumando se anula, o 
bien *ju puede ser mayor que cero, en cuyo caso en el original hay utilización plena de los 
recursos, por lo tanto i
n
1j
*
jij
*
nin
*
2i2
*
1i1 bxaxa...xaxa  

. Luego 
bubu...bubu)Ax(uT
*
m
*
m2
*
21
*
1
*
T
*  (5-10) 
Dualidad 
 
 
99 
De (5-8), (5-9) y (5-10) se deduce que 
bucx
T
**  (5-11) 
Es decir, el óptimo de la función económica del original coincide con el valor de la función 
económica del dual en u*. Por (5-7) bucx T  x  K y  u  K’, en particular 
K'u 
11)-(5 dey 
K'u 








 bubu
bucx 
 bucx TT*
T
**
T*
 
lo cual significa que valorizando la función económica del dual en cualquiera de los puntos u que 
lo satisfacen, se obtienen valores mayores que en u*. Luego u* es el punto de óptimo del dual. 
Observemos que para un programa de minimización en su forma canónica 
0x
bAx 
s.a
cx wMin



 
partiendo de la correspondiente (5-1), las (5-6) resultarán 
jij
m
1i i
*
j
jij
m
1i i
jij
m
1i i*
j
jij
m
1i i
*
j
ca
b
f0x 
ca
b
f0
ca
b
f0
0x
ca
b
f00x







































 
y, con un razonamiento análogo al anterior, llegaríamos a la equivalente conclusión. 
5.3 EL DUAL DE UN PRIMAL CON RESTRICCIONES DE IGUALDAD 
Sea el siguiente programa lineal. 
0 x,x,x
2x3xx2 
5x2xx
a .s
x4x215x z Max
321
321
321
321




 
Expresando el problema en su forma canónica resulta, 
0 x,x,x
2x3xx2 
23xxx2
5xx2x
a .s
x4x215x z Max
321
321
321
321
321





 
Capítulo 5 
 
 
100 Norma Torrent 
El correspondiente programa dual será entonces 
0u ,u,u
4)uu(3u
12)uu(u2 
5)uu(2u
a .s
)uu(25u wMin
321
321
321
321
321





 
El término 32 uu  se repite en la función objetivo y en las restricciones, por lo tanto 
haciendo 32'2 uuu  el correspondiente problema dual será 
 signoen airrestrict u 0u 
4u3u
12uu2 
5u2u
a .s
u25u wMin
'
21
'
21
'
21
'
21
'
21





 
En forma general cuando el programa primal está en su forma estándar, el programa dual 
asociado está dado por 
0x
bAx 
s.a
cxz Max



arestringid no u 
c u A 
s.a
ub wMin
TT
T


 
Así, frente a un problema con inecuaciones y ecuaciones, el dual se construye directamente 
a partir del primal, teniendo en cuenta que cada restricción de igualdad da lugar a una variable 
irrestricta en signo en el dual. Evidentemente, para una variable no restringida en el original la 
correspondiente restricción en el dual será de igualdad. Este análisis completa lo que ya 
adelantáramos en el apartado 4.7 del capítulo anterior. 
5.4 DISTINTAS ALTERNATIVAS DE CONSTRUCCIÓN DEL DUAL 
Basándonos en la forma canónica de los programas primal y dual podremos estudiar las 
diferentes alternativas que se pueden presentar. La tabla adjunta muestra las reglas para obtener 
el dual de cualquier modelo lineal. 
Maxcx
Ax
x
ubT
uAT
u
irresticta
b
0
 Min
 Tc
0
 Min MinMax Max
b b b b b
0 0 0 0
 Min MinMax Max
Max
 Min
 Tc
irresticta
Tc Tc
 0 0 0 0
 Tc Tc
 
 
Dualidad 
 
 
101 
5.5 LA SOLUCIÓN COMPLETA DEL DUAL EN LA TABLA ÓPTIMA DEL PRIMAL 
Retomemos el Ejemplo 1-1. 
0 x,x
15x
75x5,1x3 
40x2x
a .s
45x20x z Max
21
2
21
21
21





0u ,u ,u
45uu5,1u2 
20u3u
a .s
u1575u40u wMin
321
321
21
321




 
Sabemos que la tabla de óptimo para el primal es 
 20 45 0 0 0 xi/yij 
(yij>0) 
 
 ci Ai A1 A2 A3 A4 A5 xi 
 20 A1 1 0 1 0 –2 10 
 0 A4 0 0 –3 1 9/2 45/2 
 45 A2 0 1 0 0 1 15 
 zj 20 45 20 0 5 z = 875 cj – zj 0 0 –20 0 –5 
por consiguiente, la solución óptima del dual será 
875 w5;u 0;u ;02u **3
*
2
*
1  
Lógicamente reemplazando estos valores en el problema dual en su forma estándar 
obtendremos .y 0u0u *5
*
4  
Similarmente, resolviendo el dual resultará la siguiente tabla de óptimo 
 40 75 15 0 0 xi/yij 
(yij>0) 
 
 ci Ai A1 A2 A3 A4 A5 xi 
 40 A1 1 3 0 –1 0 20 
 15 A3 0 –9/2 1 2 –1 5 
 zj 40 105/2 15 –10 –15 w = 875 cj – zj 0 22,5 0 10 15 
y la solución óptima del primal estará dada por 
875z ;51 x;10x **2
*
1  
luego, despejando, .y ; 0x22,5x0x *5
*
4
*
3  
Notemos que en este caso el dual tiene menos restricciones que su primal. Si tenemos en 
cuenta que el número de iteraciones para alcanzar la solución depende en general del número de 
restricciones, resultará más ventajoso encarar la resolución del dual. 
Si bien el procedimiento antes empleado para el cálculo de los valores de las 
holguras/excesos del problema dual es absolutamente válido, veremos a continuación que estos 
valores también se encuentran en la tabla de óptimo del problema original. 
Cuando a un programa lineal en forma canónica lo llevamos a su forma estándar obtenemos 
0x
bAx
a s.
xc zMax 



 
Capítulo 5 
 
 
102 Norma Torrent 
Ahora la matriz A contiene la submatriz identidad correspondiente a las variables de 
holgura, el vector x incorpora dichas variables y al vector c se le agregan los coeficientes 
económicos de las mismas (valores nulos). Para el problema del Ejemplo 1-1 resulta 
5 ...; 2; 1;j 




0x
15xx
75xx5,1x3
40x2xx
a s.
0x0x0xx54x02zMax 
j
52
421
321
54321
 
Transformando cada una de las restricciones en dos inecuaciones de tipo , el programa 
dual estará dado por 
5 ...; 2; 1;j 







0x
51xx
15xx
75xx5,1x3 
75xx5,1x3
40x2xx
40x2xx
a .s
0x0x0xx54x02zMax 
j
52
52
421
421
321
321
54321
6 ...; 2; 1;i 






0u
0uu
0uu
0uu
45uuu5,11,5uu22u 
20u33uuu
a .s
u51u51u57u57u40u40Min w
i
65
43
21
654321
4321
654321
 
Redesignando con 653432211 uuuuuuuuu  y , tendremos 
5 ...; 2; 1;j 




0x
15xx
75xx5,1x3
40x2xx
a s.
0x0x0xx54x02zMax 
j
52
421
321
54321
0u
0u
0u
45uu5,1u2 
20u3u
a .s
u51u57u04Min w
3
2
1
321
21
321






1u
3u
1x
2x
3x
4x
5x
2u
 
El conjunto de restricciones del dual puede escribirse entonces como TT cuA  y, en su 
forma estándar, TT csu A  donde s es un vector de n componentes (en este caso 
T
521 ) s..., , s,(ss  ) correspondientes a las variables de exceso de cada restricción. 
En el óptimo T**T cs uA  (observemos la validez de (5-6) y de las restantes deducciones 
del apartado 5.2). 
,T**T cs uA  o bien, .
T
*
T
*
T
*
T
* sc Aucs Au  Si en esta última expresión 
discriminamos las componentes básicas y no básicas de A, c y s*, resulta 
    







T
*
N
T
*
BNB
T
*
T
*
T
*
s sccNBu
scA u
 
 
Dualidad 
 
 
103 
O bien, 
 














NNNNN
1
B
T
*
N
T
*
B
T
*
NN
T
*
T
*
BB
T
*
zcczcNBcs
0s, 
scNu
scBu 1
B
T
* Bcuque dado y, 
Luego,   Njjj Ij zcs * . Además teniendo en cuenta que   0, zc BB  y que 
 ,0s
T
*
B  concluimos que: 
  n ..., 2, 1,j  zcs jj*j 
Mediante un desarrollo similar al precedente se deduce que si el problema original es de 
minimización con restricciones del tipo ≥, los valores óptimos de las variables de holgura duales 
estarán dados por: 
  n ..., 2, 1,j  zcs jj*j 
Volviendo a nuestro ejemplo, el último renglón de la tabla de óptimo del original nos indica 
que: 5u 0u 0,u 0,u 0,u *8*7*6*5*4  y2 (hemos redesignado con *8*7*6*5*4 u u ,u ,u ,u y a 
*
5
*
4
*
3
*
2
*
1 s s, s, s,s y , respectivamente). Lógicamente como *8*7*6 u u ,u y son las variables de 
exceso del dual correspondientes a las condiciones de no negatividad, sus valores coincidirán 
con ,y *3*2*1 u u ,u respectivamente. 
Si en cambiohubiésemos resuelto el programa dual, de su tabla de óptimo obtendríamos 
15.xx 10xx 0,x 22,5,x 0,x *2*7*1*6*5*4*3  y 
Resumiendo: dados un programa primal y su correspondiente dual, la tabla de óptimo de 
uno cualquiera de ellos nos revelará la solución óptima del otro. Ejemplificamos esta 
propiedad para los problemas 1-1 y 3-2. 
0 x,x
15x
75x5,1x3 
40x2x
a .s
45x20x z Max
21
2
21
21
21





0u ,u ,u
45uu5,1u2 
20u3u
a .s
u1575u40u wMin
321
321
21
321




1u
2u
3u
1x
2x
 
 
 
 
 
Capítulo 5 
 
 
104 Norma Torrent 
 
2
1
u
u






0 x, x,x
22x5,00,09x
8,0x002,00,001xx38,0 
a .s
 1,2x0,7x0,32x wMin
321
32
321
321
 
 
 
3
2
1
x 
x 
x 








 
0u,u
2,1u5,0u002,0
7,00,09uu001,0 
32,00,38u
a .s
u220,8uz Max
21
21
21
1
21
 
 
HOLGURAS COMPLEMENTARIAS 
Hemos visto cómo las variables de holgura (o exceso) del problema original se relacionan con 
las variables concretas del problema dual y las concretas del original se relacionan con las de 
exceso (u holgura) del dual. Para el caso del taller de alfarería (Ejemplo 1-1), 
 Primal Dual 
 :*3x sobrante horas diarias mano de obra  :*1u Costo marginal hora de mano de obra 
 :*4x sobrante kg diarios materia prima  :*2u Costo marginal kg de materia prima 
 :
*
5x 
 
cantidad cántaros no producidos que 
satisfarían la demanda máxima diaria  :
*
3u valor marginal de cada cántaro 
 :*1x producción diaria vasijas  :*4u costo reducido de cada vasija 
 :*2x producción diaria cántaros  :*5u costo reducido de cada cántaro 
Dualidad 
 
 
105 
Análogamente, para el problema del Ejemplo 3-2 tendremos, 
 Primal Dual 
 :
*
4x 
 
kg excedentes de calcio por sobre el 
mínimo exigido  :
*
1u valor marginal kg de calcio 
 :
*
5x 
 
kg excedentes de proteínas por sobre 
el mínimo exigido  :
*
2u valor marginal kg de proteínas 
 :*1x kg de CO3Ca en la ración  :*3u costo reducido kg de CO3Ca 
 :*2x kg de maíz en la ración  :*4u costo reducido kg de maíz 
 :*3x kg de harina de soja en la ración  :*5u costo reducido kg harina de soja 
En síntesis: 
 
De esta forma, en el óptimo, siempre que en la k-ésima restricción de uno de los problemas 
(primal/dual) la variable de holgura o de exceso tome un valor distinto de cero, la k-ésima 
variable del otro problema desaparece de la base. Por otra parte, si la k-ésima variable de uno de 
los dos problemas es mayor que cero, en la k-ésima restricción del otro problema se verifica la 
igualdad (la variable de holgura o exceso de esa restricción es igual a cero). 
A esto se denomina condición de holguras complementarias. 
Ejemplo 5-1 El dual de un primal con múltiples soluciones óptimas 
Dado el siguiente programa lineal, 
 
0x,x
1xx3/2
28xx
10x
20x
5x
 
a .s
x000.1x000.1z Max
21
21
21
2
1
2
21







 
a) Plantee el correspondiente programa dual. 
b) Determine la solución de ambos problemas. 
c) Determine la solución de ambos problemas sin utilizar el método Simplex. 
a) Problema dual 
5 ..., 2, 1,i 



 0u 
000.1uuuu 
000.1u)3/2(uu
a .s
uu28u10u20u5w Min
i
5431
542
54321
 
b) Resolvemos el dual (es el que presenta menor cantidad de restricciones) tomando como base 
inicial (A2, A3). 
Capítulo 5 
 
 
106 Norma Torrent 
 –5 20 10 28 1 0 0 
 ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij 
 20 A2 0 1 0 1 –2/3 –1 0 1.000 1.000 
 10 A3 –1 0 1 1 1 0 –1 1.000 1.000 
 zj –10 20 10 30 –10/3 –20 –10 w = 30.000 cj – zj 5 0 0 –2 13/3 20 10 
 
 –5 20 10 28 1 0 0 
 ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij 
 20 A2 1 1 –1 0 –5/3 –1 1 0 
 28 A4 –1 0 1 1 1 0 –1 1.000 
 zj –8 20 8 28 –16/3 –20 –8 w = 28.000 cj – zj 3 0 2 0 19/3 20 8 
La solución óptima es   ,28.000 w;0 0; 0; 1.000; 0; 0; 0;u *T*  solución degenerada. El 
último renglón de esta tabla nos indica que   28.000. z ;19/3 0; 2; 0; 3; 8; 20;x *T*  
Observemos que, en el óptimo, los valores de *2*1 xx y son los jz correspondientes a la base 
inicial identidad, es decir 21 zz y (coincidentes con 7766 z-c z-c y ). 
Por otra parte, si en la primera tabla sale A2 en vez de A3 resulta 
 –5 20 10 28 1 0 0 
 ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij 
 28 A4 0 1 0 1 –2/3 –1 0 1.000 
 10 A3 –1 –1 1 0 5/3 1 –1 0 
 zj –10 18 10 28 –2 –18 –10 w = 28.000 cj – zj 5 2 0 0 3 18 10 
Ahora   28.000 w;0 0; 0; 1.000; 0; 0; 0;u *T*  solución degenerada y para el primal, 
  28.000. z ;3 0; 0; 2; 5; 10; 18;x *T*  Lógicamente si hubiésemos encarado la resolución del 
dual las conclusiones serían idénticas. En este caso la tabla de óptimo es: 
 1.000 1.000 0 0 0 0 0 
 ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij 
 1.000 A1 1 0 0 1 0 0 0 20 
 1.000 A2 0 1 0 –1 0 1 0 8 
 0 A3 0 0 1 –1 0 1 0 3 
 0 A5 0 0 0 1 1 –1 0 2 
 0 A7 0 0 0 5/3 0 –1 1 19/3 
 zj 1.000 1.000 0 0 0 1.000 0 z = 28.000 cj – zj 0 0 0 0 0 –1.000 0 
Luego,   28.000 z ;19/3 0; 2; 0; 3; 8; 20;x *T*  y, en base al último renglón de esta tabla, 
  28.000. w;0 0; 0; 1.000; 0; 0; 0;u *T*  Vemos además que hay múltiples soluciones, 
0),z-(c 44  por lo tanto haciendo entra a A4 se obtiene 
 1.000 1.000 0 0 0 0 0 
 ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij 
 1.000 A1 1 0 0 0 –1 1 0 18 
 1.000 A2 0 1 0 0 1 0 0 10 
 0 A3 0 0 1 0 1 0 0 5 
 0 A4 0 0 0 1 1 –1 0 2 
 0 A7 0 0 0 0 –5/3 2/3 1 3 
 zj 1.000 1.000 0 0 0 1.000 0 z = 28.000 cj – zj 0 0 0 0 0 –1.000 0 
Dualidad 
 
 
107 
La familia de tales soluciones estará dada por: 
     1λ0  ;0;3 0; 2; 5, 10; ;18119/3 0; 2; 0; 3; 8; ;20x TT* 
Los resultados anteriores ponen en evidencia la siguiente generalización. 
Si uno de los problemas (primal o dual) tiene múltiples soluciones óptimas, el otro problema 
tiene solución óptima degenerada. 
Si uno de los problemas (primal o dual) tiene solución óptima degenerada, el otro problema 
tiene múltiples soluciones óptimas. 
c) Aplicaremos el método gráfico. 
 
0x,x
1xx3/2
28xx
10x
20x
5x
 
a .s
x000.1x000.1z Max
21
21
21
2
1
2
21







 
Soluciones alternativas 
 
  
28.000z
 ;3 0; 0; 2; 5, 10; ;181 
19/3 0; 2; 0; 3; 8; ;20x
T
T*



*
1λ0 
z=1.000x
1+1.000x
2=z0
n
 
A partir de  T* 19/3 0; 2; 0; 3; 8; 20;x  
 
 
Tomando el dual como original, 
0u3/19 x,zu
...u0 x,zu
0u2 x,zu
...u0 x,zu
0u3 x,zu
*
5
*
7
*
7
*
5
*
4
*
6
*
6
*
4
*
3
*
5
*
5
*
3
*
2
*
4
*
4
*
2
*
1
*
3
*
3
*
1





 
0u8 x,zx
0u20 x,zx
*
7
*
2
*
7
*
2
*
6
*
1
*
6
*
1


 
Despejando del dual, 1.000u 0;u *4*2  
 
28.000w
0 0; 0; 1.000; 0; 0; 0;u
*
T*

 degenerada 
 
A partir de  T* 3 0; 0; 2; 5; 10; 18;x  
 
 
Tomando el dual como original, 
0u3 x,zu
...u0 x,zu
...u0 x,zu
0u2 x,zu
0u5 x,zu
*
5
*
7
*
7
*
5
*
4
*
6
*
6
*
4
*
3
*
5
*
5
*
3
*
2
*
4
*
4
*
2
*
1
*
3
*
3
*
1





 
0u10 x,zx
0u18 x,zx
*
7
*
2
*
7
*
2
*
6
*
1
*
6
*
1


 
Despejando del dual, 1.000u 0;u *4*3  
 
28.000w
0 0; 0; 1.000; 0; 0; 0;u
*
T*

 degenerada 
 
 
Capítulo 5 
 
 
108 Norma Torrent 
Ejemplo 5-2 El dual de un primal con solución óptima no acotada: propiedades primal-dual 
En el Ejemplo 3-16 resolvimos en formato tabla el siguiente problema lineal, concluyendo que 
su solución no estaba acotada. 
0 x;x
12x3x4
4x2x
15x5x3 
a .s
x08x40zMax21
21
21
21
21





 
Si planteamos su dual 
0u ,u ,u
80u3u2u5 
40u4uu3
a .s
u124u15u wMin
321
321
321
321




 
aplicando el método de las dos fases obtenemos 
 0 0 0 0 0 1 1 
 ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij 
 1 A6 –3 1 –4 –1 0 1 0 40 
 1 A7 –5 –2 3 0 –1 0 1 80 
 zj –8 –1 –1 –1 –1 1 1 f = 120 cj – zj 8 1 1 1 1 0 0 
lo cual nos indica que el dual no tiene soluciones factibles (se ha llegado al óptimo con ambas 
ficticias integrando la base con valor no nulo). Tal resultado no responde a un caso particular 
sino que constituye una propiedad de las relaciones primal-dual. 
En efecto, por (5-7), b.ucx T Luego si *cx no está acotada el dual no tiene soluciones 
factibles ya que de existir una solución posible, u, resultaría ,*T cxbu  lo cual constituye un 
absurdo. 
Si en cambio, el dual no tiene soluciones factibles puede ocurrir que la función objetivo del 
primal no esté acotada o que este último no posea soluciones factibles. 
Si uno de los problemas (primal o dual) tiene una solución óptima no acotada, el otro 
problema no tiene soluciones factibles. 
Si un de los problemas (primal o dual) no tiene soluciones factibles, el otro problema no 
tiene soluciones factibles o bien la función objetivo no está acotada. 
5.6 INTERPRETACIÓN ECONÓMICA DEL DUAL 
Resultaría lógico pensar que más allá de la relación entre los resultados del programa primal y su 
correspondiente dual, debería existir un vínculo entre los dos problemas reales, de los cuales 
ambos programas lineales no son más que sus representaciones. Trataremos entonces de 
establecer dicho vínculo. 
 
 
Dualidad 
 
 
109 
Dado el siguiente problema original 
m ..., 2, 1, j
n ..., 2, 1,i 







 0x 
bxa 
a .s
xcz Max
j
i
n
1j
jij
n
1j
jj
 
Este programa podría corresponder a un problema real en el que una organización dispone 
de una serie de recursos limitados asignables a un número finito de actividades. Se pretende 
determinar a qué nivel debe operar cada actividad de manera de maximizar el beneficio z. 
Las xj son las unidades de los bienes producidos en un cierto período de tiempo y las bi son 
las unidades de recurso i disponibles en dicho período. Las aij son las unidades de recurso i 
insumidas por cada unidad del bien j. 
Si consideramos ahora el programa dual asociado 
n ..., 2, 1, i
m ..., 2, 1,j 







 0u 
cua 
a .s
ub wMin
i
j
m
1i
iij
m
1i
ii
 
dado que los cj son $/unidad del bien j, los aijui deben ser también $/unidad del bien j, por lo 
tanto los ui representan $/unidad del recurso i; w = bTu es entonces, el valor total de los recursos 
disponibles. 
Una restricción cualquiera del dual puede escribirse como ,j
m
1i
iij cua 

donde 

m
1i
iijua es 
el valor de los recursos utilizados para producir una unidad del bien j. 
Es lógico aceptar que con cada asignación de recursos se corresponda un sistema de valores 
de los mismos. Cada valor de un recurso nada tiene que ver con su precio de mercado, 
simplemente es la resultante del aprovechamiento que la organización hace de dicho recurso. Ya 
demostramos que los valores de u que minimizan el dual son los costos marginales del problema 
original. Además cada precio sombra puede interpretarse como el beneficio que deja de percibir 
la organización por no disponer de una unidad más del recurso correspondiente; z* = w* indica 
que el beneficio máximo coincide con el mínimo valor de los recursos. P or otra parte, si fuese 
posible incrementar, o disminuir, la disponibilidad del recurso i en una unidad sin cambiar la 
solución óptima del dual, el beneficio máximo se incrementaría, o disminuiría, en ui. 
Volvamos ahora a las restricciones del dual. j
m
1i
iij cua 

expresa que el valor de los 
recursos utilizados para producir una unidad del bien j debe ser por lo menos igual al beneficio 
unitario de dicho bien, de lo contrario no se estaría haciendo el mejor aprovechamiento de estos 
recursos. Notemos además que si en el óptimo se da la relación de igual xj será mayor que cero, 
si en cambio en el óptimo vale la relación de mayor, xj será nula. 
 
Capítulo 5 
 
 
110 Norma Torrent 
Económicamente esto significa que, 
Siempre que una actividad opere a nivel estrictamente positivo, el costo marginal de los 
recursos que consume debe ser igual al beneficio que proviene de dicha actividad. De lo 
contrario no conviene en absoluto iniciar la actividad. 
Veamos cómo podrían interpretarse los conceptos precedentes en el problema del Ejemplo 
1-1. 
cántaros) de máxima (demanda
prima) materia de lidad(disponibi
obra) de mano de horas de lidad(disponibi
marginal) ión(contribuc
0 x;x
15x
75x5,1x3
40x2x 
a s.
 x5420xzMax 
21
2
21
21
21





 
Supongamos que el dueño del taller de alfarería pudiese contratar un seguro para sus 
ingresos con las siguientes características. 
u1: monto en $ que deberá pagar la compañía de seguros por cada hora de mano de obra 
perdida. 
u2: monto en $ que deberá pagar la compañía de seguros por cada kilogramo de arcilla 
perdido. 
u3: monto en $ que deberá pagar la compañía de seguros por cada decremento de una 
unidad en la demanda máxima de cántaros. 
De esta forma, la compañía de seguros intentará minimizar el monto total a pagar al dueño 
del taller, es decir minimizar 40u1 + 75u2 + 15u3. Sin embargo, el dueño del taller fijará las 
condiciones para que la compañía cubra todos sus ingresos netos en caso de no poder fabricar 
sus productos. Así, el problema de la compañía es 
cántaro) cada de marginal ión(contribuc
vasija) cada de marginal ión(contribuc
0u ,u ,u
45uu5,1u2 
20u3u
a .s
u1575u40u wMin
321
321
21
321




 
Ya sabemos que el problema del taller de alfarería y su correspondiente programa dual 
presentan el mismo valor óptimo );( ** wz  a esto se denomina equilibrio económico entre 
ambos problemas. 
Una interpretación similar puede hacerse para el caso en que el primal esté dado por 
m ..., 2, 1, j
n ..., 2, 1,i 







 0x 
bxa 
a .s
xc wMin
j
i
n
1j
jij
n
1j
jj
 
 
 
Dualidad 
 
 
111 
Volvamos al Ejemplo 3-2 
proteínas) de mínimo ento(requerimi 
calcio) de mínimo ento(requerimi
diaria) ración la de (costo
 
0 x, x,x
22x5,00,09x
8,0x002,00,001xx38,0 
a .s
 1,2x0,7x0,32x wMin
321
32
321
321




 
En el problema primal el vector b representa los nutrientes mínimos que debe contener la 
ración diaria a suministrar al comedero. Cada aij es el contenido de nutriente i por kg de 
ingrediente j. 
Su programa dual asociado es 
 soja)de harina de kg del (costo 
maíz) de kg del (costo 
Ca)CO de kg del (costo 3
0u,u
2,1u5,0u002,0
7,00,09uu001,0 
32,00,38u
a .s
u220,8uz Max
21
21
21
1
21





 
Analizando este problema, vemos que las unidades de ui son $/kg del nutriente i (es decir, 
$/unidad del nutriente i). Por lo tanto, la función económica del dual pretende maximizar el valor 
de los nutrientes requeridos en la ración diaria. 
Para cada restricción, 

2
1i
iijua será el valor de los nutrientes que intervienen en cada unidad 
(kg) del ingrediente j. Este valor debe ser menor o igual al costo del ingrediente. Como es de 
esperar, la dieta óptima contendrá sólo aquellos ingredientes para los cuales el valor de los 
nutrientes sea igual a su costo. 
En este caso podríamos pensar que una empresa de productos alimentarios para aves desea 
suministrar al criadero gránulos de calcio y gránulos de proteínas. 25 La empresa debe convencer a 
los responsables del criadero de que compren sus productos en reemplazo de la ración que 
actualmente están utilizando. Para ello, el precio de venta de los gránulos debe resultarcompetitivo con respecto al de los ingredientes que intervienen en dicha ración. 
Si u1 y u2 son los precios de venta por kilogramo de los gránulos de calcio y los de proteínas 
respectivamente, el objetivo de la empresa es fijar tales precios de manera que, resultando 
competitivos para el criadero, maximicen sus beneficios. 
Cada kilogramo de CO3Ca aportaba a la ración 0,38kg de calcio y 0kg de proteínas. El 
precio que debería pagar el criadero para obtener estas mismas cantidades de nutrientes en 
gránulos sería 0,38u1 + 0u2. Para que la compra de gránulos resulte atractiva para el criadero 
debe ocurrir que 0,38u1 + 0u2  0,32. 
Razonando en forma idéntica con respecto a los restantes ingredientes (maíz y harina de 
soja) obtendríamos 0,001u1 + 0,09u2  0,7 y 0,002u1 + 0,5u2  1,2. 
Lógicamente los precios de los gránulos deben ser positivos (u1, u2 ≥ 0). 
 
25 En la realidad el calcio y las proteínas no se consiguen en estado puro. Hemos planteado el supuesto de los 
gránulos al sólo efecto de analizar la vinculación económica entre los programas primal y dual. 
 
Capítulo 5 
 
 
112 Norma Torrent 
Ahora bien, suponiendo que el criadero acceda a emplear los gránulos comprará 
exactamente las necesidades mínimas de ambos nutrientes, esto es, 0,8kg de gránulos de calcio y 
22kg de gránulos de proteínas. Los ingresos diarios de la empresa serán entonces 0,8u1 + 22u2. 
Así, para establecer sus precios de venta la empresa debería resolver el programa dual. 
5.7 ANÁLISIS PARAMÉTRICO Y DUALIDAD 
Ya sabemos que todo problema de programación lineal tiene un problema dual asociado que 
contiene exactamente los mismos valores paramétricos. Veamos entonces cómo efectuar la 
parametrización en los términos independientes haciendo uso de las propiedades primal-dual. 
Supongamos que estamos interesados en estudiar el comportamiento de la solución óptima 
cuando en el Ejemplo 1-1 1b varía entre 0 y . 
Expresando a 1b como λ),40(1)(b1  tendremos 
)1(
0 x,x
15x
75x5,1x3
40x2x
a .s
45x20x z Max
21
2
21
21
21






 
Luego, el programa dual asociado estará dado por 
0u ,u ,u
45uu5,1u2 
20u3u
a .s
u1575u)u40(1 wMin
321
321
21
321




 
con lo cual el estudio de la variación en 1b en el problema original se traduce a un análisis 
paramétrico en los coeficientes económicos del programa dual. Para 0λ  la tabla de óptimo es: 
 40(1+) 75 15 0 0 xi/yij 
(yij>0) 
 
 ci Ai A1 A2 A3 A4 A5 xi 
 40(1+) A1 1 3 0 –1 0 20 
 15 A3 0 –9/2 1 2 –1 5 
 zj 40(1+) 105/2+120 15 –10–40 –15 w = 875+800 
 
 cj – zj 0 22,5–120 0 10+40 15 
Si 0zc 22  0,1875λ  y 0z-c 44  0,25λ  esta tabla es la de óptimo. Si 
0,25λ  ingresa 4A y sale 3A . 
 40(1+) 75 15 0 0 xi/yij 
(yij>0) 
 
 ci Ai A1 A2 A3 A4 A5 xi 
 40(1+) A1 1 3/4 1/2 0 –1/2 22,5 
 0 A4 0 –9/4 1/2 1 –1/2 2,5 
 zj 40(1+) 30+30 20+20 0 –20–20 w = 900+900 
 
 cj – zj 0 45–30 –5–20 0 20+20 
La nueva tabla es óptima para 0,25.λ1  Nos resta estudiar qué suceda para 
0,1875.λ  
 
Dualidad 
 
 
113 
Volviendo a la primera tabla vemos que si 0,1875.λ  ingresa 2A y sale 1A . 
 40(1+) 75 15 0 0 xi/yij 
(yij>0) 
 
 ci Ai A1 A2 A3 A4 A5 xi 
 75 A2 1/3 1 0 –1/3 0 20/3 
 15 A3 3/2 0 1 1/2 –1 35 
 zj 47,5 75 15 –17,5 –15 w = 1.025 cj – zj –7,5+40 0 0 17,5 15 
Para 0,1875λ  esta última tabla es óptima. 
Puesto que hemos cubierto el intervalo de variación de λ (  λ1 ), tomamos el 
programa dual como original y, haciendo uso de las relaciones entre ambos problemas, 
obtenemos el siguiente cuadro de resultados. 
 
Ejemplo 5-3 Análisis paramétrico en los términos independientes 
Resolveremos los siguiente programa lineal para 0    +. 
0 x,x,x
245x22xx
30x2x2x 
a s.
x37x4x z Max
321
321
321
321




 
Tabla de Óptimo ( = 0) 
 4 7 3 0 0 
 ci Ai A1 A2 A3 A4 A5 xi xi/yij 
 4 A1 1 0 2/3 2/3 –1/3 5 
 7 A2 0 1 2/3 –1/3 2/3 20 
 zj 4 7 22/3 1/3 10/3 z = 160 cj – zj 0 0 –13/3 –1/3 –10/3 
El correspondiente problema dual es 
0u ,u
32uu2
7u2u
4uu2
a .s
u)245(u)(30 wMin
21
21
21
21
21





 
Capítulo 5 
 
 
114 Norma Torrent 
Si  = 0  13/3.u 0,u 0,u10/3u 1/3,u *5*4*3*2*1  Luego obtenemos la tabla de 
óptimo y comenzamos el análisis. 











 
1 3/23/2
03/23/1
03/1 3/2
B)A ,A ,A(B 1521 
 30 45 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi xi/yij 
 30 A1 1 0 –2/3 1/3 0 1/3 
 45 A2 0 1 1/3 –2/3 0 10/3 
 0 A5 0 0 –2/3 –2/3 1 13/3 
 zj 0 45 –5 –20 0 w = 160 cj – zj 0 0 5 20 0 
 
 30– 45–2 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi xi/yij 
 30– A1 1 0 –2/3 1/3 0 1/3 
 45–2 A2 0 1 1/3 –2/3 0 10/3 
 0 A5 0 0 –2/3 –2/3 1 13/3 
 zj 30– 45–2 –5 –20+ 0 w = 160–7 
 
 cj – zj 0 0 5 20– 0 
Para   20 esta tabla es óptima. Si  > 20 ingresa A4 y sale A1. 
 30– 45–2 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi xi/yij 
 0 A4 3 0 –2 1 0 1 
 45–2 A2 2 1 –1 0 0 4 
 0 A5 2 0 –2 0 1 5 
 zj 90–4 45–2 –45+2 0 0 w = 180 –8 
 
 cj – zj –60+3 0 45–2 0 0 
Para 20    22,5 la tabla actual es óptima. Si  > 22,5 la solución no está acotada. Si 
analizamos el original vemos que para  = 22,5 la solución es degenerada y para  > 22,5 el 
programa no es factible (por propiedad del primal-dual). 
Resumen de cuadros 
 
5.8 EL MÉTODO DUAL SIMPLEX 
Cuando utilizamos el método Simplex para resolver un problema primal de maximización en su 
forma canónica, partimos de una solución básica factible y generamos sucesivos puntos extremos 
hasta arribar a la solución óptima (si existe), es decir, mantenemos la factibilidad mientras se 
busca la optimización. 
Dualidad 
 
 
115 
Desde el punto de vista de la dualidad siempre que en las tablas del primal exista al menos 
un ,0zc jj  las soluciones del problema dual serán no factibles. El dual se vuelve factible 
cuando el primal alcanza el óptimo. 
Surge entonces la posibilidad de emplear otro procedimiento iterativo, similar al Simplex, 
que comience con una solución básica óptima ( 0zc jj   Aj) pero no factible y, en las 
subsiguientes tablas, conserve siempre los coeficientes jj zc  no positivos hasta lograr la 
factibilidad, en cuyo caso estaremos en el óptimo. Este nuevo algoritmo fue desarrollado por C. 
E. Lemke en 1954 y se conoce con el nombre de método Dual Simplex. Las ventajas de su 
aplicación con respecto al Simplex son el prescindir de variables ficticias y requerir un menor 
número de iteraciones. Como contrapartida, no siempre resulta sencillo disponer de una solución 
básica inicial no factible e inmejorable. 
Por otra parte el Dual Simplex facilita el análisis post-óptimo en lo referente a cambios en 
los términos independientes y agregado de nuevas restricciones. 
ALGORITMO DEL DUAL SIMPLEX 
Para resolver un programa lineal mediante el método Dual Simplex los pasos a seguir son 
1. Convertir todas las restricciones a  y llevar el problema a su forma estándar. Disponer 
de una solución básica inicial inmejorable ( 0zc jj   Aj en caso maximización; 
0zc jj   Aj en caso de minimización). 
2. Si 0xi   i  IB, la solución actual es la óptima. En caso contrario, ir al punto 3. 
3. Escoger como variable que sale, ,xr a la que posea el menor valor negativo (tanto para 
maximización como para minimización). Los empates pueden romperse 
arbitrariamente. 
4. La variable que entra, ,xk será la que satisfaga la siguiente condición 
 ón)minimizaci o ónmaximizaci (para0y con rj , y
zc
min
y
zc
rj
jj
rk
kk











 
 Si no hay ningún 0yrj  el problema esno factible. 
5. Utilizar operaciones elementales para convertir la variable que entra en una variable 
básica en el renglón pivote. Ir la punto 2. 
Ejemplo 5-4 El algoritmo Dual Simplex 
Resolveremos el siguiente programa lineal. 
5x
3x
8x x
s.a
3x x wMin
2
1
21
21




 
1. Convertimos las restricciones a , llevamos el problema a su forma estándar y obtenemos 
una solución básica inicial inmejorable. 
Capítulo 5 
 
 
116 Norma Torrent 
0x,x,x,x,x
5xx
3xx
8xxx
s.a
x0x0x03x x wMin
54321
52
41
321
54321





 
 1 3 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi 
 0 A3 1 1 1 0 0 8 
 0 A4 –1 0 0 1 0 –3 
 0 A5 0 –1 0 0 1 –5 
 zj 0 0 0 0 0 cj – zj 1 3 0 0 0 
0zc jj   Aj. 
2. Puesto que ,y 0x x 54  pasamos a 3. 
3. Determinamos la variable que sale de la base. 
5x35 sale 
4. Seleccionamos la variable entrante. 
Dado que el único .x 1 y0 y 2525j entra , es  
 1 3 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi 
 0 A3 1 1 1 0 0 8 
 0 A4 –1 0 0 1 0 –3 
 0 A5 0 –1 0 0 1 –5 
 zj 0 0 0 0 0 cj – zj 1 3 0 0 0 
5. Utilizamos operaciones elementales para convertir la variable que entra en una variable 
básica en el renglón pivote. 
 1 3 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi 
 0 A3 1 0 1 0 1 3 
 0 A4 –1 0 0 1 0 –3 
 3 A2 0 1 0 0 –1 5 
 zj 0 3 0 0 –3 cj – zj 1 0 0 0 3 
Primera iteración 
2. 3. a pasamos tantolopor ,0x4  
3. Sale .4x 
4. El único .x 1 y0 y 1414j entra , es  
5. Mediante operaciones elementales obtenemos la siguiente tabla. 
Dualidad 
 
 
117 
 1 3 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi 
 0 A3 0 0 1 1 1 0 
 1 A1 1 0 0 –1 0 3 
 3 A2 0 1 0 0 –1 5 
 zj 1 3 0 –1 –3 w = 18 cj – zj 0 0 0 1 3 
La solución es óptima, a).(degenerad 18z 0;x 0;x 0;x 5;x 3;x **5
*
4
*
3
*
2
*
1  
Ejemplo 5-5 El algoritmo Dual Simplex: agregado de una nueva restricción 
En el apartado 4.6 del capítulo anterior vimos que si al problema del taller de alfarería (Ejemplo 
1-1) se le añade la restricción 8,x1  la solución óptima previamente obtenida es inadmisible. 
Además, con el propósito de evitar resolver nuevamente el problema, introdujimos la nueva 
restricción en la tabla de óptimo y mediante operaciones elementales obtuvimos la siguiente 
tabla, dejando pendiente su tratamiento en espera del método Dual Simplex. 
 20 45 0 0 0 0 
 ci Ai A1 A2 A3 A4 A5 A6 xi 
 20 A1 1 0 1 0 –2 0 10 
 0 A4 0 0 –3 1 9/2 0 45/2 
 45 A2 0 1 0 0 1 0 15 
 0 A6 0 0 –1 0 2 1 –2 
 zj 20 45 20 0 5 0 cj – zj 0 0 –20 0 –5 0 
Estamos ahora en condiciones de abordar la solución. El Dual Simplex nos dice que debe 
salir 6x y entra a la base ,3x resultando 
 20 45 0 0 0 0 
 ci Ai A1 A2 A3 A4 A5 A6 xi 
 20 A1 1 0 0 0 0 1 8 
 0 A4 0 0 0 1 –3/2 –3 57/2 
 45 A2 0 1 0 0 1 0 15 
 0 A3 0 0 1 0 –2 –1 2 
 zj 20 45 0 0 45 20 z = 835 cj – zj 0 0 0 0 –45 –20 
La solución óptima es, 835.z 0;x 0;x 28,5;x 2;x 15;x 8;x **6
*
5
*
4
*
3
*
2
*
1  
Ejemplo 5-6 El algoritmo Dual Simplex: cambio en el vector b de las restricciones 
Supongamos que para el problema del Ejemplo 1-1 se dispondrá, en las próximas semanas, sólo 
de 25 horas diarias de mano de obra. ¿Cuál será entonces el plan óptimo de producción? 
En la sección 4.3 vimos que mientras 47,5b30 1  la base óptima no cambia. Luego si 
25b1  la solución básica deja de ser factible. En efecto, 
einadmisibl básica solución







 




























 
5,67
15
5
15
75
25
2/9 13
100
20 1
bB
x
x
x
x 1
4
2
1
B 
 
 
Capítulo 5 
 
 
118 Norma Torrent 
Así, la tabla de arranque del Dual Simplex será 
 20 45 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi 
 20 A1 1 0 1 0 –2 –5 
 45 A2 0 1 0 0 1 15 
 0 A4 0 0 –3 1 9/2 135/2 
 zj 20 45 20 0 5 cj – zj 0 0 –20 0 –5 
Hacienda salir a 1x e ingresando a 5x se obtiene 
 20 45 0 0 0 
 ci Ai A1 A2 A3 A4 A5 xi 
 0 A5 –1/2 0 –1/2 0 1 5/2 
 45 A2 1/2 1 1/2 0 0 25/2 
 0 A4 9/4 0 –3/4 1 0 225/4 
 zj 45/2 45 45/2 0 0 z = 
562,5 
 
 cj – zj –5/2 0 –45/2 0 0 
y la solución óptima es 562,5.z 2,5;x 56,25;x 0;x 12,5;x 0;x **5
*
4
*
3
*
2
*
1 