DUALIDAD

Dualidad en Programación Lineal.

• La Dualidad en Programación Lineal tiene su esencia en el hecho de existir
dos modelos lineales cuando se ha planteado sólo uno para resolver un
problema específico. Cuando se obtiene la solución de uno, se está
obteniendo también la solución del otro.
• Este posee importantes relaciones y propiedades respecto al problema
primal que pueden ser de gran beneficio para la toma de decisiones.
• La solución de un modelo dual permite obtener interesantes resultados,
relativos al análisis de sensibilidad de los términos independientes. Para los
rangos de valores de los términos independientes para los que se mantiene
la base optima, la solución del dual nos permite conocer el precio sombra de
la restricción, que será la variación de la función objetivo por unidad
incrementada del término independiente de la restricción.
 FORMULACION DEL PROBLEMA DUAL
• Hemos visto como la programación lineal puede ser usada para
resolver una extensa variedad de problemas propios de los negocios, ya
sea para maximizar utilidades o minimizar costos.
• La solución óptima del problema de programación dual, proporciona la
siguiente información respecto del problema de programación original:
1. La solución óptima del problema dual proporciona los precios en el
mercado o los beneficios de los recursos escasos asignados en el problema
original.
2. La solución óptima del problema dual aporta la solución óptima del
problema original y viceversa.
• Normalmente llamamos al problema de programación lineal original el
problema de programación primal.
DEFINICION DEL PROBLEMA DUAL
• El problema dual es una programación lineal definida en forma directa y
sistemática a partir del modelo original (o primal) de programación lineal.
Los dos problemas están relacionados en forma tan estrecha que la
resolución óptima de un problema produce en forma automática la
resolución óptima del otro.
• Para nuestra definición del problema dual se requiere expresar el problema
primal en forma de ecuaciones, todas las restricciones son ecuaciones, con
lado derecho no negativo y todas las variables son no negativos. Este
requisito es consistente con el formato de tabla de inicio simple. En
consecuencia, todo resultado obtenido a partir de la solución primal optima
se aplican en forma directa al problema asociado.
 ¿CÓMO CONVERTIR UN PROBLEMA
PRIMAL A DUAL?
Un problema dual se formula de un problema primal de la siguiente forma:
1. Si el primal es un problema de maximización su dual será un problema de
minimización y viceversa.
2. Los coeficientes de la función objetivo del problema primal se convierten en los
coeficientes del vector de la disponibilidad (coeficientes de lado derecho) en el
problema dual.
3. Los coeficientes del vector de disponibilidad del problema original se convierten
en los coeficientes de la función objetivo (vector de costo o precio) en el problema
dual.
4. Los coeficientes de las restricciones en el problema primal, será la matriz de los
coeficientes tecnológicos en el dual.
5. Los signos de desigualdad del problema dual son contrarios a los del primal.
6. Cada restricción en un problema corresponde a una variable en el otro problema.
Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m
variables. Así, las variables Xn del primal se convierten en nuevas variables Ym
en el dual.
 Variables primales
Segundo X1 X2 .. Xj .. Xn
miembro de
restricciones
duales C1 C2 .. Cj .. Cn

Coef. del a11 a12 .. a1j .. a1n b1 y1

primer a21 a22 .. a2j .. a2n b2 y2
miembro de Variable
las .. .. .. .. .. .. .. dual
restricciones .. .. .. .. .. .. ..
duales
am1 am2 .. amj .. amn bm ym

j-ésima Funcción
restricción objetivo del
dual dual
Dualidad para PL de Maximización

PPL Primal PPL Dual

Maximizar Z = CtX Minimizar W = btY

s.a. AX <b s.a. AtY > C
X >0 Y > 0
b >0
Dualidad para PL de Minimización

PPL Primal PPL Dual

Minimizar Z = CtX Maximizar W = btY

s.a. AX >b s.a. AtY < C
X >0 Y > 0
b >0
 CONDICION FUNDAMENTAL

Tanto en un problema de programación lineal de

maximización como de minimización, la solución
óptima de la forma primal debe ser igual a la
solución óptima de la forma dual respectiva

Z* = W*

Observación:
La forma dual de un problema dual,
equivale a la forma primal del problema
COMPARACION PRIMAL – DUAL

PPL Primal PPL Dual El PPL dual puede

simplificar la resolución
Ct ( 1 x n ) C (n x 1) del problema si es que el
X (n x 1) Y (m x 1) número de ecuaciones
A (m x n) At ( n x m ) de la forma primal es muy
b (m x 1) bt ( 1 x m ) grande

m – restricciones
PPL Primal
n – incógnitas

n – restricciones
PPL Dual
m – incógnitas
 Reglas de Obtención de Dual
• Si el modelo está escrito de forma canónica, el dual resulta singularmente fácil
de obtener; si se trata de obtener el dual del dual, se obtendrá el primal, siendo
así se trata de una correspondencia biunívoca.
• De forma general las reglas para obtener el dual en cualquier modelo lineal se
indican de la siguiente forma.
EJEMPLO
Llevar el siguiente Máx Z = 5X1 + 2X2 – X3
PPL a su forma
dual s.a. 2X1 + X2 + 3X3 < 8
4X1 + 2X2 + X3 < 20
X1 + X2 > 3
X1 , X2 , X3 > 0
La forma primal
del PPL anterior Máx Z = 5X1 + 2X2 – X3
es:
s.a. 2X1 + X2 + 3X3 < 8
4X1 + 2X2 + X3 < 20
– X1 – X2 < –3
X1 , X2 , X3 > 0
Finalmente, la forma dual queda así:

