DUALIDAD-SIMPLEX DUAL

PROGRAMAS PRIMAL Y DUAL

2° Aplicación de Sistemas de Ecuaciones Lineales
SIMPLEX DUAL
Concepto de Dualidad

Del latín dualĭtas, el término dualidad señala la existencia

de dos fenómenos o caracteres diferentes en una misma
persona o en un mismo estado de cosas. En el ámbito de la
filosofía y la teología, se conoce como dualismo a la
doctrina que postula la existencia de dos principios
supremos independientes, antagónicos e irreductibles.

En este sentido, las nociones del bien y del mal son un

ejemplo de dualidad. Ambas pueden definirse por oposición
y hacen referencia a dos esencias completamente distintas.
Materia-espíritu y realismo-idealismo son otras muestras
de conceptos que conforman una dualidad.
EL BIEN Y EL MAL
En este caso, todo el conjunto de doctrinas
dualistas existentes y que, como hemos
mencionado, parten de esa diferenciación entre
el Bien y el Mal tienen una serie de rasgos en
común. Así, por ejemplo, nos encontramos con
el hecho de que el Bien siempre se identifica
con la luz y también con el espíritu. Por su
parte, el Mal se asocia en todo momento con la
oscuridad, con lo que es la parte corporal y
también con el propio Diablo.
DUALIDAD MATEMÁTICA
SUMA – RESTA

MULTIPLICACIÓN - DIVISIÓN

POTENCIACIÓN – RADICACIÓN

FUNCIÓN EXPONENCIAL – FUNCIÓN LOGARÍTMI

DERIVACIÓN - INTEGRACIÓN
DUALIDAD EN OPTIMIZACIÓN
 Todo programa matemático existe asociado a
otro denominado dual.

 Dado el Programa lineal P:

 Max Z=cx
 Sujeto a, Ax ≤b, x ≥0

 Entonces el Programa dual D es:

 Min W=b´y
 Sujeto a: A’y ≥c’, y≥ 0
Ejemplos

 Hallar el dual del siguiente programa Primal:

 Max z= 4x1 + 3x2
 Sujeto a
 X1 + 5x2 ≤ 10
 2x1 + 3x2≤ 15
 X1, x2 ≥ 0
Dual del Primal
 Min w = 10y1 + 15y2
 Sujeto a
 Y1 + 2 y2 ≥ 4
 5y1 + 3y2≥ 3
 Y1, y2 ≥ 0
Ej. Hallar el dual del siguiente PL
 Max z= 7x1 + 2 x2 + 3 x3
 Sujeto a
 X1 + 8 x2 + 9 x3 ≤ 100
 5 x1 – x2 – x3 ≤ 10
 16 x1 + x2 + x3 ≤ 150
 4x1 – 20 x2 -30 x3 ≤ 90
 X1, x2, x3 ≥ 0
Dual
 Min w = 100 y1 + 10 y2 + 15 y3 + 90 y4
 Sujeto a
 Y1 + 5 y2 + 10 y3 + 4 y4 ≥ 7
 8 y1 – y2 + y3 – 20 y4 ≥ 2
 9 y1 – y2 + y3 – 30 y4 ≥ 3
 yj≥0, j=1,2,3,4
Ej. Hallar el dual del siguiente de PL
 Max z = 4 x1 + 3 x2
 Sujeto a
 9 x1 + 7 x2 ≤ 100
 8 x1 + 6 x2 ≤ 75
 2 x1 + 5 x2 ≤ 50
 X1, x2 ≥ 0
Dual
Primer teorema de dualidad
 Si Xo es una solución factible del programa P,
Yo es una solución factible del dual D,
entonces Zo =cXo ≤ b’Yo = Wo
 DEMOSTRACIÓN
 Y’oAXo ≤ Y’ob=b’Yo = Wo, pues Yo ≥ 0
 Como Yo es una sol. Fact. de D
 A’Yo ≥ c’ < ----- > Y’oA ≥ c
 Zo = cXo ≤ Y’oAXo ≤ Y’ob = b’Yo = Wo
Segundo teorema de dualidad
 SI Xo, Yo son soluciones factibles de P y D