Mín W = 8Y1 + 20Y2 – 3Y3

s.a. 2Y1 + 4Y2 – Y3 > 5

Y1 + 2Y2 – Y3 > 2
3Y1 + Y2 > –1
Y1 , Y2 , Y3 > 0
Características de la Solución del Dual y
del Primal
• Existen algunas de las propiedades de interés a cerca de
las soluciones del dual y el primal.
• Si el primal tiene solución óptima acotada x*, el dual también
tendrá solución óptima acotada u*, ambas soluciones darán el
mismo valor de la función objetivo. c´x* = b´u*
• Si uno de los dos problemas tiene óptimo no acotado, el otro
solo tendrá solución, la región factible será un conjunto vacío.
• Si uno de los dos problemas no tiene solución, el otro puede
obtener óptimo no acotado, o tampoco tener solución.
 RELACIONES PPL PRIMAL – DUAL

Dado que ambos PPL obtienen la misma solución

óptima ( Z * = W * ), existen relaciones que permiten
explicar la dualidad de cada problema

Es decir que, a partir de la tabla

de la solución óptima del PPL
primal (dual) es posible construir
la tabla de la solución óptima del
PPL dual (primal), haciendo uso
de los teoremas sobre dualidad
 Principio de soluciones Básicas complementarias
Cada solución básica del PPL primal está asociada con una solución básica
de su PPL dual, y viceversa; de acuerdo a la asociación que hay entre las
variables respectivas, que está dada por:

Las variables de problema del PPL dual (primal)

se corresponden, una a una,
con las variables de holgura del PPL primal (dual)

variables de problema del variables de holgura del

PPL primal PPL primal

X1 X2 Xn Xn+1 Xn+2 Xn+m

Ym+1 Ym+2 Ym+n Y1 Y2 Ym

variables de holgura del variables de problema del
PPL dual PPL dual
En cada iteración, las variables que forman la solución básica del PPL
primal (dual) se corresponden con las variables que no forman parte de la
solución básica del PPL dual (primal)

En cada XJ = YJ
iteración
XJ = YJ
• Una vez formulado el problema dual, debemos encontrar su
solución, el método a emplear será el denominado Método
Dual-Simplex el cuál empieza con una solución óptima o
mejor que óptima, pero no factible y se mueve hacia el
óptimo mediante iteraciones que mejoran su factibilidad
conservando su optimalidad. Fíjese que es lo contrario al
método Simplex, en donde se empieza mediante una
solución factible pero no óptima y mediante iteraciones se
mejora la optimalidad, conservando la factibilidad.
Las reglas para el método simplex dual son muy parecidas a las del
método simplex. De hecho, una vez que se inician, la única diferencia
entre ellos es el criterio para elegir las variables que entran y salen y la
regla para detener el algoritmo.
Para dar inicio al método simplex dual todos los coeficientes en la
ecuación (0) deben ser no negativos (de manera que la solución básica
sea super-óptima). El método continua haciendo que el valor de la
función objetivo disminuya, y conserva siempre coeficientes no
negativos en la ecuación (0), hasta que todas las variables sean no
negativas.
Resumen del Método Simplex Dual
Paso inicial: Se introducen las variables de holgura
necesarias para construir un conjunto de ecuaciones que
describan el problema.
Se encuentra una solución básica tal que los coeficientes de
la ecuación (0) sean ceros para las variables básicas y no
negativos para las variables no básicas. Se lleva acabo la
prueba de optimalidad.

Paso iterativo:
Parte 1

Se determina la variable básica que sale de la base,

seleccionando aquella que tenga el valor negativo más
grande en valor absoluto.
Parte 2
Se determina la variable básica que entra a la base:
Se elige a aquella cuyo coeficiente en la ecuación (0) llegue primero a cero
al agregar a la ecuación cero un múltiplo creciente de la ecuación que
contiene a la variable básica que sale.

Esta elección se hace examinando las variables no básicas con

coeficientes negativos en esa ecuación (la que contiene la variable básica
que sale) y escogiendo la que tiene el cociente más pequeño dado por el
coeficiente de la ecuación (0) entre el valor absoluto del coeficiente en esa
ecuación.

Parte 3 Se determina la nueva solución básica: se comienza con el conjunto

actual de ecuaciones y se despejan las variables básicas en términos de las
no básicas mediante el método de eliminación de Gauss–Jordan.
1) Base Super - Optima de Partida:
El vértice de partida de
Z
la primera iteración no
 XJ
< 0 b >0
debe ser factible

2) Criterio de Salida de la Base:

Sale aquella variable Xj que tenga el valor más negativo en
el 2º miembro del cuadro de iteración

Máx { I ( ( AJ)-1 b ) j < 0 I }, j J

3) Criterio de Entrada a la Base:
Es análogo (transpuesto) al criterio de salida del método
simplex tradicional. Sale el mínimo valor del siguiente
cociente, donde sólo se permite evaluar a los
denominadores negativos

Mín
( coeficiente ecuación cero ) j
coeficiente ecuación ,j J
variable saliente < 0

4) Optimalidad:
La primera solución factible indica solución óptima
CONDICION DE FACTIBILIDAD.
• La variable que sale es la variable básica que tiene el valor más
negativo (los empates se rompen arbitrariamente si todas las variables
básicas son negativas, el proceso termina y esta última tabla es la
solución óptima factible).