respectivamente y si cXo = b’Yo, entonces Xo
es solución óptima de P y Yo es solución
óptima de D
Formul. del P dual desde el Primal,
Método Deductivo
 En los problemas de ingeniería,
administración, comercio, etc, el programa
primal tiene una interpretación concreta por
cuanto las variables que intervienen tienen
significado económico o físico y con uso de
los conceptos anteriores y del cálculo
difererencial deducimos el programa dual.

Ejemplo
 Una Cía produce radios y televisores, cada
radio se vende con ganancias de 30 soles y
cada TV con ganancia de 50.
 Ambos productos deben pasar por los

departamentos A y B. Mensualmente se
dispone 20 h del departamento A y 14 del B
 Cada radio requiere 1 hora de A y 1 hora de

B, cada TV requiere 2 horas de A y 1 hora de

B. Cuál es programa de producción que
maximiza la ganancia?
 X = nº de unidades del producto 1
Y = nº de unidades del producto 2
G = 30 X + 50Y
nº de unidades disponibles del recurso 1=20
nº de unidades disponibles del recurso 2=14
 Sujeto a
 X+ 2Y ≤ 20 (debido al Dpto A)
 X + Y ≤14 (debido al Dpto B)
 X, Y ≥ 0

Z = valor unit del recurso 1 (valor de 1 h en A

W = valor unit del recurso 2 (valor de 1 h de B
El óptimo es (8,6)-- > G=540
 Entonces el valor mínimo del dual es R=540
 Si el recurso 1 se aumenta de 20 a 21,

entonces la nueva solución óptima es Y=7,

X=7, de tal modo que G=560
 Zo=∆G/∆b1=(560-540)/(21-20) =20
 Si el recurso 2 se aumenta de 14 a 15

(dejando b1 en 20), la nueva solución del

primal es Y=5, X=10, G= 550, entonces
 Wo= ∆G/∆b2= (550 -540)/(15-14) =10
 El óptimo del dual es Yo = (20,10), R =540
Otras formas del primal y dual

 Teorema 3.- Si el Primal es de la forma:

 Max Z=cx
 Sujeto a, Ax = b, x ≥0

 Entonces el Programa dual D es:

 Min W=b´y
 Sujeto a: A’y ≥c, y sin restricciones
Teorema 4
 Si el Primal es de la forma:
 Max Z=cx
 Sujeto a, Ax < b, x ≥0

 Entonces el Programa dual D es:

 Min W=b´y
 Sujeto a: A’y ≥c, y ≥ 0
Teorema 5
 Si el Programa Primal es de la forma:
 Max Z=cx
 Sujeto a, Ax = b, x sin restricciones

 Entonces el Programa dual D es:

 Min W=b´y
 Sujeto a: A’y = c, y sin restricciones
Reglas de transformación Primal -
Dual
 Primal Dual
 Maximización Minimización
 i-ésima restric ≤ i-ésima variable
yi≥0
Teorema 6 de dualidad
 Xo es una solución factible del Primal, Xo es
óptima sss existe Yo una solución factible del
dual D tal que cXo = b’Yo
 EJ.- PRIMAL: max Z = 2 x1 + 5 x2
 Sujeto a
 2 x1 + 3 x2 ≤ 30
 X2 ≤ 6
 X1, x2 ≥ 0

 EL DUAL es
Min W = 30 y1 + 6 y2
 Sujeto a
 2y1 ≥ 2,
 3 y1 + y2 ≥ 5
 y1, y2 ≥ 0
Teorema 7
 A) Un programa lineal tiene una solución óp
tima finita sss el primal y el dual tiene
soluciones factibles.
 B) si el primal tiene un máximo no acotado,

entonces el dual no tiene solución factible.

 C) si el dual no tiene solución factible, pero

el primal si, entonces el primal tiene un

máximo acotado.
Método dual simplex
Este método se aplica cuando hay por lomenos
una restricción ≥
 Condición de factibilidad.- la variable que

sale es la variable que tiene el valor más