CONDICION DE OPTIMIDAD.
• La variable que entra se elige entre las variables no básicas como
sigue. Tome los cocientes de los coeficientes de la función objetivo
entre los coeficientes correspondientes a la ecuación asociada a la
variable que sale.

• Ignore los cocientes asociados a denominadores positivos o cero.

• La variable que entra es aquella con el cociente más pequeño si el

problema es de minimizar o el valor absoluto más pequeño si el
problema es de maximización (rompa los empates arbitrariamente). Si
los denominadores son ceros o positivos el problema no tiene ninguna
solución factible.
 METODO SIMPLEX – DUAL
Resuelve un PPL a partir de las relaciones primal – dual, pero
trabajando con bases super – óptimas, es decir iterando
vértices que están afuera del conjunto convexo o región de
puntos factibles

Es decir que itera bases no

factibles, pero cuando alcanza la
primera solución factible,
inmediatamente ésta última es la
solución óptima del problema
 EJEMPLO ( SIMPLEX – DUAL )
Resolver el siguiente PPL mediante el método simplex – dual

Mín Z = 3X1 + 4X2 + 5X3

s.a. X1 + 2X2 + 3X3  5
2X1 + 2X2 + X3  6
X1, X2, X3  0

Antes de emplear el método simplex – dual, se necesita la forma

estándar del PPL
PPL estándar:
Máx - Z = – 3X1 – 4X2 – 5X3 – 0X4 – 0X5 Simplex – dual requiere
s.a. X1 + 2X2 + 3X3 – X4 = 5 un vértice no factible de
2X1 + 2X2 + X3 – X5 = 6 partida, luego hay que
multiplicar las restricciones
X1, X2, X3, X4 , X5  0
por (– 1)
PPL estándar, listo para iteraciones simplex – dual:

Máx - Z + 3X1 + 4X2 + 5X3 + 0X4 + 0X5 = 0

s.a. – X1 – 2X2 – 3X3 + X4 = –5

– 2X1 – 2X2 – X3 + X5 = –6
X1 , X2 , X3 , X4 , X5 ≥ 0

Ahora, es posible elaborar el cuadro simplex

1ª Iteración: XJ1 = { X4 , X5 }
XJ1 = { X1 , X2 , X3 }
Primero buscamos la variable que sale de las VB con el valor mas negativo (ver coef. Lado
derecho: {-5; -6})
Segundo – buscamos que entra, según el valor mas pequeño del cociente entre el reglón Z y
reglón de la variable que sale.
Máx { I ( ( AJ)-1 b ) j < 0 I } = X5 Sale X5
Entra

Base Ec. nº - Z X1 X2 X3 X4 X5 2º miembro

-Z 0 1 3 4 5 0 0 0
Sale

X4 1 0 -1 -2 -3 1 0 -5
X5 2 0 -2 -2 -1 0 1 -6
Para ver quien entra:
3 , 4 , 5 3 Entra X1
Mín - 2 - 2 - 1 = -2
 F2 (- 1/2) F02 (- 3) F12 (- 1)
2ª Iteración: XJ2 = { X1 , X4 }
XJ2 = { X2 , X3 , X5 }

Base Ec. nº - Z X1 X2 X3 X4 X5 2º miembro

-Z 0 1 0 1 7/2 0 3/2 -9
X4 1 0 0 -1 - 5/2 1 - 1/2 -2
X1 2 0 1 1 1/2 0 - 1/2 3

Unico { I ( ( AJ)-1 b ) j < 0 I } = X4 Sale X4

 Para ver quien entra:
1 , 7/2 , 3/2 1
Mín - 1 - 5/2 - 1/2 = -1
Entra X2

Entra

Base Ec. nº - Z X1 X2 X3 X4 X5 2º miembro

Sale

-Z 0 1 0 1 7/2 0 3/2 -9
X4 1 0 0 -1 - 5/2 1 - 1/2 -2
X1 2 0 1 1 1/2 0 - 1/2 3

F1 (- 1) F01 (- 1) F21 (- 1)
2ª Iteración: XJ3 = { X1 , X2 }
XJ3 = { X3 , X4 , X5 }

Base Ec. nº - Z X1 X2 X3 X4 X5 2º miembro

-Z 0 1 0 0 1 1 1 - 11
X2 1 0 0 1 5/2 - 1 1/2 2
X1 2 0 1 0 -2 1 -1 1

Como ( ( AJ)-1 b ) j >0 ,

A
j J
Entonces se halló la solución óptima del problema
 Z
Además J
A
 XJ
< 0 , j
j

Comprueba que la solución básica factible es óptima

X1 1
XJ X2 2 Solución
X* = XJ = X3
= óptima
0
X4 0 Z * = 11
X5 0
 Ejemplo Simplex Dual
• Considere el siguiente modelo de Programación Lineal:

Max: 200 x1 + 150 x2 +120 x3

s.a. 15x1 +7.5x2 + 5x3  315
2x1 + 3x2 + 2x3  110
x1 + x2 + x3  50
x1, x2, x3  0

• 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. De esta forma se
obtiene la siguiente tabla inicial.
VB A B C S1 S2 S3
S1 -15 -2 -1 1 0 0 -200
S2 -7,5 -3 -1 0 1 0 -150
S3 -5 -2 -1 0 0 1 -120
- Z* 315 110 50 0 0 0 0
• 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 cociente, por tanto A
entra a la base

VB A B C S1 S2 S3
S1 -15 -2 -1 1 0 0 -200
S2 -7,5 -3 -1 0 1 0 -150
S3 -5 -2 -1 0 0 1 -120
- Z* 315 110 50 0 0 0 0
• 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:

VB A B C S1 S2 S3
S1 1 2/15 1/15 -1/15 0 0 40/3
S2 0 -2 -1/2 -1/2 1 0 -50
S3 0 -4/3 -2/3 -1/3 0 1 -160/3
- Z* 0 68 29 21 0 0 -4.200
• Paso 4: Continuar las iteraciones y siguiendo el mismo
procedimiento hasta disponer de una solución básica
factible. Luego de unas iteraciones se obtiene la siguiente
tabla final:
A B C S1 S2 S3
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 celeste) con valor óptimo
V(P)=6.620 (marcado en amarillo - se obtiene con signo cambiado). También es
interesante notar que los costos reducidos de las variables artificiales S1, S2 y S3
(marcado en verde), corresponde a la solución óptima del modelo
Caso donde se encuentra una restricción restrictiva

MAX Z = -2X1 + 3X2

Sujeto a las siguientes restricciones
1X1 + 2X2 < 12
4X1 - 2X2 > 3
6X1 - 1X2 = 10
X1, X2 > 0

1. convertir las restricciones > en una restricción equivalente

< multiplicando por (-1) ambos lados.
4X1 - 2X2  3 (-1) - 4X1 + 2X2  - 3

2. para las restricciones de igualdad, se deben obtener dos restricciones de

desigualdad una de forma < y la otra de forma > ; después regresar al
punto anterior y cambiar la restricción > a la forma < .
6X1 - 1X2 < 10
6X1 - 1X2 < 10 (-1)

6X1 - 1X2 < 10

-6X1 + 1X2  - 10
Así el problema primal se ha replanteado en la forma equivalente:
MAX Z = -2X1 + 3X2
MAX Z = -2X1 + 3X2
Sujeto a: Sujeto a las siguientes restricciones
1X1 + 2X2 < 12
X1 + 2X2 < 12 4X1 - 2X2 > 3
-4X1 + 2X2 < -3 6X1 - 1X2 = 10
6X1 - X2 < 10 X1, X2 > 0
-6X1 + X2 < -10
X1, X2 > 0
Teniendo el problema primal convertido a la forma canónica de un
problema de maximización, es fácil llevarlo al problema dual.
MIN Z = 12Y1 - 3Y2 + 10Y3 -10Y4

Sujeto a:
Y1 - 4Y2 + 6Y3 - 6Y4 > - 2
2Y1 + 2Y2 - Y3 + Y4 > 3
Y1, Y2, Y3, Y4 > 0
EJERCICIO PROBLEMA DUAL

Si el problema primal es:

MIN Z = 2X1 + 3X2
Sujeto a:
X1 > 125
X1 + X2 > 350
2X1 + X2 < 600 (-1)
X1, X2 > 0

Se pasa a la forma canónica

MIN Z = 2X1 + 3X2
Sujeto a:
X1 > 125
X1 + X2 > 350
-2X1 - X2 > -600
X1, X2 > 0

El problema dual será:

MAX Z* = 125Y1 + 350Y2 - 600Y3
Y1 + Y2 - 2Y3 < 2
Y2 - Y3 < 3
Y1, Y2 > 0
• Formato estándar
MAX Z* = 125Y1 + 350Y2 - 600Y3
Y1 + Y2 + 2Y3 + S1 = 2
Y2 + Y3 + S2 = 3
Y1, Y2, Y3, S1, S2 > 0
Igualar la función objetivo a cero
MAX Z* = 125Y1 + 350Y2 - 600Y3 + 0S1 + 0S2
Z* = 125Y1 + 350Y2 - 600Y3 + 0S1 + 0S2

Z* - 125Y1 - 350Y2 + 600Y3 - 0S1 - 0S2 = 0

Ejemplo
Maximizar – Z = – 4y1 – 12y2 – 18y3
Sujeta a:
y1 + 3y3  3
2y2 + 2y3  5
y1  0 , y2  0 , y3  0

Agregando variables de holgura

– Z + 4y1 + 12y2 + 18y3 = 0

– y1 – 3y3 + y4 = – 3
– 2y2 – 2y3 + y5 = – 5
Ejemplo
Resolver por el método simplex-dual el siguiente problema
lineal.

Mínimizar Z = 2X1 + X2

Sujeto a 3X1 + X2  3
4X1 + 3X2  6
X1 + 2X2  3
X 1  0 , X2  0
Máximizar – Z = – 2X1 – X2

Sujeto a
– 3X1 – X2 + X3 = – 3
– 4X1 – 3X2 + X4 = – 6
– X1 – 2X2 + X5 = – 3

X1  0 , X2  0 , X3  0 , X4 0 , X5  0
 Tabla Simplex-Dual

Coeficiente de

Iteración
Variable Número Lado
Básica Ecuación Z X1 X2 X3 X4 X5 Derecho
-1 2 1 0 0 0 0
Z 0
0 -3 -1 1 0 0 -3
X3 1
0
0 -4 -3 0 1 0 -6
X4 2
0 -1 -2 0 0 1 -3
X5 3
 Tabla Primera Iteración

Coeficiente de