negativo. (Los empates se rompen
arbitrariamente) si todas las variables básicas
son no negativas el proceso termina y se
alcanza la solución factible (óptima).
Condición de optimalidad
 La variable que entra se elige de entre las
variables no básicas de los cocientes de los
coeficientes de la ecuación z entre los
coeficientes correspondientes a la ecuación
asociada a la variable que sale. Ignore los
cocientes asociados a denominadores
positivos o cero (rompa los empates arbitrar).
Si todos los denominadores son cero o
positivos el problema no tiene ninguna
solución factible.
 Ejemplo 1

 Min Z = 2 x1 + x2, sujeto a

 3 x1 + x2 ≥ 3
 4 x1 + 3 x2 ≥ 6
 X1 + 2 x2 ≤ 3
 X1, x2 ≥ 0
 Se estandariza
 Max z = -2 x1 - x2, sujeto a
 -3 x1 – x2 + x3 = -3
 - 4 x1 -3 x2 +x4 = -6
 X1 + 2 x2 + x5 = 3
 Xj ≥ 0
 tablero simplex dual

Cb x1 x2 x3 x4 x5 b base
0 -3 -1 1 0 0 -3 x3
0 -4 -3 0 1 0 -6 x4
0 1 2 0 0 1 3 x5
Z -2 -1 0 0 0 0
clc;clear;
disp(‘ iteración 1, sale x4, ingresa x2’);
A=[-3 -1 1 0 0 -3; -4 -3 0 1 0 -6; 1 2 0 0 1 3; -2 -1 0 0 0 0
A(2,:)=A(2,:)/A(2,2);
A(1,:)=A(1,:) -A(2,:)*A(1,2);
A(3,:)=A(3,:) -A(2,:)*A(3,2);
A(4,:)=A(4,:) -A(2,:)*A(4,2)
Esta solución inicial no es factible
 La variable que sale es x4 ya que tiene el
valor más negativo -6, para la variable que
entra los cocientes son:
 Variable x1 x2 x3 x4 x5
 Ecuación z -2 -1 0 0 0
 {-2/-4 -1/-3}
 Entra x2, de tal modo que el Pibot es:
 A(2,:) = A(2,: )/A(2,2); y el resto de filas

juegan con éste Pibot, así:

 A(1,: )=A(1,: ) – A(2,: )*A(1,2)
 Tabla 2

x1 x2 x3 x4 x5 b bas
-1.67 0 1.00 -0.33 0 -1.00 x3
1.33 1.00 0 -0.33 0 2.00 x2
-1.67 0 0 0.67 1.00 -1.00 x5
-0.67 0 0 -0.33 0 2.00 Z
Q 0.50 0 NaN 1.00 NaN 1.00

disp(‘ Iteración 2, Sale x3, entra x1, Pibot es A1’);

A(1,: )=A(1,: )/A(1,1);
A(2,: )=A(2,: ) – A(1,: )*A(2,1);
A(3,: )=A(3,: ) – A(1,: )*A(3,1);
A(4,: )=A(4,: ) – A(1,: )*A(4,1)
Ejemplo 2

Paso 1: Se lleva el modelo a su forma estándar. En nuestro

ejemplo esto se logra agregando variables de exceso en
cada una de las restricciones (3 primeras: S1, S2, S3,
respectivamente). Luego, se multiplica cada fila de las
restricciones por -1 de modo de disponer una solución
básica inicial (infactible) en las variables de exceso S1, S2
y S3
Paso 2
Se selecciona el lado derecho "más negativo" lo cual
indicará cuál de las actuales variables básicas deberá
abandonar la base. En el ejemplo el lado derecho más
negativo se encuentra en la primera fila, por tanto S1 deja
la base. Para determinar cual de las actuales variables no
básicas (A, B, C) entrará a la base se busca el mínimo de
{-Yj/aij} donde aij es el coeficiente de la respectiva
variable no básica en la fija i (del lado derecho más
negativo, marcado en verde) y donde Yj es el costo
reducido de la respectiva variable no básica. De esta
forma se obtiene: Min {-315/-15, -110/-2, -50/-1} =
21, donde el pivote (marcado en rojo) se encuentra al
hacer el primer cuociente, por tanto A entra a la base.
Paso 3
 Se actualiza la tabla anterior siguiendo un
procedimiento similar al utilizado en el 
Método Simplex. En el ejemplo se debe dejar a
la variable A como básica y S1 como no básica.
La tabla que resulta es la siguiente:
A B C S1 S2 S3 b bas
-15.00 -2.00 -1.00 1.00 0 0 -200.00 S1
-7.50 -3.00 -1.00 0 1.00 0 -150.00 S2
-5.00 -2.00 -1.00 0 0 1.00 -120.00 S3
-315.00 -110.00 - 50.00 0 0 0 0 Z
disp(‘Iteración 1, sale S1, ingresa A’);
A(1,: )=A(1,: )/ A(1,1);
A(2,:)=A(2,:)-A(1,:)*A(2,1);
A(3,: )=A(3,:)-A(1,:)*A(3,1);
A(4,:)=A(4,:)- A(1,:)*A(4,1)
Tabla 2

A B C S1 S2 S3 b
1 2/15 1/15 -1/15 0 0 40/3

0 -2 -1/2 -1/2 1 0 -50

0 -4/3 -2/3 -1/3 0 1 -160/3

0 68 29 21 0 0 -4.200
clc;clear;
A=[-15 -2 -1 1 0 0 -200; -7.5 -3 -1 0 1 0 -150; -5 -2 -1 0 0 1 -120; 315 110 50 0 0 0
disp('iteración 1');disp('sale S1, ingresa A');
A(1,: )=A(1,: )/ A(1,1);
A(2,:)=A(2,:)-A(1,:)*A(2,1);
A(3,: )=A(3,:)-A(1,:)*A(3,1);
A(4,:)=A(4,:)- A(1,:)*A(4,1)
Q=A(4,:)./A(1,:)
disp('iteración 2');disp('sale S3, ingresa B');
A(3,: )=A(3,: )/ A(3,2);
A(1,:)=A(1,:)-A(2,:)*A(1,2);
A(2,: )=A(2,:)-A(2,:)*A(2,2);
A(4,:)=A(4,:)- A(2,:)*A(4,2)
Q=A(4,:)./A(2,:)
 TABLA 3

A B C S1 S2 S3 b
1.00 0 0.03 -0.10 0.07 0 10.00
0 1.00 0.25 0.25 -0.50 0 25.00
0 0 -0.33 0.00 -0.67 1.00 -20.00
0 0 12.00 4.00 34.00 0 -5900.00

Disp(‘Iteración 3, Sale S3, ingresa C’);

 clc;clear;
 A=[-15 -2 -1 1 0 0 -200; -7.5 -3 -1 0 1 0 -150; -5 -2 -1 0 0 1 -120; 315 110 50
0 0 0 0];
 disp('iteración 1');disp('sale S1, ingresa A');
 A(1,: )=A(1,: )/ A(1,1);
 A(2,:)=A(2,:)-A(1,:)*A(2,1);
 A(3,: )=A(3,:)-A(1,:)*A(3,1);
 A(4,:)=A(4,:)- A(1,:)*A(4,1)
 Q=A(4,:)./A(1,:)
 disp('iteración 2');disp('sale S2, ingresa B');
 A(2,: )=A(2,: )/ A(2,2);
 A(1,:)=A(1,:)-A(2,:)*A(1,2);
 A(3,: )=A(3,:)-A(2,:)*A(3,2);
 A(4,:)=A(4,:)- A(2,:)*A(4,2)
 Q=A(4,:)./A(2,:)
 disp('iteración 3');disp('sale S3, ingresa C');
 A(3,: )=A(3,: )/ A(3,3);
 A(1,:)=A(1,:)-A(3,:)*A(1,3);
 A(2,: )=A(2,:)-A(3,:)*A(2,3);
 A(4,:)=A(4,:)- A(3,:)*A(4,3)
Paso 4: Continuar las iteraciones y siguiendo el
mismo procedimiento hasta disponer de una
solución básica factible, se obtiene la siguiente
tabla final:

A B C S1 S2 S3 b

1 0 0 -1/10 0 1/10 8

0 1 0 1/4 -1 3/4 10

0 0 1 0 2 -3 60

0 0 0 4 10 36 -6.620
La solución óptima
es A=8, B=10, C=60 (marcado en verde) con
valor óptimo V(P)=6.620 (marcado en rojo - se
obtiene con signo cambiado). También es
interesante notar que los costos reducidos de
las variables artificiales S1, S2 y S3 (marcado
en amarillo), corresponde a la solución óptima
del modelo presentado en el tutorial de solver,
esto dado que dicho modelo resulta ser el 
problema dual de nuestro ejemplo.
Ejemplo 3

Para llevar el problema anterior a la forma estándar se

requiere agregar 2 variables de exceso no negativas para
la restricción 1 y 2, que llamaremos
respectivamente X4 y X5. De esta forma el problema en
su formato estándar queda definido por:
Forma estándar
tabla inicial del Método Simplex:
 ¿Cómo continuar con las iteraciones del Método
Simplex?. Antes de ello es necesario disponer de
una solución básica factible inicial. En este
contexto si quisiéramos
usar X4 y X5 como variables básicas (y en
consecuencia X1, X2 y X3 como variables no
básicas) se requiere que X4 y X5 sean mayores o
iguales a cero, sin embargo, sus coeficientes en las
respectivas filas son negativos y por tanto no se
dispone de la identidad (matriz con “1” como
diagonal y el resto de coeficientes igual a cero).
 En consecuencia para formar la identidad podemos

multiplicar por “-1” la fila 1 y 2, obteniendo lo

siguiente:
Tabla 2
Ahora X4 y X5 son variables básicas y adoptan los
valores de -1 y -3/2, respectivamente, lo que
claramente no satisface las condiciones de no
negatividad para las variables de decisión, es
decir, no corresponde a una solución básica
factible.
Sin embargo, en esta instancia podemos aplicar
el Método Simplex Dual como alternativa de
resolución. Para ello seleccionaremos una variable
que deje la base y adoptaremos como criterio de
selección aquella variable básica asociada al lado
derecho “más negativo” (con esto se busca
favorecer la rapidez de convergencia).
 Luego para determinar que variable entra a la base
realizamos un mínimo cuociente entre el negativo del
costo reducido de las variables no básicas y las entradas
estrictamente menores a cero para las variables no básicas
en la fila 2 (fila asociada al lado derecho más negativo).
 Es decir: Min{-160/-2; -120/-2; -280/-2}=60 ==> el
cuociente mínimo se alcanza en la segunda columna
asociada a la variable no básica X2, por tanto dicha
variable entra a la base.
 En cada iteración del Método Simplex Dual se escoge un
lado derecho con valor negativo, identificando la
respectiva variable básica primal, quien deja la base.
 Finalmente se realiza una iteración realizando las
operaciones filas que sean necesarias, de modo de
ingresar X2 a la base al mismo tiempo que X5 deja la
Tabla 3

sólo X4=-1/4 lo que no satisface la condición de ser una

solución básica factible. Por lo tanto realizamos una nueva
iteración, en este caso sacando de la base a la variable X4 y
calculamos el mínimo cuociente: Min{-40/-1; -160/-3;
-60/-1/2}=40 ==> el cuociente mínimo está en la primera
columna por tanto la variable X1 entra a la base.
Actualizando transformación de filas, se obtiene

Las variables básicas ahora son X1=1/4 y X2=1/2 

(que cumplen las condiciones de no negatividad).
Adicionalmente el costo reducido de las variables
no básicas también es mayor o igual a cero, por
tanto estamos frente a la solución óptima del probl
Conclusión
 el valor óptimo es V(P)=100 que se obtendría al
evaluar la solución óptima del problema en la
función objetivo, sin embargo, en el
procedimiento dicho valor se obtiene con signo
cambiado.
 El ejemplo anterior nos permitió apreciar cómo
a través del Método Simplex Dual se puede
abordar la resolución de un modelo de
Programación Lineal que luego de ser llevado a
la forma estándar no provee una solución
básica factible inicial.