Iteració Número
n Variable Ecuació Lado
Básica n Z X1 X2 X3 X4 X5 Derecho
-1 2/3 0 0 1/3 0 -2
Z 0
0 -1 2/3 0 1 - 1/3 0 -1
X3 1
1
0 1 1/3 1 0 - 1/3 0 2
X2 2
0 1 2/3 0 0 - 2/3 1 1
X5 3
 Tabla Segunda Iteración

Coeficiente de

Número
Iteración Variable Ecuació Lado
Básica n Z X1 X2 X3 X4 X5 Derecho
Z 0 -1 0 0 2/5 1/5 0 -2 2/5

X1 1 0 1 0 - 3/5 1/5 0 3/5

2
X4 2 0 0 1 4/5 - 3/5 0 1 1/5

X5 3 0 0 0 1 -1 1 0
 Tabla Final

Coeficiente de

Iteración Variable Número Lado

Básica Ecuación Z X1 X2 X3 X4 X5 Derecho
Z 0 -1 2 1 0 0 0 0
X3 1 0 -3 -1 1 0 0 -3
0
X4 2 0 -4 -3 0 1 0 -6
X5 3 0 -1 -2 0 0 1 -3

Z 0 -1 2/3 0 0 1/3 0 -2
X3 1 0 -1 2/3 0 1 - 1/3 0 -1
1
X2 2 0 1 1/3 1 0 - 1/3 0 2
X5 3 0 1 2/3 0 0 - 2/3 1 1

Z 0 -1 0 0 2/5 1/5 0 -2 2/5

X1 1 0 1 0 - 3/5 1/5 0 3/5
2
X2 2 0 0 1 4/5 - 3/5 0 1 1/5
X5 3 0 0 0 1 -1 1 0
Ejemplo
CONCLUSION
Observe que en el Dual – Simplex se hizo uso de la regla de equivalencia,
multiplicando la función objetiva por (-1), y al final, nuevamente se multiplicó el
valor de Z por (-1).
•En cada iteración del Método Simplex se muestra que:
1. Los Zj – Cj de las variables de holgura X3, X4, X5 (Z3-C3 , Z4-C4 , Z5-C5) son
los valores de las variables reales del Dual (Y1,Y2,Y3).
2. Los Zj – Cj de las variables reales X1,X2 (Z1-C1 , Z2-C2) son los valores de las
variables de holgura del Dual (Y4,Y5)
•En cada iteración del Método Dual – Simplex se muestra que:
1. Los Zj – Cj de las variables de holgura Y4,Y5 (Z4-C4 , Z5-C5) son los valores
de las variables reales del problema principal (X1,X2)
2. Los Zj – Cj de las variables reales Y1,Y2 ,Y3 (Z1-C1 , Z2-C2 , Z3-C3) son los
valores de las variables de holgura del problema principal (X3,X4,X5)
 INTERPRETACION ECONOMICA DE LA
SOLUCION OPTIMA DEL PPL - DUAL
Para determinados PPL de maximización de beneficios con
restricciones de recursos limitados (coeficientes técnicos y capacidades
máximas de los recursos) y bajo condiciones de competencia perfecta
(sin restricciones de demanda: se puede vender una cantidad ilimitada de
bienes al precio dado), se tiene que:

Z* = W*
W* = Z*
W* = b1Y1* + b2Y2* + b3Y3* + ……… + bmYm*
Z* = b1Y1* + b2Y2* + b3Y3* + ……… + bmYm*
donde m: número de restricciones en el PPL primal

Aplicando derivadas parciales respecto a cada bj, considerando a cada bj

como una variable, sólo en el óptimo y en la medida que la variación de
cada bj sea marginal, insuficiente para variar la base óptima
 W*  Z*
 b1 = Y1* =  b1

 W*  Z*
 b2
= Y2* =  b2
bj: recursos, disponibilidad
insumos, capacidades máximas

 W*  Z*
 bm = Ym* =  bm

En general: j: 1 m

 W*  Z*
 bj
= Yj* =  bj
 PRECIO SOMBRA

Yj* Es el precio máximo implícito del recurso j – ésimo

dada la solución óptima actual

Es el precio máximo que se estaría dispuesto a pagar por

adquirir una unidad adicional del recurso j – ésimo, por sobre
el precio unitario actual de dicho recurso
EJEMPLO
Una empresa fabrica dos bienes: 1 y 2, los que se venden a
$500 y $600 respectivamente, bajo condiciones de
competencia perfecta. Ambos bienes tienen un costo unitario
de $200 y para su fabricación deben compartir el uso de tres
departamentos de procesos, los que requieren la siguiente
cantidad de bienes:
Bien 1 Bien 2
Departamento 1 4 5
Departamento 2 2 5
Departamento 3 1 10
Además, cada departamento tiene una capacidad máxima de horas de
trabajo al mes, que es de 200, 150 y 250, para los departamentos de
procesos 1, 2 y 3 respectivamente

Se Pide:
Demostrar el precio sombra de cada uno de los 3 recursos e interpretar
económicamente sus respectivos significados
 PLANTEO DEL PPL ( EJEMPLO )
Variable de Decisión: Xi, cantidad del bien i - ésimo a elaborar
Máx Z = 300X1 + 400X2
s.a. 4X1 + 5X2 ≤ 200
2X1 + 5X2 ≤ 150
X1 + 10X2 ≤ 250
X1 , X2 ≥ 0

Este PPL corresponde al ejemplo desarrollado para explicar las relaciones

entre los cuadros óptimos primal – dual, por lo que ya se conoce su
solución
PLANTEAMIENTO DE PPL DUAL
Mín W = 200Y1 + 150Y2 + 250Y3
s.a. 4Y1 + 2Y2 + Y3 ≥ 300
5Y1 + 5Y2 + 10Y3 ≥ 400
Y1 , Y2 , Y3 ≥ 0
 variables de problema del variables holgura del
PPL primal PPL primal

X1 X2 X3 X4 X5
Principio de
soluciones básicas
complementarias en
el ejemplo Y4 Y5 Y1 Y2 Y3

variables de holgura del variables problema

PPL dual del PPL dual
SOLUCION PPL DUAL
Cuadro óptimo PPL dual (tras las iteraciones)

Base Ec. nº - W Y1 Y2 Y3 Y4 Y5 2º miembro

-W 0 1 0 0 25 25 20 - 15500
Y1 1 0 1 0 - 3/2 -1/2 1/5 70
Y2 2 0 0 1 7/2 1/2 - 2/5 10
W
Además J
A
< 0 , j
 YJ j
Solución
Comprueba que la solución básica factible es óptima
óptima
Y1 70
YJ Y2 10 W * = 15500
Y* = = =
YJ Y3 0
Y4 0
Y5 0
SOLUCION PPL PRIMAL
Cuadro óptimo PPL primal (tras las iteraciones)

Base Ec. nº Z X1 X2 X3 X4 X5 2º miembro

Z 0 1 0 0 70 10 0 15500
X1 1 0 1 0 1/2 -1/2 0 25
X2 2 0 0 1 - 1/5 2/5 0 20
X5 3 0 0 0 3/2 -7/2 1 25
DEMOSTRAR PRECIO SOMBRA
• Análisis para Y1* = 70  Z*
Y1* =  b1
Se busca ver qué ocurre con la función objetivo si es que aumenta la
disponibilidad del recurso 1 (horas en el departamento 1) en una unidad
Matriz inicial Matriz final
201 como XJ = { X1, X2, X5 } (ultima tabla)
(primera tabla)
b’ = 150
4 5 0 1/2 - 1/2 0
250
2 5 0 (AJ)-1 = - 1/5 2/5 0
AJ =
1 10 1 3/2 - 7/2 1
51/2 Z * ’ = 300X1 + 400X2
(AJ)-1 b’ = 99/5 Z * ’ = 300(51/2) + 400(99/5)
53/2 Z * ’ = 15570
como Z * = 15500  Z * = 70 = Y1*
Se está dispuesto a pagar como máximo $70 por una unidad adicional
de horas en el departamento 1, bajo condiciones de competencia perfecta
(todo lo que se produce se vende, al precio de equilibrio en el mercado)
• Análisis para Y2* = 10  Z*
Y2* =  b2
Se busca ver qué ocurre con la función objetivo si es que aumenta la
disponibilidad del recurso 2 (horas en el departamento 2) en una unidad
200 como XJ = { X1, X2, X5 }
b’ = 151
4 5 0 1/2 - 1/2 0
250
AJ = 2 5 0 (AJ)-1 = - 1/5 2/5 0
1 10 1 3/2 - 7/2 1

49/2 Z * ’ = 300X1 + 400X2

(AJ)-1 b’= 102/5 Z * ’ = 300(49/2) + 400(102/5)
43/2 Z * ’ = 15510

como Z * = 15500  Z * = 10 = Y2*

Se está dispuesto a pagar como máximo $10 por una unidad adicional
de horas en el departamento 2, bajo condiciones de competencia perfecta
(todo lo que se produce se vende, al precio de equilibrio en el mercado)
• Análisis para Y3* = 0  Z*
Y2* =  b3
Se busca ver qué ocurre con la función objetivo si es que aumenta la
disponibilidad del recurso 3 (horas en el departamento 3) en una unidad
200
como XJ = { X1, X2, X5 }
b’ = 150
251 4 5 0 1/2 - 1/2 0
AJ = 2 5 0 (AJ)-1 = - 1/5 2/5 0
1 10 1 3/2 - 7/2 1

25 Z * ’ = 300X1 + 400X2
(AJ)-1 b’ = 20 Z * ’ = 300(25) + 400(20)
26 Z * ’ = 15500

como Z * = 15500  Z* = 0 = Y3*

No se está dispuesto a pagar valor alguno por una unidad adicional de
horas en el departamento 3, bajo condiciones de competencia perfecta (todo
lo que se produce se vende, al precio de equilibrio en el mercado)
• Análisis para Y3* = 0
De hecho, antes del análisis ya sobran 25 horas del departamento 3,
pues es una variable de holgura en el PPL primal

Luego, disponer de una unidad adicional de este recurso no reporta

beneficio alguno, consiguiendo tan solo que el excedente de horas en
el departamento 3 suba de 25 a 26
OBSERVACION
Las variables de holgura que forman parte de la solución óptima en el
PPL primal, tienen siempre en su recurso asociado un precio sombra
igual a cero, pues el hecho de que sean variables de holgura activas
en la solución óptima implica que no aportan a la maximización de
beneficios de la función objetivo
 Importancia de la Dualidad en Programación
Lineal
• La dualidad es importante por el hecho de que es equivalente resolver un
problema a resolver su dual. Ello es debido a que los precios sombra de
dual son las soluciones de problemas y viceversa. Así, en ocasiones,
puede resultar conveniente obtener las soluciones de problemas a partir
de los precios sombra de dual en vez de resolver problemas directamente.
• La resolución de los problemas duales respecto a los primales se justifica
dada la facilidad que se presenta dados problemas donde el número de
restricciones supere al número de variables. Además de tener gran
aplicación en el análisis económico del problema.
Ventajas y Desventajas de la Dualidad.
• Una de las ventajas de la existencia del programa dual es la posibilidad
de reducir el esfuerzo computacional al resolver ciertos modelos de
programación lineal.
• Permite resolver problemas de programación lineal de forma más rápida y
sencilla.
• Es otra vía para resolver un problema de programación lineal.
• Facilita profundizar en el contenido económico del problema original (primal).
• Puede ser utilizada para resolver el caso en que se debe considerar la
introducción de una nueva variable en el primal una vez que ha de sido
obtenida la solución óptima, sin tener que resolver completamente el
problema.
• Otra de las ventajas que presenta es que dado a que el número de
restricciones y variables entre problema dual y primal es inverso, se pueden
resolver gráficamente problemas que presenten dos restricciones sin
importar el número de variables.
• Una desventaja de este método, es que se requiere para empezar
a iterar la condición de factibilidad dual.
 TEOREMA DE DUALIDAD DEBIL
Si X’ es una solución factible cualquiera de un PPL primal e Y’ es su
solución factible correspondiente en su PPL dual, entonces:

Z’ = CtX’ < btY’ = W’

CtX’ < btY’ Z’ < W’

El valor de W para cualquiera solución factible del PPL dual, entrega

una cota superior para Z

Por lo tanto, el máximo valor de Z puede ser a lo más, igual al mínimo

valor de W
 TEOREMA DE DUALIDAD FUERTE
Si X’ es una solución factible cualquiera de un PPL primal e Y’ es su
solución correspondiente en su PPL dual, y además Z’ = W’ (sus
funciones objetivo tienen el mismo valor), entonces ambas soluciones son
óptimas

Z’ = Z*
Si Z’ = W’
W’ = W*
Se halló la solución óptima del PPL primal y también se halló la solución
óptima del PPL dual
 COMENTARIOS
• El teorema débil de dualidad implica que si el primal
tiene solución ilimitada, entonces el dual no tiene
solución.
• Del mismo modo, si el dual tiene solución ilimitada,
entonces el primal no tiene solución.
• No obstante, es posible que ni el primal ni el dual tengan
solución.
• Cada componente de x se corresponde con una variable
de exceso del dual.
• Cada componente de y se corresponde con una variable
de holgura del primal.
Obtención de la Solución Dual.
• El dual de un modelo lineal es otro modelo lineal que
puede solucionarse después de las oportunas
trasformaciones, si alguna de las variables resultantes
es no negativa o no restringida en signo, del mismo
modo que el primal, sin embargo puede obtenerse la
solución del dual resolviendo el primal. Existen dos
modos de obtener una solución óptima del dual:
• A partir de la tabla simplex optima del primal, la solución
obtenida nos permitirá tener un importante resultado. El
teorema de la holgura complementaria.
RELACIONES DE CUADROS OPTIMOS PRIMAL–DUAL
Máx Z = 300X1 + 400X2
PPL primal
original
s.a. 4X1 + 5X2  200
2X1 + 5X2  150
X1 + 10X2  250
X1 , X2  0

Mín W = 200Y1 + 150Y2 + 250Y3

PPL dual
original

s.a. 4Y1 + 2Y2 + Y3  300

5Y1 + 5Y2 + 10Y3  400
Y1 , Y2 , Y3  0

Antes de ver las relaciones de las tablas óptimos, se requieren las formas estándar de
ambos PPL, para trabajar con el método simplex hasta llegar a los respectivos cuadros
óptimos
PPL primal estándar

Máx Z = 300X1 + 400X2 + 0X3 + 0X4 + 0X5

s.a. 4X1 + 5X2 + X3 = 200
2X1 + 5X2 + X4 = 150
X1 + 10X2 + X5 = 250
X1 , X2 , X3 , X4 , X5 > 0
PPL dual estándar

Mín W = 200Y1 + 150Y2 + 250Y3 + 0Y4 + 0Y5

s.a. 4Y1 + 2Y2 + Y3 – Y4 = 300
5Y1 + 5Y2 + 10Y3 – Y5 = 400
Y1 , Y2 , Y3 , Y4 , Y5 > 0
Cuadro óptimo PPL primal (tras las iteraciones)
Base Ec. nº Z X1 X2 X3 X4 X5 2º miembro
Z 0 1 0 0 70 10 0 15500
X1 1 0 1 0 1/2 -1/2 0 25
X2 2 0 0 1 - 1/5 2/5 0 20
X5 3 0 0 0 3/2 -7/2 1 25
Cuadro óptimo PPL dual (tras las iteraciones)

Base Ec. nº - W Y1 Y2 Y3 Y4 Y5 2º miembro

-W 0 1 0 0 25 25 20 - 15500
Y1 1 0 1 0 - 3/2 -1/2 1/5 70
Y2 2 0 0 1 7/2 1/2 - 2/5 10
 1. Las soluciones óptimas de los PPL
Z* W*
primal y dual son iguales =
2. La solución óptima del PPL primal W
XJ* =
(dual) coincide con el vector de  YJ
costos reducidos o derivadas
parciales ecuación cero del PPL dual Z
YJ* =
(primal)  XJ
3. Las variables básicas en el PPL primal
(dual) son variables no básicas en el XJ = YJ
PPL dual (primal)
XJ = YJ
Esto resulta por la correspondencia proveniente
del principio de las soluciones básicas
complementarias
 variables de problema del variables holgura del
PPL primal PPL primal

Principio de
X1 X2 X3 X4 X5
soluciones básicas
complementarias en
el ejemplo
Y4 Y5 Y1 Y2 Y3
variables de holgura del variables problema del
PPL dual PPL dual

4. Las columnas en la tabla de los coeficientes que

acompañan a las variables no básicas también poseen
correspondencia entre PPL primal y PPL dual

Esto acontece debido a que en el PPL primal se suman variables de

holgura (la función objetivo maximiza + Z), mientras que en el PPL dual se
restan variables de exceso (la función objetivo maximiza - W)
 Complementariedad
• Teorema de complementariedad: Sean x = (x1, x2, ..., xn),
y = (y1, y2, ..., ym) soluciones factibles del primal y el dual,
respectivamente. Sean (w1, w2, ..., wm) las variables de
holgura correspondientes del primal, y sean (z1, z2, ..., zn)
las variables de exceso correspondientes del dual.
Entonces x e y son óptimas para sus respectivos
problemas si y sólo si xjzj = 0,  j = 1, 2, . . . , n, y además
wiyi = 0,  i = 1, 2, ..., m.
• El teorema de complementariedad nos permite obtener
rápidamente una solución óptima del problema dual si
conocemos una solución óptima del problema primal.
• Para ello, si tenemos que en una solución óptima del primal
xj>0, entonces en el dual zj=0. Además si en la solución
óptima del primal wi>0, entonces en el dual yi=0.
• De esta manera sólo quedarán por determinar los valores
óptimos de unas pocas variables del problema dual.
EJEMPLO
A partir del siguiente cuadro óptimo, construir el cuadro óptimo de su PPL
dual respectivo, si se sabe que el problema original es de 2 variables

Base Ec. nº Z X1 X2 X3 X4 X5 2º miembro

Z 0 1 0 0 4/5 0 12/5 6240
X4 1 0 0 0 - 3/5 1 1/5 520
X2 2 0 0 1 4/5 0 - 3/5 240
X1 3 0 1 0 - 1/5 0 2/5 440
Base Ec. nº Z X1 X2 X3 X4 X5 2º miembro
Z 0 1 0 0 4/5 0 12/5 6240
X4 1 0 0 0 - 3/5 1 1/5 520
X2 2 0 0 1 4/5 0 - 3/5 240
X1 3 0 1 0 - 1/5 0 2/5 440

Principio de
X1 X2 X3 X4 X5
soluciones
básicas
complementarias
Y4 Y5 Y1 Y2 Y3

Base Ec. nº - W Y1 Y2 Y3 Y4 Y5 2º miembro

-W 0 1 0 520 0 440 240 - 6240
Y1 1 0 1 0 4/5
Y3 2 0 0 1 12/5
Base Ec. nº Z X1 X2 X3 X4 X5 2º miembro
Z 0 1 0 0 4/5 0 12/5 6240
X4 1 0 0 0 - 3/5 1 1/5 520
X2 2 0 0 1 4/5 0 - 3/5 240
X1 3 0 1 0 - 1/5 0 2/5 440

Principio de
X1 X2 X3 X4 X5
soluciones
básicas
complementarias
Y4 Y5 Y1 Y2 Y3

Base Ec. nº - W Y1 Y2 Y3 Y4 Y5 2º miembro

-W 0 1 0 520 0 440 240 - 6240
Y1 1 0 1 3/5 0 1/5 - 4/5 4/5
Y3 2 0 0 - 1/5 1 - 2/5 3/5 12/5
 El problema Dual será
Si el problema es primal es MIN Z = 200Y1 + 5000Y2+ 4000Y3
MAX Z = 45X1 + 17X2 + 55X3
Sujeto a las siguientes restricciones:
Sujeto a las siguientes restricciones:
X1 + X2 + X3 < 200 Y1 + 9Y2 + 10Y3 > 45
9X1 + 8X2 + 10X3 < 5000 Y1 + 8Y2 + 7Y3 > 17
10X1 + 7X2 + 21X3 < 4000 Y1 + 10Y2 + 21Y3 > 55
X1, X2, X3 > 0 Y1, Y2, Y3 > 0
Si el problema primal
es
MIN Z = 2X1 + 3X2

Sujeto a
2X1 + X2  16
X1 + 3X2  20
X1 + X2  10
X1, X2  0
Si el problema primal es El problema dual será
MIN Z = 2X1 + 3X2 MAX Z = 16Y1 + 20Y2 + 10Y3

Sujeto a Sujeto a
2X1 + X2  16 2Y1 + Y2 + Y3  2
X1 + 3X2  20 Y1 + 3Y2 + Y3  3
X1 + X2  10 Y1, Y2  0
X1, X2  0
 Interpretación de las Variables Duales
• Cada variable de dual está asociada a una restricción del programa
primal, y su valor óptimo representa el incremento de la función
objetivo del primal por cada unidad que aumente, el término
independiente de dicha restricción, siempre que este último
aumento no suponga un cambio de base.
• Los valores de estas variables se denominan precios sombra; los
precios sombra obtenidos a partir del optimo del dual serán
validos siempre que no varíe la base optima. En consecuencia los
resultados obtenidos del dual están íntimamente ligados al análisis
de sensibilidad de los términos independientes.